http://www.ma-xy.com
目录
第一章 二阶椎规划 1
1.1 问题的引入与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 凸二次规划的转化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 凸二次约束线性规划的转化 . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.3 凸二次约束二次规划问题 QCQP . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.4 支持向量机的锥形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2
模型规范化及其基本理论
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 二阶椎和二阶椎规划的定义 . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 拉格朗日对偶问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 二阶锥规划的研究进展 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.4 最优化条件及对偶定理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 最优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 原始 - 对偶内点算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.2 非精确不可行内点算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.3 预估校正算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.4 基于核函数的原始-对偶内定算法 . . . . . . . . . . . . . . . . . . . . . . . 15
1
http://www.ma-xy.com
第一章 二阶椎规划
1.1 问题的引入与分析
为了说明二阶椎规划的重要性，我们先将如下几个优化问题转化为二阶椎规划 SOCP 问题：
1. 凸二次规划的转化；
2. 凸二次约束线性规划的转化；
3. 凸二次约束二次规划的转化；
4. 支持向量机的二阶锥形式；
1.1.1 凸二次规划的转化
考虑如下的严格凸二次规划问题
min f(x) = x
T
Qx + a
T
x + β
s.t.
Ax = b
x ⩾ 0
其中：Q 是一个对称正定矩阵，即 Q = Q
T
> 0；a ∈ R
n
, β ∈ R, A ∈ R
m×n
。令 ¯u = Q
1
2
x+
1
2
Q
−
1
2
a，
则目标函数 f 可以写为
f(x) = ∥¯u∥
2
+ β −
1
4
a
T
Q
−1
a
于是原问题变为
min u
0
s.t.
Ax = b
Q
1
2
x − ¯u = −
1
2
Q
−
1
2
a
(u
0
; ¯u) ⪰ 0
x ⪰ 0
其中：⪰ 是定义在 K 上的偏序。∀x, y ∈ K，如果 x − y ∈ K，记为 x ⪰ K
y
或 x ⪰ y, x ∈ R
n
。
1
http://www.ma-xy.com
1.1 问题的引入与分析 第一章 二阶椎规划
1.1.2 凸二次约束线性规划的转化
考虑凸二次约束线性目标规划问题
min
x
c
T
x
s.t.
x
T
Q
i
x + a
T
i
x + β
i
⩽ 0
i ∈ I = {1, 2, . . . , r}
其中：对
Q
i
作
Cholesky
分解，设
Q
i
=
B
i
B
T
i
(i = 0, 1, . . . , m)，B
i
∈ R
k
i
×n
，rank(B
i
) = k
i
, i ∈ I。
记 q(x) = x
T
B
T
Bx + a
T
x + β ⩽ 0，则
(Bx)
T
Bx ⩽ 1 · (−a
T
x − β)
即 ∥Bx∥
2
⩽ (
1−a
T
x−β
2
)
2
− (
1+a
T
x+β
2
)
2
。令
u
0
=
1 − a
T
x − β
2
¯u =
Bx
1+a
T
+β
2
于是 q(x) = ∥¯u∥
2
− µ
2
0
⩽ 0。
1.1.3 凸二次约束二次规划问题 QCQP
考虑凸二次约束二次规划问题 QCQP
min x
T
Q
0
x + a
T
0
x + β
0
s.t.
x
T
Q
i
x + a
T
i
x + β
i
⩽ 0
i = 1, 2, . . . , m
其中：a
i
∈ R
n
，β
i
∈ R，Q
i
为对称半正定，即 Q
i
⪰ 0(i = 1, 2, . . . , m)，x ∈ R
n
。
对 Q
i
作 Cholesky 分解，设 Q
i
= B
i
B
T
i
(i = 0, 1, . . . , m)，则原问题变为如下二阶锥规划
min t
s.t.
(u
i0
; ¯u
i
) ⪰ 0 i = 1, 2, . . . , m
u
00
=
1 + a
T
0
x − β
0
+ t
2
¯u =
B
T
0
x
a
T
0
x+β
0
−t+1
2
u
i0
=
1 − a
T
i
x − β
i
2
¯u
i
=
B
T
i
x
a
T
i
x+β
i
+1
2
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.1 问题的引入与分析
1.1.4 支持向量机的锥形式
SVM 针对大规模不是十分有效，Debrath、Muramatsu 和 Takahashi 于 2005 年给出了一个
针对大规模问题的基于二阶锥规划的支持向量机学习方法。考虑二分类支持向量机的一般形式
min
1
2
w
T
w + C
l
i=1
ξ
i
s.t.
y
i
(w
T
ϕ(x
i
) + b) ⩾ 1 − ξ
i
ξ
i
⩾ 0
i = 1, 2, ···
其中：C 为罚权重，ϕ(x
i
) 是一个将 x
i
映射到高维的映射，y
i
= {−1, 1}，w 为优化参数，{x
i
, y
i
}
l
i=1
为样本数据且已知。
上述模型的对偶问题为
min
1
2
α
T
Qα − e
T
α
s.t.
y
T
α = 0
0 ⩽ α
i
⩽ C
其中：α 为拉格朗日乘子，e 为单位向量，Q ⩾ 0，Q
ij
= y
i
y
j
K(x
i
x
j
)。K(x
i
x
j
) =
ϕ(x
i
), ϕ(x
j
)
是内积核。将模型重新写为
min
1
2
α
T
Qα − e
T
α
s.t.
y
T
α = 0
α + β = Ce
α, β ⩾ 0
α, β ∈ R
l
其中：β 为松弛变量，Q ⩾ 0，设 Q 的秩为 r，其 Cholesky 分解为 Q = BB
T
，其中 B ∈ R
l×r
，
则
α
T
Qα = α
T
BB
T
α = ∥B
T
α∥
2
于是，极小化 α
T
Qα 等价于在约束 ∥B
T
α∥
2
下极小化 θ。利用双曲约束的等价关系：
w
T
w ⩽ xy, w ∈ R
n
, x ∈ R
+
, y ∈ R
+
⇔ (x + y; 2w; x − y) ⩾ 0
可以把约束 ∥B
T
α∥
2
⩽ Q 转化为
θ − 1
2
2
+ ∥B
T
α∥
2
⩽
θ + 1
2
2
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.2 模型规范化及其基本理论 第一章 二阶椎规划
令
u = B
T
α
z
1
=
θ + 1
2
z
2
=
θ − 1
2
则模型定为
min
1
2
(z
1
+ z
2
) − e
T
α
s.t.
y
T
α = 0
α + β = Ce
G
T
α − u = 0, u ∈ R
r
z
1
− z
2
= 1
α, β ⩾ 0
z
2
1
⩾ z
2
2
+ ∥w∥
2
上述问题是一个二阶锥规划。
1.2 模型规范化及其基本理论
1.2.1 二阶椎和二阶椎规划的定义
定义 (二阶锥) 二阶锥又称为 Lorentz 锥，n 维二阶锥 K
n
的定义为
K
n
= {(x
1
, x
2
) ∈ R × R
n−1
|x
1
⩾ ∥x
2
∥}
其中：∥ · ∥ 为 L
2
范数，如果是其它范数，亦可定义其它锥。
定义二阶锥内部为
intK
n
= {(x
1
, x
2
) ∈ R × R
n−1
|x
1
> ∥x
2
∥}
不难看出在 R, R
2
, R
3
中二阶锥的形状，如图 (1.1) 所示
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.2 模型规范化及其基本理论
图 1.1: 三维二阶锥示意图
上面给出了二阶锥 K 的定义，二阶锥规划就是在二阶锥内求变量 x 使目标最优，即最优化
模型的约束条件为二阶锥条件。
二阶锥规划的标准形式为
min
r
i=1
C
T
i
x
i
s.t.
r
i=1
A
i
x
i
= b
i
x
i
∈ K
n
i
i ∈ I
其中：I = {1, 2, . . . , r}，b ∈ R
m
，C
i
∈ K
n
i
，A
i
∈ R
m×n
i
，K
n
i
= {(x
i1
, ¯x
i
) ∈ R
n
i
|x
i1
⩾ ∥¯x
T
i
∥}，
x
i
= (x
i1
, ¯x
i
) 表示 (x
i1
, ¯x
T
i
)
T
，且 ¯x
i
= (x
i2
, x
i3
, . . . , x
in
i
, )。
1.2.2 拉格朗日对偶问题
为得到上述问题的对偶形式，将 x
i
∈ K
n
i
转化为
n
i
j=2
x
2
ij
− ¯x
2
i
⩽ 0及x
i1
⩾ 0
对 u
i
⩾ 0, i ∈ I，有
u
i
n
i
j=2
x
2
ij
− ¯x
2
i
= −
(u
i
x
i1
)x
i1
+
ni
j=2
(−u
i
x
i1
)x
ij

我们设
s
i
= (u
i
x
i1
, −u
i
x
i2
, . . . , u
i
x
in
i
)
T
∈ R
n
i
显然 s
i
∈ K
n
i
，且
u
i
n
i
j=2
x
2
ij
− x
2
i1
= −s
T
i
x
i
i ∈ I
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.2 模型规范化及其基本理论 第一章 二阶椎规划
于是原问题的 Lagrange 对偶函数为
θ(s
i
, y) = inf
r
i=1
c
T
i
x
i
−
r
i=1
s
T
i
x
i
+ y
T
b −
r
i=1
A
i
x
i

= inf
r
i=1
(c
i
− s
i
− A
T
i
y)
T
x
i
+ b
T
y
其中：y ∈ R
m
。当 c
i
− s
i
− A
T
i
y = 0 时，θ(s
i
, y) = b
T
y，故对偶问题可描述为
max b
T
y
s.t.
A
T
i
y + s
i
= c
i
i ∈ I
s
i
∈ K
n
i
这里，s
i
为松弛变量，y ∈ R
m
为决策变量。
令
K = K
n
1
× K
n
2
× ··· × K
n
r
A = (A
1
, A
2
, ··· , A
r
) ∈ R
m×n
C = (c
1
, c
2
, ··· , c
r
) ∈ R
n
x = (x
1
, x
2
, ··· , x
r
) ∈ K
s = (s
1
, s
2
, ··· , s
r
) ∈ K
n = n − 1 + n
2
+ ··· + n
r
则原二阶锥规划及其对偶问题可简写为如下形式
min{c
T
x|Ax = b, x ∈ K}
max{b
T
y|A
T
y + s = c, s ∈ K}
注：假设 A 是行满秩的，即 rank(A) = m, m ⩽ n。
二阶锥规划 (SOCP) 介于线性规划和半正定规划之间，属于凸优化问题。目标函数是线性函
数，约束是一个仿射空间和有限个二阶锥的笛卡尔积交空间。
1.2.3 二阶锥规划的研究进展
todo: 未完成：引入最优化基础.docx 的 5-5.2。
1.2.4 最优化条件及对偶定理
作为研究二阶锥规划的代数基础，欧几里得约当 (Jordan) 代数显示了它独有的功效。1994 年
Faraut 和 Koranyi 在《Analysis on Symmetric Cones》中指出：Jordan 代数使线性规划、半定规划
和二阶锥规划有了统一的理论基础。Alizadeh 和 Goldfard 在《second-order-conc programming》
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.2 模型规范化及其基本理论
中提出了针对二阶锥规划的 Jordan 代数，指出对它们的理解可使人们观察到二阶锥规划问题的
所有方面：从对偶性、互补性到非退化条件，最终到内点法的设计与分析。下面给出论文中的一些
结论，为了书写方便，令 K = K
n
。对于任意的 x = (x
1
, ¯x) ∈ R ×R
n−1
和 s = (s
1
, ¯s) ∈ R ×R
n−1
，
与二阶锥 K 相伴的 Jordan 积定义为
x ◦ s = (x
T
s, x
1
¯s + s
1
¯x)
对上述的 Jordan 积 (R
n
, ◦)，有如下性质
¬
：
(1) 对 ∀α, β ∈ R，有分配律
x ◦ (αy + βz) = αx ◦ y + βx ◦ z
(αy + βz) ◦ x = αy ◦ x + βz ◦ x
(2) x ◦ s = s ◦ x；
(3) 设向量 e 为唯一的单位元，e = (1, 0, . . . , 0)
T
∈ R
n
x ◦ e = e ◦ x = x
(4) 令 x
2
= x ◦ x，则 ∀s ∈ R
n
，有 x ◦ (x
2
◦ s) = x
2
◦ (x ◦ s)。
定义 (向量特征值) ∀x = (x
1
, ¯x) ∈ R × R
n−1
，有
x
2
− 2x
1
x + (x
2
1
+ ∥¯x∥
2
)e = 0
我们称多项式
P (λ, x) = λ
2
− 2x
1
λ + (x
2
1
− ∥¯x∥
2
) = 0
为 x 的特征多项式，并且称特征多项式的两个根 λ
1
(x) = x
1
− ∥¯x∥ 和 λ
2
(x) = x
1
+ ∥¯x∥ 为 x 的
特征值。
对 ∀x ∈ R
n
，易证明下面的等式成立
x =
1
2
(x
1
− ∥¯x∥)
1
−
¯x
∥¯x∥
+
1
2
(x
1
+ ∥¯x∥)
1
¯x
∥¯x∥
¬
注：Jordan 积’◦’ 一般不满足结合律，即 ∀x, y, z ∈ R
n
。
(x ◦ y) ◦ z = x ◦ (y ◦ z)
但在内积定义下，结合律成立
⟨
x, y ◦ z
⟩
=
⟨
x ◦ y, z
⟩
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.2 模型规范化及其基本理论 第一章 二阶椎规划
定义 (特征值分解) ∀x = (x
1
, ¯x) ∈ R × R
n−1
，其特征值分解为
x = λ
1
(x)u
(1)
+ λ
2
(x)u
(2)
其中：特征值 λ
1
(x) = x
1
− ∥¯x∥, λ
2
(x) = x
1
+ ∥¯x∥。特征向量 (i = 1, 2)
u
(i)
=
1
2
1 − (−1)
i
¯x
∥¯x∥
¯x = 0
1
2
1 − (−1)
i
w
¯x = 0
这里，w ∈ R
n−1
是满足 ∥w∥ = 1 的任意向量。
易知
x ∈ K ⇔ λ
2
(x) ⩾ λ
1
(x) ⩾ 0
x ∈ intK ⇔ λ
2
(x) ⩾ λ
1
(x) > 0
注意到，u
(1)
, u
(2)
属于 K，但不属于 intK。此外
u
(1)
◦ u
(2)
= 0, u
(1)
+ u
(2)
= e, ∥u
(1)
∥ = ∥u
(2)
∥ =
1
√
2
u
(1)
◦
u
(1)
=
u
(1)
, u
(2)
◦
u
(2)
=
u
(2)
利用向量的特征值分解，可以定义
¬绝对值：|x| = |λ
1
(x)|u
(1)
+ |λ
2
(x)|u
(2)
, ∀x ∈ K;
平方：x
2
= λ
1
(x)
2
u
(1)
+ λ
2
(x)
2
u
(2)
;
®平方根：
√
x =
λ
1
(x)u
(1)
+
λ
2
(x)u
(2)
,;
¯逆：x
−1
= λ
1
(x)
−1
u
(1)
+ λ
2
(x)
−1
u
(2)
。
容易证明下列关系式成立
|x| =
√
x
2
, x
2
= x ◦ x, (
√
x)
2
= x
并且，如果 x
−1
存在，则称 x 可逆，且满足 x ◦ x
−1
= e。
对任意的 x = (x, ¯x) ∈ R × R
n−1
，其行列式和迹分别定义为
det(x) = λ
1
(x)λ
2
(x) = x
2
1
− ∥¯x∥
2
Tr(x) = λ
1
(x) + λ
2
(x) = 2x
1
对任意的 x = (x, ¯x) ∈ R × R
n−1
，定义对称矩阵
L
x
=
x ¯x
T
¯x x
1
I
∈ R
n×n
其中：I 为 n − 1 × n − 1 的单位矩阵。有
x ◦ s = s ◦ x = L
x
s = L
s
x = L
x
L
s
e
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.2 模型规范化及其基本理论
这里，当且仅当 x ∈ K(x ∈ intK) 时，L
x
是半正定矩阵 (正定矩阵)。此外，如果 x ∈ intK，那
么矩阵 L
x
可逆：
L
−1
x
=
1
det(x)
x
1
−¯x
T
−¯x
det(x)
x
1
I +
¯x¯x
T
x
1
上面分析了 K 为单一二阶锥的情况，所有结论可平行推广到 K = K
n
1
×K
n
2
×···K
n
r
的情
形。令 x = (x
1
···x
r
)，s = (s
1
···s
r
)，x
i
, s
i
∈ K
n
i
，i = (1, 2, ··· , r)，则
(1) x ◦ s = (x
1
◦ s
1
, ··· , x
r
◦ s
r
)；
(2) L
x
= diag(L
x
1
, L
x
2
, ··· , L
x
r
)；
(3) Tr(x) =
r
i=1
Tr(x
i
) =
r
i=1
[λ
1
(x
i
) + λ
2
(x
i
)]；
(4) det(x) =
r
i=1
det(x
i
) =
r
i=1
λ
1
(x
i
) + λ
2
(x
i
)；
(5) x 的特征值具有 2r 个 (含多重特征值，由 x
1
, ··· , x
r
的特征值构成)；
(6) 如果 x
i
∈ intK
n
i
，则 x
−1
= (x
−1
1
, ··· , x
−1
r
)。
上面介绍了一些欧几里得约当 (Jordan) 代数在二阶锥问题中的一些具体理论。下面，我们
利用这些理论来分析二阶锥规划最优性条件及对偶理论。并在此基础上介绍一些最优化算法。
弱对偶定理
设
x
和
(
y, s
)
分别为二阶锥规划原问题和对偶问题的可行解，则对偶间隙为
c
T
x − b
T
y = x
T
s ⩾ 0
强对偶定理 如果二阶锥原问题和对偶问题均存在严格可行解，则原问题和对偶问题存在最优解
x
∗
和 (y
∗
, s
∗
)，并且 p
∗
= c
T
x
∗
= b
T
y
∗
= d
∗
。这里：p
∗
, d
∗
为原始问题 (P) 和对偶问题 (D) 的最
优解。
半强对偶定理 如果原问题存在严格可行解，并且其目标函数值在可行域内有下界，则对偶问题
可解，且 p
∗
= d
∗
。
互补条件 对 ∀x = (x
1
···x
r
) ∈ K, s = (s
1
···s
r
) ∈ K，x
i
∈ K
n
i
, s
i
∈ K
n
i
, i = 1, 2, ··· , r，使
x
T
s = 0，当且仅当 x
i
◦ s
i
= 0，即
(i) x
T
i
s
i
= x
i1
s
i1
+ ¯x
T
i
¯s
i
= 0
(ii) x
i1
¯s
i
+ s
i1
¯x
i
= 0
KKT 条件 - 最优化条件 假设原问题和对偶问题存在严格可行解，则 (x, y, s) 是其最优解的充
要条件是
Ax = b x ∈ K
A
T
y + s = c s ∈ K
x ◦ s = 0
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二阶椎规划
1.3 最优化算法
内点算法是求解二阶锥规划最有效的方法之一。内点法要求初始搜索点在可行域内 (如何选
取 x
0
？)。2004 年 Zhou 和 Toh 在《Polynomiality of an inexact infeasile interior point algorithm for
semidente Programming》中提出一种求解半定规划的非精确不可行内点算法，此方法可推广到
二阶锥规划中，但其初始点的选取受到某个最优解的限制。1996 年，Nemirovskii 和 Scheinberg 在
《Extension of Karmarkar’s algorithm onto convex quadratically constrained quadratic problems》
中证明了线性规划的原始对偶内点法可推广到二阶锥规划中。1994 年 Adler 和 Alizadeh 研究了
求解半定规划和二阶锥规划统一的原始—对偶方法，提出了适用于二阶锥规划的搜索方向。2000
年，Monteiro 和 Tsudiya 介绍了确定二阶锥规划 AHO 搜索方向的牛顿方程组，给出了沿 AHO
方向的二阶锥规划的预估—校正算法的多项式收敛性。
1.3.1 原始 - 对偶内点算法
内点法通常称为严格可行内点算法，因为算法所产生的所有迭代点都严格可行，其基本思想
是：在可行域内选取中心路径的一个领域，算法始终追踪在这个邻域内。原始—对偶内点法的基
本思想是：在中心路径附近取一个初始点，然后求一个搜索方向使对偶间隙能够减小。
记原始规划和对偶规划的可行解与严格可行解为
F (P ) = {x|Ax = b, x ∈ K}
F (D) = {(y, s)|A
T
y + s = c, s ∈ K}
F
0
(P ) = {x|Ax = b, x ∈ intK}
F
0
(D) = {(y, s)|A
T
y + s = c, s ∈ intK}
假设：F
0
(P ) × F
0
(D) = 0，且 A 的行向量是线性无关的。由强对偶定理可知，P 和 D 都存在
最优解，且最优值相等。此外，解 P 和 D 等价于求解 KKT 条件
Ax = b x ∈ K
A
T
y + s = c s ∈ K
x ◦ s = 0
定义向量值函数 F : R × R
m
× R → R
2n+m
F (x, y, s) =
Ax − b
A
T
y + s − c
x ◦ s
则有 F (x, y, s) = 0。把 KKT 条件加以扰动，有
Ax = b x ∈ K
A
T
y + s = c s ∈ K
x ◦ s = µe
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.3 最优化算法
上述方程称为中心路径方程。
已证明，上述方程对任意 µ > 0 都有唯一解 (x(µ), y(µ), s(µ))，当 µ 取遍所有正数时，这些
解的轨迹称为中心路径。在中心路径方程中，分别以 x + ∆x, y + ∆y, s + ∆s 代替 x, y, s，并去
掉含 ∆x, ∆s 的非线性项，得到
A∆x = r
p
= b − Ax
A
T
∆y + ∆s = r
d
= c − A
T
y − s
L
x
∆s + L
s
∆x = µe − L
x
s
上式又可以写成矩阵形式
A 0 0
0 A
T
I
L
s
0 L
x
∆x
∆y
∆s
=
r
p
r
d
r
c
解上述方程，即可得到搜索方向 (∆x, ∆y, ∆s)
∆y = (AL
−1
s
L
x
A
T
)[r
p
+ AL
−1
s
(L
x
r
d
− r
c
)]
∆s = r
d
− A
T
∆y
∆x = −L
−1
s
(L
x
∆s − r
c
)
在此基础上，我们给出中心路径邻域的概念：
L
x
= diag(L
x
1
, ··· , L
x
r
)
L
x
i
=
x
i
¯x
T
i
¯x
i
x
i1
I
对 ∀x, s ∈ R
n
，定义
β
xi
=
x
2
i1
− ∥¯x
i
∥
2
T
x
i
=
x
i1
¯x
T
i
¯x
i
β
xi
I +
¯x
i
¯x
T
i
β
x
i
x
i1
T
x
= diag(T
x
1
, ··· , T
x
r
)
W
xs
= (w
1
, ··· , w
r
) = T
x
s
且
W
xs
= L
w
x
s
R
xs
= T
x
L
−1
x
L
s
T
x
λ
1
i
(W
xs
) = w
i1
− ∥¯w
i
∥
λ
2
i
(W
xs
) = w
i1
− ∥¯w
i
∥
http://www.ma-xy.com 11 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二阶椎规划
对 ∀(x, s) ⊂ intK × intK，定义距离如下
d
2
(x, s) =
√
2∥W
xs
− µe∥
d
∞
(
x, s
) =
max
i=1,2,...,r
j=1,2
|
λ
−j
i
(W
xs
) − µ|
给定常数 β ∈ (0, 1)，定义中心路径的邻域为
N
2
(β) = {(x, s) ∈ F
0
(P ) × F
0
(D)|d
2
(x, s) ⩽ βµ} β = γ τ = µ
N
∞
(β) = {(x, s) ∈ F
0
(P ) × F
0
(D)|d
∞
(x, s) ⩽ βµ}
显然，d
∞
(x, s) ⩽ d
2
(x, s)，所以 N
2
(β) ⊂ N
∞
(β)。下面，给出基于 AHO 搜索方向与路径跟踪内
点法：
step1. 初始化。
路径参数 β ∈ (0,
1
5
)，δ ∈ (0, 1)，满足
φ(β
2
+ δ
2
)
(1 − 3β)
2
⩽
1 −
δ
√
2r
β
令 σ = 1 −
δ
√
2n
，ε ∈ (0, 1)。初始点 (x
0
, y
0
, s
0
) ∈ N(β)
µ
0
=
x
T
0
y
0
r
置 k := 0。
step2. 计算搜索方向 (∆x
k
, ∆y
k
, ∆s
k
)。计算 µ
k
=
x
T
k
s
k
r
，若 µ
k
⩽ ε，则终止；否则，转到 step3。
step3. 计算步长 α。
α
k
= max{α ∈ (0, 1)|(x
k
(α
′
), y
k
(α
′
), s
k
(α
′
)) ∈ N(β), ∀α ∈ (0, α
′
]}
其中：(x
k
(α
′
), y
k
(α
′
), s
k
(α
′
)) = (x
k
, y
k
, s
k
) + α(∆x
k
, ∆y
k
, ∆s
k
)。
step4. 求点 (x
k+1
, y
k+1
, s
k+1
)
(x
k+1
, y
k+1
, s
k+1
) = (x
k
, y
k
, s
k
) + α
k
(∆x
k
, ∆y
k
, ∆s
k
)
置 k := k + 1，转到 step2。
在上面的原始 - 对偶内点算法中，选取不同的搜索方向 和中心路径邻域 就产生了不同的算
法。
1.3.2 非精确不可行内点算法
定义不可行中心路径：
S = {(x, y, s) ∈ K × R
m
× K|F (x, y, s) = 0}
S
ε
= {(x, y, s) ∈ intK × R
m
× intK|x
T
s ⩽ ε, ∥r
p
∥ ⩽ ε, ∥r
d
∥ ⩽ ε}
C = {(x, y, s) ∈ intK × R
m
× intK|r
p
= (µ/µ
0
)r
p
0
, r
d
= (µ/µ
0
)r
d
0
, x ◦ s = µe}
http://www.ma-xy.com 12 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.3 最优化算法
毫无疑问：S 是 KKT 条件 F = 0 的解集，S
ε
是 F = 0 的 ε 近似解集。称 C 为 (x
0
, y
0
, s
0
) 为
不可行中心路径，其中
µ
0
=
x
T
0
s
0
r
> 0 µ =
x
T
s
r
> 0 K
0
= intK
定义不可行中心路径 C 的邻域
N(β, µ) = {(x, y, s) ∈ intK × R
m
× intK|d
2
(x, s) =
√
2∥W
rs
− µe∥ ⩽ βµ}
给定当前点 (x, y, s) ∈ intK×R
m
×intK，基于 AHO 方向的原始-对偶内点算法通常取下列方程
组的解是 (dx, dy, ds) = (∆x, ∆y, ∆s) 为牛顿方向
A∆x = b − Ax
A
T
∆y + ds = c − A
T
y − s
L
s
∆x + L
x
∆s = µe − L
x
s
我们取下面方程组的解 (∆x, ∆y, ∆s) 为非精确搜索方向
A∆x = b − Ax + ρφ
¯
b
A
T
∆y + ∆s = c − A
T
y − s + ρφ¯c
L
s
∆x + L
x
∆s = (1 − y)µe − L
x
s
其中：ρ ∈ (0, 1)，η ∈ (0, 1)，
¯
b = Ax
0
− b，¯c = Ay
0
− s
0
− c。
这里，初始点 (x
0
, y
0
, s
0
) 取 x
0
= s
0
= ξe, 0 < ξ < 1 是一个常数。下面，给出非精确不可行
内点算法。
step1. 初始化。
β ∈ (0,
1
5
)，ρ ∈ (0, 1)，0 < τ < 1−ρ < η < 1，φ = 1，x
0
= s
0
= ξe, 0 < ξ < 1，µ
0
=
x
T
0
s
r
= ξ
2
。
并且 (φ
0
, µ, x
0
, y
0
, z
0
) ∈ N(β, µ
0
)，容许误差 ε > 0，置 k := 0。
step2. 求非精确搜索方向 (∆x
k
, ∆y
k
, ∆s
k
)。
step3. 计算 α
k
φ(α) = (1 − 2α)φ
k
µ(α) = (1 − ηα)µ
k
α
k
= max{¯α ∈ (0, 1)|(φ(α), µ(α), x
k
(α), y
k
(α), s
k
(α)) ∈ N, ∀α ⊂ (0, ¯α]}
其中：(x
k
(α), y
k
(α), s
k
(α)) = (x
k
, y
k
, s
k
) + α(∆x
k
, ∆y
k
, ∆s
k
)。
step4. 求点 (x
k+1
, y
k+1
, s
k+1
)
(x
k+1
, y
k+1
, s
k+1
) = (x
k
, y
k
, s
k
) + α
k
(∆x
k
, ∆y
k
, ∆s
k
))
φ
k+1
= (1 − τα
k
)φ
k
µ
k+1
= (1 − ηα
k
)µ
k
若 φ
k+1
⩽ ε，终止迭代；否则置 k := k + 1，返回 step2。
http://www.ma-xy.com 13 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二阶椎规划
算法性质：
¬设 (x
k
, y
k
, s
k
) ∈ N，选取 β ∈ (0,
1
5
)，0 < ρ < 1，0 < τ < 1 − ρ < η <
1−5β
1+2
√
2r−3β
，假定
(∆x
k
, ∆y
k
, ∆s
k
) 为非精确方程的解，且满足 ∆
T
x
k
, ∆s
k
⩾ 0，令 ¯α = (1 − 2
√
2τ − η)β/4τ
2
，则
当 α ∈ (0, ¯α] 时，有 (φ(α), µ(α), x
k
(α), y
k
(α), s
k
(α)) ∈ N。
多项式收敛性。设 {(x
k
, y
k
, s
k
)} 为算法产生的序列，且 ∆
T
x
k
∆s
k
⩾ 0。令 ϵ > 0，β ∈ (0,
1
5
)，
ρ ∈ (0, 1)。如果 0 < τ < 1 −ρ < η <
1−5β
1+2
√
2r−3β
，则算法至多经过 K = O(
√
rlnε
−1
) 次迭代终止。
1.3.3
预估校正算法
1996 年 Miao 提出了关于线性规划的两个不可行内点预估—校正算法。预估方向分别采
用了牛顿方向和欧拉方向，每次迭代算法需要接两个线性方程组。算法是全局收敛的，且有
O(n ln(1/ε)) 迭代复杂性界。n 为线性规划中自变量 x 的维数。而且预估方向是牛顿方向的算法
在最优解存在的假设下还具有 Q - 二阶收敛性。
step1. 初始化。
ε > 0, β ∈ (0,
1
4
]，γ 是一个与 β 相关的常数。取 (x
0
, y
0
, s
0
) ∈ N (β, µ
0
)，µ
0
=
(x
0
)
T
s
0
r
，置
k := 0。
step2.(确定预估方向) 求如下方程组得到预估方向 (∆x
p
, ∆y
p
, ∆s
p
)。
A∆x
p
= r
p
k
A
T
∆y
p
+ ∆s
p
= r
d
k
L
k
s
∆x
p
+ L
k
x
∆s
p
= −L
x
s
k
牛顿方向
L
k
s
∆x
p
+ L
k
x
∆s
p
= −µ
k
e 欧拉方向
step3. 确定步长 α
k
(x(α), y(α), s(α)) = (x
k
, y
k
, s
k
) + α(∆x
p
, ∆y
p
, ∆s
p
)
α
k
= max{α ∈ [0, 1]| ∥L
x
(α)s(α) − (1 − α)µ
k
e∥ ⩽ Γβ(1 − α)µ
k
}
x(α), s(α) ∈ K × K
令 (ˆx
k
, ˆy
k
, ˆs
k
) = (x
k
, y
k
, s
k
) + α
k
(∆x
p
, ∆y
p
, ∆s
p
)。
step4. 确定搜索方向。
如果 α
k
= 1，则停止迭代，(ˆx
k
, ˆy
k
, ˆs
k
) 为最优解，否则求解如下方程组，得到校正方向
(∆x
c
, ∆y
c
, ∆s
c
)
A
∆
x
c
= 0
A
T
∆y
c
+ ∆s
c
= 0
ˆ
L
k
s
∆x
c
+
ˆ
L
k
x
∆s
c
= (1 − α
k
)µ
k
e −
ˆ
L
k
x
ˆs
k
http://www.ma-xy.com 14 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.3 最优化算法
step5. 求 (x
k+1
, y
k+1
, s
k+1
)。
(x
k+1
, y
k+1
, s
k+1
) = (ˆx
k
, ˆy
k
, ˆs
k
) + (∆x
c
, ∆y
c
, ∆s
c
)
µ
k+1
=
x
k+1
T
s
k+1
r
若 (x
k+1
, y
k+1
, s
k+1
) ∈ S
ε
，终止迭代；否则置 k := k + 1，返回 step2。
算法收敛性：
1. 序列 {x
k
, y
k
, s
k
} 的任意聚点都属于解集；
2. 序列 {(x
k
)
T
· s
k
}, {r
p
k
}, {r
d
k
}Q-线性收敛到零；
3. 序列 {(x
k
)
T
· s
k
}, {r
p
k
}, {r
d
k
}Q-二次收敛到零。
注：二阶锥规划的二阶锥约束虽是用凸点锥，但在顶点处不光滑。
1.3.4 基于核函数的原始-对偶内定算法
原始-对偶内点法的基本思想是：首先选取中心路径上的一个初始值，然后寻求一个使对偶
间隙逐渐见效的搜索方向，再在该搜索方向上确定一个合适的步长，使得迭代点仍是二阶锥规划
问题的严格可行解。下面，我们用一个核函数来确定搜索方向。
定义 (核函数) 称单变量函数 φ : R
++
→ R
+
为一个核函数，如果 φ 满足
φ
′
(1) = φ(1) = 0
φ
′′
(
t
)
>
0
lim
t→0
φ(t) = lim
t→∞
φ(t) = ∞
显然，φ 是严格凸的并且在 t = 1 处取极小值 φ(1) = 0。目前，已有文献研究的核函数的增
长项大部分是二次的。例如：
φ(t) =
t
p+1
− 1
p(p + 1)
+ φ
b
(t) t ⩾ 0
其中：φ
b
(t) 为核函数的阻碍项，且 p ⩾ 1，这里，函数增长项设为 p + 1 ⩾ 2。
下面，我们给出一个新的线性增长项核函数
φ(t) = t − 1 +
1
σ
(e
σ (t
−1
−1)
− 1) t > 0, σ ⩾ 1
其中：φ(t) 的增长项 t − 1 是线性的。
我们先来补充一下基础内容，然后再介绍算法。前面，我们定义了 K = K
n
, x = (x
1
, ¯x) ∈ R
n
，
其对称矩阵为
L
x
=
x
1
¯x
T
¯x x
1
I
∈ R
n×n
http://www.ma-xy.com 15 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二阶椎规划
其中：I 为 n − 1 × n − 1 单位矩阵。记矩阵 L
x
的最小特征值与最大特征值
为 λ
1
, λ
2
，则有
λ
1
(x) = x
1
− ∥¯x∥
λ
2
(x) = x
1
+ ∥¯x∥
易知
x ∈ K ⇔ λ
2
(x) ⩾ λ
1
(x) ⩾ 0
x ∈ intK ⇔ λ
2
(x) ⩾ λ
1
(x) > 0
引理 设 x, s ∈ R
n
，有
λ
1
(x + s) ⩾ max{λ
1
(x) −
√
2∥s∥, λ
1
(x) −
√
2∥x∥}
另外，记特征值 λ
1
, λ
min
≜ λ
2
对应的特征向量为 u
(1)
, u
(2)
，Tr(x) 为迹，det(x) 为行列式。
迹函数 Tr(x) 有如下性质：对 ∀x, s ∈ R
n
，有
Tr(x ◦ s) = 2x
T
s
Tr(x ◦ x) = 2∥x∥
2
引理 设 x, y, z ∈ K，有
Tr((x ◦ s) ◦ z) = Tr(x ◦ (y ◦ z))
引理 设 x ∈ R
n
, s ∈ K，有
λ
2
(x)Tr(s) ⩽ Tr(x ◦ s) ⩽ λ
1
(x)Tr(s)
利用向量 x 的特征值分解，我们可以将任意实值函数 ϕ(t) : R
++
→ R
+
扩展到 intK 到 K
的映射：
定义 设 ϕ : R
++
→ R
+
且 x ∈ R
n
，向量 u
(1)
, u
(2)
为特征向量，定义向量值函数 ϕ(x) 如下
ϕ(x) = ϕ(λ
2
(x))u
(1)
+ ϕ(λ
1
(x))u
(2)
x ∈ intK
即
ϕ(x) =
ϕ(λ
2
(x)) + ϕ(λ
1
(x))
2
,
ϕ(λ
1
(x)) + ϕ(λ
2
(x))
2
¯x
∥¯x∥
¯x = 0
(ϕ(λ
1
(x), 0, ··· , 0)) ¯x = 0
引理 设 ϕ : R
++
→ R
+
且 x ∈ intK，则 ϕ(x) ∈ K。
注：前面已经定义了 λ
max
= λ
1
, λ
min
= λ
2
。
http://www.ma-xy.com 16 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.3 最优化算法
引理 设 ϕ : R
++
→ R
+
是二次可微的，如果 ϕ
′′
(t) 是单调下降的，则有
λ
1
(x)(ϕ
′′
(t)) = ϕ
′′
(λ
2
(x)) x ∈ intK
当讨论的空间为 R
n
时，φ(·)φ
′
(·) 表示向量值函数；当讨论的空间为 R 时，φ(·)φ
′
(·) 表示单
变量函数。易知
φ
′
(t) = 1 −
e
σ( t
−1
−1)
t
2
φ
′′
(t) =
(σ + 2t)e
σ (t
−1
−1)
t
4
φ(1) = φ
′
(1) = 0
lim
t→0
φ(t) = lim
t→∞
φ(t) = +∞
并且 φ(t) 是严格凸的。
基于 φ(t)，定义 intK 上一个实值障碍函数 ψ(x) 如下：
ψ(x) = Tr(φ(x)) = 2(φ(x))
1
= φ(λ
2
(x)) + φ(λ
1
(x)) x ∈ intK
这里，(φ(x))
1
表示向量 φ(x) 的第一个分量。
因为对于任意的 t > 0，都有 φ(t) ⩾ 0，并且 λ
1
(x) ⩾ λ
2
(x) > 0(x ∈ intK)，所以有
ψ(x) ⩾ 0(x ∈ intK)。此外，因为 φ(t) = 0，当且仅当 t = 1，所以 ψ(x) = 0。当且仅当
λ
1
(x) = λ
2
(x) = 1，即当且仅当 x = e。同理，ψ
′
(x) = 0 当且仅当 φ
′
(λ
1
(x)) = φ
′
(λ
2
(x)) = 0，
即当且仅当 λ
1
(x) = λ
2
(x) = 1。这是因为核函数 φ(t) 是严格凸并且在 t = 1 处取得最小值。归
纳起来，可写为
ψ(x) = 0 ⇔ φ(x) = 0 ⇔ φ
′
(x) = 0 ⇔ x = e
引理 ∀x ∈ intK，ψ(x) 是非负和严格凸的并且在 x = e 处取得极小值。
令 x(t) = (x
1
(t), . . . , x
n
(t)) 为 t 的函数，用 x
′
(t) 表示 x 关于 t 的导数，即
x
′
(t) = (x
′
1
(t), x
′
2
(t) . . . , x
′
n
(t))
则有
d
dt
(x(t) ◦ s(t)) = x
′
(t) ◦ s(t) + x(t) ◦ s
′
(t)
d
dt
Tr(φ(x(t))) = Tr(φ
′
(x(t)) ◦ x
′
(t))
将上述理论推广到 K = K
n
1
× K
n
2
× ··· × K
n
r
上，函数 φ(x) 和 ψ(x) 的定义分别是
φ(x) = (φ(x
1
), ··· , φ(x
r
))
ψ(x) =
r
i=1
ψ(x
i
) =
r
i=1
Tr(φ(x
i
))
http://www.ma-xy.com 17 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二阶椎规划
而 φ
′
(x) 定义为
φ
′
(x) = (φ
′
(x
1
), φ
′
(x
2
), . . . , φ
′
(x
r
))
新的搜索方向
带扰动 µ 的 KKT 方程为
Ax = b x ∈ K
A
T
y + s = c s ∈ K
L
x
s = µe
利用牛顿法，得到关于搜索方向 (∆x, ∆y, ∆s) 的方程组：
A∆x = 0 x ∈ K
A
T
∆y + ∆s = 0 s ∈ K
L
x
∆s + L
s
∆x = µe − L
x
s
当且仅当 AL
−1
L
x
A
T
非奇异时，上述方程组有唯一的解，但这个条件通常很难满足，即使
A 是满秩的。主要原因在于 L
x
L
s
和 L
s
L
x
通常不相等。我们对上述方程组进行一定的变换，然
后再求解。下面，我们采用NT-换算方法 来进行处理。
对任意的 x
i
, x
i
∈ intK
i
以及 i ∈ J = {1, 2, . . . , r}，定义 NT-换算矩阵 W
i
如下
w
i
=
(s
i
1
)
2
− ∥(¯s)
i
)∥
2
(x
i
1
)
2
− ∥(¯x)
i
∥
2
1
4
(¯s)
i
= (¯s
i
1
,
¯
¯s
i
) = w
−1
i
(s
i
1
, ¯s
i
)
(¯x)
i
= (¯x
i
1
,
¯
¯x
i
) = w
i
(x
i
1
, ¯x
i
)
ζ
i
= (ζ
i
1
,
¯
ζ
i
) = (¯x
i
1
+ ¯s
i
1
,
¯
¯s
i
−
¯
¯x
i
)
α
i
=
ζ
i
1
Γ(ζ
i
)
, β
i
=
¯
¯
ζ
i
Γ(ζ
i
)
Γ(ζ
i
) =
(ζ
i
1
)
2
− (
¯
¯
ζ
i
)
T
¯
ζ
i
W
i
= w
i
α
i
β
T
i
β
i
I +
β
i
β
T
i
1+α
i
引理 (1) (1) w
i
x
i
= (w
i
)
−1
s
i
；(2) Tr(w
i
x
i
◦ (w
i
)
−1
s
i
) = Tr(x
i
◦ s
i
)；(3) det((w
i
)x
i
) =
λ
i
−1
det(x
i
)，det((w
i
)
−1
s
i
) = λ
i
−1
det(s
i
)，λ
i
=
det
(
s
i
)
det(x
i
)
；(4) x
i
∈ K
i
(intK
i
) ⇔ W
i
x
i
∈
K
i
(intK
i
)。
定义
v
i
:=
W
i
x
i
√
µ
=
(W
i
)
−1
s
i
√
µ
i ∈ J
http://www.ma-xy.com 18 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.3 最优化算法
引理 ∀i ∈ J，有
µ
2
det((v
i
)
2
) = det(x
i
) det(s
i
)
µTr((v
i
)
2
) = Tr(x
i
◦ s
i
)
进一步，定义
W = diag(w
1
, w
2
, ··· , w
r
)
则
v = (v
1
, v
2
, ··· , v
r
) =
W x
√
µ
令
¯
A =
AW
−1
√
µ
，dx =
W ∆x
√
µ
，ds =
W
−1
∆s
√
µ
，则原方程组变为
¯
Adx = 0
¯
A
T
∆y + ds = 0
L(W
−1
v)W ds + L(W v)W
−1
dx = e − L(W
−1
v)W v
上述方程组可能不存在解，为克服这一缺点，将第三个等式换为
L(v)ds + L(v)dx = e − L(v)v
即
ds + dx = e − L(v)
−1
e − v = v
−1
− v
因此，方程组变为
¯
Adx = 0
¯
A
T
∆y + ds = 0
ds + dx = v
−1
− v (1.1)
因为
¯
A
¯
A
T
正定，故上述方程组有唯一解。注意到，如果采用典型的对数障碍函数
φ(t) =
t
2
− 1
2
− log t
则 −φ
′
(t) = t
−1
− t，从而有 −φ
′
(v) = v
−1
− v。
下面，将 (1.1) 式右边替换为 −φ
′
(v)。这里 φ(t) 为核函数，因此我们的搜索方程为
¯
Adx = 0
¯
A
T
∆y + ds = 0
ds + dx = −φ
′
(v)
http://www.ma-xy.com 19 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二阶椎规划
上述方程组有唯一解，求解完方程组后，由NT-换算 有
∆x =
√
µW
−1
dx
∆s =
√
µW ds
由
ψ(x) = 0 ⇔ φ(x) = 0 ⇔ φ
′
(x) = 0 ⇔ x = e
易知
ψ(v) = 0 ⇔ φ(v) = 0 ⇔ φ
′
(v) = 0 ⇔ v = e
由方程组，我们有
ds = −
¯
A
T
∆y
d
T
s
dx = −∆y
T
¯
Adx = 0
即 dx, ds 是正定的。因此，当且仅当 φ
′
(v) = 0，当且仅当 v = e 有 dx = ds = 0。
引理 φ
′
(v) = 0，当且仅当 x ◦ s = µe。
由上述引理知，如果 (x, y, s) = (x(µ), y(µ), s(µ))，则 (∆x, ∆y, ∆s) 是非零的。沿此搜索方
向，利用先搜索技术确定步长 α
k
，即可得到更新点。
步长 α
k
的选取
设 W
i
为 K
i
的自同构，并满足 W
i
x
i
= (W
i
)
−1
s
i
。定义
v
i
=
W
i
x
i
√
µ
=
(W
i
)
−1
s
i
√
µ
d
i
x
=
W
i
∆x
i
√
µ
=
(W
i
)
−1
∆s
i
√
µ
则有
W
i
(x
i
+ αx
i
) =
√
µ(v
i
+ αd
i
x
)
(W
i
)
−1
(s
i
+ αs
i
) =
√
µ(v
i
+ αd
i
s
)
由引理 1 可知
µ
2
det(v
i
+ αd
i
x
) det(v
i
+ αd
i
s
) = det(x
i
+ α∆x
i
) det(s
i
+ α∆s
i
)
µTr((v
i
+ αd
i
x
) ◦ (v
i
+ αd
i
s
)) = Tr((x
i
+ α∆x
i
) ◦ (s
i
+ α∆s
i
))
另一方面，设 W
i
+
是 K
i
的自同构，并满足 W
i
+
x
i
+
= (W
i
+
)
−1
s
i
+
。定义
v
i
+
=
W
i
+
x
i
+
√
µ
=
(W
i
+
)
−1
s
i
+
√
µ
http://www.ma-xy.com 20 http://www.ma-xy.com
http://www.ma-xy.com
第一章 二阶椎规划 1.3 最优化算法
其中：x
i
+
= x
i
+ α∆x
i
，s
i
+
= s
i
+ α∆s
i
。
由引理 1 可知
µ
2
det((v
i
+
)
2
) = det(x
i
+ α∆x
i
) det(s
i
+ α∆s
i
)
µTr((v
i
+
)
2
) = Tr((v
i
+ αd
i
x
) ◦ (v
i
+ α∆d
i
s
))
引理 如果 x, s, z ∈ intK，满足
det(z
2
) = det(x) det(s)
Tr(z
2
) = Tr(x ◦ s)
则有
ψ(z) ⩽
1
2
(ψ(x) + ψ(s))
由上述引理，我们有
ψ
(
v
i
+
) ⩽
1
2
(ψ(v
i
+ αd
i
x
) + ψ(v
i
+ αd
i
s
))
将上述不等式两边关于 i 求和，有
ψ(v
+
) ⩽
1
2
(ψ(v + αd
x
) + ψ(v + αd
s
))
定义 ψ(v) 的改变量为
f(α) = ψ(v
+
) − ψ(v)
定义
f
1
(α) =
1
2
(ψ(v + αdx) + ψ(v + αds)) − ψ(v)
则 f(α) ⩽ f
1
(α)。易知 f(0) = f
1
(0) = 0，因为 f
1
(α) 是凸的 (但 f(α) 不一定是凸的)。
将 f
1
(α) 关于 α 求导
f
′
1
(α) =
1
2
Tr(φ
′
(v + αdx) ◦ dx + φ
′
(v + αds) ◦ ds)
f
′
1
(0) =
1
2
Tr(φ
′
(v) ◦ (dx + ds)) = −
1
2
Tr(φ
′
◦ φ
′
) = −2δ(v)
2
将 f
1
(α) 关于 α 二次求导
f
′′
1
(α) =
1
2
Tr(φ
′′
(v + αdx) ◦ (dx ◦ ds) + φ
′′
(v + αds) ◦ (ds ◦ ds))
为简化分析，定义
λ
2
(v) = min{λ
2
(v
i
)|i ∈ J}
λ
1
(v) = max{λ
1
(v
i
)|i ∈ J}
http://www.ma-xy.com 21 http://www.ma-xy.com
http://www.ma-xy.com
1.3 最优化算法 第一章 二阶椎规划
注意到，如果 f
1
(α) ⩽ 0，那么新的迭代点严格可行，这是因为当新的迭代点趋向于可行域边界
时，f
1
(α) 将趋向于无界。
显然，理想的步长是使 f
1
(α) 最小的 α。下面，我们给出一个默认 (缺省) 步长
引理
f
′′
1
(α) ⩽ 2δ
2
φ
′′
(λ
2
(v) − 2αδ)
引理 如果 α 满足
−φ
′
(λ
2
(v) − 2αδ) + φ
′
(λ
2
(v)) ⩽ 2δ (1.2)
则有 f
′
1
(α) ⩽ 0
引理 设 ρ : [0 , ∞) → (0, 1] 是函数 −
1
2
φ
′
(t) 在 (0, 1] 上的反函数，则满足 (1.2) 式的步长 α
的最大值为
¯α =
ρ(δ) − ρ(2δ)
2δ
引理
¯α ⩾
1
φ
′′
(ρ(2δ))
引理 如果 α 满足 0 < α ⩽ ¯α，则有
f(α) ⩽ −αδ
2
定义 t = ρ(2δ)，由 ρ 的定义可知
−φ
′
(t) = 4δ =
e
σ (t
−1
−1)
t
2
− 1
从而有
e
σ (t
−1
−1)
= t
2
(4δ + 1)
进而
t
−1
= 1 +
1
σ
log t +
1
σ
log(4δ + 1)
因为 0 < t ⩽ 1，所以
t
−1
⩽ 1 +
1
σ
log(4δ + 1)
因此，可得
¯α ⩾
1
φ
′′
(t)
=
t
4
(σ + 2t)e
σ( t
−1
−1)
⩾
1
(σ + 2)(4δ + 1)(1 +
1
σ
log(4δ + 1))
2
定义缺省步长为 ˜α
˜α =
1
(σ + 2)(4δ + 1)(1 +
1
σ
log(4δ + 1))
2
http://www.ma-xy.com 22 http://www.ma-xy.com