Stochastic and robust optimisation

Real-world optimisation problems involve uncertainty: future returns, covariances, customer demand, parameter calibrations. Three frameworks: scenario-based stochastic programming, chance constraints, and robust (worst-case) optimisation. Each makes a different commitment to how uncertainty is modelled and how risk-averse the decision maker is.

Stochastic programming

Replace the deterministic objective f(x) with an expectation E_ξ[f(x, ξ)] over random ξ. Sample N scenarios ξ_1, ..., ξ_N from the joint distribution, solve:

minimize    (1/N) Σ_s  f(x, ξ_s)
subject to  (1/N) Σ_s  g(x, ξ_s)  ≤  0   (scenario-averaged constraints)

Sample-average approximation (SAA): replace expectations with empirical averages over N drawn scenarios. Convergence theory guarantees that the SAA optimum converges to the true optimum as N → ∞ (with optimality-gap rates depending on problem geometry).

Two-stage stochastic programming

Stage 1: make decision x. Stage 2: scenario ξ realises, make recourse decision y(ξ) optimally given x and ξ. Useful for portfolio construction with mid-period rebalancing, dynamic hedging, inventory planning, and capital allocation.

Chance constraints

P(g(x, ξ) ≤ 0) ≥ 1 - α

Require constraint satisfaction with probability ≥ 1 - α. Generally non-convex, but tractable convex reformulations exist for specific distributions (Gaussian → SOCP, as in Module 8) or via convex approximations (Bernstein, scenario-CVaR).

Conditional Value-at-Risk (CVaR) optimisation

VaR optimisation is non-convex. Rockafellar-Uryasev (2000) derived a remarkable convex programming representation of CVaR minimisation:

CVaR_α(L(x, ξ)) = min_t  t + (1/(1-α)) E[(L(x, ξ) - t)⁺]

Joint optimisation over (x, t) is a convex program (under convex L). With Monte Carlo scenarios: introduce slack variables z_s ≥ L(x, ξ_s) - t, z_s ≥ 0; minimise t + (1/(N(1-α))) Σ z_s subject to constraints. This converts CVaR optimisation into an LP or QP, depending on how L depends on x. Industry-standard tail-risk allocation runs on this.

Robust optimisation

Decision-maker is averse to model uncertainty. Choose x to optimise the worst case over an uncertainty set U:

min_x  max_{ξ ∈ U}  f(x, ξ)

Convex tractability hinges on the geometry of U. Box-shaped U: LP. Ellipsoidal U: SOCP. Polyhedral U: LP. Soyster (1973) showed that polyhedral robust LPs are themselves LPs (with more variables); Ben-Tal-Nemirovski (1998) developed the ellipsoidal case.

Distributionally robust optimisation (DRO)

Instead of optimising over scenarios or worst-case parameters, optimise over the worst distribution in some ambiguity set: min_x sup_{P ∈ P̃} E_P[f(x, ξ)]. Wasserstein-ball ambiguity sets (P̃ contains all distributions within Wasserstein distance ε of the empirical distribution) make DRO equivalent to regularised SAA in many cases. DRO is the modern frontier of optimisation under uncertainty.

Which framework when?

• Stochastic programming: when you have a credible joint distribution and want expected-value optimality.
• Chance constraints: when you have safety-critical constraints (regulatory VaR, risk limits) that must hold with high probability.
• CVaR / Expected Shortfall: when you want tail-aware risk control with convex tractability.
• Robust: when you distrust the distribution and want worst-case-set guarantees.
• DRO: when you trust the empirical distribution but want robustness to small distributional shifts.