5 Convex Structure
This chapter follows the convex-optimization framework of [ Wol12 , Chapter 4 ] .
Let \(V\) and \(V'\) be finite-dimensional real Hilbert spaces, let \(K\subseteq V\) be a closed pointed convex cone with nonempty interior, let \(T:V\to V'\) be linear, and fix \(c\in V\) and \(b\in V'\). As in [ Wol12 , Chapter 4, equations (4.1)–(4.2) ] , define the dual cone, the primal and dual feasible sets, and their values by
The values belong to the extended real line. The conventions are \(\inf \varnothing =+\infty \) and \(\sup \varnothing =-\infty \); an objective unbounded below has infimum \(-\infty \), and one unbounded above has supremum \(+\infty \). The nonempty-interior assumption is Wolf’s convention for a conic program; the definitions and weak duality do not require it.
Following [ Wol12 , Chapter 4, lines 72–78 ] , the primal problem is strictly feasible when there is an \(x\in \operatorname {int}K\) with \(T(x)=b\). The dual problem is strictly feasible when there is a \(y\in V'\) such that \(c-T^*(y)\in \operatorname {int}K^*\). A primal optimizer is an \(x^0\in \mathcal F_p\) satisfying \(\langle c|x^0\rangle \leq \langle c|x\rangle \) for every \(x\in \mathcal F_p\); a dual optimizer is a \(y^0\in \mathcal F_d\) satisfying \(\langle b|y\rangle \leq \langle b|y^0\rangle \) for every \(y\in \mathcal F_d\).
For every \(x\in \mathcal F_p\) and \(y\in \mathcal F_d\), \(\langle b|y\rangle \leq \langle c|x\rangle \). Consequently, \(C_d\leq C_p\) with the extended-real conventions of Definition 5.1.
Dual feasibility and \(x\in K\) give
This is the pointwise inequality. Taking the supremum over \(y\in \mathcal F_d\) and then the infimum over \(x\in \mathcal F_p\) proves \(C_d\leq C_p\).
If \(x\in \mathcal F_p\), \(y\in \mathcal F_d\), and \(\langle c|x\rangle =\langle b|y\rangle \), then \(x\) and \(y\) are primal and dual optimizers, respectively, and \(C_p=C_d=\langle c|x\rangle =\langle b|y\rangle \).
For any \(z\in \mathcal F_p\) and \(w\in \mathcal F_d\), weak duality gives \(\langle b|w\rangle \leq \langle c|x\rangle =\langle b|y\rangle \leq \langle c|z\rangle \). Hence \(x\) minimizes the primal objective and \(y\) maximizes the dual objective. Taking the corresponding infimum and supremum gives the asserted value equality.
If \(\mathcal F_p\) is nonempty and \(p\in \mathbb {R}\), then \(C_p=p\) in the extended real line if and only if \(p\) is the greatest lower bound of \(\{ \langle c|x\rangle :x\in \mathcal F_p\} \). If \(\mathcal F_d\) is nonempty, then \(C_d=p\) if and only if \(p\) is the least upper bound of \(\{ \langle b|y\rangle :y\in \mathcal F_d\} \).
The embedding \(\mathbb {R}\to \overline{\mathbb {R}}\) preserves and reflects order. Thus the defining extended-real infimum is \(p\in \mathbb {R}\) exactly when \(p\) is a lower bound of all real objective values and every other real lower bound is at most \(p\). The supremum statement is the order-dual argument.
The finiteness hypotheses below correct the attainment sentences printed at lines 72–78 of [ Wol12 , Chapter 4 ] ; the counterexamples to the unqualified statements are recorded in [ con26h ] . Suppose the primal problem is strictly feasible and \(C_p\in \mathbb R\). Then \(C_p=C_d\) and there is a dual optimizer \(y^0\in \mathcal F_d\) with \(\langle b|y^0\rangle =C_d\). Dually, if the dual problem is strictly feasible and \(C_d\in \mathbb R\), then \(C_p=C_d\) and there is a primal optimizer \(x^0\in \mathcal F_p\) with \(\langle c|x^0\rangle =C_p\).
Write the primal problem in the form \(\inf \{ \langle d|x\rangle :x\in C,\ A(x)=r\} =p\) and consider the convex set
The map \((x,s)\mapsto (A(x),\langle d|x\rangle +s)\) onto \(\operatorname {ran}(A)\times \mathbb {R}\) is open. Strict feasibility therefore gives \(D\) nonempty interior. The greatest-lower-bound property places \((r,p)\) in \(\overline D\setminus \operatorname {int}D\), so a separating functional \(f\) satisfies \(f\leq 0\) on \(D\) and \(f(r,p)=0\). If \(\alpha =f(0,1)\) vanished, the image under \(f\) of an interior point of \(D\) would make \(0\) an interior point of \((-\infty ,0]\), a contradiction. Hence \(\alpha {\lt}0\), and normalization by \(-\alpha \) gives \(y\) such that, for every \(x\in C\),
For \(C=K\), \(A=T\), \(d=c\), and \(r=b\), (7) is dual feasibility and dual attainment. For the converse direction, write the dual as a primal problem on \(V'\times K^*\) with equality map \((y,z)\mapsto T^*(y)+z\) and objective \(\langle -b|y\rangle \). The same separation argument gives \(x\) with \(T(-x)=b\) and \(-x\in K^{**}=K\), hence a primal optimizer. Weak duality then gives equality of the two extended-real values in both cases.
The Hermitian \(n\times n\) matrices form a finite-dimensional real Hilbert space for Wolf’s trace pairing \(\langle A|B\rangle =\operatorname {Re}\operatorname{tr}(AB)\). Its positive-semidefinite matrices form a closed proper cone \(K_{\mathrm{psd}}\) satisfying \(K_{\mathrm{psd}}^*=K_{\mathrm{psd}}\), and \(\operatorname {int}K_{\mathrm{psd}}=\{ A:A{\gt}0\} \). The last identity also covers the zero-dimensional matrix space, where positive definiteness is vacuous and the cone is the whole space.
For Hermitian data \(F_i\), the traces \(\operatorname{tr}(F_iX)\) are real; define \(T(X)_i=\operatorname{tr}(F_iX)\). Then \(T^*(y)=\sum _i y_iF_i\). Consequently the conic primal constraint is precisely \(X\geq 0\) and \(\operatorname{tr}(F_iX)=b_i\), while conic dual feasibility is precisely \(F_0-\sum _i y_iF_i\geq 0\). The two conic strict-feasibility predicates become, respectively, \(X{\gt}0\) with the trace constraints and \(F_0-\sum _i y_iF_i{\gt}0\), exactly as in [ Wol12 , Chapter 4, lines 85–105 ] .
For every feasible \(X\) and \(y\),
Taking the supremum and infimum gives Wolf’s semidefinite weak-duality inequality, equation (4.3), with the extended-real conventions of Definition 5.1. If there is a strictly feasible \(X{\gt}0\) and the primal value is finite, equality holds and the dual optimum is attained. Dually, a strictly positive slack and a finite dual value give equality and primal attainment. These finiteness hypotheses are the correction required for the unqualified printed claim at lines 100–105.
Let \(b\in \mathbb {R}^n\) and let \(F_0,F_1,\ldots ,F_n\) be Hermitian matrices. Suppose that \(X^0\geq 0\), \(\operatorname{tr}(F_iX^0)=b_i\) for every \(i\), \(F_0-\sum _i y_i^0F_i\geq 0\), and the two objective values are equal. Then, as in [ Wol12 , Chapter 4, equation (4.4) ] ,
Thus \(X^0\) and \(F_0-\sum _i y_i^0F_i\) have orthogonal supports. Under equality of the conic values and primal attainment, a dual vector \(y^0\) is optimal if and only if there is a primal-feasible \(X^0\geq 0\) satisfying this equation and the dual slack is positive semidefinite, as stated at lines 113–116.
The equality constraints and equality of the objectives give \(\operatorname{tr}((F_0-\sum _i y_i^0F_i)X^0)=0\). If two positive semidefinite matrices have zero trace pairing, the product of their positive square roots has zero Hilbert–Schmidt norm; hence their product and the product of their support projections vanish. This proves (9) and the support statement. For the optimizer characterization, choose a primal optimizer. Equality of the two values identifies its objective with that of every dual optimizer, so complementary slackness applies. Conversely, the vanishing product forces the trace pairing, hence the objective gap, to vanish; pointwise weak duality then makes both feasible points optimizers.