Nelinearno programiranje

U matematici, nelinearno programiranje (NLP) je proces rešavanja optimizacionog problema^[1]^[2] gde su neka od ograničenja ili objektivnih funkcija nelinearna. Optimizacioni problem je jedan od proračuna ekstrema (maksimuma, minimuma ili stacionarnih tačaka) jedne objektivne funkcije nad setom nepoznatih realnih promenljivih, koji je uslovljen zadovoljavanjem sistema jednačina i nejednačina, kolektivno zvanih ograničenja. To je potpolje matematičke optimizacije koje se bavi problemima koji nisu linearni.^[3]^[4]^[5]

Primenjivost

Tipični nekonveksni problem je problem optimizacije troškova prevoza selekcijom iz seta transportnih metoda, od kojih jedan ili više manifestuju efekte razmera, s različitim stepenima povezivanja i ograničenjima kapaciteta. Primer bi bio transport naftnih derivata s obzirom na izbor ili kombinaciju cevovoda, željezničkih tankera, cestovnih tankera, rečne barke ili priobalskog broda. Zbog ekonomije veličine šarže, troškovne funkcije mogu imati i diskontinuitete osim glatkih promena.

U eksperimentalnoj nauci neke se jednostavnih analiza podataka (poput uklapanja spektra sa zbirom pikova poznatog položaja i oblika, ali nepoznate magnitude) mogu se obaviti linearnim metodama, ali generalno su i ovi problemi nelinearni. Tipično postoji teorijski model ispitivanog sistema s promenjivim parametrima u njemu, i model eksperimenta ili eksperimenata, koji takođe može da ima nepoznate parametre. Potrebno je da se numerički pronađe najbolje uklapanje. U ovom slučaju se često zahteva izvesna mera preciznosti rezultata, kao i samo najbolje uklapanje.

Definicija

Neka su n, m, i p pozitivni celi brojevi. Neka je X podskup skupa Rⁿ, neka su f, g_i, i h_j funkcije realnih vrednosti na X za svako i u {1, …, m} i svako j u {1, …, p}, pri čemu je bar jedna od f, g_i, i h_j nelinearna.

Problem nelineare minimizacije je problem optimizacije oblika

{\begin{aligned}{\text{minimiziraj }}&f(x)\\{\text{tako da je }}&g_{i}(x)\leq 0{\text{ za svako }}i\in \{1,\dotsc ,m\}\\&h_{j}(x)=0{\text{ za svako }}j\in \{1,\dotsc ,p\}\\&x\in X.\end{aligned}}

Problem nelinearne maksimizacije je definisan na sličan način.

Mogući tipovi seta ograničenja

Postoji nekoliko mogućnosti za prirodu skupa ograničenja, poznatog i pod nazivom izvodljivi skup ili izvodljiva regija. Neizvodljiv je problem za koji nijedan skup vrednosti za izabrane promenljive ne zadovoljava sva ograničenja. To jest, ograničenja su uzajamno kontradiktorna i ne postoji rešenje, te je izvodljivi skup je prazan skup. Izvodljiv je problem za koji postoji barem jedan niz vrednosti za skup izabranih promenljivih koji zadovoljava sva ograničenja. Neograničeni problem je izvodljiv problem za koji se ciljna funkcija može učiniti boljom od bilo koje date konačne vrednosti. Prema tome, ne postoji optimalno rešenje, jer uvek postoji izvodljivo rešenje koje daje bolju vrednost objektivne funkcije od bilo kojeg predloženog rešenja.

Metodi za rešavanje problema

Ako je ciljna funkcija f linearna, a ograničeni prostor politop, problem je problem linearnog programiranja, koji se može rešiti korišćenjem poznatih tehnika linearnog programiranja, kao što je simpleks metoda.

Ako je ciljna funkcija konkavna (problem maksimizacije), ili konveksna (problem minimizacije), i skup ograničenja je konveksan, onda se program naziva konveksnim i opšte metode iz konveksne optimizacije mogu se koristiti u većini slučajeva.

Ako je ciljna funkcija kvadratna, a ograničenja linearna, koriste se tehnike kvadratnog programiranja.

Ako je ciljna funkcija odnos konkavne i konveksne funkcije (u slučaju maksimizacije), a ograničenja su konveksna, onda se problem može transformisati u problem konveksne optimizacije pomoću tehnika frakcijskog programiranja.

Dostupno je nekoliko metoda za rešavanje nekonveksnih problema. Jedan od pristupa je upotreba posebnih formulacija problema linearnog programiranja. Druga metoda uključuje upotrebu tehnika separacije i evaluacije, gde je program podeljen na podklase koje treba rešiti konveksnim (problem minimizacije) ili linearnim aproksimacijama, koje formiraju donju granicu sveukupnih troškova u podelama. S naknadnim podelama, u nekom trenutku će se dobiti stvarno rešenje, čiji je trošak jednak najboljoj donjoj granici dobivenoj za bilo koje od približnih rešenja. Ovo rešenje je optimalno, mada je moguće da nije jedinstveno. Algoritam se takođe može zaustaviti rano, sa sigurnošću da je najbolje moguće rešenje unutar tolerancije od najbolje pronađene tačke; takve tačke se nazivaju ε-optimalnim. Prekid na ε-optimalnim tačkama je obično neophodan da bi se osigurao konačni prekid. Ovo je posebno korisno za velike, teške probleme i probleme sa nepredvidivim troškovima ili vrednostima, gde se neizvesnost može proceniti odgovarajućom procenom pouzdanosti.

Pod pretpostavkama diferencijabilnosti i konstantnih kvalifikacija, Karuš–Kan–Takerovi uslovi (KKT) pružaju potrebne uslove da rešenje bude optimalno. Pod pretpostavkom konveksnosti, ovi uslovi su takođe dovoljni. Ako su neke funkcije nediferencirane, subdiferencijabilne verzije KKT uslova su dostupne.^[6]

Primeri

Dvodimenzioni primer

Jednostavni problem (prikazan na dijagramu) može se definisati pomoću ograničenja

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

sa objektivnom funkcijom koju treba maksimizovati

f(x) = x₁ + x₂

gde je x = (x₁, x₂).

Trodimenzioni primer

Još jedan jednostavan problem (pogledajte dijagram) može se definisati pomoću ograničenja

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

sa objektivnom funkcijom koju treba maksimizovati

f(x) = x₁x₂ + x₂x₃

gde je x = (x₁, x₂, x₃).

Reference

^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. стр. 129. ISBN 978-0-521-83378-3.
^ „How Traffic Shaping Optimizes Network Bandwidth”. IPC. 12. 7. 2016. Приступљено 13. 2. 2017.
^ "The Nature of Mathematical Programming Архивирано 2014-03-05 на сајту Wayback Machine," Mathematical Programming Glossary, INFORMS Computing Society.
^ Martins, Joaquim R. R. A.; Ning, Andrew (2021-10-01). Engineering Design Optimization (на језику: енглески). Cambridge University Press. ISBN 978-1108833417.
^ Du, D. Z.; Pardalos, P. M.; Wu, W. (2008). „History of Optimization”. Ур.: Floudas, C.; Pardalos, P. Encyclopedia of Optimization. Boston: Springer. стр. 1538—1542.
^ Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. стр. xii+454. ISBN 978-0691119151. MR 2199043.

Literatura

Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French изд.). Berlin: Springer-Verlag. стр. xiv+490. ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5.
Luenberger, David G.; Ye, Yinyu (2008). Linear and nonlinear programming. International Series in Operations Research & Management Science. 116 (Third изд.). New York: Springer. стр. xiv+546. ISBN 978-0-387-74502-2. MR 2423726.
Jan Brinkhuis and Vladimir Tikhomirov, Optimization: Insights and Applications, 2005, Princeton University Press
Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge: Cambridge University Press. ISBN 0-521-83378-7.
Gill, P. E.; Murray, W.; Wright, M. H. (1982). Practical Optimization. London: Academic Press. ISBN 0-12-283952-8.
Lee, Jon (2004). A First Course in Combinatorial Optimization. Cambridge University Press. ISBN 0-521-01012-8.
Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd изд.). Berlin: Springer. ISBN 0-387-30303-0.
Snyman, J. A.; Wilke, D. N. (2018). Practical Mathematical Optimization : Basic Optimization Theory and Gradient-Based Algorithms (2nd изд.). Berlin: Springer. ISBN 978-3-319-77585-2.
Hassanzadeh, Hamidreza; Rouhani, Modjtaba (2010). „A multi-objective gravitational search algorithm”. In Computational Intelligence, Communication Systems and Networks (CICSyN): 7—12.
Shirazi, Ali; Najafi, Behzad; Aminyavari, Mehdi; Rinaldi, Fabio; Taylor, Robert A. (2014-05-01). „Thermal–economic–environmental analysis and multi-objective optimization of an ice thermal energy storage system for gas turbine cycle inlet air cooling”. Energy. 69: 212—226. doi:10.1016/j.energy.2014.02.071.
Najafi, Behzad; Shirazi, Ali; Aminyavari, Mehdi; Rinaldi, Fabio; Taylor, Robert A. (2014-02-03). „Exergetic, economic and environmental analyses and multi-objective optimization of an SOFC-gas turbine hybrid cycle coupled with an MSF desalination system”. Desalination. 334 (1): 46—59. doi:10.1016/j.desal.2013.11.039.
Rafiei, S. M. R.; Amirahmadi, A.; Griva, G. (2009). „Chaos rejection and optimal dynamic response for boost converter using SPEA multi-objective optimization approach”. 2009 35th Annual Conference of IEEE Industrial Electronics. стр. 3315—3322. ISBN 978-1-4244-4648-3. S2CID 2539380. doi:10.1109/IECON.2009.5415056.
Ropponen, A.; Ritala, R.; Pistikopoulos, E. N. (2011). „Optimization issues of the broke management system in papermaking”. Computers & Chemical Engineering. 35 (11): 2510. doi:10.1016/j.compchemeng.2010.12.012.
Pllana, Sabri; Memeti, Suejb; Kolodziej, Joanna (2019). „Customizing Pareto Simulated Annealing for Multi-objective Optimization of Control Cabinet Layout”. arXiv:1906.04825  [cs.OH].
Nguyen, Hoang Anh; van Iperen, Zane; Raghunath, Sreekanth; Abramson, David; Kipouros, Timoleon; Somasekharan, Sandeep (2017). „Multi-objective optimisation in scientific workflow”. Procedia Computer Science. 108: 1443—1452. doi:10.1016/j.procs.2017.05.213 . hdl:1826/12173.
Ganesan, T.; Elamvazuthi, I.; Vasant, P. (2015-07-01). „Multiobjective design optimization of a nano-CMOS voltage-controlled oscillator using game theoretic-differential evolution”. Applied Soft Computing. 32: 293—299. doi:10.1016/j.asoc.2015.03.016.
Ganesan, T.; Elamvazuthi, I.; Shaari, Ku Zilati Ku; Vasant, P. (2013-01-01). Zelinka, Ivan; Chen, Guanrong; Rössler, Otto E.; Snasel, Vaclav; Abraham, Ajith, ур. Hypervolume-Driven Analytical Programming for Solar-Powered Irrigation System Optimization. Advances in Intelligent Systems and Computing. Springer International Publishing. стр. 147—154. ISBN 978-3-319-00541-6. doi:10.1007/978-3-319-00542-3_15.
Ganesan, T.; Elamvazuthi, I.; Shaari, Ku Zilati Ku; Vasant, P. (2013-01-01). Gavrilova, Marina L.; Tan, C. J. Kenneth; Abraham, Ajith, ур. Multiobjective Optimization of Green Sand Mould System Using Chaotic Differential Evolution. Lecture Notes in Computer Science. Springer Berlin Heidelberg. стр. 145—163. ISBN 978-3-642-45317-5. doi:10.1007/978-3-642-45318-2_6.
Surekha, B.; Kaushik, Lalith K.; Panduy, Abhishek K.; Vundavilli, Pandu R.; Parappagoudar, Mahesh B. (2011-05-07). „Multi-objective optimization of green sand mould system using evolutionary algorithms”. The International Journal of Advanced Manufacturing Technology. 58 (1–4): 9—17. ISSN 0268-3768. S2CID 110315544. doi:10.1007/s00170-011-3365-8.
„MultiObjective Optimization in Engine Design Using Genetic Algorithms to Improve Engine Performance | ESTECO”. www.esteco.com. Архивирано из оригинала 10. 04. 2017. г. Приступљено 2015-12-01.
Courteille, E.; Mortier, F.; Leotoing, L.; Ragneau, E. (2005-05-16). „Multi-Objective Robust Design Optimization of an Engine Mounting System”. SAE Technical Paper Series (PDF). 1. Warrendale, PA. doi:10.4271/2005-01-2412.
Domingo-Perez, Francisco; Lazaro-Galilea, Jose Luis; Wieser, Andreas; Martin-Gorostiza, Ernesto; Salido-Monzu, David; Llana, Alvaro de la (април 2016). „Sensor placement determination for range-difference positioning using evolutionary multi-objective optimization”. Expert Systems with Applications. 47: 95—105. doi:10.1016/j.eswa.2015.11.008.
Bemporad, Alberto; Muñoz de la Peña, David (2009-12-01). „Multiobjective model predictive control”. Automatica. 45 (12): 2823—2830. doi:10.1016/j.automatica.2009.09.032.
Panda, Sidhartha (2009-06-01). „Multi-objective evolutionary algorithm for SSSC-based controller design”. Electric Power Systems Research. 79 (6): 937—944. doi:10.1016/j.epsr.2008.12.004.
Fiandaca, Giovanna; Fraga, Eric S.; Brandani, Stefano (2009). „A multi-objective genetic algorithm for the design of pressure swing adsorption”. Engineering Optimization. 41 (9): 833—854. S2CID 120201436. doi:10.1080/03052150903074189. Приступљено 2015-12-01.
Sendín, José Oscar H.; Alonso, Antonio A.; Banga, Julio R. (2010-06-01). „Efficient and robust multi-objective optimization of food processing: A novel approach with application to thermal sterilization”. Journal of Food Engineering. 98 (3): 317—324. doi:10.1016/j.jfoodeng.2010.01.007. hdl:10261/48082 .

Spoljašnje veze

Mathematical Programming Glossary Архивирано на сајту Wayback Machine (28. март 2010)

[1] Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (pdf). Cambridge University Press. стр. 129. ISBN 978-0-521-83378-3.

[2] „How Traffic Shaping Optimizes Network Bandwidth”. IPC. 12. 7. 2016. Приступљено 13. 2. 2017.

[3] "The Nature of Mathematical Programming Архивирано 2014-03-05 на сајту Wayback Machine," Mathematical Programming Glossary, INFORMS Computing Society.

[edo2021-4] Martins, Joaquim R. R. A.; Ning, Andrew (2021-10-01). Engineering Design Optimization (на језику: енглески). Cambridge University Press. ISBN 978-1108833417.

[5] Du, D. Z.; Pardalos, P. M.; Wu, W. (2008). „History of Optimization”. Ур.: Floudas, C.; Pardalos, P. Encyclopedia of Optimization. Boston: Springer. стр. 1538—1542.

[6] Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. стр. xii+454. ISBN 978-0691119151. MR 2199043.

[1]

[2]

[3]

[4]

[5]

[6]