Robust optimization

Robust optimization is an area of ​​optimization in mathematics. This involves optimization problems, in which, after stability to uncertainty and / or variability in the values ​​of the problem parameters is sought.

History

The origins of the Robust optimization goes back to the founding of modern decision theory in the 1950s. This worst-case analyzes were developed to deal with high uncertainties. Robust Optimization has been in the 70s to its own area of ​​research with various developments in areas such as operations research, control theory, statistics, economics, inter alia,

Example

Consider the simple linear optimization problem

With a subset of.

The condition in the constraints makes this problem to a ' robust ' problem. It means that for every couple must apply the constraints for the ' worst ' case of, ie also for the pair that maximizes the value of for given.

For the case that the parameter space is finite and thus there is only a finite number of elements, this robust optimization problem is itself a linear optimization problem: For each pair there is a linear constraint.

In the event that it is not a finite set, this problem is a linear semi-infinite optimization problem is a linear optimization problem with a finite number (two) decision variables and an infinite number of constraints.

Classification

There are a number of criteria for classification problems and models of Robust Optimization. For example, a distinction between problems with local or global robustness models possible, or even between stochastic and non-stochastic robustness models. Modern methods of Robust optimization are designed primarily to non-stochastic robustness models that are based on the worst ( worst-case ) case.

Local robustness

Models with local robustness try to protect the nominal value of a parameter against small disturbances. A model of the model of the stability of radius:

With the nominal value of the parameter as a sphere with a radius centered at the point, and when the set of values ​​of which satisfy the given for deciding the stability and efficiency characteristics.

The robustness (or the stability of radius) of the decision so that the radius of the largest sphere which is centered at the point of meeting the criteria of the stability of all elements.

Global robustness

Given the robust optimization problem

Wherein the set of all possible values ​​of referred to come into question.

This is a global optimization problem in robust against that the robust constraint considers all possible values ​​of.

The difficulty with such a global constraint is that a situation may arise in which it is not, that this constraint satisfied. Even if such a exists, the constraint itself may be too conservative. It can lead to the solution leads only to a small objective function value, which are not available representative of other solutions. There could be, for example, one that the robust constraint only slightly injured, but reaches a much larger objective function value. In these cases it may be necessary to soften the robust Nebenbedinungung something and / or to change the formulation of the problem.

Example

Assume that the goal is to meet the constraint, wherein the decision variable, and a parameter referred to with the possible values ​​. Is there no so, then the following measure of robustness is plausible:

Which should constitute an appropriate measure of the "size" of the crowd. For example, a finite set, then as the cardinality of the set to be considered.

The robustness of the decision, so that the size of the largest sub-set of, for which the constraint is met for each in this quantity. The optimal decision is thus the one with the greatest robustness value.

This produces the following robust optimization problem:

The importance of global robustness described is not often used in practice, because the resulting robust optimization problems usually (but not always ) are very difficult to solve.

Bibliography

• Armin Scholl: Robust Planning and Optimization: Fundamentals - Concepts and methods - experimental studies. Heidelberg 2001, ISBN 3790814083

• Optimization