Robust optimization

In mathematics, robust optimization is an approach in optimization to deal with uncertainty. It is similar to the recourse model of stochastic programming, in that some of the parameters are random variables, except that feasibility for all possible realizations (called scenarios) is replaced by a penalty function in the objective. As such, the approach integrates goal programming with a scenario-based description of problem data. To illustrate, consider the LP:

${\displaystyle \min cx+dy:Ax=b,Bx+Cy=e,x,y\geq 0,}$

where d, B, C and e are random variables with possible realizations ${\displaystyle {(d(s),B(s),C(s),e(s):s\in \{1,...,N\})}}$, where N = the number of scenarios. The robust optimization model for this LP is:

${\displaystyle \min f(x,y(1),...,y(N))+wP(z(1),...,z(N)):Ax=b,x\geq 0,}$

${\displaystyle \ B(s)x+C(s)y(s)+z(s)=e(s),}$ and ${\displaystyle y(s)\geq 0,\,\forall s=1,...,N,}$

where f is a function that measures the cost of the policy, P is a penalty function, and w > 0 (a parameter to trade off the cost of infeasibility). One example of f is the expected value: ${\displaystyle \ f(x,y)=cx+\sum _{s}{d(s)y(s)p(s)}}$, where p(s) = probability of scenario s. In a worst-case model, ${\displaystyle \ f(x,y)=\max _{s}{d(s)y(s)}}$. The penalty function is defined to be zero if (x, y) is feasible (for all scenarios) -- i.e., P(0)=0. In addition, P satisfies a form of monotonicity: worse violations incur greater penalty. This often has the form ${\displaystyle \ P(z)=U(z^{+})+V(-z^{-})}$ -- i.e., the "up" and "down" penalties, where U and V are strictly increasing functions.

The above makes robust optimization similar (at least in the model) to a goal program. Recently, the robust optimization community defines it differently – it optimizes for the worst-case scenario, as in minimax. Let the uncertain MP be given by

${\displaystyle \min f(x;s):x\in X(s),}$

where S is known as the uncertainty set, which is usually a compact convex object as opposed to a small collection of scenarios (like parameter values).

The robust optimization model (according to this more recent definition) is:

${\displaystyle \min _{x}{\max _{s\in S}f(x;s)}\,x\in X(t)\,\forall t\in S,}$

The policy (x) is required to be feasible no matter what parameter value (scenario) occurs; hence, it is required to be in the intersection of all possible X(s). The inner maximization yields the worst possible objective value among all scenarios. There are variations, such as "adjustability" (i.e., recourse).

See also

• Info-gap decision theory
• Minimax
• Minimax regret
• Robust statistics

External links

• ROME: Robust Optimization Made Easy
• AIMMS: Robust Optimization
• Robust Decision-Making Under Severe Uncertainty

Bibliography

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., Nemirovski, A. (1998). Robust Convex Optimization. Mathematics of Operations Research 23, 769-805.

Ben-Tal, A., Nemirovski, A. (1999). Robust solutions to uncertain linear programs. Operations Research Letters 25, 1-13.

Ben-Tal, A. and Arkadi Nemirovski, A. (2002). Robust optimization—methodology and applications, Mathematical Programming, Series B 92, 453-480.

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.

Bertsimas, D. and M. Sim. (2003). Robust Discrete Optimization and Network Flows. Mathematical Programming, 98, 49-71.

Bertsimas, D. and M. Sim. (2004). Price of Robustness. Operations Research, 52(1), 35-53.

Bertsimas, D. and M. Sim. (2006). Tractable Approximations to Robust Conic Optimization Problems Dimitris Bertsimas. Mathematical Programming, 107(1), 5 – 36.

Chen, W. and M. Sim. (2009). Goal Driven Optimization. Operations Research. 57(2), 342-357.

Chen, X., M. Sim, P. Sun and J. Zhang. (2008). A Linear-Decision Based Approximation Approach to Stochastic Programming. Operations Research 56(2), 344-357.

Chen, X., M. Sim and P. Sun (2007). A Robust Optimization Perspective on Stochastic Programming. Operations Research, 55(6), 1058-1071.

Dembo, R. (1991). Scenario optimization, Annals of Operations Research, 30(1), 63-80.

Gupta, S.K. and Rosenhead, J. (1968). Robustness in sequential investment decisions, Management science, 15(2), B-18-29.

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

Mutapcic, Almir and Boyd, Stephen. (2009). Cutting-set methods for robust convex optimization with pessimizing oracles, Optimization Methods and Software, 24(3), 381-406.

Mulvey, J.M., Vanderbei, R.J., Zenios, S.A. (1995). Robust Optimization of Large-Scale Systems Operations Research, 43(2),264-281.

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

Sniedovich, M. (2007). The art and science of modeling decision-making under severe uncertainty, Decision Making in Manufacturing and Services, 1(1-2), 111-136.

Sniedovich, M. (2008). Wald's Maximin Model: a Treasure in Disguise!, Journal of Risk Finance, 9(3), 287-291.

Sniedovich, M. (2010). A bird's view of info-gap decision theory, Journal of Risk Finance, 11(3), 268-283.

Wald, A. (1939). Contributions to the theory of statistical estimation and testing hypotheses, The Annals of Mathematics, 10(4), 299-326.

Wald, A. (1945). Statistical decision functions which minimize the maximum risk, The Annals of Mathematics, 46(2), 265-280.

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