SQP最优化方法.doc

1

Chapter 11
Sequential quadratic Programming

11.0 正定二次规划的紧约束集法

考虑正定二次规划

min f (x) = 1 xT Gx + rT x
2

s.t.

aT x - bi = 0 i
i ÎU = {1,2,L , m}

aT x - bi £ 0 i
i ÎV = {m +1,L , m + p}

（0.1）

其中G 是 n´ n 对称正定矩阵。

11.0.1 正定二次规划的性质

定理 0.1 若问题（0.1）的可行集 S 非空，则必有唯一的

全局最优解。

[证明] 取 xˆ Î S ，记

S0 = { Î S f (x) £ f (x)}
x ˆ

显然 S0 是闭集，下面证明 S0 是有界集。假若 S0 无界，即

2

有 x(k) Î S0 ,(k = 1,2,L ) ，使得
x(k) ® +¥,(k ® +¥)

记 G 的最小特征值为s1 > 0 ，则

f (x(k) ) = 1 x(k)T Gx(k) + rT x(k)
2

³ 1 x(k) 2 - r x(k) ® +¥,(k ® +¥)
2

此与 f (x(k) ) £ f (x) 矛盾。故 S0 有界。 ˆ

连续函数 f (x) 在有界闭集 S0 上必可取到最小值，即有

x* Î S0 ，使得
f (x) ³ f (x* ), ("x Î S )
0

而 "x Î S \ S0 ，有 f (x) ³ f (x) ³ f (x* ) ，所以 ˆ

f (x) £ f (x* ), ("x Î S )

即 x* 是 f (x) 在 S 是的全局最优解。

最 后 证 明 x* 的 唯 一 性 。 假 若 另 有 x1* Î S ， 使 得

f (x1* ) = f (x* ) .因为 G 正定， f (x) 是严格凸函数，取
( )
x = 1 x1* + x* ，则 x Î S ，且
2
( )
f (x) = f æ 1 x1* + x* ö < 1 f (x1* ) + 1 f (x* ) = f (x* )

èç2
ø÷2
2

3

此与 x* 是 f (x) 在 S 是的全局最优解矛盾。证毕

下面的定理是紧约束集法的理论基础。

定理 0.2 设 x(k) 是问题 0.1）
（ 的可行解， 紧约束集为V (k) 。

求解下述等式约束问题

min f (x) = 1 xT Gx + rT x
2

s.t.

aT x - bi = 0 i
i ÎU = {1,2,L ,m}
（0.2）

aT x - bi = 0 i
i ÎV ( k )

如果问题（0.2）的最优解恰好就是 x(k) ，且相应于V (k) 的

Lagrangian 乘 子 l(i k ) ³ 0, (i Î V (k ) )， 那 么 x(k) 就 是 问 题
（0.1）的最优解。

[证明] 因为 x(k) 是问题（0.2）的最优解，则有 Lagrangian

乘子 l(ik ) ³ 0, (i Î V (k ) )及 l(jk ) ³ 0, ( j Î U )，使得

Gx


(k )
+r+
å

l(k ) a +
å

l(k ) a = 0

iÎ V

(k )
i
i

j ÎU
j
j

同条件还有
l(ik ) ³ 0, (i Î V (k ) )。这正说明 x(k ) 是问题

（0.1）的 KKT 点。由 8.2.3 节的类似推导，可知 x (k ) 就