Robust optimization

From Glossary

Jump to: navigation, search

A term given to an approach to deal with uncertainty, similar to the recourse model of stochastic programming, 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:

\min cx + dy: Ax=b, Bx + Cy = e, x, \ge 0,

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

\min f(x, y(1), \dots, y(N)) + wP(z(1), \dots, z(N)): Ax=b, x \ge 0,

B(s)x + C(s)y(s) + z(s) = e(s), \mbox{ and } y(s) \ge 0, \mbox{ for all } s = 1, \dots, N,

where f is a function that measures the cost of the policy, LaTeX: P is a penalty function, and LaTeX: w > 0 (a parameter to trade off the cost of infeasibility). One example of LaTeX: f is the expected value: LaTeX: \textstyle f(x, y) = cx + \sum_{s} d(s) y(s) p(s), where LaTeX: p(s) = probability of scenario s. In a worst-case model, LaTeX: \textstyle f(x,y) = \max_{s} d(s) y(s). The penalty function is defined to be zero if LaTeX: (x, y) is feasible (for all scenarios) -- i.e., LaTeX: P(0)=0. In addition, LaTeX: P satisfies a form of monotonicity: worse violations incur greater penalty. This often has the form LaTeX: \textstyle P(z) = U(z^+) + V(-z^-) -- i.e., the "up" and "down" penalties, where LaTeX: U and LaTeX: 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. Let the uncertain MP be given by

\min f(x; s): x \in X(s),

where LaTeX: S is some set of scenarios (like parameter values). The robust optimization model (according to this more recent definition) is:

\min_x \left \{\max_{s \in S} f(x; s) \right \} x \in X(t) \mbox{ for all } t \in S,

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

Personal tools