Robust optimization explained

Robust optimization is a field of mathematical 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. It is related to, but often distinguished from, probabilistic optimization methods such as chance-constrained optimization.[1] [2]

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,[3] electrical engineering,[4] [5] [6] control theory,[7] finance,[8] portfolio management[9] logistics,[10] manufacturing engineering,[11] chemical engineering,[12] medicine,[13] 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

maxx,y \{3x+2y\}  subject to  x,y\ge0;cx+dy\le10,\forall(c,d)\inP

where

P

is a given subset of

R2

.

What makes this a 'robust optimization' problem is the

\forall(c,d)\inP

clause in the constraints. Its implication is that for a pair

(x,y)

to be admissible, the constraint

cx+dy\le10

must be satisfied by the worst

(c,d)\inP

pertaining to

(x,y)

, namely the pair

(c,d)\inP

that maximizes the value of

cx+dy

for the given value of

(x,y)

.

If the parameter space

P

is finite (consisting of finitely many elements), then this robust optimization problem itself is a linear programming problem: for each

(c,d)\inP

there is a linear constraint

cx+dy\le10

.

If

P

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 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:

\hat{\rho}(x,\hat{u}):=max\rho\ge \{\rho:u\inS(x),\forallu\inB(\rho,\hat{u})\}

where

\hat{u}

denotes the nominal value of the parameter,

B(\rho,\hat{u})

denotes a ball of radius

\rho

centered at

\hat{u}

and

S(x)

denotes the set of values of

u

that satisfy given stability/performance conditions associated with decision

x

.

In words, the robustness (radius of stability) of decision

x

is the radius of the largest ball centered at

\hat{u}

all of whose elements satisfy the stability requirements imposed on

x

. The picture is this:

where the rectangle

U(x)

represents the set of all the values

u

associated with decision

x

.

Global robustness

Consider the simple abstract robust optimization problem

maxx\in \{f(x):g(x,u)\leb,\forallu\inU\}

where

U

denotes the set of all possible values of

u

under consideration.

This is a global robust optimization problem in the sense that the robustness constraint

g(x,u)\leb,\forallu\inU

represents all the possible values of

u

.

The difficulty is that such a "global" constraint can be too demanding in that there is no

x\inX

that satisfies this constraint. But even if such an

x\inX

exists, the constraint can be too "conservative" in that it yields a solution

x\inX

that generates a very small payoff

f(x)

that is not representative of the performance of other decisions in

X

. For instance, there could be an

x'\inX

that only slightly violates the robustness constraint but yields a very large payoff

f(x')

. 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

g(x,u)\leb,

. where

x\inX

denotes the decision variable and

u

is a parameter whose set of possible values in

U

. If there is no

x\inX

such that

g(x,u)\leb,\forallu\inU

, then the following intuitive measure of robustness suggests itself:

\rho(x):=maxY\subseteq \{size(Y):g(x,u)\leb,\forallu\inY\} , x\inX

where

size(Y)

denotes an appropriate measure of the "size" of set

Y

. For example, if

U

is a finite set, then

size(Y)

could be defined as the cardinality of set

Y

.

In words, the robustness of decision is the size of the largest subset of

U

for which the constraint

g(x,u)\leb

is satisfied for each

u

in this set. An optimal decision is then a decision whose robustness is the largest.

This yields the following robust optimization problem:

maxx\in \{size(Y):g(x,u)\leb,\forallu\inY\}

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

z(U):=maxx\in \{f(x):g(x,u)\leb,\forallu\inU\}

where

g

is a real-valued function on

X x U

, and assume that there is no feasible solution to this problem because the robustness constraint

g(x,u)\leb,\forallu\inU

is too demanding.

To overcome this difficulty, let

l{N}

be a relatively small subset of

U

representing "normal" values of

u

and consider the following robust optimization problem:

z(l{N}):=maxx\in \{f(x):g(x,u)\leb,\forallu\inl{N}\}

Since

l{N}

is much smaller than

U

, its optimal solution may not perform well on a large portion of

U

and therefore may not be robust against the variability of

u

over

U

.

One way to fix this difficulty is to relax the constraint

g(x,u)\leb

for values of

u

outside the set

l{N}

in a controlled manner so that larger violations are allowed as the distance of

u

from

l{N}

increases. For instance, consider the relaxed robustness constraint

g(x,u)\leb+\beta ⋅ dist(u,l{N}) , \forallu\inU

where

\beta\ge0

is a control parameter and

dist(u,l{N})

denotes the distance of

u

from

l{N}

. Thus, for

\beta=0

the relaxed robustness constraint reduces back to the original robustness constraint.This yields the following (relaxed) robust optimization problem:

z(l{N},U):=maxx\in \{f(x):g(x,u)\leb+\beta ⋅ dist(u,l{N}) , \forallu\inU\}

The function

dist

is defined in such a manner that

dist(u,l{N})\ge0,\forallu\inU

and

dist(u,l{N})=0,\forallu\inl{N}

and therefore the optimal solution to the relaxed problem satisfies the original constraint

g(x,u)\leb

for all values of

u

in

l{N}

. It also satisfies the relaxed constraint

g(x,u)\leb+\beta ⋅ dist(u,l{N})

outside

l{N}

.

Non-probabilistic robust optimization models

The dominating paradigm in this area of robust optimization is Wald's maximin model, namely

maxx\inminu\inf(x,u)

where the

max

represents the decision maker, the

min

represents Nature, namely uncertainty,

X

represents the decision space and

U(x)

denotes the set of possible values of

u

associated with decision

x

. 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.[14] [15] [16]

The equivalent mathematical programming (MP) of the classic format above is

maxx\in \{v:v\lef(x,u),\forallu\inU(x)\}

Constraints can be incorporated explicitly in these models. The generic constrained classic format is

maxx\inminu\in \{f(x,u):g(x,u)\leb,\forallu\inU(x)\}

The equivalent constrained MP format is defined as:

maxx\in \{v:v\lef(x,u),g(x,u)\leb,\forallu\inU(x)\}

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 and stochastic optimization models. Recently, probabilistically robust optimization has gained popularity by the introduction of rigorous theories such as scenario optimization 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.[17] [18]

See also

Further reading

External links

Notes and References

  1. https://www.mdpi.com/1996-1073/15/3/825
  2. https://people.eecs.berkeley.edu/~elghaoui/Teaching/EE227A/lecture24.pdf
  3. Bertsimas. Dimitris. Sim, Melvyn . The Price of Robustness. Operations Research. 2004. 52. 1. 35–53. 10.1287/opre.1030.0065. 2268/253225 . 8946639 . free.
  4. Giraldo . Juan S. . Castrillon . Jhon A. . Lopez . Juan Camilo . Rider . Marcos J. . Castro . Carlos A. . July 2019 . Microgrids Energy Management Using Robust Convex Programming . IEEE Transactions on Smart Grid . 10 . 4 . 4520–4530 . 10.1109/TSG.2018.2863049 . 115674048 . 1949-3053.
  5. The design of a risk-hedging tool for virtual power plants via robust optimization approach . Applied Energy . October 2015 . 10.1016/j.apenergy.2015.06.059 . Shabanzadeh M . 155 . 766–777 . Sheikh-El-Eslami . M-K . Haghifam . P. M-R.
  6. Book: 1504–1509 . July 2015 . 10.1109/IranianCEE.2015.7146458 . Shabanzadeh M . Fattahi . M . 2015 23rd Iranian Conference on Electrical Engineering . Generation Maintenance Scheduling via robust optimization . 978-1-4799-1972-7 . 8774918 .
  7. Khargonekar. P.P.. Petersen, I.R. . Zhou, K. . Robust stabilization of uncertain linear systems: quadratic stabilizability and H/sup infinity / control theory. IEEE Transactions on Automatic Control. 35. 3. 356–361. 10.1109/9.50357. 1990.
  8. https://books.google.com/books?id=p6UHHfkQ9Y8C&dq=economics%20robust%20optimization&pg=PR11 Robust portfolio optimization
  9. Md. Asadujjaman and Kais Zaman, "Robust Portfolio Optimization under Data Uncertainty" 15th National Statistical Conference, December 2014, Dhaka, Bangladesh.
  10. Yu. Chian-Son. Li, Han-Lin . A robust optimization model for stochastic logistic problems. International Journal of Production Economics. 64. 1–3. 385–397. 10.1016/S0925-5273(99)00074-2. 2000.
  11. Strano. M. Optimization under uncertainty of sheet-metal-forming processes by the finite element method. Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture. 220. 8. 1305–1315. 10.1243/09544054JEM480. 2006. 108843522.
  12. Bernardo. Fernando P.. Saraiva, Pedro M. . Robust optimization framework for process parameter and tolerance design. AIChE Journal. 1998. 44. 9. 2007–2017. 10.1002/aic.690440908. 10316/8195. free.
  13. Chu. Millie. Zinchenko, Yuriy . Henderson, Shane G . Sharpe, Michael B . Robust optimization for intensity modulated radiation therapy treatment planning under uncertainty. Physics in Medicine and Biology. 2005. 50. 23. 5463–5477. 10.1088/0031-9155/50/23/003. 16306645. 2005PMB....50.5463C . 15713904 .
  14. Verdu . S. . Poor . H. V. . 1984 . On Minimax Robustness: A general approach and applications . IEEE Transactions on Information Theory . 30 . 2. 328–340 . 10.1109/tit.1984.1056876. 10.1.1.132.837 .
  15. Kassam . S. A. . Poor . H. V. . 1985 . Robust Techniques for Signal Processing: A Survey . Proceedings of the IEEE . 73 . 3. 433–481 . 10.1109/proc.1985.13167. 2142/74118 . 30443041 . free .
  16. M. Danish Nisar. "Minimax Robustness in Signal Processing for Communications", Shaker Verlag,, August 2011.
  17. Ben-Tal A., El Ghaoui, L. and Nemirovski, A. (2009). Robust Optimization. Princeton Series in Applied Mathematics, Princeton University Press, 9-16.
  18. [Sven Leyffer|Leyffer S.]

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Robust optimization".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.