Оптимизација (математика)

У математици, израз оптимизација, или математичко програмирање, се односи на проучавање проблема у којима се тражи максимизовање или минимизовање реалне функције систематичким бирањем вредности реалних или целобројних променљивих из одређеног скупа. Проблеми оптимизације се јављају у свим квантитативним дисциплинама од рачунарства и инжењерства до оперативних истраживања и економије, а развој метода решавања је вековима од интереса у математици. Проблем се може представити на следећи начин

Графикон функције z = f(x, y) = −(x² + y²) + 4. Глобални максимум на (x, y, z) = (0, 0, 4 је означен плавом тачком.

Нелдер-Мидовова претрага минимума Симионескове функције. Симплексни врхови су поређани по вредностима, при чему 1 има најнижу (fx најбољу) вредност.

Дата је: a функција f : A $\to$ R из неког скупа A у скуп реалних бројева

Тражи се: елемент x₀ из A такав да f(x₀) ≤ f(x) за свако x из A (минимизација) или такав да f(x₀) ≥ f(x) за свако x из A (максимизација).

Таква формулација се назива оптимизациони проблем или проблем математичког програмирања (овај израз није директно повезан са рачунарским програмирањем, али се користи на пример код линеарног програмирања. Многи теоријски и проблеми који се јављају у пракси се могу представити на овакав начин.

Типично, A је неки подскуп Еуклидског простора Rⁿ, који се често представља скупом услова (једнакости или неједнакости) које чланови треба да задовоље. Елементи A се називају изводљивим решењима. Функција f се назива објективном функцијом, или функцијом коштања. Изводљиво решење које минимизује (или максимизује ако је то циљ) објективну функцију се назива оптималним решењем. Домен A од f се назива простором претраге, а елементи од A су кандидати за решења или задовољива решења.

Оптимизациони проблеми

Главни чланак: Оптимизациони проблем

Проблем оптимизације се може представити на следећи начин:

Дата је: функција f : A → ℝ из неког скупа A до реалних бројева

Тражи се: елемент x₀ ∈ A такав да је f(x₀) ≤ f(x) за свако x ∈ A („минимизација“) или такав да је f(x₀) ≥ f(x) за свако x ∈ A („максимизација“) .

Таква формулација се назива оптимизациони проблем или проблем математичког програмирања (термин који није директно повезан са компјутерским програмирањем, али се још увек користи, на пример, у линеарном програмирању – види историју испод). Многи стварни и теоријски проблеми могу се моделовати у овом општем оквиру.

Пошто важи следеће

$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)$

са

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

подесније је решавати проблеме минимизације. Међутим, била би валидна и супротна перспектива.

Проблеми формулисани коришћењем ове технике у областима физике могу се односити на технику као на минимизацију енергије, говорећи о вредности функције f као представљању енергије система који се моделује. У машинском учењу увек је неопходно континуирано процењивати квалитет модела података коришћењем функције трошкова где минимум подразумева скуп могуће оптималних параметара са оптималном (најнижом) грешком.

Типично, A је неки подскуп Еуклидског простора ℝⁿ, често специфициран скупом ограничења, једнакости или неједнакости које чланови A морају да задовоље. Домен A од f назива се простор претраживања или скуп избора, док се елементи A називају кандидатска решења или изводљива решења.

Функција f се назива, различито, функција циља, функција губитка или функција трошкова (минимизација), функција корисности или функција способности (максимизација), или у одређеним пољима, функција енергије или енергетски функционал. Изводљиво решење које минимизира (или максимизира, ако је то циљ) циљну функцију назива се оптимално решење.

У математици, конвенционални проблеми оптимизације се обично наводе у смислу минимизације.

Локални минимум x* је дефинисан као елемент за који постоји неко δ > 0 тако да

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

важи израз f(x*) ≤ f(x);

то јест, у неком региону око x* све вредности функције су веће или једнаке вредности на том елементу. Слично се дефинишу локални максимуми.

Док је локални минимум бар добар као и сви оближњи елементи, глобални минимум је бар једнако добар као сваки изводљиви елемент. Генерално, осим ако циљна функција није конвексна у проблему минимизације, може постојати неколико локалних минимума. У конвексном проблему, ако постоји локални минимум који је унутрашњи (није на ивици скупа изводљивих елемената), то је такође глобални минимум, али неконвексни проблем може имати више од једног локалног минимума од којих сви не морају бити глобални минимуми.

Велики број алгоритама предложених за решавање неконвексних проблема – укључујући већину комерцијално доступних решавача – није у стању да направи разлику између локално оптималних решења и глобално оптималних решења, и третираће прва као стварна решења оригиналног проблема. Глобална оптимизација је грана примењене математике и нумеричке анализе која се бави развојем детерминистичких алгоритама који су у стању да гарантују конвергенцију у коначном времену до стварног оптималног решења неконвексног проблема.

Нотација

Проблеми оптимизације се често изражавају посебним ознакама. Следио неколико примера:

Минимална и максимална вредност функције

Може се размотрити следећа нотација:

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

Ово означава минималну вредност циљне функције x² + 1, када се бира x из скупа реалних бројева ℝ. Минимална вредност у овом случају је 1, а јавља се на x = 0.

Слично, нотација

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

тражи максималну вредност циљне функције 2x, где x може бити било који реалан број. У овом случају не постоји такав максимум, јер је циљна функција неограничена, те је одговор „бесконачно“ или „недефинисано“.

Види још

• Теорија игара
• Симплекс алгоритам
• Линеарно програмирање

Литература

• 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. CS1 одржавање: Формат датума (веза)
• 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 . 

Спољашње везе

• „Decision Tree for Optimization Software”.  Links to optimization source codes
• „Global optimization”. Архивирано из оригинала 29. 01. 2022. г. Приступљено 19. 12. 2021. 
• „EE364a: Convex Optimization I”. Course from Stanford University. 
• Varoquaux, Gaël. „Mathematical Optimization: Finding Minima of Functions”.