二次规划问题
序列二次规划法
求解一般线性优化问题:
12min (x)
h (x)0,i E {1,...,m }s.t.(x)0,i {1,...,m }
i i f g I =∈=??
≥∈=? (1.1) 基本思想：在每次迭代中通过求解一个二次规划子问题来确定一个下降方向，通过减少价值函数来获取当前迭代点的移动步长，重复这些步骤直到得到原问题的解。
1.1等式约束优化问题的Lagrange-Newton 法
考虑等式约束优化问题
min (x)
s.t.h (x)0,E {1,...,m}
j f j =∈=
(1.2)
其中:,n f R R →:()n i h R R i E →∈都为二阶连续可微的实函数. 记1()((),...,())T m h x h x h x =. 则(1.3)的Lagrange 函数为： 1(,)()*()()*()m
T i i i L x u f x u h x f x u h x ==-=-∑
（1.3）
其中12(,,...,)T m u u u u =为拉格朗日乘子向量。
约束函数()h x 的Jacobi 矩阵为：1()()((),...,())T T m A x h x h x h x =?=??.
对（1.3）求导数，可以得到下列方程组：
(,)()A()*(,)0(,)()T x u L x u f x x u L x u L x u h x ???
???-?===?????-????
（1.4）
现在考虑用牛顿法求解非线性方程（1.4）.
(,)L x u ?的Jacobi 矩阵为：
(,)()(,)()
0T W x u A x N x u A x ??
-= ?-??
（1.5）
其中2
2
1
(,)L(,)()*()m
xx i
i
i W x u x u f x u h x ==?=?-?∑是拉格朗日函数L(,)x u 关于x 的
Hessen 矩阵.
(,)N x u 也称为K-T 矩阵。对于给定的点(,)k k k z x u =，牛顿法的迭代格式为：
1k k k z z z +=+?. 其中k k (d ,v )k z ?=是线性方程组
k k k k (,)()(x )A(x )u *()0(x )k k k k T T k k d W x u A x f A x v h ??-??
-?+??= ? ? ? ?-???
???
（1.6）
的解。
注意：只要k A(x )行满秩且(,)k k W x u 是正定的，那么（1.6）的系数矩阵非奇异，且方程组有唯一解。
引理1：已知矩阵,n n
n m U R
S R ??∈∈，则对任意满足*0T S x =的非零向量x 都有0
T
x Ux >的充要条件是存在常数*0σ>，使得对任意的*
σσ≥都有
*(U *S*S )0,0T T n x x x R σ+>?≠∈.
证明略。
鉴于方程组（1.6）的求解数值不稳定，故考虑将它转化成一个严格凸二次规划问题.转化的条件是(1.4)的解点*x 处的最优性二阶充分条件成立，即对满足*()*0T
A x d =的任一向量0d ≠，成立*
*
*(,)*0T
d W x u d >。 再由引理1知：当0τ>充分小时，1
(*,*)(*)(*)2T W x u A x A x τ
+
正定。 考虑（1.6）中的(,)k k W x u 用一个正定矩阵来代替，记
1
(,)(,)()()2k T k k k k k B x u W x u A x A x τ
=+
则当**
(,)(,)k k x u x u →时，矩阵**
B(,)x u 正定。
（1.6）的第一个展开式为
k (,)*d (x )*(x )(x )*T T k k k k k k k W x u A v f A u -=-?+
将上式变形为：
k 11
[(,)()()]*d (x )*[()](x )22k k T T k k k k k k k k W x u A x A x A v u A x d f ττ
+
-++=-? 令~
1:()2k T
k k k k u v u A x d τ
=++后得：~k (,)*d (x )*(x )T k k k k k B x u A u f -=-?. 因此，（1.6）等价于
k ~k (x )(,)()*()0(x )k k k k T k k d f B x u A x A x h u ?????-??
?=- ? ? ? ???????
（1.7）
进一步，可以把方程（1.7）转换成如下严格凸二次规划：
k k k k k 1min (d)(x ,u )d f(x )2
..(x )A(x )d 0
T
T k q d B d
s t h =
+?+=
（1.8）
方程（1.7）和（1.8）具有同解的。
1.2一般形式的约束优化问题
将1.1节中构造二次规划子问题求解等式约束优化问题的思想推广到一般形式的约束优化问题(1.5)。在给定点k k (x ,u ,)k k z λ=后，将约束函数线性化，并对拉格朗日函数进行二次多项式近似，得到下列二次规划子问题：
k k k k k k k 1
min (x ,u )d f(x )2
(x )(x )d 0,i E ..(x )(x )d 0,i T T T
i i T
i i d W d
h h s t g g I
+??+?=∈??+?=∈?? （1.9）
其中2
12k k k k k k {1,...,m },I {1,...m },W W(x ,u ,)(x ,u ,)k xx E L λλ====?，拉格朗日函数为
12
1
1
(,)()*()*g ()m m i i i i i i L x u f x u h x x λ===--∑∑.
于是，迭代点k x 的校正步k d 以及新的拉格朗日乘子估计量11,k k u λ++可以分别定义为问题
的一个K-T 点*x 和相应的拉格朗日乘子向量*,*u λ。
定理1：给定约束优化问题（1.1）的最优解*d 和相应的拉格朗日乘子*,*0u λ≥.假定在*x 处，下面的条件成立：
（1） 有效约束的Jacobi 矩阵(x*)S J 行满秩，其中(*)E (*)S x I x =U ;
（2） 严格互补松弛条件成立，即******
(x )0,0,(x )0,(x )0;i i i i i i g g g λλλ≥≥=+>
（3） 二阶最优性充分条件成立，即对满足*()*0T
A x d =的任一向量0d ≠，成立
****(,,)*0T d W x u d λ>.
那么若k k k (x ,u ,)λ充分靠近*
*
*
(x ,u ,)λ，则二次规划问题(1.9)存在一个局部极小点*
d ，使
得其对应的有效约束指标集*
()S d 与原问题在*x 处的有效指标集*
()S x 是相同的。
注意：在构造二次规划子问题时，需要计算拉格朗日函数在迭代点k x 处的Hessen 矩阵，计算量过大。为了克服这个缺陷，韩世平基于牛顿-拉格朗日法提出了一种利用对称正定矩阵k B 来代替拉格朗日矩阵k W 的序列二次规划法。
对于一般约束优化问题（1.1），在迭代点k k k k z (x ,u ,)λ=，构造下列形式的二次规划子问题：
k k k k k k k 1
min (x ,u )d f(x )2
(x )(x )d 0,i E ..(x )(x )d 0,i T T T
i i T
i i d B d
h h s t g g I
+??+?=∈??+?=∈?? （1.10）
并且用（1.10）的解k d 作为原问题变量x 在第k 次迭代过程中的搜索方向。其中k d 有一个好的性质是它许多罚函数（价值函数）的下降方向。例如，对于L1精确罚函数：
1
(x,)f(x)[|h (x)||[g (x)]_|]i i i E
i I
P σσ
∈∈=+
+∑∑
其中0σ>为罚参数，g (x)]_max{0,g (x)}i i =-。
为了保证SQR 方法的全局收敛性，通常借助价值函数来确定搜索步长。用来衡量一维
搜索的好坏。
算法（一般约束优化问题的SQP 方法）
Step 0: 给定初始点12000(,u ,)R R R ,m
m
n x λ∈??对称正定矩阵0n
B R ∈.