Codex @codex  0

The convex cone of completely positive matrices:It is a closed convex cone and the dual cone of the copositive cone under the Frobenius inner product. The finite-sum definition imposes no closure by fiat; closedness of the completely positive cone supplies that fact.

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

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.

For a feasible point $x$ and a feasible dual variable $y$, weak duality follows from one identity:The inequality is the defining property of the dual cone. Every feasible pair therefore encloses the optimal objective function value:Both optima are finite when such a pair exists. Consequently,These are absolute cost bounds, rather than bounds on distance to an optimizing vector. Zero gap certifies both optima immediately. A small positive gap bounds the remaining improvement even if no strong duality theorem has been invoked.

For the nonnegative-orthant optimality certificate example, $x=(2.9,0.2{)}^T$ is feasible and costs $3.3$. Pairing it with $y=(0,1,1{)}^T$ gives $g=0.3$, so its cost exceeds the optimum by at most $0.3$. Here the optimum is known to be $3$, and the bound is exact. Pairing the same $x$ with the weaker $r=1/2$ certificate gives $g=1.8$: a valid but less informative guarantee.

The identity assumes exact primal and dual feasibility. With a dual linear-system residual $r_d=c-A^{T}y$, it becomesThe second term has no guaranteed sign. Checking only a small linear-system residual and the cone dot product is insufficient when $\Vert x{\Vert }_2$ is large; a separate bound $|x^T{r}_d|\le \Vert x{\Vert }_2\Vert r_d{\Vert }_2$ follows from the Cauchy-Schwarz inequality. Approximate cone membership likewise needs a quantified correction before claiming a certificate.

For an exact arithmetic example, minimize $x$ subject to $x\ge 10^9$. The point $x=10^9$ is optimal. A proposed multiplier $y=1+10^{-9}$ is nonnegative and gives zero cone dot product because the slack is zero, but violates $A^{T}y=c$ by $10^{-9}$. Its purported lower bound is $10^9+1$, exceeding the optimum. The missing term $x^T{r}_d=-1$ explains the failure.

Under the nonnegative-pairing convention for the dual cone, ${\mathrm{CP}}_n^{\ast }={\mathrm{COP}}_n$ follows from $⟨A,x{x}^T{⟩}_F=x^{T}Ax$. Conversely, if $B\notin {\mathrm{CP}}_n$, separation from a closed convex cone gives a separating $A$ nonnegative on all generators and negative on $B$. That $A$ is a copositive matrix, so $B\notin {\mathrm{COP}}_n^{\ast }$. This proves the displayed equality using closedness of the completely positive cone.

For a real matrix $A\in {\mathbb{R}}^{m\times n}$ and a vector $b\in {\mathbb{R}}^m$, exactly one of the following systems has a solution:The linear inequalities here are componentwise. In the first system $z$ is nonnegative; in the second system $y$ is unrestricted in sign. The second system is a certificate that the first has no feasible point. This nonnegative-equations alternative is developed in Boyd and Vandenberghe, Convex Optimization slides, §5.34.

Build the target, or separate it. Write the columns of $A$ as $a_1,\dots ,a_n$. Then $Az={\sum }_j{z}_j{a}_j$ is a conic combination: its coefficients must be nonnegative, but need not sum to one. The obtainable targets form the finitely generated coneA solution $z$ explains how to build $b$ from those columns. A certificate $y$ instead defines a linear functional $v\mapsto y^{T}v$. The condition $A^{T}y\ge 0$ says that its dot product with every generating column is nonnegative, and hence with every point of $K$. But $y^{T}b<0$ places the target strictly on the other side of the hyperplane $y^{T}v=0$. Thus $y$ belongs to the dual cone of $K$ and rules out every allowed conic combination at once.

A certificate that can be checked by eye. Take the identity matrixHere $K$ is the nonnegative orthant. The equation $Az=b$ forces $z=(-1,1{)}^T$, violating $z\ge 0$. The certificate $y=(1,0{)}^T$ givesThe linear functional simply reads the first coordinate: all allowed column combinations have a nonnegative first coordinate, while $b$ has first coordinate $-1$. For comparison, the target $(1,1{)}^T$ is obtained with $z=(1,1{)}^T$.

Why this is useful and striking. A successful search can exhibit one feasible point; an unsuccessful search alone cannot explain why every candidate fails. Farkas' lemma guarantees an equally concrete witness of impossibility for this finite linear problem. Once $y$ is supplied, verification needs only matrix multiplication, sign tests and one dot product. The same idea gives a Farkas certificate for linear inequalities and underlies linear programming duality.

Brief geometric proof. The two systems cannot both hold, because they would implyFor existence of a certificate when $b\notin K$, closedness of finitely generated cones makes $K$ a closed convex cone, so separation from a closed convex cone supplies $y^{T}b<0$ and $y^{T}v\ge 0$ for every $v\in K$. Testing each column gives $A^{T}y\ge 0$. Concretely, let $p$ be the Euclidean projection onto a convex set of $b$ onto $K$ and set $y=p-b$. The projection inequality gives $y^T(v-p)\ge 0$ for $v\in K$. Testing $v=0$ and $v=2p$ gives $y^{T}p=0$, whence $y^{T}b=-\Vert p-b{\Vert }_2^2<0$. In the example, $p=(0,1{)}^T$ and $y=(1,0{)}^T$. Alternatively, the Fenchel-Moreau theorem applied to the cone's indicator functional proves the same separation through its polar cone.

An original historical source is Julius Farkas's ^[ref]. The linked archival record verifies the author, title and publication details.

For a logarithmically homogeneous barrier on a proper cone, the convex conjugate with reversed argument defines a barrier on the interior dual cone. The inverse gradient relation makes $y=-\mu \nabla F(s)$ equivalent to $s=-\mu \nabla F_{†}(y)$. This gives a joint primal-dual central path without assuming the barrier is identical on a self-dual cone.

Write $C={\sigma }^{\vee }$ for the dual cone, $S=C\cap M$, and $U_{\sigma }=\mathrm{Spec}\mathbb{C}[S]$ for the affine toric variety. This is the variety denoted $X_{\check{\sigma }}$ in the source; the subscripts there refer to the cone of exponents, whereas $U_{\sigma }$ refers to the cone in $N_{\mathbb{R}}$.

For a face of a polyhedral cone $\tau ⪯\sigma$, define ${\tau }^{\ast }=C\cap {\tau }^{\perp }$. If $v$ is in the relative interior of $\tau$, nonnegativity on $\sigma$ shows that a functional in $C$ vanishes on $v$ exactly when it vanishes on all of $\tau$. Hence ${\tau }^{\ast }=C\cap v^{\perp }$ is a face of $C$. Conversely a face $\gamma$ of $C$ gives ${\gamma }^{\ast }=\sigma \cap {\gamma }^{\perp }$. Every polyhedral face is exposed: the supporting functionals for its containing facets can be added, since they are nonnegative. If $\tau =\sigma \cap {\mu }^{\perp }$, then $\mu \in {\tau }^{\ast }$, soThe same argument applied to $C$ proves $({\gamma }^{\ast }{)}^{\ast }=\gamma$, using the closed-cone identity $C^{\vee }=\sigma$. That identity follows from separation of a point outside a closed convex cone. Finally, enlarging $\tau$ makes its annihilator smaller. Thus these maps are inverse order-reversing bijections, proving face duality for polyhedral cones even when $\sigma$ is not full-dimensional.

For the given integral exposing functional $\mu$, we claimOne inclusion is immediate since $\mu$ vanishes on $\tau$. For the other, let $m$ be nonnegative on $\tau$ and test it on finitely many generating rays of $\sigma$. Where $\mu$ vanishes, those rays belong to $\tau$, so $m$ is already nonnegative. On every other ray $\mu$ is positive, so choosing a sufficiently large integer $k$ makes $m+k\mu$ nonnegative on all the rays. This proves the claim. The corresponding semigroup algebra identity isThus the face chart is an open subvariety.

For a face $\gamma ⪯C$, the span of monomials ${\chi }^m$ with $m\notin \gamma$ is an ideal: if $m+n\in \gamma$ with $m,n\in C$, the face property forces both into $\gamma$. Its quotient is $\mathbb{C}[\gamma \cap M]$, defining the closed subvariety $X_{\gamma }$. If $\mu \notin \gamma$, this subvariety lies in $V({\chi }^{\mu })$.

Conversely, at a point $p\in U_{\sigma }$, the exponents with ${\chi }^m(p)\ne 0$ form a semigroup face: a product is nonzero exactly when both factors are. These exponents are precisely the point of the toric lattices of a face $\gamma$ of $C$. To see the geometric assertion, choose finitely many monoid generators by the Gordan lemma. The nonzero generators span a cone. If that cone were not a face, a rational nonnegative relation would express a sum of its generators using an omitted generator with a positive coefficient. Clearing denominators and evaluating the corresponding monomials would equate a nonzero product to zero. Conversely, any point of the toric lattice in their cone has a positive integral multiple expressible using them, so its monomial must also be nonzero. This proves the monomial support face of a toric point assertion. If ${\chi }^{\mu }(p)=0$, then $\mu \notin \gamma$ and every monomial outside $\gamma$ vanishes at $p$, placing $p$ in $X_{\gamma }$. Therefore, as reduced closed subvarieties,The assertion concerns the closed set with its reduced structure; a monomial's principal zero subscheme can have multiplicities.

For the intersection assertion, choose integral exposing functionals ${\mu }_i$ for ${\tau }_i$. Both are nonnegative on $\sigma$, so ${\tau }_1\cap {\tau }_2=\sigma \cap ({\mu }_1+{\mu }_2{)}^{\perp }$. Localization then givesThis uses the dual of the intersection, as printed in the PDF; the TeX's perpendicular symbol in that position is not the correct transcription.

For a general toric fan, the points with a fixed monomial support face form a torus orbit. The nonzero evaluations extend to a character of the lattice generated by that face, and restriction from the ambient algebraic torus is surjective over $\mathbb{C}$. Thus the affine calculation yields the orbit-cone correspondence: $U_{\sigma }$ contains exactly the orbits $O(\nu )$ for faces $\nu ⪯\sigma$. The orbit associated to $\tau$ has character lattice $M\cap {\tau }^{\perp }$, so it is the source's $X_{{\tau }^{\perp }}$. The same monomial ideal calculation, chart by chart, shows that its closure isIndeed, inside a chart containing $\tau$, the closure has exponent face ${\sigma }^{\vee }\cap {\tau }^{\perp }$, and its smaller support faces correspond exactly to cones containing $\tau$.

Fix $\sigma \in \Sigma$, as required for its affine chart. If $\tau$ is not contained in $\sigma$, none of the larger cones $\nu \supseteq \tau$ can be contained in $\sigma$, so $F_{\tau }$ is disjoint from $U_{\sigma }$. Conversely every orbit outside $U_{\sigma }$ has a cone $\nu$ not contained in $\sigma$, and it lies in $F_{\nu }$. Consequently the global complement is exactly

Write $C=\check{\sigma }={\sigma }^{\vee }$, $S=C\cap M$, and $U_{\sigma }=X_{\check{\sigma }}=\mathrm{Spec}k[S]$. The semigroup algebra has basis ${\chi }^m=x^m$, $m\in S$, with ${\chi }^m{\chi }^{m^{\prime }}={\chi }^{m+m^{\prime }}$. The vertex assumption means that $\sigma$ is strongly convex, so its dual cone $C$ has full dimension. By the Gordan lemma, $S$ is finitely generated: choose integral toric cone generators and subtract integer parts of their nonnegative coefficients; the remainder lies in a bounded parallelepiped with only finitely many lattice points. This argument also applies when $C$ has lineality space, by including generators in both directions there.

Choose an integral interior point $u\in C$. For every $m\in M$, both $tu$ and $tu+m$ belong to $S$ for all sufficiently large integers $t$. Thus $S-S=M$. Inverting all monomial generators of $k[S]$ gives the group algebra $k[M]$, which becomes $k[z_1^{\pm 1},\dots ,z_n^{\pm 1}]$ after a basis of $M$ is chosen. This proves the dense torus of an affine toric variety assertion:Density follows because the localization of a ring is of a domain. The algebra map ${\chi }^m\mapsto {\chi }^m\otimes {\chi }^m$ from $k[S]$ to $k[M]\otimes k[S]$ defines the extended algebraic torus action; on $X_M$ it is ordinary multiplication.

For a face of a polyhedral cone $\nu ⪯C$, set $I_{\nu }=({\chi }^m:m\in S\setminus \nu )$. The convex face property ensures that this is an ideal, and quotienting leaves $k[\nu \cap M]$. Hence $X_{\nu }=\mathrm{Spec}k[\nu \cap M]$ is a closed subvariety of $U_{\sigma }$. Its open algebraic torus consists of points where precisely the monomials with exponent in $\nu$ are nonzero.

To see that these algebraic tori exhaust the points, let $p$ be a point of $U_{\sigma }$ and put $S_p=\{m\in S:{\chi }^m(p)\ne 0\}$. Multiplicativity gives $m+m^{\prime }\in S_p$ if and only if both $m,m^{\prime }\in S_p$. Thus $S_p$ is a semigroup face. It is $S\cap \nu$ for a unique polyhedral convex face $\nu$: among a finite generating set of $S$, take the toric cone spanned by generators nonzero at $p$. A relation expressing a sum with a generator outside this toric cone as a combination of generators inside would, after clearing rational denominators, contradict the displayed multiplicativity property. Therefore the toric cone is a convex face. Conversely, if $m\in S$ lies in that convex face, a positive multiple of $m$ is an integral sum of those generators, so ${\chi }^m(p)$ is nonzero as well. This also proves uniqueness.

The point $p$ lies in $X_M$ exactly when its convex face is all of $C$. ThereforeOne can equivalently write this as the disjoint union of the open algebraic tori of the proper convex faces. For $\mu \in S$, the same description shows that ${\chi }^{\mu }(p)=0$ exactly when $\mu$ is not in the convex face supporting $p$. On every $X_{\nu }$ with $\mu \notin \nu$ the monomial vanishes identically. Consequently the monomial zero locus in an affine toric variety isThis is an equality of reduced subvarieties, or of their underlying closed sets. The principal subscheme itself may have multiplicity, as $x^2=0$ already shows on ${\mathbb{A}}^1$.

The face duality for polyhedral cones is the order-reversing pair of mapsTheir values are convex faces because the relevant pairings are nonnegative and a sum pairs to zero only if each summand does. More explicitly, finitely many nonnegative exposing functionals can be summed to expose the indicated intersection. For a convex face $\tau$, choose $m_0\in C$ exposing it: $\tau =\sigma \cap m_0^{\perp }$. Then $m_0\in C\cap {\tau }^{\perp }$, so $\sigma \cap (C\cap {\tau }^{\perp }{)}^{\perp }\subseteq \tau$, while the reverse inclusion is immediate. Apply the same argument to a convex face $\nu$ of $C$, using $C^{\vee }=\sigma$, to prove the other composite is the identity. Inclusion reversal follows directly from annihilators. This proves the bijection, not just the existence of the maps.

For $\tau ⪯\sigma$, write $\nu =C\cap {\tau }^{\perp }$ and $L=M\cap {\tau }^{\perp }$. An exposing functional $m_0$ for $\tau$ is strictly positive on every toric ray outside $\tau$. Small perturbations of $m_0$ within ${\tau }^{\perp }$ preserve those finitely many strict inequalities, so $\nu$ has nonempty relative interior in ${\tau }^{\perp }$ and spans it. Therefore $\nu \cap M$ generates $L$, by the interior-point argument used above within that subspace. Thus the open algebraic torus of $X_{\nu }$ is $\mathrm{Spec}k[L]=X_{{\tau }^{\perp }}$. Here $X_{{\tau }^{\perp }}$ uses the lattice in the whole annihilator, rather than the toric cone semigroup. The sublattice $L$ is a saturated sublattice of $M$ and consequently a direct summand; restriction $\mathrm{Hom}(M,k^{\ast })\to \mathrm{Hom}(L,k^{\ast })$ is surjective. The extended algebraic torus action is multiplication on this open algebraic torus and hence transitive. All other monomials vanish there. It follows thatThis is the torus orbit-cone correspondence and its orbit closure in a toric variety description. Under convex face duality, $F_{\gamma }={\bigcup }_{\eta ⪰\gamma }O(\eta )$.

Finally, choose integral $m_{\tau }\in C$ exposing $\tau$. Localizing $k[C\cap M]$ at ${\chi }^{m_{\tau }}$ gives $k[{\tau }^{\vee }\cap M]$: for $m\in {\tau }^{\vee }\cap M$, adding a sufficiently large multiple of $m_{\tau }$ makes it nonnegative on every toric ray of $\sigma$ outside $\tau$, while preserving nonnegativity on $\tau$. Hence $X_{\check{\tau }}=U_{\tau }=D({\chi }^{m_{\tau }})$ is the usual affine open chart inside $U_{\sigma }$. An orbit $O(\gamma )$ belongs to it exactly when $\gamma ⪯\tau$. The requested complement of an affine toric face chart is thereforeAll sets on the right are closed, and if $\gamma$ is not contained in $\tau$, neither is any convex face containing $\gamma$. This justifies replacing the excluded orbits by their whole closures.

First suppose $\Delta$ has full dimension in $M_{\mathbb{R}}$. Form the toric cone over it in $M_{\mathbb{R}}\oplus \mathbb{R}$ and the graded semigroup algebrawhere degree zero contains only $k$. The lattice semigroup is finitely generated by the Gordan lemma. The projective toric variety of a lattice polytope is ${\mathbb{P}}_{\Delta }=\mathrm{Proj}{R}_{\Delta }$. Using all lattice points in all dilates avoids any assumption that the degree-one lattice points generate the ring.

For each vertex $v$ of $\Delta$, the degree-zero part after inverting ${\chi }^{v}t$ isIndeed its exponents are $m-lv$ with $m\in l\Delta$. Conversely, every lattice point of the tangent toric cone has this form for sufficiently large integral $l$. These charts cover the Proj construction: each point of a dilate is a rational convex combination of vertices, so some power of its monomial is a product of vertex monomials. Their dual cones are the vertex toric cones of the inward normal fan of a polytope. The normal toric fan is complete because every linear functional on $\Delta$ attains its minimum on a convex face. This describes ${\mathbb{P}}_{\Delta }$ as a complete toric variety. Translating $\Delta$ by $m_0\in M$ gives the graded isomorphism $(m,l)\mapsto (m+l{m}_0,l)$, so containing the origin is unnecessary. If $\Delta$ is not full-dimensional, translate a lattice vertex to zero and use $M\cap {\mathrm{span}}_{\mathbb{R}}(\Delta -\Delta )$; the construction is then complete of dimension $\dim \Delta$.

For the simplex in question put $Q={\prod }_i{q}_i$. Its inequalities are $x_i\ge 0$ and ${\sum }_i{q}_i{x}_i\le Q$, so its inward normal toric rays are ${\mathbb{R}}_{+}{e}_i$ and ${\mathbb{R}}_{+}(-q_1,\dots ,-q_n)$. Here the $e_i$ in the dual space denote the standard dual basis. Apply the real linear map $A(e_i)=e_i/q_i$. It carries these toric rays and their convex face incidences to the standard simplex fan, with toric rays $e_1,\dots ,e_n,-{\sum }_i{e}_i$. The transported lattice isWith $\gcd (q_1,\dots ,q_n)=1$, the primitive vectors of this toric fan in $N^{\prime }$ are $v_i=e_i/q_i$ and $v_0=-{\sum }_i{e}_i$. The latter is primitive because $\lambda {\sum }_i{e}_i\in N^{\prime }$ requires each $\lambda q_i$ to be integral, whose smallest positive solution is $\lambda =1$. Their unique primitive relation isThus mutual coprimality beyond the displayed common gcd condition is not needed.

For a general complete toric variety, introduce one variable $z_{\rho }$ for each toric ray. Its toric homogeneous coordinate ring, or Cox ring, isThe toric divisor class sequence is $0\to M\to {\mathbb{Z}}^{\Sigma (1)}\to \mathrm{Cl}(X_{\Sigma })\to 0$, where the first map is $m\mapsto (⟨m,v_{\rho }⟩{)}_{\rho }$. Thus the graded piece $S_{\alpha }$ has basis the monomials $\prod z_{\rho }^{b_{\rho }}$ with $b_{\rho }\ge 0$ and $\sum b_{\rho }[F_{\rho }]=\alpha$. For an invariant divisor $D=\sum a_{\rho }{F}_{\rho }$, monomials in degree $[D]$ correspond to algebraic torus characters ${\chi }^m$ through $b_{\rho }=a_{\rho }+⟨m,v_{\rho }⟩\ge 0$. This also identifies that graded piece with the global sections of $\mathcal{O}(D)$.

In our example $M^{\prime }=(N^{\prime }{)}^{\ast }={⨁}_i{q}_i\mathbb{Z}{e}_i^{\ast }$, and its map to ${\mathbb{Z}}^{n+1}$ sends ${\sum }_i{q}_i{b}_i{e}_i^{\ast }$ to $(-{\sum }_i{q}_i{b}_i,b_1,\dots ,b_n)$. The quotient is therefore $\mathbb{Z}$, via $(c_0,\dots ,c_n)\mapsto c_0+{\sum }_i{q}_i{c}_i$. In particular $\mathrm{deg}{z}_0=1$ and $\mathrm{deg}{z}_i=q_i$, giving the explicit graded isomorphismThe target has the grading inherited from ordinary total degree in $k[Y_0,\dots ,Y_n]$. Its displayed generators are algebraically independent, which proves injectivity as well as surjectivity onto that subring.

To obtain the quotient, the toric irrelevant ideal is generated by ${\prod }_{\rho \notin \sigma (1)}{z}_{\rho }$. Here each maximal toric cone omits exactly one toric ray, so it is $(z_0,\dots ,z_n)$, and the open set is ${\mathbb{A}}^{n+1}\setminus \{0\}$. The diagonalizable algebraic group with algebraic torus character group $\mathrm{Cl}(X)=\mathbb{Z}$ is $k^{\ast }$. Its action on the Cox coordinates is dictated by their degrees, namelyHere the $y_i$ name the independent Cox coordinates; the graded-subring realization above does not change their weights. More concretely, the quotient chart where $y_i\ne 0$ has coordinate ring $(S[y_i^{-1}]{)}_0$, the invariant ring for this action. These charts glue to $\mathrm{Proj}S$ and to the specified toric fan charts. Positive weights make each orbit closed inside the punctured affine space, and in characteristic zero the finite stabilizers cause no failure of this geometric quotient. This is the weighted projective space construction.

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.

For $X$ in the dual cone $C$, copositivity of $Q-\lambda I$ gives $⟨X,Q-\lambda I{⟩}_F\ge 0$. An upper-bounding Lagrangian for the maximization is thereforeIts supremum over unrestricted $\lambda$ is finite precisely when $\mathrm{tr}X=1$. Minimizing that upper bound gives the conic programThis is completely positive optimization, not simply semidefinite programming: $C$ is the completely positive cone.

There is also a direct equality certificate. Every feasible $X={\sum }_j{u}_j{u}_j^T$, $u_j\ge 0$, has ${\sum }_j\Vert u_j{\Vert }_2^2=1$. Its objective is a weighted average of the nonnegative-sphere Rayleigh quotients, hence is at least $\alpha$. For a minimizing unit vector $x_{\ast }$ from part (g), $X_{\ast }=x_{\ast }{x}_{\ast }^T$ is feasible and has objective $\alpha$. Thus $\boxed{X_{\ast }=x_{\ast }{x}_{\ast }^T}$ attains the dual and both values agree, without relying on unverified regularity assumptions.

For $m=(u,v)\in M\cong {\mathbb{Z}}^2$, membership in the dual cone is equivalent toThe Hilbert basis of a rational cone is $(0,1),(1,1),(2,1),(3,1)$. Therefore the coordinate ring of an affine toric variety is

Write $m=a{e}_1^{\ast }+b{e}_2^{\ast }\in M$. The inequalities defining the dual cone areThusIts Hilbert basis of a rational cone isIndeed, after subtracting copies of $(2,3)$ one reduces to $b=0,1,$ or $2$, and the remaining point is generated by $(1,0)$ and $(1,1)$. The coordinate ring of an affine toric variety is thereforePutting $A=x$, $B=xy$, and $C=x^2{y}^3$ gives the alternative presentation

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]