Robustní optimalizace - Robust optimization
Robustní optimalizace je obor optimalizace teorie, která se zabývá optimalizačními problémy, ve kterých se hledá určitá míra robustnosti nejistota která může být reprezentována 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 a používání analýza nejhoršího případu a Waldův model Maximin jako nástroj pro řešení 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 oborech. V průběhu let byl použit v statistika, ale také v operační výzkum,[1]elektrotechnika,[2][3] teorie řízení,[4] finance,[5] řízení portfolia[6] logistika,[7] výrobní inženýrství,[8] chemické inženýrství,[9] lék,[10] a počítačová věda. v inženýrství problémy, tyto formulace často nesou název „Robust Design Optimization“, RDO nebo „Reliability Based Design Optimization“, RBDO.
Příklad 1
Zvažte následující lineární programování problém
kde je daná podmnožina .
To, co z tohoto dělá problém „robustní optimalizace“, je klauzule v omezeních. Z toho vyplývá, že pro pár být přípustný, omezení musí být uspokojen nejhorší vztahující se k , jmenovitě pár který maximalizuje hodnotu pro danou hodnotu .
Pokud je prostor parametrů je konečný (skládající se z konečně mnoha prvků), pak je tento robustní optimalizační problém sám o sobě a lineární programování problém: pro každého existuje lineární omezení .
Li není konečná množina, pak je tento problém lineární napůl nekonečné programování problém, jmenovitě problém lineárního programování s konečně mnoha (2) rozhodovacími proměnnými a nekonečně mnoha omezeními.
Klasifikace
Existuje řada klasifikačních kritérií pro robustní optimalizační problémy / modely. Zejména lze rozlišovat mezi problémy, se kterými se vypořádáváme místní a globální modely robustnosti; a mezi pravděpodobnostní a bez pravděpodobnosti modely robustnosti. Moderní robustní optimalizace se zabývá především nepravděpodobnými modely robustnosti, které jsou nejhorší případ orientovaný a jako takový obvykle nasazen Waldovy modely Maximin.
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 poloměr stability Modelka:
kde označuje nominální hodnotu parametru, označuje kouli o poloměru se středem na a označuje množinu hodnot které splňují dané podmínky stability / výkonu spojené s rozhodnutím .
Slovy, robustnost (poloměr stability) rozhodnutí je poloměr největší koule se středem na všechny jehož prvky splňují požadavky na stabilitu kladené na . Obrázek je tento:
kde obdélník představuje množinu všech hodnot spojené s rozhodnutím .
Globální robustnost
Zvažte jednoduchý abstraktní robustní optimalizační problém
kde označuje množinu všech možný hodnoty v úvahu.
Tohle je globální robustní optimalizační problém ve smyslu omezení robustnosti představuje všechny možný hodnoty .
Potíž je v tom, že takové „globální“ omezení může být příliš náročné, protože neexistuje který splňuje toto omezení. Ale i když takový existuje, omezení může být příliš „konzervativní“ v tom, že poskytuje řešení který generuje velmi malou výplatu který nereprezentuje výkon jiných rozhodnutí v . Například by mohla existovat který jen mírně porušuje omezení robustnosti, ale přináší 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.
Příklad 2
Zvažte případ, kdy cílem je uspokojit omezení . kde označuje rozhodovací proměnnou a je parametr, jehož sada možných hodnot v . Pokud není takhle , pak se navrhuje následující intuitivní míra robustnosti:
kde označuje příslušnou míru „velikosti“ sady . Například pokud je tedy konečná množina lze definovat jako mohutnost sady .
Slovy, robustnost rozhodování je velikost největší podskupiny pro které je omezení je spokojen s každým v této sadě. Optimálním rozhodnutím je pak rozhodnutí, jehož robustnost je největší.
Tím se získá následující robustní problém s optimalizací:
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
kde je funkce se skutečnou hodnotou , a předpokládejme, že neexistuje proveditelné řešení tohoto problému z důvodu omezení robustnosti je příliš náročný.
Abychom tuto obtíž překonali, dovolme být relativně malou podmnožinou představující "normální" hodnoty a zvažte následující robustní problém s optimalizací:
Od té doby je mnohem menší než , jeho optimální řešení nemusí fungovat dobře na velké části a proto nemusí být robustní vůči variabilitě přes .
Jedním ze způsobů, jak tento problém vyřešit, je uvolnit omezení pro hodnoty mimo sadu kontrolovaným způsobem, aby byla povolena větší porušení jako vzdálenost z zvyšuje. Zvažte například omezení uvolněné robustnosti
kde je kontrolní parametr a označuje vzdálenost z . Tedy pro omezení uvolněné robustnosti se redukuje zpět na původní omezení robustnosti. Tím se získá následující (uvolněná) robustní optimalizace:
Funkce je definován takovým způsobem, že
a
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í
mimo .
Nepravděpodobné robustní optimalizační modely
Dominantním paradigmatem v této oblasti robustní optimalizace je Waldův model Maximin, jmenovitě
Kde představuje osobu s rozhodovací pravomocí, představuje přírodu, a to nejistota, představuje rozhodovací prostor a označuje množinu možných hodnot spojené s rozhodnutím . To je klasický formát generického modelu a je často označován jako minimax nebo maximin optimalizační problém. Pravděpodobnost (deterministický) model byl a je široce používán pro robustní optimalizaci, zejména v oblasti zpracování signálu.[11][12][13]
Ekvivalent matematické programování (MP) výše uvedeného klasického formátu je
Omezení lze do těchto modelů explicitně začlenit. Obecný omezený klasický formát je
Ekvivalentní omezený formát MP je definován jako:
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á optimalizace modely. Pravděpodobně robustní optimalizace si v poslední době získala popularitu zavedením přísných teorií jako např optimalizace scénáře schopen 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ý.[14]
Viz také
- Poloměr stability
- Minimax
- Odhad minimaxu
- Minimax lituje
- Robustní statistiky
- Robustní rozhodování
- Stochastické programování
- Stochastická optimalizace
- Teorie rozhodování o mezerách
- Taguchi metody
Reference
- ^ Bertsimas, Dimitris; Sim, Melvyn (2004). „Cena robustnosti“. Operační výzkum. 52 (1): 35–53. doi:10.1287 / opre.1030.0065.
- ^ Shabanzadeh M; Sheikh-El-Eslami, M-K; Haghifam, P; MR (říjen 2015). „Návrh nástroje zajišťujícího riziko pro virtuální elektrárny prostřednictvím robustního optimalizačního přístupu“. Aplikovaná energie. 155: 766–777. doi:10.1016 / j.apenergy.2015.06.059.
- ^ Shabanzadeh M; Fattahi, M (červenec 2015). Plánování údržby generace pomocí robustní optimalizace. 23. íránská konference v elektrotechnice (ICEE). 1504–1509. doi:10.1109 / IranianCEE.2015.7146458. ISBN 978-1-4799-1972-7.
- ^ Khargonekar, P.P .; Petersen, I.R .; Zhou, K. (1990). "Robustní stabilizace nejistých lineárních systémů: kvadratická stabilizace a teorie H / sup nekonečno / řízení". Transakce IEEE na automatickém ovládání. 35 (3): 356–361. doi:10.1109/9.50357.
- ^ Robustní optimalizace portfolia
- ^ Md. Asadujjaman a Kais Zaman, „Robustní optimalizace portfolia za nejistoty dat“, 15. národní statistická konference, prosinec 2014, Dháka, Bangladéš.
- ^ Yu, Chian-Son; Li, Han-Lin (2000). "Robustní optimalizační model pro stochastické logistické problémy". International Journal of Production Economics. 64 (1–3): 385–397. doi:10.1016 / S0925-5273 (99) 00074-2.
- ^ Strano, M (2006). "Optimalizace za nejistoty procesů tváření plechů metodou konečných prvků". Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture. 220 (8): 1305–1315. doi:10.1243 / 09544054JEM480.
- ^ Bernardo, Fernando P .; Saraiva, Pedro M. (1998). "Robustní optimalizační rámec pro návrh parametrů procesu a tolerance". AIChE Journal. 44 (9): 2007–2017. doi:10,1002 / aic.690440908. hdl:10316/8195.
- ^ Chu, Millie; Zinchenko, Yuriy; Henderson, Shane G; Sharpe, Michael B (2005). "Robustní optimalizace pro plánování léčby radiační terapií modulovanou intenzitou za nejistoty". Fyzika v medicíně a biologii. 50 (23): 5463–5477. doi:10.1088/0031-9155/50/23/003. PMID 16306645.
- ^ Verdu, S .; Chudák, H. V. (1984). „Na Minimax Robustness: Obecný přístup a aplikace“. Transakce IEEE na teorii informací. 30 (2): 328–340. CiteSeerX 10.1.1.132.837. doi:10.1109 / tit.1984.1056876.
- ^ Kassam, S. A .; Chudák, H. V. (1985). "Robustní techniky pro zpracování signálu: průzkum". Sborník IEEE. 73 (3): 433–481. doi:10.1109 / proc.1985.13167. hdl:2142/74118.
- ^ M. Danish Nisar. „Robustnost Minimax při zpracování signálu pro komunikaci“ Shaker Verlag, ISBN 978-3-8440-0332-1, Srpen 2011.
- ^ Ben-Tal A., El Ghaoui, L. a Nemirovski, A. (2009). Robustní optimalizace. Princeton Series in Applied Mathematics, Princeton University Press, 9-16.
Další čtení
- HJ Greenberg. Glosář matematického programování. Celosvětová Síť, http://glossary.computing.society.informs.org/, 1996-2006. Upraveno společností 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í, řada 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). Matematické programování, speciální vydání o robustní optimalizaci, Svazek 107 (1-2).
- Ben-Tal A., El Ghaoui, L. a Nemirovski, A. (2009). Robustní optimalizace. Princeton Series in Applied Mathematics, 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í návrh pro optimalizaci a robustnost pro inženýry John Wiley & Sons, Inc. ISBN 978-1-118-79619-1
- Gupta, S.K .; 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, J.M .; Vanderbei, R.J .; Zenios, S.A. (1995). "Robustní optimalizace rozsáhlých systémů". Operační výzkum. 43 (2): 264–281. doi:10.1287 / opre.43.2.264.
- Rosenblat, M. J. (1987). "Robustní přístup k návrhu zařízení". International Journal of Production Research. 25 (4): 479–486. doi:10.1080/00207548708919855.
- Rosenhead, M.J .; Elton, M; Gupta, S.K. (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.