Conic Programming

Optimization · Axiom Academy

Understanding optimization over cones: from linear to semidefinite programming 1. Cones and Conic Constraints A cone is a set K that is closed under positive scaling: if x is in K, then so is tx for all t greater than or equal to 0. A convex cone is additionally closed under addition. Three fundamental cones form a hierarchy of increasing expressiveness: Nonnegative Orthant: The set of vectors with all nonnegative components. Constraints over this cone yield linear programs. Second-Order Cone (Lorentz Cone): Vectors where the last component dominates the Euclidean norm of the remaining components. This generalizes LP to SOCP. Positive Semidefinite Cone: Symmetric matrices with all nonnegative eigenvalues. This leads to semidefinite programs, the most expressive class. 3. Second-Order Cone Programming SOCP constraints have the elegant form: the norm of Ax + b is less than or equal to c transpose x + d. This generalizes linear constraints by allowing quadratic terms under the norm. SOCPs can model robust optimization, portfolio optimization with risk constraints, and many engineering design problems involving worst-case analysis. SDP optimizes over the cone of positive semidefinite matrices, typically written as X succeeds or equals 0, meaning X is symmetric and all eigenvalues are nonnegative. Equivalently, X is PSD if z transpose X z is greater than or equal to 0 for all vectors z. This powerful constraint allows modeling matrix variables with structural requirements.

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