http://www.ma-xy.com
目录
第一章 半定规划 1
1.1 半定规划的产生与发展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 线性半定规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.1 线性半定规划的一般形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2.2 对偶性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 半定规划的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.1
线性规划转化为半定规划
. . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 二阶锥规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.3 二次约束二次凸规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 最优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 原始-对偶路径跟踪内点算法 . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.2 非光滑优化方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.3 一阶非线性规划算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 非线性半定规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.1 一般形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5.2 最优性条件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1
http://www.ma-xy.com
第一章 半定规划
1.1 半定规划的产生与发展
半定规划 (Semxdenite Programming) 简称 SDP，可视为线性规划的推广。SDP 几乎和 LP
同时产生，但由于产生初期缺乏有效的处理方法而被遗忘。上世纪八九十年代，Fletder 激发了
SDP 的研究，出现了许多 SDP 的理论上高效的算法，尤其是内点法的产生，更引发了 SDP 研
究的高潮。
1984 年，Karmarkar 提出 LP 的内点法。该算法具有多项式复杂性，在实践中效果很好。内
点法随后被用于处理凸二次规划和某些线性互补问题。1984-1997 年间，LP 的内点法几乎趋于
完善。1988 年，Nesterov 和 Nemirovsky 在研究具有自协调性质的障碍函数时，证实了内点法原
则上可以运用到一切凸优化问题。为了实用，障碍函数的一阶二阶导数必须易于计算。Nesterov
和 Nemirovsky 证实了每一个凸集都存在一个自协调障碍函数。但一般来说，它们的自协调障碍
函数不易于计算。幸运的是，SDP 有易于计算的障碍函数。
关于一般凸优化问题的内点法，可参考 1993.Den Hertog 的《Interior point approch to linear
quadratic and convex programming》。1997 年，Nesterov 和 Nemirovsky、Alizadeh 与 Kamath、
Karmarkar 独立地把 LP 的内点法推广到了半定规划。此外，用于求解 SDP 的方法还有势下降
算法、割平面方法等。
九十年代中期开始，不可行内点算法逐渐兴起。上个世纪末，SDP 又被推广到了非线性半定
规划 (NLSDP)，即线性或非线性目标函数受到非线性矩阵不等式和向量不等式约束的优化问题。
已有的算法有：
SQP
方法、内点法、增广
Lagrange
方法、分支切割法等。
1.2 线性半定规划
1.2.1 线性半定规划的一般形式
线性半定规划是线性规划的一种推广：目标函数为线性函数，约束条件为对称矩阵的仿射组
合半正定。这个约束是非线性的、非光滑、凸的，因而 SDP 是一个非光滑凸优化问题。
1
http://www.ma-xy.com
1.2 线性半定规划 第一章 半定规划
线性半定规划的标准形式如下
min C • X
s.t.
A
i
• X = b
i
i = 1, 2, . . . , m
X ⪰ 0
其中：b
i
为正实数，• 或者
A, B
表示 Frobenius 内核。
当 A, B ∈ R
n×n
, R
n×n
时，有
A, B
= A • B =
i
j
A
ij
B
ij
= Tr(A
T
B)
设 S
n
是 n × n 实对称矩阵全体，X ∈ S
n
, X ⪰ 0 表示 X 为半正定，X ≻ 0 为正定，C , A
i
∈ R
n×n
。
不失为一般性，可以假设 C, A
i
∈ S
n
，否则，令
C = (C + C
T
)/2
A
i
= ( A
i
+ A
T
i
)/2
为了方便，我们引进线性算子 A : S
n
→ R
m
AX =
A
1
• X
A
2
• X
.
.
.
A
m
• X
令 b = (b
1
, b
2
, · · · , b
m
)
T
，则 SDP 可以写为
min C • X
s.t.
AX = b
X ⪰ 0
A 的伴随算子记为 A
T
: R
m
→ S
n
: ∀X ∈ S
n
, y ∈ R
m
，有
AX, y
=
X, A
T
y
因为
AX, y
=
m
i=1
y
i
Tr(A
i
X) = Tr
X
m
i=1
y
i
A
i
=
X, A
T
y
所以有 A
T
y =
m
i=1
y
i
A
i
。
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 半定规划 1.2 线性半定规划
1.2.2 对偶性
对偶问题
利用 Lagrange 方法，可以得到线性半定规划的对偶问题：
max b
T
y
s.t.
A
T
y + Z = c
Z ⪰ 0
其中：Z ∈ S
m
，y ∈ R
m
，A
T
: R
m
→ S
n
为 A 的伴随算子。
对偶理论
线性半定规划是线性规划的推广，它与线性规划有类似的对偶理论。
引理 (1) 设 A, B ∈ S
n
，且 A ⪰ 0, B ⪰ 0，则 A • B ⩾ 0。
引理 (2) 设 A, B ∈ S
n
，且 A ⪰ 0, B ⪰ 0，则 A • B = 0 当且仅当 AB = 0。
定理 (弱对偶定理) 令 X, y 分别为原问题 P 和对偶问题 D 的可行解，则
C • X ⩾ b
T
y
下面，引进严格可行域的概念：
F
0
(P ) = {X|AX = b, X > 0}
F
0
(D) = {y|A
T
y + Z = C, Z > 0}
同样可定义可行域
F (P ) = {X|AX = b, X ⩾ 0}
F (D) = {y|A
T
y + Z = C, Z ⩾ 0}
定理 (强对偶定理) (1) 如果 P 存在可行解或者 D 存在可行解，则 p
∗
= d
∗
。
(2) 如果 P 和 D 都存在可行解，则 p
∗
= d
∗
，且 F (D) = ϕ，F (P ) = ϕ。
如果 P 和 D 都存在严格可行解，则至少存在一对原始 - 对偶最优解，即 F (D) = ϕ，F (P ) =
ϕ。从而就存在可行解 X, y，使得
C • X
= b
T
y = p
∗
= d
∗
，η =
Z, X
= 0 。由 A◦B ⇔ AB = 0，
有 XZ = 0。将 XZ = 0 称为互补松弛条件，它可以看成是线性规划互补松弛条件的推广。
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.3 半定规划的应用 第一章 半定规划
最优解条件-KKT 条件
若 P 和 D 存在严格可行解，则 X 为 P 的最优解，当且仅当存在 (X, Z) ∈ S
n
× S
n
，使得
AX = b X ⩾ 0
A
T
y + Z = C Z ⩾ 0
XZ = ⟨Z ◦ X⟩ = 0
需要指出的是，尽管 X 和 Z 都是对称半正定的，但 XZ 却未必对称。若记
F (X, y, Z) =
A
T
y + Z − C
AX − b
XZ
则 F (X, y, Z) 为 S
n
× R
m
× S
n
→ S
n
× R
m
× R
n×m
的函数。所以，上述最优化方程组是超定
的，不能直接用牛顿法求解。
1.3 半定规划的应用
1.3.1 线性规划转化为半定规划
考虑如下线性规划问题
min c
T
x
s.t.
a
T
i
x = b
i
i = 1, 2, . . . , m
x ⩾ 0
其中：x, c, a
i
∈ R
n
，b
i
为实数。i ∈ J = {1, 2, . . . , m}。令 Diag(x) ∈ R
n×n
表示由向量 x 中
的分量构成的对角矩阵。diag 是 Diag 的伴随算子。x ⩾ 0 表示其每一个分量非负。令 X =
Diag(x), C = Diag(c), A
i
= Diag(a
i
), i ∈ J。由于 x ⩾ 0 ⇔ X ⪰ 0，则线性规划可转化为半定规
划：
min C • X
s.t.
A
i
• X = b
i
i = 1, 2, . . . , m
X ⪰ 0
易知，若 X 为上述 SDP 的最优解，则 x
∗
= Diag(diag(X)) 也是其最优解，从而 SDP 与 LP 可
以转化。
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 半定规划 1.3 半定规划的应用
1.3.2 二阶锥规划
考虑如下二阶椎规划
min c
T
x
s.t. ∥A
i
x + b
i
∥ ⩽ c
T
i
x + d
i
i = 1, 2, . . . , m
其中：x ∈ R
n
, c ∈ R
n
, A
i
∈ R
n×n
，c
i
∈ R
n
, d
i
∈ R, i ∈ J ，∥u∥ = (u
T
u)
1
2
。其约束可以转化为如
下形式
(c
T
i
x + d
i
)I A
i
x − b
i
(A
i
x + b
i
)
T
c
T
i
x + d
i
⩾ 0
故，二阶锥可转化为
min c
T
x
s.t.
(c
T
i
x + d
i
)I A
i
x − b
(A
i
x + b
i
)
T
c
T
i
x + d
i
⩾ 0
i = 1, 2, . . . , m
1.3.3 二次约束二次凸规划
带二次约束的二次凸规划的一般形式如下：
min x
T
Q
0
x − q
T
0
x − c
0
s.t.
x
T
Q
i
x − q
T
i
x = c
i
i = 1, 2, . . . , m
其中：Q
i
∈ S
n
且半正定，q
i
∈ R
n
, c
i
∈ R。
因为 Q
i
是对称的半正定矩阵，则存在 B
i
使得 Q
i
= B
T
i
B
i
，从而二次约束可转化为
I B
i
x
x
T
B
T
i
q
T
i
x + B
i
⪰ 0 i = 1, 2, . . . , m
于是原问题可转化为半定规划
min t
s.t.
I B
0
x
x
T
B
T
0
q
T
0
x + B
0
+ t
⪰ 0
I B
i
x
x
T
B
T
i
q
T
i
x + B
i
⪰ 0
其中：优化变量为 (x
T
, t
T
)
T
。
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.4 最优化算法 第一章 半定规划
1.4 最优化算法
由于线性半定规划是凸规划，所以可以根据其可行解集的结构来构造多项式时间算法，如椭
圆算法。但椭圆算法在实际运行中效果较差。Nesterov 和 Alizadeh 分别独立地用线性半定规划
的最优条件得到了内点算法。Alizadeh 证明了大多数线性规划的内点算法可以推广到半定规划
上，Nesterov 和 Nemirovskii 利用自 concordant 罚函数的定义给出了用内点算法求解锥规划的
更完善的理论，证明了半定规划存在多项式时间算法。
内点算法按其下降方式分类可分为：路径跟踪算法、势下降算法等；从处理的规则来分可分
为：原内点算法、对偶调比内点算法和原始-对偶内点算法；从产生的迭代点列是否满足约束可分
为：可行与不可行内点算法。虽然不可行内点算法易于实现，但没有可行内点算法易于进行理论
分析。
内点算法适用于小规模的问题，对于大规模问题，存在内存要求过大，执行时间过长等缺点。
在一定条件下，线性半定规划可转化为特征值优化问题。利用非光滑优化技术发展起来的非光滑
优化方法—谱丛方法成为近几年来求解较大规模问题的有效算法。
1.4.1 原始-对偶路径跟踪内点算法
我们在原半定规划的目标函数中加入罚函数 −µlog det(X)。其中，µ 为罚权重
min C • X − µlog det(X)
s.t.
AX = b
X ⪰ 0
因为 ∀d ∈ R，集合 {X|AX = b, ⟨C, X⟩ = d, X ⪰ 0} 是有界闭集，且上述目标函数是严格凸
的，所以，上述罚问题的最优解存在唯一，且易知，其最优解一定存在半正定约束的内部。通过
引进拉格朗日乘子 y，可将上述约束问题转化为如下无约束优化
L(X, y, µ) = C • X − µlog det(X) + y
T
(b − AX)
L
(
X, y, µ
)
是定义在
S
′′
+
上的凸函数，其最优性条件为
∇
x
L = C − µX
−1
− A
T
y = 0
∇
y
L = b − AX = 0
令 Z = µX
−1
，可得到
AX = b X > 0 (1.1)
A
T
y + Z = C Z > 0 (1.2)
ZX = µI (1.3)
其中：第一个条件为原问题的严格可行解条件，第二个条件使对偶问题的严格可行解条件，第三
个条件是当 µ → 0 时相应的互补松弛条件 ZX = 0。上面的方程组 (1.1) 仅是必要条件而非充分。
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 半定规划 1.4 最优化算法
对于不固定的 µ，方程组 (1.1) 存在唯一解 (X
µ
, Z
µ
)。X
µ
和 Z
µ
分别构成的曲线称为中心路
径，这是一条光滑曲线。下面证明：当 µ → 0 时，(X
µ
, Z
µ
) 存在聚点。若 (X
∗
, Z
∗
) 是 (X
µ
, Z
µ
)
的聚点，那么，X
∗
和 Z
∗
分别为原问题和对偶问题的最优解。
引理 令 A, B ∈ S
n
+
，则 λ
min
(A)λ
max
(B) ⩽
A, B
⩽ nλ
min
(A)λ
max
(B)。
引理 令 X
′
, X
′′
∈ { X ∈ S
′
|AX = b} 和 Z
′
, Z
′′
∈ { Z = C−A
T
y, y ∈ R
n
}，则 ⟨X
′
− X
′′
, Z
′
− Z
′′
⟩ =
0。
定理 对给定的序列 {µ
k
}，满足 µ
k
> 0 且当 k → ∞ 时有 µ
k
→ 0。当 µ
k
→ 0 时，(X
µ
k
, Z
µ
k
)
一定存在聚点，且如果 (X
∗
, Z
∗
) 是 (X
µ
k
, Z
µ
k
) 的聚点，则 X
∗
和 Z
∗
为原始-对偶问题的最优解。
为了确定 (X
µ
k
, Z
µ
k
)，需要解如下方程组
F
µ
(X, y, Z) =
AX − b
A
T
y + Z − C
XZ − µI
= 0
我们称这个方程组为中心路径方程组，它的解 (X
µ
, Y
µ
, Z
µ
) 为解析中心路径。
利用牛顿法求解
F
µ
+ ∇F
µ
· (∆x, ∆y, ∆z)
T
= 0
可得到搜索方向 (∆x, ∆y, ∆z)。其相当于解如下线性系统
A∆x = −(AX − b) =: −r
p
(1.4)
A
T
∆y + ∆z
T
= −(A
T
y + Z − C) =: −r
d
(1.5)
∆xZ + X∆z = µI − XZ =: −r
c
(1.6)
上述线性系统是一个超定的方程组，不能直接利用牛顿法求解，我们可以考虑对称化方案。
由于一般的 X, Z 是不可变换的，这样解上式得到的 ∆z 虽然是对称的，但 ∆x 一般是不对
称的，这与下一步迭代需要 X + α∆x 是对称的矛盾。利用不同的对称技巧，可以得到不同的内
点算法，主要有 NT 方向、HKM 方向、AHO 方向等。这些方法得到的 ∆x 是对称的。在降低对
偶间隙方向，AHO 方法最好，利用 AHO 方法，算法终止时的对偶间隙一般小于利用 HKM 方
法或者 NT 方法的 10—100 倍；在计算量方面，NT 方法少于 AHO 方法，但微大于 HKM 方法；
在稳定性方面，NT 方法是最好的。
Zhang
通过引进对称化算子，统一了这些方向
H
p
(M) =
1
2
(P MP
−1
+ (P MP
−1
)
T
)
则 ∆xZ + X∆z = µI − XZ 等价于 H
p
(XZ, ∆xZ, X∆z) = µI。
当 P = X
−
1
2
时为 KM 方向；当 P = Z
1
2
时为 HKM 方向；当 P
T
P = w 时为 NT 方向；当
P = I 时为 AHO 方向。其中，W = X
1
2
(X
1
2
ZX
1
2
)
−
1
2
X
1
2
。下面给出内点算法的一般框架。
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.4 最优化算法 第一章 半定规划
step1. 初始化。初始可行点 (X
0
, y
0
, Z
0
)，满足 X
0
> 0, Z
0
> 0。
step2. 选择 µ。
step3. 计算 (∆x, ∆y, ∆z)。如需对称化，可利用上面的对称化算子得到对称矩阵。
step4. 选择步长 α，使 X + α∆x�Z + α∆z 均大于 0。
step5. 进行如下更新
X := X + α∆x
y := y + α∆y
Z := Z + α∆z
step6. 如果 ∥AX − b∥，∥A
T
y + Z − C∥
F
，⟨X, Z⟩ 都足够小，则停止；否则，返回 step2。
HKM 方向 HKM 搜索方向就是建立在对称化的 KKT 条件使用牛顿法的基础上进行的。我们
通过求解线性化的中心路径方程组 (CPE) 得到 HKM 搜索方向。
首先，由方程组 (1.4) 中的第二个方程得
∆z = −A
T
∆y − r
d
(1.7)
然后把它代入最后一个方程得
∆x = −X(∆z)Z
−1
− r
c
Z
−1
= X(A
T
∆y + r
d
)Z
−1
− r
c
Z
−1
= X(A
T
∆y + r
d
)Z
−1
− X + µZ
−1
(1.8)
再把 ∆x 代入第一个方程组，得
A(XA
T
∆yZ
−1
) = A(−µZ
−1
+ X − Xr
d
Z
−1
) − r
p
= A(−µZ
−1
− Xr
d
Z
−1
) + b
(1.9)
由此可得出 ∆y，然后再代回 (1.7) 即得 ∆z。这里需要注意的是，由式 (1.7) 可以看出 ∆z 是对
称矩阵。但由式 (1.8) 可知 ∆x 未必对称，所以，需要把 ∆x 对称化，只需要将它投影到 S
n
+
上。
譬如，我们可以取对称算子 B : X →
X+X
T
2
，即以
∆x+∆x
T
2
代替 ∆x。这样，我们便得到了搜索
方向
∆
s
= (∆
x,
∆
y,
∆
z
)
T
。
1.4.2 非光滑优化方法
一个对称矩阵是半正定的等价于其最小特征值非负：λ
min
(X) ⩾ 0，即 λ
max
(−X) ⩽ 0。由
于这个性质，半定规划 SDP 与基于矩阵仿射集上的特征值优化有着密切的联系。设 F (P ) =
{X|AX = b, X ⩾ 0} 是一有界集。若原 SDP 问题具有可行集 F ，则 P 与 D 无对偶间隙，且存
在 ¯y ∈ R
m
，使得
A
T
¯y = I
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 半定规划 1.4 最优化算法
在对偶问题 D 中，Z ⪰ 0 等价于 λ
max
(−Z) ⩽ 0，利用 Lagrange 乘子法，将条件 Z ⪰ 0 加
入目标函数，得到无约束非光滑优化问题
min
y ∈R
m
µ
0
λ
max
(C − A
T
y) + b
T
y (1.10)
引理 若 A 满足 A
T
y = I，令 µ = max{0, b
T
¯y}，则对偶问题 D 等价于上式 (1.10)。进而，
如果原问题 P 有可行解，则所有可行解 X ∈ F (P ) 满足 Tr(X) = µ
0
，并且可得到最优值 p
∗
，
p
∗
= d
∗
= min b
T
y。
下面，研究最大特征值函数 λ
max
(·)。矩阵 X 的最大特征值函数可以表示为 λ
max
(X) =
max
∥p∥=1
p
T
Xp。当 p 是 X 的最大特征值对应的单位特征向量时，λ
max
(X) = p
T
Xp，令
Ω = {W ⪰ 0|W • I = 1}
则 Ω 是集合 {pp
T
| ∥p∥ = 1} 的凸包。将 p
T
Xp 转化成矩阵内积的形式 ⟨X, pp
T
⟩，则
λ
max
(X) = max{
X, W
|W ∈ Ω}
由凸分析的相关知识，易知 Ω 有界，λ
max
(X) 是凸函数，且 lipschitz 连续。因此，λ
max
(X) 在
X 处次微分 ∂λ
max
(X)，即满足不等式
λ
max
(Y ) ⩾ λ
max
(X) + ⟨W, Y − X⟩, ∀Y ∈ S
n
W
的合集为
∂λ
max
(X) = {W ∈ Ω|⟨X, W ⟩ = λ
max
(x)}
= {p ∪ p
T
|Tr(V ) = 1, V ⪰ 0}
其中：p 的列由 X 的最大特征值对应的特征向量空间的标准正交基组成。
令 f(y) = µ
0
λ
max
(C − A
T
y) + b
T
y，容易知 f(y) 是凸函数，且有
∂λ
max
(C − A
T
y
k
) = {W ⪰ 0|Tr(W ) = µ
0
, ⟨C − A
T
y, W ⟩ = λ
max
(C − A
T
y)}
= {p ∪ p
T
|Tr(V ) = µ, V ⪰ 0}
以及
∂f(y) = {ξ|ξ = b − µ
0
AW, W ∈ ∂λ
max
(C − A
T
y)}
其中：矩阵 P 的列构成 C − A
T
y 的最大特征值所对应的特征向量空间中的标准正交基。
关于非光滑凸规划解的一阶最优性条件，我们有：
定理 设 f : R
n
→ R 是凸函数，则下列条件等价
¬O ∈ ∂f (x)；
x 是 f 的最优解，即 f(x) ⩽ f (y), ∀y ∈ R
n
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.4 最优化算法 第一章 半定规划
在光滑凸规划中，负梯度方向是最速下降方向，利用该方向可设计最速下降算法。但在非光
滑凸规划中，负次梯度 (次微分元素) 方向并不一定是下降方向。关于下降方向有如下定理
定理 设 f : R
n
→ R 是凸函数，x 不是 f 的最优解，g 满足
g = min{∥g∥|g ∈ ∂f (x)} (1.11)
则 −g 是具有最速下降性质的下降方向。
但在实际应用时，上式 (1.11) 一般不能精确求解，利用它计算很难保证收敛。同时，次微分
∂f(x) 并不是对任何问题都容易求。由此，产生了一在非光滑优化中到重要作用的技术—向量化
技术。设目标函数 f 是凸的局部 Lipschitz 函数，f 以及它的一个次梯度 g
f
∈ ∂f(x) 可以计算。
易知，式 (1.11) 满足上述条件。
算法产生 R
n
中的一个序列 {x
k
}
k
和一个试验点序列 {y
k
}
k
，设 x
′
= y
′
。在第 k 个迭代点
上，在 y
k
处作 f 的线性近似
¯
f(x, y
k
) = f (y
k
) + g
f
(y
k
)
T
(x − y
k
)
设 f 的一个凸包络函数 (割平面模) 为
ˆ
f
k
(x) = max{
¯
f(x, y
j
)|j = 1, 2, · · · , k}
按下式来选取一个试验点
y
k+1
= arg min
x∈R
n
{
ˆ
f
k
(x) + µ
k
∥x − µ
k
∥
2
/2}
其中：取 µ
k
> 0 是为了使 y
k+1
取在
ˆ
f
k
值同 f 值比较接近的区域内，这也是一种安全措施，当
y
k+1
处的值比 x
k
处足够好时，即满足
f(y
k+1
) ⩽ f (x
k
) − y(f(x
2
) −
ˆ
f
k
(y
k+1
))
其中：η ∈ (0, 0.5)，f(x
k
) −
ˆ
f
k
(y
k+1
) 为预期的下降量。因此，上式表示在 y
k+1
处，f 值有明显
下降。于是令 x
k+1
= y
k+1
，否则令 x
k+1
= x
k
，再以 y
k+1
进行下一次迭代。
Helmberg 和 Rendl 将这种方法推广并应用到式 (1.11) 上，得到谱向量丛方法。这里的推广
指的是将上述的凸包络函数 (即割平面模) 中的平面变成了曲面，从而伴随着每次迭代要求解一
个小规模的二次半定规划 (上述方法是解一个二次凸规划)。
1.4.3 一阶非线性规划算法
todo:《最优化基础.docx》
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 半定规划 1.5 非线性半定规划
1.5 非线性半定规划
1.5.1 一般形式
前面介绍了线性半定规划，下面介绍非线性半定规划。非线性半定规划 (NLSDP) 的一般形
式为
min f(x)
s.t. G(x) ⪯ 0
其中：x ∈ R
n
为优化变量 (决策变量)，f(x) : R
m
→ R，G(x) : R
m
→ S
n
。
假设 f(x) 和 G(x) 都在 R
m
上充分光滑，对于 A ∈ S
n
，设 λ
1
(A) ⩾ λ
2
(A) ⩾ · · · ⩾ λ
n
(A)
是矩阵 A 的以下降顺序排列的特征值。A 的特征值分解为 A = P diag(λ
1
, λ
2
, · · · , λ
n
)P
T
，A
†
是
一个矩阵，其定义如下
A
†
= P diag((λ
1
)
+
, (λ
2
)
+
, · · · , (λ
n
)
+
)P
T
其中：(λ)
+
= max{0, λ}，容易看出 A
†
正是 A 在 S
n
+
上的正交投影。给定一个矩阵值函数 G(x)，
用 DG(x) 表示 G(x) 在 x 处的导数
DG(x) =
∂G(x)
∂x
i
m
i=1
=
∂G(x)
∂x
1
, · · · ,
∂G(x)
∂x
n
T
我们之所以利用这个记号，是因为
DG(x)y =
m
i=1
y
i
∂G(x)
∂x
i
∀y ∈ R
m
若 v = (v
1
, · · · , v
m
)
T
是一个从 R
m
到 S
n
的线性算子。正如上面的 DG(x) 那样，对其共轭算子，
我们有
v
T
z = (Tr(v
1
z), · · · , Tr(v
m
z))
T
∀z ∈ S
n
1.5.2 最优性条件
我们考虑 NLSDP 原问题 (P) 的拉格朗日函数 L : R
m
× S
n
× R
p
→ R，即
L(x, z, λ) = f (x) + Tr(zG(x))
对于 D 的一个可行点 x
∗
，其 KKT 条件为：存在 z
∗
∈ S
n
和 λ
∗
∈ R
p
，使得
∇f(x
∗
) + DG(x
∗
)z
∗
= 0
Tr(z
∗
G(x
∗
)) = 0
z
∗
⪰ 0
http://www.ma-xy.com 11 http://www.ma-xy.com
http://www.ma-xy.com
1.5 非线性半定规划 第一章 半定规划
其中：(z
∗
, λ
∗
) 称为与 x
∗
相对立的 KKT 条件；Tr(z
∗
G(x
∗
)) = 0 称为互补松弛条件。互补松弛
条件 Tr(z
∗
G(x
∗
)) = 0 有下面两种等价形式
λ
j
(z
∗
) = 0 或者 λ
j
G(x
∗
) ∀j ∈ {1, 2, · · · , n} (1.12)
z
∗
G(x
∗
) = 0
这两种形式都由下面的 Frobenius 不等式得到
Tr(AB) = 0 ⩽
n
j=1
λ
j
(A)λ
j
(B)
其中：当且仅当存在一个可逆矩阵 P 使得 P
−1
的 P 和 P
−1
的 P 同时为对角矩阵。由式 (1.12)，
我们可以定义 KKT 中的严格互补松弛条件为
λ
j
(z
∗
) = 0 ⇔ λ
j
G(x
∗
) < 0, ∀j ∈ {1, 2, · · · , n}
http://www.ma-xy.com 12 http://www.ma-xy.com
