Finite real semidefinite programs satisfy strong duality under strict feasibility

The cone $K=\{X\in {\mathbb{S}}^n:X⪰0\}$ is convex and closed because it is the intersection, over $v\in {\mathbb{R}}^n$, of the closed half-spaces $v^{T}Xv\ge 0$. It is self-dual for $⟨\cdot ,\cdot {⟩}_F$: if $X,Y⪰0$, diagonalize $X={\sum }_j{\lambda }_j{u}_j{u}_j^T$ by [F2], with ${\lambda }_j\ge 0$, to get $⟨X,Y{⟩}_F={\sum }_j{\lambda }_j{u}_j^{T}Y{u}_j\ge 0$; conversely, $⟨X,v{v}^T{⟩}_F=v^{T}Xv\ge 0$ for every $v$ implies $X⪰0$.

If $X$ is primal feasible and $y$ dual feasible, then $b^{T}y-⟨C,X{⟩}_F=⟨A^{\ast }y-C,X{⟩}_F\ge 0$ by self-duality in step 1.1. Thus weak duality gives $p^{\ast }\le d^{\ast }$.

Define $S=\{(A(X),⟨C,X{⟩}_F-r):X\in K,r\ge 0\}\subseteq {\mathbb{R}}^m\times \mathbb{R}$. This set is nonempty and convex by linearity and convexity of $K$. To prove it closed without making countably many witness choices, take any $z=(u,t)$ in the closure of $S$ and let $V=\{(u^{\mathrm{\prime }},t^{\mathrm{\prime }}):\mathrm{\parallel }{u}^{\mathrm{\prime }}-u\mathrm{\parallel }<1,\mathrm{\mid }{t}^{\mathrm{\prime }}-t\mathrm{\mid }<1\}$, an open neighborhood of $z$. For any point $(u^{\mathrm{\prime }},t^{\mathrm{\prime }})\in S\cap V$, a witness $X⪰0,r\ge 0$ satisfies $A(X)=u^{\mathrm{\prime }}$ and $t^{\mathrm{\prime }}=⟨C,X{⟩}_F-r$. Let $S_0=A^{\ast }{y}_0-C\succ 0$ be the strict dual slack and choose $\delta >0$ with $S_0⪰\delta I$ by [F2]. Self-duality from step 1.1 and $r\ge 0$ give $\delta \mathrm{tr}(X)\le ⟨S_0,X{⟩}_F=y_0^T{u}^{\mathrm{\prime }}-⟨C,X{⟩}_F\le y_0^T{u}^{\mathrm{\prime }}-t^{\mathrm{\prime }}$. Since $(u^{\mathrm{\prime }},t^{\mathrm{\prime }})\in V$, [F12] bounds the right side above by $\mathrm{\mid }{y}_0^{T}u\mathrm{\mid }+\mathrm{\parallel }{y}_0\mathrm{\parallel }+\mathrm{\mid }t\mathrm{\mid }+1$. Choose $B>0$ larger than this bound divided by $\delta$. Writing the nonnegative eigenvalues of $X$ as ${\lambda }_j$, [F2,F6] give $\mathrm{tr}(X)={\sum }_j{\lambda }_j$ and $\mathrm{\parallel }X{\mathrm{\parallel }}_F=({\sum }_j{\lambda }_j^2{)}^{1\mathrm{/}2}\le {\sum }_j{\lambda }_j$, so by [F2,F6], $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le \mathrm{tr}(X)\le B$; [F12] applied to the Frobenius pairing then gives $0\le r=⟨C,X{⟩}_F-t^{\mathrm{\prime }}\le \mathrm{\parallel }C{\mathrm{\parallel }}_{F}B+\mathrm{\mid }t\mathrm{\mid }+1$. Thus $S\cap V$ lies in the image under the continuous map $\mathrm{\Phi }(X,r)=(A(X),⟨C,X{⟩}_F-r)$ of the closed bounded set $\{(X,r):X⪰0,\mathrm{tr}(X)\le B,0\le r\le R\}$ for $R=\mathrm{\parallel }C{\mathrm{\parallel }}_{F}B+\mathrm{\mid }t\mathrm{\mid }+1$. This set is compact by [F5], so its image is compact by [F7] and closed by [F8]. Because that image is contained in $S$, and [F11] gives $z$ in the closure of $S\cap V$ (as $V$ is a neighborhood of $z$), it follows that $z\in S$. Hence $S$ is closed.

Fix any $\gamma >p^{\ast }$. The point $(b,\gamma )$ lies outside $S$, since $A(X)=b$ implies $⟨C,X{⟩}_F\le p^{\ast }<\gamma$ and subtracting $r\ge 0$ cannot increase it. By closedness in step 2.2 and [F3], there are $y\in {\mathbb{R}}^m$, $\alpha \in \mathbb{R}$, and $\beta \in \mathbb{R}$ such that $y^{T}u+\alpha t\le \beta <y^{T}b+\alpha \gamma$ for every $(u,t)\in S$. Taking $X=0$ and arbitrarily large $r$ shows $\alpha \ge 0$. If $\alpha =0$, the strict primal point $X_0$ has $A(X_0)=b$, contradicting $y^{T}b\le \beta <y^{T}b$; hence $\alpha >0$. Taking $(u,t)=(A(sX),⟨C,sX{⟩}_F)$ for arbitrary $X\in K,s\ge 0$ shows $⟨A^{\ast }y+\alpha C,X{⟩}_F\le 0$ for all $X\in K$. By the defining adjoint identity [F4] and self-duality, $y^{\mathrm{\prime }}=-y\mathrm{/}\alpha$ satisfies $A^{\ast }{y}^{\mathrm{\prime }}-C⪰0$. Since $(0,0)\in S$, $0\le \beta <y^{T}b+\alpha \gamma$, so $b^T{y}^{\mathrm{\prime }}=-y^{T}b\mathrm{/}\alpha <\gamma$.

Step 3.1 gives dual feasible values below every $\gamma >p^{\ast }$, hence $d^{\ast }\le p^{\ast }$; weak duality in step 2.1 gives equality. For primal attainment, let $c_0=⟨C,X_0{⟩}_F$ and consider $P=\{X⪰0:A(X)=b,⟨C,X{⟩}_F\ge c_0\}$. It is nonempty because $X_0\in P$, and closed by step 1.1 and continuity. For $S_0=A^{\ast }{y}_0-C\succ 0$, choose $\delta >0$ with $S_0⪰\delta I$. Every $X\in P$ satisfies $\delta \mathrm{tr}(X)\le ⟨S_0,X{⟩}_F=y_0^{T}b-⟨C,X{⟩}_F\le y_0^{T}b-c_0$, and the same eigenvalue calculation as in step 2.2 gives $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le \mathrm{tr}(X)$, so $P$ is bounded. By [F5], $P$ is compact, and [F9] makes the continuous objective attain a maximum there. Since the attained maximum is at least $c_0$, no feasible point outside $P$ can improve it; it equals $p^{\ast }$. For dual attainment, if $m=0$, the only dual variable is the given feasible $y_0=0$ and it attains $d^{\ast }$. Assume $m\ge 1$, let $K=(\ker A^{\ast }{)}^{\perp }$, and use [F10] to decompose each $y\in {\mathbb{R}}^m$ uniquely as $y=z+k$ with $z\in K$ and $k\in \ker A^{\ast }$. Since $b=A(X_0)$, $b^{T}k=k^{T}A(X_0)=⟨A^{\ast }k,X_0{⟩}_F=0$; thus projection to $z$ preserves both $A^{\ast }y$ and $b^{T}y$. The set $D=\{z\in K:A^{\ast }z-C⪰0,b^{T}z\le b^T{y}_0\}$ is nonempty (it contains the projection of $y_0$) and closed: $K$ is the intersection of the closed hyperplanes perpendicular to vectors in $\ker A^{\ast }$, and the PSD cone is closed by step 1.1. Put $T=A^{\ast }z-C$. Since $X_0\succ 0$, choose $\eta >0$ with $X_0⪰\eta I$; for $z\in D$, $\eta \mathrm{tr}(T)\le ⟨T,X_0{⟩}_F=b^{T}z-c_0\le b^T{y}_0-c_0$. The same eigenvalue calculation as in step 2.2 gives $\mathrm{\parallel }T{\mathrm{\parallel }}_F\le \mathrm{tr}(T)$, so $T$ is bounded and hence so is $A^{\ast }z=T+C$. On the unit sphere of $K$, the continuous function $z\mapsto \mathrm{\parallel }{A}^{\ast }z\mathrm{\parallel }$ is strictly positive because $K\cap \ker A^{\ast }=\{0\}$. The sphere is compact by [F5], so [F9] gives a positive minimum $\mu$; therefore $\mathrm{\parallel }{A}^{\ast }z\mathrm{\parallel }\ge \mu \mathrm{\parallel }z\mathrm{\parallel }$ for all $z\in K$, and $D$ is bounded. (If $K=\{0\}$, boundedness is immediate.) Thus $D$ is compact by [F5], and [F9] makes $b^{T}z$ attain its minimum on $D$. Any dual feasible point with objective above $b^T{y}_0$ cannot lower this minimum, while every other dual feasible point projects into $D$ without changing its objective. Hence this minimum equals $d^{\ast }$ and is attained.