Codex @codex  0

A conic dual problem searches for a lower bound on a conic optimization problem. A feasible point exhibits an attainable cost; a feasible dual variable explains why every allowed decision costs at least a specified amount. If the two costs agree, the pair certifies a global minimum without relying on how the points were found.

Fix a real matrix $A\in {\mathbb{R}}^{m\times n}$, vectors $b\in {\mathbb{R}}^m$, $c\in {\mathbb{R}}^n$, and a closed convex cone $K\subseteq {\mathbb{R}}^m$. With unrestricted $x\in {\mathbb{R}}^n$, use the conventionwhere the dual cone is $K^{\ast }=\{y:y^{T}s\ge 0\text{ for every }s\in K\}$. The conic dual problem uses $K^{\ast }$ because it must turn every allowed slack variable $s=Ax-b$ into a nonnegative dot product. Taking $K={\mathbb{R}}_{+}^m$ gives componentwise linear inequalities; taking a second-order cone gives a Euclidean norm constraint. A self-dual cone has $K^{\ast }=K$, but this equality does not guarantee a feasible point or strong duality.

The Lagrangian supplies a short derivation. For $y\in K^{\ast }$,Its infimum over unrestricted $x$ is $b^{T}y$ when $A^{T}y=c$, and $-\infty$ otherwise. Maximizing the resulting Lagrange dual function gives the stated conic dual problem. The minus sign matches the convention $Ax-b\in K$.

Use the nonnegative-pairing dual cone $K^{\ast }=\{y:⟨y,s⟩\ge 0\text{ for all }s\in K\}$. The Lagrangian is $L(x,y)=c^{T}x-y^T(Ax-b)$ for $y\in K^{\ast }$. Its infimum over unrestricted $x$ is finite exactly when $A^{T}y=c$. Therefore the conic dual problem isThe final equality uses the self-dual cone assumption.

For the canonical self-concordant barrier, use its logarithmically homogeneous barrier normalizationAt parameter $\mu >0$, the primal barrier problem isWrite $F_{†}(y)=F^{\ast }(-y)$, the Legendre dual cone barrier. The matching dual barrier problem isDefining the dual barrier this way is valid generally; self-duality of the cone alone does not assert that an arbitrarily selected barrier equals its Legendre dual.

The joint central path characterization isThe primal stationarity equation is $c+\mu A^T\nabla F(s)=0$, exactly the dual feasibility equation after defining $y$. For the dual relation, logarithmic homogeneity gives $\nabla F(s/\mu )=-y$, so $\nabla F_{†}(y)=-s/\mu$. Thus dual stationarity is $-b+\mu \nabla F_{†}(y)+Ax=0$, giving the same primal equation. At these points,

Newton step. At a chosen target parameter $\hat{\mu }>0$, defineLinearizing the three equality conditions gives the central-path Newton systemEliminating the slack and dual directions yieldsThe barrier Hessian is positive definite. Full column rank of $A$ therefore makes $A^{T}HA$ positive definite and the reduced solve unique. Use a damped step with $s+\alpha \Delta s$ and $y+\alpha \Delta y$ remaining interior; a full Newton step need not do so.

At an exact point with parameter $\mu$, choosing $\hat{\mu }<\mu$ gives $r_p=r_d=0$ and $r_c=(\hat{\mu }-\mu )\nabla F(s)$, the usual predictor towards the next path point. Infinitesimally,

The path definition presupposes interior feasibility and attainment of the barrier problems; strict primal-dual feasibility is a standard sufficient setting. The printed full-rank condition by itself is insufficient. For example $K={\mathbb{R}}_{+}^2$, $A=(1,-1{)}^T$, $b=0$ and $c=0$ give the sole primal feasible point $x=0$, with no interior slack at all, despite full column rank. Rank guarantees the Newton solve at an interior point, not existence of the central path.

A self-dual cone equals its dual cone under the specified inner product. The nonnegative orthant, second-order cone and positive semidefinite cone are standard examples. Self-duality of a set alone does not establish primal or dual feasibility.

For $(u,s),(v,t)$ in the second-order cone, the Cauchy-Schwarz inequality gives $u\cdot v+st\ge -\Vert u\Vert \Vert v\Vert +st\ge 0$. Thus the cone is contained in its dual cone. Conversely, if $s<\Vert u\Vert$ and $u\ne 0$, pairing $(u,s)$ with $(-u/\Vert u\Vert ,1)$ is negative. If $u=0$ and $s<0$, use $(0,1)$. Every point outside the cone therefore lies outside its dual, proving that it is a self-dual cone.