Robust Optimization

Decision under uncertainty with imperfect probabilistic description of reality

The field of decision-making under uncertainty was pioneered in the 1950s by Dantzig [6] and Charnes and Cooper [5], who set the foundation for, respectively, stochastic programming and optimization under probabilistic constraints. While these classes of problems require very different models and solution techniques, they share the same assumption that the probability distributions of the random variables are known exactly, and despite Scarf's [10] early observation that we may have reason to suspect that the future demand will come from a distribution that differs from that governing past history in an unpredictable way," the majority of the research efforts in decision-making under uncertainty over the past decades have relied on the precise knowledge of the underlying probabilities. Even under this simplifying assumption, a number of computational issues arises, e.g., the need for multi-variate integration to evaluate chance constraints and the large-scale nature of stochastic programming problems. The reader is referred to Birge and Louveaux [4] and Kall and Mayer [9] for an overview of solution techniques. Today, stochastic programming has established itself as a powerful modeling tool when an accurate probabilistic description of the randomness is available; however, in many real-life applications the decision-maker does not have this information, for instance when it comes to assessing customer demand for a product. (The lack of historical data for new items is an obvious challenge to estimating probabilities, but even well-established product lines can face sudden changes in demand, due to the market entry by a competitor or negative publicity.) Estimation errors have notoriously dire consequences in industries with long production lead times such as automotive, retail and high-tech, where they result in stockpiles of unneeded inventory or, at the other end of the spectrum, lost sales and customers' dissatisfaction. The need for an alternative, non-probabilistic, theory of decision-making under uncertainty has become pressing in recent years because of volatile customer tastes, technological innovation and reduced product life cycles, which reduce the amount of information available and make it obsolete more quickly.

In mathematical terms, imperfect information threatens the relevance of the solution obtained by the computer in two important aspects: (i) the solution might not actually be feasible when the decision-maker attempts to implement it, and (ii) the solution, when feasible, might lead to a far greater cost (or smaller revenue) than the truly optimal strategy. Potential infeasibility, e.g., from errors in estimating the problem parameters, is of course the primary concern of the decision- maker. The field of operations research remained essentially silent on that issue until Soyster's work [11], where every uncertain parameter in convex programming problems was taken equal to its worst-case value within a set. While this achieved the desired effect of immunizing the problem against parameter uncertainty, it was widely deemed too conservative for practical implementation. In the mid-1990s, research teams led by Ben-Tal and Nemirovski ([1], [2], [3]) and El-Ghaoui and Lebret ([7], [8]) addressed the issue of over conservatism by restricting the uncertain parameters to belong to ellipsoidal uncertainty sets, which removes the most unlikely outcomes from consideration and yields tractable mathematical programming problems. In line with these authors' terminology, optimization for the worst-case value of parameters within a set has become known as robust optimization. Prof D. Bertsimas (Sloan School of Management, MIT) in Robust and data-driven optimization: modern decision making under uncertainty, (with A. Thiele), Tutorials on Operations Research, INFORMS, Chapter 4, 195-122, 2006.

In practice the art of robust optimization consists in setting up the most relevant uncertainty sets while enabling the formulation of a convex approximation of the robust counterpart decision problem.


[1] A. Ben-Tal and A. Nemirovski. Robust convex optimization. Mathematics of Operations Research, 23(4):769-805, 1998.
[2] A. Ben-Tal and A. Nemirovski. Robust solutions to uncertain programs. Operations Research Letters, 25:1-13, 1999.
[3] A. Ben-Tal and A. Nemirovski. Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming, 88:411-424, 2000.
[4] J. Birge and F. Louveaux. Introduction to stochastic programming. Springer Verlag, 1997.
[5] A. Charnes and W. Cooper. Chance-constrained programming. Management Science, 6(1):73-79, 1959.
[6] G. Dantzig. Linear programming under uncertainty. Management Science, 1(3-4):197-206, 1955.
[7] L. El-Ghaoui and H. Lebret. Robust solutions to least-square problems to uncertain data matrices. SIAM Journal on Matrix Analysis and Applications, 18:1035-1064, 1997.
[8] L. El-Ghaoui, F. Oustry, and H. Lebret. Robust solutions to uncertain semidefinite programs. SIAM Journal on Optimization, 9:33-52, 1998.
[9] P. Kall and J. Mayer. Stochastic linear programming: Models, theory and computation. Springer Verlag, 2005.
[10] H. Scarf. Studies in the mathematical theory of inventory and production, chapter A min-max solution of an inventory problem, pages 201-209. Stanford University Press, 1958.
[11] A. Soyster. Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21:1154-1157, 1973.