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$.

The same relative coordinates give the proximity time of translating line segments asThis is a convex norm-constrained problem, rather than the linear feasibility problem for contact. One can solve it as a small second-order cone problem. If the distance between the initial line segments is at most $d$, the answer is zero; if no feasible point exists, the threshold is never reached.

For an elementary analytic algorithm, consider the nine combinations in which each of $s,r$ is either free, fixed at zero or fixed at one. In each case, minimize the squared distance over the free parameters. Writing $q(t)$ for $D+tv$ plus the fixed endpoint contributions, and $K$ for the columns belonging to free parameters, stationarity isIf the Gram matrix $K^{T}K$ is nonsingular, $z(t)=-(K^{T}K{)}^{-1}{K}^{T}q(t)$ is affine in time. Retain only the time interval on which its entries lie in $[0,1]$. The residual is then $r_0+t{r}_1$, and feasibility reduces toIntersect its solution interval with $t\ge 0$ and the free-parameter validity interval, and record the first point. Include the four endpoint–endpoint cases, where there are no unfixed segment parameters. Take the earliest valid candidate among all cases. The actual closest pair belongs to one of these faces of the parameter square, so this enumeration cannot miss the first approach.

The complications are the quadratic threshold equation, changes of the active closest-point feature and singular Gram matrices for parallel or degenerate segments. In a singular case, keep the affine family of minimizers and its feasibility bounds, or use the original convex problem; a pseudoinverse answer alone can fall outside the segment even when another minimizer is feasible. Constant-distance cases and tangential threshold contact must also be retained. Merely checking moving endpoints misses approaches between interior points.

The fidelity norm here is unsquared, as in the original PDF. Write $(s{)}_{+}=\max (s,0)$, so $h(Gu)={\sum }_i((Gu{)}_i{)}_{+}^2$. Introduce $a,q\in {\mathbb{R}}^n$ and $t\in \mathbb{R}$. The second-order cone reformulation of one-sided quadratic denoising issubject to the affine cone constraintswhere ${\mathcal{Q}}_d=\{(r,z):r\ge \Vert z{\Vert }_2\}$ is the second-order cone. All coordinates displayed inside the cone memberships are affine in the optimization variables, so stacking them has precisely the form $Ax-b\in K$. The first cone enforces $t\ge \Vert u-g{\Vert }_2$, and each three-dimensional cone enforces $q_i\ge a_i^2$. The two scalar inequalities give $a_i\ge ((Gu{)}_i{)}_{+}$.

Every feasible lift therefore has objective at least the original objective. Conversely, for any $u$, choose $a_i=((Gu{)}_i{)}_{+}$, $q_i=a_i^2$ and $t=\Vert u-g{\Vert }_2$ to attain equality. Thus the reformulation is exact. It is a second-order cone program over the product $K={\mathcal{Q}}_{n+1}\times {\mathcal{Q}}_3^n\times {\mathbb{R}}_{+}^{2n}$, a proper closed self-dual cone. It preserves the asymmetric derivative penalty; replacing it by $\Vert Gu{\Vert }^2$ would change the problem.

The canonical Lorentz-cone barrier is $-\log (r^2-\Vert z{\Vert }^2)$ on $r>\Vert z\Vert$, and each orthant coordinate contributes $-\log s$. Their sum, composed with the affine slack map, isIts domain explicitly requires $t>\Vert u-g\Vert$, $q_i>a_i^2$, $a_i>0$ and $a_i>(Gu{)}_i$; the positive Lorentz branch must not be inferred merely from positivity of a squared expression. The barrier parameter of the product-cone barrier is $\boxed{\nu =4n+2}$, with two per Lorentz block and one per scalar orthant slack. A strict feasible lift can always be obtained by choosing $a$ above both bounds, $q$ above $a^2$, and $t$ above the fidelity norm.

The set $C$ is the second-order cone. PutWhen $\rho \ge |t|$ and $\rho >0$, one has $0\le \alpha \le 1$, and the proposed pointlies on the boundary of $C$ because $\Vert \alpha u{\Vert }_2=\alpha \rho$.

Set $\delta =(\rho -t)/2\ge 0$. Sincefor any $(v,s)\in C$ we obtainwhere the first inequality is the Cauchy-Schwarz inequality and the second uses $\Vert v{\Vert }_2\le s$. Part (d) therefore giveswhenever $\Vert u{\Vert }_2\ge |t|$ and $u\ne 0$. At $(u,t)=(0,0)$ the projection is plainly $(0,0)$, consistent with the limiting formula.

If $\rho \le -t$, then for every $(v,s)\in C$,Applying part (d) with $\pi =0$ givesTogether with the trivial case $\rho \le t$, this is the full projection onto the second-order cone.

A curved feasible set can have the same certificate structure. ConsiderWrite $x=(t,z{)}^T$ and use the second-order cone $K=\{(s_0,s_1,s_2):s_0\ge \sqrt{s_1^2+s_2^2}\}$. In this coordinate ordering,Self-duality of a second-order cone makes $K^{\ast }=K$. The equality $A^{T}y=c$ forces $y_0=1$ and $y_2=0$, leaving $-1\le y_1\le 1$. Its dual objective function is $b^{T}y=-y_1$, maximized at $y=(1,-1,0{)}^T$. Thus every feasible point satisfies $t\ge 1$, and $(t,z)=(1,0)$ attains that bound: $\boxed{p_{\ast }=d_{\ast }=1}$.

The zero dot product is $(1,1,0)\cdot (1,-1,0)=0$. Individual coordinate products need not be nonnegative here: the cancellation $1-1=0$ occurs across coordinates. The valid complementary slackness condition is cone-level orthogonality, rather than the coordinatewise interpretation of the nonnegative orthant.

A second-order cone program has a linear objective and affine constraints taking values in products of second-order cones and nonnegative orthants. Norm epigraphs have the form $(t,z)\in \mathcal{Q}$; quadratic epigraphs admit the affine lift $((q+1)/2,(q-1)/2,a)\in {\mathcal{Q}}_3$, equivalent to $q\ge a^2$. Product-cone self-concordant barriers give interior-point methods.

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.

For a proper cone $K$, suppose a point satisfies $Ax-b\in \mathrm{int}K$ and $p_{\ast }$ is finite. This generalized Slater condition gives strong duality and attainment of the conic dual problem's optimum. It does not by itself assert primal attainment.^[ref]

The two worked examples have strict primal points: $(u,v)=(2,2)$ has slack $(2,2,1)$ in the interior of the nonnegative orthant, and $(t,z)=(2,0)$ has slack $(2,1,0)$ in the interior of the second-order cone. Both optima were already certified by explicit feasible pairs. Slater's condition explains why a matching optimal dual variable can be expected under these hypotheses; checking a supplied zero-gap pair needs only weak duality.

Changing cone geometry preserves the bound mechanism. For a positive semidefinite cone, the dual cone pairing is the Frobenius inner product of two matrices. This connects the same certificate idea to semidefinite programming, while the central path uses strictly interior primal and dual points to approach vanishing gap.

In 1995, Lieven Vandenberghe and Stephen Boyd presented a primal-dual interior-point method for convex optimization with matrix inequalities. Their algorithmic study included exploiting problem structure and allowing incomplete conjugate gradient method solves within an iteration. This illustrates how the primal-dual viewpoint guides computation as well as checking a final answer.^[ref]