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∑jyi∗yjxij≥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λifi(x)+i=1∑pνihi(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∑λnynHXyn 由于有无数个 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∑λnynHXyn=n∑tr(λnynHXyn)=n∑tr(λnYnX)=tr(n∑λnYnX)=tr(ZX) 其中， Y n = y n y n H Y_n = y_ny_n^H Yn=ynynH， Z = ∑ n λ n Y n Z = \sum_n \lambda_nY_n Z=∑nλnYn。因此， 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(λnYnX)=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(λnYnX)必均等于 0 0 0，这是因为易证 t r ( λ n Y n X ) ≥ 0 \mathrm{tr}( \lambda_nY_nX)\ge 0 tr(λnYnX)≥0。
