Normalized Hermitian inequality SDPs have equal primal and dual values

If $n=0$, there is one matrix $X$, all traces are zero, and primal nonemptiness implies $b_j\ge 0$ for every $j$. The primal singleton is compact with optimum $0$, while every $y\ge 0$ is dual feasible and $b\cdot y\ge 0$, with equality at $y=0$. The vector $q_1=m+1$, $q_j=1$ for $j\ge 2$ is strictly positive and its empty matrix slack is positive definite in the quadratic-form sense, since there is no nonzero vector. Thus all conclusions hold. Henceforth assume $n\ge 1$.

Regard the Hermitian matrices $H_n$ as a real space with coordinates the $n$ real diagonal entries and the real and imaginary parts above the diagonal, giving ${\mathbb{R}}^{n^2}$. Direct diagonal summation yields $\mathrm{tr}(UV)={\sum }_i{U}_{ii}{V}_{ii}+2{\sum }_{i<j}\mathrm{Re}(U_{ij}\overline{V_{ij}})$ for Hermitian $U,V$. This is a real inner product, with norm $\mathrm{\parallel }U{\mathrm{\parallel }}_F=({\sum }_{i,j}\mathrm{\mid }{U}_{ij}{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$; all finite linear maps below are continuous in these coordinates. The cone $K=\{X\in H_n:X⪰0\}$ is convex and closed, being the intersection over $v\in {\mathbb{C}}^n$ of the closed real half-spaces $v^{\ast }Xv\ge 0$.

Direct summation gives $\mathrm{tr}(Dv{v}^{\ast })=v^{\ast }Dv$. For $X\in K$, write $X={\sum }_i{\lambda }_i{v}_i{v}_i^{\ast }$ in an orthonormal eigenbasis, with ${\lambda }_i\ge 0$. Then $\mathrm{tr}(X)={\sum }_i{\lambda }_i$ and $\mathrm{\parallel }X{\mathrm{\parallel }}_F^2=\mathrm{tr}(X^2)={\sum }_i{\lambda }_i^2$, so $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le \mathrm{tr}(X)$. For $D\in K$, $\mathrm{tr}(DX)={\sum }_i{\lambda }_i{v}_i^{\ast }D{v}_i\ge 0$. Conversely, a Hermitian $D$ pairing nonnegatively with every $X\in K$ has $v^{\ast }Dv\ge 0$ by testing $X=v{v}^{\ast }$, so $D\in K$. Thus $K$ is self-dual for the real trace pairing. If $D$ is Hermitian with $\mathrm{\parallel }D\mathrm{\parallel }\le 1$, [F4] gives $\mathrm{\mid }{v}^{\ast }Dv\mathrm{\mid }\le \mathrm{\parallel }v{\mathrm{\parallel }}^2$, whence $-I⪯D⪯I$ and $\mathrm{\mid }\mathrm{tr}(DX)\mathrm{\mid }\le \mathrm{tr}(X)$ for $X\in K$.

The first constraint gives $0\le \mathrm{tr}(X)\le R$ for every primal feasible $X$. That feasible set is nonempty, closed by step 1.2 and continuity of its finitely many constraints, and bounded by $\mathrm{\parallel }X{\mathrm{\parallel }}_F\le R$. Hence [F5] and [F7] give compactness and attainment of the primal maximum. Step 2.1 with $D=C$ gives $\mathrm{\mid }\mathrm{tr}(CX)\mathrm{\mid }\le R$, so $p^{\ast }\in [-R,R]$.

Set $q_1=m+1$ and $q_j=1$ for $j\ge 2$. Step 2.1 gives $S_0:={\sum }_j{q}_j{A}_j-C⪰((m+1)-(m-1)-1)I=I$, so $q$ has strictly positive coordinates and positive definite matrix slack. For primal feasible $X$ and dual feasible $y$, self-duality gives $b\cdot y-\mathrm{tr}(CX)={\sum }_j{y}_j(b_j-\mathrm{tr}(A_{j}X))+\mathrm{tr}(({\sum }_j{y}_j{A}_j-C)X)\ge 0$. Thus $p^{\ast }\le d^{\ast }\le b\cdot q$, and the dual infimum is finite.

Put $A(X)=(\mathrm{tr}(A_{j}X){)}_j$ and $\mathrm{\Phi }(X,s,a)=(A(X)+s,\mathrm{tr}(CX)-a)$. The image $S=\mathrm{\Phi }(K\times {\mathbb{R}}_{+}^m\times {\mathbb{R}}_{+})$ is a nonempty convex cone containing $(0,0)$. To prove it closed, fix $z=(u,t)\in \bar{S}$ and the open neighborhood $V=\{(u^{\mathrm{\prime }},t^{\mathrm{\prime }}):\mathrm{\mid }{u}_j^{\mathrm{\prime }}-u_j\mathrm{\mid }<1\text{ for all }j,\mathrm{\mid }{t}^{\mathrm{\prime }}-t\mathrm{\mid }<1\}$. For every point of $S\cap V$ and every witness $(X,s,a)$, step 4.1 gives $\mathrm{tr}(X)+{\sum }_j{s}_j+a\le \mathrm{tr}(S_{0}X)+q\cdot s+a=q\cdot u^{\mathrm{\prime }}-t^{\mathrm{\prime }}\le {\sum }_j{q}_j(\mathrm{\mid }{u}_j\mathrm{\mid }+1)+\mathrm{\mid }t\mathrm{\mid }+1$. With $B={\sum }_j{q}_j(\mathrm{\mid }{u}_j\mathrm{\mid }+1)+\mathrm{\mid }t\mathrm{\mid }+2$, all these witnesses belong to the closed bounded set $E=\{(X,s,a):X\in K,\mathrm{tr}(X)\le B,0\le s_j\le B,0\le a\le B\}$ in ${\mathbb{R}}^{n^2+m+1}$. By [F5] and [F6], $\mathrm{\Phi }(E)$ is compact and closed, and $S\cap V\subseteq \mathrm{\Phi }(E)\subseteq S$. Every neighborhood $U$ of $z$ has $U\cap V$ meeting $S$, so [F8] gives $z\in \overline{S\cap V}\subseteq \mathrm{\Phi }(E)\subseteq S$. Thus $S$ is closed; no sequence of witness selections was used.

Fix $\gamma >p^{\ast }$. If $A(X)+s=b$ with $X\in K,s\ge 0$, then $X$ is primal feasible and $\mathrm{tr}(CX)-a\le p^{\ast }<\gamma$ for $a\ge 0$. Hence $(b,\gamma )\mathrm{\notin }S$. By [F9] there are $w\in {\mathbb{R}}^m$ and $\alpha ,\beta \in \mathbb{R}$ with $w\cdot u+\alpha t\le \beta <w\cdot b+\alpha \gamma$ for every $(u,t)\in S$. The points $(0,-a)\in S$ for all $a\ge 0$ force $\alpha \ge 0$. Fix one primal feasible $X_f$ and set $s_f=b-A(X_f)\ge 0$; then $(b,\mathrm{tr}(C{X}_f))\in S$. If $\alpha =0$, that point gives the contradiction $w\cdot b\le \beta <w\cdot b$. Thus $\alpha >0$, using no strictness of $X_f$ or its scalar inequalities.

The coordinate rays $(s,0)\in S$ force $w_j\le 0$. Scaling $(A(X),\mathrm{tr}(CX))\in S$ by arbitrarily large nonnegative scalars forces $\mathrm{tr}(({\sum }_j{w}_j{A}_j+\alpha C)X)\le 0$ for every $X\in K$. Self-duality therefore makes $y=-w\mathrm{/}\alpha \ge 0$ dual feasible. Since $(0,0)\in S$, separation gives $0\le \beta <w\cdot b+\alpha \gamma$, so $b\cdot y<\gamma$. Consequently every $\gamma >p^{\ast }$ exceeds some dual feasible objective. If $d^{\ast }>p^{\ast }$, taking $\gamma =(p^{\ast }+d^{\ast })\mathrm{/}2$ contradicts the definition of $d^{\ast }$. Thus $d^{\ast }\le p^{\ast }$, and weak duality gives equality. Step 3.1 supplies primal attainment and the interval. An additionally promised optimal dual witness satisfies $b\cdot y^{\ast }=d^{\ast }=p^{\ast }$ and retains its promised norm bound.