# Robust optimization

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:

$LaTeX: \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:

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

$LaTeX: 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

$LaTeX: \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:

$LaTeX: \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).