![]() | ||
Robust optimization is a field of 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.
Contents
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, control theory, finance, portfolio management logistics, manufacturing engineering, chemical engineering, medicine, 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
where
What makes this a 'robust optimization' problem is the
If the parameter space
If
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:
where
In words, the robustness (radius of stability) of decision
where the rectangle
Global robustness
Consider the simple abstract robust optimization problem
where
This is a global robust optimization problem in the sense that the robustness constraint
The difficulty is that such a "global" constraint can be too demanding in that there is no
Example 2
Consider the case where the objective is to satisfy a constraint
where
In words, the robustness of decision is the size of the largest subset of
This yields the following robust optimization problem:
This intuitive notion of global robustness is not used often in practice because the robust optimization problems that it induces are usually (not always) very difficult to solve.
Example 3
Consider the robust optimization problem
where
To overcome this difficulty, let
Since
One way to fix this difficulty is to relax the constraint
where
The function
and
and therefore the optimal solution to the relaxed problem satisfies the original constraint
outside
Non-probabilistic robust optimization models
The dominating paradigm in this area of robust optimization is Wald's maximin model, namely
where the
The equivalent mathematical programming (MP) of the classic format above is
Constraints can be incorporated explicitly in these models. The generic constrained classic format is
The equivalent constrained MP format is defined as:
Probabilistic robust optimization models
These models quantify the uncertainty in the "true" value of the parameter of interest by probability distribution functions. They have been traditionally classified as stochastic programming and stochastic optimization models.
Robust counterpart
The solution method to many robust program involves creating a deterministic equivalent, called the robust counterpart. The practical difficulty of a robust program depends on if its robust counterpart is computationally tractable.