Convex Optimization

Optimization’s real watershed is not linear vs nonlinear but convex vs nonconvex: for a convex problem a local optimum is automatically global, and a simple gradient/KKT condition certifies it — convex problems are the ones you can actually solve and trust. The subject then has two jobs. (1) Recognize or build convexity — a calculus of convexity-preserving operations on sets and functions, the two welded together by the epigraph. (2) Exploit it — optimality conditions and, above all, duality, which lower-bounds every problem, closes the gap under Slater, certifies optimality via KKT, prices the constraints, and turns intractable robust/infinite problems into solvable ones. Problems sort into a hierarchy LP ⊂ QP ⊂ SOCP ⊂ SDP; modeling is transforming yours down to the simplest class that still holds it. A running thread climbs that tower: norm approximation $\min \lVert Ax - b\rVert$. Prerequisites cashed in: PSD matrices, eigenvalues, SVD, projection (track 2); OLS / ridge / lasso (track 4); lasso geometry, SVM, soft-thresholding, logistic loss (track 6); MAP-as-penalty and conjugacy (track 7); MLE (track 3).

1. Why convexity — local is global

• Convex set: the segment between any two of its points stays inside — $\theta x + (1-\theta)y \in C$ for $\theta \in [0,1]$. Convex function: its domain is convex and every chord lies above the graph,

$f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y), \qquad \theta \in [0,1].$

(Affine = the boundary case, equality always; concave = $-f$ convex.)

• The payoff — local optimum is global. Derive it. Suppose $x$ is locally optimal but some feasible $y$ has $f(y) < f(x)$. Walk from $x$ toward $y$: $z_\theta = (1-\theta)x + \theta y$. Convexity bounds the value on the segment,

$f(z_\theta) \le (1-\theta)f(x) + \theta f(y) < f(x) \quad\text{for } \theta \in (0,1].$

Because the feasible set is convex and $x, y$ are both feasible, every $z_\theta$ on the segment is feasible too. For small $\theta$, $z_\theta$ is arbitrarily close to $x$ yet strictly better — contradicting local optimality. So no feasible point beats $x$: local = global. This single fact is why convex problems are tractable; non-convex ones hide better optima in valleys you can’t see locally.

• Certifiability (first-order). For differentiable convex $f$, the first-order Taylor expansion is a global underestimator:

$f(y) \ge f(x) + \nabla f(x)^T(y - x) \quad \forall x, y.$

From local information at $x$ you bound $f$ everywhere. Setting up the unconstrained optimum: $\nabla f(x) = 0$ then forces $f(y) \ge f(x)$ for all $y$ — a certificate of global optimality, not just a stationarity coincidence.

• Recognizing the easy cases. Least squares ($\min \lVert Ax-b\rVert_2^2$, a bowl) and linear programs (linear objective, affine constraints) are the two oldest convex templates. The running example $\min \lVert Ax - b\rVert$ is convex for any norm (norms are convex) — the open question is which class it lands in (§4).

Implications

• “Local = global” is the entire reason the taxonomy below matters: every modeling trick exists to keep you inside the convex world where this holds.
• Certifiability means convex solvers return not just an answer but a proof (the dual certificate, §5) — you know you’re done.

Core competency set

• State convex set / convex function (chords above); prove local = global by the segment argument.
• State the first-order global-underestimator inequality and why $\nabla f = 0$ certifies the unconstrained optimum.

2. Convex sets

• Three notions, one knob: how free is $\theta$ in $\theta_1 x_1 + \theta_2 x_2 + \cdots$?

  • affine combination: $\sum\theta_i = 1$, $\theta_i$ any sign — the whole line through any two points stays in. Example: the solution set $\{x : Ax = b\}$ (and conversely every affine set is such a solution set).
  • convex combination: $\sum\theta_i = 1$, $\theta_i \ge 0$ — only the segment stays in.
  • conic combination: $\theta_i \ge 0$ (no sum constraint) — a convex cone holds all of these.

  Each hull (affine/convex/conic) is the smallest such set containing $C$; loosening the constraint on $\theta$ enlarges the notion. A set is convex iff it equals its convex hull.

• The example zoo — memorize the shape and a representation:

  • hyperplane $\{a^Tx = b\}$ (normal $a$); halfspace $\{a^Tx \le b\}$ — convex, not affine (not closed under scaling).
  • Euclidean ball $B(x_c, r) = \{x_c + ru : \lVert u\rVert_2 \le 1\}$; ellipsoid $\{(x-x_c)^TP^{-1}(x-x_c) \le 1\}$, $P \succ 0$, equivalently $\{x_c + Au : \lVert u\rVert_2 \le 1\}$ — the semi-axes are the singular values of $A$ (track 2).
  • norm ball $\{x : \lVert x - x_c\rVert \le r\}$ for any norm ($L_1$ ball = diamond, $L_\infty$ = cube); norm cone $\{(x,t) : \lVert x\rVert \le t\}$ — the Euclidean one is the second-order cone.
  • polyhedron $\{Ax \preceq b,\ Cx = d\}$ — a finite intersection of halfspaces and hyperplanes.
  • PSD cone $S^n_+ = \{X = X^T : z^TXz \ge 0\ \forall z\}$ — a convex cone (the boundary is rank-deficient matrices); the workhorse of SDP (§4).

• The working skill — build, don’t check. To show a set is convex, assemble it from the zoo via operations that preserve convexity (never grind the definition; that’s only for disproving — find two points whose midpoint escapes):

  • intersection of any number of convex sets — a polyhedron is an intersection of halfspaces, and the construction extends to infinite intersections. Example: $\{x : |x_1\cos t + \cdots + x_m\cos mt| \le 1\ \forall\, |t| \le \pi/3\}$ is convex — an infinite intersection of slabs, one per $t$.
  • affine image / preimage $\{Ax + b : x \in C\}$ and $\{x : Ax + b \in C\}$ — scaling, translation, projection; also the LMI solution set $\{x : \sum x_iA_i \preceq B\}$ (preimage of $S^n_+$, hence convex) and the hyperbolic cone $\{x : x^TPx \le (c^Tx)^2,\ c^Tx \ge 0\}$.
  • perspective $P(x,t) = x/t$ ($t > 0$) — the pinhole-camera map (divide by the last coordinate and drop it); preserves convexity both ways.
  • linear-fractional $f(x) = (Ax+b)/(c^Tx+d)$ — affine, then perspective.

• Separating hyperplane theorem. Two nonempty disjoint convex sets $C, D$ can be separated: $\exists\, a \ne 0, b$ with $a^Tx \le b$ on $C$ and $a^Tx \ge b$ on $D$ (build $a$ from the segment between the two closest points). Strict separation needs extra (e.g. one set closed, the other a point). This theorem is the existence engine behind duality (§5) and the Fredholm-style “either solve it or certify infeasibility” alternatives.

• Supporting hyperplane theorem. At every boundary point $x_0$ of a convex set $C$ there is a supporting hyperplane $\{x : a^Tx = a^Tx_0\}$ with $a^Tx \le a^Tx_0$ for all $x \in C$ — a tangent halfspace containing $C$. (Convexity is exactly what guarantees one exists at every boundary point.) This is the geometric content of strong duality: the dual optimum is the supporting hyperplane to the value set at the optimum (§5).

• Generalized inequalities. A proper cone $K$ — convex, closed, solid (nonempty interior), pointed (contains no line) — defines a partial order $x \preceq_K y \iff y - x \in K$. The two you use: componentwise ($K = \mathbb R^n_+$) and the Löwner/PSD order ($K = S^n_+$). Unlike $\le$ on $\mathbb R$ it is not a total order — some pairs are incomparable.

• Dual cone $K^* = \{y : y^Tx \ge 0\ \forall x \in K\}$ (the vectors making a non-obtuse angle with all of $K$) — always convex, even if $K$ isn’t. $\mathbb R^n_+$ and $S^n_+$ are self-dual; the $(L_1, L_\infty)$ norm cones are duals of each other. The dual cone supplies the multipliers for cone constraints (§4 SDP, §5).

• Minimum vs minimal — and why scalarization works. With a non-total order, “smallest” splits in two:

  • $x$ is the minimum of $S$ if $x \preceq_K y$ for all $y \in S$ (it beats everything; unique if it exists). Dual test: $x$ is minimum iff it is the unique minimizer of $\lambda^Tz$ over $S$ for every $\lambda \succ_{K^*} 0$.
  • $x$ is minimal if nothing is strictly below it ($y \preceq_K x \Rightarrow y = x$); there can be many. Dual fact: if $x$ minimizes $\lambda^Tz$ over $S$ for some $\lambda \succ_{K^*} 0$ then $x$ is minimal — and for convex $S$ every minimal point arises this way.

  This is exactly scalarization: a single price $\lambda \succ_{K^*} 0$ collapses a vector objective to a scalar one whose solution is Pareto-optimal — the Pareto frontier is traced by sweeping $\lambda$ (regularization tradeoff curves, §6).

Implications

• The convexity-preserving operations mirror §3’s function operations — and are the reason real modeling never invokes the definition: you assemble convex objects from a known kit.
• The supporting hyperplane theorem is the seed of duality: a separating/supporting hyperplane between the achievable-value set and the “better-than-$p^\star$” region is the optimal dual multiplier (§5’s geometric interpretation). Set geometry and duality are one story.
• Scalarization (minimal-via-dual-inequality) is why multi-objective problems reduce to weighted scalar ones, and why the regularization parameter $\gamma$ traces a Pareto curve.

Core competency set

• Give the affine/convex/conic combination distinction (the $\theta$ knob) and the example zoo with a representation each (ellipsoid, norm cone, polyhedron, PSD cone).
• Name the convexity-preserving operations with an example each (infinite intersection, LMI preimage, perspective); state the separating and supporting hyperplane theorems and their link to duality.
• Define proper cone, $\preceq_K$, dual cone (self-dual examples); distinguish minimum vs minimal and state the scalarization (dual-inequality) characterization.

3. Convex functions

• Definition and the line test. $f$ is convex if $\mathrm{dom}\,f$ is convex and every chord lies above the graph (§1). The practical checker: $f$ is convex iff its restriction to every line is convex — $g(t) = f(x + tv)$ convex in $t$ for all $x \in \mathrm{dom}\,f$, all $v$. This collapses an $n$-dimensional question to one dimension. Worked ($\log\det$): for $f(X) = \log\det X$ on $S^n_{++}$, restrict to the line $X + tV$ and set $g(t) = \log\det(X + tV)$. Factor out $X^{1/2}$ from both sides:

$X + tV = X^{1/2}\big(I + t\,X^{-1/2}VX^{-1/2}\big)X^{1/2}.$

Take $\log\det$, using $\det(ABC) = \det A\,\det B\,\det C$ and $\det X^{1/2}\,\det X^{1/2} = \det X$:

$g(t) = \log\det X + \log\det\big(I + t\,X^{-1/2}VX^{-1/2}\big).$

Let $\lambda_i$ be the eigenvalues of $M = X^{-1/2}VX^{-1/2}$; then $I + tM$ has eigenvalues $1 + t\lambda_i$ and $\det(I+tM) = \prod_i(1+t\lambda_i)$, so the log of the product is a sum of logs:

$g(t) = \log\det X + \sum_{i=1}^n \log(1 + t\lambda_i).$

Each $\log(1+t\lambda_i)$ is concave in $t$ and a sum of concave functions is concave, so $g$ is concave on every line — by the line test, $\log\det$ is concave.

• First-order condition (differentiable): convex $\iff$ the tangent is a global underestimator,

$f(y) \ge f(x) + \nabla f(x)^T(y - x) \quad \forall x, y.$

Local slope bounds the entire function — the property that makes $\nabla f = 0$ certify a global min (§1) and that powers the dual lower bounds (§5).

• Second-order condition: convex $\iff \nabla^2 f(x) \succeq 0$ everywhere (PD ⟹ strictly convex). Worked, in rising difficulty:
  • quadratic $\tfrac12 x^TPx + q^Tx + r$: $\nabla^2 f = P$, convex iff $P \succeq 0$ (the bowl opens up everywhere);
  • least squares $\lVert Ax - b\rVert_2^2 = (Ax-b)^T(Ax-b)$: gradient $\nabla f = 2A^T(Ax-b)$, so $\nabla^2 f = 2A^TA$; and $A^TA \succeq 0$ for any $A$ because $z^TA^TAz = \lVert Az\rVert_2^2 \ge 0$ (track 2) — convex always;
  • quadratic-over-linear $x^2/y$ ($y>0$): partials $f_x = 2x/y$, $f_y = -x^2/y^2$, then $f_{xx} = 2/y$, $f_{xy} = -2x/y^2$, $f_{yy} = 2x^2/y^3$, which assemble as $\nabla^2 f = \frac{2}{y^3}\begin{bmatrix} y^2 & -xy \\ -xy & x^2 \end{bmatrix} = \frac{2}{y^3}\binom{y}{-x}\binom{y}{-x}^T \succeq 0,$ a rank-1 outer product scaled by $2/y^3 > 0$, hence PSD;
  • log-sum-exp $\log\sum_k e^{x_k}$ (the smooth $\max$): with $z_k = e^{x_k}$, $\nabla^2 f = \tfrac{1}{\mathbf 1^Tz}\mathrm{diag}(z) - \tfrac{1}{(\mathbf 1^Tz)^2}zz^T$, and

$v^T\nabla^2 f\,v = \frac{(\sum_k z_k v_k^2)(\sum_k z_k) - (\sum_k v_k z_k)^2}{(\sum_k z_k)^2} \ge 0$

by Cauchy–Schwarz on the vectors $\sqrt{z_k}$ and $\sqrt{z_k}\,v_k$ — a genuine PSD proof, not an assertion.

• The epigraph bridge — the keystone. $\text{epi}\,f = \{(x,t): f(x) \le t\}$, everything on/above the graph. Then

$f \text{ convex} \iff \text{epi}\,f \text{ convex}.$

This welds §2 to §3: every fact about convex sets becomes a fact about convex functions and back. It is also the reformulation trick behind half of modeling — replace “minimize $f(x)$” by “minimize $t$ s.t. $f(x) \le t$” (§4). (Sublevel sets $\{f \le \alpha\}$ are convex too — but the converse fails, which is what makes quasiconvexity weaker.)

• Jensen. Convexity is exactly $f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$; the probabilistic form is $f(E z) \le E f(z)$ — you pay more on the downside than you recover on the up. (Reappears as the certainty-equivalence bound, §6.)
• The convexity calculus — atoms + operations. Never check the definition; decompose. Atoms: affine $a^Tx+b$, any norm, $\max$, $\exp$, $-\log$, $x\log x$, log-sum-exp, quadratic-over-linear $x^2/y$, $\log\det$ (concave). Operations that preserve convexity, each with its signature use:
  • nonnegative weighted sum / integral — $\sum w_i f_i$, $w_i \ge 0$;
  • affine precomposition $f(Ax+b)$ — the log-barrier $-\sum_i \log(b_i - a_i^Tx)$ (convex on the polyhedron interior, the engine of interior-point methods), and any norm of an affine map $\lVert Ax - b\rVert$ (the running example, convex for free);
  • pointwise max $\max_i f_i$ — piecewise-linear $\max_i(a_i^Tx + b_i)$, and the sum of the $r$ largest entries $x_{[1]} + \cdots + x_{[r]} = \max\{x_{i_1} + \cdots + x_{i_r}\}$ over index sets (a max of linear functions);
  • pointwise sup $g(x) = \sup_{y} f(x,y)$ — convex because $\text{epi}\,g = \bigcap_y \text{epi}\,f(\cdot,y)$ (epigraph bridge). The support function $S_C(x) = \sup_{y\in C} y^Tx$, the distance to the farthest point of a set, and $\lambda_{\max}(X) = \sup_{\lVert y\rVert_2=1} y^TXy$ (a sup of linear-in-$X$ functions — that’s why max-eigenvalue is convex);
  • composition $h(g(x))$: convex if ($h$ convex ↑, $g$ convex) or ($h$ convex ↓, $g$ concave) — read it off the chain rule $h''(g)\,g'^2 + h'(g)\,g''$;
  • partial minimization $\inf_{y\in C} f(x,y)$ convex if $f$ is jointly convex and $C$ convex (Schur-complement minimization is the classic instance — minimizing a joint quadratic over $y$ leaves the Schur complement in $x$);
  • perspective $t\,f(x/t)$ ($t>0$) — cone-ifies $f$;
  • conjugate $f^*(y) = \sup_{x}(y^Tx - f(x))$ — convex even if $f$ isn’t (a sup of affine functions of $y$); the biconjugate $f^{**}$ is the convex envelope (largest convex underestimator). Worked: negative entropy $f(x) = \sum_i x_i\log x_i$ has conjugate $f^*(y) = \sum_i e^{y_i - 1}$ — the term that makes the entropy-maximization dual closed-form (§5).
• Quasiconvex (weaker): all sublevel sets $\{f \le \alpha\}$ are convex (but $f$ itself need not be) — e.g. $\sqrt{|x|}$, the linear-fractional $(c^Tx+d)/(e^Tx+f)$, internal rate of return. Optimized by bisection on $\alpha$ (a convex feasibility problem at each threshold), not in one shot. Log-concave ($\log f$ concave): Gaussian densities, CDFs — and preserved under products and (crucially) marginalization/convolution, the reason many statistical likelihoods stay tractable.

Implications

• The atom-list + operation-list is the subject’s working skill; the rest of modeling is pattern-matching your objective to it, never invoking the definition.
• The conjugate is the analytic engine of duality (§5) — the dual function literally is a conjugate of the objective.
• Sup-of-convex is convex but inf is not (unless jointly convex) — the asymmetry is why worst-case robustness (§6) is the hard direction and partial-minimization needs joint convexity.

Core competency set

• Use the line test (log-det example); state FOC (global underestimator) and SOC.
• Prove log-sum-exp convex via the Cauchy–Schwarz Hessian argument; prove $f$ convex $\iff$ epi $f$ convex and use it for pointwise sup.
• Recite the atoms and operations with a signature example each; give the composition rule and the negative-entropy conjugate.
• Define quasiconvex (sublevel sets) + bisection, and log-concave + what it survives.

4. Convex problems and the hierarchy

• Standard form: minimize $f_0(x)$ s.t. $f_i(x) \le 0$ ($i=1..m$), $h_i(x) = 0$ ($i=1..p$). It is a convex problem when $f_0, f_i$ are convex and the equalities are affine ($Ax = b$) — then the feasible set is convex and (§1) every local optimum is global.
• Optimality condition (differentiable $f_0$): $x$ is optimal iff feasible and

$\nabla f_0(x)^T(y - x) \ge 0 \quad \text{for all feasible } y$

— the negative gradient points out of the feasible set; you can’t descend without leaving. Unconstrained, this is $\nabla f_0(x) = 0$.

• Equivalent reformulations (solve one, recover the other) — the modeling toolkit:
  • epigraph: $\min t$ s.t. $f_0(x) \le t$ (the bridge from §3) — turns any objective into a linear one with one extra constraint;
  • slack variables: $a_i^Tx \le b_i \rightsquigarrow a_i^Tx + s_i = b_i,\ s_i \ge 0$;
  • eliminate equalities: $Ax = b \rightsquigarrow x = Fz + x_0$ with $\text{range}(F) = \mathcal N(A)$;
  • introduce variables / partial-minimize to expose structure.
• The hierarchy — each class contains the previous; modeling is recognizing (or transforming to) the lowest one that holds your problem.

Linear program (LP) — $\min c^Tx$ s.t. $Gx \preceq h,\ Ax = b$. The feasible set is a polyhedron; the level sets of $c^Tx$ are parallel hyperplanes, so you slide the $-c$ hyperplane across the polyhedron until it last touches — the optimum sits at a vertex.

• Diet problem (the archetype): cheapest food mix meeting nutrient floors, $\min c^Tx$ s.t. $Ax \succeq b,\ x \succeq 0$.
• Piecewise-linear minimization $\min \max_i(a_i^Tx + b_i)$ is not linear — but epigraph-ize the max: $\min t$ s.t. $a_i^Tx + b_i \le t$, an LP. (This is precisely how $L_1$ and $L_\infty$ norm approximation of the running example become LPs.)
• Chebyshev center — the gem. Find the largest ball $\{x_c + u : \lVert u\rVert_2 \le r\}$ inscribed in a polyhedron $\{a_i^Tx \le b_i\}$. “Maximize the inscribed radius” looks nonlinear, but the ball lies in halfspace $i$ iff its worst (deepest-into-the-constraint) point does. Split the sup off the constant term:

$\sup_{\lVert u\rVert_2 \le r} a_i^T(x_c + u) = a_i^Tx_c + \sup_{\lVert u\rVert_2 \le r} a_i^Tu.$

The inner sup is maximized at $u = r\,a_i/\lVert a_i\rVert_2$ (Cauchy–Schwarz), giving $r\lVert a_i\rVert_2$, so the halfspace constraint becomes

$a_i^Tx_c + r\lVert a_i\rVert_2 \le b_i,$

linear in $(x_c, r)$ — so $\max r$ s.t. these constraints is an LP. Recognizing the linear problem hiding under a geometric description is the whole skill.

• Linear-fractional $\min (c^Tx+d)/(e^Tx+f)$ is quasiconvex (bisection), but homogenizes to an exact LP: set $y = x/(e^Tx+f)$, $z = 1/(e^Tx+f)$, giving $\min c^Ty + dz$ s.t. $Gy \preceq hz$, $Ay = bz$, $e^Ty + fz = 1$, $z \ge 0$.

Quadratic program (QP) — $\min \tfrac12 x^TPx + q^Tx + r$ s.t. $Gx \preceq h,\ Ax = b$, with $P \succeq 0$ (the bowl). Minimize a convex quadratic over a polyhedron; the objective’s sublevel sets are ellipsoids, and the optimum is where the smallest ellipsoid touches the polyhedron.

• Least squares is the unconstrained QP, $\min \lVert Ax - b\rVert_2^2$, with the analytic solution $x^\star = A^\dagger b$ (track 2/4) — and the QP framework lets you add what OLS can’t handle: box bounds $l \preceq x \preceq u$, ordering (isotonic regression), nonnegativity.
• Markowitz mean–variance (the archetype): with random cost $c$ (mean $\bar c$, covariance $\Sigma$), $c^Tx$ has mean $\bar c^Tx$ and variance $x^T\Sigma x$, so

$\min\ \bar c^Tx + \gamma\, x^T\Sigma x = E[c^Tx] + \gamma\,\mathrm{Var}(c^Tx)$

trades expected cost against risk, $\gamma > 0$ the risk-aversion dial. The $L_2$ version of the running example lives here.

QCQP — convex-quadratic constraints too, $\tfrac12 x^TP_ix + q_i^Tx + r_i \le 0$ ($P_i \succeq 0$): the feasible set is an intersection of ellipsoids with an affine set.

Second-order cone program (SOCP) — $\min f^Tx$ s.t. $\lVert A_ix + b_i\rVert_2 \le c_i^Tx + d_i$ (norm $\le$ affine, not squared). Setting $c_i = 0$ recovers a QCQP; $A_i = 0$ recovers an LP — so SOCP strictly generalizes both. Robust LP with ellipsoidal data uncertainty lands exactly here (§6).

Geometric program (GP) — minimize a posynomial (sum of monomials $c\,x_1^{a_1}\cdots x_n^{a_n}$, $c > 0$, any real exponents) s.t. posynomials $\le 1$, monomials $= 1$. Not convex as written — but substitute $y_i = \log x_i$ and take logs: a monomial becomes affine $a^Ty + b$, a posynomial becomes log-sum-exp of affine, both convex. The cantilever-beam design (minimize weight s.t. bounds on stress, deflection, aspect ratio) is the archetype — weight and stress are posynomials/monomials in the segment dimensions.

Semidefinite program (SDP) — the variable enters a linear matrix inequality $\sum_i x_iF_i \preceq G$ ($F_i, G$ symmetric), objective $c^Tx$. Top of the everyday hierarchy.

• Eigenvalue minimization: $\min \lambda_{\max}(A(x))$, $A(x) = A_0 + \sum_i x_iA_i$ — use $\lambda_{\max}(A) \le t \iff A \preceq tI$ to get $\min t$ s.t. $A(x) \preceq tI$, an SDP.
• Everything is an SDP (the containment chain made concrete): an LP is $\min c^Tx$ s.t. $\mathrm{diag}(Ax-b) \preceq 0$ (a diagonal LMI); an SOCP constraint $\lVert Ax+b\rVert_2 \le c^Tx+d$ is the LMI $\begin{bmatrix} (c^Tx+d)I & Ax+b \\ (Ax+b)^T & c^Tx+d \end{bmatrix} \succeq 0$ (Schur complement). So LP ⊂ QP ⊂ QCQP ⊂ SOCP ⊂ SDP is a true nesting — each solvable as the next, the price being a slower solver.
• Quasiconvex problems (quasiconvex objective, convex constraints) are solved by bisection — at each candidate value $t$, the sublevel set is convex, so check feasibility; $\lceil\log_2((u-l)/\epsilon)\rceil$ iterations (e.g. bounds $u - l = 1$, tolerance $\epsilon = 10^{-3}$: $\lceil\log_2 1000\rceil = 10$ feasibility solves).
• Picture to hold: the objective’s level sets are nested contours; slide to the lowest one still touching the feasible set. At the touch point the contour’s normal $\nabla f_0$ points back into the set — which is exactly $\nabla f_0(x)^T(y-x) \ge 0$.

Implications

• “Which class?” is the central modeling question: the lower the class, the faster and more reliable the solver, so transform down (the running example shows one problem taking different classes by norm choice).
• The epigraph reformulation is the universal move — it linearizes objectives and is why “minimize $t$ s.t. …” appears everywhere.

Core competency set

• Write standard form and the variational optimality condition $\nabla f_0(x)^T(y-x)\ge0$.
• Reformulate via epigraph / slack / equality-elimination.
• Build the hierarchy LP ⊂ QP ⊂ QCQP ⊂ SOCP ⊂ SDP with the form + geometry of each; sort $L_1/L_2/L_\infty$ approximation by class.
• Reproduce the gems: piecewise-linear → epigraph → LP; the Chebyshev-center sup-derivation; Markowitz mean–variance QP; eigenvalue-min and LP/SOCP-as-SDP (diag / Schur). State bisection for quasiconvex.

5. Duality — the keystone

Constraints are inconvenient; price them instead of enforcing them. This one idea pays off four ways: it bounds, certifies, prices, and robustifies.

• The Lagrangian folds constraints into the objective with prices $\lambda_i \ge 0$ (inequalities) and $\nu_i$ (equalities):

$L(x, \lambda, \nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \sum_i \nu_i h_i(x).$

($\lambda_i$ is the charge for violating $f_i \le 0$; you’re subsidized for slack. Sign convention matters — write constraints as $f_i \le 0$ so $\lambda_i \ge 0$.)

• The dual function minimizes out $x$: $g(\lambda, \nu) = \inf_x L(x,\lambda,\nu)$. It is concave always (an infimum of functions affine in $(\lambda,\nu)$), even when the primal is non-convex — and it is built from conjugates, $g$ involves $-f_0^*(\cdot)$.
• Weak duality — bound. Derive it. Take any feasible $x$ and any $\lambda \succeq 0, \nu$. Since $g$ is an infimum over $x'$, it is below $L$ at this particular $x$:

$g(\lambda,\nu) = \inf_{x'} L(x',\lambda,\nu) \le L(x,\lambda,\nu).$

Expand $L$ and sign the two penalty terms — $\lambda_i f_i(x) \le 0$ ($\lambda_i\ge0$, $f_i\le0$) and $\nu_i h_i(x) = 0$ ($h_i = 0$):

$L(x,\lambda,\nu) = f_0(x) + \underbrace{\textstyle\sum_i \lambda_i f_i(x)}_{\le\,0} + \underbrace{\textstyle\sum_i \nu_i h_i(x)}_{=\,0} \le f_0(x).$

Chaining, $g(\lambda,\nu) \le f_0(x)$ for every feasible $x$; take the inf over feasible $x$: $g(\lambda,\nu) \le p^\star$. Every dual value is a lower bound on the primal optimum — for any problem, convex or not. The best bound is the dual problem $\max_{\lambda \succeq 0,\nu} g$, itself always convex. Picture to hold: each price vector $(\lambda,\nu)$ lays a horizontal floor $g(\lambda,\nu)$ under $p^\star$; the dual problem raises the highest floor, and under Slater the floor reaches the ceiling — the gap closes.

• Worked dual functions (the bound made concrete — each derivation is “form $L$, minimize out $x$, read off $g$”):
  • Least-norm of linear equations $\min x^Tx$ s.t. $Ax = b$. $L = x^Tx + \nu^T(Ax - b)$; set $\nabla_x L = 2x + A^T\nu = 0 \Rightarrow x = -\tfrac12 A^T\nu$; substitute back:

$g(\nu) = -\tfrac14 \nu^TAA^T\nu - b^T\nu,$

a concave quadratic, giving $p^\star \ge g(\nu)$ for every $\nu$ (useful as a stopping certificate for iterative solvers).

• Standard-form LP $\min c^Tx$ s.t. $Ax = b,\ x \succeq 0$. $L = -b^T\nu + (c + A^T\nu - \lambda)^Tx$ is affine in $x$, so $\inf_x L = -\infty$ unless the $x$-coefficient vanishes:

$g(\lambda,\nu) = \begin{cases} -b^T\nu & A^T\nu - \lambda + c = 0 \\ -\infty & \text{otherwise}\end{cases}$

— finite only on an affine set, hence concave. Making that implicit constraint explicit, the dual of an LP is another LP: $\max -b^T\nu$ s.t. $A^T\nu + c \succeq 0$.

• Norm minimization $\min \lVert x\rVert$ s.t. $Ax = b$: $g(\nu) = b^T\nu$ if $\lVert A^T\nu\rVert_* \le 1$, else $-\infty$, where $\lVert\cdot\rVert_*$ is the dual norm — because $\inf_x(\lVert x\rVert - y^Tx) = 0$ when $\lVert y\rVert_* \le 1$ and $-\infty$ otherwise.
• The dual function is a conjugate. For $\min f_0(x)$ s.t. $Ax \preceq b,\ Cx = d$,

$g(\lambda,\nu) = -f_0^*(-A^T\lambda - C^T\nu) - b^T\lambda - d^T\nu,$

so once you know the conjugate $f_0^*$ (§3) the dual is automatic — e.g. entropy maximization plugs in $f_0^*(y) = \sum_i e^{y_i-1}$. The dual is the objective’s conjugate, evaluated at the constraint-transformed prices.

• Geometric interpretation — why duality works (the deep picture). Plot the achievable (constraint, objective) pairs $\mathcal G = \{(f_1(x), f_0(x)) : x \in \mathcal D\}$ in the $(u,t)$ plane (one inequality, for drawing). Then $p^\star = \inf\{t : (u,t)\in\mathcal G,\ u \le 0\}$, and the dual value is

$g(\lambda) = \inf_{(u,t)\in\mathcal G}\,(t + \lambda u),$

the lowest intercept of the line $\lambda u + t = g(\lambda)$ — a non-vertical supporting hyperplane of $\mathcal G$ with slope $-\lambda$, read where it crosses the $t$-axis ($u = 0$). Raising $\lambda \ge 0$ tilts the line up to the highest intercept $d^\star$. So: strong duality = there is a non-vertical supporting hyperplane to (the epigraph of) $\mathcal G$ at $(0, p^\star)$. For a convex problem that boundary is convex, so the hyperplane exists; and Slater — a point with $u < 0$ — is exactly what forces it to be non-vertical, closing the gap. The multipliers are the slopes of that supporting hyperplane, tying duality back to §2’s hyperplanes.

• Strong duality — the gap closes. $d^\star \le p^\star$ always (weak); $d^\star = p^\star$ (no gap) holds for convex problems under a constraint qualification — Slater’s: a strictly feasible point exists ($f_i(x) < 0$, equalities met). LPs have strong duality whenever feasible. Duality is bigger than convexity: some non-convex problems (the trust-region subproblem $\min x^TAx + 2b^Tx$ s.t. $x^Tx \le 1$, $A \not\succeq 0$) still have zero gap, and the dual of the non-convex two-way partitioning $\min x^TWx$ s.t. $x_i^2 = 1$ gives the bound $p^\star \ge n\lambda_{\min}(W)$ — a free certificate from an SDP dual.
• Complementary slackness — derive it. Assume strong duality, $x^\star$ and $(\lambda^\star,\nu^\star)$ optimal. Run the weak-duality chain at equality:

$f_0(x^\star) = g(\lambda^\star,\nu^\star) \le L(x^\star,\lambda^\star,\nu^\star) = f_0(x^\star) + \sum_i \lambda_i^\star f_i(x^\star) \le f_0(x^\star).$

Every "$\le$" is an equality, so $\sum_i \lambda_i^\star f_i(x^\star) = 0$; each term is $\le 0$, so each is zero: $\lambda_i^\star f_i(x^\star) = 0$. A constraint is either tight ($f_i = 0$) or unpriced ($\lambda_i = 0$).

• KKT conditions — certify. At a primal–dual optimum (with strong duality) all four hold: (1) primal feasibility $f_i(x)\le0,\ h_i(x)=0$; (2) dual feasibility $\lambda \succeq 0$; (3) complementary slackness $\lambda_i f_i(x)=0$; (4) stationarity $\nabla f_0(x) + \sum_i \lambda_i \nabla f_i(x) + \sum_i \nu_i \nabla h_i(x) = 0$. For convex problems the converse holds — KKT ⟹ optimal: stationarity makes $x$ minimize $L(\cdot,\lambda,\nu)$ so $g(\lambda,\nu) = L(x,\lambda,\nu)$, and CS makes $L(x,\lambda,\nu) = f_0(x)$; hence $f_0(x) = g(\lambda,\nu)$ and weak duality says $x$ is optimal. KKT is the optimality certificate solvers return.
• KKT in action — water-filling (the worked example to know cold). $\min -\sum_i \log(x_i + \alpha_i)$ s.t. $x \succeq 0,\ \mathbf 1^Tx = 1$ ($\alpha_i > 0$). Stationarity, dual feasibility, complementary slackness: $-\tfrac{1}{x_i + \alpha_i} - \lambda_i + \nu = 0$, $\lambda_i \ge 0$, $\lambda_i x_i = 0$. Casework on whether $x_i > 0$ collapses to

$x_i = \max\{0,\ 1/\nu - \alpha_i\}, \qquad \nu \text{ fixed by } \textstyle\sum_i \max\{0,\ 1/\nu - \alpha_i\} = 1.$

Picture: the $\alpha_i$ are floor heights of $n$ patches; pour one unit of water and it floods to a common level $1/\nu$ — patches poking above the waterline get $x_i = 0$. The dual variable $\nu$ is the water level. (This is how power is allocated across parallel communication channels.)

• Numeric anchor: $\alpha = (0.2,\ 0.5,\ 1.5)$. Try flooding all three patches, so $x_i = 1/\nu - \alpha_i$ and the budget $\sum_i x_i = 1$ reads $\sum_i(1/\nu - \alpha_i) = 1$. With $\sum_i\alpha_i = 2.2$ this is $3/\nu - 2.2 = 1$, so $3/\nu = 3.2$ and $1/\nu = 3.2/3 \approx 1.07$. But $1.07 < \alpha_3 = 1.5$ would give $x_3 < 0$ — patch 3 is above water; drop it and re-solve on $\{1,2\}$: $2/\nu - (0.2+0.5) = 1$, so $2/\nu = 1.7$ and $1/\nu = 0.85$. Now $0.85 < 1.5$ (3 stays dry) and $> 0.5, 0.2$ (1,2 wet). Allocation $x = (0.65,\ 0.35,\ 0)$, water level $1/\nu = 0.85$ — the active set found by the same drop-and-recheck the KKT casework prescribes.
• Sensitivity — price. Perturb the constraints to $f_i \le u_i$, $h_i = v_i$; the optimal value $p^\star(u,v)$ satisfies the local shadow-price relation

$\lambda_i^\star = -\frac{\partial p^\star}{\partial u_i}, \qquad \nu_i^\star = -\frac{\partial p^\star}{\partial v_i}.$

A big $\lambda_i^\star$ means tightening constraint $i$ hurts a lot; a slack constraint has $\lambda_i^\star = 0$ (CS, read as sensitivity). The multipliers are exactly the supporting-hyperplane slopes of §2.

Implications

• The four dividends are one idea: weak duality (bound) → strong duality (the bound is tight) → KKT (a checkable certificate) → shadow prices (what the constraints cost). This is the connective tissue of the whole field.
• Even for non-convex problems the dual gives a free lower bound and is convex — which is why hard combinatorial problems (two-way partitioning) get SDP-relaxation bounds from their duals.
• KKT specializes to everything you’ve seen: OLS normal equations, ridge, the lasso soft-threshold and its active-set $|\langle x_j, r\rangle| = \lambda$ (track 6), the SVM support vectors (track 6) — all are KKT systems.

Core competency set

• Write the Lagrangian and dual function; argue $g$ is concave; derive at least one worked dual (least-norm or LP) by “minimize out $x$, read off $g$.”
• State the dual-as-conjugate formula; draw the $\mathcal G$-set geometric interpretation and say what strong duality / Slater mean on it.
• Derive weak duality (the two-inequality chain) and complementary slackness (the sandwich).
• State the four KKT conditions, that KKT ⟺ optimal for convex problems, and solve water-filling; state the shadow-price reading of $\lambda^\star$.

6. Recognizing convex problems in the wild

The skill that makes the theory pay: take a messy real problem and reveal/transform it into a convex program in the hierarchy.

Maximum likelihood

• MLE maximizes $\ell(x) = \log p_x(y)$; it’s a convex problem whenever the log-likelihood is concave in the parameters. iid data factorizes it into a sum, $\ell(x) = \sum_i \log p(y_i - a_i^Tx)$ for the linear-measurement model $y_i = a_i^Tx + v_i$.
• Gaussian noise ⟹ $\ell \propto -\lVert Ax - b\rVert_2^2$ ⟹ MLE is least squares (a QP). The running example is the Gaussian MLE.
• Poisson counts ($y_i \sim \text{Pois}(a_i^Tx)$): $\ell(x) = \sum_i y_i \log(a_i^Tx) - \sum_i a_i^Tx$ — concave ($\log$ is), maximize s.t. $a_i^Tx \ge 0$.
• Logistic: $\ell(a,b) = y^T(Ua + b\mathbf 1) - \sum_i \log(1 + e^{a^Tu_i + b})$ — affine minus log-sum-exp, hence concave (track 6’s logistic regression, now seen as a convex program with a unique optimum). The ML-classification view: $\text{sign}(a^Tx_i+b) = y_i$ is non-convex, but maximizing the margin $y_i(a^Tx_i+b)$ and applying any nonincreasing convex $\phi$ gives the convex surrogate $\min \sum_i \phi(y_i(a^Tx_i+b))$ — $\phi(t)=\log(1+e^{-t})$ recovers logistic, the hinge recovers the SVM (track 6).

Norm approximation, regularization, and the dual’s residual story

• Choosing the norm in $\min\lVert Ax-b\rVert$ chooses the penalty on residuals, and the dual reveals where residuals concentrate. For the $L_1$ problem, the dual condition is $|\nu_i| \le 1$ with the minimizer of $|r_i| - \nu_i r_i$ forcing $r_i = 0$ unless $|\nu_i| = 1$ — so $L_1$ approximation drives many residuals exactly to zero (sparse residuals), the same KKT mechanism as lasso’s sparse coefficients (track 6). Penalty shape is a modeling decision: dead-zone ignores small errors, log-barrier forbids large ones.
• Regularized approximation is bi-objective $(\lVert Ax-b\rVert, \lVert x\rVert)$, scalarized to $\min \lVert Ax-b\rVert + \gamma\lVert x\rVert$; sweeping $\gamma>0$ traces the optimal tradeoff curve. Tikhonov $\lVert Ax-b\rVert_2^2 + \delta\lVert x\rVert_2^2$ is ridge (track 4), $\lVert\cdot\rVert_1$ regularization is lasso — the convex-optimization view of the penalty-as-prior dictionary (track 7).

Robust optimization — where duality earns its keep

• Data $A$ is uncertain in a set $\mathcal U$; worst-case robustness minimizes $\sup_{A\in\mathcal U}\lVert Ax-b\rVert$ — an infinite family of constraints, one per $u\in\mathcal U$. The constraint set is still convex (intersection of convex sets), but you make it solvable by dualizing the inner sup into a finite program.
• Robust LP stays an LP under box uncertainty. Require $(a+u)^Tx \le b$ for all $\lVert u\rVert_\infty \le \delta$; the binding case is the worst $u$, which maximizes $u^Tx = \sum_i u_i x_i$. The box decouples across coordinates, and each $|u_i| \le \delta$ independently picks $u_i = \delta\,\mathrm{sign}(x_i)$:

$\sup_{\lVert u\rVert_\infty \le \delta} u^Tx = \sum_i \sup_{|u_i|\le\delta} u_i x_i = \sum_i \delta|x_i| = \delta\lVert x\rVert_1.$

So the robust constraint is $a^Tx + \delta\lVert x\rVert_1 \le b$, still linear-representable: introduce $t_i$ with $-t_i \le x_i \le t_i$ and use $\delta\mathbf 1^Tt$ — the $L_1$ term epigraph-izes into an LP. For ellipsoidal uncertainty $u = Pz,\ \lVert z\rVert_2 \le 1$, the same sup is $\sup_{\lVert z\rVert_2\le1} z^TP^Tx = \lVert P^Tx\rVert_2$, so the constraint reads $a^Tx + \lVert P^Tx\rVert_2 \le b$ — a norm $\le$ affine, i.e. an SOCP (a general norm ball gives the dual norm $\lVert P^Tx\rVert_*$). Numeric feel: a manufacturing LP that loses most of its profit under a tiny data perturbation becomes, robustified, provably no worse than ~6% off the nominal optimum — a small price for guaranteed feasibility, bought entirely with the dual reformulation. Polyhedral uncertainty $\{u: Fu+g\succeq0\}$ needs the Lagrange dual of the inner max: $\sup_u\{x^Tu : Fu+g\succeq0\}$ becomes $\min\{\lambda^Tg : F^T\lambda + x = 0,\ \lambda\succeq0\}$, turning $\forall u$ into finitely many linear constraints.

• Robust LS = regularized LS. With $A = \bar A + U$, $U$ random mean-zero covariance $P$:

$E\lVert(\bar A + U)x - b\rVert_2^2 = \lVert\bar Ax - b\rVert_2^2 + x^TPx = \lVert\bar Ax-b\rVert_2^2 + \lVert P^{1/2}x\rVert_2^2.$

Robustness is Tikhonov regularization — and worst-case robust LS climbs to an SDP. The standing lesson: robustness moves you up the hierarchy (LP→SOCP→SDP), and duality is the vehicle.

Stochastic programming

• Objective/constraints depend on $x$ and a random $w$; minimize $F_0(x) = E\,f_0(x,w)$ s.t. $E\,f_i(x,w) \le 0$. If each $f$ is convex in $x$ for every $w$, then $F$ is convex (linearity of expectation preserves it) — a convex problem, though usually without closed form.
• Certainty equivalence ignores noise, using $w = E w$. Jensen bounds the error: $f_i(x, E w) \le E f_i(x, w)$ for $f_i$ convex in $w$ — the mean-field problem under-states the true (stochastic) optimum.
• Chance/violation constraints: replace "$E f_i \le 0$" with $\text{Prob}(f_i(x,w) \le 0) \ge \eta$ or a penalty on the violation $E(\max_i f_i)_+ \le \epsilon$ — sometimes convex (SOCP for Gaussian linear constraints).
• Monte Carlo sample-average approximation $\hat F_i(x) = \sum_j \pi_j f_i(x, w_j)$ replaces the expectation by samples. Solution and value are random; as $N\to\infty$ they converge — but with a downward (optimistic) bias, $E\,\hat F_0(x^\star_{\text{mcs}}) \le p^\star$, since $E[\min] \le \min[E]$. Validate out of sample (the firewall principle, track 6).

Optimal detector & experiment design (vector/SDP applications)

• Detector design: choose a randomized detector $T$ (columns are choice probabilities) to trade off false-positive vs false-negative rates — a vector objective; scalarize by $\lambda$ and recover the Neyman–Pearson likelihood-ratio test analytically, or minimize the worst error as an LP.
• Experiment design: $m$ noisy measurements $y_i = a_i^Tx + w_i$ give estimator error covariance $E = (\sum_i a_i a_i^T)^{-1}$; choosing the $a_i$ to make $E$ “small” (in the $\preceq_{S^n_+}$ order) is an SDP — diversity of measurements (a larger $\sum a_ia_i^T$) shrinks the error.

Implications

• Every application is the same move: find the convex program underneath, then place it on the hierarchy. MLE concavity, regularization-as-prior, and robust-LS-as-Tikhonov all unify stats/ML methods you met elsewhere under one optimization roof.
• Duality is not just theory: it’s the concrete tool that converts a sup-over-uncertainty (infinite constraints) into a finite SOCP/SDP — the workhorse of robust optimization.

Core competency set

• Show Gaussian/Poisson/logistic MLE are concave and place each in the hierarchy; give the margin-surrogate view of classification.
• Explain the $L_1$ dual’s sparse-residual story and regularization-as-scalarization (ridge/lasso/Tikhonov).
• Derive robust-LP-box → $\delta\lVert x\rVert_1$ and robust-LS → Tikhonov; state “robustness climbs the hierarchy via duality.”
• State certainty-equivalence (Jensen bound) and the MC downward bias.

7. Memorize cold

• Convex set: segment stays in; convex function: chords above, $f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$.
• Local = global for convex (segment-contradiction proof); FOC global underestimator $f(y) \ge f(x) + \nabla f(x)^T(y-x)$; SOC $\nabla^2 f \succeq 0$.
• Epigraph bridge: $f$ convex $\iff$ epi $f$ convex; minimize-$t$-s.t.-$f\le t$ reformulation.
• Convexity-preserving ops (functions): nonneg sum, affine precomp, pointwise sup (epigraph intersection), composition rule, partial min (jointly convex), perspective, conjugate $f^*(y)=\sup_x(y^Tx - f(x))$.
• Affine/convex/conic = the $\theta$ knob (sum-1 any-sign / sum-1 nonneg / nonneg). Zoo: halfspace, ellipsoid $\{x_c + Au\}$, norm cone, polyhedron, PSD cone $\{z^TXz\ge0\}$.
• Convexity-preserving ops (sets): intersection (even infinite), affine image/preimage, perspective $x/t$, linear-fractional. Separating hyperplane (disjoint convex → $a$ separates); supporting hyperplane (convex → one at every boundary point) = the seed of duality.
• Proper cone (convex/closed/solid/pointed) → $\preceq_K$ (not total); dual cone $K^* = \{y: y^Tx\ge0\,\forall x\in K\}$; $\mathbb R^n_+, S^n_+$ self-dual, $(L_1,L_\infty)$ dual. Minimum (beats all; unique-min of every $\lambda^Tz$) vs minimal (nothing below; minimizes some $\lambda^Tz$) → scalarization/Pareto.
• Hierarchy LP ⊂ QP/QCQP ⊂ SOCP ($\lVert Ax+b\rVert_2 \le c^Tx+d$) ⊂ SDP ($\sum x_iF_i \preceq G$); GP convex after $\log$; quasiconvex by bisection.
• LP gems: piecewise-linear $\min\max_i(a_i^Tx+b_i)$ → epigraph → LP; Chebyshev center $a_i^Tx_c + r\lVert a_i\rVert_2 \le b_i$. QP gems: least squares = unconstrained QP; Markowitz $\min \bar c^Tx + \gamma x^T\Sigma x$. SDP: $\lambda_{\max}(A) \le t \iff A \preceq tI$; LP/SOCP as SDP via diag / Schur.
• Optimality (diff’able): $\nabla f_0(x)^T(y-x) \ge 0\ \forall$ feasible $y$; unconstrained $\nabla f_0 = 0$.
• Lagrangian $L = f_0 + \sum\lambda_i f_i + \sum\nu_i h_i$; dual $g = \inf_x L$ is concave always; $g = -f_0^*(-A^T\lambda - C^T\nu) - b^T\lambda - d^T\nu$ (dual = conjugate). Worked: least-norm $g(\nu) = -\tfrac14\nu^TAA^T\nu - b^T\nu$; LP dual is an LP $\max -b^T\nu$ s.t. $A^T\nu + c \succeq 0$; norm-min needs $\lVert A^T\nu\rVert_* \le 1$.
• Weak duality $g(\lambda,\nu) \le p^\star$ (always); strong $d^\star = p^\star$ under Slater (strict feasibility); gap $p^\star - d^\star$. Geometric: $g(\lambda)$ = $t$-intercept of a non-vertical supporting hyperplane (slope $-\lambda$) of $\mathcal G = \{(f_1, f_0)\}$; strong duality = such a hyperplane at $(0, p^\star)$, Slater forces non-vertical.
• Complementary slackness $\lambda_i^\star f_i(x^\star) = 0$ (tight or unpriced). KKT = primal feas + dual feas + CS + stationarity $\nabla f_0 + \sum\lambda_i\nabla f_i + \sum\nu_i\nabla h_i = 0$; for convex problems KKT ⟺ optimal. Water-filling: $x_i = \max\{0, 1/\nu - \alpha_i\}$, $\nu$ = water level.
• Shadow price $\lambda_i^\star = -\partial p^\star/\partial u_i$.
• MLE concave ⟹ convex: Gaussian→LS, Poisson, logistic (affine − log-sum-exp); margin surrogate $\min\sum\phi(y_i(a^Tx_i+b))$.
• Robust LP box → $a^Tx + \delta\lVert x\rVert_1 \le b$; norm-ball → dual-norm SOCP; robust LS = Tikhonov $\lVert\bar Ax-b\rVert^2 + \lVert P^{1/2}x\rVert^2$; robustness climbs the hierarchy via duality.
• Certainty equivalence Jensen bound $f(x,Ew)\le Ef(x,w)$; MC downward bias $E[\min]\le\min[E]$.

Named moves (cross-track glossary): local-is-global (the watershed); build-don’t-check (convexity calculus of atoms + operations); epigraph-bridge (sets↔functions, minimize-$t$); recognize-the-class then transform-down the hierarchy; price-the-constraints (Lagrangian); inf-of-affine-is-concave (dual function); dual-is-a-conjugate; supporting-hyperplane-of-the-$\mathcal G$-set (the geometric why of duality); weak-duality-bound then close-under-Slater; the-sandwich (complementary slackness); water-fill (KKT casework); KKT-as-certificate (and KKT-systems behind OLS/ridge/lasso/SVM — tracks 4, 6); shadow-price (sensitivity); scalarize-the-vector-objective (regularization, detector design); dualize-the-inner-sup (robust optimization, infinite → finite); robustness-climbs-the-hierarchy.