Optimizarea robustă este un domeniu al teoriei optimizării matematice care se ocupă cu probleme de optimizare în care se urmărește o anumită măsură de robustețe împotriva incertitudinii ce poate fi reprezentată ca o variabilitate deterministică în valoarea parametrilor problemei și/sau a soluției acesteia. Este înrudită cu, dar adesea distinsă de, metodele de optimizare probabilistică, cum ar fi optimizarea cu restricții de probabilitate (chance-constrained optimization).

Istoric Originile optimizării robuste datează de la fundamentarea teoriei moderne a deciziei în anii 1950 și utilizarea analizei celui mai nefavorabil caz (worst-case analysis) și a ca instrument pentru tratarea incertitudinii severe. A devenit o disciplină de sine stătătoare în anii 1970, prin dezvoltări paralele în mai multe domenii științifice și tehnologice. De-a lungul anilor, a fost aplicată în statistică, dar și în , inginerie electrică, , finanțe,Robust portfolio optimization Md. Asadujjaman and Kais Zaman, "Robust Portfolio Optimization under Data Uncertainty" 15th National Statistical Conference, December 2014, Dhaka, Bangladesh. logistică, , inginerie chimică, medicină, și informatică. În problemele de inginerie, aceste formulări poartă adesea denumirea de „Optimizare a proiectării robuste” (RDO – Robust Design Optimization) sau „Optimizarea proiectării bazate pe fiabilitate” (RBDO – Reliability Based Design Optimization).

Exemplul 1

Se consideră următoarea problemă de programare liniară:

unde este o submulțime dată a lui .

Ceea ce face ca aceasta să fie o problemă de „optimizare robustă” este clauza din restricții. Implicația sa este că, pentru ca o pereche să fie admisibilă, restricția trebuie să fie satisfăcută pentru cel mai defavorabil caz asociat lui , și anume perechea care maximizează valoarea lui pentru valoarea dată a lui .

Dacă spațiul parametrilor este finit (format dintr-un număr finit de elemente), atunci această problemă de optimizare robustă este ea însăși o problemă de programare liniară: pentru fiecare există o restricție liniară .

Dacă nu este o mulțime finită, atunci această problemă este o problemă de liniară, mai exact o problemă de programare liniară cu un număr finit (2) de variabile de decizie și un număr infinit de restricții.

Clasificare Există o serie de criterii de clasificare pentru problemele/modelele de optimizare robustă. În special, se poate face distincția între probleme care tratează modele de robustețe locale și globale, precum și între modele de robustețe probabilistice și neprobabilistice. Optimizarea robustă modernă se ocupă în principal cu modele neprobabilistice de robustețe care sunt orientate spre (worst case) și, ca atare, utilizează de obicei modele de tip .

Robustețe locală

Există cazuri în care se caută robustețea împotriva micilor perturbații ale valorii nominale a unui parametru. Un model foarte popular de robustețe locală este modelul razei de stabilitate:

unde denotă valoarea nominală a parametrului, denotă o bilă de rază centrată în , iar denotă mulțimea valorilor lui care satisfac condițiile date de stabilitate/performanță asociate deciziei .

Pe scurt, robustețea (raza de stabilitate) deciziei este raza celei mai mari bile centrate în ale cărei elemente satisfac toate cerințele de stabilitate impuse lui . Reprezentarea grafică este următoarea:

500px

unde dreptunghiul reprezintă mulțimea tuturor valorilor asociate deciziei .

Robustețe globală

Se consideră problema abstractă simplă de optimizare robustă:

unde denotă mulțimea tuturor valorilor posibile ale lui luate în considerare.

Aceasta este o problemă de optimizare robustă „globală” în sensul că restricția de robustețe reprezintă toate valorile posibile ale lui .

Dificultatea constă în faptul că o astfel de restricție „globală” poate fi prea restrictivă, astfel încât să nu existe niciun care să o satisfacă. Dar chiar dacă un astfel de există, restricția poate fi prea „conservatoare”, generând o soluție cu un beneficiu foarte mic, nereprezentativ pentru performanța altor decizii din . De exemplu, ar putea exista un care încalcă doar ușor restricția de robustețe, dar oferă un beneficiu mult mai mare. În astfel de cazuri, poate fi necesară o relaxare a restricției de robustețe și/sau o modificare a formulării problemei.

Exemplul 2 Se consideră cazul în care obiectivul este satisfacerea unei restricții , unde denotă variabila de decizie, iar este un parametru a cărui mulțime de valori posibile este . Dacă nu există niciun astfel încât , atunci se sugerează următoarea măsură intuitivă a robusteții:

unde denotă o măsură adecvată a „mărimii” mulțimii . De exemplu, dacă este o mulțime finită, ar putea fi definită ca fiind mulțimii .

Cu alte cuvinte, robustețea unei decizii este mărimea celei mai mari submulțimi din pentru care restricția este îndeplinită pentru fiecare din această mulțime. O este atunci o decizie a cărei robustețe este maximă.

Aceasta conduce la următoarea problemă de optimizare robustă:

Această noțiune intuitivă de robustețe globală nu este folosită des în practică, deoarece problemele de optimizare robustă pe care le induce sunt de obicei (dar nu întotdeauna) foarte dificil de rezolvat.

Exemplul 3 Se consideră problema de optimizare robustă:

unde este o pe , și se presupune că nu există o soluție admisibilă pentru această problemă deoarece restricția de robustețe este prea exigentă.

Pentru a depăși această dificultate, fie o submulțime relativ mică a lui , care reprezintă valorile „normale” ale lui , și se consideră următoarea problemă de optimizare robustă:

Deoarece este mult mai mică decât , soluția sa optimală s-ar putea să nu aibă o performanță bună pe o porțiune mare din și, prin urmare, să nu fie robustă la variabilitatea lui pe .

O cale de rezolvare a acestei probleme este relaxarea restricției pentru valorile lui din afara mulțimii într-un mod controlat, astfel încât să fie permise abateri mai mari pe măsură ce distanța lui față de crește. De exemplu, se consideră restricția de robustețe relaxată:

unde este un parametru de control, iar denotă distanța lui față de . Astfel, pentru , restricția de robustețe relaxată se reduce la restricția de robustețe originală. Aceasta conduce la următoarea problemă de optimizare robustă (relaxată):

Funcția este definită astfel încât

și

prin urmare, soluția optimală a problemei relaxate satisface restricția originală pentru toate valorile lui din . De asemenea, satisface restricția relaxată

în afara lui .

Modele neprobabilistice de optimizare robustă

Paradigma dominantă în acest domeniu al optimizării robuste este , și anume:

unde reprezintă decidentul, reprezintă Natura (adică incertitudinea), reprezintă spațiul deciziilor, iar denotă mulțimea valorilor posibile ale lui asociate deciziei . Acesta este formatul clasic al modelului generic, fiind adesea numit problemă de optimizare minimax sau maximin. Modelul neprobabilistic (determinist) a fost și este utilizat pe scară largă pentru optimizarea robustă, în special în domeniul prelucrării semnalelor.M. Danish Nisar. "Minimax Robustness in Signal Processing for Communications", Shaker Verlag, , August 2011.

Formularea echivalentă prin programare matematică (MP) a formatului clasic de mai sus este:

Restricțiile pot fi încorporate explicit în aceste modele. Formatul clasic generic cu restricții este:

Formularea MP echivalentă cu restricții este definită ca:

Modele probabilistice de optimizare robustă Aceste modele cuantifică incertitudinea din valoarea „reală” a parametrului de interes prin funcții de distribuție de probabilitate. Ele au fost clasificate în mod tradițional ca modele de și . Recent, optimizarea probabilistică robustă a câștigat popularitate prin introducerea unor teorii riguroase, cum ar fi , capabile să cuantifice nivelul de robustețe al soluțiilor obținute prin randomizare. Aceste metode sunt de asemenea relevante pentru metodele de optimizare bazate pe date (data-driven optimization).

Echivalentul robust Metoda de rezolvare pentru multe probleme de programare robustă implică crearea unui echivalent determinist, numit „echivalentul robust” (robust counterpart). Dificultatea practică a unei probleme robuste depinde de caracterul tratabil din punct de vedere computațional al echivalentului său robust.Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2009). Robust Optimization. Princeton Series in Applied Mathematics, Princeton University Press, 9-16.Leyffer S., Menickelly M., Munson T., Vanaret C. and Wild S. M (2020). A survey of nonlinear robust optimization. INFOR: Information Systems and Operational Research, Taylor \& Francis.

Note

Lectură suplimentară H.J. Greenberg. Mathematical Programming Glossary. World Wide Web, http://glossary.computing.society.informs.org/, 1996-2006. Edited by the INFORMS Computing Society.

Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2006). Mathematical Programming, Special issue on Robust Optimization, Volume 107(1-2). Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2009). Robust Optimization. Princeton Series in Applied Mathematics, Princeton University Press.

Dodson, B., Hammett, P., and Klerx, R. (2014) Probabilistic Design for Optimization and Robustness for Engineers John Wiley & Sons, Inc.

Kouvelis P. and Yu G. (1997). Robust Discrete Optimization and Its Applications, Kluwer.

Nejadseyfi, O., Geijselaers H.J.M, van den Boogaard A.H. (2018). "Robust optimization based on analytical evaluation of uncertainty propagation". Engineering Optimization 51 (9): 1581-1603. doi:10.1080/0305215X.2018.1536752.

Rustem B. and Howe M. (2002). Algorithms for Worst-case Design and Applications to Risk Management, Princeton University Press.

Wald, A. (1950). Statistical Decision Functions, John Wiley, NY.

Vezi și Rază de stabilitate Minimax

Statistică robustă

Teoria deciziei bazată pe decalaj informațional

Legături externe ROME: Robust Optimization Made Easy Robust Decision-Making Under Severe Uncertainty Robustimizer: Robust optimization software

Categorie:Optimizare