Optimizacija (matematika)

Grafikon funkcije z = f(x, y) = −(x² + y²) + 4. Globalni maksimum na (x, y, z) = (0, 0, 4 je označen plavom tačkom.

Nelder-Midovova pretraga minimuma Simioneskove funkcije. Simpleksni vrhovi su poređani po vrednostima, pri čemu 1 ima najnižu (fx najbolju) vrednost.

U matematici, izraz optimizacija, ili matematičko programiranje, se odnosi na proučavanje problema u kojima se traži maksimizovanje ili minimizovanje realne funkcije sistematičkim biranjem vrednosti realnih ili celobrojnih promenljivih iz određenog skupa. Problemi optimizacije se javljaju u svim kvantitativnim disciplinama od računarstva i inženjerstva do operativnih istraživanja i ekonomije, a razvoj metoda rešavanja je vekovima od interesa u matematici. Problem se može predstaviti na sledeći način

Data je: a funkcija f : A $\to$ R iz nekog skupa A u skup realnih brojeva

Traži se: element x₀ iz A takav da f(x₀) ≤ f(x) za svako x iz A (minimizacija) ili takav da f(x₀) ≥ f(x) za svako x iz A (maksimizacija).

Takva formulacija se naziva optimizacioni problem ili problem matematičkog programiranja (ovaj izraz nije direktno povezan sa računarskim programiranjem, ali se koristi na primer kod linearnog programiranja. Mnogi teorijski i problemi koji se javljaju u praksi se mogu predstaviti na ovakav način.

Tipično, A je neki podskup Euklidskog prostora Rⁿ, koji se često predstavlja skupom uslova (jednakosti ili nejednakosti) koje članovi treba da zadovolje. Elementi A se nazivaju izvodljivim rešenjima. Funkcija f se naziva objektivnom funkcijom, ili funkcijom koštanja. Izvodljivo rešenje koje minimizuje (ili maksimizuje ako je to cilj) objektivnu funkciju se naziva optimalnim rešenjem. Domen A od f se naziva prostorom pretrage, a elementi od A su kandidati za rešenja ili zadovoljiva rešenja.

Optimizacioni problemi

Glavni članak: Optimizacioni problem

Problem optimizacije se može predstaviti na sledeći način:

Data je: funkcija f : A → ℝ iz nekog skupa A do realnih brojeva

Traži se: element x₀ ∈ A takav da je f(x₀) ≤ f(x) za svako x ∈ A („minimizacija“) ili takav da je f(x₀) ≥ f(x) za svako x ∈ A („maksimizacija“) .

Takva formulacija se naziva optimizacioni problem ili problem matematičkog programiranja (termin koji nije direktno povezan sa kompjuterskim programiranjem, ali se još uvek koristi, na primer, u linearnom programiranju – vidi istoriju ispod). Mnogi stvarni i teorijski problemi mogu se modelovati u ovom opštem okviru.

Pošto važi sledeće

$f\left(\mathbf {x} _{0}\right)\geq f\left(\mathbf {x} \right)\Leftrightarrow {\tilde {f}}\left(\mathbf {x} _{0}\right)\leq {\tilde {f}}\left(\mathbf {x} \right)$

sa

${\tilde {f}}\left(\mathbf {x} \right):=-f\left(\mathbf {x} \right),\,{\tilde {f}}\,:\,A\rightarrow \mathbb {R}$

podesnije je rešavati probleme minimizacije. Međutim, bila bi validna i suprotna perspektiva.

Problemi formulisani korišćenjem ove tehnike u oblastima fizike mogu se odnositi na tehniku kao na minimizaciju energije, govoreći o vrednosti funkcije f kao predstavljanju energije sistema koji se modeluje. U mašinskom učenju uvek je neophodno kontinuirano procenjivati kvalitet modela podataka korišćenjem funkcije troškova gde minimum podrazumeva skup moguće optimalnih parametara sa optimalnom (najnižom) greškom.

Tipično, A je neki podskup Euklidskog prostora ℝⁿ, često specificiran skupom ograničenja, jednakosti ili nejednakosti koje članovi A moraju da zadovolje. Domen A od f naziva se prostor pretraživanja ili skup izbora, dok se elementi A nazivaju kandidatska rešenja ili izvodljiva rešenja.

Funkcija f se naziva, različito, funkcija cilja, funkcija gubitka ili funkcija troškova (minimizacija), funkcija korisnosti ili funkcija sposobnosti (maksimizacija), ili u određenim poljima, funkcija energije ili energetski funkcional. Izvodljivo rešenje koje minimizira (ili maksimizira, ako je to cilj) ciljnu funkciju naziva se optimalno rešenje.

U matematici, konvencionalni problemi optimizacije se obično navode u smislu minimizacije.

Lokalni minimum x* je definisan kao element za koji postoji neko δ > 0 tako da

$\forall \mathbf {x} \in A\;{\text{где је}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,$

važi izraz f(x*) ≤ f(x);

to jest, u nekom regionu oko x* sve vrednosti funkcije su veće ili jednake vrednosti na tom elementu. Slično se definišu lokalni maksimumi.

Dok je lokalni minimum bar dobar kao i svi obližnji elementi, globalni minimum je bar jednako dobar kao svaki izvodljivi element. Generalno, osim ako ciljna funkcija nije konveksna u problemu minimizacije, može postojati nekoliko lokalnih minimuma. U konveksnom problemu, ako postoji lokalni minimum koji je unutrašnji (nije na ivici skupa izvodljivih elemenata), to je takođe globalni minimum, ali nekonveksni problem može imati više od jednog lokalnog minimuma od kojih svi ne moraju biti globalni minimumi.

Veliki broj algoritama predloženih za rešavanje nekonveksnih problema – uključujući većinu komercijalno dostupnih rešavača – nije u stanju da napravi razliku između lokalno optimalnih rešenja i globalno optimalnih rešenja, i tretiraće prva kao stvarna rešenja originalnog problema. Globalna optimizacija je grana primenjene matematike i numeričke analize koja se bavi razvojem determinističkih algoritama koji su u stanju da garantuju konvergenciju u konačnom vremenu do stvarnog optimalnog rešenja nekonveksnog problema.

Notacija

Problemi optimizacije se često izražavaju posebnim oznakama. Sledio nekoliko primera:

Minimalna i maksimalna vrednost funkcije

Može se razmotriti sledeća notacija:

$\min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)$

Ovo označava minimalnu vrednost ciljne funkcije x² + 1, kada se bira x iz skupa realnih brojeva ℝ. Minimalna vrednost u ovom slučaju je 1, a javlja se na x = 0.

Slično, notacija

$\max _{x\in \mathbb {R} }\;2x$

traži maksimalnu vrednost ciljne funkcije 2x, gde x može biti bilo koji realan broj. U ovom slučaju ne postoji takav maksimum, jer je ciljna funkcija neograničena, te je odgovor „beskonačno“ ili „nedefinisano“.

Vidi još

• Teorija igara
• Simpleks algoritam
• Linearno programiranje

Literatura

• 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 izd.). 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 izd.). 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. str. 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, ur. Hypervolume-Driven Analytical Programming for Solar-Powered Irrigation System Optimization. Advances in Intelligent Systems and Computing. Springer International Publishing. str. 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, ur. Multiobjective Optimization of Green Sand Mould System Using Chaotic Differential Evolution. Lecture Notes in Computer Science. Springer Berlin Heidelberg. str. 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. Arhivirano iz originala 10. 04. 2017. g. Pristupljeno 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 (april 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. CS1 održavanje: Format datuma (veza)
• 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. Pristupljeno 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

• „Decision Tree for Optimization Software”.  Links to optimization source codes
• „Global optimization”. Arhivirano iz originala 29. 01. 2022. g. Pristupljeno 19. 12. 2021. 
• „EE364a: Convex Optimization I”. Course from Stanford University. 
• Varoquaux, Gaël. „Mathematical Optimization: Finding Minima of Functions”.