right|thumb|Az f(x,y) = -(x²+y²)+4 egyenletű paraboloid. A globális maximumot a (0,0,4) pontban piros pont jelöli A matematikai optimalizáció a legjobb elem kiválasztását jelenti a matematikában, a statisztikában, a számítástechnikában és az alkalmazott tudományokban. A legjobb elemet az alternatívák egy halmazából választják ki."The Nature of Mathematical Programming ," Mathematical Programming Glossary, INFORMS Computing Society.

A legegyszerűbb esetben az optimalizáció egy valós függvény maximumának vagy minimumának meghatározását jelenti. A feladat egy egyszerű (de nem optimális) megoldása az, hogy az algoritmus végigpróbálgatja a megengedett halmaz elemeit, mindegyikhez kiszámítva a függvény értékeit. Az optimalizáció elméletének és technikájának általánosítása az alkalmazott matematika egy külön fejezetét alkotja. Általánosabban, az optimalizáció egy adott megengedett tartományon keresi egy függvény legjobb értékét, ahol mind a megengedett tartomány, mind a függvény sok különböző típusba tartozhat.

Optimalizációs feladatok Egy optimalizációs feladat megadása pl. a következőképpen történhet: Adva van: egy f : A R függvény, ami az A halmazból a valós számokba képez Keresünk: egy x0 elemet A-ban úgy, hogy f(x0) ≤ f(x) minden x A-beli elemre („minimalizáció”) vagy úgy, hogy f(x0) ≥ f(x) minden x A-beli elemre („maximalizáció”).

Egy ilyen módon megfogalmazott feladatot optimalizálási feladatnak vagy matematikai programozási feladatnak neveznek. A kifejezés nem áll közvetlen kapcsolatban a számítógépek programozásával; a lineáris programozási feladat közelebb áll az optimalizálási feladathoz, annak egy altípusát jelöli. Sok valós és elméleti probléma modellezhető így, például a fizikában vagy a gépi látásban az energia minimalizálása.

Tipikusan A az Rn tér részhalmaza, amit egyenletek és egyenlőtlenségek határoznak meg. Az A halmaz azokból a pontokból áll, amelyek megoldják az így megadott egyenlőtlenségrendszert. Ezeket a pontokat megengedett megoldásoknak is hívják.

Az f függvényt többféleképpen is nevezik, például minimalizáció esetén költségfüggvénynek, energiafüggvénynek, energiafunkcionálnak, indirekt hasznossági függvénynek, vagy maximalizáció esetén hasznossági függvénynek. A feladatnak megfelelően a minimalizáló vagy maximalizáló megengedett megoldást optimális megoldásnak hívják.

Konvenció szerint a standard alakot minimalizációként fogalmazzák meg. Az általános feladatban, ahol a megengedett pontok halmaza vagy a függvény nem konvex, több lokális minimum is adódhat. (Az x* pont lokális minimum, ha van egy δ > 0, hogy minden x pontra, amire , teljesül )

Szavakkal: egy függvénynek egy adott pontban lokális minimuma van, ha van egy környezete, ahol a függvény nem vesz fel kisebb értéket, mint az adott pontban.

A nemkonvex feladatot megoldó algoritmusok nem tudnak különbséget tenni a lokális és a globális minimum között, ezért megoldásként lokális minimumot adnak. Az alkalmazott matematika és a numerikus analízis egy egész ága, a globális optimalizáció foglalkozik olyan determinisztikus algoritmusok kifejlesztésével, amelyek véges időben konvergálnak a globális minimumhoz.

Jelölések Az optimalizációs feladatokat gyakran sajátos jelöléssel írják fel. Néhány példa: Függvény minimuma és maximuma Tekintsük a következő jelölést:

Ez a célfüggvény minimuma, ahol az x számot a valós számok halmazából választjuk. Most a minimum , az helyen.

Hasonlóan,

a 2x célfüggvény maximumát, ahol x bármely valós szám lehet. Ebben az esetben a maximum nem létezik, válaszként a „végtelen” vagy a „nem értelmezett” szavakat használják.

Módszerek függvények szélsőértékének meghatározására Függvények minimumának, és maximumának (azaz szélsőértékének) meghatározásához elég módszereket találnunk a minimumok meghatározására, mivel a függvény maximumát megkaphatjuk úgy, hogy megkeressük a függvény inverzének a minimumát. Egy adott függvény szélsőértéke lehet lokális vagy globális. A lokális szélsőértéket numerikusan meghatározni egyszerűbb, mint a globális szélsőértékeket, ezek keresésére is általában a lokális szélsőérték kereső módszereket szoktuk alkalmazni, viszont itt véletlenszerű kezdőfeltételekre határozunk meg több szélsőértéket, és ezeket összehasonlítva meghatározzuk a legextrémebb esetet, és ezt tekintjük globális szélsőértéknek, vagy egy másik módszert alkalmazva véges amplitúdójú lépésenként vett kezdőértékekre megnézzük hogy a szélsőértékünk változik, és ha nem akkor ezt tekintjük globális szélsőértéknek.

Egy dimenzióban használatos szélsőértékkereső módszerek Aranymetszés módszere:

Vegyük az a<b<c, számhármast és értékeljük ki a függvényben. Ha f(b) kisebb mint f(a), és f(c), ez azt jelenti, hogy minimum valahol  a és c között van. Most értékeljük ki a függvényt tetszőleges x (ahol b<x<c). Ha f(b)<f(x), akkor a minimumot közrezáró számhármasunk (a, b, x), ha f(b)>f(x) akkor pedig (a, x , b). Ezt addig ismételjük, míg a két szélsőérték közti különbség kellően kicsi. A módszer konvergenciája lineáris, viszont bármilyen függvén esetében alkalmazható. Parabolikus interpoláció: Ennél a módszernél is kiválasztunk három bemeneti értéket, ezekre kiértékeljük a függvényt, majd rajtuk keresztül parabolát illesztünk. Majd a parabola minimumpontjának az abszcisszáját használjuk a egy új parabola szerkesztéséhez. Az illesztett parabolák minimumpontjai hamar elkezdenek konvergálni a minimum felé. A módszer konvergenciája szupralineáris, ezért sokkal gyorsabban megtalálja a minimumpontot mint az aranymetszés módszere, viszont nem alkalmazható akármilyen függvényre.

Optimális paraméterek Tekintsük a következő jelölést:

vagy ekvivalensen:

Ez azt az intervallumbeli x értékét reprezentálja, ami minimalizálja az x2 + 1 célfüggvényt. Ebben az esetben a válasz az x = -1, minvel x = 0 is nem megengedett, mivel nem tartozik a megengedett halmazhoz.

Hasonlóan,

vagy ekvivalensen

reprezentálja az párt, ami maximalizálja az célfüggvény értékét azzal a megkötéssel, hogy x eleme a intervallumnak. Ebben az esetben a megoldások az (5, 2kπ) és (−5,(2k+1)π) alakú párok, ahol k befutja az egész számok halmazát.

Arg min és arg max gyakran argmin és argmax alakban jelenik meg, és rendere a minimum argumentumát és a maximum argumentumát jelentik. Története Fermat és Lagrange differenciál- és integrálszámításon alapuló képleteket használt az optimumok meghatározásához. Newton és Gauss iterációs módszereket dolgozott ki az optimum megközelítésére. Az optimalizációnak először George B. Dantzig adott nevet; tőle származik a lineáris programozás, habár Leonid Kantorovich 1939-ben már nagy részét kidolgozta. Dantzig 1947-ben publikálta a szimplex algoritmust, és Neumann János még abban az évben kifejlesztette a dualitáselméletet.

A programozás itt nem a számítógép programozására utal. Az Amerikai Egyesült Államok hadseregében programnak nevezték a tréning és a logisztika megszervezésének feladatát, amivel Dantzig akkoriban foglalkozott.

További nevezetes kutatók:

Richard Bellman Ronald A. Howard Narendra Karmarkar William Karush Leonid Khachiyan Bernard Koopman Harold Kuhn Joseph Louis Lagrange Lovász László

Arkadi Nemirovski Yurii Nesterov Boris Polyak Lev Pontryagin James Renegar R. Tyrrell Rockafellar Cornelis Roos Naum Z. Shor Michael J. Todd Albert Tucker

Fontosabb részterületei A konvex programozás felteszi, hogy a célfüggvény konvex, vagy konkáv, és a megengedett halmaz konvex. A nemlineáris programozás speciális esetének, vagy a lineáris és a kvadratikus programozás közös általánosításának tekinthető. A lineáris programozás, vagy operációkutatás (LP) lineáris célfüggvényt és egyenlőtlenségrendszerrel megadott megengedett halmazt feltételez. Szóhasználata szerint a megengedett halmaz poliéder, korlátos esetben politóp. A másodrendű kúpprogramozás (SOCP) magában foglalja a kvadratikus programozás egyes eseteit. A szemidefinit programozás (SDP) az a részterület, amiben a változók szemidefinit mátrixok. A lineáris és a konvex kvadratikus programozás egy közös általánosítása. A kúpprogramozás a konvex programozás általános alakja. Az LP, SOCP és SDP ennek speciális esetei, egy bizonyos kúptípussal. A geometriai programozás módszere az optimalizálási feladatot polinom formára alakítja. Az egészértékű programozás megengedett halmaza csak olyan pontokat tartalmaz, amelyek minden koordinátája egész. Mivel izolált pontokból áll, a feladat nem tekinthető konvex programnak. Nehezebb megoldani, mint a normál lineáris programot, ezért sokszor a normál lineáris program alapján adnak becslést, ha lehet. A kvadratikus programozás megengedi, hogy a célfüggvény másodfokú legyen, de a megengedett halmaznak itt is poliédernek kell lennie. Speciális esetben a program konvex. A törtfüggvényű programozásban a célfüggvény két nemlineáris függvény hányadosa. A konkáv törtfüggvényű programok konvex optimalizációs feladattá alakíthatók. A nemlineáris programozás az általános esettel foglalkozik, amikor a célfüggvény, vagy a megengedett halmaz nem lineáris részeket is tartalmaz. A megoldás nehézsége erősen függ a program konvex, vagy konkáv voltától. A sztochasztikus programozás azokkal az esetekkel foglalkozik, amikor a megkötések vagy a paraméterek véletlen valószínűségi változóktól függnek. A robusztus programozás pontatlannak, hibával terheltnek tekinti a bemenő adatokat, és akként számol velük. A sztochasztikus programozás véletlen függvényértékeket feltételez, vagy azt, hogy a kereső folyamat véletlen bejövő értékeket talál. A kombinatorikus optimalizálás diszkrét, vagy diszkrétre visszavezethető megengedett halmazokkal foglalkozik. A végtelen dimenziós optimalizálás végtelen dimenziós terek részhalmazain, például függvényterekben optimalizál. A heurisztikus, vagy metaheurisztikus módszerek keveset, vagy semmit sem feltételeznek a feladatról. Sok nehéz programozási feladat megoldását segítik, de nem garantálják, hogy megtalálják az optimumot. A megkötések kielégítése csak a megengedett halmazzal foglalkozik, a célfüggvényt konstansnak tekinti. A megkötéses programozás az adott megengedett halmazt próbálja meg különböző megkötésekkel meghatározni. A diszjunktív programozás esetén nem kell minden kikötésnek teljesülnie, de vannak olyanok, amelyeknek viszont teljesülniük kell.

Több részterületen használnak dinamikus módszereket, amelyek az időben optimalizálnak: A variációszámítás funkcionálokkal foglalkozik, azaz függvények függvényeivel. Az optimális kontroll a variációszámítás általánosítása. A dinamikus programozás több részre osztható feladatokkal foglalkozik. A részproblémák kapcsolatait a Bellman-egyenlet írja le. A matematikai programozás egyensúlyi megkötésekkel megkötései variációs egyenlőtlenségekkel vagy komplementerekkel adhatók meg. Többcélfüggvényű optimalizálás A több célfüggvény bonyolultabbá teszi a feladatot. Például egy szerkezetnek könnyűnek és merevnek kell lennie. A két célfüggvény konfliktusban van, ezért egy észszerű kompromisszumot kell kötni. Meghatározható a legkönnyebb és a legmerevebb szerkezet, valamint végtelen sok átmenet a kettő között aszerint, hogy melyiket mennyire tekintjük fontosnak. A Pareto-halmaz azokat a megengedett értékeket tartalmazza, ahol az egyik függvény javítása valamely másik függvény rontásához vezet. A Pareto-halmaz ábrázolása a Pareto-görbe.

Maximalizáció esetén egy adott pont gyengén dominál egy ponthalmazt, ha a halmaz összes pontjára minden célfüggvény legfeljebb akkora értéket ad, mint az adott pont. Erősen dominálja a halmazt, ha van olyan függvény, aminek értéke az adott pontban nagyobb, mint a halmazban. Minimalizáció esetén a nagyobb szó helyett mindenütt kisebbet kell írni. A pont Pareto optimális, ha nincs egy másik pont, ami jobb nála.

A Pareto-optimumok közül kiválasztható a kedvenc megoldás. Más szóval, a feladat úgy van megfogalmazva, hogy kimaradtak belőle információk. A kívánt célok vannak megadva, és nem az ő legjobb kombinációjuk. Egyes esetekben ez az információ interaktívan pótolható.