关于SDP的凸性与拉格朗日函数

Boyd的书中给出了凸优化最基本的标准定义如下：

minimize ⁡ f 0 ( x )  subject to  f i ( x ) ⩽ 0 , i = 1 , ⋯   , m h i ( x ) = 0 , i = 1 , ⋯   , p \begin{array}{ll} \operatorname{minimize} & f_{0}(x) \\ \text { subject to } & f_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p \end{array} minimize subject to ​f0​(x)fi​(x)⩽0,i=1,⋯,mhi​(x)=0,i=1,⋯,p​
其中 f f f为凸函数， h h h为仿射函数。而同时我们知道SDP的最简单形式如下：
minimize ⁡ f 0 ( x )  subject to  X ⪰ 0 \begin{array}{ll} \operatorname{minimize} & f_{0}(x) \\ \text { subject to } & X \succeq 0 \end{array} minimize subject to ​f0​(x)X⪰0​
并且知道这也是一个凸问题。为什么呢？根据半正定的定义， X ⪰ 0 X \succeq 0 X⪰0表示， ∀ y \forall y ∀y，有 y H X y ≥ 0 y^HXy\ge 0 yHXy≥0。对于每一个给定的 y y y， y H X y ≥ 0 → ∑ i ∑ j y i ∗ y j x i j ≥ 0 y^HXy\ge 0\rightarrow\sum_i\sum_jy_i^*y_jx_{ij}\ge0 yHXy≥0→∑i​∑j​yi∗​yj​xij​≥0无疑是一个关于 X X X的仿射约束，那么无疑是一个凸函数。因此 X ⪰ 0 X \succeq 0 X⪰0 实质上是无数个凸函数约束 (因为要对所有 y y y均成立)。尽管是无穷多的约束，但每个约束都是凸的不等式约束，故而符合凸优化的基本定义。

同时我们知道，拉格朗日函数定义如下：
L ( x , λ , ν ) = f 0 ( x ) + ∑ i = 1 m λ i f i ( x ) + ∑ i = 1 p ν i h i ( x ) L(x, \lambda, \nu)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x) L(x,λ,ν)=f0​(x)+i=1∑m​λi​fi​(x)+i=1∑p​νi​hi​(x)
一言以蔽之即通过拉格朗日乘子将限制条件写入到目标函数之中。那么如何对SDP问题写出其拉格朗日函数呢？

正如上面的分析，对于给定的 y y y，限制条件为 y H X y ≥ 0 y^HXy\ge 0 yHXy≥0，那么对其可以引入拉格朗日乘子 λ ≥ 0 \lambda\ge 0 λ≥0，在目标函数中加入 λ y H X y \lambda y^HXy λyHXy这一项。那么对所有的 y y y都这么操作的话，拉格朗日函数就可以写为：
L ( x , λ 1 , ⋯   , ) = f 0 ( x ) + ∑ n λ n y n H X y n L(x, \lambda_1, \cdots, )=f_{0}(x) + \sum_n \lambda_n y_n^HXy_n L(x,λ1​,⋯,)=f0​(x)+n∑​λn​ynH​Xyn​
由于有无数个 y n y_n yn​，也就有无数个 λ n \lambda_n λn​，后面这一项是写不完的。但我们显然可以有：
∑ n λ n y n H X y n = ∑ n t r ( λ n y n H X y n ) = ∑ n t r ( λ n Y n X ) = t r ( ∑ n λ n Y n X ) = t r ( Z X ) \sum_n \lambda_n y_n^HXy_n = \sum_n \mathrm{tr}(\lambda_ny_n^HXy_n )= \sum_n \mathrm{tr}(\lambda_nY_nX)=\mathrm{tr}( \sum_n \lambda_nY_nX)=\mathrm{tr}( ZX) n∑​λn​ynH​Xyn​=n∑​tr(λn​ynH​Xyn​)=n∑​tr(λn​Yn​X)=tr(n∑​λn​Yn​X)=tr(ZX)
其中， Y n = y n y n H Y_n = y_ny_n^H Yn​=yn​ynH​， Z = ∑ n λ n Y n Z = \sum_n \lambda_nY_n Z=∑n​λn​Yn​。因此，
L ( x , λ 1 , ⋯   , ) = f 0 ( x ) + t r ( Z X ) L(x, \lambda_1, \cdots, )=f_{0}(x) + \mathrm{tr}( ZX) L(x,λ1​,⋯,)=f0​(x)+tr(ZX)，
注意到， Z Z Z是一个半正定矩阵。
那么，关于KKT条件中的互补松弛条件，我们还有一个小结论。本来互补松弛条件应当写为：
t r ( Z X ) = 0 \mathrm{tr}( ZX)=0 tr(ZX)=0
但由于 Z Z Z和 X X X均为半正定矩阵，那么我们可以有 Z = S H S Z = S^HS Z=SHS， X = A H A X=A^HA X=AHA:
t r ( Z X ) = 0 → t r ( S H S A H A ) = 0 → ∥ S A H ∥ F = 0 → S A H = 0 \mathrm{tr}( ZX) = 0\rightarrow \mathrm{tr}(S^HSA^HA)=0\rightarrow \|SA^H\|_F=0\rightarrow SA^H=0 tr(ZX)=0→tr(SHSAHA)=0→∥SAH∥F​=0→SAH=0
因此 Z X = 0 ZX=0 ZX=0.
故而 t r ( Z X ) = 0 \mathrm{tr}( ZX)=0 tr(ZX)=0与 Z X = 0 ZX=0 ZX=0等价。

注：按最基本的定义里，互补松弛条件应该是针对每个约束而言，也即应写为：
t r ( λ n Y n X ) = 0 , ∀ n \mathrm{tr}( \lambda_nY_nX) = 0 , \forall n tr(λn​Yn​X)=0,∀n

但事实上这与 t r ( Z X ) = 0 \mathrm{tr}( ZX)=0 tr(ZX)=0是等价的。因为 X X X为半正定，因此 t r ( Z X ) = 0 \mathrm{tr}( ZX)=0 tr(ZX)=0时，说明所有 t r ( λ n Y n X ) \mathrm{tr}( \lambda_nY_nX) tr(λn​Yn​X)必均等于 0 0 0，这是因为易证 t r ( λ n Y n X ) ≥ 0 \mathrm{tr}( \lambda_nY_nX)\ge 0 tr(λn​Yn​X)≥0。