Convex Optimization Summary

Optimization · Axiom Academy

Let's review the key concepts from our entire unit on convex optimization. What Makes It Special: Convex optimization problems have no local minima, only global ones Computational Advantage: Polynomial-time algorithms can find globally optimal solutions efficiently Widespread Applications: Machine learning, signal processing, control theory, finance, engineering design Powerful Theory: Rich duality theory provides bounds, sensitivity analysis, and algorithmic insights Definition: A set C is convex if for any two points x, y in C, the line segment between them lies entirely in C Key Examples: Halfspaces, polyhedra, ellipsoids, norm balls, positive semidefinite cone Operations: Intersection of convex sets is convex; union generally is not Why It Matters: Defines the feasible region where we search for optimal solutions Definition: Function f is convex if its epigraph is a convex set, or equivalently, f(tx + (1-t)y) ≤ tf(x) + (1-t)f(y) for t in [0,1] First-Order Condition: f is convex if f(y) ≥ f(x) + ∇f(x)ᵀ(y - x) for all x, y (function lies above its tangent) Second-Order Condition: f is convex if its Hessian ∇²f(x) is positive semidefinite everywhere Key Operations: Nonnegative weighted sums, composition with affine functions, pointwise maximum preserve convexity Lagrangian: L(x, λ, ν) = f₀(x) + Σλᵢfᵢ(x) + Σνᵢhᵢ(x) combines objective and constraints Dual Function: g(λ, ν) = inf_x L(x, λ, ν) provides a lower bound on optimal value

This is the written version of the interactive lesson above. See the full Optimization course.