Kochenderfer & Wheeler, Chapter 20

Optimization under Uncertainty

The world is noisy. Design solutions that work well not just at the ideal operating point, but across the range of real-world variability.

Prerequisites: Chapter 18 (Probabilistic Surrogates), Chapter 10 (Constraints).

Chapters

Simulations

Quizzes

Chapter 0: Why Uncertainty Matters

You design a wing that is optimal at exactly 200 km/h, 15°C, and zero turbulence. In the real world, speed varies, temperature fluctuates, and gusts hit. If your design is brittle — amazing at the exact design point but terrible under perturbations — it is a bad design.

The core idea: Robust optimization designs for uncertainty. Instead of minimizing f(x) at a single point, we minimize f(x, z) where z represents uncertain parameters we cannot control. The optimum may shift from a deep but narrow valley to a shallower but wider basin — because the wide basin stays good under perturbation.

Uncertainty arises from many sources: manufacturing tolerances, sensor noise, model approximations, environmental variability. A good design accommodates these uncertainties rather than ignoring them.

Robust optimization prefers a design that:

Performs well across a range of uncertain conditions, not just at one point Achieves the absolute minimum at one specific condition Ignores noise

Chapter 1: Types of Uncertainty

Type	Also Called	Source	Can It Be Reduced?
Aleatory	Irreducible / random	Inherent variability (noise, quantum effects)	No — must be accommodated
Epistemic	Reducible / model	Lack of knowledge (model approximations, limited data)	Yes — with more data or better models

We model uncertainty with a random vector z ∈ Z. The design x is under our control; z is not. The objective becomes f(x, z), and we want to find x that works well across the distribution (or set) of possible z values.

Key insight: The type of uncertainty determines the approach. For aleatory uncertainty (known distribution), use expected-value optimization. For epistemic uncertainty (unknown distribution, only bounds known), use minimax (worst-case) optimization.

Aleatory uncertainty differs from epistemic in that it:

Cannot be reduced by gathering more data — it is inherent Can always be eliminated with better models Only affects the constraints

Chapter 2: Minimax (Worst-Case)

The minimax approach assumes the worst case: minimize the maximum possible objective value over all z ∈ Z:

minimize_x maximize_z∈Z f(x, z)

This is conservative but provides guarantees: the design will perform at least as well as the minimax value, regardless of which z occurs.

The tradeoff: Minimax protection comes at a cost. The robust minimizer is often worse than the nominal minimizer at the exact design point. The wider the uncertainty set Z, the more conservative the solution. The design in a wide valley beats the design in a narrow valley because it is less sensitive to perturbations.

If there are feasibility constraints, minimax requires that the design be feasible for all z ∈ Z, not just one. This shrinks the feasible set to the intersection of all scenario-specific feasible sets.

Minimax optimization protects against the worst case by:

Minimizing the maximum possible objective over all z in the uncertainty set Averaging over all possible z Ignoring unlikely scenarios

Chapter 3: Set-Based Methods

Set-based methods assume z lies in a set Z but make no assumptions about its probability distribution. Beyond minimax, other set-based approaches include:

Regret-based: Minimize the maximum regret, where regret is the gap between your objective value and the best achievable for each z: minimize_x max_z[f(x,z) − f*(z)].

Constraint tightening: Shrink the feasible set to ensure feasibility under all z. If g(x,z) ≤ 0 must hold for all z ∈ Z, tighten to g(x, z̄) + Δ ≤ 0 where Δ accounts for the worst-case perturbation.

Think of it this way: Set-based methods are like building a house to withstand any storm up to category 5, without knowing the probability of each category. You prepare for the worst.

Set-based uncertainty methods differ from probabilistic ones because they:

Make no assumptions about the probability distribution of z Require a known probability distribution Can only handle linear constraints

Chapter 4: Expected Value

When you know (or can estimate) the probability distribution of z, you can optimize the expected objective:

minimize_x E_z[f(x, z)]

The expectation integrates over all possible z, weighted by their probability. This finds the design that performs best on average. It can be estimated via Monte Carlo sampling: draw z⁽¹⁾, ..., z^(m) from the distribution and approximate E[f] ≈ (1/m)∑f(x, z⁽ⁱ⁾).

Key insight: Expected-value optimization is less conservative than minimax. It does not protect against the absolute worst case — it protects against the average case. If bad outcomes are rare, the expected-value solution can be much better than the minimax solution at the likely operating point.

Expected-value optimization is less conservative than minimax because it:

Weights scenarios by their probability, not just the worst case Ignores uncertainty entirely Only considers the best case

Chapter 5: Variance Reduction

Beyond the expected value, the variance of f(x, z) matters. A design with low expected value but high variance is risky. Adding a variance penalty gives:

minimize_x E[f(x,z)] + κ · Var[f(x,z)]

The parameter κ controls risk aversion. Higher κ penalizes variability more, preferring designs that are consistent even if slightly worse on average.

The mean-variance tradeoff: This is the same idea behind Markowitz portfolio theory. You want high expected return (low expected cost) but also low risk (low variance). The efficient frontier of mean-variance tradeoffs mirrors the Pareto frontier of Chapter 15.

Adding a variance penalty to the expected value favors designs that are:

Consistent under uncertainty, even if slightly worse on average Optimal only at the exact design point Feasible only for one realization of z

Chapter 6: Chance Constraints

Chance constraints require that constraints be satisfied with at least a specified probability:

P(g(x, z) ≤ 0) ≥ 1 − δ

For example, "the bridge must support the load in 99.9% of scenarios." The parameter δ is the acceptable failure probability.

Chance constraints are harder to enforce than deterministic constraints because evaluating the probability requires integration over z. Common approaches: sample average approximation (estimate the probability from Monte Carlo samples) or analytical bounds (for Gaussian distributions, convert to deterministic constraints via quantiles).

Think of it this way: Minimax says "no failure ever." Chance constraints say "failure rate below δ." Chance constraints are less conservative and more practical when absolute guarantees are impossible or unnecessarily expensive.

A chance constraint P(g(x,z) ≤ 0) ≥ 0.95 means:

The constraint must be satisfied with at least 95% probability 95% of design variables must satisfy the constraint The constraint is relaxed by 95%

Chapter 7: Robust vs. Reliable

Approach	Focus	Technique
Robust design	Objective insensitivity	Minimize mean + variance of f
Reliable design	Constraint satisfaction probability	Chance constraints, safety margins

Robust design cares about the objective being good under uncertainty. Reliable design cares about constraints being satisfied under uncertainty. A good design under uncertainty is both robust (good performance on average) and reliable (constraints rarely violated).

Practical perspective: In engineering, reliability often trumps optimality. A bridge that is slightly overdesigned but never fails is worth more than a bridge that is perfectly optimized but occasionally collapses. The cost of failure must be weighed against the cost of conservatism.

The difference between robust and reliable design is that robust focuses on:

Objective insensitivity, while reliable focuses on constraint satisfaction Speed, while reliable focuses on accuracy Linear problems, while reliable handles nonlinear

Chapter 8: Summary

Approach	Uncertainty Model	Character
Minimax	Set-based (z ∈ Z)	Most conservative; worst-case guarantee
Expected value	Probabilistic (z ~ p)	Average-case optimal
Mean + variance	Probabilistic	Risk-averse average case
Chance constraints	Probabilistic	Constraint failure bounded by δ

The full picture: This chapter completes the optimization toolbox. From unconstrained gradient descent (Chapter 5) through constrained optimization (Chapters 10–14), surrogate-based global search (Chapters 17–19), and now robust design under uncertainty — you have the tools to tackle real-world optimization problems where nothing is perfect, nothing is free, and nothing is certain.

Optimization under uncertainty is important because real-world designs must:

Perform well across uncertain conditions, not just at one ideal point Only work at the nominal operating point Ignore manufacturing tolerances