Robust optimization
Encyclopedia
Robust optimization is a field of optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....

 theory that deals with optimization problems where robustness is sought against uncertainty
Uncertainty
Uncertainty is a term used in subtly different ways in a number of fields, including physics, philosophy, statistics, economics, finance, insurance, psychology, sociology, engineering, and information science...

 and/or variability in the value of a parameter of the problem.

History

The origins of robust optimization date back to the establishment of modern decision theory
Decision theory
Decision theory in economics, psychology, philosophy, mathematics, and statistics is concerned with identifying the values, uncertainties and other issues relevant in a given decision, its rationality, and the resulting optimal decision...

 in the 1950s and the use of worst case analysis and Wald's maximin model
Wald's maximin model
In decision theory and game theory, Wald's maximin model is a non-probabilistic decision-making model according to which decisions are ranked on the basis of their worst-case outcomes. That is, the best decision is one whose worst outcome is at least as good as the worst outcome of any other...

  as a tool for the treatment of severe uncertainty. It became a field of its own in the 1970s with parallel developments in fields such as operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...

, control theory
Control theory
Control theory is an interdisciplinary branch of engineering and mathematics that deals with the behavior of dynamical systems. The desired output of a system is called the reference...

, statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....

, economics
Economics
Economics is the social science that analyzes the production, distribution, and consumption of goods and services. The term economics comes from the Ancient Greek from + , hence "rules of the house"...

, and more.

Example

Consider the simple linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...

 problem

where is a given subset of .

What makes this a 'robust optimization' problem is the clause in the constraints. Its implication is that for a pair to be admissible, the constraint must be satisfied by the worst pertaining to , namely the pair that maximizes the value of for the given value of .

If the parameter space is finite (consisting of finitely many elements), then this robust optimization problem itself is a linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...

 problem: for each there is a linear constraint .

If 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
Worst Case
Worst Case is the 3rd book in the Michael Bennett series from James Patterson and Michael Ledwidge.-Plot summary:NYPD Detective Mike Bennett and his new partner FBI Special Agent Emily Parker are on the trail of Francis Mooney, a Manhattan trusts and estates lawyer with terminal lung cancer...

 oriented and as such usually deploy Wald's maximin models
Wald's maximin model
In decision theory and game theory, Wald's maximin model is a non-probabilistic decision-making model according to which decisions are ranked on the basis of their worst-case outcomes. That is, the best decision is one whose worst outcome is at least as good as the worst outcome of any other...

.

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
Stability radius
The stability radius of an object at a given nominal point is the radius of the largest ball, centered at the nominal point, all whose elements satisfy pre-determined stability conditions...

 model:


where denotes the nominal value of the parameter, denotes a ball of radius centered at and denotes the set of values of that satisfy given stability/performance conditions associated with decision .

In words, the robustness (radius of stability) of decision is the radius of the largest ball centered at all of whose elements satisfy the stability requirements imposed on . The picture is this:
where the rectangle represents the set of all the values associated with decision .

Global robustness

Consider the simple abstract robust optimization problem


where denotes the set of all possible values of under consideration.

This is a global robust optimization problem in the sense that the robustness constraint represents all the possible values of .

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

Example

Consider the case where the objective is to satisfy a constraint . where denotes the decision variable and is a parameter whose set of possible values in . If there is no such that , then the following intuitive measure of robustness suggests itself:


where denotes an appropriate measure of the "size" of set . For example, if is a finite set, then could be defined as the cardinality of set .

In words, the robustness of decision is the size of the largest subset of for which the constraint is satisfied for each in this set. An optimal decision is then a decision whose robustness is the largest.

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

Consider the robust optimization problem
where is a real-valued function on , and assume that there is no feasible solution to this problem because the robustness constraint is too demanding.

To overcome this difficult, let be a relatively small subset of representing "normal" values of and consider the following robust optimization problem:

Since is much smaller than , its optimal solution may not perform well on a large portion of and therefore may not be robust against the variability of over .

One way to fix this difficulty is to relax the constraint for values of outside the set in a controlled manner so that larger violations are allowed as the distance of from increases. For instance, consider the relaxed robustness constraint


where is a control parameter and denotes the distance of from . Thus, for the relaxed robustness constraint reduces back to the original robustness constraint.

This yields the following (relaxed) robust optimization problem:


The function is defined in such a manner that

and


and therefore the optimal solution to the relaxed problem satisfies the original constraint for all values of in . In addition, it also satisfies the relaxed constraint


outside .

Non-probabilistic robust optimization models

The dominating paradigm in this area of robust optimization is Wald's maximin model
Wald's maximin model
In decision theory and game theory, Wald's maximin model is a non-probabilistic decision-making model according to which decisions are ranked on the basis of their worst-case outcomes. That is, the best decision is one whose worst outcome is at least as good as the worst outcome of any other...

, namely


where the represents the decision maker, the represents Nature, namely uncertainty
Uncertainty
Uncertainty is a term used in subtly different ways in a number of fields, including physics, philosophy, statistics, economics, finance, insurance, psychology, sociology, engineering, and information science...

, represents the decision space and denotes the set of possible values of associated with decision . This is the classic format of the generic model, and is often referred to as minimax or maximin optimization problem. The non-probabilistic (deterministic) model has been and is being extensively used for robust optimization especially in the field of signal processing .

The equivalent mathematical programming
Mathematical Programming
Mathematical Programming, established in 1971, and published by Springer Science+Business Media, is the official scientific journal of the Mathematical Optimization Society. It currently consists of two series: A and B. The "A" series contains general publications. The "B" series focuses on topical...

 (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

In another effort and in one of the non-probabilistic models, Erfani and Utyuzhnikov , use the fuzzy variables in order to quantify the uncertainties within the design parameters. They introduce a Robust measure in context of multiobjective optimization
Multiobjective optimization
Multi-objective optimization , also known as multi-criteria or multi-attribute optimization, is the process of simultaneously optimizing two or more conflicting objectives subject to certain constraints....

 to find the robust Pareto optimal solutions.

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
Stochastic programming
Stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within...

 and stochastic optimization
Stochastic optimization
Stochastic optimization methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involve random objective functions or random constraints, for example. Stochastic...

 models.

See also

  • Stability radius
    Stability radius
    The stability radius of an object at a given nominal point is the radius of the largest ball, centered at the nominal point, all whose elements satisfy pre-determined stability conditions...

  • Minimax
    Minimax
    Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...

  • Minimax estimator
  • Minimax regret
  • Robust statistics
    Robust statistics
    Robust statistics provides an alternative approach to classical statistical methods. The motivation is to produce estimators that are not unduly affected by small departures from model assumptions.- Introduction :...

  • Robust decision making
    Robust decision making
    Robust decision making is an iterative decision analytic framework that helps identify potential robust strategies, characterize the vulnerabilities of such strategies, and evaluate the tradeoffs among them...

  • Stochastic programming
    Stochastic programming
    Stochastic programming is a framework for modeling optimization problems that involve uncertainty. Whereas deterministic optimization problems are formulated with known parameters, real world problems almost invariably include some unknown parameters. When the parameters are known only within...

  • Stochastic optimization
    Stochastic optimization
    Stochastic optimization methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involve random objective functions or random constraints, for example. Stochastic...

  • Info-gap decision theory
    Info-gap decision theory
    Info-gap decision theory is a non-probabilistic decision theory that seeks to optimize robustness to failure – or opportuneness for windfall – under severe uncertainty, in particular applying sensitivity analysis of the stability radius type to perturbations in the value of a given estimate of the...


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK