Robust Optimization is a relatively new approach to modeling uncertainty in optimization problems. Whereas stochastic programming assumes there is a probabilistic description of the uncertainty, robust optimization works with a deterministic, set-based description of the uncertainty. The robust optimization approach constructs a solution that is feasible for any realization of the uncertainty in a given set.
For a given optimization problem, there can be multiple robust versions depending on the structure of the uncertainty set. When formulating a robust counterpart of an optimization problem, maintaining tractability is an important issue. From Bertsimas, Brown and Caramanis (2011), the robust counterpart of a linear program can be written as:
\[ \begin{array}{ccccc}
\min & c^T x & & & \\
\mbox{s.t.} & A x & \leq & b & \forall a_1 \in \mathcal{U}_1, \cdots, a_m \in \mathcal{U}_m
\end{array}
\]
where \(a_i\) represents the \(i\)th row of the uncertain matrix \(A\) and takes values in the uncertainty set \(\mathcal{U}_i \in \mathbb{R}^n\). Then \[a_i^T x \leq b_i \iff \max_{\{a_i \in \mathcal{U}_i\} } a_i^T x \leq b_i, \forall i.\]
The types of uncertainty sets include ellipsoidal, polyhedral, cardinality constrained, and norm uncertainty.
References
- Ben-Tal, A. and Nemirovski, A. 1999. Robust solutions of uncertain linear programs. Operations Research 25: 1-13.
- Ben-Tal, A., El Ghaoui, L., and Nemirovski, A. 2009. Robust Optimization. Princeton University Press, Princeton, NJ.
- Bertsimas, D., Brown, D. B., and C. Caramanis. 2011. Theory and Applications of Robust Optimization. SIAM Review 53(3): 464-501.
- Bertsimas, D., Pachamanova, D., and Sim, M. 2004. Robust Linear Optimization Under General Norms. Operations Research Letters 32: 510–516.
- Bertsimas, D. and Sim, M. 2003. Robust Discrete Optimization and Network Flows. Mathematical Programming Series B 98: 49-71.
- Bertsimas, D. and Sim, M. 2004. The Price of Robustness. Operations Research 52: 35-53.
- Bertsimas, D. and Sim, M. 2006. Tractable Approximations to Robust Conic Optimization Problems. Mathematical Programming 107: 5–36.
- Bertsimas, D. and Thiele, A. 2006. A Robust Optimization Approach to Supply Chain Management. Operations Research 54: 150-168.
- El Ghaoui, L. and Lebret, H. 1997. Robust Solutions to Least-Square Problems to Uncertain Data Matrices. SIAM Journal on Matrix Analysis and Applications 18: 1035–1064.
- El Ghaoui, L., Oustry, F., and Lebret, H. 1998. Robust Solutions to Uncertain Semidefinite Programs. SIAM Journal on Optimization 9: 33–52.