Robust optimization

Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution. It is related to, but often distinguished from, probabilistic optimization methods such as chance-constrained optimization.

History

The origins of robust optimization date back to the establishment of modern decision theory in the 1950s and the use of worst case analysis and Wald's maximin model as a tool for the treatment of severe uncertainty. It became a discipline of its own in the 1970s with parallel developments in several scientific and technological fields. Over the years, it has been applied in statistics, but also in operations research,^[1] electrical engineering,^[2]^[3]^[4] control theory,^[5] finance,^[6] portfolio management^[7] logistics,^[8] manufacturing engineering,^[9] chemical engineering,^[10] medicine,^[11] and computer science. In engineering problems, these formulations often take the name of "Robust Design Optimization", RDO or "Reliability Based Design Optimization", RBDO.

Example 1

Consider the following linear programming problem

\max _{x,y}\ \{3x+2y\}\ \ \mathrm {subject\ to} \ \ x,y\geq 0;cx+dy\leq 10,\forall (c,d)\in P

where $P$ is a given subset of $\mathbb {R} ^{2}$ .

What makes this a 'robust optimization' problem is the $\forall (c,d)\in P$ clause in the constraints. Its implication is that for a pair $(x,y)$ to be admissible, the constraint $cx+dy\leq 10$ must be satisfied by the worst $(c,d)\in P$ pertaining to $(x,y)$ , namely the pair $(c,d)\in P$ that maximizes the value of $cx+dy$ for the given value of $(x,y)$ .

If the parameter space $P$ is finite (consisting of finitely many elements), then this robust optimization problem itself is a linear programming problem: for each $(c,d)\in P$ there is a linear constraint $cx+dy\leq 10$ .

If $P$ is not a finite set, then this problem is a linear semi-infinite programming problem, namely a linear programming problem with finitely many (2) decision variables and infinitely many constraints.

Classification

There are a number of classification criteria for robust optimization problems/models. In particular, one can distinguish between problems dealing with local and global models of robustness; and between probabilistic and non-probabilistic models of robustness. Modern robust optimization deals primarily with non-probabilistic models of robustness that are worst case oriented and as such usually deploy Wald's maximin models.

Local robustness

There are cases where robustness is sought against small perturbations in a nominal value of a parameter. A very popular model of local robustness is the radius of stability model:

{\hat {\rho }}(x,{\hat {u}}):=\max _{\rho \geq 0}\ \{\rho :u\in S(x),\forall u\in B(\rho ,{\hat {u}})\}

where ${\hat {u}}$ denotes the nominal value of the parameter, $B(\rho ,{\hat {u}})$ denotes a ball of radius $\rho$ centered at ${\hat {u}}$ and $S(x)$ denotes the set of values of $u$ that satisfy given stability/performance conditions associated with decision $x$ .

In words, the robustness (radius of stability) of decision $x$ is the radius of the largest ball centered at ${\hat {u}}$ all of whose elements satisfy the stability requirements imposed on $x$ . The picture is this:

where the rectangle $U(x)$ represents the set of all the values $u$ associated with decision $x$ .

Global robustness

Consider the simple abstract robust optimization problem

\max _{x\in X}\ \{f(x):g(x,u)\leq b,\forall u\in U\}

where $U$ denotes the set of all possible values of $u$ under consideration.

This is a global robust optimization problem in the sense that the robustness constraint $g(x,u)\leq b,\forall u\in U$ represents all the possible values of $u$ .

The difficulty is that such a "global" constraint can be too demanding in that there is no $x\in X$ that satisfies this constraint. But even if such an $x\in X$ exists, the constraint can be too "conservative" in that it yields a solution $x\in X$ that generates a very small payoff $f(x)$ that is not representative of the performance of other decisions in $X$ . For instance, there could be an $x'\in X$ that only slightly violates the robustness constraint but yields a very large payoff $f(x')$ . In such cases it might be necessary to relax a bit the robustness constraint and/or modify the statement of the problem.