Robust optimization

from Wikipedia, the free encyclopedia

Robust optimization is an area of optimization in mathematics . It is about optimization problems in which stability against uncertainty and / or variability in the values ​​of the problem parameters is sought.

history

The origins of robust optimization go back to the founding of modern decision theory in the 1950s. In this worst-case analyzes designed to deal with high uncertainty to. Robust optimization became a separate research area in the 1970s with various developments in areas such as operations research , control theory , statistics , economics and others

example

Let the simple linear optimization problem be given

with as a subset of .

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

In the event that the parameter space is finite and therefore only consists of a finite number of elements, this robust optimization problem is itself a linear optimization problem: for every pair there is a linear constraint .

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

Classification

There are a number of classification criteria for problems or models of robust optimization. So is z. For example, it is possible to differentiate between problems with local or global robustness models, or between stochastic and non- stochastic robustness models. Modern methods of robust optimization are primarily based on 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 for this is the model of the stability radius :

with as the nominal value of the parameter, as a sphere with a radius that is centered on the point , and as the set of values ​​of which meet the stability or efficiency properties given for the decision .

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

Global robustness

The robust optimization problem is given

where denotes the set of all possible values ​​of that come into question.

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

The difficulty with such a global constraint is that a situation can arise in which there is no such constraint to be met. Even if one exists, the constraint itself can be too conservative . It can mean that the solution only leads to a small objective function value , which, however, is not representative of other solutions . For example, it could be that the robust constraint violates only very slightly, but achieves a much larger objective function value . In these cases it may be necessary to relax the robust constraint and / or to change the formulation of the problem.

example

Suppose the goal is to meet the constraint , where denotes the decision variable and a parameter with the possible values . If there is not such a thing as , then the following measure of robustness is plausible:

being an appropriate measure of the "size" of the crowd . For example, if a finite set, then as the cardinality of the set are considered.

The robustness of the decision is thus the size of the largest subset of , for which the secondary condition is fulfilled for each in this set. The optimal decision is therefore the one with the greatest robustness value.

This creates the following robust optimization problem:

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

literature

  • Armin Scholl : Robust planning and optimization. Basics, concepts and methods, experimental investigations. Physica-Verlag, Heidelberg 2001, ISBN 3-7908-1408-3 (plus dissertation, TU Darmstadt).