Optimization — Foundations¶

Job: State first-order optimality; develop convex analysis and Lagrangian duality; apply KKT conditions under constraint qualifications; orient rates for first-order methods.

Core¶

Problem classes¶

Problem: $\min_{x\in X} f(x)$ with $X=\{x:g_i(x)\le0,\ h_j(x)=0\}$ (or abstract closed $X$).

Class	Feature
Unconstrained smooth	$\nabla f=0$, Hessian tests
Convex	local min $\Rightarrow$ global; duality
LP / QP / SDP	polyhedral / cone structure; strong duality regimes
Composite	$\min f+g$ with $g$ nonsmooth (prox)
Nonconvex	KKT necessary only; saddles abound

Unconstrained optimality¶

$f\in C^1$: $\nabla f(x_*)=0$ necessary for local min. $C^2$: $\nabla^2 f(x_*)\succeq0$ necessary; $\nabla^2 f(x_*)\succ0$ sufficient for strict local min. Descent lemma for $L$-smooth $f$: $f(y)\le f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\|y-x\|^2$.

Convex analysis¶

Convex set $C$: $x,y\in C\Rightarrow[x,y]\subset C$. Convex function: $f(tx+(1-t)y)\le tf(x)+(1-t)f(y)$. Epigraph convex $\Leftrightarrow$ $f$ convex. Subdifferential $$ \partial f(x)={v:f(y)\ge f(x)+\langle v,y-x\rangle\ \forall y}. $$ $0\in\partial f(x_*)\Leftrightarrow x_*$ global minimizer for convex $f$. For $f\in C^1$, $\partial f=\{\nabla f\}$. Jensen: $f(\mathbb{E}X)\le\mathbb{E}f(X)$.

Projection onto closed convex $C\subset$ Hilbert: firmly nonexpansive; VI characterization $\langle x-P_C x,y-P_C x\rangle\le0$ $\forall y\in C$.

Fenchel conjugate $f^*(y)=\sup_x\langle y,x\rangle-f(x)$; biconjugate $f^{**}=f$ iff $f$ closed convex (proper). Fenchel–Rockafellar duality under qualification conditions.

Lagrangian duality and KKT¶

Lagrangian: $L(x,\lambda,\nu)=f(x)+\sum\lambda_i g_i(x)+\sum\nu_j h_j(x)$, $\lambda\ge0$. Dual $g(\lambda,\nu)=\inf_x L$. Weak duality: $\inf f\ge\sup g$.

KKT (necessary). At local min $x_*$, under a CQ (LICQ: active $\nabla g_i,\nabla h_j$ lin. ind.; or MFCQ, Slater for convex), $\exists\lambda,\nu$ with \begin{align} \nabla_x L(x_,\lambda,\nu)&=0,\ \lambda_i&\ge0,\quad \lambda_i g_i(x_)=0,\ g_i(x_)&\le0,\quad h_j(x_)=0. \end{align} Sufficient: $f,g_i$ convex, $h_j$ affine, KKT $\Rightarrow$ global min. Strong duality under Slater: exists $x$ with $g_i(x)<0$ (and $h=0$) for convex inequalities.

Fritz John: without CQ, multipliers $(\lambda_0,\lambda,\nu)\neq0$ with $\lambda_0\nabla f+\cdots=0$, $\lambda_0\ge0$ — $\lambda_0=0$ marks degeneracy.

Linear programming¶

Polyhedral feasible sets; optima at vertices (if attained). Strong duality when either problem is feasible and bounded. Primal-dual: complementary slackness. Simplex vs interior-point: combinatorial vs polynomial self-concordant path-following (Nesterov–Nemirovski).

First-order algorithms¶

Method	Setting	Rate (schematic)
GD step $1/L$	$L$-smooth convex	$f(x_k)-f_*=O(1/k)$
GD	$\mu$-strongly convex smooth	linear $(1-\mu/L)^k$
Nesterov accelerated	smooth convex	$O(1/k^2)$
Proximal gradient	$f$ smooth + $g$ prox-friendly	analogous
Projected GD	smooth over simple convex $C$	same as GD on constrained

Prox $\operatorname{prox}_{t g}(x)=\arg\min_y g(y)+\frac1{2t}\|y-x\|^2$. Mirror descent / conditional gradient (Frank–Wolfe) for structured domains.

Newton / quasi-Newton: local quadratic; BFGS; interior-point Newton on central path for conic programs.

Second-order sufficiency (nonconvex)¶

At KKT point with LICQ: LICQ + strict complementarity + $Z^\top\nabla_{xx}^2 L Z\succ0$ on tangent to active set (SOSC) $\Rightarrow$ strict local min.

See it¶

$\min \frac12\|Ax-b\|_2^2$ s.t. $x\ge0$. Stationarity: $A^\top(Ax-b)-\lambda=0$, $\lambda\ge0$, $\lambda\odot x=0$. Equivalent to KKT for nonnegative least squares; active-set / coord-descent methods exploit complementarity.

SVM dual (pointer): soft-margin SVM QP dual is sparse (support vectors); strong duality + complementary slackness select the geometric margin solution.

Check¶

Why is LICQ needed for KKT necessity?

Without CQ, multipliers may fail to exist (textbook degeneracies). Fritz John adds a multiplier on $\nabla f$ that can vanish, giving little information.

Convex $f$ can have multiple minimizers — when is the set of minimizers convex?

Always: argmin of a convex function on a convex set is convex (possibly empty). Strict convexity $\Rightarrow$ at most one minimizer.

Why does GD with fixed step $>2/L$ diverge for $L$-smooth convex $f$?

Descent lemma / gradient Lipschitz: the map $x\mapsto x-\eta\nabla f(x)$ is not guaranteed nonexpansive / descent for $\eta>2/L$; quadratic $f(x)=\frac{L}{2}x^2$ oscillates or diverges for large $\eta$.

Pitfalls¶

Nonconvex landscapes: KKT points include saddles; need SOSC / landscape analysis.
Duality gap without convexity/Slater.
Differentiating through argmin needs implicit function / Danskin under uniqueness.
Confusing stationarity with global optimality.
“Convex optimization is easy” — polynomial in theory; structure and conditioning dominate practice.

Refs¶

Boyd–Vandenberghe, Convex Optimization; Nocedal–Wright; Rockafellar, Convex Analysis; Bertsekas; Nesterov, Introductory Lectures on Convex Optimization.

Next¶

Index · Numerical analysis · Linear algebra · Game theory · Calculus · ML mathematics — non-convex optimization landscapes of neural networks; NTK / lazy training · Conic & SDP · Nonconvex & Landscape · Variational & Monotone · Online & Stochastic