Convex Cones, Separation, Conic Duality, and Semidefinite Programs

A finite-dimensional linear feasibility problem has a strict separating certificate when its target lies outside the closure of the relevant conic image. If that image is closed—as it is for the nonnegative orthant and every polyhedral cone—this is exactly an infeasibility certificate. For semidefinite cones, however, a linear image need not be closed: a problem can be infeasible but arbitrarily close to feasible, with no certificate of the elementary strict-separation form.

Primal–dual conic formulations always give weak duality: every dual feasible point supplies a lower bound on every primal feasible point. Equality of optimal values and attainment require additional hypotheses, such as an applicable primal or dual Slater condition. A floating-point residual is evidence about a nearby numerical problem, not by itself a proof of exact feasibility, positivity, infeasibility, or optimality. These distinctions are what make conic certificates useful in QFT rather than merely persuasive.

Required background. Bilinear and Hermitian Forms, Adjoints, and Isometries supplies dual pairings and Hermitian adjoints; Normal Forms, Spectra, and Projectors supplies the finite spectral theorem and the eigenvalue test for positive semidefiniteness.

Finite-dimensional conic certification

The argument below is finite dimensional. It does not develop infinite-dimensional convex duality, general nonlinear or nonconvex optimization, algorithms, solver implementation, or production numerics.

The basic setting is a pair of finite-dimensional real vector spaces $V$ and $W$, with algebraic duals $V^*$ and $W^*$. The pairing is written

$$\langle s,x\rangle, \qquad s\in V^*, \quad x\in V.$$

For a linear map $A:V\to W$, its dual map is

$$A^*:W^*\longrightarrow V^*, \qquad \langle A^*y,x\rangle = \langle y,Ax\rangle.$$

This $A^*$ is a canonical dual map; it does not require an inner product. When Hermitian matrices appear later, they are regarded as a real vector space and paired by $\operatorname{Tr}(XY)$. Thus there is no hidden choice between the site’s conjugate-linear bra convention and a complex-bilinear optimization pairing.

Norms enter only when numerical residuals and distances are discussed. Every finite-dimensional norm gives the same topology, but it gives different numerical values, so a reported residual must name its norm and scaling.

Convex sets, cones, duals, and faces

A set $C\subseteq V$ is convex when

$$tx+(1-t)z\in C \quad \text{for all }x,z\in C,\quad 0\leq t\leq1.$$

A convex cone $K\subseteq V$ is closed under nonnegative linear combinations:

$$x,z\in K,\quad \alpha,\beta\geq0 \quad\Longrightarrow\quad \alpha x+\beta z\in K.$$

Unless stated otherwise, conic programs on this page use a closed convex cone. A cone is pointed if $K\cap(-K)=\{0\}$ and solid if its interior is nonempty. A closed, convex, pointed, solid cone is often called proper. Weak duality does not need all of these adjectives, so they should not be added silently.

The dual cone is

$$K^* = \left\{ s\in V^*: \langle s,x\rangle\geq0 \text{ for every }x\in K \right\}.$$

The negative polar cone is

$$K^\circ = \left\{ s\in V^*: \langle s,x\rangle\leq0 \text{ for every }x\in K \right\} =-K^*.$$

Naming the sign avoids a common source mismatch: some references call $K^*$ the polar, while others reserve “polar” for $K^\circ$. The dual cone is always closed and convex. The finite-dimensional bipolar theorem gives

$$K^{**}=\overline K$$

for a convex cone after the natural identification $V^{**}\simeq V$. Consequently, a closed convex cone is recovered exactly from all of its dual inequalities.

The relative interior $\operatorname{ri}C$ is the interior taken inside the affine hull of $C$. It is the correct notion when a feasible set or a cone has already been restricted to a lower-dimensional affine space. A convex subcone $F\subseteq K$ is a face of $K$ when

$$x,z\in K,\quad x+z\in F \quad\Longrightarrow\quad x,z\in F.$$

Faces matter because feasible points may be forced onto the boundary of the ambient cone. In that case an ambient-interior Slater point is impossible, even though the problem may have a relative-interior point in a smaller face. Identifying that face can restore an appropriate regularity statement; the algorithms for doing so are outside this page.

Three reference examples are:

• $\mathbb R_+^n$ is a closed, proper, self-dual polyhedral cone under the standard pairing;
• a nonzero linear subspace is a closed convex cone with lineality, so it is not pointed; a proper subspace also has empty ambient interior; and
• the positive-semidefinite cone is closed, proper, and self-dual, but its linear images need not be closed.

Separation turns geometry into a certificate

Strong separation of a point. Let $C$ be a nonempty closed convex subset of a finite-dimensional real vector space, and let $b\notin C$. Then there is a nonzero $q\in V^*$ and a real number $\alpha$ such that

$$\langle q,x\rangle \leq \alpha < \langle q,b\rangle \qquad \text{for every }x\in C.$$

One proof chooses any Euclidean inner product, lets $x_0$ be a closest point of $C$ to $b$, and differentiates the squared distance along the segment $x_0+t(x-x_0)$. Minimality at $t=0$ gives

$$\langle b-x_0,x-x_0\rangle_{\mathrm E}\leq0 \qquad (x\in C).$$

The vector $b-x_0$ defines the separating covector. Moreover,

$$\langle b-x_0,b\rangle_{\mathrm E} - \langle b-x_0,x_0\rangle_{\mathrm E} = \|b-x_0\|_{\mathrm E}^2>0,$$

which produces the strict gap. The inner product is only a proof device: the existence of a separating covector is independent of that choice.

For two arbitrary disjoint closed convex sets, strict separation does not follow from closedness alone. The point-versus-closed-set theorem works because a closest point exists in finite dimension. Likewise, applying it to a conic image requires that the image itself be closed.

Farkas alternatives and the closure condition

Consider the feasibility problem

$$Ax=b, \qquad x\in K,$$

where $K\subseteq V$ is a closed convex cone. Its attainable right-hand sides form the convex cone

$$A(K)=\{Ax:x\in K\}\subseteq W.$$

Separation gives the always-correct alternative

$$\boxed{ \begin{aligned} &b\in\overline{A(K)},\\ &\text{or there exists }q\in W^* \text{ with } A^*q\in K^*, \quad \langle q,b\rangle<0. \end{aligned}}$$

Exactly one line can hold. Indeed, if $A^*q\in K^*$, then

$$\langle q,Ax\rangle = \langle A^*q,x\rangle \geq0 \qquad (x\in K),$$

so continuity rules out $\langle q,b\rangle<0$ for every $b\in\overline{A(K)}$. Conversely, if $b$ lies outside the closed cone $\overline{A(K)}$, strong separation supplies such a $q$.

This becomes a feasibility alternative only when $A(K)$ is closed:

$$b\notin A(K) \quad\Longleftrightarrow\quad \exists q: A^*q\in K^*, \ \langle q,b\rangle<0.$$

For $K=\mathbb R_+^n$, the image $A(K)$ is a finitely generated polyhedral cone and is closed. This is the familiar Farkas lemma: exactly one of

$$\begin{aligned} &Ax=b,\quad x\geq0,\\ &A^{\mathsf T}q\geq0,\quad q^{\mathsf T}b<0 \end{aligned}$$

is solvable.

As a concrete sign check, let

$$A= \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}, \qquad b= \begin{pmatrix} 0\\ 1 \end{pmatrix}, \qquad K=\mathbb R_+^2.$$

The equations require $x_1+x_2=0$ and $x_1-x_2=1$, which are incompatible with $x_1,x_2\geq0$. The covector

$$q= \begin{pmatrix} 1\\ -1 \end{pmatrix}$$

satisfies

$$A^{\mathsf T}q= \begin{pmatrix} 0\\ 2 \end{pmatrix} \geq0, \qquad q^{\mathsf T}b=-1<0.$$

The certificate is independently checkable by two matrix products. Its strict negative sign is the contradiction.

It is useful to distinguish two kinds of conic infeasibility:

• strongly infeasible: $b\notin\overline{A(K)}$; a strict separating certificate exists;
• weakly infeasible: $b\in\overline{A(K)}\setminus A(K)$; the exact system is infeasible, but its distance from feasibility is zero and the elementary strict certificate does not exist.

Polyhedral systems have no weakly infeasible case. Semidefinite systems can, as an explicit example below will show.

One declared primal–dual conic pair

Let $c\in V^*$. The standard primal problem used here is

$$\begin{aligned} (P)\qquad p^* = \inf_{x\in V}\;&\langle c,x\rangle\\ \text{subject to }& Ax=b,\qquad x\in K . \end{aligned}$$

Introduce $y\in W^*$ for the equality constraint. With the sign convention

$$L(x,y) = \langle c,x\rangle +\langle y,b-Ax\rangle,$$

the Lagrangian becomes

$$L(x,y) = \langle y,b\rangle +\langle c-A^*y,x\rangle.$$

Its infimum over $x\in K$ is finite precisely when $c-A^*y\in K^*$. Writing this dual slack as $s$, the dual is

$$\begin{aligned} (D)\qquad d^* = \sup_{y\in W^*,\,s\in V^*}\;& \langle y,b\rangle\\ \text{subject to }& A^*y+s=c,\qquad s\in K^* . \end{aligned}$$

This derivation fixes every sign. For any primal feasible $x$ and dual feasible $(y,s)$,

$$\begin{aligned} \langle c,x\rangle-\langle y,b\rangle &= \langle A^*y+s,x\rangle-\langle y,Ax\rangle\\ &= \langle s,x\rangle\\ &\geq0. \end{aligned}$$

This is weak duality. It needs neither strict feasibility nor attainment. It proves all of the following:

• every dual feasible objective is a lower bound on every primal feasible objective;
• every primal feasible objective is an upper bound on every dual feasible objective;
• an exactly feasible pair with zero gap is optimal on both sides; and
• for a pure feasibility problem with $c=0$, a dual feasible point with positive objective proves primal infeasibility.

The last item matches the earlier Farkas signs. If $A^*q\in K^*$ and $\langle q,b\rangle<0$, set $y=-q$ and $s=A^*q$. Then $A^*y+s=0$ while $\langle y,b\rangle>0$, contradicting the zero primal objective that any feasible point would have.

Weak duality does not say that either optimum is attained, that $p^*=d^*$, or that infeasibility on one side automatically produces a certificate of the simplest form.

Strong duality and attainment are separate conclusions

The optimal values are extended real numbers. The primal is infeasible when $p^*=+\infty$ and unbounded below when $p^*=-\infty$; the dual uses the corresponding maximization conventions. When both sides are feasible, weak duality gives

$$d^*\leq p^*.$$

Strong duality means equality of the two values. Primal attainment means that some feasible $x^*$ realizes $p^*$; dual attainment means that some feasible $(y^*,s^*)$ realizes $d^*$. These are three different statements.

For a proper cone, the familiar one-sided Slater results can be stated cleanly:

• If there is an $x_0\in\operatorname{int}K$ with $Ax_0=b$, and $p^*$ is finite, then $p^*=d^*$ and the dual optimum is attained.
• If there is a dual feasible $(y_0,s_0)$ with $s_0\in\operatorname{int}K^*$, and $d^*$ is finite, then $p^*=d^*$ and the primal optimum is attained.
• If both strict-feasibility conditions hold, both optima are finite, equal, and attained.

For a lower-dimensional cone, or after the constraints force all feasible points into a proper face, one first works in the span of the relevant minimal face and then uses the corresponding relative-interior condition. Merely replacing every occurrence of “interior” by “relative interior” without specifying that reduction can hide an incorrect ambient problem.

Slater conditions are sufficient, not necessary. Linear programs have stronger polyhedral duality theorems, and many nonpolyhedral programs enjoy zero gap without a strict point. Conversely, convexity, feasibility, and even attainment on both sides do not force zero gap, as the examples below show.

If feasible $x,y,s$ have zero gap, then

$$\langle s,x\rangle=0.$$

This is complementary slackness. It is an exact optimality certificate when combined with primal and dual feasibility. It should not be used as a substitute for either feasibility check. The one-sided attainment statements are the conic specialization of Boyd and Vandenberghe 2004, §5.2.3, PDF; Vandenberghe and Boyd 1996, §3 gives the corresponding SDP formulation.

The positive-semidefinite cone

Let $\operatorname{Herm}(n)$ denote the Hermitian $n\times n$ matrices, regarded as a real vector space. Its pairing is

$$\langle S,X\rangle = \operatorname{Tr}(SX).$$

For Hermitian $S$ and $X$, this trace is real because

$$\operatorname{Tr}(SX)^* = \operatorname{Tr}(XS) = \operatorname{Tr}(SX).$$

A Hermitian matrix is positive semidefinite, written $X\succeq0$, when

$$v^\dagger Xv\geq0 \qquad \text{for every }v\in\mathbb C^n.$$

By the finite spectral theorem, this is equivalent to every eigenvalue of $X$ being nonnegative. Positive definiteness, $X\succ0$, means every eigenvalue is strictly positive; these matrices form the interior of the PSD cone.

The cone is self-dual under the trace pairing. If $S,X\succeq0$, then

$$\operatorname{Tr}(SX) = \operatorname{Tr}\!\left( X^{1/2}SX^{1/2} \right) \geq0.$$

Conversely, if $S$ is not positive semidefinite, there is a $v$ with $v^\dagger Sv<0$. Taking $X=vv^\dagger\succeq0$ gives

$$\operatorname{Tr}(SX)=v^\dagger Sv<0,$$

so $S$ is not in the dual cone. Hence

$$\operatorname{Herm}_+(n)^* = \operatorname{Herm}_+(n).$$

Real symmetric matrices form the usual SDP special case, denoted $\mathbb S_+^n$. The Hermitian formulation changes neither the conic logic nor weak duality; all linear maps on $\operatorname{Herm}(n)$ are understood as real-linear.

The faces of the PSD cone have a concrete spectral description. For a subspace $U\subseteq\mathbb C^n$,

$$F_U = \{X\succeq0:\operatorname{Ran}X\subseteq U\}$$

is a face, exposed by the orthogonal projector $P_{U^\perp}$:

$$F_U = \{X\succeq0: \operatorname{Tr}(P_{U^\perp}X)=0\}.$$

Thus a constraint that forces a common kernel can confine every feasible matrix to a proper face. That is the geometric reason ambient Slater can fail.

Linear matrix inequalities and standard SDP form

A linear matrix inequality is

$$F(x) = F_0+\sum_{j=1}^m x_jF_j \succeq0,$$

where the $F_j$ are fixed Hermitian matrices and $x_j$ are real variables. Its feasible set is convex because the PSD cone is convex and $F$ is affine.

The $2\times2$ example

$$\begin{pmatrix} t&u\\ u&1 \end{pmatrix} \succeq0 \quad\Longleftrightarrow\quad t\geq u^2$$

is the epigraph of a convex quadratic. The equivalence follows from the Schur complement using the positive pivot $1$. A Schur-complement formula with a singular pivot needs an additional range condition; the invertible formula must not be applied unchanged.

The equality-form semidefinite program is

$$\begin{aligned} (P_{\rm SDP})\qquad \inf_{X\in\operatorname{Herm}(n)}\;& \operatorname{Tr}(CX)\\ \text{subject to }& \operatorname{Tr}(A_iX)=b_i, \quad i=1,\ldots,m,\\ &X\succeq0. \end{aligned}$$

Define

$$\mathcal A(X)_i=\operatorname{Tr}(A_iX).$$

Under the Euclidean pairing on $\mathbb R^m$ and the trace pairing on matrices,

$$\mathcal A^*(y)=\sum_{i=1}^m y_iA_i.$$

The dual is therefore

$$\begin{aligned} (D_{\rm SDP})\qquad \sup_{y\in\mathbb R^m}\;&b^{\mathsf T}y\\ \text{subject to }& S=C-\sum_{i=1}^m y_iA_i\succeq0. \end{aligned}$$

For feasible $X,y,S$, the conic gap identity becomes

$$\operatorname{Tr}(CX)-b^{\mathsf T}y = \operatorname{Tr}(SX) \geq0.$$

Although the product $SX$ need not itself be Hermitian, its trace is real and nonnegative. Moreover,

$$X,S\succeq0, \quad \operatorname{Tr}(SX)=0 \quad\Longleftrightarrow\quad SX=0.$$

Thus zero SDP gap makes the ranges of $X$ and $S$ orthogonal. It does not assert entrywise complementarity and does not imply strict complementarity.

A complete two-by-two certificate

Consider the exact problem

$$\begin{aligned} \text{minimize}\quad&-X_{12}\\ \text{subject to}\quad& X_{11}=1,\qquad X_{22}=1,\qquad X\succeq0, \end{aligned}$$

over real symmetric $2\times2$ matrices. In standard form,

$$C=-\frac12(E_{12}+E_{21}), \qquad A_1=E_{11}, \qquad A_2=E_{22}.$$

The dual is

$$\begin{aligned} \text{maximize}\quad&y_1+y_2\\ \text{subject to}\quad& S=C-y_1E_{11}-y_2E_{22}\succeq0. \end{aligned}$$

An exact primal–dual pair is

$$X^* = \begin{pmatrix} 1&1\\ 1&1 \end{pmatrix}, \qquad y^* = \begin{pmatrix} -\tfrac12\\ -\tfrac12 \end{pmatrix}, \qquad S^* = \frac12 \begin{pmatrix} 1&-1\\ -1&1 \end{pmatrix}.$$

Both matrices are PSD: their eigenvalues are respectively $(2,0)$ and $(1,0)$. The equality constraints hold, the dual slack identity holds, and

$$\operatorname{Tr}(CX^*)=-1 = (b^{\mathsf T}y^*), \qquad S^*X^*=0.$$

Weak duality now proves that both points are optimal and that $X_{12}\leq1$ for every feasible $X$. This is a certificate, not just a candidate solution: every required equality and eigenvalue can be checked by hand.

The hypotheses for the stronger theorem are also visible. The primal has the strictly feasible point $X=I$, and $y=(-1,-1)$ gives

$$S= \begin{pmatrix} 1&-\tfrac12\\ -\tfrac12&1 \end{pmatrix} \succ0.$$

Both Slater conditions hold, so zero gap and attainment were guaranteed before the optimizer was found.

What the missing hypotheses can change

Primal Slater does not guarantee primal attainment

Let

$$B=\frac12(E_{12}+E_{21})$$

and consider

$$\inf\left\{ X_{11}: \operatorname{Tr}(BX)=1,\quad X\succeq0 \right\}.$$

The constraint is $X_{12}=1$. The matrices

$$X_\varepsilon = \begin{pmatrix} \varepsilon&1\\ 1&\varepsilon^{-1} \end{pmatrix}, \qquad \varepsilon>0,$$

are PSD because their determinant is zero and their diagonal entries are positive. They show that the infimum is $0$. It is not attained: if a PSD matrix had $X_{11}=0$, its first row and column would vanish, contradicting $X_{12}=1$.

The primal nevertheless has a strict point, for example

$$\begin{pmatrix} 2&1\\ 1&2 \end{pmatrix} \succ0.$$

Its scalar dual has slack

$$S=E_{11}-yB = \begin{pmatrix} 1&-\tfrac y2\\ -\tfrac y2&0 \end{pmatrix} \succeq0,$$

which forces $y=0$. The dual attains value zero, exactly as the one-sided Slater theorem predicts. It makes no promise that the strictly feasible primal side attains.

Feasibility and attainment do not force zero gap

For a $3\times3$ real symmetric matrix $X$, consider

$$\begin{aligned} \text{minimize}\quad&X_{11}\\ \text{subject to}\quad& X_{22}=0,\\ &X_{11}+2X_{23}=1,\\ &X\succeq0. \end{aligned}$$

PSD together with $X_{22}=0$ forces the second row and column to vanish. Hence $X_{23}=0$, every feasible point has $X_{11}=1$, and the primal attains $p^*=1$ at $\operatorname{diag}(1,0,0)$.

With

$$C=E_{11}, \qquad A_1=E_{22}, \qquad A_2=E_{11}+E_{23}+E_{32}, \qquad b=(0,1),$$

the dual maximizes $y_2$ subject to

$$S=C-y_1A_1-y_2A_2\succeq0.$$

The $(3,3)$ entry of $S$ is zero, so PSD forces its third row and column to vanish. In particular, $S_{23}=-y_2=0$. Thus $d^*=0$, attained for $y_1=y_2=0$. Both problems are feasible and attain, but

$$p^*-d^*=1.$$

Neither side has a strict point: the primal always has $X_{22}=0$, while the dual slack always has $S_{33}=0$. This exact counterexample is why a named qualification must precede any strong-duality claim.

Weak infeasibility can hide behind vanishing residuals

Define a linear map on the real symmetric matrix space by

$$\mathcal A: \mathbb S^2\longrightarrow\mathbb R^2, \qquad \mathcal A \begin{pmatrix} a&z\\ z&d \end{pmatrix} = (a,z).$$

Its image is

$$\mathcal A(\mathbb S_+^2) = \{(a,z):a>0,\ z\in\mathbb R\} \cup\{(0,0)\}.$$

To verify this description, if $a>0$ choose $d=z^2/a$, producing a rank-one PSD matrix. If $a=0$, PSD forces the first row and column to vanish, so $z=0$. The image is therefore not closed.

Take $b=(0,1)$. There is no $X\succeq0$ with $\mathcal A(X)=b$, but

$$X_\varepsilon = \begin{pmatrix} \varepsilon&1\\ 1&\varepsilon^{-1} \end{pmatrix} \succeq0, \qquad \mathcal A(X_\varepsilon) = (\varepsilon,1) \longrightarrow (0,1).$$

Thus the equality residual tends to zero while the cone constraint is satisfied exactly. At the same time, $\|X_\varepsilon\|_2\to\infty$. The target lies in the closure of the conic image but not in the image itself: this is weak infeasibility, and no strict ordinary Farkas separator exists.

This example is a complete warning against the rule “tiny residual plus PSD means feasible.” It also shows why variable magnitude, scaling, and distance to ill-posedness belong beside the residual. The failure of the ordinary SDP Farkas alternative and the role of smaller faces are developed in Liu and Pataki 2015, §§1–3.

Reading finite-precision output

Suppose a numerical procedure returns $(\widehat x,\widehat y,\widehat s)$. With the exact problem data held fixed, define

$$r_p=A\widehat x-b, \qquad r_d=c-A^*\widehat y-\widehat s.$$

The computed objective difference obeys the exact identity

$$\begin{aligned} \widehat g &= \langle c,\widehat x\rangle - \langle\widehat y,b\rangle\\ &= \langle\widehat s,\widehat x\rangle + \langle\widehat y,r_p\rangle + \langle r_d,\widehat x\rangle. \end{aligned}$$

When $r_p=r_d=0$ and both cone-membership tests pass, this reduces to the nonnegative weak-duality gap $\langle\widehat s,\widehat x\rangle$. With residuals present, cancellation can even make a reported objective difference negative.

A minimally informative report keeps the following quantities separate:

1. the primal equality residual $\|r_p\|$;
2. the dual stationarity residual $\|r_d\|$;
3. the cone distances $\operatorname{dist}(\widehat x,K)$ and $\operatorname{dist}(\widehat s,K^*)$;
4. the primal and dual objective values;
5. the complementarity pairing $\langle\widehat s,\widehat x\rangle$;
6. the chosen absolute and relative scalings;
7. variable magnitudes and an applicable conditioning or distance-to-ill-posedness estimate; and
8. arithmetic precision and the independent verification method.

For example, after nondimensionalizing every coordinate with declared reference units and choosing compatible norms and their induced operator norms, one possible dimensionless normalization is

$$\rho_p = \frac{\|A\widehat x-b\|} {1+\|A\|\,\|\widehat x\|+\|b\|},$$

and

$$\rho_d = \frac{\|c-A^*\widehat y-\widehat s\|} {1+\|c\|+\|A^*\|\,\|\widehat y\|+\|\widehat s\|}.$$

A relative objective difference can be reported as

$$\rho_g = \frac{ \left| \langle c,\widehat x\rangle - \langle\widehat y,b\rangle \right| }{ 1+ \left|\langle c,\widehat x\rangle\right| + \left|\langle\widehat y,b\rangle\right| }.$$

These formulas are declared choices, not universal definitions. If the data retain physical units, each bare $1$ must be replaced by a declared same-unit reference scale before unlike quantities are added. Multiplying one constraint by a small number can make its raw residual small without changing its exact solution set. Scaling used internally should therefore be recorded, while final residuals should also be recomputed against the original data.

For an approximate Hermitian matrix $\widehat X$, the spectral-norm distance to the PSD cone is

$$\operatorname{dist}_2( \widehat X,\operatorname{Herm}_+(n)) = \max\{0,-\lambda_{\min}(\widehat X)\}.$$

The Frobenius distance instead combines all negative eigenvalues:

$$\operatorname{dist}_{\rm F}( \widehat X,\operatorname{Herm}_+(n)) = \left( \sum_{\lambda_j(\widehat X)<0} \lambda_j(\widehat X)^2 \right)^{1/2}.$$

The numbers

$$m_X=\lambda_{\min}(\widehat X), \qquad m_S=\lambda_{\min}(\widehat S)$$

are PSD margins. A rigorously positive lower bound certifies positive definiteness; a rigorously negative upper bound certifies failure of PSD. A value close to zero without an eigenvalue error bound is inconclusive. Raw margins are scale dependent, and congruence transformations can change them while preserving exact PSD.

Small backward error means that the candidate exactly solves a nearby problem. Small forward error means that it is close to a solution of the stated problem. Ill-conditioning can separate these notions by many orders of magnitude. The weakly infeasible example above makes the distinction visible without any floating-point arithmetic. Jansson 2009, §§3–4, PDF is the numerical authority used here for verified bounds, conditioning, and rigorous infeasibility checks.

From a numerical candidate to a checked certificate

A proof-oriented verification sequence is:

1. Freeze the intended input data, basis, pairing, cone, objective direction, and primal–dual sign convention.
2. Re-evaluate all primal and dual equalities from serialized certificate data rather than trusting a solver status string.
3. Verify cone membership independently. For rational matrices this can use exact arithmetic and an exact Gram or semidefinite-safe factorization; for analytic or irrational data it can use outward-rounded interval bounds or another justified enclosure.
4. Recompute objective values, the gap identity, complementarity, and PSD margins against the original, unscaled data.
5. Check the qualification actually invoked for strong duality or attainment. If strict feasibility fails, determine whether a smaller face or an extended certificate theorem is required.
6. Preserve the data, precision, tolerances, transformations, and independent result needed to reproduce the conclusion.

For a matrix on the PSD boundary, an ordinary floating-point Cholesky attempt is not a proof. With exact rational data, one can instead exhibit an exact factorization $X=RR^\dagger$, verify all principal minors, or use an equivalent exact semidefinite test. With interval data, the enclosure must account for rounding in both the equalities and the spectral bound.

The resulting claim ladder is strict:

Verified object	Licensed conclusion
Exact primal feasible point	Feasibility and an exact primal upper bound
Exact dual feasible point	An exact dual lower bound
Exact feasible primal–dual pair with equal objectives	Optimality of both points
Exact strict Farkas separator	Strong infeasibility of the stated conic system
Outward-rounded interval verification with all errors enclosed	The theorem supported by that enclosure
Solver status, small residual, small gap, or nearly nonnegative eigenvalues alone	Numerical evidence only

An exact certificate for rounded input data proves a statement about those rounded data. It transfers to intended analytic data only after the data error itself has been bounded in the correct direction.

Stop rules for a finite problem

Stop with an exact finite conclusion only after every datum and certificate condition used in the implication has been verified exactly or with rigorous enclosures. Stop with a bounded numerical statement when only finite-precision residuals, margins, and convergence checks are available. Stop without a feasibility or infeasibility conclusion when the problem is close to ill-posed, the certificate theorem’s hypotheses are unmet, or refinement changes the status without a controlled bound.

The cost of checking a supplied certificate is often much smaller than the cost of finding it, but this is not automatic. Degeneracy, weak infeasibility, large dynamic range, and a feasible set confined to a small face can make both search and verification difficult. Algorithm selection and production solver engineering require specialist optimization methods beyond this page.

From conic certificates to conformal bootstrap

The reusable mathematical pattern behind a scalar crossing exclusion is

$$f_0+\sum_i x_i f_i=0, \qquad x_i\geq0.$$

Here the nonnegative coefficients are supplied physically by unitarity and the chosen normalization; this page does not derive those facts. For a finite declared reduction, setting $b=-f_0$ turns feasibility into membership in its conic image. For the exact OPE sum, the function-space topology and convergence are part of the statement: in general $b$ lies in the closure or completion of the algebraic conic hull, and replacing that closure by the cone itself requires a closedness theorem. A separating functional $\alpha$ with

$$\alpha(f_i)\geq0 \quad\text{for every allowed }i, \qquad \alpha(-f_0)<0$$

gives a contradiction. Equivalently, normalize $\alpha(f_0)=1$ and obtain

$$0 = \alpha(f_0) + \sum_i x_i\alpha(f_i) >0.$$

Matrix-valued positive sectors replace some coefficients $x_i\geq0$ by PSD matrices and lead to semidefinite rather than purely polyhedral constraints. The conic meaning is unchanged: a correctly verified dual functional is an exclusion certificate for the declared assumptions. A convex-cone crossing formulation appears in Rattazzi, Rychkov, Tonni, and Vichi 2008, §§4–5.2; the polynomial-matrix to SDP translation appears in Simmons-Duffin 2015, §§2.1–2.4.

The finite reduction still has a direction that must be checked:

• Applying finitely many exact continuous linear functionals, with their termwise action on the convergent crossing sum justified, gives a necessary finite system. If that system is rigorously infeasible and positivity has been verified over the entire declared allowed sector, the assumptions are excluded.
• Replacing an infinite generator set by a finite sample usually gives an inner approximation. Failure of membership in that smaller cone does not by itself exclude membership in the full cone.
• An outer approximation can support exclusion when the target lies outside it, but membership in the outer cone does not prove membership in the exact cone.
• Rational, polynomial, derivative, spin, or spectral truncations inherit exact claim language only when their approximation errors and tail directions are controlled.

Even an exactly feasible finite crossing problem does not construct a CFT. It does not supply an operator algebra, all correlators, OPE convergence, crossing in every channel, or consistency at all truncation orders. Likewise, failure to find a separator is not an existence theorem.

From Crossing Equations to Convex Optimization develops the positivity gate, normalization, truncation, and physical claim boundary. Linear Functionals and Positivity develops the functional domain and sector-by-sector sign check, while Solver Certificates and Independent Verification develops the physical workflow for preserving and rechecking solver outputs.

Common pitfalls

Omitting the closure in conic Farkas. A closed cone can have a nonclosed linear image. The ordinary strict certificate detects $b\notin\overline{A(K)}$, not every point of $\overline{A(K)}\setminus A(K)$.

Treating convexity as strong duality. Convexity gives the geometry behind duality, and weak duality follows directly from cone positivity. Zero gap and attainment need a separate theorem with verified hypotheses.

Reversing the one-sided Slater conclusion. Primal strict feasibility guarantees dual attainment under the finite-value hypothesis; it does not guarantee primal attainment. The dual statement is reversed.

Checking only the objective gap. With nonzero primal or dual residuals, the reported objective difference contains residual terms. Feasibility, cone membership, and complementarity must be checked separately.

Calling a small negative eigenvalue “PSD within tolerance.” That phrase is a numerical policy, not an exact cone statement. Report the eigenvalue enclosure, scale, norm, and implication actually justified.

Using determinant alone as a PSD test. For a $2\times2$ Hermitian matrix, principal minors give a short test. In higher dimension, a nonnegative determinant alone says almost nothing about the signs of the individual eigenvalues.

Promoting nonexclusion to existence. A primal point for one finite relaxation shows only what the declared finite system supports. It does not construct a quantum field theory.

What this method now permits

Given finite-dimensional data, one can now:

• put the problem into the declared conic pair $Ax=b$, $x\in K$ and $A^*y+s=c$, $s\in K^*$;
• derive weak duality without guessing a transpose or sign;
• specialize the pair to the PSD cone and verify an exact SDP certificate;
• determine whether a Farkas separator addresses infeasibility or only strong infeasibility;
• state the exact Slater condition used for zero gap and the side whose optimum it guarantees to attain; and
• separate residuals, cone violations, gaps, PSD margins, scaling, conditioning, and finite-precision limitations before drawing a conclusion.

The physical continuation is the conformal-crossing optimization problem. The independent Hilbert-space branch begins instead at Banach and Hilbert Spaces, Completion, and Riesz Representation; it is not a prerequisite for this finite-dimensional route.

Exercises

Recover the dual and its sign

Starting from

$$\inf\{\langle c,x\rangle:Ax=b,\ x\in K\},$$

derive the dual using the Lagrangian $L(x,y)=\langle c,x\rangle+\langle y,b-Ax\rangle$. Explain why the condition is $c-A^*y\in K^*$ rather than its negative.

Solution

The Lagrangian is

$$L(x,y) = \langle y,b\rangle + \langle c-A^*y,x\rangle.$$

If $c-A^*y\in K^*$, its pairing with every $x\in K$ is nonnegative, and the infimum over the cone is attained at $x=0$ with value $\langle y,b\rangle$. If the covector is outside $K^*$, there is an $x_0\in K$ with negative pairing; scaling $tx_0$ sends the infimum to $-\infty$. Hence the dual maximizes $\langle y,b\rangle$ subject to $c-A^*y\in K^*$.

Diagnose the weakly infeasible matrix system

For

$$\mathcal A \begin{pmatrix} a&z\\ z&d \end{pmatrix} =(a,z),$$

show directly that $b=(0,1)$ is not in $\mathcal A(\mathbb S_+^2)$ but is in its closure. Why can no covector $q$ satisfy both $\mathcal A^*q\succeq0$ and $q^{\mathsf T}b<0$?

Solution

If $a=0$ in a PSD matrix, its first row and column vanish, so $z=0$; therefore $(0,1)$ is not in the image. The rank-one matrices

$$\begin{pmatrix} \varepsilon&1\\ 1&\varepsilon^{-1} \end{pmatrix}$$

map to $(\varepsilon,1)$, which converges to $(0,1)$, so the target is in the closure.

Writing $q=(q_1,q_2)$ gives

$$\mathcal A^*q = \begin{pmatrix} q_1&q_2/2\\ q_2/2&0 \end{pmatrix}.$$

PSD with a zero lower-right diagonal entry forces $q_2=0$. But $q^{\mathsf T}b=q_2$, so it cannot be negative.

Transfer the certificate to a crossing equation

Suppose an exact finite projection of a normalized unitary crossing equation has the form

$$f_0+\sum_i x_if_i=0, \qquad x_i\geq0.$$

State a functional condition that excludes the assumed spectrum. Then state two facts that this exclusion does not prove.

Solution

A functional satisfying

$$\alpha(f_0)=1, \qquad \alpha(f_i)\geq0 \quad\text{for every allowed }i$$

would turn the crossing equation into

$$0 = 1+\sum_i x_i\alpha(f_i) >0,$$

a contradiction. The sign condition must cover every allowed sector, not only sampled generators.

The certificate does not prove that a spectrum not excluded by this projection belongs to a CFT, and it does not control the continuum problem unless the projection, positivity representation, approximation, and tails have the required one-sided error bounds.

References

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, PDF, Chapters 2, 4, and 5 and §§11.7.1–11.7.3, Cambridge University Press, 2004. These chapters and sections develop convex sets and cones, separation, semidefinite programs, Lagrange duality, theorems of alternatives, Slater conditions, and residual-aware optimization language. Its real-coordinate notation is translated to the typed dual pairings used here.
• Christian Jansson, “On Verified Numerical Computations in Convex Programming”, PDF, Japan Journal of Industrial and Applied Mathematics 26 (2009), 337–363. This is the numerical reliability source for rounding error, conditioning, interval verification, rigorous bounds, and the distinction between an approximate solver result and a verified conic conclusion.
• Minghui Liu and Gábor Pataki, “Exact Duality in Semidefinite Programming Based on Elementary Reformulations”, SIAM Journal on Optimization 25 (2015), 1441–1454, especially §§1–3. This is the specialist source for nonpolyhedral duality pathologies, weak infeasibility, facial reduction, and why the simplest SDP Farkas certificate can fail.
• Riccardo Rattazzi, Vyacheslav S. Rychkov, Erik Tonni, and Alessandro Vichi, “Bounding Scalar Operator Dimensions in 4D CFT”, Journal of High Energy Physics 2008(12), 031, especially §§4–5.2. These sections formulate the crossing sum rule, positivity of squared OPE coefficients, the convex-cone geometry, and finite functional projections. Its physical formulation is only summarized here and is developed in Volume 9.
• David Simmons-Duffin, “A Semidefinite Program Solver for the Conformal Bootstrap”, Journal of High Energy Physics 2015(06), 174, especially §§2.1–2.4. This is a QFT-application and computational source for translating polynomial matrix positivity into SDP form, primal–dual gaps, and finite-precision termination quantities. Solver design and the paper’s application-specific status language are not imported into this theorem-led page.
• Lieven Vandenberghe and Stephen Boyd, “Semidefinite Programming”, SIAM Review 38 (1996), 49–95, especially §§1 and 3. This is the structural SDP authority for LMIs, the PSD trace pairing, primal–dual formulations, complementarity, and strict-feasibility qualifications.