第六章二 次 规 划研究问题
Iibxa
Eibxats
xCGxxxq
i
T
i
i
T
i
TT
.
1
2
1
m in
其中 G 是 nn? 对称阵．
注,(1)若 Hesse阵是半正定的,则称为凸二次规划，此问题有时并不比求解线性规划困难．
(2)对非凸二次规划，可能有多个局部极小点，
求解比较困难．
§ 6.2 解析法等式约束二次规划
bxAts
xgGxxxq
T
TT
.
2
1
m in
其中,,mnm RARb
以下假设 A 为列满秩的,即,mAr?
直接消去法对等式约束中矩阵 A 进行分块,使得
BA
为
mm? 阶非奇异方阵,此时等式约束可改写成：
bxAxA NTNBTB
相关的量 Agx,,与 G 作如下分块：
N
B
NNNB
BNBB
N
B
N
B
g
g
g
GG
GG
G
A
A
A
x
x
x
其中,,mnNmB RxRx 其余类似．
该分块使得
BA
为 mm? 阶非奇异方阵,因此
1?BA 存在,此时由上面方程可得：
NTNTBB xAbAx 1
将此代入,xq 则可将等式约束二次规划转化为下列无约束优化问题：
cxgxGx NTNTN
Rx mnN
21m in
其中 T
NTBBBBNBNBNTNTBNBNN AAGAAGAAAAGGG 11?
bAGAAGgAAgg BBBBNNBBBNN 111
bAgbAGAbc TBTBTBBBBT 121?
如果 G? 正定,则可求出无约束问题的最优解为
, 1* gGx N 代入可确定对应的,*Bx 从而得到二次规划最优解：
gG
gGAAbA
x
x
x
T
N
T
B
T
B
N
B
1
1
*
*
*
相应的最优 Lagrange乘子 *? 可由下式确定，
** GxgA
只需考虑该方程组的前 m 行就可以给出,*?
**1* NBNBBBBB xGxGgA
例 1,用直接消去法求解：
31
21.
1m in
32
321
2
3
2
2
2
1
xx
xxxts
xxxxq
解,由 (3)可得,4132 xx
将上式代入 (2)可得,52 31 xx
上面两式就是在变量分解,,,321 xxxxx NB
将 (4)(5)代入 (1)可得：
614m in 232323
3
xxxRx
由 (6)可得：,
2
1
3?x
代入可得,.
2
1,
2
3,1* Tx?
利用 ** GxgA 可得：
*
2
*
1
11
11
01
1
3
2
由上式可得 Lagrange乘子,.1,2 *2*1
Lagrange方法等式约束的二次规划问题的 Lagrange函数为：
bxAxgGxxxL TTTT 21,
KT条件为,
0, AgGxxxL
0,
bxAxL T
矩阵形式为：
1.6
0?
b
gx
A
AG
T?
系数矩阵称为 KKT矩阵．
定理 1:假设 A 为列满秩矩阵,,mAr? 若投影
Hesse阵 GZZT 正定,则等式二次规划问题的
KKT矩阵,
0TA
AG
K
是非奇异的,从而存在唯一的 KKT对**,?x
满足方程组 (6.1).
例 2,用 Lagrange方法求解：
02
042.
m in
321
321
2
3
2
2
2
1
xxx
xxxts
xxxxq
解：
2
2
2
G
2
4b
11
12
11
A
2?Ar
2
4
0
0
0
00111
00121
11200
12020
11002
2
1
3
2
1
x
x
x
7
4,
7
8,
7
6,
7
10,
7
2,** TTx?
其中,
7
6,
7
10,
7
2* Tx?
7
4,
7
8*? 为最优乘子,
作 业
(1)用 Lagrange方法求解：
1.
2m in
21
2121
2
2
2
1
xxts
xxxxxxxf
§ 6.3 有效集方法严格凸二次规划
mlIibxa
lEibxats
xCGxxxf
i
T
i
i
T
i
TT
,,10
,,10.
1
2
1
m in
其中 G 是 nn? 对称阵．
当 G 为正定阵时,(1)为严格凸二次规划．
理论基础定理 2,设 *x 是二次规划问题 (1)的局部极小点，
则 *x 必是问题：
221m in xCGxxxf TT
*0,IEibxaxcts iTii
的局部极小点,反之，如果 *x 是 (1)的可行点,
且是 (2)的 KT点,而且相应的乘子 *? 满足：
**,0 xIii
则 *x 必是问题 (1)的 KT点．
证明,设 *x 是 (1)的可行点,且是 (2)的 KT点，
因此存在ExIi
i?**
使得：
0
*
**
ExIi
ii aCGx
****,0,0 xIibxa iiTii
定义,**,,0 xIiIi
i
可知,?
m
i
ii aCGx
1
** 0?
Iibxa iTiii,0,0 ***
再由 *x 是 (1)的可行点,可知是 (１ )的 KT点,
算法原理设 kx 是 (1)的一个可行解,相应的有效集为
,kI kA 为 A 中对应于 kI 的子阵,求解二次规划：
k
T
k
TT
bxAts
xCGxxxf
.
3
2
1
m in
容易证明,(3)与下面二次规划等价：
0.
4
2
1
m in
dAts
dgGdddq
T
k
T
k
T
其中 CGxxfgdxx kkkk,
分析,当 0?
kd
时,kx 为 (3)的最优解,若对应
Lagrange乘子非负,则 kx 为 (1)的最优解,
当 0?
kd
时,并且
kk dx?
为 (1)的可行解,则令;1 kkk dxx 否则以 kd 为方向作线搜索,以求得更好的可行点．
步长的选取方法,由于xf 为凸二次函数,故最优解必在边界上达到,设步长,,0 1 kkkkk dxx
由可行性要求有, kikkkTi Iibdxa
即,5kkTiikTik Iixabda
因为 kx 为可行解,故 kkTii Iixab,非正．
在 (5)中,当 0?kTi da 时,k 恒成立；
当 0?kTi da 时,要求,
k
k
T
i
k
T
ii
k Iida
xab
此时6,0m in
k
T
t
k
T
tt
k
T
i
k
T
i
k
T
ii
Iikk da
xabda
da
xab
k
合并,7,1m in
kk
分析,当 1?
k?
时,;
1 kk II
当 1?
k?
时,即
kk
时,则存在某个,
kIt?
在 1?kx 处增加了一个有效约束,.
1 tII kk
当 0?
kd
时,且 Lagrange乘子有负分量,若
,0?sk? 则 kx 不是 (1)的最优解．
此时需要找可行下降方向．
(4)中删去第 s 个约束,所得到的新的二次规划问题的最优解必为一个可行下降方向．
二次规划的有效集算法
Step1,给出,1x 确定 ;1,1?kI
Step2,求解 (4)得最优解,kd
若,0?
kd
则转 Step4; 否则转 Step3;
Step3,计算 (4)的 Lagrange乘子向量,
k?
并求,m in
ikIisk k
若,0?
sk?
则
kx
为 (1)的最优解，停；
否则,令,\ sII
kk?
相应改变
kA
转 Step2
Step4,由 (7)确定,k? 令 ;1 kkkk dxx
Step5,若,1?
k?
则令,
1 tII kk
其中 t 由 (6)确定； 否则令 ;
1 kk II
Step6,令,1 kk 转 Step2；
有效集算法收敛定理定理 3,若在有效集算法中,每步迭代 kA 为列满秩且,0?
k?
则算法有限步收敛到问题 (1)的最优解．
例 3,用有效集法解二次规划：
01
0
0.
42m in
2133
222
111
21
2
2
2
1
xxbxa
xbxa
xbxats
xxxxxf
T
T
T
解：
2
1
2
1
21 422
2
2
1
x
x
x
x
xxxf
4
2
2
2
2
1
x
x
xg
取2,1,0,0 11 Ix T
0
0.
4,2
2
2
2
1
,
2
1
m in
2
1
211
d
dts
ddd
ddddgGdddq
T
TTT
求解：
2
11
00?
gd
A
AG
T
即：
0
0
4
2
0010
0001
1020
0102
2
1
2
1
d
d
得, TTT xd 0,04,20,0
211
因,044,2m in21
故令,12\12 II
0.
4,2
2
2
2
1
,
2
1
m in
1
212
dts
ddd
ddddgGdddq
T
TTT
求解：
0
4
2
001
020
102
1
2
1
d
d
得, 2,2,0
22Td
求步长：
0,3,2m in
2
2
2
2 daida
xab T
iT
i
T
ii?
3,1
2
1
2
1
23
233
t
da
xab
T
T
所以,,1,0,222322 Tdxx
,3,1323II
求解, dgGdddq TT
32
1m in
0
0.
2,2
2
2
2
1
21
1
dd
dts
ddd
T
即：
0
0
2
2
0011
0001
1020
1102
3
1
2
1
d
d
得, TTT xd 1,02,00,0
433
因,03
所以,1,04* Txx 相应,2,0,0* T
作 业
(1)用有效集方法求解：
0
0
623.
102m in
2
1
21
21
2
221
2
1
x
x
xxts
xxxxxxxf
取初始可行点,
2
5,0
1
T
x?
Iibxa
Eibxats
xCGxxxq
i
T
i
i
T
i
TT
.
1
2
1
m in
其中 G 是 nn? 对称阵．
注,(1)若 Hesse阵是半正定的,则称为凸二次规划，此问题有时并不比求解线性规划困难．
(2)对非凸二次规划，可能有多个局部极小点，
求解比较困难．
§ 6.2 解析法等式约束二次规划
bxAts
xgGxxxq
T
TT
.
2
1
m in
其中,,mnm RARb
以下假设 A 为列满秩的,即,mAr?
直接消去法对等式约束中矩阵 A 进行分块,使得
BA
为
mm? 阶非奇异方阵,此时等式约束可改写成：
bxAxA NTNBTB
相关的量 Agx,,与 G 作如下分块：
N
B
NNNB
BNBB
N
B
N
B
g
g
g
GG
GG
G
A
A
A
x
x
x
其中,,mnNmB RxRx 其余类似．
该分块使得
BA
为 mm? 阶非奇异方阵,因此
1?BA 存在,此时由上面方程可得：
NTNTBB xAbAx 1
将此代入,xq 则可将等式约束二次规划转化为下列无约束优化问题：
cxgxGx NTNTN
Rx mnN
21m in
其中 T
NTBBBBNBNBNTNTBNBNN AAGAAGAAAAGGG 11?
bAGAAGgAAgg BBBBNNBBBNN 111
bAgbAGAbc TBTBTBBBBT 121?
如果 G? 正定,则可求出无约束问题的最优解为
, 1* gGx N 代入可确定对应的,*Bx 从而得到二次规划最优解：
gG
gGAAbA
x
x
x
T
N
T
B
T
B
N
B
1
1
*
*
*
相应的最优 Lagrange乘子 *? 可由下式确定，
** GxgA
只需考虑该方程组的前 m 行就可以给出,*?
**1* NBNBBBBB xGxGgA
例 1,用直接消去法求解：
31
21.
1m in
32
321
2
3
2
2
2
1
xx
xxxts
xxxxq
解,由 (3)可得,4132 xx
将上式代入 (2)可得,52 31 xx
上面两式就是在变量分解,,,321 xxxxx NB
将 (4)(5)代入 (1)可得：
614m in 232323
3
xxxRx
由 (6)可得：,
2
1
3?x
代入可得,.
2
1,
2
3,1* Tx?
利用 ** GxgA 可得：
*
2
*
1
11
11
01
1
3
2
由上式可得 Lagrange乘子,.1,2 *2*1
Lagrange方法等式约束的二次规划问题的 Lagrange函数为：
bxAxgGxxxL TTTT 21,
KT条件为,
0, AgGxxxL
0,
bxAxL T
矩阵形式为：
1.6
0?
b
gx
A
AG
T?
系数矩阵称为 KKT矩阵．
定理 1:假设 A 为列满秩矩阵,,mAr? 若投影
Hesse阵 GZZT 正定,则等式二次规划问题的
KKT矩阵,
0TA
AG
K
是非奇异的,从而存在唯一的 KKT对**,?x
满足方程组 (6.1).
例 2,用 Lagrange方法求解：
02
042.
m in
321
321
2
3
2
2
2
1
xxx
xxxts
xxxxq
解：
2
2
2
G
2
4b
11
12
11
A
2?Ar
2
4
0
0
0
00111
00121
11200
12020
11002
2
1
3
2
1
x
x
x
7
4,
7
8,
7
6,
7
10,
7
2,** TTx?
其中,
7
6,
7
10,
7
2* Tx?
7
4,
7
8*? 为最优乘子,
作 业
(1)用 Lagrange方法求解：
1.
2m in
21
2121
2
2
2
1
xxts
xxxxxxxf
§ 6.3 有效集方法严格凸二次规划
mlIibxa
lEibxats
xCGxxxf
i
T
i
i
T
i
TT
,,10
,,10.
1
2
1
m in
其中 G 是 nn? 对称阵．
当 G 为正定阵时,(1)为严格凸二次规划．
理论基础定理 2,设 *x 是二次规划问题 (1)的局部极小点，
则 *x 必是问题：
221m in xCGxxxf TT
*0,IEibxaxcts iTii
的局部极小点,反之，如果 *x 是 (1)的可行点,
且是 (2)的 KT点,而且相应的乘子 *? 满足：
**,0 xIii
则 *x 必是问题 (1)的 KT点．
证明,设 *x 是 (1)的可行点,且是 (2)的 KT点，
因此存在ExIi
i?**
使得：
0
*
**
ExIi
ii aCGx
****,0,0 xIibxa iiTii
定义,**,,0 xIiIi
i
可知,?
m
i
ii aCGx
1
** 0?
Iibxa iTiii,0,0 ***
再由 *x 是 (1)的可行点,可知是 (１ )的 KT点,
算法原理设 kx 是 (1)的一个可行解,相应的有效集为
,kI kA 为 A 中对应于 kI 的子阵,求解二次规划：
k
T
k
TT
bxAts
xCGxxxf
.
3
2
1
m in
容易证明,(3)与下面二次规划等价：
0.
4
2
1
m in
dAts
dgGdddq
T
k
T
k
T
其中 CGxxfgdxx kkkk,
分析,当 0?
kd
时,kx 为 (3)的最优解,若对应
Lagrange乘子非负,则 kx 为 (1)的最优解,
当 0?
kd
时,并且
kk dx?
为 (1)的可行解,则令;1 kkk dxx 否则以 kd 为方向作线搜索,以求得更好的可行点．
步长的选取方法,由于xf 为凸二次函数,故最优解必在边界上达到,设步长,,0 1 kkkkk dxx
由可行性要求有, kikkkTi Iibdxa
即,5kkTiikTik Iixabda
因为 kx 为可行解,故 kkTii Iixab,非正．
在 (5)中,当 0?kTi da 时,k 恒成立；
当 0?kTi da 时,要求,
k
k
T
i
k
T
ii
k Iida
xab
此时6,0m in
k
T
t
k
T
tt
k
T
i
k
T
i
k
T
ii
Iikk da
xabda
da
xab
k
合并,7,1m in
kk
分析,当 1?
k?
时,;
1 kk II
当 1?
k?
时,即
kk
时,则存在某个,
kIt?
在 1?kx 处增加了一个有效约束,.
1 tII kk
当 0?
kd
时,且 Lagrange乘子有负分量,若
,0?sk? 则 kx 不是 (1)的最优解．
此时需要找可行下降方向．
(4)中删去第 s 个约束,所得到的新的二次规划问题的最优解必为一个可行下降方向．
二次规划的有效集算法
Step1,给出,1x 确定 ;1,1?kI
Step2,求解 (4)得最优解,kd
若,0?
kd
则转 Step4; 否则转 Step3;
Step3,计算 (4)的 Lagrange乘子向量,
k?
并求,m in
ikIisk k
若,0?
sk?
则
kx
为 (1)的最优解，停；
否则,令,\ sII
kk?
相应改变
kA
转 Step2
Step4,由 (7)确定,k? 令 ;1 kkkk dxx
Step5,若,1?
k?
则令,
1 tII kk
其中 t 由 (6)确定； 否则令 ;
1 kk II
Step6,令,1 kk 转 Step2；
有效集算法收敛定理定理 3,若在有效集算法中,每步迭代 kA 为列满秩且,0?
k?
则算法有限步收敛到问题 (1)的最优解．
例 3,用有效集法解二次规划：
01
0
0.
42m in
2133
222
111
21
2
2
2
1
xxbxa
xbxa
xbxats
xxxxxf
T
T
T
解：
2
1
2
1
21 422
2
2
1
x
x
x
x
xxxf
4
2
2
2
2
1
x
x
xg
取2,1,0,0 11 Ix T
0
0.
4,2
2
2
2
1
,
2
1
m in
2
1
211
d
dts
ddd
ddddgGdddq
T
TTT
求解：
2
11
00?
gd
A
AG
T
即：
0
0
4
2
0010
0001
1020
0102
2
1
2
1
d
d
得, TTT xd 0,04,20,0
211
因,044,2m in21
故令,12\12 II
0.
4,2
2
2
2
1
,
2
1
m in
1
212
dts
ddd
ddddgGdddq
T
TTT
求解：
0
4
2
001
020
102
1
2
1
d
d
得, 2,2,0
22Td
求步长：
0,3,2m in
2
2
2
2 daida
xab T
iT
i
T
ii?
3,1
2
1
2
1
23
233
t
da
xab
T
T
所以,,1,0,222322 Tdxx
,3,1323II
求解, dgGdddq TT
32
1m in
0
0.
2,2
2
2
2
1
21
1
dd
dts
ddd
T
即：
0
0
2
2
0011
0001
1020
1102
3
1
2
1
d
d
得, TTT xd 1,02,00,0
433
因,03
所以,1,04* Txx 相应,2,0,0* T
作 业
(1)用有效集方法求解：
0
0
623.
102m in
2
1
21
21
2
221
2
1
x
x
xxts
xxxxxxxf
取初始可行点,
2
5,0
1
T
x?
