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

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

Графикон функције z = f(x, y) = −(x² + y²) + 4. Глобални максимум на (x, y, z) = (0, 0, 4 је означен плавом тачком.
Нелдер-Мидовова претрага минимума Симионескове функције. Симплексни врхови су поређани по вредностима, при чему 1 има најнижу (fx најбољу) вредност.
Дата је: a функција f : A R из неког скупа A у скуп реалних бројева
Тражи се: елемент x0 из A такав да f(x0) ≤ f(x) за свако x из A (минимизација) или такав да f(x0) ≥ f(x) за свако x из A (максимизација).

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

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

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

уреди

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

Дата је: функција f : A → ℝ из неког скупа A до реалних бројева
Тражи се: елемент x0A такав да је f(x0) ≤ f(x) за свако xA („минимизација“) или такав да је f(x0) ≥ f(x) за свако xA („максимизација“) .

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

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

 

са

 

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

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

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

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

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

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

 

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

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

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

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

Нотација

уреди

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

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

уреди

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

 

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

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

 

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

Апликације

уреди

Механика

уреди

Проблеми у динамици крутог тела (посебно наглешени у динамици крутог тела) често захтевају технике математичког програмирања, пошто се динамика крутог тела може посматрати као покушај решавања обичне диференцијалне једначине на вишеструкој граници ограничења;[5] ограничења су различита нелинеарна геометријска ограничења, попут ових „ове две тачке увек морају да се поклапају“, „ова површина не сме да продре ни у једну другу“, или „ова тачка увек мора да лежи негде на овој кривој“. Такође, проблем израчунавања контактних сила може се решити решавањем проблема линеарне комплементарности, који се такође може посматрати као QP (квадратично програмски) проблем.

Многи дизајнерски проблеми се такође могу изразити као оптимизациони програми. Овај вид примене се зове оптимизација дизајна. Један подскуп је инжењерска оптимизација, а други новији и растући подскуп ове области је мултидисциплинарна оптимизација дизајна, која је, иако корисна у многим проблемима, посебно примењена на проблеме ваздухопловног инжењерства.

Овај приступ се може применити у космологији и астрофизику.[6]

Економија и финансије

уреди

Економија је блиско повезана са оптимизацијом агената тако да једна утицајна дефиниција сходно томе описује економију као науку која је „проучавање људског понашања као односа између циљева и оскудних средстава“ са алтернативним употребама.[7] Модерна теорија оптимизације укључује традиционалну теорију оптимизације, али се такође преклапа са теоријом игара и проучавањем економске равнотеже. Кодови часописа Journal of Economic Literature класификују математичко програмирање, технике оптимизације и сродне теме под JEL:C61-C63.

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

Од 1970-их, економисти су моделовали динамичке одлуке током времена користећи теорију контроле.[8] На пример, динамички модели претраге се користе за проучавање понашања на тржишту рада.[9] Кључна разлика је између детерминистичких и стохастичких модела.[10] Макроекономисти граде динамичке стохастичке моделе опште равнотеже (DSGE) који описују динамику читаве економије као резултат међузависних оптимизирајућих одлука радника, потрошача, инвеститора и влада.[11][12]

Електротехника

уреди

Неке уобичајене примене техника оптимизације у електротехници укључују дизајн активног филтера,[13] смањење лутајућег поља у суперпроводним системима за складиштење магнетне енергије, дизајн мапирања простора микроталасних структура,[14] антене за слушалице,[15][16][17] електромагнетски-базирани дизајн. Електромагнетно валидирана оптимизација дизајна микроталасних компоненти и антена је у великој мери користила одговарајући физички заснован или емпиријски сурогатни модел и методологије мапирања простора од открића мапирања простора 1993. године.[18][19] Технике оптимизације се такође користе у анализи тока снаге.[20]

Грађевинарство

уреди

Оптимизација се широко користи у грађевинарству. Менаџмент изградње и транспортно инжењерство су међу главним гранама грађевинарства које се у великој мери ослањају на оптимизацију. Најчешћи грађевински проблеми који се решавају оптимизацијом су пресецање и насипање путева, анализа животног циклуса објеката и инфраструктуре,[21] нивелисање ресурса,[22][23] алокација водних ресурса, управљање саобраћајем[24] и оптимизација реда вожње.

Операционо истраживање

уреди

Још једно поље које у великој мери користи технике оптимизације су операциона истраживања.[25] Операциона истраживања такође користе стохастичко моделовање и симулацију за подршку побољшаном доношењу одлука. У овој области све више користи стохастичко програмирање за моделовање динамичких одлука које се прилагођавају догађајима; такви проблеми се могу решити методом оптимизације великих размера и стохастичком оптимизацијом.

Молекуларно моделовање

уреди

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

Биологија рачунарских система

уреди

Технике оптимизације се користе у многим аспектима биологије рачунарских система као што су изградња модела, оптимални експериментални дизајн, метаболички инжењеринг и синтетичка биологија.[26] Линеарно програмирање је примењено за израчунавање максималних могућих приноса производа ферментације,[26] и на извођење закључака о регулаторним мрежама гена из више скупова података микромрежа,[27] као и транскрипционих регулаторних мрежа из високопропустних података.[28] Нелинеарно програмирање је коришћено за анализу енергетског метаболизма[29] и примењено је на метаболички инжењеринг и процену параметара у биохемијским путевима.[30]

Види још

уреди

Референце

уреди
  1. ^ "The Nature of Mathematical Programming Архивирано 2014-03-05 на сајту Wayback Machine," Mathematical Programming Glossary, INFORMS Computing Society.
  2. ^ Martins, Joaquim R. R. A.; Ning, Andrew (2021-10-01). Engineering Design Optimization (на језику: енглески). Cambridge University Press. ISBN 978-1108833417. 
  3. ^ Du, D. Z.; Pardalos, P. M.; Wu, W. (2008). „History of Optimization”. Ур.: Floudas, C.; Pardalos, P. Encyclopedia of Optimization. Boston: Springer. стр. 1538—1542. 
  4. ^ W. Erwin Diewert (2008). "cost functions," The New Palgrave Dictionary of Economics, 2nd Edition Contents.
  5. ^ Vereshchagin, A.F. (1989). „Modelling and control of motion of manipulation robots”. Soviet Journal of Computer and Systems Sciences. 27 (5): 29—38. 
  6. ^ Haggag, S.; Desokey, F.; Ramadan, M. (2017). „A cosmological inflationary model using optimal control”. Gravitation and Cosmology. 23 (3): 236—239. Bibcode:2017GrCo...23..236H. ISSN 1995-0721. S2CID 125980981. doi:10.1134/S0202289317030069. 
  7. ^ Lionel Robbins (1935, 2nd ed.) An Essay on the Nature and Significance of Economic Science, Macmillan, p. 16.
  8. ^ Dorfman, Robert (1969). „An Economic Interpretation of Optimal Control Theory”. American Economic Review. 59 (5): 817—831. JSTOR 1810679. 
  9. ^ Sargent, Thomas J. (1987). „Search”. Dynamic Macroeconomic Theory. Harvard University Press. стр. 57—91. ISBN 9780674043084. 
  10. ^ A.G. Malliaris (2008). "stochastic optimal control," The New Palgrave Dictionary of Economics, 2nd Edition. Abstract Архивирано 2017-10-18 на сајту Wayback Machine.
  11. ^ Rotemberg, Julio; Woodford, Michael (1997). „An Optimization-based Econometric Framework for the Evaluation of Monetary Policy” (PDF). NBER Macroeconomics Annual. 12: 297—346. JSTOR 3585236. doi:10.2307/3585236 . 
  12. ^ From The New Palgrave Dictionary of Economics (2008), 2nd Edition with Abstract links:
    • "numerical optimization methods in economics" by Karl Schmedders
    • "convex programming" by Lawrence E. Blume
    • "Arrow–Debreu model of general equilibrium" by John Geanakoplos.
  13. ^ De, Bishnu Prasad; Kar, R.; Mandal, D.; Ghoshal, S.P. (2014-09-27). „Optimal selection of components value for analog active filter design using simplex particle swarm optimization”. International Journal of Machine Learning and Cybernetics. 6 (4): 621—636. ISSN 1868-8071. S2CID 13071135. doi:10.1007/s13042-014-0299-0. 
  14. ^ Koziel, Slawomir; Bandler, John W. (јануар 2008). „Space Mapping With Multiple Coarse Models for Optimization of Microwave Components”. IEEE Microwave and Wireless Components Letters. 18 (1): 1—3. CiteSeerX 10.1.1.147.5407 . S2CID 11086218. doi:10.1109/LMWC.2007.911969. 
  15. ^ Tu, Sheng; Cheng, Qingsha S.; Zhang, Yifan; Bandler, John W.; Nikolova, Natalia K. (јул 2013). „Space Mapping Optimization of Handset Antennas Exploiting Thin-Wire Models”. IEEE Transactions on Antennas and Propagation. 61 (7): 3797—3807. Bibcode:2013ITAP...61.3797T. doi:10.1109/TAP.2013.2254695 . 
  16. ^ N. Friedrich, “Space mapping outpaces EM optimization in handset-antenna design,” microwaves&rf, August 30, 2013.
  17. ^ Cervantes-González, Juan C.; Rayas-Sánchez, José E.; López, Carlos A.; Camacho-Pérez, José R.; Brito-Brito, Zabdiel; Chávez-Hurtado, José L. (фебруар 2016). „Space mapping optimization of handset antennas considering EM effects of mobile phone components and human body”. International Journal of RF and Microwave Computer-Aided Engineering. 26 (2): 121—128. S2CID 110195165. doi:10.1002/mmce.20945 . 
  18. ^ Bandler, J.W.; Biernacki, R.M.; Chen, Shao Hua; Grobelny, P.A.; Hemmers, R.H. (1994). „Space mapping technique for electromagnetic optimization”. IEEE Transactions on Microwave Theory and Techniques. 42 (12): 2536—2544. Bibcode:1994ITMTT..42.2536B. doi:10.1109/22.339794. 
  19. ^ Bandler, J.W.; Biernacki, R.M.; Shao Hua Chen; Hemmers, R.H.; Madsen, K. (1995). „Electromagnetic optimization exploiting aggressive space mapping”. IEEE Transactions on Microwave Theory and Techniques. 43 (12): 2874—2882. Bibcode:1995ITMTT..43.2874B. doi:10.1109/22.475649. 
  20. ^ Convex relaxation of optimal power flow: A tutorial. 2013 iREP Symposium on Bulk Power System Dynamics and Control. doi:10.1109/IREP.2013.6629391. 
  21. ^ Piryonesi, Sayed Madeh; Tavakolan, Mehdi (9. 1. 2017). „A mathematical programming model for solving cost-safety optimization (CSO) problems in the maintenance of structures”. KSCE Journal of Civil Engineering. 21 (6): 2226—2234. S2CID 113616284. doi:10.1007/s12205-017-0531-z. 
  22. ^ Hegazy, Tarek (јун 1999). „Optimization of Resource Allocation and Leveling Using Genetic Algorithms”. Journal of Construction Engineering and Management. 125 (3): 167—175. doi:10.1061/(ASCE)0733-9364(1999)125:3(167). 
  23. ^ Piryonesi, S. Madeh; Nasseri, Mehran; Ramezani, Abdollah (9. 7. 2018). „Piryonesi, S. M., Nasseri, M., & Ramezani, A. (2018). Resource leveling in construction projects with activity splitting and resource constraints: a simulated annealing optimization.”. Canadian Journal of Civil Engineering. 46: 81—86. S2CID 116480238. doi:10.1139/cjce-2017-0670. hdl:1807/93364 . 
  24. ^ Herty, M.; Klar, A. (2003-01-01). „Modeling, Simulation, and Optimization of Traffic Flow Networks”. SIAM Journal on Scientific Computing. 25 (3): 1066—1087. Bibcode:2003SJSC...25.1066H. ISSN 1064-8275. doi:10.1137/S106482750241459X. 
  25. ^ „New force on the political scene: the Seophonisten”. Архивирано из оригинала 18. 12. 2014. г. Приступљено 14. 9. 2013. 
  26. ^ а б Papoutsakis, Eleftherios Terry (фебруар 1984). „Equations and calculations for fermentations of butyric acid bacteria”. Biotechnology and Bioengineering. 26 (2): 174—187. ISSN 0006-3592. PMID 18551704. S2CID 25023799. doi:10.1002/bit.260260210. 
  27. ^ Wang, Yong; Joshi, Trupti; Zhang, Xiang-Sun; Xu, Dong; Chen, Luonan (2006-07-24). „Inferring gene regulatory networks from multiple microarray datasets”. Bioinformatics (на језику: енглески). 22 (19): 2413—2420. ISSN 1460-2059. PMID 16864593. doi:10.1093/bioinformatics/btl396. 
  28. ^ Wang, Rui-Sheng; Wang, Yong; Zhang, Xiang-Sun; Chen, Luonan (2007-09-22). „Inferring transcriptional regulatory networks from high-throughput data”. Bioinformatics. 23 (22): 3056—3064. ISSN 1460-2059. PMID 17890736. doi:10.1093/bioinformatics/btm465 . 
  29. ^ Vo, Thuy D.; Paul Lee, W.N.; Palsson, Bernhard O. (мај 2007). „Systems analysis of energy metabolism elucidates the affected respiratory chain complex in Leigh's syndrome”. Molecular Genetics and Metabolism. 91 (1): 15—22. ISSN 1096-7192. PMID 17336115. doi:10.1016/j.ymgme.2007.01.012. 
  30. ^ Mendes, P.; Kell, D. (1998). „Non-linear optimization of biochemical pathways: applications to metabolic engineering and parameter estimation”. Bioinformatics. 14 (10): 869—883. ISSN 1367-4803. PMID 9927716. doi:10.1093/bioinformatics/14.10.869 . 

Литература

уреди

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

уреди