二次规划.ppt

等式约束的二次规划问题
直接消去法 求解问题(1)最简单又最直接的方法就是利用约束来消去部分变量，从而把问题
转化成无约束问题，这一方法称为直接消去法。
将 A 分解成为如下形式：
A B,N
其中 B 为基矩阵，相应的将 x,c, H 作如下分块：
x

xB xN

,
c

cB cN

,
H

H11 H21
H12
H 22

其中 H11 为 m m 维矩阵。这样，问题(1)的约束条件变为： BxB NxN b
即：
xB B1b B1NxN (2)
等式约束的二次规划问题
将(2)代入 f x中就得到与问题(1)等价的无约束问题：
min
如果 Hˆ 2正定，则问题(3)的最优解为： x*N Hˆ 21cˆN
此时，问题(1)的解为：
x*

xx**NB


B1b

0


B1N

I

Hˆ 21cˆN
记点 x* 处的拉格朗日乘子为 λ* ，则有： AT λ* f x* Hx* c ，故知：
x1 2x2 x3 4 x1 x2 x3 2
通过高斯消元法可得：

x1 x1

2x2 4 x2 2

x3 x3

x1


1 3
x3


x2

2
2 3
x3
代入 f x 中可得到等价的无约束问题：
min


x3


14 9
x32

8 3
min f x 1 xT Hx cT x

2
s.t. Ax = b
(1)
其中 H 为 n 维对称阵，A 为 m n 维矩阵，c 为 n 维列向量，b 为 m 维列向
量。
此处为了方便讨论，不妨假设 rank A m n。
下面介绍求解等式约束下二次规划问题的两种方法。
λ* B1 T H11x*B H12x*N cB
如果 Hˆ 2 半正定且问题(3)无下界，或者 Hˆ 2 有负特征值，则不难证明问题(1)不存在 有限解。
等式约束的二次规划问题
例1
求解二次规划问题 首先将约束写成
min s.t.

f x x12 x22 x32
xN
1 2
xTN
Hˆ 2
xN
cˆTNxN
(3)
Hˆ 2 H22 H21B1N NT B1 T H12 NT B1 T H11B1N
其中： cˆN cN NT
B1 T cB
H21 NT
B1
T
H11
B1b
x3

4
等式约束的二次规划问题
由标准形式可知
Hˆ 2


28 9

，显然为正定，故求其极值只需令其梯度为
0：

x3


28 9
x3

8 3

0
故可求得问题的唯一最优解为：
x*
x1*, x2*, x3*
T


2 7
,
10 7
,

6 7
T

再利用 AT λ* f
G

等式约束的二次规划问题
从而由式(4)可得问题(1)的最优解为：
x* Qc Rb

λ*

RT c

Gb
(5)
Q H1 H1AT AH1AT 1 AH1
当
H 1
存在时，可得
Q,
R,
G
的表达式为：
R G

H1AT AH1AT AH1AT 1
维列向量。
特别的，当 H 正定时，目标函数为凸函数，线性约束下可行域又是凸集，问题
称为凸二次规划。凸二次规划是一种最简单的非线性规划，且具有如下性质：
(1) K-T 条件不仅是最优解的必要条件，而且是充分条件；
(2) 局部最优解就是全局最优解。
等式约束的二次规划问题
等式约束的二次规划问题可以表示为：
第七章 二次规划
二次规划问题的数学模型
二次规划（Quadratic Programming，简称 QP)问题可以表述成如下标准形式：
min f x 1 xT Hx cT x

2
s.t. Ax b
其中 H Rnn 为 n 阶实对称矩阵，A 为 m n 维矩阵，c 为 n 维列向量，b 为 m
0 0
0 , 2
c 0 , 1

b

0
，若写成矩阵形式，有：
H AT x c
A
0

λ



b
(4)
H AT
式中的系数矩阵 A
0
称为拉格朗日矩阵，它是对称的但不一定是正定的。

如果拉格朗日矩阵可逆，则可以表示为：
H
AT
1

Q
R
A
0



R
T
从而引起最优解 x* 的数值不稳定。
等式约束的二次规划问题
拉格朗日乘子法
问题(1)的拉格朗日乘子函数为：
L

x,
λ

1 2xTHxcTx

λT

Ax

b
。令：
λx
L L

x, x,
λ λ


0 0
Hx c AT λ 0
可以得到
K-T
条件：
Ax
x*
1

Hx*

c
，即：

2
1
1 1 1
12**


2 0 0
0 2 0
0
0 2

2 7
10 7

6 7
T
可以求得：
1*

8 7
, 2*


4 7
直接消去法思想简单明了，使用方便．不足之处是 B 可能接近一个奇异方阵，
λ*

RT f
x(0)
等式约束的二次规划问题

例2
用拉格朗日乘子法求解问题：
min s.t.


x12 2x22 x32 2x1x2 x3 x1 x2 x3 4 2x1 x2 x3 2
2 2 0 0
由问题可以知道如下矩阵表述： H 2 4
1

下面给出 x* 和 λ* 的另一种表达式。设 x(0) 是问题(1)的任一可行解，即 x(0) 满足关系式
Ax(0) b ，那么在 x(0) 处目标函数的梯度可以表示为：
f x(0) Hx(0) c
x* x(0) Qf x(0)
则式(5)可以写为：