Robustní optimalizace - Robust optimization

Robustní optimalizace je pole optimalizační teorie zabývající se optimalizačními problémy, ve kterém je hledána určitá míra robustnosti proti nejistotě, kterou lze reprezentovat jako deterministická variabilita v hodnotě parametrů samotného problému a / nebo jeho řešení.

Dějiny

Počátky robustní optimalizace sahají až do založení moderní teorie rozhodování v padesátých letech minulého století a použití analýzy nejhorších případů a Waldova modelu maximinů jako nástroje pro léčbu závažné nejistoty. Stala se vlastní disciplínou v 70. letech s paralelním vývojem v několika vědeckých a technologických oblastech. V průběhu let se uplatnil ve statistice , ale také v operačním výzkumu , elektrotechnice , teorii řízení , financích , logistice správy portfolia , výrobním inženýrství , chemickém inženýrství , medicíně a informatice . V technických problémech mají tyto formulace často název „Robust Design Optimization“, RDO nebo „Reliability Based Design Optimization“, RBDO.

Příklad 1

Zvažte následující problém lineárního programování

{\ displaystyle \ max _ {x, y} \ \ {3x + 2y \} \ \ \ mathrm {předmět \ to} \ \ x, y \ geq 0; cx + dy \ leq 10, \ forall (c, d ) \ v P}

kde je daná podmnožina . ${\ displaystyle P}$ ${\ displaystyle \ mathbb {R} ^ {2}}$

To, co z tohoto dělá problém „robustní optimalizace“, je klauzule v omezeních. Z toho vyplývá, že aby byl pár přípustný, musí být omezení uspokojeno tím nejhorším, co se ho týká , konkrétně dvojicí, která maximalizuje hodnotu pro danou hodnotu . ${\ displaystyle \ forall (c, d) \ v P}$ ${\ displaystyle (x, y)}$ ${\ displaystyle cx + dy \ leq 10}$ ${\ displaystyle (c, d) \ v P}$ ${\ displaystyle (x, y)}$ ${\ displaystyle (c, d) \ v P}$ ${\ displaystyle cx + dy}$ ${\ displaystyle (x, y)}$

Pokud je prostor parametrů konečný (skládající se z konečně mnoha prvků), pak je tento robustní optimalizační problém sám o sobě problémem lineárního programování : pro každý existuje lineární omezení . ${\ displaystyle P}$ ${\ displaystyle (c, d) \ v P}$ ${\ displaystyle cx + dy \ leq 10}$

Pokud to není konečná množina, pak je tento problém problémem lineárního polo nekonečného programování , konkrétně problémem lineárního programování s konečně mnoha (2) rozhodovacími proměnnými a nekonečně mnoha omezeními. ${\ displaystyle P}$

Klasifikace

Existuje řada klasifikačních kritérií pro robustní optimalizační problémy / modely. Zejména lze rozlišit mezi problémy s místními a globálními modely robustnosti; a mezi pravděpodobnostními a nepravděpodobnými modely robustnosti. Moderní robustní optimalizace se zabývá primárně nepravděpodobnými modely robustnosti, které jsou orientovány na nejhorší případy a jako takové obvykle nasazují Waldovy modely maximinu .

Místní robustnost

Existují případy, kdy se hledá robustnost proti malým poruchám ve jmenovité hodnotě parametru. Velmi oblíbeným modelem lokální robustnosti je model poloměru stability :

{\ displaystyle {\ hat {\ rho}} (x, {\ hat {u}}): = \ max _ {\ rho \ geq 0} \ \ {\ rho: u \ v S (x), \ forall u \ v B (\ rho, {\ hat {u}}) \}}

kde označuje nominální hodnotu parametru, označuje kouli o poloměru se středem na a označuje sadu hodnot, které splňují dané podmínky stability / výkonu spojené s rozhodnutím . ${\ displaystyle {\ hat {u}}}$ ${\ displaystyle B (\ rho, {\ hat {u}})}$ ${\ displaystyle \ rho}$ ${\ displaystyle {\ hat {u}}}$ ${\ displaystyle S (x)}$ ${\ displaystyle u}$ ${\ displaystyle x}$

Řečeno slovy, robustnost (poloměr stability) rozhodnutí je poloměr největší koule soustředěný u všech prvků, které splňují požadavky na stabilitu kladené . Obrázek je tento: ${\ displaystyle x}$ ${\ displaystyle {\ hat {u}}}$ ${\ displaystyle x}$

kde obdélník představuje množinu všech hodnot spojených s rozhodnutím . ${\ displaystyle U (x)}$ ${\ displaystyle u}$ ${\ displaystyle x}$

Globální robustnost

Zvažte jednoduchý abstraktní robustní optimalizační problém

{\ displaystyle \ max _ {x \ v X} \ \ {f (x): g (x, u) \ leq b, \ forall u \ v U \}}

kde označuje soubor všech možných uvažovaných hodnot . ${\ displaystyle U}$ ${\ displaystyle u}$

Jedná se o globální problém robustní optimalizace v tom smyslu, že omezení robustnosti představuje všechny možné hodnoty . ${\ displaystyle g (x, u) \ leq b, \ forall u \ in U}$ ${\ displaystyle u}$

Potíž je v tom, že takové „globální“ omezení může být příliš náročné, protože neexistuje žádné, které by toto omezení uspokojilo. Ale i když taková existence existuje, omezení může být příliš „konzervativní“ v tom, že přináší řešení, které generuje velmi malou výplatu, která nereprezentuje výkon ostatních rozhodnutí v . Mohlo by například dojít k tomu, že pouze mírně poruší omezení robustnosti, ale přinese velmi velkou výplatu . V takových případech může být nutné trochu uvolnit omezení robustnosti a / nebo upravit výrok problému. ${\ displaystyle x \ v X}$ ${\ displaystyle x \ v X}$ ${\ displaystyle x \ v X}$ ${\ displaystyle f (x)}$ ${\ displaystyle X}$ ${\ displaystyle x '\ v X}$ ${\ displaystyle f (x ')}$

Příklad 2

Zvažte případ, kdy cílem je uspokojit omezení . kde označuje rozhodovací proměnnou a je to parametr, jehož množina možných hodnot v . Pokud nic takového neexistuje , navrhne se následující intuitivní míra robustnosti: ${\ displaystyle g (x, u) \ leq b,}$ ${\ displaystyle x \ v X}$ ${\ displaystyle u}$ ${\ displaystyle U}$ ${\ displaystyle x \ v X}$ ${\ displaystyle g (x, u) \ leq b, \ forall u \ in U}$

{\ displaystyle \ rho (x): = \ max _ {Y \ subseteq U} \ \ {velikost (Y): g (x, u) \ leq b, \ forall u \ in Y \} \, \ x \ v X}

kde označuje příslušnou míru „velikosti“ množiny . Například pokud je konečná množina, pak by mohla být definována jako mohutnost množiny . ${\ velikost zobrazení (Y)}$ ${\ displaystyle Y}$ ${\ displaystyle U}$ ${\ velikost zobrazení (Y)}$ ${\ displaystyle Y}$

Stručně řečeno, robustnost rozhodování je velikost největší podskupiny, pro kterou je omezení splněno pro každou z této sady. Optimálním rozhodnutím je pak rozhodnutí, jehož robustnost je největší. ${\ displaystyle U}$ ${\ displaystyle g (x, u) \ leq b}$ ${\ displaystyle u}$

Tím se získá následující robustní problém s optimalizací:

{\ displaystyle \ max _ {x \ v X, Y \ subseteq U} \ \ {velikost (Y): g (x, u) \ leq b, \ forall u \ v Y \}}

Tato intuitivní představa globální robustnosti se v praxi často nepoužívá, protože robustní optimalizační problémy, které vyvolává, jsou obvykle (ne vždy) velmi obtížně řešitelné.

Příklad 3

Zvažte robustní optimalizační problém

{\ displaystyle z (U): = \ max _ {x \ v X} \ \ {f (x): g (x, u) \ leq b, \ forall u \ v U \}}

kde je funkce se skutečnou hodnotou a předpokládejme, že pro tento problém neexistuje proveditelné řešení, protože omezení robustnosti je příliš náročné. ${\ displaystyle g}$ ${\ displaystyle X \ krát U}$ ${\ displaystyle g (x, u) \ leq b, \ forall u \ in U}$

Abychom tento problém překonali, pojďme být relativně malou podmnožinou reprezentující „normální“ hodnoty a zvažte následující robustní optimalizační problém: ${\ displaystyle {\ mathcal {N}}}$ ${\ displaystyle U}$ ${\ displaystyle u}$

{\ displaystyle z ({\ mathcal {N}}): = \ max _ {x \ v X} \ \ {f (x): g (x, u) \ leq b, \ forall u \ in {\ mathcal {N}} \}}

Jelikož je mnohem menší než , jeho optimální řešení nemusí fungovat dobře na velké části a proto nemusí být robustní proti variabilitě over . ${\ displaystyle {\ mathcal {N}}}$ ${\ displaystyle U}$ ${\ displaystyle U}$ ${\ displaystyle u}$ ${\ displaystyle U}$

Jedním ze způsobů, jak vyřešit tento problém, je uvolnit omezení pro hodnoty mimo množinu kontrolovaným způsobem, takže jsou povolena větší porušení, protože vzdálenost od se zvyšuje. Zvažte například omezení uvolněné robustnosti ${\ displaystyle g (x, u) \ leq b}$ ${\ displaystyle u}$ ${\ displaystyle {\ mathcal {N}}}$ ${\ displaystyle u}$ ${\ displaystyle {\ mathcal {N}}}$

{\ displaystyle g (x, u) \ leq b + \ beta \ cdot dist (u, {\ mathcal {N}}) \, \ \ forall u \ in U}

kde je kontrolní parametr a označuje vzdálenost od . Tak, pro uvolněné robustnosti omezení snižuje zpět na původní robustnosti omezení. Tím se získá následující (uvolněný) robustní problém s optimalizací: ${\ displaystyle \ beta \ geq 0}$ ${\ displaystyle dist (u, {\ mathcal {N}})}$ ${\ displaystyle u}$ ${\ displaystyle {\ mathcal {N}}}$ ${\ displaystyle \ beta = 0}$

{\ displaystyle z ({\ mathcal {N}}, U): = \ max _ {x \ v X} \ \ {f (x): g (x, u) \ leq b + \ beta \ cdot dist (u , {\ mathcal {N}}) \, \ \ všichni u \ v U \}}

Funkce je definována takovým způsobem, že ${\ displaystyle dist}$

{\ displaystyle dist (u, {\ mathcal {N}}) \ geq 0, \ forall u \ in U}

a

{\ displaystyle dist (u, {\ mathcal {N}}) = 0, \ forall u \ in {\ mathcal {N}}}

a proto optimální řešení uvolněného problému splňuje původní omezení pro všechny hodnoty v . Rovněž uspokojuje uvolněné omezení ${\ displaystyle g (x, u) \ leq b}$ ${\ displaystyle u}$ ${\ displaystyle {\ mathcal {N}}}$

{\ displaystyle g (x, u) \ leq b + \ beta \ cdot dist (u, {\ mathcal {N}})}

venku . ${\ displaystyle {\ mathcal {N}}}$

Nepravděpodobné robustní optimalizační modely

Dominující paradigma v této oblasti robustní optimalizace je Wald je Maximin modelu , a to

{\ displaystyle \ max _ {x \ v X} \ min _ {u \ v U (x)} f (x, u)}

kde reprezentuje rozhodovatele, reprezentuje Nature, konkrétně nejistotu , představuje rozhodovací prostor a označuje soubor možných hodnot spojených s rozhodováním . Toto je klasický formát generického modelu a často se o něm říká, že se jedná o problém s optimalizací minimax nebo maximin . Nepravděpodobnostní ( deterministický ) model byl a je široce používán pro robustní optimalizaci, zejména v oblasti zpracování signálu. ${\ displaystyle \ max}$ ${\ displaystyle \ min}$ ${\ displaystyle X}$ ${\ displaystyle U (x)}$ ${\ displaystyle u}$ ${\ displaystyle x}$

Ekvivalentní matematické programování (MP) výše uvedeného klasického formátu je

{\ displaystyle \ max _ {x \ v X, v \ v \ mathbb {R}} \ \ {v: v \ leq f (x, u), \ forall u \ v U (x) \}}

Omezení lze do těchto modelů explicitně začlenit. Obecný omezený klasický formát je

{\ displaystyle \ max _ {x \ v X} \ min _ {u \ v U (x)} \ \ {f (x, u): g (x, u) \ leq b, \ forall u \ v U (X)\}}

Ekvivalentní omezený formát MP je definován jako:

{\ displaystyle \ max _ {x \ v X, v \ v \ mathbb {R}} \ \ {v: v \ leq f (x, u), g (x, u) \ leq b, \ forall u \ v U (x) \}}

Pravděpodobně robustní optimalizační modely

Tyto modely kvantifikují nejistotu ve „skutečné“ hodnotě sledovaného parametru pomocí funkcí rozdělení pravděpodobnosti. Byly tradičně klasifikovány jako stochastické programování a stochastické optimalizační modely. Pravděpodobně robustní optimalizace si v poslední době získala popularitu zavedením přísných teorií, jako je optimalizace scénářů schopných kvantifikovat úroveň robustnosti řešení získaných randomizací. Tyto metody jsou také relevantní pro metody optimalizace založené na datech.

Robustní protějšek

Metoda řešení mnoha robustních programů zahrnuje vytvoření deterministického ekvivalentu, který se nazývá robustní protějšek. Praktická obtížnost robustního programu závisí na tom, zda je jeho robustní protějšek výpočetně využitelný.

Viz také

Reference

Další čtení

HJ Greenberg. Glosář matematického programování. World Wide Web, http://glossary.computing.society.informs.org/ , 1996-2006. Upraveno INFORMS Computing Society.
Ben-Tal, A .; Nemirovski, A. (1998). "Robustní konvexní optimalizace". Matematika operačního výzkumu . 23 (4): 769–805. CiteSeerX 10.1.1.135.798 . doi : 10,1287 / bř . 23.4.769 .
Ben-Tal, A .; Nemirovski, A. (1999). "Robustní řešení nejistých lineárních programů". Dopisy o operačním výzkumu . 25 : 1–13. CiteSeerX 10.1.1.424.861 . doi : 10,1016 / s0167-6377 (99) 00016-4 .
Ben-Tal, A .; Arkadi Nemirovski, A. (2002). "Robustní optimalizace - metodologie a aplikace". Matematické programování, Series B . 92 (3): 453–480. CiteSeerX 10.1.1.298.7965 . doi : 10,1007 / s101070100286 .
Ben-Tal A., El Ghaoui, L. a Nemirovski, A. (2006). Mathematical Programming, Special issue on Robust Optimization, Volume 107 (1-2).
Ben-Tal A., El Ghaoui, L. a Nemirovski, A. (2009). Robustní optimalizace. Série Princeton v aplikované matematice, Princeton University Press.
Bertsimas, D .; Sim, M. (2003). "Robustní diskrétní optimalizace a síťové toky". Matematické programování . 98 (1–3): 49–71. CiteSeerX 10.1.1.392.4470 . doi : 10,1007 / s10107-003-0396-4 .
Bertsimas, D .; Sim, M. (2006). "Přibližná aproximace k problémům s robustní kuželovou optimalizací Dimitris Bertsimas". Matematické programování . 107 (1): 5–36. CiteSeerX 10.1.1.207.8378 . doi : 10,1007 / s10107-005-0677-1 .
Chen, W .; Sim, M. (2009). "Optimalizace zaměřená na cíl". Operační výzkum . 57 (2): 342–357. doi : 10,1287 / opre.1080.0570 .
Chen, X .; Sim, M .; Sun, P .; Zhang, J. (2008). „Přístup aproximace lineárního rozhodnutí ke stochastickému programování“. Operační výzkum . 56 (2): 344–357. doi : 10,1287 / opre.1070.0457 .
Chen, X .; Sim, M .; Sun, P. (2007). "Perspektiva robustní optimalizace na stochastické programování". Operační výzkum . 55 (6): 1058–1071. doi : 10,1287 / opre.1070.0441 .
Dembo, R (1991). "Optimalizace scénáře". Annals of Operations Research . 30 (1): 63–80. doi : 10,1007 / bf02204809 .
Dodson, B., Hammett, P. a Klerx, R. (2014) Pravděpodobnostní design pro optimalizaci a robustnost pro inženýry John Wiley & Sons, Inc. ISBN 978-1-118-79619-1
Gupta, SK; Rosenhead, J. (1968). "Robustnost při postupných investičních rozhodnutích". Věda o řízení . 15 (2): 18–29. doi : 10,1287 / mnsc.15.2.B18 .
Kouvelis P. a Yu G. (1997). Robustní diskrétní optimalizace a její aplikace, Kluwer.
Mutapcic, Almir; Boyd, Stephen (2009). "Metody řezací sady pro robustní konvexní optimalizaci s pesimizujícími věštci". Optimalizační metody a software . 24 (3): 381–406. CiteSeerX 10.1.1.416.4912 . doi : 10,1080 / 10556780802712889 .
Mulvey, JM; Vanderbei, RJ; Zenios, SA (1995). "Robustní optimalizace rozsáhlých systémů". Operační výzkum . 43 (2): 264–281. doi : 10,1287 / opre.43.2.264 .
Rosenblat, MJ (1987). "Robustní přístup k návrhu zařízení". International Journal of Production Research . 25 (4): 479–486. doi : 10.1080 / 00207548708919855 .
Rosenhead, MJ; Elton, M; Gupta, SK (1972). „Robustnost a optimalita jako kritéria pro strategická rozhodnutí“. Provozní výzkum čtvrtletně . 23 (4): 413–430. doi : 10,2307 / 3007957 . JSTOR 3007957 .
Rustem B. a Howe M. (2002). Algoritmy pro nejhorší design a aplikace pro řízení rizik, Princeton University Press.
Sniedovich, M (2007). „Umění a věda modelování rozhodování pod vážnou nejistotou“ . Rozhodování ve výrobě a službách . 1 (1–2): 111–136. doi : 10,7494 / dmms.2007.1.2.111 .
Sniedovich, M (2008). „Waldův Maximinův model: poklad v přestrojení!“. Journal of Risk Finance . 9 (3): 287–291. doi : 10,1108 / 15265940810875603 .
Sniedovich, M (2010). "Ptačí pohled na teorii rozhodování o informační mezeře". Journal of Risk Finance . 11 (3): 268–283. doi : 10,1108 / 15265941011043648 .
Wald, A (1939). "Příspěvky k teorii statistických odhadů a testování hypotéz" . Annals of Mathematics . 10 (4): 299–326. doi : 10,1214 / aoms / 1177732144 .
Wald, A (1945). "Statistické rozhodovací funkce, které minimalizují maximální riziko". Annals of Mathematics . 46 (2): 265–280. doi : 10,2307 / 1969022 . JSTOR 1969022 .
Wald, A. (1950). Statistické rozhodovací funkce, John Wiley, NY.
Shabanzadeh, Morteza; Fattahi, Mohammad (2015). "Plánování údržby generování pomocí robustní optimalizace". 2015 23. íránská konference o elektrotechnice . 1504–1509. doi : 10.1109 / IranianCEE.2015.7146458 . ISBN 978-1-4799-1972-7.

Languages

In other projects