Robust optimization is a field of
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
theory that deals with optimization problems in which a certain measure of robustness is sought against
uncertainty
Uncertainty refers to epistemic situations involving imperfect or unknown information. It applies to predictions of future events, to physical measurements that are already made, or to the unknown. Uncertainty arises in partially observable or ...
that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution.
History
The origins of robust optimization date back to the establishment of modern
decision theory
Decision theory (or the theory of choice; not to be confused with choice theory) is a branch of applied probability theory concerned with the theory of making decisions based on assigning probabilities to various factors and assigning numerical ...
in the 1950s and the use of worst case analysis and
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 – the optimal decision is one with the least bad worst outco ...
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
Statistics (from German language, German: ''wikt:Statistik#German, Statistik'', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of ...
, but also in
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
,
electrical engineering
Electrical engineering is an engineering discipline concerned with the study, design, and application of equipment, devices, and systems which use electricity, electronics, and electromagnetism. It emerged as an identifiable occupation in the l ...
,
control theory
Control theory is a field of mathematics that deals with the control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive the system to a ...
,
finance
Finance is the study and discipline of money, currency and capital assets. It is related to, but not synonymous with economics, the study of production, distribution, and consumption of money, assets, goods and services (the discipline of fina ...
,
portfolio management logistics
Logistics is generally the detailed organization and implementation of a complex operation. In a general business sense, logistics manages the flow of goods between the point of origin and the point of consumption to meet the requirements of ...
,
manufacturing engineering
Manufacturing engineering or production engineering is a branch of professional engineering that shares many common concepts and ideas with other fields of engineering such as mechanical, chemical, electrical, and industrial engineering.
Manufa ...
,
chemical engineering
Chemical engineering is an engineering field which deals with the study of operation and design of chemical plants as well as methods of improving production. Chemical engineers develop economical commercial processes to convert raw materials int ...
,
medicine
Medicine is the science and practice of caring for a patient, managing the diagnosis, prognosis, prevention, treatment, palliation of their injury or disease, and promoting their health. Medicine encompasses a variety of health care pract ...
, and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
. In
engineering
Engineering is the use of scientific method, scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad rang ...
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
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
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 (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
problem: for each
there is a linear constraint
.
If
is not a finite set, then this problem is a linear
semi-infinite programming In optimization theory, semi-infinite programming (SIP) is an optimization problem with a finite number of variables and an infinite number of constraints, or an infinite number of variables and a finite number of constraints. In the former case the ...
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
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
oriented and as such usually deploy
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 – the optimal decision is one with the least bad worst outco ...
s.
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
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 2
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
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
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 3
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 difficulty, 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
. 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
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 – the optimal decision is one with the least bad worst outco ...
, namely
:
where the
represents the decision maker, the
represents Nature, namely
uncertainty
Uncertainty refers to epistemic situations involving imperfect or unknown information. It applies to predictions of future events, to physical measurements that are already made, or to the unknown. Uncertainty arises in partially observable or ...
,
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 optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
(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:
:
Probabilistically 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
In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, ...
and
stochastic optimization
Stochastic optimization (SO) 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 involves random objective funct ...
models. Recently, probabilistically robust optimization has gained popularity by the introduction of rigorous theories such as
scenario optimization
The scenario approach or scenario optimization approach is a technique for obtaining solutions to robust optimization and chance-constrained optimization problems based on a sample of the constraints. It also relates to inductive reasoning in mod ...
able to quantify the robustness level of solutions obtained by randomization. These methods are also relevant to data-driven optimization methods.
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.
[ Leyffer S., Menickelly M., Munson T., Vanaret C. and Wild S. M (2020). A survey of nonlinear robust optimization. ''INFOR: Information Systems and Operational Research,'' Taylor \& Francis.]
See also
*
Stability radius
In mathematics, the stability radius of an object (system, function, matrix, parameter) at a given nominal point is the radius of the largest ball, centered at the nominal point, all of whose elements satisfy pre-determined stability conditions ...
*
Minimax
Minimax (sometimes MinMax, MM or saddle point) is a decision rule used in artificial intelligence, decision theory, game theory, statistics, and philosophy for ''mini''mizing the possible loss for a worst case (''max''imum loss) scenario. When de ...
*
Minimax estimator
In statistical decision theory, where we are faced with the problem of estimating a deterministic parameter (vector) \theta \in \Theta from observations x \in \mathcal, an estimator (estimation rule) \delta^M \,\! is called minimax if its maximal ...
*
Minimax regret
In decision theory, on making decisions under uncertainty—should information about the best course of action arrive ''after'' taking a fixed decision—the human emotional response of regret is often experienced, and can be measured as the value ...
*
Robust statistics
Robust statistics are statistics with good performance for data drawn from a wide range of probability distributions, especially for distributions that are not normal. Robust statistical methods have been developed for many common problems, suc ...
*
Robust decision making
Robust decision-making (RDM) is an iterative decision analytics framework that aims to help identify potential robust strategies, characterize the vulnerabilities of such strategies, and evaluate the tradeoffs among them. RDM focuses on informing ...
*
Stochastic programming
In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, ...
*
Stochastic optimization
Stochastic optimization (SO) 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 involves random objective funct ...
*
Info-gap decision theory
Info-gap decision theory seeks to optimize robustness to failure under severe uncertainty,Yakov Ben-Haim, ''Information-Gap Theory: Decisions Under Severe Uncertainty,'' Academic Press, London, 2001.Yakov Ben-Haim, ''Info-Gap Theory: Decisions Unde ...
*
Taguchi methods
Taguchi methods ( ja, タグチメソッド) are statistical methods, sometimes called robust design methods, developed by Genichi Taguchi to improve the quality of manufactured goods, and more recently also applied to engineering, biotechnology, ...
References
Further reading
*H.J. Greenberg. Mathematical Programming Glossary. World Wide Web, http://glossary.computing.society.informs.org/, 1996-2006. Edited by the INFORMS Computing Society.
*
*
*
*Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2006). ''Mathematical Programming, Special issue on Robust Optimization,'' Volume 107(1-2).
*Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2009). Robust Optimization. ''Princeton Series in Applied Mathematics,'' Princeton University Press.
*
*
*
*
*
*
* Dodson, B., Hammett, P., and Klerx, R. (2014) ''Probabilistic Design for Optimization and Robustness for Engineers'' John Wiley & Sons, Inc.
*
*Kouvelis P. and Yu G. (1997). ''Robust Discrete Optimization and Its Applications,'' Kluwer.
*
*
*Nejadseyfi, O., Geijselaers H.J.M, van den Boogaard A.H. (2018). "Robust optimization based on analytical evaluation of uncertainty propagation". ''Engineering Optimization'' 51 (9): 1581-1603. do
10.1080/0305215X.2018.1536752
*
*
*Rustem B. and Howe M. (2002). ''Algorithms for Worst-case Design and Applications to Risk Management,'' Princeton University Press.
*
*
*
*
*
*Wald, A. (1950). ''Statistical Decision Functions,'' John Wiley, NY.
*{{cite book , doi=10.1109/IranianCEE.2015.7146458, isbn=978-1-4799-1972-7, chapter=Generation Maintenance Scheduling via robust optimization, title=2015 23rd Iranian Conference on Electrical Engineering, year=2015, last1=Shabanzadeh, first1=Morteza, last2=Fattahi, first2=Mohammad, pages=1504–1509, s2cid=8774918
External links
ROME: Robust Optimization Made EasyRobust Decision-Making Under Severe UncertaintyRobustimizer: Robust optimization software
Mathematical optimization