Conic optimization

Optimization of a linear function subject to affine constraints and membership in a closed convex cone. Choosing the positive semidefinite cone gives semidefinite programming; other choices include copositive optimization and completely positive optimization. Dual cones produce scalar-product bounds on feasible objectives.

An interior-point method solves constrained mathematical optimization problems by maintaining variables in the interiors of their feasible cones or inequality domains. Barrier derivatives are defined there, and damped Newton methods keep subsequent iterates in their domains. A central path gives a family of barrier-regularized optima whose duality gap approaches zero; a conic phase-I problem can supply a strict feasible starting point.

An auxiliary conic optimization problem searches for strict feasibility before following a central path. Given $e\in \mathrm{int}K$, minimizing $t$ subject to $Ax-b+te\in K$ and $t\ge -1$ has a strict feasible start for sufficiently large $t$. Any feasible solution with $t<0$ certifies $Ax-b\in \mathrm{int}K$. If the original problem is strictly feasible, a small negative $t$ is feasible. Equality constraints and dual feasibility require their corresponding auxiliary procedures.

A convex three-times differentiable barrier $F$ is self-concordant whenA barrier of parameter $\nu$ additionally satisfies $|DF(x)[h]|\le \sqrt{\nu D^{2}F(x)[h,h]}$ and diverges at the domain boundary. Logarithmically homogeneous cone barriers satisfy $F(tx)=F(x)-\nu \log t$. The orthant barrier $-{\sum }_i\log x_i$ has parameter equal to the dimension, while the Lorentz-cone barrier $-\log (t^2-\Vert z{\Vert }^2)$ on $t>\Vert z\Vert$ has parameter two. Their Hessians define Dikin ellipsoids and control interior Newton steps.

For a nondegenerate self-concordant barrier, the open local Hessian ballis contained in its barrier domain. This is the Dikin ellipsoid. It supplies a quantitative way to ensure that a damped Newton method stays interior, without relying on Euclidean distance to a possibly curved boundary.

For a strictly feasible primal-dual conic optimization problem and a logarithmically homogeneous barrier, the central path consists of solutionsThe primal-dual gap is $⟨s,y⟩=\nu \mu$. Existence requires appropriate feasibility and boundedness hypotheses, rather than merely a full-rank constraint matrix. Linearizing these equations gives a central-path Newton system.

At a target barrier parameter $\mu$, let $r_p=Ax-b-s$, $r_d=A^{\top }y-c$, $r_c=y+\mu \nabla F(s)$. The Newton direction solvesFull column rank of $A$ and a positive-definite barrier Hessian give a positive-definite reduced matrix. Backtracking must keep both cone variables interior; solving the linear equations alone does not guarantee that a full step stays inside the cones.

For ${\min }_x{c}^{\top }x$ subject to $Ax-b\in K$, the Lagrangian dual problem is ${\max }_y{b}^{\top }y$ subject to $A^{\top }y=c$ and $y\in K^{\ast }$. At feasible primal-dual points, the gap is $⟨Ax-b,y⟩\ge 0$. A self-dual cone has $K^{\ast }=K$, but self-duality alone does not imply feasibility or strong duality.

Conic optimization using the completely positive cone. For a real symmetric matrix $Q$, the trace-normalized program $\min \{⟨Q,X{⟩}_F:X\in {\mathrm{CP}}_n,\mathrm{tr}X=1\}$ minimizes a weighted average of nonnegative-unit-vector Rayleigh quotients. The weights are the squared norms of the factors in $X={\sum }_j{x}_j{x}_j^T$. Hence a minimizing rank-one factor attains the same value as the original orthant minimum.

Conic optimization using the copositive cone. The constraint $Q-\lambda I\in {\mathrm{COP}}_n$ supplies an exact reformulation of a Rayleigh quotient minimum on the nonnegative orthant. Exact conic formulation does not itself provide an efficient membership algorithm.

Let $\alpha =\min \{x^{T}Qx:x\ge 0,\Vert x{\Vert }_2=1\}$ for a real symmetric matrix $Q$. Compactness gives attainment. Homogeneity shows $Q-\lambda I$ is a copositive matrix exactly when $\lambda \le \alpha$, provingIts conic program dual is the trace-normalized completely positive optimization problem. A minimizing vector gives $X=x{x}^T$, which certifies equality and dual attainment directly. In general $\alpha$ differs from the unrestricted smallest eigenvalue.