17 Optimization under Uncertainty
Previous chapters assumed that the optimization objective is to minimize a deterministic function of our design points. In many engineering tasks, however, there
may be uncertainty in the objective function or the constraints. Uncertainty may
arise due to a number of factors, such as model approximations, imprecision, andfluctuations of parameters over time. This chapter covers a variety of methods foraccounting for uncertainty in our optimization to enhance robustness.1

17.1 Uncertainty
Uncertainty in the optimization process can arise for a variety of reasons. Theremay be irreducible uncertainty,2 which is inherent to the system, such as background noise, varying material properties, and quantum effects. These uncertainties cannot be avoided and our design should accommodate them. There may
also be epistemic uncertainty,3 which is uncertainty caused by a subjective lack ofknowledge by the designer. This uncertainty can arise from approximations in
the model4 used when formulating the design problem and errors introduced bynumerical solution methods.
Accounting for these various forms of uncertainty is critical to ensuring robust
designs. In this chapter, we will use z ∈ Z to represent a vector of random
values. We want to minimize f (x, z), but we do not have control over z. Feasibility
depends on both the design vector x and the uncertain vector z. This chapter
introduces the feasible set over x and z pairs as F . We have feasibility if and only
if (x, z) ∈ F . We will use X as the design space, which may include potentiallyinfeasible designs depending on the value of z.
Optimization with uncertainty was briefly introduced in section 15.5 in thecontext of using a Gaussian process to represent an objective function inferred

Additional references include:
H.-G. Beyer and B. Sendhoff,“Robust Optimization—A Comprehensive Survey,” Computer
Methods in Applied Mechanics
and Engineering, vol. 196, no. 33,
pp. 3190–3218, 2007. G.-J. Park,
T.-H. Lee, K. H. Lee, and K.-H.
Hwang, “Robust Design: An
Overview,” AIAA Journal, vol. 44,
no. 1, pp. 181–191, 2006.
1

This form of uncertainty is sometimes called aleatory uncertainty or
random uncertainty.

2

Epistemic uncertainty is also
called reducible uncertainty.
3

The statistician George Box famously wrote: All models are wrong;some models are useful. G. E. P. Box,
W. G. Hunter, and J. S. Hunter,
Statistics for Experimenters: An Introduction to Design, Data Analysis, andModel Building, 2nd ed. Wiley, 2005.
p. 440.
4

308 c ha p te r 17. op ti mi z a ti on u n d e r u n c e rta i n ty

from noisy measurements. We had f (x, z) = f (x) + z with the additional assumption that z comes from a zero-mean Gaussian distribution.5 Uncertainty
may be incorporated into the evaluation of a design point in other ways. For
example, if we had noise in the input to the objective function,6 we might havef (x, z) = f (x + z). In general, f (x, z) can be a complex, nonlinear function of x
and z. In addition, z may not come from a Gaussian distribution; in fact, it may
come from a distribution that is not known.
Figure 17.1 demonstrates how the degree of uncertainty can affect our choiceof design. For simplicity, x is a scalar and z is selected from a zero-mean Gaussian
distribution. We assume that z corresponds to noise in the input to f , and sof ( x, z) = f ( x + z). The figure shows the expected value of the objective function
for different levels of noise. The global minimum without noise is a. However,aiming for a design near a can be risky since it lies within a steep valley, making it
rather sensitive to noise. Even with low noise, it may be better to choose a designnear b. Designs near c can provide even greater robustness to larger amounts ofnoise. If the noise is very high, the best design might even fall between b and c,which corresponds to a local maximum in the absence of noise.
There are a variety of different ways to account for uncertainty in optimization.
We will discuss both set-based uncertainty and probabilistic uncertainty.7

Here, the two-argument versionof f takes as input the design point
and random vector, but the singleargument version of f represents
a deterministic function of the design point without noise.
5

For example, there may be variability in the manufacturing of ourdesign.

6

Other approaches for representing uncertainty include DempsterShafer theory, fuzzy-set theory, andpossibility theory, which are beyond
the scope of this book.
7

expected value

Figure 17.1. The global minimum
at a in the noiseless case is sensitive
to noise. Other design points may
be more robust depending on the
anticipated level of noise.

a

b

c
x

noise-freevery low noise

low noisehigh noisevery high noise© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

17. 2. se t-ba se d u n c e rta i n ty 309

17.2 Set-Based Uncertainty
Set-based uncertainty approaches assume that z belongs to a set Z , but theseapproaches make no assumptions about the relative likelihood of different points
within that set. The set Z can be defined in different ways. One way is to defineintervals for each component of Z . Another way is to define Z by a set of inequality
constraints, g(x, z) ≤ 0, similar to what was done for the design space X inchapter 10.

17.2.1Minimax

In problems with set-based uncertainty, we often want to minimize the maximum
possible value of the objective function. Such a minimax approach8 solves the
optimization problem
minimize maximize f (x, z)
x∈X

z∈Z

Also called the robust counterpart
approach or robust regularization.
8(17.1)

In other words, we want to find an x that minimizes f , assuming the worst-casevalue for z.
This optimization is equivalent to defining a modified objective function
f mod (x) = maximize f (x, z)(17.2)

minimize f mod (x)(17.3)z∈Z

and then solvingx∈X

Example 17.1 shows this optimization on a univariate problem and illustrates theeffect of different levels of uncertainty.
In problems where we have feasibility constraints, our optimization problem
becomesminimize maximize f (x, z) subject to (x, z) ∈ F and (x, z′ ) ∈ F for all z′
x∈X

z∈Z

(17.4)

Example 17.2 shows the effect of applying minimax on the space of feasible design
points when there are constraints.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

310 c ha p te r 17. op ti mi z a ti on u n d e r u n c e rta i n ty

Example 17.1. Example of a minimax approach to optimization under set-based uncertainty.

Consider the objective functionf ( x, z) = f ( x + z) = f ( x̃ ) =


− x̃


x̃2

if x̃ ≤ 0otherwise

where x̃ = x + z, with a set-based uncertainty region z ∈ [−ǫ, ǫ]. The minimax approach is a minimization problem over the modified objective function
f mod ( x ) = maximizez∈[−ǫ,ǫ] f ( x, z).
4trueǫ = 0.2
ǫ = 0.4
ǫ = 0.6
ǫ = 0.8
ǫ = 1.0
ǫ = 1.2
ǫ = 1.4
ǫ = 1.6
ǫ = 1.8
ǫ = 2.0

y

3

2

1

0

−1

−0.5

0
x

0.5

1

The figure above shows f mod ( x ) for several different values of ǫ. The
minimum for ǫ = 0 coincides with the minimum of f ( x, 0). As ǫ is increased,
the minimum first shifts right as x increases faster than x2 and then shifts
left as x2 increases faster than x. The robust minimizer does not generally
coincide with the minimum of f ( x, 0).

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

17. 2. se t-ba se d u n c e rta i n ty

Consider an uncertain feasible set in the form of a rotated ellipse, where(x, z) ∈ F if and only if z ∈ [0, π/2] and311

Example 17.2. The minimax approach applied to uncertainty inthe feasible set.

( x1 cos z + x2 sin z)2 + ( x1 sin z − x2 cos z)2 /16 ≤ 1
When z = 0, the major axis of the ellipse is vertical. Increasing values of z
slowly rotates it counter clockwise to horizontal at z = π/2. The figure below
shows the vertical and horizontal ellipses and the set of all points that arefeasible for at least one z in blue.
A minimax approach to optimization should consider only design points
that are feasible under all values of z. The set of designs that are always
feasible are given by the intersection of all ellipses formed by varying z. Thisset is outlined in red.

x2

x1

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

312 c ha p te r 17. op ti mi z a ti on u n d e r u n c e rta i n ty

17.2.2 Information-Gap Decision Theory
Instead of assuming the uncertainty set Z is fixed, an alternative approach known
as information-gap decision theory9 parameterizes the uncertainty set by a nonnegative scalar gap parameter ǫ. The gap controls the volume of the parameterized set
Z (ǫ) centered at some nominal value z̄ = Z (0). One way to define Z (ǫ) is as a
hypersphere of radius ǫ centered at a nominal point z̄:Z (ǫ) = {z | kz − z̄k2 ≤ ǫ}

9F. M. Hemez and Y. Ben-Haim,“Info-Gap Robustness for the Correlation of Tests and Simulations ofa Non-Linear Transient,” Mechanical Systems and Signal Processing,vol. 18, no. 6, pp. 1443–1467, 2004.

(17.5)

Figure 17.2 illustrates this definition in two dimensions.
By parameterizing the uncertainty set, we avoid committing to a particular
uncertainty set. Uncertainty sets that are too large sacrifice the quality of thesolution, and uncertainty sets that are too small sacrifice robustness. Design
points that remain feasible for larger gaps are considered more robust.
In information-gap decision theory, we try to find the design point that allows
for the largest gap while preserving feasibility. This design point can be obtainedby solving the following optimization problem:ǫ if (x, z) ∈ F for all z ∈ Z (ǫ)(17.6)x∗ = arg max maximizeǫ∈[0,∞) 0 otherwisex∈X
This optimization focuses on finding designs that ensure feasibility in thepresence of uncertainty. In fact, equation (17.6) does not explicitly include theobjective function f . However, we can incorporate the constraint that f (x, z) be no
greater than some threshold ymax . Such performance constraints can help us avoid
excessive risk aversion. Figure 17.3 and example 17.3 illustrate the application of
information-gap decision theory.

17.3 Probabilistic Uncertainty
Models of probabilistic uncertainty use distributions over a set Z . Probabilistic
uncertainty models provide more information than set-based uncertainty models,
allowing the designer to account for the probability of different outcomes of adesign. These distributions can be defined using expert knowledge or learned
from data. Given a distribution p over Z , we can infer a distribution over the
output of f using methods that will be discussed in chapter 18. This section will

z2

ǫ

z̄

z1
Figure 17.2. A parametrized uncertainty set Z (ǫ) in the form of a
hypersphere.

x̃2

x∗

F
x̃1
Figure 17.3. Information-gap decision theory applied to an objectivefunction with additive noise f (x̃)
with x̃ = x + z and a circular uncertainty set

Z ( ǫ ) = {z | k z k2 ≤ ǫ }The design x∗ is optimal underinformation-gap decision theory as
it allows for the largest possible ǫsuch that all x∗ + z are feasible.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

17. 3. p roba bi l i sti c u n c e rta i n ty 313

Consider the robust optimization of f ( x, z) = x̃2 + 6e− x̃ with x̃ = x + z
subject to the constraint x̃ ∈ [−2, 2] with the uncertainty set Z (ǫ) = [−ǫ, ǫ].
2

10

y

noise-freeǫ = 0.3
ǫ = 0.6
ǫ = 0.9
ǫ = 1.2
ǫ = 1.5
ǫ = 1.8
ǫ = 2.1
ǫ = 2.4
ǫ = 2.7
ǫ = 3.0

Z

8
6

x∗

4
2
10

Z

y

8
6
4
2
−3

Example 17.3. We can mitigate excessive risk aversion by applying a
constraint on the maximum acceptable objective function value when
applying information-gap decision
theory.

x∗
−2

−1

0
x

1

2

3

Applying information-gap decision theory to this problem results in a
maximally-sized uncertainty set and a design centered in the suboptimal
region of the objective function. Applying an additional constraint on the
maximum objective function value, f ( x, z) ≤ 5, allows the same approach tofind a design with better noise-free performance. The blue lines indicate theworst-case objective function value for a given uncertainty parameter ǫ.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

314 c ha p te r 17. op ti mi z a ti on u n d e r u n c e rta i n ty

outline five different metrics for converting this distribution into a scalar value
given a particular design x. We can then optimize with respect to these metrics.10

17.3.1 Expected Value
One way to convert the distribution output by f into a scalar value is to use theexpected value or mean. The expected value is the average output that we can expect
when considering all outputs of f (x, z) for all z ∈ Z and their corresponding
probabilities. The expected value as a function of the design point x is
Ez∼ p [ f (x, z)] =ZZf (x, z) p(z) dz

Further discussion of various
metrics can be found in A. Shapiro,
D. Dentcheva, and A. Ruszczyński,Lectures on Stochastic Programming:
Modeling and Theory, 2nd ed. SIAM,
2014.
10

(17.7)The expected value does not necessarily correspond to the objective function
without noise, as illustrated in example 17.4.
Computing the integral in equation (17.7) analytically may not be possible.
One may approximate that value using sampling or a variety of other moresophisticated techniques discussed in chapter 18.

17.3.2 Variance
Besides optimizing with respect to the expected value of the function, we may
also be interested in choosing design points whose value is not overly sensitive to
uncertainty.11 Such regions can be quantified using the variance of f :h2 iVar[ f (x, z)] = Ez∼ p f (x, z) − Ez∼ p [ f (x, z)](17.8)=ZZ

f (x, z)2 p(z) dz − Ez∼ p [ f (x, z)]2

(17.9)

Sometimes
designers
seekplateau-like regions where theoutput of the objective function
is relatively constant, such as
producing materials with consistent performance or schedulingtrains such that they arrive at aconsistent time.

11© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

17. 3. p roba bi l i sti c u n c e rta i n ty 315

One common model is to apply zero-mean Gaussian noise to the function output, f (x, z) = f (x) + z, as was the case with Gaussian processes in chapter 16.
The expected value is equivalent to the noise-free case:Example 17.4. The expected valueof an uncertain objective function
depends on how the uncertainty
is incorporated into the objectivefunction.

Ez∼N (0,Σ) [ f (x) + z] = Ez∼N (0,Σ) [ f (x)] + Ez∼N (0,Σ) [z] = f (x)It is also common to add noise directly to the design vector,
f (x, z) = f (x + z) = f (x̃). In such cases the expected value is affected by
the variance of zero-mean Gaussian noise.
Consider minimizing the expected value of f ( x̃ ) = sin(2x̃ )/ x̃ withx̃ = x + z for z drawn from a zero-mean Gaussian distribution N (0, ν). Increasing the variance increases the effect that the local function landscapehas on a design.

y

2

ν=0
ν = 0.5
ν = 1.0
ν = 1.5
ν = 2.0

1
0

−10

−8

−6

−4

−2

0
x

2

4

6

8

10

The plot above shows that changing the variance affects the location of
the optima.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

316 c ha p te r 17. op ti mi z a ti on u n d e r u n c e rta i n ty

sensitivey

We call design points with large variance sensitive and design points withsmall variance robust. Examples of sensitive and robust points are shown infigure 17.4. We are typically interested in good points as measured by their
expected value that are also robust. Managing the trade-off between the expected
objective function value and the variance is a multiobjective optimization problem(see example 17.5), and we can use techniques discussed in chapter 12.

robustx17.3.3 Statistical Feasibility
An alternative metric against which to optimize is statistical feasibility. Given p(z),we can compute the probability a design point x is feasible:
P (x ∈ F ) =Z

Z((x, z) ∈ F ) p(z) dz(17.10)This probability can be estimated through sampling. If we are also interested
in ensuring that the objective value does not exceed a certain threshold, we canincorporate a constraint f (x, z) ≤ ymax as is done with information-gap decision
theory. Unlike the expected value and variance metrics, we want to maximize
this metric.

Figure 17.4.
Probabilistic approaches produce probability distributions over the model output.
Design points can be sensitive or
robust to uncertainty. The blue regions show how the distribution
over a normally distributed design
is affected by the objective function.

17.3.4 Value at Risk
The value at risk (VaR) is the best objective value that can be guaranteed withprobability α. We can write this definition mathematically in terms of the cumulative distribution function, denoted Φ(y), over the random output of the objectivefunction.The probability that the outcome is less than or equal to y is given by
Φ(y). VaR with confidence α is the minimum value of y such that Φ(y) ≥ α. Thisdefinition is equivalent to the α quantile of a probability distribution. An α close to
1 is sensitive to unfavorable outliers, whereas an α close to 0 is overly optimistic
and close to the best possible outcome.

17.3.5 Conditional Value at Risk
The conditional value at risk (CVaR) is related to the value at risk.12 CVaR is the
expected value of the top 1 − α quantile of the probability distribution over the
output. This quantity is illustrated in figure 17.5.

The conditional value at risk
is also known as the mean excess loss, mean shortfall, and tailvalue at risk. R. T. Rockafellar and
S. Uryasev, “Optimization of Conditional Value-at-Risk,” Journal of
Risk, vol. 2, pp. 21–42, 2000.
12© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

17. 3. p roba bi l i sti c u n c e rta i n ty 317

Consider the objective function f ( x, z) = x2 + z, with z drawn from a Gamma
distribution that depends on x. We can construct a function dist(x) that
returns a Gamma distribution from the Distributions.jl package:

Example 17.5. Considering boththe expected value and the variance in optimization under uncertainty.

dist(x) = Gamma(2/(1+abs(x)),2)

This distribution has mean 4/(1 + | x |) and variance 8/(1 + | x |).

y

10

5

0
−3

−2

−1

0
x

1

2

3

expected value±σ

We can find a robust optimizer that minimizes both the expected value
and the variance. Minimizing with respect to the expected value, ignoring
the variance, produces two minima at x ≈ ±0.695. Incorporating a penalty
for the variance shifts these minima away from the origin. The figure below
pshows objective functions of the form α E [y | x ] + (1 − α) Var[y | x ] forα ∈ [0, 1] along with their associated minima.

αµ + (1 − α)σ

10
8
6
4
2

−3

−2

−1

0
x

1

2

3

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

318 c ha p te r 17. op ti mi z a ti on u n d e r u n c e rta i n ty

0.4

p(y)

0.3
0.2

top 1 − α quantile

0.1
0

VaR

expected value

Figure 17.5. CVaR and VaR for aparticular level α. CVaR is the expected value of the top 1 − α quantile, whereas the VaR is the lowest
objective function value over thesame quantile.

CVaR

y

CVaR has some theoretical and computational advantages over VaR. CVaR isless sensitive to estimation errors in the distribution over the objective output.
For example, if the cumulative distribution function is flat in some intervals, thenVaR can jump with small changes in α. In addition, VaR does not account for costs
beyond the α quantile, which is undesirable if there are rare outliers with very
poor objective values.13

17.4 Summary• Uncertainty in the optimization process can arise due to errors in the data, themodels, or the optimization method itself.
• Accounting for these sources of uncertainty is important in ensuring robust
designs.
• Optimization with respect to set-based uncertainty includes the minimax approach that assumes the worst-case and information-gap decision theory thatfinds a design robust to a maximally sized uncertainty set.

For an overview of properties,
see G. C. Pflug, “Some Remarkson the Value-at-Risk and theConditional Value-at-Risk,” inProbabilistic Constrained Optimization: Methodology and Applications,S. P. Uryasev, ed. Springer, 2000,
pp. 272–281. and R. T. Rockafellar
and S. Uryasev, “Conditional
Value-at-Risk for General Loss
Distributions,” Journal of Banking
and Finance, vol. 26, pp. 1443–1471,
2002.
13

• Probabilistic approaches typically minimize the expected value, the variance,risk of infeasibility, value at risk, conditional value at risk, or a combination ofthese.

17.5 Exercises
Exercise 17.1. Suppose we have zero-mean Gaussian noise in the input such thatf ( x, z) = f ( x + z). Consider the three points a, b, and c in the figure below:© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

319

y

17. 5 . e x e rc i se sabg( x ) ≤ 0

c
x

X

y

Which design point is best if we are minimizing the expected value minus thestandard deviation?
Exercise 17.2. Optima, such as the one depicted in figure 17.6, often lie on aconstraint boundary and are thus sensitive to uncertainties that could cause them
to become infeasible. One approach to overcome uncertainty with respect tofeasibility is to make the constraints more stringent, reducing the size of thefeasible region as shown in figure 17.7.

x1

xFigure 17.6. Optima with active
constraints are often sensitive to
uncertainty.

Figure 17.7. Applying more stringent constraints during optimization prevents designs from being
too close to the true feasibility
boundary.

x2

x2

x∗

x1

It is common to rewrite constraints of the form g(x) ≤ gmax to γg(x) ≤ gmax ,where γ > 1 is a factor of safety. Optimizing such that the constraint values stay
below gmax /γ provides an additional safety buffer.
Consider a beam with a square cross section thought to fail when the stresses
exceed σmax = 1. We wish to minimize the cross section f ( x ) = x2 , where x is the
cross section length. The stress in the beam is also a function of the cross section
length g( x ) = x −2 . Plot the probability that the optimized design does not fail as
the factor of safety varies from 1 to 2:• Uncertainty in maximum stress, g( x, z) = x −2 + z• Uncertainty in construction tolerance, g( x, z) = ( x + z)−2
© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com

320 c ha p te r 17. op ti mi z a ti on u n d e r u n c e rta i n ty

• Uncertainty in material properties, g( x, z) = (1 + z) x −2
where z is zero-mean noise with variance 0.01.
Exercise 17.3. The six-sigma method is a special case of statistical feasibility inwhich a production or industrial process is improved until its assumed Gaussian
output violates design requirements only with outliers that exceed six standard
deviations. This requirement is fairly demanding, as is illustrated in figure 17.8.
Figure 17.8. Statistical feasibility
can be met either by shifting theobjective function mean away fromthe feasibility boundary or by reducing the variance of the objectivefunction.

N ( x | µ, σ)

0.4
0.3

feasibility boundary

0.2
0.1
0

−6

−2

−4

0

2

4

6

number of standard deviations from the mean

Consider the optimization problem
minimize x1xsubject to e x1 ≤ x2 + z ≤ 2e x1
with z ∼ N (0, 1). Find the optimal design x ∗ such that ( x, z) is feasible for all|z| ≤ 6.

© 2019 Massachusetts Institute of Technology, shared under a Creative Commons CC-BY-NC-ND license.
2022-05-22 00:25:57-07:00, revision 47fd495, comments to bugs@algorithmsbook.com