第 十 二 章 二次规划
§12.1 二次规划问题
称形如
1 , 2 , ,
2
1m in ( )
2
s. t.
,
, { },
, { 1 , , }
e
e
TT
T
ii
T
i i e
f x x G x r x
a x b i
a x b i m m m
Em
I
??
? ? ???
??
? ?
?
(12.1.1)
的非线性规划问题为二次规划问题 ，其中 G 是 nn? 对称矩 阵， ,, nix r a ?? ， ib?? ，
1,2 ,,i m? ? . 问题 (12.1.1)的可行域仍记为 D ，即
{ | , ;},n T Ti i i iD x a ix b E a x ibI? ? ? ? ?? ? .
对于 二次规划问题 (12.1.1)， 由定理 9.1.3 可知，如果 x 是 问题 (12.1.1)的局部极小点，
则必存在乘子 ( 1, 2, , )i im? ? ? ，使得
1
,
0 ,
0
,
0 , ,,
( ) 0 , .
m
i
i
T
ii
T
i
i ii
T
ii i
r G x a
a x b i
a x b
ax
iI
bi
E
I
?
?
?
?
??
??
? ?
?
?
?
?
?
?
?
(12.1.2)
进一步，由定理 9.2.1 可知， 对于满足
0 , ( )T id a i E I x???
的 一切 nd?? ，都有 0Td Gd? .
反过来，设 x 是 问题 (12.1.1)的 K-K-T 点， ? 是相应的 Lagrange 乘子，如果对满足
0 , ,
(0,
0 ,
) ,
( 0 ) ,
T
i
T
i
T
ii
a i E
d a I
d
x
d a I
i
i x ?
?
?
?
?
? ?
?
(12.1.3)
的一切非零向量 nd?? ，都有 0Td Gd? ，则 由定理 9.2.2 可知， x 是 (12.1.1)的严格 局部
极小点 .
特别地，当 G 为半正定矩阵时， (12.1.1)中的目标函数 ()fx 为凸函数，可行域 D 为凸
集，从而二次规划问题 (12.1.1)为凸规划，由 定理 9.3.3 可知，这时， x 是（ 12.1.1）的全局
极小点的充分必要条件为 x 是（ 12.1.1）的 K-K-T 点 .
对于非凸函数 ()fx， 二次规划问题 (12.1.1)有如下充分必要条件 .
第十二章 二次 规划
210 最优化理论与方法 [乌力吉 ]
定理 12.1.1 设 x 是 问题 (12.1.1)的可行解，则 x 是 (12.1.1)的 局部 极小 点的 充分必要 条
件是 x 是 (12.1.1)的 K-K-T 点且 对一切满足 (12.1.3)的 d 都有 0Td Gd? .
证 必要性 . 设 x 问题 (12.1.1)的局部极小点，则由定理 9.1.4 和定理 9.1.3 可知 x 是
(12.1.1)的 K-K-T 点 . 设 d 是满足 (12.1.3)的任一非零向量，显然，对充分小的 0t? ，有
x Dtd? ? ，
于是 ，由 d 满足 (12.1.3)式，我们有
22( ) ( 1( ) ) ( ) 2 ( )TTf x t d f x tf x d t d f xx df? ? ? ? ? ??
22
1
11( ) ( )22m T T Ti
i if x t d a t d Gd f x t d Gd??? ? ? ? ??
，
这表明 0Td Gd? .
充分性 . 设充分条件成立，即存在 ( , )x ? 满足 (12.1.2)且 对一切满足 (12.1.3)的 d 都有
0Td Gd? . 如果 x 不是 (12.1.1)的局部极小点， 则存在可行 点列 {}kx 收敛到 x 且满足
(( ) )kf fxx ? . 令
1 ||, (| | )k k kk
kxdx x x? ?? ? ??
， 1,2,k? ? ，
显然， 0( )k k? ? ??， 且 有界序列 {}kd 有收敛子列，不妨设 lim
k k dd?? ?
.
由于每个 kx 都是可行点 ， 故有
) ( )1 [( ] 0 ,T k T k Ti i i i ikaad x b a ix b E? ? ? ? ? ?? ， (12.1.4)
) ( ) ]1 [( 0 , ( )T k T k Ti i i i ikd x b aa a ix b I x? ? ? ? ? ?? . (12.1.5)
记 { ( ) | }0ii I xI ?? ?? ?，以及
| 0 ,{(;, ) }0n T TiiK x Ea x i a x i Ix? ? ?? ??? ，
0 |{ ( 0 , ; 0 \}, )n T TiiK x E Ia x i a x i I x I??? ? ? ? ? ??? ,
显然， K 和 0K 都 是多面锥，且由 (12.1.4)和 (12.1.5)看到， {}kdK? .
由凸分析可知，在多面锥 K 中存在有限个元素 12, , , lyy y? ， 称为多面锥 K 的基， 对任
意 x K? ，存在非负数 12, , , l? ? ?? ，满足
1 1 2 2 lly y yx ? ? ?? ? ?? ?.
由于 0KK? ， 故按 0 ( 1, 2 ,, )jyjKl? ? ?是否成立， 我们把 K 的基 12, , , lyy y? 分成 两部
分，不妨设
1 2 0, , , ry y y K?? ， 1 2 0, , , \r r ly y Ky K?? ?? .
易见，对于每个 (1 )j lyr j??? ， 至少存在一个 )(iaiI?? ，使得 0Tija y ? ，从而，对每
§ 12.1 二次规划问题
最优化理论与方法 [乌力吉 ] 211
个 (1 )j lyr j??? ，有
0TijIi ay?? ?? .
设 jy 是 jy 在 0K 上的投影， 2 ,1, ,r r lj ??? ? ，则存在一个正数 0M? ，满足
|| || Tj j i ji IMy y a y??? ? ??, 2 ,1, ,r r lj ??? ? .
因此，对任意 x K? ，有
11
rl
j j j jj j rx yy??? ? ??? ?? 11 [ ( ])
rl
j j j j jjr jjy y yy??? ? ???????
1 1 1 ( )
r l l
j j j j jj j r j rjj yy y y???? ? ? ? ?????? ? ?
，
设 x 是 x 在 0K 上的投影，由于
1 01
rl
j jjjj j ry y K??? ? ?????
，
故有
0|| || in f || ||z Kx x x z?? ? ? 11|| |( )|
rl
jj j jj j rx y y??? ? ?? ? ???
1 )|| ( ||j
l
jjjr y y?????? 1 )|| ||
l
jjjr jyy??????
1
l T
ijjr i IjM ay? ??? ?? ?? 1
l
jjrTiji I ayM ?? ???? ??
11
rl
j j j jTi j j ri IM y ya ??? ? ? ??
??? ???
??? ? ?i TiI axM ??? ?
.
对每个 k ， 设 kd 为 kd 在 0K 上 的 投影， 则由于 0kd K? 满足 (12.1.3)式，故由充分条件
知
( 0)k T kd Gd ? . (12.1.6)
因此
( ) [ ( ) ] [ ( ) ]k T k k k k T k k kd G d Gd d d d d d??? ? ?
( ) ( ) ( )k T k k k T k kGGd d d d d d? ? ? ?
( ) ( )k k T k kd d d dG? ? ?
2 2 2|| || || || || ||k k k kGd d d d? ? ? ? ? ?
22 || || TkiIiGaM d??? ? ??
，
(12.1.7)
另一方面， 将 ()kfx 在 x 处 Taylor 展开，得
) (kkkfxx df ???
第十二章 二次规划
212 最优化理论与方法 [乌力吉 ]
221( ) ( ) ( )2( ) T k k T kkkf x d d x df fx??? ?? ? ?
2
1
1( ) ( )2Tkm
i
k T kk i i kf x a d d G d? ? ?
?? ? ??
21( ) ( ) ( )2
i
T k k T kk i i k
I Gf x a d d d f x? ? ???? ? ? ??
，
(12.1.8)
如果 I??? 或 对 某个 k ，有 0,Tkia Idi?? ? ，则由充分条件知 ( 0)k T kd Gd ? ，与上式矛
盾，故 I??? 且 对任意 k ， 都 有
0TkiIi a d?? ?? . (12.1.9)
于是，由不等式 (12.1.7)和 (12.1.8)，我们有
10 ( )2T k k T kii
Ii k Ga d d d???????
2( m i n 2 || || )i Tki k iI IiGM ad??? ?? ??? ?
，
注意到不等式 (12.1.9)以及 0( )k k? ? ??，我们可以肯定上述不等式对充分大的 k 不成立，
这一矛盾表明 x 只能是 (12.1.1)的局部极小点 .
§12.2 二次规划的对偶问题
对于二次规划问题 (12.1.1)，称二次极大化问题
1m a x ( , ) )
2
s.t. ,
0 ,
TT
i
T
TL x x G x r x A x b
G x r A
iI
??
?
?
? ? ? ?
??
??
（
(12.2.1)
为 问题 (12.1.1)的 Wolfe 对偶 ，其中 mn? 矩阵 A 的第 i 行为 Tia ， 1,2 ,,i m? ? .
当 G 为正 定 矩阵 时，令 Ty Gx A r?? ? ?，则 (12.2.1)可改写为
11m a x ( , )
2
s.t. ,
0 , .
TT
T
i
Q y b y G y
A y r
iI
??
?
?
???
??
??
(12.2.2)
如果 x 是 二次规划问题 (12.1.1)的可行解，而 ( , )y? 是 其 对偶问题 (12.2.2)的可行解，则
有
111( ) ( , ) ( )22T T T TTf x Q y x G x A y x b y G y? ? ? ?? ? ? ? ? ?
111)22T T T Tx G x A x b y x y G y? ?? ? ? ? ?（
§ 12.2 二次规划的对偶问题
最优化理论与方法 [乌力吉 ] 213
1
1
1 ( 2 )2m T T T Ti i i
i a x b x Gx y G y x y?
?
?? ? ? ? ?? （ ）
111 ( ) ( ) 02TTi i i
iI a x b x G y G x G y?
??
?? ? ? ? ? ?? （ ）
，
其中 等式成立 的充分必要条件是 0
Ti i i
iI a x b?? ??? （ ）
且 1x G y?? . 由此，我们得到如下定
理 .
定理 12.2.1（对偶定理） 设 x 是二次规划问题 (12.1.1)的可行解，而 ( , )y? 是其对偶问题
(12.2.2)的可行解，则有 (( )) ,Qf yx ?? ；若存在原始问题 (12.1.1)的可行解 x 和对偶问题
(12.2.2)的可行解 ( , )y? ，使得 ( ) ( , )f x Q y?? ，则 x 和 ( , )y? 分别是原始问题和
对偶问题的最优解 .
由于当且仅当 0
Ti i i
iI a x b?? ??? （ ）
且 1x G y?? 时，有 (( )) ,Qf yx ?? ，故有如下定理 .
定理 12.2.2 若 G 为正定矩阵，则原始问题 (12.1.1)的可行解 x 是最优解的充分必要条件
是存在对偶问题 (12.2.2)的可行解 ( , )y? 满足 1x G y?? 且 0
Ti i i
iI a x b?? ??? （ ）
.
定理 12.2.3 若 G 为正定矩阵，则原始问题不可行当且仅当对偶问题无界 .
证 若 原始 问题可行，则由 ( ) ( , )f x Q y?? 可知 对偶问题有界 . 若 原始 问题不可行， 则
利用 Farkas 引理可构造 一个 无界的对偶可行解，故对偶问题无界 .
下面考察 Lagrange 函数
1( , ) )2 T T TL x x G x r x A x b??? ? ? ?（，
显然， ( , )Lx? 的梯度和 Hesse 矩阵分别为
( , ) TG x r ALx b A x ?? ????? ?????? ， 2 ( , ) TGALx A? ???? ????? ?O.
当 G 为正定矩阵时， 由于矩阵
1
IAG I
???????
O 可逆，且满足
11
1TT
T
IGG A I G AA G I A G AAI ?
? ?
? ? ? ??? ? ? ??? ? ? ?? ? ? ???
? ? ? ?? ? ? ?
OO OOO，
故 2 ( , )Lx?? 恰 有 n 个正特征值，而且它的负特征值的个数正好为 A 的秩 ，因此 ， ( , )Lx? 的
稳定点 是 鞍点 .
事实上， 对于原始问题 (12.1.1)的任意可行点 x D? ， 有
1m a x ( , ) m a x [ ( ) ( ] ( )
m T
i i iiL x f x a x b f x????? ? ? ? ?? ? ? ?? ）
，
其中 ? ?| 0 ,m i iI??? ? ? ? ?? 是对偶问题 (12.2.1)的可行域 .
反过来，对于对偶问题 (12.2.1)的任意可行点 ??? ，由于 ( , )Lx? 是 x 的凸函数， 故
第十二章 二次规划
214 最优化理论与方法 [乌力吉 ]
min ( , )nx Lx??? 的最优解可由 方程 ( , ) 0xLx???解出 ，即满足 TGx r A ??? ， 令 Ty A r???，
则 y Gx? ，从而
11m i n ( , ) ( , )2n TTx L x b y G y Q y? ? ??? ? ? ?? .
设 ( , )x ? 二次规划问题 (12.1.1)的 K-K-T 点 ，令 Ty A r???，则 x 是原始问题
(12.1.1)的可行点， ( , )y? 是对偶问题 (12.2.2)的可行点 ， 并对任意 nx?? 和 ??? 有
( , ) ( , ) ( , ) ( ) ( , )L x Q y L x f x L x? ? ? ?? ? ? ?，
故 ( , )x ? 是 ( , )Lx? 的鞍点 . 更一般地，我们有如下定理 .
定理 12.2.4 设 G 正定，则 x D? 是问题 (12.1.1)的最优解 的 充分必要 条件是：存在
??? ，使对一切 nx?? 和 ??? ，都有 ( , ) ( , ) ( , )L x L x L x? ? ???.
§12.3 等式约束问题
本节我们讨论只有等式约束条件的二次规划问题
1m in ( )
2s.t . , TTf x x Gx r xAx b??? (12.3.1)
其中 mn? 矩阵 A 是行满秩的，即 ()R A m? . 显然，问题 (12.3.1)的 Lagrange 函数为
1( , ) )2 T T TL x x G x r x A x b??? ? ? ?（， (12.3.2)
K-K-T 条件为
, . TGx A rAx b?? ? ? ?? ?
?
(12.3.3)
如果 G 为半正定矩阵，则问题 (12.3.1)是凸规划，这时， K-K-T 条件 (12.3.3)的解就是问
题 (12.3.1)的最优解，从而求解问题 (12.3.1)可以转化为求解线性方程组 (12.3.3)，这种方法称
为 Lagrange 乘子法 .
§12.3.1 直接 消去法
由于 ()R A m? ，故 矩阵 A 的列向量的秩也等于 m ， 不妨设 A 的前 m 列向量线性无关，
并对 问题 (12.3.1)中的 矩阵和向量做如下分块 ：
? ? BNA A A? ， B
N
xx x?????
??
， BB BN
N B N N
GGG ??? ??
??
， B
N
rr r?????
??
，
由矩阵 G 的对称性可知， TNB BNG G? . 将 它们 代入 问题 (12.3.1)，得
§ 12.3 等式约束问题
最优化理论与方法 [乌力吉 ] 215
1m in ( ) [ ]
2s . t. . N N NT T T T T TB B B B B B N N B B B BN N N
BN
NN
BN
f x x G x x G x x G x x G x r x r
A x x
x
Ab
? ? ? ? ? ?
??
(12.3.4)
而由 BNBNA x A x b??可解出
1 1 1()BNB BNNNBx A b A x A b A A x? ? ?? ? ? ?，
将其代入问题 (12.3.4)，得到关于自变量 Nx 的无约束最优化问题
1 ?) 2? ? ?m i n (
nmN TTN N N Nx Nf x x r x cxG?? ?? ??
， (12.3.5)
其中
11? T T T TN N N N B B N N B B N N B B B B NG G G A A A A G A A G A A? ? ? ?? ? ? ?，
1? ()T T T TN N N B B NB N B B B Br r A A r G A A G A b? ? ?? ? ? ?，
111? 2 T T TB B B B B Bc b A G A b r A b? ? ???.
无约束最优化问题 (12.3.5)的最优性条件为
)? 0( ? ?N N N NG x rfx? ? ? ?. (12.3.6)
如果 G 是正定矩阵 (或半正定矩阵 )，则 由 列满秩矩阵 1BNAAP
I
???????
??
满足关系
1? ( ) B B B NT T T BN
N N B N B N N
GG AAG P G P A A I I?? ??? ? ?? ? ? ????
?? ??
可知，矩阵 ?NG 是正定矩阵 (或半正定矩阵 ).
因此，当 ?NG 为 正定矩阵时，严格凸二次函数 ?()Nfx 有唯一的极小点 1?N N Nx G r??? ，
从而二次规划问题 (12.3.1)有唯一解
1 1 1
1
? ?
? ?B B B N N NN NNx A b A A G rx x Gr
? ? ?
?
??????? ????
??? ??
，
对应的乘子为
( )TB B B B B N N BA G x G x r? ?? ? ?.
当 ?NG 为 半正定矩阵 但不是正定矩阵 时，凸二次函数 ?()Nfx 有 无穷多个 极小点，由于凸
函数的驻点必为极小点，故 ?()Nfx 的极小点 Nx 可通过求解线性方程组 (12.3.6)得到，从而
得到二次规划问题 (12.3.1)的最优解
11
? ? ? ? ()B B N NBN N N N NA b A A xxx x G r I G G x
??
??
??????? ????
? ? ??? ??
，
这里 ?NG? 是 ?NG 的广义逆， nmx ??? 任意 .
当 ?NG 有负特征值 时，凸二次函数 ?()Nfx 没有极小值，从而二次规划问题 (12.3.1)没有最
第十二章 二次规划
216 最优化理论与方法 [乌力吉 ]
优解 .
§12.3.2 广义消去法
直接消去法虽然方法简单，便于 理解和 实现，但在实际计算中所选择的 BA 有可能接近
奇异，使得算法数值不稳定 . 为了 克服 这样的缺陷， 我们 提出如下的广义消去法 .
AV 是矩阵 A 的行向量生成的 n? 中子空间， AV? 是 AV 的正交补空间，即
{ | }A nV z A z? ???0? ，
由于 ()R A m? ，故 dim AVm? ， dim AV n m? ??.
设 12, , , myy y? 是 AV 的一个基， 12, , , nmzz z ?? 是 AV? 是一个基，并令
12[ ]myYy y? ? ， 12[ ]nmzzZz ?? ? ，
显然有 AZ?O ， 并 假设 mAY I? ， 这里 mI 是 m 阶单位矩阵 .
事实上， 由于 A 的行向量和 Y 的列向量都是子空间 AV 的基，故存在过渡可逆矩阵 P ，
满足 TY AP? ，由此可知 TAY AA P? ，而由矩阵 A 是行满秩知，矩阵 TAA 是正定矩阵从
而可逆，因此矩阵 AY 可逆 . 若令 1()Y Y AY ?? ，则有 mAY I? ，且 Y 的列向量等价于 Y
的列向量，从而 Y 的列向量也是子空间 AV 的基，因此，不妨假设 mAY I? .
对任意 nx?? ， x 可以唯一地分解为
12x xx? ? ， 1 Ax V? ， 2 Ax V?? ，
即存在 ?, nxx?? ，满足
?x Yx Zx??，
把它代入约束条件 Ax b? 得 xb? ，再把 ?x Yb Zx??代入二次规划问题 (12.3.1)，得到无约
束最优化问题
?
11? ? ? ? ?m i n ( ) ( ) ( 2 )22
n TTx f x x Z G Z x r G Y b Z x r G Y b Y b? ? ? ? ? ??
. (12.3.7)
如果 G 为正定矩阵，则由 Z 列满秩知， TZGZ 为正定矩阵，从而 (12.3.7)有唯一 的极小
点
1? ( ) ( )TTx Z G Z Z r G Y b?? ? ?， (12.3.8)
由此得到二次规划问题 (12.3.1)的最优解
1 ( ) ( )TTx Y b Z Z G Z Z r G Y b?? ? ?， (12.3.9)
相应的乘子为
( )TY Gx r? ??
11[ ( ) ] [ ( ) ]T T T T T T TY G G Z Z G Z Z G Y b Y Y G Z Z G Z Z r??? ? ? ?. (12.3.10)
§ 12.3 等式约束问题
最优化理论与方法 [乌力吉 ] 217
因此，一旦确定了矩阵 Y 和 Z ，就可计算最优解 x 及其乘子 ? . 特别地，取
1BAY ??????
??O
， 1BNAAZ
I
???????
??
， (12.3.11)
则广义消去法就是前面介绍的直接消去法 .
在实际计算中，我们一般用下面的方法来构造矩阵 Y 和 Z . 首先将 TA 进行 QR 分解，
即
? ?1 2 1T RRA Q Q Q Q R? ? ? ?? ? ?? ? ? ?? ? ? ?OO， (12.3.12)
其中 Q 是 n 阶正交矩阵， R 是 m 阶 可逆 上三角矩阵， 12,QQ分别是前 m 列和后 nm? 列构
成的矩阵 . 然后取
11()TY Q R?? ， 2ZQ? ， (12.3.14)
显然，
111( ) ( )T T T mA Y R Q R IQ ???， 12()TTAZ QRQ??O，
且矩阵 ? ? YZ 非奇异 .
§12.3.3 Lagrange 乘子法
如果 G 为半正定矩阵，则问题 (12.3.1)是凸规划，这时， K-K-T 条件 (12.3.3)的解就是问
题 (12.3.1)的最优解，从而求解问题 (12.3.1)可以转化为求解线性方程组 (12.3.3)，这种方法称
为 Lagrange 乘子法 .
在线性方程组
T xrGA
bA ? ???? ? ? ? ????? ? ? ??? ? ? ? ???O
(12.3.15)
中， 如果其系数矩阵可逆，记
1TTG A Q R
A R S
?? ? ? ????
? ? ? ???? ? ? ?O ， (12.3.16)
则由逆矩阵的定义，我们得到矩阵方程
,
,
,
.
T
n
TT
nm
mn
T
m
G Q A R I
G R A
AQ
S
A R I
?
?
? ??
????
? ??
?
? ?
?
?
O
O
(12.3.17)
如果 G 是可逆的，则从上述方程解得
第十二章 二次规划
218 最优化理论与方法 [乌力吉 ]
1 1 1 1 1
1 1 1
11
( ) ,
( ) ,
( ) ,
TT
T
T
Q G G A A G A A G
R A G A A G
S A G A
? ? ? ? ?
? ? ?
??
? ???
??
? ???
(12.3.18)
从而，线性方程组 (12.3.15)的解为
,.Tx Qc R bRc Sb?? ? ? ?? ??
?
(12.3.18)
上述 x 就 是二次规划问题 (13.3.1)的 K-K-T 点 ，而 ? 是其对应的乘子 .
如果存在矩阵 ,YZ满足 §12.3.2 中的条件，且 TZGZ 是正定矩阵，则 矩阵
TGA
A????????O
(12.3.19)
是 非奇异的 ， 这是因为齐次线性方程组
, TGx AAx ?? ???
?
00 (12.3.20)
有解 意味着
( ) 0T T T TG x x Ax A x????? ，
且由 Ax?0 知，存在 nmu ??? ，满足 x Zu? ，代入上式，得
0TTu Z GZu ? ，
由 TZGZ 是正定矩阵的假设知， u?0 ，从而 x?0 ，由于 A 是行满秩的，故齐次线性方程
组 (12.3.20)只有零解，从而矩阵 (12.3.19)非奇异的 .
矩阵 (12.3.19)非奇异 表明 (12.3.18)中的 K-K-T 点及其乘子唯一存在 ， 当满足 §12.3.2 中条
件的矩阵 ,YZ存在时， 在矩阵方程 (12.3.17)中，假设
TR Y ZM?? ，
其中 M 为待定 n 阶方阵，显然，上述 TR 满足其中的第四个方程， 对其第二个方程两边左
乘 TZ 得到 TTZ GR ?O ，再代入上述 TR ，由此可以确定
1)( TTM Z GGZ Z Y?? ，
故
1( )T T TGGRZ ZYYZ Z??? ，
对其第二个方程两边再左乘 TY ，并代入上述 TR ，得
1)(T T T TS Y G G Z Z YZZ G Y Y G? ?? ，
再把上述 R 代入第一个方程，我们发现， 等式 (12.3.18)的矩阵可由公式
§ 12.4 积极集法
最优化理论与方法 [乌力吉 ] 219
1
1
1
()
)
,
)
(,
(,
TT
T T T
T T T T
G Z Z G Y
Q Z Z G Z
Y G G Z Z G Y Y G
Z
R Y Z Z
S Z Z Y
?
?
?
? ??
??
?
??
??
(12.3.21)
来 计算 .
这表明 Lagrange 方法也是一种广义消去法 .
§12.4 积极集法
本节讨论二次规划问题（ QP）的一般形式
1 , 2 , ,
2
1m in ( )
2
s. t.
,
, { },
, { 1 , , }
e
e
TT
T
ii
T
i i e
f x x G x r x
a x b i
a x b i m m m
Em
I
??
? ? ???
??
? ?
?
(12.4.1)
其中 G 是 nn? 对称矩阵， ,, nix r a ?? ， ib?? ， 1,2 ,,i m? ? .
在当前可行迭代点 kx 的充分小邻域 ? 内，由于非积极约束并不起到约束作用，故在邻
域 ? 内求解二次规划问题 (12.4.1)可以写成
1 , 2 , ,
1m in ( )
2
s . t. , { } ,
(, ) { | 0 }
e
TT
T
ii
T
ii
k T k
ii
f x x G x r x
a x b i
a x b
Em
Ii x i I a x b
??
? ??
? ? ? ? ??
?
由 §12.3 看到，具有等式约束的二次规划问题容易求解，因此，我们 把 上述最优化问题
简化为求解子问题
1m in ( )
2
s .t. ) , (
TT
Tii k
f x x G x r x
a x b i IE x
??
???
(12.4.2)
记 ()kk IIE x?? ， 若令 kx dx? ? ，则 子问题 (12.4.2)等价于求解二次规划问题
1m in
2
s .t. 0 ,
() TkT
Ti k
fd G d d
a d i I
x?
?
?
?
(12.4.3)
其中 ()kkfx rGx?? ?.
算法 12.1（ 二次规划问题的积极集 法）
步 1： 给定初始可行点 0x D? ，令 00 ()IIE x?? ，置 0k? ；
步 2： 求解等式约束二次规划子问题 (12.4.3)得到最优解 kd ，若 kd ?0 ，则转步 4；
步 3： 若 0( )kiki I I? ? ? ?，则算法结束，输出近似解 kx ，否则 取
m {in }|kkki i kIi I? ? ??? ， (12.4.4)
第十二章 二次规划
220 最优化理论与方法 [乌力吉 ]
令 1 \{}k k kI Ii? ? ， 1kkx x? ? ， 转步 6；
步 4： 计算可行步长的上界
m i 0 , \n T TiikiT
i
k k
kkb a x a d iad II? ???? ??????
，
令 {1 }min , kk? ?? ， 置 1k k kkx x d?? ?? ；
步 5： 若 1k?? ，则 取 1kkI I? ? ，否则取 1 {}kkII j? ?? ， 其中 \ kj II? 满足 1Tjjka x b? ? ；
步 6： 置 1kk??，转步 2.
下面简单分析算法 12.1 的合理性 .
(I) 如果子问题 (12.4.3)的最优解 kd ?0 ，则 kx 就是 等式约束 子问题
1m in ( )
2
s .t. , k
TT
Tii
f x x G x r x
a x b i I
?
? ?
?
(12.4.4)
的最优解 ，下面分两种情形讨论 .
(Ia) 如果这时 kx 对应的 Lagrange 乘子 0( )kiki I I? ? ? ? ， 则由 下面的 定理可知， kx 是
原问题 (12.4.1)的 K-K-T 点 .
定理 12.4.1 若某个 kx 是二次规划问题 (12.4.1)的最优解，则 kx 必是等式约束二次规划子
问题 (12.4.2)的最优解，反过来，若某个 kx 是等式约束子问题 (12.4.4)的 K-K-T 点，且还是原
问题 (12.4.1)的可行点，则当相应的乘子 k? 满足 0ki?? ( ki II?? )时， kx 必为原问题 (12.4.1)
的 K-K-T 点 .
证 设 kx 是二次规划问题 (12.4.1)的最优解，由于 kx 本身是子问题 (12.4.2)的可行点，若
它不是子问题 (12.4.2)的最优解，则在点 kx 的任意充分小的邻域
{ | || |) |}(;kkxxN xx ?? ???
中都有子问题 (12.4.2)的可行点 ( );kNxx? ?? ，满足
( ) ( )kf x f x? ? ，
但当 ? 充分小， x? 充分靠近 kx 时，它必成为原问题 (12.4.1)的一个可行点，从而与 kx 是原问
题 (12.4.1)的 最优解矛盾 .
反过来，设 kx 是等式约束子问题 (12.4.4)的 K-K-T 点，则存在乘子 )(kiki I? ? ，满足
k
kki
i iIGx r a?????
，
,Tiik ka x b i I?? ，
再由 kx 是原问题 (12.4.1)的可行点，有
,\Tiik ka x b i I I?? ，
§ 12.4 积极集法
最优化理论与方法 [乌力吉 ] 221
这时，令 \0( )kiki II? ?? ，故当 0ki?? ( ki II?? )时，由 (12.1.2)式可知， kx 是原问题 (12.4.1)
的 K-K-T 点 .
(Ib) 如果这时 kx 对应的 Lagrange 乘子满足
mi { ( ) } 0n|kk k kii Ixi? ? ?? ?，
则由 kx 是子问题 (12.4.4)的最优解知， kx 是子问题 (12.4.4)的 K-K-T 点，故有
()
k
k k k T ki i k
iIGx r a Af x ??????? ? ?
，
其中 kA 是以 )(TikaiI? 为行向量的矩阵， ()
kkkiiI????
. 如果 kA 的行向量线性无关，则向
量
1( ) kTTk k k iAAd A e??
满足
1) ( )( ) ( ) ( 0k k kk T T k T T T k T kk k k k i i iA A e ef x d A A? ? ???? ? ? ?， (12.4.5)
1( ) kkTTk k k k k i iAAA d A A e e???， (12.4.6)
其中
kie
是第 ki 个分量为 1其余 分量均为零的单位向量 . 不等式 (12.4.5)意味着上述 d 是 目标
函数 ()fx在 kx 处的下降方向，而等式 (12.4.6)表明 d 在 kx 处满足等式约束
0, }\ {Ti k kd i Ia i??
以及 可行 条件 0
kiTad?
， 因此， 如果 我们 令 \{}k k kI Ii? ，然后 再去 求解子问题 (12.4.3)， 则
其最优解必 为 ()fx在 kx 处的下降方向 .
(II) 如果子问题 (12.4.3)的最优解 kd ?0 ， 则 kd 是 ()fx 在 kx 处的下降方向 . 类似于线
性规划的单纯形法，我们为了保证迭代点的可行性，必须要求
( ) ,T k kiix td b i Ea ? ? ?， (12.4.7)
( ) ,T k kx td b i Ia ? ? ?， (12.4.8)
由 kx 的可行性及 0,Tki Ea di??知 (12.4.7)显然成立，而让不等式 (12.4.8)成立， t 不能超过
m i 0 , \n T TiikiT
i
k k
kkb a x a d iad II? ???? ??????
.
定理 12.4.2 设点列 {}kx 是由算法 12.1 产生的，若对任何 k ，向量组
{ | ( )}kia i E I x??
总是 线性无关，则算法 12.1 或有限 步 终止于原问题的 K-K-T 点，或原问题无下界 .
证 如果原问题无下界，则定理得证 . 故不妨设 原问题 (12.4.1)有下界 ， 这时， 由算法 12.1
是 可行 点 方法 可知 ， 它所 产生的 点列 {}kx 也必 有界 . 下面只须证点列 {}kx 必 有限 步终止 .
反证 . 假设 {}kx 为无穷点列 ， 由于原问题 (12.4.1)中约束条件的个数有限，故 kI 中的元
第十二章 二次规划
222 最优化理论与方法 [乌力吉 ]
素数不可能无限增加，这意味着在算法 12.1 中， 存在无穷指标集 1K ， 使得
1, k Kdk??0 . (12.4.9)
对于每个 1k K? ， 由 原问题只有有限多个约束 知 ， 存在无穷指标集 10KK? ，使对任
意 120,k kK? ，有
12kkI I?
， 而当 1k K? 时， kx 必为等式约束子问题 (12.4.4)的最优解，从
而对任意 120,k kK? ， 都有
12(( ))kkf fxx ? . (12.4.10)
设 0k 是 0K 中的最小自然数，则 由 等式 (12.4.10)以及 算法 12.1 是一个下降算法 可知 ， 当
0kk? 时，就有
0(( ))kk fxfx ? . (12.4.11)
于是 ，由前面的分析 (Ib)可知 ， 当 0kk? 时， 在算法 12.1 中， 或者 kd ?0 ， 或者 kd ?0
但 0k?? ，从而 ，对每个 0kk? ，都有
0kkx x? .
(12.4.12)
当 0kk? 时， 如果 kd ?0 ，则必有 1kd? ?0 ，若不然，由等式约束子问题 (12.4.4)的 K-K-T
条件 以及算法 12.1 的步 3 可 知
0 \ { }11
k k k
k k
i i i
k k ki i i i
IIa G x G x Gr r rxa??
??
????? ??????
，
且 0
kki??
，但这 与 { | }ikaiI? 线性无关矛盾 . 因此， 由 0K 是无穷指标集 可知，对每个 0kk? ，
kd ?0 和 kd ?0 只能交替出现 ，从而有
0 0 0 0
0 0 0\{
2
( }) {
2
}k k k
k k k kii
ii I ij iiI rra G x G x a??
??
? ???? ? ? ???
.
(12.4.13)
由 0 1kd ? ?0 必为下降方向，我们有
0 0 0 0 0 0 0 000
0
1 1 1 1 10 ( ) ( ) kk
k
k k k k k k k kT T T Ti ii
i iIf x fd d a d a dx ??
? ? ? ? ?
?? ? ??? ??
，
由于
00 0kki? ?
， 故有
00 1 0k kTiad? ?
；
(12.4.14)
而由 算法 12.1 步 4 中下标 j 的选择可知，
0 1 0kTjad? ? . (12.4.15)
不等式 (12.4.14)和 (12.4.15)表明下标
0kj i?
， 于是，由等式 (12.4.13)以及
00 0kki? ?
可知，
向量组
0| { } }{ ika i j I??
线性相关， 但这 与定理的假设矛盾 .
§12.5 Lemke 转轴法
本节讨论如下二次规划问题
§ 12.6 路径跟踪法
最优化理论与方法 [乌力吉 ] 223
1m in ( )
2
s.t. ,
TTf x x G x r x
A bx
x
?
??
? 0
(12.5.1)
其中 G 是 nn? 对称矩阵， , nxr?? ， A 是 mn? 矩阵且 Rank( )Am? ， mb???? .
二次规划问题 (12.5.1)的 Lagrange 函数为
1( , , ) ( )2 T TTTL x y u x G x r x y A x b xu? ? ? ? ?， (12.5.2)
其中 ,mnyu????是相应的 Lagrange 乘子 . 因此，二次规划问题 (12.5.1)的 K-K-T 条件为
( ) 0 ,
,
,,
, , 0 .
T
T
T
G x r A
A x b A
yu
yy
ux
x
u
b
x
??
??
? ? ?
? ???
? ? ??
??
0
00
00
令 w Ax b?? ，则上述 K-K-T 条件可以写成如下形式
,
, , 0 ,
,,
,
0.
T
T
T
yu
y
G x r A
A x w b
w
x
yw
u x u
??? ??
? ? ? ??
?
?
?
? ? ?
??? ?
0
00
00
0 (12.5.3)
如果再令
,,T r x uGAM q z vb y wA??? ? ? ? ? ? ?? ? ? ??? ? ? ? ? ? ??? ? ? ? ? ???O ，
则 (12.5.3)式相当于
, , 0Tv M z q zz v? ? ? ? ?00， (12.5.4)
这是一个标准的线性互补问题 LCP(q,M)， 因此， 我们可以用算法 10.5 来求解 K-K-T 条件
(12.5.3).
当矩阵 G 是半正定矩阵时，线性互补问题 (12.5.4)是可求解的，且其解为原问题 (12.5.1)
的最优解 .
§1 2.6 路径跟踪法
本节讨论如下二次规划问题
1m in ( ) 2
s .t.
TTf x x G x r x
A x b
??
?
(12.6.1)
其中 G 是 nn? 对称 正定 矩 阵， , nxr?? ， A 是 mn? 矩阵且 Rank( )Am? ， mb???? .
第十二章 二次规划
224 最优化理论与方法 [乌力吉 ]
令 w Ax b?? ，则 二次规划问题 (12.6.1)的 K-K-T 条件为
,
,,
0 , 1, 2 ,
,
,,
T
jj
y
w
G x r A
A
w j m
x w b
y
y
?
??
??
? ??
? ? ? ??
?
?
??
0
00
0
?
即有
,
,
,
,
,
TG x r A
A x w b
w
y
y
YW e
? ??
? ??
?
??
?
???
?
??
0
0
0
00 (12.6.2)
其中 12, , , )d ia g ( myYy y? ?， 12, , , )d ia g ( mwWw w? ?， (1,1, ,1)Tme ? ?? ?.
路径跟踪 法是引入光滑因子 0?? ，得到 K-K-T 条件 (12.6.2)的松弛形式
,
,
,
,
,
TG x r A
A
y
y
Y
x
W
b
e
w
e
w
?
?
?
? ??
? ? ? ??
?
?
?
?
? ?
0
00
0 (12.6.3)
类似于定理 11.6.1， 我们可以证明： 在适当条件下， 对每个正数 ? ，松弛 K-K-T 条件
(12.6.3)存在唯一的内点解 ( ( ), ( ), ( ))x y w? ? ?，一般把点集 { ( ( ) , ( ) , ( ) ) | 0 }x y w? ? ? ? ?称
为中心路径 .
二次规划问题的 路径跟踪 法的基本思想是利用牛顿法求解非线性方程组 (12.6.3)，并逐
步减小参数 ? ，使其趋向于零 . 下面给出具体算法 .
算法 12.2（ 二次规划问题 的路径跟踪法）
步 1： 给定初始点 0 0 0)(,,xyw ，其中 000, 0y w??，参数 (0,1)?? ， (0,1)p? ，容
许误差 0?? ，置 0k? ；
步 2： 计算 k kb Ax w? ? ?? ， k T kr G x A y? ? ? ? ， ()k T kyw? ? ， m???? ；
步 3： 如果 11m a x { || || , || || , }? ? ? ??，则停止迭代，输出近似最优解 ( , , )k k kywx ；
步 4： 确定搜索方向，求解线性方程组
T
k k k k
G A x
A I y
W Y w e Y W e
?
?
?
???? ? ? ? ??? ? ? ? ?
? ? ?? ? ? ?
? ? ? ???? ? ? ???
O
O
O
，
§ 12.6 路径跟踪法
最优化理论与方法 [乌力吉 ] 225
得解 ( , ),k k kyxw???；
步 5： 确定步长，计算
1 ,m a x { , }
j
j
kki
kki j n i
wyyw?
??
??? ? ?，
取步长 min{ / ,1}p??? ；
步 6： 置 1k k kxxx ?? ??? ， 1k k ky y y?? ??? ， 1k k kw w w?? ??? ；
步 7： 置 1kk??，转步 2.
第十二章 二次规划
226 最优化理论与方法 [乌力吉 ]
|
|
