nemirovski2006convex

Convex Approximations of Chance Constrained Programs

Authors: Arkadi Nemirovski, Alexander Shapiro · Year: 2006 · Venue: SIAM Journal on Optimization, 17(4):969–996

Raw full-text conversion pending — the LAN/marker cluster is down (2026-07-04). Built from the abstract + §1–2 read in full (the convex-approximation and CVaR result) plus §3–6 read via abstract and section structure, from the author-hosted PDF via firecrawl (www2.isye.gatech.edu/~nemirovs/SIOPT_Bern_2006.pdf), not a marker conversion. File the PDF to Docs/raw/pdf/nemirovski2006convex.pdf and run marker when the cluster returns.

Summary

The paper studies chance constrained programs $\min f(\mathbf{x})$ s.t. $\mathrm{Prob}\{F(\mathbf{x},\xi )\le 0\}\ge 1-\alpha$, which are generically computationally intractable (nonconvex feasible sets, feasibility only checkable by Monte-Carlo, NP-hard cases). It builds a general class of convex conservative approximations: efficiently solvable convex programs whose feasible set is contained in the chance-constraint feasible set, so any solution is feasible-suboptimal for the true problem. Two central results follow. First, within a family of approximations generated by a one-dimensional “generating function” $\psi$, the piecewise-linear ${\psi }^{\ast }(z)=[1+z{]}^{+}$ is the least conservative choice, and it reproduces exactly the CVaR constraint — i.e. the Rockafellar–Uryasev CVaR constraint is the tightest convex conservative approximation obtainable this way. Second, for constraints affine in an independent-component perturbation $\xi$, they derive the Bernstein approximation, an explicit convex program (jointly convex in $\mathbf{x}$ and a scale variable) with size independent of the risk level $\alpha$, and extend it to ambiguous chance constraints where $\xi$‘s distribution is only known to lie in a convex compact set.

Key Claims

• Chance constraints are generically intractable. Even the bilinear scalar constraint $\mathrm{Prob}\{a^{\top }x\le b\}\ge 1-\alpha$ has, in general, a nonconvex feasible set and a left-hand side that cannot be computed to accuracy $ϵ$ in time polynomial in $\dim a$ and $\ln (1/ϵ)$ unless P = NP (Khachiyan). Convexity+computability together are a “rare commodity” (holds for log-concave / rotationally-invariant, e.g. Gaussian, data).
• Generating-function approximations. For a nonnegative, nondecreasing, convex generating function $\psi$ with $\psi (z)>\psi (0)=1$ for $z>0$, defining $\Psi (\mathbf{x},t)=t\mathbb{E}[\psi (t^{-1}F(\mathbf{x},\xi ))]$ gives a convex conservative approximation: ${\inf }_{t>0}[\Psi (\mathbf{x},t)-t\alpha ]\le 0\Rightarrow \mathrm{Prob}\{F>0\}\le \alpha$ (§2).
• CVaR is the tightest member (the load-bearing result). The piecewise-linear ${\psi }^{\ast }(z)=[1+z{]}^{+}$ is “the best choice of the generating function” (least conservative / most accurate). With it the approximate constraint becomes ${\inf }_{t>0}\mathbb{E}[[F(\mathbf{x},\xi )+t{]}^{+}]-t\alpha \le 0$, which is equivalent to ${\mathrm{CVaR}}_{1-\alpha }[F(\mathbf{x},\xi )]\le 0$. They state: “The idea of using CVaR as a convex approximation of VaR is due to Rockafellar and Uryasev.”
• Chance constraint = VaR constraint. They note the chance constraint in (1.1) “is nothing but ${\mathrm{VaR}}_{1-\alpha }[F(\mathbf{x},\xi )]\le 0$,” and since ${\mathrm{CVaR}}_{1-\alpha }\ge {\mathrm{VaR}}_{1-\alpha }$, the CVaR constraint is a convex conservative (inner) approximation.
• CVaR is tightest but not always computable. A stated drawback of the optimal ${\psi }^{\ast }$: it is “unclear how to compute efficiently the corresponding function $\Psi (\mathbf{x},t)$” even for affine $F$ with independent ${\xi }_j$ — which motivates the (slightly more conservative but explicit) exponential/Bernstein route.
• Bernstein approximation. For $F_i(\mathbf{x},\xi )=f_{i0}(\mathbf{x})+{\sum }_j{\xi }_j{f}_{ij}(\mathbf{x})$ with independent ${\xi }_j$ of computable moment-generating functions, a large-deviation bound yields an explicit convex program, jointly convex in $\mathbf{x}$ and the scale $t$ (their step past Pintér 1989: the scale becomes a variable, not an ad-hoc constant). Its size is independent of $\alpha$ — unlike scenario approximation, whose sample size $N\gtrsim \mathrm{Ceil}(2n{\alpha }^{-1}\log (12/\alpha )+2{\alpha }^{-1}\log (2/\delta )+2n)$ grows like $1/\alpha$ and linearly in $n$.
• Ambiguous chance constraints. The construction extends to distributionally-robust form: the tuple of (independent) component distributions is only known to lie in a convex compact set, and the constraint must hold for every member — a worst-case-over-distributions reading (§6).

Method

The object is the chance constrained program (1.1) ${\min }_{\mathbf{x}\in X}f(\mathbf{x})$ s.t. $\mathrm{Prob}\{F(\mathbf{x},\xi )\le 0\}\ge 1-\alpha$, replaced by a convex conservative surrogate (1.3) ${\min }_{\mathbf{x}\in X,u}f(\mathbf{x})$ s.t. $G(\mathbf{x},u)\le 0$ with $G$ convex and efficiently computable, feasible set $\subseteq$ that of (1.1). The generating-function bound uses the Markov-type inequality $p(\mathbf{x})\le \mathbb{E}[\psi (t^{-1}F(\mathbf{x},\xi ))]$ for $t>0$; convexity of $\psi$ and $\psi (z)\ge 1_{[0,\infty )}(z)$ make this a valid, convex, conservative envelope. Optimizing the free scale $t$ inside the constraint (moving to ${\inf }_{t>0}$) keeps convexity via perspective/partial-minimization arguments. The Bernstein branch replaces ${\psi }^{\ast }$ by the exponential $\psi (z)=e^z$, whose $\Psi (\mathbf{x},t)$ is computable from moment-generating functions, trading a little tightness for an explicit program.

Regime. A stochastic-programming / optimization-theory paper, regime-agnostic — no dynamics of any robot, let alone the free-flying / free-floating distinction. It governs the risk layer: which convex surrogate to put in place of an intractable chance constraint.

Relevance to thesis

This is the citable authority for the sentence “CVaR is the tightest convex conservative approximation of a chance constraint,” which underpins the CVaR-vs-chance-constraint trade in risk-aware view scoring. It sharpens the thesis argument in two ways. (i) At a matched risk level, a CVaR constraint is strictly more conservative than the chance constraint it approximates — but that extra conservatism is the minimum achievable within a convex program, so a fair CVaR-vs-chance comparison must retune levels or credit this minimality rather than treat CVaR as gratuitously cautious. (ii) The paper’s own caveat — the optimal CVaR generating function is not always efficiently computable, which is why they develop Bernstein — supports the brief’s stance that we justify CVaR by tail-severity semantics and covariance-/distribution-misspecification robustness (the ambiguous-chance-constraint / worst-case-over-distributions reading), not by tractability. For non-Gaussian, possibly ambiguous inspection uncertainty, the §6 ambiguous extension is the directly relevant tool.

Connections

Topics: chance_constraints · conditional_value_at_risk · value_at_risk · coherent_risk_measures · sequential_convex_programming Sources: rockafellar2000optimization (the CVaR form shown here to be the tightest convex approximation) · majumdar2017how · ren2022chance · dixit2023risk

Key Equations / Quotes

Chance constrained program (1.1) and its convex conservative surrogate (1.3):

$$\underset{\mathbf{x}\in X}{\min }f(\mathbf{x})\text{s.t.}\mathrm{Prob}\{F(\mathbf{x},\xi )\le 0\}\ge 1-\alpha ⟶\underset{\mathbf{x}\in X,u}{\min }f(\mathbf{x})\text{s.t.}G(\mathbf{x},u)\le 0$$

Generating-function bound (§2), then the optimal ${\psi }^{\ast }(z)=[1+z{]}^{+}$ giving the CVaR constraint (Eqs. 2.8, 2.10–2.11):

$$\Psi (\mathbf{x},t)=t\mathbb{E}\left[\psi \left(t^{-1}F(\mathbf{x},\xi )\right)\right],\underset{t>0}{\inf }\left[\Psi (\mathbf{x},t)-t\alpha \right]\le 0\Rightarrow \mathrm{Prob}\{F>0\}\le \alpha$$ $$\underset{t>0}{\inf }\mathbb{E}\left[[F(\mathbf{x},\xi )+t{]}^{+}\right]-t\alpha \le 0⟺{\mathrm{CVaR}}_{1-\alpha }[F(\mathbf{x},\xi )]\le 0,{\mathrm{CVaR}}_{1-\alpha }(Z):=\underset{\tau \in \mathbb{R}}{\inf }\tau +\frac{1}{\alpha }\mathbb{E}[Z-\tau {]}^{+}$$

“From the point of view of the most accurate approximation, the best choice of the generating function $\psi$ is the piecewise linear function ${\psi }^{\ast }$.” (§2)

“Since the chance constraint in (1.1) is nothing but ${\mathrm{VaR}}_{1-\alpha }[F(x,\xi )]\le 0$, the constraint ${\mathrm{CVaR}}_{1-\alpha }[F(x,\xi )]\le 0$ defines a convex conservative approximation of the chance constraint.” (§2)

Open Questions

• The tightest-convex result is within the generating-function family; is CVaR the tightest convex conservative approximation in an absolute sense, or only relative to this class? (The paper claims the former only for $\psi$-generated approximations.)
• Bernstein needs $F$ affine in $\xi$ with independent components. Inspection uncertainty couples base and arm through the manipulator Jacobian (correlated, non-affine) — how much tightness is lost forcing it into the affine/independent mold?
• The ambiguous (§6) extension is the natural home for covariance-misspecification robustness; what convex compact ambiguity set correctly models an estimated camera-pose / state covariance for view scoring?