Robust optimization: Difference between revisions

Revision as of 18:38, 27 June 2017

Latest revision as of 08:15, 27 August 2025

(46 intermediate revisions by 31 users not shown)

Line 1:

{{Short description|Mathematical optimization theory}}

'''Robust optimization''' is a field of [[optimization (mathematics)|optimization]] theory that deals with optimization problems in which a certain measure of robustness is sought against [[uncertainty]] that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution.

'''Robust optimization''' is a field of [[mathematical optimization]] theory that deals with optimization problems in which a certain measure of robustness is sought against [[uncertainty]] that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution. It is related to, but often distinguished from, [[probabilistic optimization]] methods such as chance-constrained optimization.<ref>{{cite journal | doi=10.3390/en15030825 | doi-access=free | title=Probabilistic Optimization Techniques in Smart Power System | date=2022 | last1=Riaz | first1=Muhammad | last2=Ahmad | first2=Sadiq | last3=Hussain | first3=Irshad | last4=Naeem | first4=Muhammad | last5=Mihet-Popa | first5=Lucian | journal=Energies | volume=15 | issue=3 | page=825 | hdl=11250/2988376 | hdl-access=free }}</ref><ref>{{Cite web| title=Robust Optimization: Chance Constraints | date=2008-04-28 | url=https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture24.pdf | archive-url=https://web.archive.org/web/20230605233436/https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture24.pdf | archive-date=2023-06-05}}</ref>

== History ==

The origins of robust optimization date back to the establishment of modern [[decision theory]] in the 1950s and the use of '''worst case analysis''' and [[Wald's maximin model]] as a tool for the treatment of severe uncertainty. It became a discipline of its own in the 1970s with parallel developments in several scientific and technological fields. Over the years, it has been applied in [[statistics]], but also in [[operations research]],<ref>{{cite journal|last=Bertsimas|first=Dimitris|author2=Sim, Melvyn |title=The Price of Robustness|journal=Operations Research|year=2004|volume=52|issue=1|pages=35–53|doi=10.1287/opre.1030.0065|hdl=2268/253225 |s2cid=8946639 |hdl-access=free}}</ref> [[electrical engineering]],<ref>{{Cite journal |last1=Giraldo |first1=Juan S. |last2=Castrillon |first2=Jhon A. |last3=Lopez |first3=Juan Camilo |last4=Rider |first4=Marcos J. |last5=Castro |first5=Carlos A. |date=July 2019 |title=Microgrids Energy Management Using Robust Convex Programming |journal=IEEE Transactions on Smart Grid |volume=10 |issue=4 |pages=4520–4530 |doi=10.1109/TSG.2018.2863049 |bibcode=2019ITSG...10.4520G |s2cid=115674048 |issn=1949-3053}}</ref><ref name="VPP Robust 2015">{{Cite journal| title = The design of a risk-hedging tool for virtual power plants via robust optimization approach | journal= Applied Energy | date = October 2015 | doi = 10.1016/j.apenergy.2015.06.059 | author = Shabanzadeh M | volume = 155 | pages = 766–777 | last2 = Sheikh-El-Eslami | first2 = M-K |last3 = Haghifam | first3 = P|last4 = M-R| bibcode= 2015ApEn..155..766S }}</ref><ref name="RO2015">{{Cite journalbook| title pages= Generation Maintenance Scheduling via robust optimization | journal= 23rd Iranian Conference in Electrical Engineering (ICEE)1504–1509 | date = July 2015 | doi = 10.1109/IranianCEE.2015.7146458 | author = Shabanzadeh M | last2 = Fattahi | first2 = M | title= 2015 23rd Iranian Conference on Electrical Engineering | chapter= Generation Maintenance Scheduling via robust optimization | isbn= 978-1-4799-1972-7 | s2cid= 8774918 }}</ref> [[control theory]],<ref>{{cite journal|last=Khargonekar|first=P.P.|author2=Petersen, I.R. |author3=Zhou, K. |title=Robust stabilization of uncertain linear systems: quadratic stabilizability and H/sup infinity / control theory|journal=IEEE Transactions on Automatic Control|volume=35|issue=3|pages=356–361|doi=10.1109/9.50357|year=1990}}</ref> [[finance]],<ref>[https://books.google.com/books?id=p6UHHfkQ9Y8C&lpg=PR11&ots=AqlJfX5Z0X&dq=economics%20robust%20optimization&lr&hl=it&pg=PR11#v=onepage&q&f=false%20 Robust portfolio optimization]</ref> [[Investment management|portfolio management]]<ref>Md. Asadujjaman and Kais Zaman, "Robust Portfolio Optimization under Data Uncertainty" 15th National Statistical Conference, December 2014, Dhaka, Bangladesh.</ref> [[logistics]],<ref>{{cite journal|last=Yu|first=Chian-Son|author2=Li, Han-Lin |title=A robust optimization model for stochastic logistic problems|journal=International Journal of Production Economics|volume=64|issue=1-31–3|pages=385–397|doi=10.1016/S0925-5273(99)00074-2|year=2000}}</ref> [[manufacturing engineering]],<ref>{{cite journal|last=Strano|first=M|title=Optimization under uncertainty of sheet-metal-forming processes by the finite element method|journal=Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture|volume=220|issue=8|pages=1305–1315|doi=10.1243/09544054JEM480|year=2006|s2cid=108843522}}</ref> [[chemical engineering]],<ref>{{cite journal|last=Bernardo|first=Fernando P.|author2=Saraiva, Pedro M. |title=Robust optimization framework for process parameter and tolerance design|journal=AIChE Journal|year=1998|volume=44|issue=9|pages=2007–2017|doi=10.1002/aic.690440908|bibcode=1998AIChE..44.2007B |hdl=10316/8195|hdl-access=free}}</ref> [[medicine]],<ref>{{cite journal|last=Chu|first=Millie|author2=Zinchenko, Yuriy |author3=Henderson, Shane G |author4= Sharpe, Michael B |title=Robust optimization for intensity modulated radiation therapy treatment planning under uncertainty|journal=Physics in Medicine and Biology|year=2005|volume=50|issue=23|pages=5463–5477|doi=10.1088/0031-9155/50/23/003|pmid=16306645|bibcode=2005PMB....50.5463C |s2cid=15713904 }}</ref> and [[computer science]]. In [[engineering]] problems, these formulations often take the name of "Robust Design Optimization", RDO or "Reliability Based Design Optimization", RBDO.

== Example 1==

Line 11 ⟶ 12:

where <math>P</math> is a given subset of <math>\mathbb{R}^{2}</math>.

What makes this a 'robust optimization' problem is the <math>\forall (c,d)\in P</math> clause in the constraints. Its implication is that for a pair <math>(x,y)</math> to be admissible, the constraint <math>cx + dy \le 10</math> must be satisfied by the '''worst''' <math>(c,d)\in P</math> pertaining to <math>(x,y)</math>, namely the pair <math>(c,d)\in P</math> that maximizes the value of <math>3xcx + 2ydy</math> for the given value of <math>(x,y)</math>.

If the parameter space <math>P</math> is finite (consisting of finitely many elements), then this robust optimization problem itself is a [[linear programming]] problem: for each <math>(c,d)\in P</math> there is a linear constraint <math>cx + dy \le 10</math>.

Line 86 ⟶ 87:

: <math>dist(u,\mathcal{N})= 0,\forall u\in \mathcal{N}</math>

and therefore the optimal solution to the relaxed problem satisfies the original constraint <math>g(x,u)\le b</math> for all values of <math>u</math> in <math>\mathcal{N}</math>. In addition, itIt also satisfies the relaxed constraint

: <math>g(x,u)\le b + \beta \cdot dist(u,\mathcal{N})</math>

Line 97 ⟶ 98:

: <math>\max_{x\in X}\min_{u\in U(x)} f(x,u)</math>

where the <math>\max</math> represents the decision maker, the <math>\min</math> represents Nature, namely [[uncertainty]], <math>X</math> represents the decision space and <math>U(x)</math> denotes the set of possible values of <math>u</math> associated with decision <math>x</math>. This is the ''classic'' format of the generic model, and is often referred to as ''minimax'' or ''maximin'' optimization problem. The non-probabilistic ('''deterministic''') model has been and is being extensively used for robust optimization especially in the field of signal processing.<ref>{{cite journal | last1 = Verdu | first1 = S. | last2 = Poor | first2 = H. V. | year = 1984 | title = On Minimax Robustness: A general approach and applications | url = | journal = IEEE Transactions on Information Theory | volume = 30 | issue = 2| pages = 328–340 | doi=10.1109/tit.1984.1056876| citeseerx = 10.1.1.132.837 }}</ref><ref>{{cite journal | last1 = Kassam | first1 = S. A. | last2 = Poor | first2 = H. V. | year = 1985 | title = Robust Techniques for Signal Processing: A Survey | url = | journal = Proceedings of the IEEE | volume = 73 | issue = 3| pages = 433–481 | doi=10.1109/proc.1985.13167| hdl = 2142/74118 | s2cid = 30443041 | hdl-access = free }}</ref><ref>M. Danish Nisar. [httphttps://www.shaker.eu/shop/978-3-8440-0332-1 "Minimax Robustness in Signal Processing for Communications"], Shaker Verlag, {{ISBN|978-3-8440-0332-1}}, August 2011.</ref>

The equivalent [[mathematical programming]] (MP) of the classic format above is

Line 111 ⟶ 112:

:<math>\max_{x\in X,v\in \mathbb{R}} \ \{v: v\le f(x,u), g(x,u)\le b, \forall u\in U(x)\}</math>

===ProbabilisticProbabilistically robust optimization models===

These models quantify the uncertainty in the "true" value of the parameter of interest by probability distribution functions. They have been traditionally classified as [[stochastic programming]] and [[stochastic optimization]] models. Recently, probabilistically robust optimization has gained popularity by the introduction of rigorous theories such as [[scenario optimization]] able to quantify the robustness level of solutions obtained by randomization. These methods are also relevant to data-driven optimization methods.

===Robust counterpart===

The solution method to many robust program involves creating a deterministic equivalent, called the robust counterpart. The practical difficulty of a robust program depends on if its robust counterpart is computationally tractable.<ref>Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2009). Robust Optimization. ''Princeton Series in Applied Mathematics,'' Princeton University Press, 9-16.</ref><ref>[[Sven Leyffer|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.</ref>

== See also ==

Line 124 ⟶ 125:

* [[Robust statistics]]

* [[Robust decision making]]

* [[Robust fuzzy programming]]

* [[Stochastic programming]]

* [[Stochastic optimization]]

Line 135 ⟶ 137:

== Further reading ==

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

*{{cite journal | last1 = Ben-Tal | first1 = A. | last2 = Nemirovski | first2 = A. | year = 1998 | title = Robust Convex Optimization | url = | journal = [[Mathematics of Operations Research]] | volume = 23 | issue = 4| pages = 769–805 | doi=10.1287/moor.23.4.769| citeseerx = 10.1.1.135.798 | s2cid = 15905691 }}

*{{cite journal | last1 = Ben-Tal | first1 = A. | last2 = Nemirovski | first2 = A. | year = 1999 | title = Robust solutions to uncertain linear programs | url = | journal = [[Operations Research Letters]] | volume = 25 | issue = | pages = 1–13 | doi=10.1016/s0167-6377(99)00016-4| citeseerx = 10.1.1.424.861 }}

*{{cite journal | last1 = Ben-Tal | first1 = A. | last2 = Arkadi Nemirovski | first2 = A. | year = 2002 | title = Robust optimization—methodology and applications | url = | journal = Mathematical Programming, Series B | volume = 92 | issue = 3| pages = 453–480 | doi=10.1007/s101070100286| citeseerx = 10.1.1.298.7965 | s2cid = 1429482 }}

*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.

*{{cite journal | last1 = Bertsimas | first1 = D. | last2 = Sim | first2 = M. | year = 2003 | title = Robust Discrete Optimization and Network Flows | url = | journal = Mathematical Programming | volume = 98 | issue = 1–3| pages = 49–71 | doi=10.1007/s10107-003-0396-4| citeseerx = 10.1.1.392.4470 | s2cid = 1279073 }}

*{{cite journal | last1 = Bertsimas | first1 = D. | last2 = Sim | first2 = M. | year = 2006 | title = Tractable Approximations to Robust Conic Optimization Problems Dimitris Bertsimas | url = | journal = Mathematical Programming | volume = 107 | issue = 1| pages = 5–36 | doi=10.1007/s10107-005-0677-1| citeseerx = 10.1.1.207.8378 | s2cid = 900938 }}

*{{cite journal | last1 = Chen | first1 = W. | last2 = Sim | first2 = M. | year = 2009 | title = Goal Driven Optimization | url = | journal = Operations Research | volume = 57 | issue = 2| pages = 342–357 | doi=10.1287/opre.1080.0570 | url = http://scholarbank.nus.edu.sg/handle/10635/43946 }}

*{{cite journal | last1 = Chen | first1 = X. | last2 = Sim | first2 = M. | last3 = Sun | first3 = P. | last4 = Zhang | first4 = J. | year = 2008 | title = A Linear-Decision Based Approximation Approach to Stochastic Programming | url = | journal = Operations Research | volume = 56 | issue = 2| pages = 344–357 | doi=10.1287/opre.1070.0457}}

*{{cite journal | last1 = Chen | first1 = X. | last2 = Sim | first2 = M. | last3 = Sun | first3 = P. | year = 2007 | title = A Robust Optimization Perspective on Stochastic Programming | url = | journal = Operations Research | volume = 55 | issue = 6| pages = 1058–1071 | doi=10.1287/opre.1070.0441 | url = http://scholarbank.nus.edu.sg/handle/10635/44052 }}

*{{cite journal | last1 = Dembo | first1 = R | year = 1991 | title = Scenario optimization | url = | journal = Annals of Operations Research | volume = 30 | issue = 1| pages = 63–80 | doi=10.1007/bf02204809| s2cid = 44126126 }}

* Dodson, B., Hammett, P., and Klerx, R. (2014) ''Probabilistic Design for Optimization and Robustness for Engineers'' John Wiley & Sons, Inc. {{ISBN|978-1-118-79619-1}}

*{{cite journal | last1 = Gupta | first1 = S.K. | last2 = Rosenhead | first2 = J. | year = 1968 | title = Robustness in sequential investment decisions | urldoi = 10.1287/mnsc.15.2.B18 | journal = Management Science | volume = 15 | issue = 2| pages = 18–29 }}

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

*{{cite journal | last1 = Mutapcic | first1 = Almir | last2 = Boyd | first2 = Stephen | year = 2009 | title = Cutting-set methods for robust convex optimization with pessimizing oracles | url = | journal = Optimization Methods and Software | volume = 24 | issue = 3| pages = 381–406 | doi=10.1080/10556780802712889| citeseerx = 10.1.1.416.4912 | s2cid = 16443437 }}

*{{cite journal | last1 = Mulvey | first1 = J.M. | last2 = Vanderbei | first2 = R.J. | last3 = Zenios | first3 = S.A. | year = 1995 | title = Robust Optimization of Large-Scale Systems | url = | journal = Operations Research | volume = 43 | issue = 2| pages = 264–281 | doi=10.1287/opre.43.2.264}}

*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]].

*{{cite journal | last1 = Rosenblat | first1 = M.J. | year = 1987 | title = A robust approach to facility design | url = | journal = International Journal of Production Research | volume = 25 | issue = 4| pages = 479–486 }}

*{{cite journal | last1 = RosenheadRosenblat | first1 = M.J | last2 = Elton | first2 = M | last3 = Gupta | first3 = S.K. | year = 19721987 | title = RobustnessA androbust Optimalityapproach asto Criteriafacility for Strategic Decisionsdesign | urljournal = |International journalJournal =of OperationalProduction Research Quarterly | volume = 2325 | issue = 4| pages = 413–430479–486 | doi = 10.23071080/300795700207548708919855 }}

*{{cite journal | last1 = Rosenhead | first1 = M.J | last2 = Elton | first2 = M | last3 = Gupta | first3 = S.K. | year = 1972 | title = Robustness and Optimality as Criteria for Strategic Decisions | journal = Operational Research Quarterly | volume = 23 | issue = 4| pages = 413–430 | doi=10.2307/3007957| jstor = 3007957 }}

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

*{{cite journal | last1 = Sniedovich | first1 = M | year = 2007 | title = The art and science of modeling decision-making under severe uncertainty | url = | journal = Decision Making in Manufacturing and Services | volume = 1 | issue = 1-21–2| pages = 111–136 | doi = 10.7494/dmms.2007.1.2.111 | doi-access = free }}

*{{cite journal | last1 = Sniedovich | first1 = M | year = 2008 | title = Wald's Maximin Model: a Treasure in Disguise! | url = | journal = Journal of Risk Finance | volume = 9 | issue = 3| pages = 287–291 | doi=10.1108/15265940810875603}}

*{{cite journal | last1 = Sniedovich | first1 = M | year = 2010 | title = A bird's view of info-gap decision theory | url = | journal = Journal of Risk Finance | volume = 11 | issue = 3| pages = 268–283 | doi=10.1108/15265941011043648}}

*{{cite journal | last1 = Wald | first1 = A | year = 1939 | title = Contributions to the theory of statistical estimation and testing hypotheses | url = | journal = The Annals of MathematicsMathematical Statistics| volume = 10 | issue = 4| pages = 299–326 | doi=10.1214/aoms/1177732144| doi-access = free }}

*{{cite journal | last1 = Wald | first1 = A | year = 1945 | title = Statistical decision functions which minimize the maximum risk | url = | journal = The Annals of Mathematics | volume = 46 | issue = 2| pages = 265–280 | doi=10.2307/1969022| jstor = 1969022 }}

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

*M.{{cite Shabanzadeh,book M|doi=10. Fattahi1109/IranianCEE. 2015.7146458|isbn=978-1-4799-1972-7|chapter=Generation Maintenance Scheduling via robust optimization.|title=2015 DOI:23rd 10.1109/IranianCEE.2015.7146458Iranian Conference on ,Electrical Engineering|year=2015|last1=Shabanzadeh|first1=Morteza|last2=Fattahi|first2=Mohammad|pages=1504–1509|s2cid=8774918 }}

==External links==

* [httphttps://www.robustopt.com ROME: Robust Optimization Made Easy]

* [http://robust.moshe-online.com: Robust Decision-Making Under Severe Uncertainty]

* [https://robustimizer.com/ Robustimizer: Robust optimization software]

{{Major subfields of optimization}}

[[Category:Mathematical optimization]]