Matematikai optimalizálás

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.

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 $\to$ R függvény, ami az A halmazból a valós számokba képez

Keresünk: egy x₀ elemet A-ban úgy, hogy f(x₀) ≤ f(x) minden x A-beli elemre („minimalizáció”) vagy úgy, hogy f(x₀) ≥ 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 Rⁿ 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 $\|\mathbf {x} -\mathbf {x} ^{*}\|\leq \delta$, teljesül $f(\mathbf {x} ^{*})\leq f(\mathbf {x} )$)

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:

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

Ez a $x^{2}+1$ célfüggvény minimuma, ahol az x számot a valós számok $\mathbb {R}$ halmazából választjuk. Most a minimum $1$, az $x=0$ helyen.

Hasonlóan,

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

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:

${\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,$

vagy ekvivalensen:

${\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{ }}\;x\in (-\infty ,-1].$

Ez azt az $(-\infty ,-1]$ intervallumbeli x értékét reprezentálja, ami minimalizálja az x² + 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,

${\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos(y),$

vagy ekvivalensen

${\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos(y),\;{\text{ }}\;x\in [-5,5],\;y\in \mathbb {R} ,$

reprezentálja az $(x,y)$ párt, ami maximalizálja az $x\cos(y)$ célfüggvény értékét azzal a megkötéssel, hogy x eleme a $[-5,5]$ 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ó.

A többcélfüggvényű optimalizálás tovább általánosítható vektoroptimalizálássá, ahol a részben rendezést nem a Pareto rendezés adja meg.

Többmodális optimalizáció

Az optimalizációs feladatok gyakran többmodálisak; ez azt jelenti, hogy egynél több jó megoldásuk van. Ezek lehetnek globális optimumok, vagy lehetnek helyi és globális optimumok keverékei. Ezek közül kell megtalálni legalább egyet.

A klasszikus optimalizációs módszerek iterációs eljárások, ezért nem teljesítenek megfelelően, ha több legjobb megoldást keresnek velük, mivel különböző kezdőértékek esetén is ugyanoda konvergálhatnak több optimum esetén is. Ennek ellenére népszerűek az evolúciós algoritmusok a többmodális feladatok megoldására.

A kritikus pontok és az optimumok osztályozása

Megengedettségi probléma

A megengedettségi probléma azt vizsgálja, hogy vannak-e egyáltalán megengedett pontok. A célfüggvényt nem veszi figyelembe, konstansnak tekinti, ezért számára minden megengedett pont optimum.

Az iteratív módszereknek szükségük van egy megengedett pontra, ahonnan elindulhatnak. Ennek egy módja, hogy pótváltozók bevezetésével lazítunk a megkötéseken, akár a tér minden pontja megengedetté tehető. Ezután az algoritmus kioptimalizálja a pótváltozókat úgy, hogy értékük ne legyen pozitív.

Létezés

Karl Weierstrass szélsőértéktétele szerint kompakt halmazon értelmezett folytonos valós értékű függvény felveszi a minimumát és a maximumát. Általánosabban, kompakt halmazon értelmezett alulról félig folytonos függvény felveszi a minimumát, és kompakt halmazon értelmezett felülről félig folytonos függvény a maximumát.

Az optimum szükséges feltételei

Fermat stacionárius pontokról szóló tétele szerint a nem korlátos feladatok optimumai a stacionárius pontokban találhatók. Itt a célfüggvény gradiense vagy deriváltja nulla. Általánosabban, az optimumra jelöltek a stacionárius pontok; azok a pontok, ahol a célfüggvény nem deriválhatók; és a megengedett halmaz határa. Az elsőrendű feltétel egy egyenlet, amely a megengedett halmaz belsejében keres optimumot a célfüggvény deriváltjának felhasználásával, és azokat a pontokat keresi, ahol a derivált értéke nulla.

A Lagrange-szorzók módszere a Karush–Kuhn–Tucker-feltételek vagy a complementary slackness conditions felhasználásával, amelyek használhatók az optimum kiszámítására.

Az optimum elégséges feltételei

A derivált nullhelyei nem biztos, hogy szélsőértéket adnak. Erre példa az x³ függvény a nullában. Itt a derivált nulla, mégsincs helyi minimum vagy maximum. Ha a célfüggvény kétszer differenciálható, akkor ezek a pontok vizsgálhatók a második deriválttal, vagy a második deriváltak mátrixával (Hesse-mátrix). Korlátos megengedett halmaz esetén a korlátos Hesse-megkötések jelentenek további bizonyítékot. A másodrendű feltételek különbséget tesznek minimumok, maximumok és más stacionárius pontok között. Az elsőrendű feltételekkel kiválasztott megoldásjelöltek esetén a másodrendű módszerek legalább helyi optimumot bizonyítanak.

Az optimumok érzékenysége és folytonossága

A borítéktétel leírja, hogyan változik az optimum értéke, ahogy a paraméterek változnak. Ennek a kiszámítását összehasonlító statisztikának nevezik.

Claude Berge (1963) maximumtétele az optimális megoldás folytonosságát paraméterek függvényeként írja le.

Analízis

Ha a megengedett halmaz nem korlátos, és a célfüggvény kétszer differenciálható, akkor a gradiens vagy az első derivált nullhelyei kritikus pontok. Általánosabban, konvex célfüggvény és más lokálisan Lipschitz célfüggvények esetén a nulla szubgradiens bizonyítja, hogy az adott pont helyi minimum.

Továbbá a kritikus pontok tovább osztályozhatók az ottani Hesse-mátrix definitsége szerint. Ha a Hesse mátrix pozitív definit, akkor ott helyi minimum van. Ha a Hesse-mátrix negatív definit, akkor ott maximum van. Ha a Hesse-mátrix indefinit, akkor a pont nyeregpont.

A korlátos problémák a Lagrange-szorzókkal nem korlátossá alakíthatók. A Lagrange-relaxáció szintén képes közelítő megoldásokat adni bonyolult korlátos problémákra.

Ha a célfüggvény konvex, akkor bármely helyi minimum globális minimum lesz. A konvex függvények minimalizálására hatásos numerikus módszerek vannak, mint a belső pontos módszerek.

Módszerek

A feladatok megoldására véges lépésszámú vagy iteratív algoritmusokat használnak, amelyek közelítenek az optimumhoz. Használnak heurisztikus módszereket is, amelyek közelítő megoldást nyújtanak, habár konvergenciájuk nem szükségszerű.

Optimalizációs algoritmusok

• George Dantzig szimplex algoritmusa a lineáris programozás számára
• A szimplex algoritmus kiterjesztései a kvadratikus programozás és a törtlineáris programozás számára
• A szimplex algoritmus módosításai a hálózati optimalizálásra
• Kombinatorikus algoritmusok

Iteratív módszerek

A nemlineáris programozás iteratív módszerei osztályozhatók aszerint, hogy Hesse-mátrixokat, gradienseket vagy csak függvényértékeket értékelnek ki. A Hesse-mátrixok és a gradiensek használata javítja a konvergenciát, de növeli a bonyolultságot. Bizonyos esetekben ez a bonyolultság nagyon nagy lehet.

Általában a függvényértékek kiszámítása nehezebb, mint maga az eljárás. A deriváltak további hasznos információt nyújtanak, de még nehezebbek. Legalább N + 1 kiértékelést jelent N helyett. A második deriváltakat összegyűjtő Hesse-mátrix N² kiértékelést jelent. A Newton-módszer szintén második deriváltakat használ, ezért minden lépése N² kiértékelést igényel. A gradiens optimalizálók minden lépése csak N kiértékelést igényel, viszont lassabbak, így több iterációra van szüksége. A legjobb algoritmus választása inkább a feladattól függ.

A Hesse-mátrixot, vagy approximációját (differenciákkal) használó módszerek:

• Newton-módszer
  • Szekvenciális kvadratikus programozás: A Newton-módszeren alapuló kis és közepes skálán működő módszer. Egyes változatai magas dimenziószámú térben is működnek.

Gradienseken és közelítésükön, vagy szubgradiensen alapuló módszerek:

• Kvázi-Newton-módszerek: iteratív módszerek közepes dimenziószámra.
• Konjugált gradiens módszerek: magas dimenziókban is működő algoritmus. Habár a kvadratikus célfüggvényekre az elmélet szerint véges sok lépésben terminál, a véges pontosságú gépeken ezt nem lehet megfigyelni.
• Belsőpontos módszerek: módszerek egy nagy osztálya. Egyes fajtáik gradienssel, vagy szubgradienssel működnek, míg másoknak Hesse-mátrixra van szükségük.
• Gradiens módszer: Történetileg és az oktatásban fontos módszer, amit újra felfedeztek a bonyolult problémák megoldására.
• Szubgradiens módszerek: általánosított gradienseket használ lokálisan Lipschitz-függvényeket tartalmazó nagy problémákra. A konjugált gradiens módszerre hasonlítanak.
• Köteg leszállási módszer: alacsony dimenziós iterációs módszer lokálisan Lipschitz-függvényekkel a konvex minimalizációs feladatok megoldására.
• Ellipszoid-módszer: alacsony dimenziós iteráció kvázikonvex célfüggvényekre. Elméleti szempontból nagy az érdeklődés iránta, különösen azért, mert polinomiális időben old meg bizonyos kombinatorikus optimalizációs feladatokat. Hasonlít a kvázi-Newton módszerekre.
• Redukált gradiens módszer (Frank–Wolfe): speciális szerkezetű, lineáris megkötéseket tartalmazó feladatok megoldására, különösen közlekedési hálózatokra. Nem korlátos általános feladatok esetén átmegy a gradiens módszerbe, amit már csak nagyon ritkán alkalmaznak.
• Szimultán perturbációs sztochasztikus approximáció (SPSA): sztochasztikus feladatok megoldására alkalmas. Véletlen gradiens approximációt tartalmaz.

Csak a függvényértékeket használó módszerek: Ha a feladat folytonosan differenciálható, akkor a gradiensek közelíthetők differenciákkal. Ekkor használhatók a gradiens alapú módszerek is.

• Interpoláció
• Mintakereső módszerek, amelyek jobban konvergálnak, mint a Nelder–Mead-heurisztika.

Heurisztikák

Az optimalizációs algoritmusok és az iteratív módszerek mellett a heurisztikák közelítő megoldást tudnak adni néhány optimalizációs problémára:

• Memetikus algoritmus
• Differenciális evolúció
• Differenciális keresőalgoritmus, Matlab kódlink
• Dinamikus relaxáció
• Genetikus algoritmusok
• Hegymászó heurisztika
• Nelder–Mead szimpliciális heurisztika: a minimalizációs feladatok megoldásában népszerű heurisztika. Nem használ gradienseket.
• Részecskeraj optimalizáció
• Mesterséges méhkolónia optimalizáció
• Szimulált edzés
• Tabu keresés
• Reactive Search Optimization (RSO), LIONsolverben implementálva

Alkalmazásai

Mérnöki tudományok

A merev testek dinamikájának, különösen a csatolt részekből álló merev testek dinamikájának problémái gyakran igényelnek matematikai optimalizációs eszközöket, mivel a feladat tekinthető úgy is, hogy egy közönséges differenciálegyenletet kell megoldani egy korlátos sokaságon. A megkötések lehetnek nem lineáris geometriai korlátozások is, mint például, hogy ennek a két pontnak mindig egybe kell esnie, vagy ez a felület nem hatolhat át egy másik felületen, vagy hogy ennek a pontnak mindig ezen a görbén kell lennie. Az erők problémája megoldható lineáris komplementaritási problémaként, ami egy kvadratikus programozási probléma.

Több tervezési probléma kifejezhető optimalizációs feladatként. Ez az alkalmazás a tervezési optimalizáció. Ennek egy része a mérnöki optimalizáció, és egy másik új, és gyorsan fejlődő a multidiszciplináris tervezési optimalizáció.

Operációkutatás

Az operációkutatás szintén kiterjedten használja az optimalizációs módszereket. Emellett sztochasztikus modellezést és szimulációt is használ a döntéshozáshoz. A dinamikus döntéshozás modellezéséhez egyre inkább támaszkodik a sztochasztikus programozásra, hogy alkalmazkodjon az eseményekhez; ezek a problémák nagy skálájú optimalizációval és sztochasztikus optimalizációs módszerekkel oldhatók meg.

Gazdaság

A közgazdaság közel áll az ágensek optimalizálásához, mivel jó közelítést ad az emberek viselkedésére. A modern optimalizációelmélet magában foglalja a hagyományos optimalizáció elméletét és a játékelméletet, meg a gazdasági egyensúlyok tanulmányozását. A Journal of Economic Literature a JEL:C61-C63 alá sorolja a matematikai programozást, az optimalizáció módszereit és a kapcsolódó területeket.

A mikrogazdaságtanban a hasznosság maximalizálásának feladata és duálisa, a kiadás minimalizálásának problémája gazdaságtani optimalizációs problémák. A fogyasztókról felteszik, hogy maximalizálják a hasznosságukat, míg a cégek a hasznukat maximalizálják. Az ágenseket kockázatkerülőnek modellezik. Az árakat optimalizációelmélettel modellezik, azonban matematikailag a sztochasztikus optimalizáció megfelelőbb, mint a statikus optimalizáció. A kereskedelem elmélete szintén optimalizációval magyarázza a nemzetek közötti kereskedelmi mintákat. A piaci portfóliók a többcélú optimalizálásra adnak példát.

Az 1970-es évektől kezdve a közgazdászok a dinamikus döntéseket a control theory felhasználásával modellezik. A mikrogazdaságtanban a munkaerőpiacot dinamikus keresőmodellekkel tanulmányozzák. A determinisztikus és a sztochasztikus modellek között lényeges a különbségtétel. A makrogazdaságtanban a dinamikus sztochasztikus általános egyensúly (DSGE) modellekkel írják le a teljes gazdaság dinamikáját a dolgozók, a vállalatok, az állam és a feltalálók egymástól független optimalizációs döntéseinek eredményeként.

Források

Összefoglaló

Hallgatóknak

• Applied mathematical programming. Addison Wesley (1977) 
• Rardin, Ronald L.. Optimization in operations research. Prentice Hall, 919. o. (1997). ISBN 0-02-398415-5 
• Strang, Gilbert. Introduction to applied mathematics. Wellesley, MA: Wellesley-Cambridge Press (Strang's publishing company), xii+758. o. (1986). ISBN 0-9614088-0-4 
• William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1986). "Preface". Numerical Recipes: The Art of Scientific Computing. New York: Cambridge University Press. p. xi. ISBN 0-521-30811-9.

Diplomásoknak

• Magnanti, Thomas L.. Twenty years of mathematical programming, Contributions to Operations Research and Economics: The twentieth anniversary of CORE (Papers from the symposium held in Louvain-la-Neuve, January 1987). Cambridge, MA: MIT Press, 163–227. o. (1989). ISBN 0-262-03149-3 
• Minoux, M.. Mathematical programming: Theory and algorithms, Translated by Steven Vajda from the (1983 Paris: Dunod) French, Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd., xxviii+489. o.. (2008 Second ed., in French: Programmation mathématique: Théorie et algorithmes. Editions Tec & Doc, Paris, 2008. xxx+711 pp. ISBN 978-2-7430-1000-3. MR868279 (1986). ISBN 0-471-90170-9 
• Optimization, Handbooks in Operations Research and Management Science. Amsterdam: North-Holland Publishing Co., xiv+709. o. (1989). ISBN 0-444-87284-1 
  • J. E. Dennis, Jr. and Robert B. Schnabel, A view of unconstrained optimization (pp. 1–72);
  • Donald Goldfarb and Michael J. Todd, Linear programming (pp. 73–170);
  • Philip E. Gill, Walter Murray, Michael A. Saunders, and Margaret H. Wright, Constrained nonlinear programming (pp. 171–210);
  • Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin, Network flows (pp. 211–369);
  • W. R. Pulleyblank, Polyhedral combinatorics (pp. 371–446);
  • George L. Nemhauser and Laurence A. Wolsey, Integer programming (pp. 447–527);
  • Claude Lemaréchal, Nondifferentiable optimization (pp. 529–572);
  • Roger J-B Wets, Stochastic programming (pp. 573–629);
  • A. H. G. Rinnooy Kan and G. T. Timmer, Global optimization (pp. 631–662);
  • P. L. Yu, Multiple criteria decision making: five basic concepts (pp. 663–699).
• Shapiro, Jeremy F.. Mathematical programming: Structures and algorithms. New York: Wiley-Interscience [John Wiley & Sons], xvi+388. o. (1979) 
• Spall, J. C. (2003), Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control, Wiley, Hoboken, NJ.

Folytonos optimalizálás

• Mordecai Avriel. Nonlinear Programming: Analysis and Methods. Dover Publishing (2003). ISBN 0-486-43227-0 
• Numerical optimization: Theoretical and practical aspects, Second revised ed. of translation of 1997 French, Universitext, Berlin: Springer-Verlag, xiv+490. o.. DOI: 10.1007/978-3-540-35447-5 (2006). ISBN 3-540-35445-X 
• Perturbation analysis of optimization problems, Springer Series in Operations Research. New York: Springer-Verlag, xviii+601. o. (2000). ISBN 0-387-98705-3 
• Convex Optimization (pdf), Cambridge University Press (2004). ISBN 978-0-521-83378-3. Hozzáférés ideje: 2011. október 15. 
• Jorge Nocedal and Stephen J. Wright. Numerical Optimization. Springer (2006). ISBN 0-387-30303-0 
• Ruszczyński, Andrzej. Nonlinear Optimization. Princeton, NJ: Princeton University Press, xii+454. o. (2006). ISBN 978-0691119151 

Kombinatorikus optimalizáció

• R. K. Ahuja, Thomas L. Magnanti, and James B. Orlin (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Inc. ISBN 0-13-617549-X.
• William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver; Combinatorial Optimization; John Wiley & Sons; 1 edition (November 12, 1997); ISBN 0-471-55894-X.
• Graphs and algorithms, Translated by Steven Vajda from the second (Collection de la Direction des Études et Recherches d'Électricité de France [Collection of the Department of Studies and Research of Électricité de France], v. 37. Paris: Éditions Eyrolles 1985. xxviii+545 pp. MR868083) French, Wiley-Interscience Series in Discrete Mathematics, Chichester: John Wiley & Sons, Ltd., xix+650. o.. (Fourth ed. Collection EDF R&D. Paris: Editions Tec & Doc 2009. xxxii+784 pp. MR745802 (1984). ISBN 0-471-10374-8 
• Eugene Lawler. Combinatorial Optimization: Networks and Matroids. Dover (2001). ISBN 0-486-41453-1 
• Lawler, E. L.; Lenstra, J. K. & Rinnooy Kan, A. H. G. et al. (1985), The traveling salesman problem: A guided tour of combinatorial optimization, John Wiley & Sons, ISBN 0-471-90413-9.
• Jon Lee; A First Course in Combinatorial Optimization; Cambridge University Press; 2004; ISBN 0-521-01012-8.
• Christos H. Papadimitriou and Kenneth Steiglitz Combinatorial Optimization : Algorithms and Complexity; Dover Pubns; (paperback, Unabridged edition, July 1998) ISBN 0-486-40258-4.

Kapcsolódó szócikkek

• Lineáris programozás
• Szimplex módszer
• Operációkutatás