Solidna optymalizacja - Robust optimization

Optymalizacja odporna jest dziedziną teorii optymalizacji, która zajmuje się problemami optymalizacyjnymi, w których poszukiwana jest pewna miara odporności na niepewność, którą można przedstawić jako deterministyczną zmienność wartości parametrów samego problemu i/lub jego rozwiązania.

Historia

Początki odpornej optymalizacji sięgają powstania nowoczesnej teorii decyzji w latach 50. XX wieku i wykorzystania analizy najgorszego przypadku oraz modelu maksyminy Walda jako narzędzia do leczenia dużej niepewności. Stała się odrębną dyscypliną w latach 70. z równoległym rozwojem w kilku dziedzinach naukowych i technologicznych. Z biegiem lat, została ona zastosowana w statystykach , ale także w badaniach operacyjnych , elektrotechniki , teorii sterowania , finansów , zarządzania portfelem logistyki , inżynierii produkcji , inżynierii chemicznej , medycynie i informatyce . W problemach inżynierskich formuły te często przyjmują nazwę „Robust Design Optimization”, RDO lub „Reliability Based Design Optimization”, RBDO.

Przykład 1

Rozważ następujący problem programowania liniowego

{\ Displaystyle \ max _ {x, y} \ \ {3x + 2y \} \ \ \ operatorname {temat \ do} \ \ x, y \ geq 0; cx + dy \ równoważnik 10, \ forall (c, d) )\w p}

gdzie jest dany podzbiór . $P$ ${\ Displaystyle \ mathbb {R} ^ {2}}$

To, co sprawia, że jest to problem „dokładnej optymalizacji”, to klauzula w ograniczeniach. Z tego wynika, że aby para była dopuszczalna, ograniczenie musi być spełnione przez najgorsze z , czyli parę, która maksymalizuje wartość dla danej wartości . ${\ Displaystyle \ forall (c, d) \ w P}$ $(x,y)$ $cx+dy\leq 10$ ${\ Displaystyle (c, d) \ w P}$ $(x,y)$ ${\ Displaystyle (c, d) \ w P}$ $cx+dy$ $(x,y)$

Jeśli przestrzeń parametrów jest skończona (składająca się ze skończenie wielu elementów), to ten problem solidnej optymalizacji sam w sobie jest problemem programowania liniowego : dla każdego istnieje ograniczenie liniowe . $P$ ${\ Displaystyle (c, d) \ w P}$ $cx+dy\leq 10$

Jeśli nie jest zbiorem skończonym, to problemem jest liniową pół-nieskończony programowanie problemem, a mianowicie zadania programowania liniowego z skończenie wielu zmiennych (2) Decyzja i nieskończenie wiele ograniczeń. $P$

Klasyfikacja

Istnieje szereg kryteriów klasyfikacyjnych dla problemów/modeli optymalizacji. W szczególności można rozróżnić problemy związane z lokalnymi i globalnymi modelami odporności; oraz między probabilistycznymi i nieprobabilistycznymi modelami odporności. Współczesna solidna optymalizacja zajmuje się głównie nieprobabilistycznymi modelami odporności, które są zorientowane na najgorszy przypadek i jako takie zwykle wykorzystują modele maksimin Walda .

Lokalna odporność

Istnieją przypadki, w których poszukuje się odporności na małe zakłócenia nominalnej wartości parametru. Bardzo popularnym modelem odporności lokalnej jest model promienia stateczności :

{\ Displaystyle {\ kapelusz {\ rho }} (x, {\ kapelusz {u}}): = \ max _ {\ rho \ geq 0} \ \ {\ rho: u \ w S (x), \ forall u\w B(\rho ,{\kapelusz {u}})\}}

gdzie oznacza nominalną wartość parametru, oznacza kulę o promieniu wyśrodkowanym na i oznacza zbiór wartości spełniających określone warunki stateczności/osiągów związane z decyzją . ${\kapelusz {u}}$ ${\ Displaystyle B (\ rho, {\ kapelusz {u}})}$ ${\ Displaystyle \ rho}$ ${\kapelusz {u}}$ ${\ Displaystyle S (x)}$ ${\ Displaystyle u}$ $x$

Mówiąc słowami, solidność (promień stateczności) decyzji jest promieniem największej kuli wyśrodkowanej na wszystkich, których elementy spełniają wymagania stateczności nałożone na . Obraz jest taki: $x$ ${\kapelusz {u}}$ $x$

gdzie prostokąt reprezentuje zbiór wszystkich wartości związanych z decyzja . ${\ Displaystyle U (x)}$ ${\ Displaystyle u}$ $x$

Globalna odporność

Rozważ prosty, abstrakcyjny i solidny problem optymalizacji

{\ Displaystyle \ max _ {x \ w X} \ \ {f (x): g (x, u) \ leq b, \ dla wszystkich u \ w U \}}

gdzie oznacza zbiór wszystkich możliwych wartości rozważanych. ${\ Displaystyle U}$ ${\ Displaystyle u}$

Jest to globalny problem solidnej optymalizacji w tym sensie, że ograniczenie odporności reprezentuje wszystkie możliwe wartości . $g(x,u)\leq b,\forall u\w u$ ${\ Displaystyle u}$

Trudność polega na tym, że takie „globalne” ograniczenie może być zbyt wymagające, ponieważ nie ma takiego ograniczenia, które by je spełniało. Ale nawet jeśli takie istnieje, ograniczenie może być zbyt „konserwatywne”, ponieważ daje rozwiązanie, które generuje bardzo małą wypłatę, która nie jest reprezentatywna dla wykonania innych decyzji w . Na przykład może istnieć błąd, który tylko nieznacznie narusza ograniczenie odporności, ale przynosi bardzo duże korzyści . W takich przypadkach może być konieczne złagodzenie ograniczenia odporności i/lub zmodyfikowanie opisu problemu. ${\ Displaystyle x \ w X}$ ${\ Displaystyle x \ w X}$ ${\ Displaystyle x \ w X}$ $f(x)$ ${\ Displaystyle X}$ $x'\w X$ $f(x')$

Przykład 2

Rozważ przypadek, w którym celem jest spełnienie ograniczenia . gdzie oznacza zmienną decyzyjną i jest parametrem, którego zbiór możliwych wartości w . Jeśli nie ma takiego , wówczas sugeruje się następująca intuicyjna miara odporności: $g(x,u)\leq b$ ${\ Displaystyle x \ w X}$ ${\ Displaystyle u}$ ${\ Displaystyle U}$ ${\ Displaystyle x \ w X}$ $g(x,u)\leq b,\forall u\w u$

{\ Displaystyle \ rho (x): = \ max _ {Y \ subseteq U} \ \ {rozmiar (Y): g (x, u) \ leq b, \ forall u \ w Y \} \ , \ x\ w X}

gdzie oznacza odpowiednią miarę „rozmiaru” zbioru . Na przykład, jeśli jest zbiorem skończonym, to można by go zdefiniować jako liczność zbioru . ${\ Displaystyle rozmiar (Y)}$ ${\ Displaystyle Y}$ ${\ Displaystyle U}$ ${\ Displaystyle rozmiar (Y)}$ ${\ Displaystyle Y}$

Mówiąc słownie, solidność decyzji jest wielkością największego podzbioru, dla którego ograniczenie jest spełnione dla każdego w tym zbiorze. Optymalna decyzja jest wtedy decyzją, której odporność jest największa. ${\ Displaystyle U}$ $g(x,u)\leq b$ ${\ Displaystyle u}$

Daje to następujący solidny problem optymalizacji:

{\ Displaystyle \ max _ {x \ w X, Y \ subseteq U} \ \ {rozmiar (Y): g (x, u) \ leq b, \ forall u \ w Y \}}

To intuicyjne pojęcie globalnej odporności nie jest często używane w praktyce, ponieważ problemy z niezawodną optymalizacją, które ono wywołuje, są zwykle (nie zawsze) bardzo trudne do rozwiązania.

Przykład 3

Rozważ problem solidnej optymalizacji

{\ Displaystyle z (U): = \ max _ {x \ w X} \ \ {f (x): g (x, u) \ leq b \ dla wszystkich u \ w U \}}

gdzie jest funkcją o wartościach rzeczywistych on i załóżmy, że nie ma wykonalnego rozwiązania tego problemu, ponieważ ograniczenie odporności jest zbyt wymagające. $g$ ${\ Displaystyle X \ razy U}$ $g(x,u)\leq b,\forall u\w u$

Aby przezwyciężyć tę trudność, stwórzmy stosunkowo mały podzbiór reprezentujący „normalne” wartości i rozważmy następujący problem niezawodnej optymalizacji: ${\ Displaystyle {\ Mathcal {N}}}$ ${\ Displaystyle U}$ ${\ Displaystyle u}$

{\ Displaystyle Z ({\ mathcal {N}}): = \ max _ {x \ w X} \ \ {f (x): g (x, u) \ leq b \ dla wszystkich u \ w {\ mathcal {N}}\}}

Ponieważ jest znacznie mniejszy niż , jego optymalne rozwiązanie może nie działać dobrze na dużej części , a zatem może nie być odporne na zmienność ponad . ${\ Displaystyle {\ Mathcal {N}}}$ ${\ Displaystyle U}$ ${\ Displaystyle U}$ ${\ Displaystyle u}$ ${\ Displaystyle U}$

Jednym ze sposobów rozwiązania tej trudności jest rozluźnienie ograniczenia dla wartości poza zbiorem w sposób kontrolowany, tak aby dozwolone były większe naruszenia w miarę zwiększania odległości od wartości . Rozważmy na przykład rozluźnione ograniczenie odporności $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}}) \ \ \ dla wszystkich u \ w U}

gdzie jest parametrem kontrolnym i oznacza odległość od . W związku z tym, dla rozluźnionego ograniczenia odporności wraca się do pierwotnego ograniczenia odporności. Daje to następujący (zrelaksowany) solidny problem optymalizacji: ${\ Displaystyle \ beta \ geq 0}$ ${\ Displaystyle dist (u {\ mathcal {N}})}$ ${\ Displaystyle u}$ ${\ Displaystyle {\ Mathcal {N}}}$ ${\ Displaystyle \ beta = 0}$

{\ Displaystyle z ({\ mathcal {N}}, U): = \ max _ {x \ w X} \ \ {f (x): g (x, u) \ leq b + \ beta \ cdot odl. (u ,{\mathcal {N}})\ ,\ \dla wszystkich u\w U\}}

Funkcja jest zdefiniowana w taki sposób, że $dist$

{\ Displaystyle dist (u {\ mathcal {N}}) \ geq 0 \ forall u \ w U}

i

{\ Displaystyle dist (u {\ mathcal {N}}) = 0, \ dla wszystkich u \ w {\ mathcal {N}}}

i dlatego optymalne rozwiązanie zrelaksowanego problemu spełnia pierwotne ograniczenie dla wszystkich wartości in . Spełnia również zrelaksowane ograniczenie $g(x,u)\leq b$ ${\ Displaystyle u}$ ${\ Displaystyle {\ Mathcal {N}}}$

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

na zewnątrz . ${\ Displaystyle {\ Mathcal {N}}}$

Nieprobabilistyczne odporne modele optymalizacji

Dominującym paradygmatem w tym obszarze odpornej optymalizacji jest maksymalizacyjny model Walda , a mianowicie:

{\ Displaystyle \ max _ {x \ w X} \ min _ {u \ w U (x)} f (x, u)}

gdzie reprezentuje decydenta, reprezentuje Naturę, czyli niepewność , reprezentuje przestrzeń decyzyjną i oznacza zbiór możliwych wartości związanych z decyzją . Jest to klasyczny format modelu generycznego i jest często określany jako problem optymalizacji minimax lub maximin . Model nieprobabilistyczny ( deterministyczny ) był i jest szeroko stosowany do solidnej optymalizacji, zwłaszcza w dziedzinie przetwarzania sygnałów. $\max$ $\min$ ${\ Displaystyle X}$ ${\ Displaystyle U (x)}$ ${\ Displaystyle u}$ $x$

Równoważne programowanie matematyczne (MP) powyższego klasycznego formatu to

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

W tych modelach można wyraźnie włączyć ograniczenia. Ogólny ograniczony format klasyczny to

{\ Displaystyle \ max _ {x \ w X} \ min _ {u \ w U (x)} \ \ {f (x, u): g (x, u) \ równoważnik b \ dla wszystkich u \ w U (x)\}}

Równoważny ograniczony format MP jest zdefiniowany jako:

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

Modele optymalizacji probabilistycznie odporne

Modele te określają ilościowo niepewność „prawdziwej” wartości interesującego parametru za pomocą funkcji rozkładu prawdopodobieństwa. Tradycyjnie klasyfikowano je jako programowanie stochastyczne i modele optymalizacji stochastycznej . Ostatnio popularność zyskała probabilistycznie odporna optymalizacja dzięki wprowadzeniu rygorystycznych teorii, takich jak optymalizacja scenariuszy, która jest w stanie określić ilościowo poziom niezawodności rozwiązań uzyskanych przez randomizację. Metody te są również istotne dla metod optymalizacji opartych na danych.

Solidny odpowiednik

Metoda rozwiązania wielu solidnych programów polega na stworzeniu deterministycznego odpowiednika, zwanego odpornym odpowiednikiem. Praktyczna trudność solidnego programu zależy od tego, czy jego solidny odpowiednik jest wykonalny obliczeniowo.

Zobacz też

Bibliografia

Dalsza lektura

HJ Greenberga. Słownik programowania matematycznego. Sieć WWW, http://glossary.computing.society.informs.org/ , 1996-2006. Wydane przez INFORMS Computing Society.
Ben-Tal, A.; Niemirowski, A. (1998). „Solidna wypukła optymalizacja”. Matematyka badań operacyjnych . 23 (4): 769-805. CiteSeerX 10.1.1.135.798 . doi : 10.1287/moor.23.4.769 .
Ben-Tal, A.; Niemirowski, A. (1999). „Solidne rozwiązania niepewnych programów liniowych”. Listy z badań operacyjnych . 25 : 1–13. CiteSeerX 10.1.1.424.861 . doi : 10.1016/s0167-6377(99)00016-4 .
Ben-Tal, A.; Arkadi Niemirowski, A. (2002). „Solidna optymalizacja — metodologia i zastosowania”. Programowanie matematyczne, seria B . 92 (3): 453-480. CiteSeerX 10.1.1.298.7965 . doi : 10.1007/s101070100286 .
Ben-Tal A., El Ghaoui, L. i Nemirovski, A. (2006). Programowanie matematyczne, wydanie specjalne na temat solidnej optymalizacji, tom 107(1-2).
Ben-Tal A., El Ghaoui, L. i Nemirovski, A. (2009). Solidna optymalizacja. Seria Princeton w matematyce stosowanej, Princeton University Press.
Bertsimas, D.; Sim, M. (2003). „Solidna dyskretna optymalizacja i przepływy sieciowe”. Programowanie matematyczne . 98 (1–3): 49–71. CiteSeerX 10.1.1.392.4470 . doi : 10.1007/s10107-003-0396-4 .
Bertsimas, D.; Sim, M. (2006). „Wykonalne przybliżenia do solidnych problemów optymalizacji stożkowej Dimitris Bertsimas”. Programowanie matematyczne . 107 (1): 5-36. CiteSeerX 10.1.1.207.8378 . doi : 10.1007/s10107-005-0677-1 .
Chen, W.; Sim, M. (2009). „Optymalizacja zorientowana na cel”. Badania operacyjne . 57 (2): 342–357. doi : 10.1287/opre.1080.0570 .
Chen, X.; Sim, M.; Słońce, P.; Zhang, J. (2008). „Podejście aproksymacyjne oparte na decyzji liniowej do programowania stochastycznego”. Badania operacyjne . 56 (2): 344–357. doi : 10.1287/opre.1070.0457 .
Chen, X.; Sim, M.; Słońce, P. (2007). „Solidna perspektywa optymalizacji programowania stochastycznego”. Badania operacyjne . 55 (6): 1058–1071. doi : 10.1287/opre.1070.0441 .
Dembo, R (1991). „Optymalizacja scenariusza”. Roczniki Badań Operacyjnych . 30 (1): 63–80. doi : 10.1007/bf02204809 .
Dodson, B., Hammett, P. i Klerx, R. (2014) Probabilistic Design for Optimization and Solidness for Engineers John Wiley & Sons, Inc. ISBN 978-1-118-79619-1
Gupta, SK; Rosenhead, J. (1968). „Solidność w sekwencyjnych decyzjach inwestycyjnych”. Nauka o zarządzaniu . 15 (2): 18–29. doi : 10.1287/mnsc.15.2.B18 .
Kouvelis P. i Yu G. (1997). Solidna optymalizacja dyskretna i jej zastosowania, Kluwer.
Mutapcic, Almir; Boyd, Stephen (2009). „Metody cięcia-set dla solidnej optymalizacji wypukłej z pesymistycznymi wyroczniami”. Metody optymalizacji i oprogramowanie . 24 (3): 381-406. CiteSeerX 10.1.1.416.4912 . doi : 10.1080/10556780802712889 .
Mulvey, JM; Vanderbei, RJ; Zenios SA (1995). „Solidna optymalizacja systemów wielkoskalowych”. Badania operacyjne . 43 (2): 264–281. doi : 10.1287/opre.43.2.264 .
Rosenblat, MJ (1987). „Solidne podejście do projektowania obiektów”. Międzynarodowy Dziennik Badań nad Produkcją . 25 (4): 479–486. doi : 10.1080/00207548708919855 .
Rosenhead, MJ; Eltona, M; Gupta, SK (1972). „Solidność i optymalność jako kryteria decyzji strategicznych”. Kwartalnik Badań Operacyjnych . 23 (4): 413–430. doi : 10.2307/3007957 . JSTOR 3007957 .
Rustem B. i Howe M. (2002). Algorytmy projektowania najgorszego przypadku i zastosowania w zarządzaniu ryzykiem, Princeton University Press.
Śniedowicz, M (2007). „Sztuka i nauka modelowania podejmowania decyzji w warunkach silnej niepewności” . Podejmowanie decyzji w produkcji i usługach . 1 (1–2): 111–136. doi : 10.7494/dmms.2007.1.2.111 .
Śniedowicz, M (2008). „Wald's Maximin Model: skarb w przebraniu!”. Dziennik Finansów Ryzyka . 9 (3): 287–291. doi : 10.1108/15265940810875603 .
Śniedowicz, M (2010). „Widok z lotu ptaka teorii decyzji o lukach informacyjnych”. Dziennik Finansów Ryzyka . 11 (3): 268–283. doi : 10.1108/15265941011043648 .
Wald, A (1939). „Wkład do teorii estymacji statystycznej i testowania hipotez” . Roczniki Matematyki . 10 (4): 299–326. doi : 10.1214/aoms/1177732144 .
Wald, A (1945). „Statystyczne funkcje decyzyjne, które minimalizują maksymalne ryzyko”. Roczniki Matematyki . 46 (2): 265–280. doi : 10.2307/1969022 . JSTOR 1969022 .
Wald, A. (1950). Statystyczne funkcje decyzyjne, John Wiley, NY.
Szabanzade, Morteza; Fattahi, Mahomet (2015). „Planowanie konserwacji generacji dzięki solidnej optymalizacji”. 2015 23. Irańska Konferencja Elektrotechniki . s. 1504-1509. doi : 10.1109/IranianCEE.2015.7146458 . Numer ISBN 978-1-4799-1972-7.

Languages

In other projects