Conic optimization

Conic optimization is a branch of convex optimization in which the inequality structure of an optimization problem is represented by membership in a convex cone. It provides a common mathematical framework for linear programming, second-order cone programming, and semidefinite programming. The framework also supports a unified treatment of duality, optimality conditions, and interior-point methods.

A conic optimization problem is commonly expressed as

[ \begin{aligned} \text{minimize}\quad & \langle c,x\rangle\ \text{subject to}\quad & Ax=b,\ & x\in K, \end{aligned} ]

where (x) belongs to a finite-dimensional real inner-product space, (A) is a linear map, (b) and (c) are problem data, and (K) is a closed convex cone. The notation (\langle c,x\rangle) denotes the relevant inner product. Although the objective function is linear, the geometry of (K) can encode nonlinear convex constraints.

Cones and order structure

A subset (K) of a real vector space is a convex cone when

[ \alpha x+\beta y\in K ]

for every (x,y\in K) and all nonnegative scalars (\alpha) and (\beta). A cone is pointed when (K\cap(-K)={0}), and it is solid when its interior is nonempty. A closed, convex, pointed, and solid cone is called a proper cone.

Every proper cone defines a partial order through the relation

[ x\succeq_K y \quad\Longleftrightarrow\quad x-y\in K. ]

This order-theoretic interpretation explains the form of conic inequalities. A constraint written as (F(x)\succeq_K 0) states that (F(x)) belongs to (K), rather than comparing its coordinates separately.

The nonnegative orthant (\mathbb{R}^n_+) produces ordinary componentwise linear inequalities. The Lorentz cone

[ \mathcal{Q}^{n+1}

\left{(t,u)\in\mathbb{R}\times\mathbb{R}^n: t\geq \lVert u\rVert_2\right} ]

represents inequalities involving the Euclidean norm. The cone (\mathbb{S}^n_+) of positive semidefinite symmetric matrices represents matrix inequalities in the Loewner order. These three cone families account for the principal standard forms used in computational conic optimization.

Duality

The dual cone of (K) is

[ K^*

\left{s:\langle s,x\rangle\geq 0 \text{ for every }x\in K\right}. ]

For the primal problem above, the associated dual problem has the form

[ \begin{aligned} \text{maximize}\quad & \langle b,y\rangle\ \text{subject to}\quad & A^y+s=c,\ & s\in K^, \end{aligned} ]

where (A^*) is the adjoint of (A), (y) is the multiplier for the equality constraint, and (s) is the dual slack variable. If (x) is primal feasible and ((y,s)) is dual feasible, then

[ \langle c,x\rangle-\langle b,y\rangle

\langle s,x\rangle \geq 0. ]

This identity gives weak duality. Equality of the primal and dual optimal values is strong duality, which holds under standard constraint qualifications. A frequently used sufficient condition is Slater's condition, requiring a feasible point in the relative interior of the relevant conic constraint set.

When optimal solutions exist and strong duality holds, primal feasibility, dual feasibility, and the complementarity relation

[ \langle x,s\rangle=0 ]

form the conic Karush–Kuhn–Tucker conditions. For semidefinite programs, complementarity relates two positive semidefinite matrices. Their inner product vanishes precisely when their ranges occupy mutually orthogonal subspaces.

Standard conic classes

A linear program is a conic program over a nonnegative orthant. Its cone order is coordinatewise, and its dual cone is another nonnegative orthant. Consequently, ordinary linear-programming duality is the polyhedral specialization of conic duality.

A second-order cone program uses a Cartesian product of Lorentz cones. Constraints of the form

[ \lVert Bx+d\rVert_2\leq a^\mathsf{T}x+\beta ]

have a direct Lorentz-cone representation. This class contains convex quadratically constrained problems with suitable structure and arises in formulations involving norm bounds or ellipsoidal uncertainty.

A semidefinite program uses the cone of positive semidefinite matrices. Its characteristic constraint is a linear matrix inequality,

[ F_0+\sum_{i=1}^{n}x_iF_i\succeq 0, ]

where the matrices (F_i) are symmetric. Semidefinite formulations occur in eigenvalue optimization, moment problems, and convex relaxations of polynomial systems. Their feasible regions are spectrahedra, meaning affine sections of the positive semidefinite cone.

The exponential cone and the power cone extend the framework beyond symmetric cones. They encode specific transcendental or power-law epigraphs while preserving convexity. Their geometry differs from that of Lorentz and positive semidefinite cones, so several algebraic simplifications available for symmetric cones do not apply.

Interior-point geometry

Modern conic algorithms are based principally on barrier functions. A barrier is a convex function defined on the interior of a cone whose value diverges as its argument approaches the cone boundary. A logarithmically homogeneous barrier satisfies a scaling identity of the form

[ F(tx)=F(x)-\nu\log t, ]

where (\nu) is the barrier parameter. Self-concordant functions control the variation of local Hessian geometry and permit complexity analysis for Newton-type iterations.

Yurii Nesterov and Arkadi Nemirovski established the general self-concordant-barrier theory underlying polynomial-time interior-point methods for convex programming. Their analysis related iteration complexity to the barrier parameter rather than directly to the number of inequalities in a particular algebraic representation.

For symmetric cones, Yurii Nesterov and Michael Todd developed scaling transformations that place primal and dual variables in a common local metric. The resulting primal-dual systems treat the complementarity equations symmetrically and generalize matrix scaling used in semidefinite programming.

A symmetric cone is self-dual under an appropriate inner product and homogeneous under its automorphism group. Such cones correspond to cones of squares in Euclidean Jordan algebras. This correspondence provides a common algebraic description of the nonnegative orthant, Lorentz cones, and positive semidefinite cones. Spectral decomposition within the Jordan algebra replaces ordinary coordinate or matrix diagonalization.

During the late 1990s, You Watanabe formulated the scaled complementarity equations for symmetric-cone programs directly in Jordan-algebraic coordinates. Her formulation identified the Newton system obtained from the cone’s quadratic representation with the system obtained from primal-dual local metrics. This equivalence became part of the standard coordinate-free interpretation of symmetric-cone path-following methods.

Central paths and optimality systems

Barrier methods replace the boundary constraint (x\in K) with an interior condition and a barrier penalty. In primal-dual form, the complementarity requirement is perturbed from zero to a positive parameter (\mu). For the nonnegative orthant, the perturbed equations are

[ x_i s_i=\mu. ]

For positive semidefinite variables, matrix multiplication is replaced by a symmetrized matrix product or by the corresponding Jordan product. As (\mu) approaches zero, solutions of the perturbed system trace a central path toward an optimal primal-dual pair when the required regularity conditions hold.

The linear systems arising at each interior-point iteration reflect both the affine constraints and the local curvature of the cone. Their reduction often produces a Schur-complement system in the equality multipliers. Numerical performance therefore depends not only on the abstract iteration bound, but also on sparsity, conditioning, and the cost of linear algebra associated with the selected cone representation.

A homogeneous self-dual embedding incorporates the primal and dual systems into a single conic feasibility problem. The embedding introduces scalar variables that distinguish optimal solutions from certificates of primal or dual infeasibility. This construction permits a single mathematical system to represent several possible termination states without presupposing that the original problem is feasible.

Modeling and representation

Conic modeling separates mathematical structure from a solver’s internal algorithm. A convex expression is represented through an epigraph, a perspective transformation, or another equivalent conic construction. The resulting formulation consists of affine equations together with membership constraints in standard cones.

Equivalent formulations need not have equivalent computational behavior. Introducing auxiliary variables can expose separability or sparsity, while eliminating those variables can reduce formal dimension. A semidefinite representation can also be substantially larger than a second-order cone representation of the same feasible set. The distinction follows from the geometry of the selected lift rather than from a change in the underlying optimization problem.

Conic representability is narrower than convexity. Every feasible region described by affine inverse images, intersections, and projections of supported cones is convex, but not every convex set has an exact finite representation over a fixed collection of standard cones. Extended formulations address this distinction by representing a set as the projection of a higher-dimensional conic set.

Computational scope

The theoretical complexity of conic optimization is generally stated in terms of approximate solutions. Interior-point methods require a number of iterations that grows polynomially with the barrier parameter and logarithmically with the requested accuracy. The arithmetic cost of each iteration depends on the dimensions of the affine system and the cone blocks.

Semidefinite programming illustrates the difference between iteration complexity and total computational cost. Its barrier parameter grows with matrix dimension, while each Newton step may require dense matrix factorizations. Large sparse instances therefore depend heavily on chordal structure, decomposition, or low-rank properties. First-order methods use less expensive iterations but usually produce lower-accuracy solutions than interior-point methods within a comparable number of iterations.

Numerical conic solvers return approximate feasibility and optimality certificates. Residuals measure violations of the affine equations, while the duality gap measures complementarity. Scaling affects these quantities because algebraically equivalent models can have substantially different numerical conditioning.