Optimization¶
Job: minimize objectives over feasible sets; exploit convex structure where local minima are global; deploy first-order conditions, duality, and algorithms with rates.
Core¶
Optimization is decision under constraints: \(\min_{x\in X} f(x)\). Convexity turns stationarity into global optimality and yields strong duality under constraint qualifications. Nonconvex problems need second-order tests, landscape analysis, or global methods (branch-and-bound, multistart).
| Layer | Content |
|---|---|
| Unconstrained | \(\nabla f=0\), Hessian tests; smooth rates |
| Convex analysis | epigraphs, subdifferentials, projections |
| Constrained | KKT, LICQ/MFCQ/Slater; Lagrangian duality |
| Structured | LP/QP/SDP; composite nonsmooth (\(f+g\)) |
| Algorithms | GD, proximal, Newton, interior-point |
| Variational | VI, monotone operators (pointer) |
Reading map¶
| Page | Focus |
|---|---|
| Foundations | convex sets/functions; KKT; duality; LP; first-order rates |
| Conic & SDP | LP/SOCP/SDP, Lovász theta, Goemans–Williamson, interior-point |
| Nonconvex & Landscape | strict saddle escape, NTK/lazy, annealing |
| Variational & Monotone | VI, maximal monotone, proximal point, ADMM |
| Online & Stochastic | OCO/regret, FTRL, SGD, bandit/UCB |
Dependency order¶
- Multivariable calculus + linear algebra (linear algebra)
- Foundations
- Numerical analysis for implementation stability
- Applications: ML training, control, game theory saddles
Where it appears¶
- Numerical analysis: Newton, Krylov, conditioning of KKT systems
- Game theory: zero-sum as \(\min\max\); variational inequalities
- Statistics / ML: MLE, empirical risk, regularized estimators
- PDE / calculus of variations: energy minimization
Signature results¶
| Result | Content |
|---|---|
| Convex local \(\Rightarrow\) global | \(f\) convex on convex \(C\) |
| KKT necessity | under CQ (LICQ, MFCQ, …) at local min |
| KKT sufficiency | convex data + KKT \(\Rightarrow\) global min |
| Strong duality | convex problem + Slater-type conditions |
| Smooth GD rates | \(O(1/k)\) convex smooth; linear if strong convex |
See it¶
Nonnegative least squares. \(\min\frac12\|Ax-b\|_2^2\) s.t. \(x\ge0\). KKT: \(A^\top(Ax-b)-\lambda=0\), \(\lambda\ge0\), \(\lambda\odot x=0\). Complementarity encodes the active set; coordinate descent and active-set QP solvers exploit the structure.
Support vector machines (pointer). Soft-margin SVM is a convex QP; dual is sparse in support vectors — textbook strong duality + complementary slackness in ML.
Check¶
Why is a constraint qualification needed for KKT necessity?
Without CQ, Lagrange multipliers for the constraints may fail to exist even at a genuine local min (Fritz John conditions allow a vanishing multiplier on \(\nabla f\)). LICQ/MFCQ/Slater restore nontrivial multipliers.
When is \(\operatorname{argmin} f\) a convex set?
If \(f\) is convex (on a convex domain), the argmin set is convex (possibly empty). Strict convexity \(\Rightarrow\) at most one minimizer.
Pitfalls¶
- KKT points of nonconvex problems include saddles; need SOSC / landscape analysis.
- Duality gap without convexity or Slater.
- Differentiating through argmin needs implicit-function or Danskin hypotheses (uniqueness).
- Confusing stationarity with global optimality outside convexity.
Refs¶
Boyd–Vandenberghe, Convex Optimization; Nocedal–Wright; Rockafellar, Convex Analysis; Bertsekas; Nesterov, Introductory Lectures.
Next¶
Foundations · Numerical analysis · Linear algebra · Game theory · Calculus · Conic & SDP · Nonconvex & Landscape · Variational & Monotone · Online & Stochastic