Chance constrained optimization • chance constraints and percentile optimization • chance constraints for log-concave distributions • convex approximation of chance constraints sources: Rockafellar & Uryasev, Nemirovsky & Shapiro EE364A — Chance Constrained Optimization 1Chance constraints and pe r centile optimization • ‘chance constraints’ (η is ‘confidence leve l’): Prob(fi(x, ω) ≤ 0) ≥ η – convex in some cases (later) – generally interested in η = 0.9, 0.95, 0.99 – η = 0.999 meaningless (unless you’re sure about the distribution tails) • percentile optimization (γ is ‘η-pe r centile’): minimize γ subject to Prob(f0(x, ω) ≤ γ) ≥ η – convex or quasi-convex in some ca ses (late r ) EE364A — Chance Constrained Optimization 2Value-at-risk and conditional value-at-risk • value-at-risk of random variable z, a t level η: VaR(z; η) = inf{γ | Prob(z ≤ γ) ≥ η} – chance constraint Prob(fi(x, ω) ≤ 0) ≥ η same as VaR(fi(x, ω); η) ≤ 0 conditional value-at-risk: • CVaR(z; η) = inf (β + 1/(1 − η) E(z − β)+) β – CVaR(z; η) ≥ VaR(z; η) (more on this later) EE364A — Chance Constrained Optimization 3CVaR interpretation (for continuous distributions) in CVaR definition, β⋆ = VaR(z; η):• d 0 =(β + 1/(1 − η) E(z − β)+) = 1 − 1/(1 − η) Prob(z ≥ β)dβ so Prob(z ≥ β⋆) = 1 − η • conditional tail expectation (or expected shortfall) E(z|z ≥ β ⋆ ) = E(β ⋆ + (z − β ⋆ )|z ≥ β ⋆ ) = β ⋆ + E((z − β ⋆ )+)/ Prob(z ≥ β ⋆ ) = CVaR(z; η) EE364A — Chance Constrained Optimization 4Chance constraints for lo g-concave distributions • suppose – ω has log-concave density p(ω) – C = {(x, ω) | f(x, ω) ≤ 0} is convex in (x, ω) then � • Prob(f(x, ω) ≤ 0) = 1((x, ω) ∈ C)p(ω) dω is log-concave, since integrand is • so chance constraint Prob(f(x, ω) ≤ 0) ≥ η can be expressed as convex constraint log Prob(f(x, ω) ≤ 0) ≥ log η EE364A — Chance Constrained Optimization 5� � Linear inequality with normally distributed parameter • consider aTx ≤ b, with a ∼ N(¯a, Σ) then aTx − b ∼ N(¯aTx − b, xTΣx)• hence • a¯ x Prob(a T x ≤ b) = Φ b√−xTΣTx and so • Prob(a T x ≤ b) ≥ η ⇐⇒ b − a¯T x ≥ Φ−1(η)�Σ1/2 x�2 a second-order cone constraint for η ≥ 0.5 (i.e., Φ−1(η) ≥ 0) EE364A — Chance Constrained Optimization 6Portfolio optimization example • x ∈ Rn gives portfolio allocation; xi is (fractional) position in asset i x must satisfy 1Tx = 1, x ∈ C (convex portfolio constraint set) • portfolio return (say, in percent) is pTx, where p ∼ N(¯p, Σ) • (a mor e realistic model is p log-norma l) • maximize expected return subject to limit on proba bility of loss EE364A — Chance Constrained Optimization 7• problem is maximize E pTx subject to Prob(pTx ≤ 0) ≤ β 1Tx = 1, x ∈ C • can be expresse d as c onve x pr oblem (provided β ≤ 1/2) maximize p¯Tx subject to p¯Tx ≥ Φ−1(1 − β)�Σ1/2x�2 1Tx = 1, x ∈ C (an SOCP when C is polyhedron) EE364A — Chance Constrained Optimization 8Example • n = 10 a ssets, β = 0.05, C = {x | x � −0.1} • compare – optimal por tfolio – optimal por tfolio w/o loss risk constraint – uniform portfolio (1/n)1 portfolio optimal w/o loss constraint uniform E pTx 7.51 10.66 3.41 Prob(pTx ≤ 0) 5.0% 20.3% 18.9% EE364A — Chance Constrained Optimization 9return distributions: −20 −15 −10 −5 0 5 10 15 20 25 30 optimal w/o loss co n straint −20 −15 −10 −5 0 5 10 15 20 25 30 uniform −20 −15 −10 −5 0 5 10 15 20 25 30 EE364A — Chance Constrained Optimization 10Convex approximation o f chance constraint bound • assume fi(x, ω) is convex in x suppose φ : R R is nonnegative convex nondecreasing, with φ(0) = 1• →• for any αi > 0, φ(z/αi) ≥ 1(z > 0) for all z, so E φ(fi(x, ω)/αi) ≥ Prob(fi(x, ω) > 0) • hence (convex) constraint E φ(fi(x, ω)/αi) ≤ 1 − η ensures chance constraint Prob(fi(x, ω) ≤ 0) ≥ η holds • this holds for any αi > 0; we now show how to optimize over αi EE364A — Chance Constrained Optimization 11write constraint as • E αiφ(fi(x, ω)/αi) ≤ αi(1 − η) – (perspective function) vφ(u/v) is convex in (u, v) for v > 0, nondecreasing in u – so composition αiφ(fi(x, ω)/αi) is convex in (x, αi) for αi > 0 – hence constra int above is convex in x and αi – so we can optimize over x and αi > 0 via convex optimization • yields a convex stochastic optimization problem that is a conse r vative approximation of the chance-constrained problem • we ’ ll look at some special cases EE364A — Chance Constrained Optimization 12Markov chance constraint bound • taking φ(u) = (u + 1)+ gives Markov bound: f or any αi > 0, Prob(fi(x, ω) > 0) ≤ E(fi(x, ω)/αi + 1)+ • convex appr oximation constraint E αi(fi(x, ω)/αi + 1)+ ≤ αi(1 − η) can be written as E(fi(x, ω) + αi)+ ≤ αi(1 − η) • we ca n optimize over x a n d αi ≥ 0 EE364A — Chance Constrained Optimization 13� � Interpretation via cond i tion al value-at-risk • write conservative approximation as E(fi(x, ω) + αi)+ 1 − η − αi ≤ 0 • LHS is convex in (x, αi), so minimum over αi, E(fi(x, ω) + αi)+inf − αi αi>0 1 − η is convex in x • this is CVaR(fi(x, ω); η) (can show αi > 0 can be dropped) • so convex approximation replaces VaR(fi(x, ω); η) ≤ 0 with CVaR(fi(x, ω); η) ≤ 0 w hich is convex in x EE364A — Chance Constrained Optimization 14Chebyshev chance constraint bound • taking φ(u) = (u + 1) 2+ yields Chebyshev bound: for any αi > 0, Prob(fi(x, ω) > 0) ≤ E(fi(x, ω)/αi + 1)• convex appr oximation constraint 2+ E αi(fi(x, ω)/αi + 1) 2+ ≤ αi(1 − η) can be written as E(fi(x, ω) + αi)2+ /αi ≤ αi(1 − η) EE364A — Chance Constrained