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

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

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

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

Дата је: 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}- су кандидати за решења или задовољива решења.

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

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

Дата је: функција Шаблон:Math из неког скупа Шаблон:Mvar до реалних бројева

Тражи се: елемент Шаблон:Math такав да је Шаблон:Math за свако Шаблон:Math („минимизација“) или такав да је Шаблон:Math за свако Шаблон:Math („максимизација“) .

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

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

$f\left({𝐱}_0\right)\ge f\left(𝐱\right)\iff \tilde{f}\left({𝐱}_0\right)\le \tilde{f}\left(𝐱\right)$

са

$\tilde{f}\left(𝐱\right):=-f\left(𝐱\right),\tilde{f}:A\to ℝ$

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

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

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

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

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

Локални минимум Шаблон:Math је дефинисан као елемент за који постоји неко Шаблон:Math тако да

$\mathrm{\forall }𝐱\in A\text{где је}\Vert 𝐱-{𝐱}^{\ast }\Vert \le \delta ,$

важи израз Шаблон:Math;

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

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

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

Нотација

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

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

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

$\underset{x\in ℝ}{\min }(x^2+1)$

Ово означава минималну вредност циљне функције Шаблон:Math, када се бира Шаблон:Mvar из скупа реалних бројева Шаблон:Math. Минимална вредност у овом случају је 1, а јавља се на Шаблон:Math.

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

$\underset{x\in ℝ}{\max }2x$

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

Апликације

Механика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Види још

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

Литература

• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite arxiv
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite book
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite web
• Шаблон:Cite book
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal
• Шаблон:Cite journal

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

• Шаблон:Cite web Links to optimization source codes
• Шаблон:Cite web
• Шаблон:Cite web
• Шаблон:Cite web