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

У математици, израз оптимизација, или математичко програмирање, се односи на проучавање проблема у којима се тражи максимизовање или минимизовање реалне функције систематичким бирањем вредности реалних или целобројних променљивих из одређеног скупа.[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 може бити било који реалан број. У овом случају не постоји такав максимум, јер је циљна функција неограничена, те је одговор „бесконачно“ или „недефинисано“.

Види још уреди

Референце уреди

  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.

Литература уреди

Спољашње везе уреди