第七章约束最优化方法
§ 7.2 罚函数法基本思想设法将约束问题求解转化为无约束问题求解．
具体说,根据约束的特点，构造某种惩罚函数，
然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解．
惩罚策略,企图违反约束的迭代点给予很大的目标函数值,迫使一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直到收敛到极小点．
外罚函数法引例,求解等式约束问题,
222121,m in xxxxf
02,21 xxts
解,图解法求出最优解,1,1* Tx?
构造：
2
2,
21
21
2
2
2
1
21 xx
xxxxxxF
但是21,xxF 性态极坏,无法用有效的无约束优化算法求解．
设想构造, 2
21222 2; 1 xxxxxP
其中? 是很大的正数．
求解此无约束问题得,
12
2
21
xx
当 时,有：
TTT xxxx 1,1,,*2*121
等式约束问题
1m in nRxxf?
lEixcst i?,2,10,
构造,xPxfxP ~,
其中 0 为参数，称为罚因子．
分析, 1~
1
l
i
i xcxP
当 x 不是可行解时,,0~,0 xPxc i? 越大，
惩罚越重,因此当? 充分大时,xP~ 应充分小．
即,xP 的极小点应充分逼近可行域,进而逼近 (1)的最优解．
不等式约束问题
2m in nRxxf?
mIixcst i?,2,10,
构造,xPxfxP ~,
分析, 1,0m in~
1
m
i
i xcxP
当 x 不是可行解时,,0~,0 xPxc i? 越大，
惩罚越重,因此当? 充分大时,xP~ 应充分小．
即,xP 的极小点应充分逼近可行域,进而逼近 (2)的最优解．
一般约束问题
3m in nRxxf?
lEixcst i?,2,10,
mlIixc i,,10
构造,4~,xPxfxP
1,1,0m in~
11
m
lj
j
l
i
i xcxcxP
其中：
注,一般取,2
例 1,用外罚函数法求解：
01.
m in
1
2
2
2
1
xts
xxxf
解, 212221 1,0m in, xxxxP
即,
011
01,
1
2
1
2
2
2
1
1
2
2
2
1
xxxx
xxxxP
因此：
1122
12
111
11
1 xxx
xx
x
P
2
2
2 xxP
令,0
21
xPxP
得, 0
1 21
xx
最优值,
11
1
1
,
22
xP
当 时：
0,1 21 xx
1,,** xfxPxx
注,(1)x 往往不满足约束条件,x 都是从可行域外部趋向于 *x 的,因此叫外罚函数法．
(2)通过求解一系列无约束最优化问题来求解约束最优化问题的方法,又称为序列无约束极小化技术 SUMT.外罚函数法,又称 SUMT外点法．
外罚函数法算法
Step1,给出 nRx?
0 (可是不可行点 ),4100
罚因子,111 放大系数,10?CC,1?k
Step2,以
1?kx
为初始点求无约束问题：
xPxfxP kk ~,m in得.kk xx
Step3,若,~kk xP 则,*
kxx?
停； 否则转 step4
Step4,令,1 kk C,1 kk 转 step2.
例 2,用 SUMT外点法求解：
0.
22m in
2
2
1
2
12
4
1
xxts
xxxxf
取 05.0,10,1.0,1,2 10 Cx T
求解 222121241 22m in xxxxx k
迭代过程见下表：
１ 0.1 (1.4539,0.7608) 0.0935 0.1831
２ 1 (1.1687,0.7407) 0.5753 0.3908
３ 10 (0.9906,0.8425) 0.5203 0.1926
４ 100 (0.9507,0.8875) 1.9405 0.0267
k k? Tkx 1?
1?kf1~?kk xP?
收敛性分析引理 1,对于由 SUMT外点法产生的点列,1,?kx
k总有：
kkkk xPxP,,11
1~~ kk xPxP
kk xfxf 1
收敛性分析定理 1,设约束问题 (3)和无约束问题 (4)的整体最优解为 *x 和,1 kx
k
对正数序列,,
1 kkk
且,
k?
则由 SUMT外点法产生的点列
kx
的任何聚点 x~ 必是 (3)的整体最优解．
证,不妨设,~xx
k?
因为 *x 和 kx 分别为 (3)和 (4)的整体最优解，
且,0~ *?xP 所以有：
kkkkkk xPxPxfxPxfxf,~~ ***
kkxP?,? 为单调有界序列,设其极限为,0p
*,xfxPxf kkk
kxf? 亦为单调有界序列,设其极限为,0f
00,lim~lim fpxfxPxP kkkkkkk
k 0~lim
kk xP
xx k ~ 且xP~ 连续； 0~~ xP 即 x~ 为可行解
*x? 为最优解；xfxf ~*
xfxx k,~ 连续；*lim~ xfxfxf kk
xfxf ~* 即 x~ 为 (3)的整体最优解．
外罚函数法评价
(1) 如果有了求解无约束问题的好算法，利用外罚函数法求解约束问题很方便．
(2)每个近似解
kx?
往往不是可行解，这是某些实际问题所无法接受的,内罚函数法可以解决．
(3)由收敛性定理
k?
取越大越好,而
k?
越大将造成增广目标函数,xP 的 Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解．乘子法可解决这个问题．
内罚函数法惩罚策略,在可行域的边界上筑起一道很高的
“围墙,,当迭代点靠近边界时，目标函数值陡然增大，以示惩罚，阻止迭代点穿越边界，
这样就可以把最优解,挡,在可行域内了．
注,惩罚策略只适合于不等式约束问题，
并且要求可行域的内点集非空．
不等式约束问题
2m in nRxxf?
mIixcst i?,2,10,
构造,xBrxfrxB ~,
其中,
m
i i xc
xB
1
1~ 或
m
i
i xcxB
1
ln~
分析,x 为可行域的内点时,xB~ 为有限正数，
几乎不受惩罚； x 接近边界时,xB~ 趋于无穷大，
施以很重的惩罚； 迫使极小点落在可行域内，
最终逼近极小点．
例 3,用内罚函数法求解,
0
01.
1
3
1
m in
2
1
2
3
1
x
xts
xxxf
解,
21
2
3
1
1
1
11
3
1,
xx
rxxrxB
令,
011 21
2
1
1
x
rx
x
B
01 2
22
xrxB
所以
r
rrx 1
当 0?r 时,
3
80,1 ** fx T
注,一般rxB,最优解很难用解析法求出，
需采用序列无约束最优化方法．
内罚函数法算法
Step1,给出 nRx?
0 (要求是可行点 ),4100
罚因子,1011?rr 缩小系数,1.0?CC,1?k
Step2,以
1?kx
为初始点求无约束问题：
xBrxfrxB kk ~,m in得.kk rxx?
Step3,若,~kk xBr 则,*
kxx?
停； 否则转 step4
Step4,令,
1 kk Crr,1 kk 转 step2.
例 4,用 SUMT内点法求解,
0
01.
1
3
1
m in
2
1
2
3
1
x
xts
xxxf
取 1.0,1.0,10,4,3 10crx T
迭代结果见下表：
１ 10 (2.0402,3.1623) 12.5290 12.7755
２ 1 (1.1473,0.3162) 3.6165 0.9951
３ 0.1 (1.0488,0.1000) 2.9667 0.3049
４ 0.01 (1.0157,0.0316) 2.7616 0.0953
５ 0.001 (1.0016,0.0316) 2.7046 0.0941
k kr Tkx 1?
1?kf1~?kk xBr
收敛性分析引理 2,对于由 SUMT内点法产生的点列,1,?kx
k
总有,
kkkk rxBrxB,,11
定理 2,设可行域 D 的内点集IixcRxD in,00
非空,xf 在 D 上存在极小点,*x 对严格单减正数列
kkk rrr1,且,0?kr 则由 SUMT外点法产生的点列
kx 的任何聚点 x~ 是约束问题 (2)的最优解．
证,由于,,*0 kk xfxfDDx
*,xfxfrxB kkk
由引理 2知
kk rxB,
单调减少且下有界，
于是它有极限，记作,~B 即：
,~,lim *xfBrxB kkk
若能证明,,~ *xfB? 则可得,*lim xfxf
kk
再由 f 的连续性，可得：
*lim~ xfxfxf kk
即 x~ 是 (2)的最优解．
再证,*,lim xfrxB
kkk
由xf 的连续性知,对于任意小的正数,k 存在
,0 取满足 *xx 的,0Dx? 使得：
2/* xfxf
由 0lim?
kk r
知,对于同一个,? 存在 K 当 Kk? 时
2/~xBrk
又因为xBrxfrxBrxB
kkkk
~,,
2/2/
~,** xBrxfxfxfrxB
kkk
乘子法引例,求解等式约束问题,
2222121 3,m in xxxxxf
0,2?xts
解,最优解,0,0* Tx?
分析, 2
2221222221 33,xxxxxxxxL
对于任何,,xL 关于 x 的极小点是不存在的．
正因为如此，才引进外罚函数法的．
问题,能否找到某个,*? 使 *x 恰好是*,?xP
的无约束极小呢？回答是否定的．
设想,能否在不改变最优解的前提下,以某个在最优解 *x 处梯度为零的函数来取代xf 呢？
启发,xPxL ~, (增广 Lagrange函数 )
通过求解增广 Lagrange函数的序列无约束问题来获得原约束问题的解．
等式约束问题的乘子法
1m in nRxxf?
0,?xCst
其中,,,,
21 Tl xcxcxcxCxf 和xci
二阶连续可微．?li?,2,1?
设 lR 为 Lagrange乘子向量,则对应 Lagrange
函数为,xCxfxL T,
设 *x 是,xL 的极小点,*? 是相应的乘子向量,
(1)可等价为,
0.
,m in *
xCts
xL?
启发,采用外罚函数法．
52,,,xCxCxLxM T构造：
我们将证明,? 适当大时,*x 是,,*xM 极小点．
但 *? 是未知的,在求 *x 的同时,采用迭代法求出
,*? 这是乘子法的基本思想．
定理３,设 *x 与 *? 满足 *x 为问题 (1)的严格局部极小点的二阶充分条件,则存在,0* 使对所有
,* *x 为,,*xM 的严格局部极小点；
反之,若 00?xC 且 0x 对某个 0? 是无约束问题
(5)的局部极小点,则 0x 是约束问题 (1)的局部极小点,
算法构造采用迭代法求点列,
k?
使,*k
设已有
k?
和,kx 则由一阶最优性条件有：
0,, kkkkkkx xCxCxfxM
要求 *xxk? 和 *k 且,0***xCxf
采用,
kkk xC 1
或, ljxc
kjjkjk,,2,11
例 5,用乘子法求解：
02.
m in
21
2
2
2
1
xxts
xxxf
解：
221212221 222,, xxxxxxxM
增广 Lagrange函数为：
令：
022 211
1
xxxxM
022 212
2
xxxxM
得：
22
2
21?
xx
所以,乘子迭代公式为：
2211 xxkk
即：
1
2
1
1
1
kk
取,10
所以：
11
20
11
1
1 kk
设,*
k
对上式取极限有：
11
20
11
1 **
得,2*
得,Tx 1,1*?
等式约束的乘子法 (PH算法 )
Step1,给出
110,,x
Step2,以
1?kx
为初始点求无约束问题：
xCxCxCxfxM TkTkkk 2,,m in得,kx
Step3,若,kxC 则,*
kxx?
停； 否则转 step4
Step4,当及放大系数,0,1C
,1,1,0 k?
,/ 1kk xCxC 转 step5;
否则令,
1 kk C
转 step5;
Step5,令,1,
1 kkxC kkkk
转 step2;
作 业
(1)用外罚函数法求解：
01.
1m in
2
2
2
2
1
xts
xxxf
(2)用内罚函数法求解：
0.
1m in 2
xts
xxf
§ 7.4 SQP方法基本思想无约束变尺度法是在牛顿法的基础上发展而来的，而牛顿法可以看作是求梯度零点（最优性条件）
的一种方法．
对于约束最优化问题，我们同样希望用牛顿法来求解 K-T点，并在此基础上发展形成了约束变尺度法．
SQP算法与有关算法相比具有许多显著的优点，
目前认为该方法是求解中小规模约束问题的十分有效的方法．
等式约束问题
1m in nRxxf?
mEixcst i?,2,10,
其 Lagrange函数为,xcxfxL T,
一阶最优性条件为, 0,xL
或者为,
xcxL
xAxgxL Tx
,
0,
其中xA 表示约束的 Jacobi矩阵：
xcxcxcxA mT,,21
上述方程组是含有 nm? 个方程和 nm? 个未知量的非线性方程组,用牛顿法解这个方程组可得：
k
k
k
k
k
k
d
dxxx
1
1
其中 kdx 和 kd? 是下面牛顿方程组的解：
kkkk xL
d
dxxL?
,,2
把这个方程组展开得：
k
kkx
k
T
kkkxx
xc
xL
d
dx
xA
xAxL?
,
0
,
考虑到 kkk d 1 以及
kTkkkkx xAxgxL,
可以将方程组改写成：
k
k
k
T
kkkxx
xc
xgdx
xA
xAxL
0
,
所得解为 kdx 和,1?k?
而以上方程组恰好是下面二次规划问题
dxxLdxxgdxdxq kkxxTkT?,21m in 2
0, kk xcdxxAst
的一阶必要条件,1?k? 是其最优 Lagrange乘子．
注,(1)SQP方法就是通过求解一系列二次规划问题产生收敛于问题最优解和 Lagrange乘子的迭代序列kx 和.k?
(2)二次规划问题中，约束是原问题约束的线性近似，但目标函数却不是原问题中目标函数的二次近似,这个函数的 Hesse阵为
,,2 kkxx xL 它不仅包含目标函数的二阶导数信息，而且还包含了所有约束函数的二阶导数信息．
一般约束最优化问题
2m in nRxxf?
Iixc
Eixcst
i
i
0
0.
每次迭代所要求解的二次规划子问题为,
Iixcdxc
Eixcdxcts
dxLdxgddq
ki
T
ki
ki
T
ki
kkxx
T
k
T
0
0.
3,
2
1
m in
2
注,(1)以上方法实质上是求等式约束问题的
Lagrange函数的平稳点,被称为拉格朗日－牛顿法,它最早是由 Wilson(1963)提出的．
(2)以上方法虽然收敛速度可达二阶,但是仅仅是局部收敛的,对初始点的选取要求较高,为了保证全局收敛性,必须定义某一衡量 kx 和 k? 的好坏,在原问题最优解处达到极小的效益函数,
然后针对效益函数沿由 (3)确定的方向进行线性搜索。
(3)Lagrange-Newton法最主要的缺点是要求计算
Lagrange函数的 Hesse阵,使其因为计算量太大而失去应用价值。 为了克服计算 Hesse阵的缺点，
借鉴无约束最优化中的拟牛顿法,在每次迭代中用一正定阵 kB 近似 Hesse阵,而随着迭代的进行将用拟牛顿公式对 kB 进行修正。 因此，人们常称这类算法为约束变尺度法。
(4)Lagrange-Newton法最重要的理论贡献是：
由它我们得知可通过逐步求解 (3)的二次规划子问题来求解一般的非线性约束问题。
SQP方法的一般迭代格式
Step1,给定,
0x
正定阵,
1 nnRB
令,1?k
Step2,求解二次规划子问题:,
kk BxQ
Iixcdxc
Eixcdxcts
dBdgddq
ki
T
ki
ki
T
ki
k
T
k
T
0
0.
4
2
1
m in
得解
kd
及其对应的乘子,
1?k?
Step3,针对所选的效益函数从点
kx
沿方向
kd
进行线搜索确定步长,
k?
并令,
1 kkkk dxx
Step4,利用
1?k?
等信息,采用某种拟牛顿公式对
kB
进行修正,得到,
1?kB
令,1 kk 转 Step2
注,上述算法中,当 IE 时，
即为无约束变尺度法的格式．
效益函数
Han(韩世平 )1977年提出用如下的 1l 精确罚函数作效益函数：
Ii
ii
Ei
ii xcxcxfxW,0m a x,
注,在线搜索中,使 W 下降,相当于兼顾了xf
的下降和违反约束的程度的降低．
两者的轻重以系数
i?
加以调节．
系数的调节
Powell(1977)对 i? 的自动调节公式如下：
设 k? 为二次规划 (4)的最优乘子向量，则：
2
2
1
,m a x
51
1 k
k
k
i
k
i
k
i
k
i
k
i
理论上可以证明,这样选取 i? 值,使 kd 为
,xW 的下降方向．
矩阵的修正令,
m
i
ii xcxfxL
1
,
其中
i?
为二次规划 (4)的最优乘子,记：
xxs
,,xLsxLy xx
其中?x 表示,
1?kx x
表示,
kx
为保持?B 的正定性,要求,0?sy T
现在线搜索是对,xW 进行,而不是对,xL
做的,因此未必有,0?sy T
Powell提出了下面的改进：
61,01 Bsyz
其中：
7
2.0
8.0
2.01
Bsssy
syBss
Bss
Bsssy
TT
TT
T
TT
B 的修正公式为：
8szzzBss BB s sBB T TT T
其中?B 表示,
1?kB B 表示,kB
约束变尺度法 (WHP法 )
Step1,给定,
0x
正定阵,
0B
给定,0 令,0?k
Step2,求解二次规划 (4),得
kd
及,
k?
转 Step3.
Step3,按 (5)求,
k?
并代入效益函数,作线搜索得,
k?
令,
1 kkkk dxx
Step4,计算,
1 kkk xxs
当
ks
时,则
1?kx
为近似最优解,停； 否则计算,,,
1 kkxkkxk xLxLy
按 (6),(7)求,
kz
代入 (8)得,
1?kB
令,1 kk 转
Step2.
信赖域 SQP算法基本思想对 SQP算法的一般格式：
在 Step2中,代替求解,,
kk BxQ
我们求解加上信赖域约束 kd 后的另一不再是二次规划的子问题来确定,
kd
然后用适当的方法估计
k?
（若所选效益函数需要这种信息的话）．
在 Step3中,代替沿
kd
对所选效益函数进行线搜索,我们采用信赖域方法处理．
注,(1)如果将信赖域约束
kd
直接加到二次规划问题kk BxQ,的约束中去,则所得问题可能因不可行而无解．
(2)这类子问题的缺点是它不再是一个二次规化问题,从而必须设计一特定的算法来解它．
下面介绍一种可用于一般约束问题,通过求解类似于无约束优化问题中简单信赖域子问题来确定 kd 的方法．
§ 7.2 罚函数法基本思想设法将约束问题求解转化为无约束问题求解．
具体说,根据约束的特点，构造某种惩罚函数，
然后把它加到目标函数中去，将约束问题的求解化为一系列无约束问题的求解．
惩罚策略,企图违反约束的迭代点给予很大的目标函数值,迫使一系列无约束问题的极小点或者无限地靠近可行域，或者一直保持在可行域内移动，直到收敛到极小点．
外罚函数法引例,求解等式约束问题,
222121,m in xxxxf
02,21 xxts
解,图解法求出最优解,1,1* Tx?
构造：
2
2,
21
21
2
2
2
1
21 xx
xxxxxxF
但是21,xxF 性态极坏,无法用有效的无约束优化算法求解．
设想构造, 2
21222 2; 1 xxxxxP
其中? 是很大的正数．
求解此无约束问题得,
12
2
21
xx
当 时,有：
TTT xxxx 1,1,,*2*121
等式约束问题
1m in nRxxf?
lEixcst i?,2,10,
构造,xPxfxP ~,
其中 0 为参数，称为罚因子．
分析, 1~
1
l
i
i xcxP
当 x 不是可行解时,,0~,0 xPxc i? 越大，
惩罚越重,因此当? 充分大时,xP~ 应充分小．
即,xP 的极小点应充分逼近可行域,进而逼近 (1)的最优解．
不等式约束问题
2m in nRxxf?
mIixcst i?,2,10,
构造,xPxfxP ~,
分析, 1,0m in~
1
m
i
i xcxP
当 x 不是可行解时,,0~,0 xPxc i? 越大，
惩罚越重,因此当? 充分大时,xP~ 应充分小．
即,xP 的极小点应充分逼近可行域,进而逼近 (2)的最优解．
一般约束问题
3m in nRxxf?
lEixcst i?,2,10,
mlIixc i,,10
构造,4~,xPxfxP
1,1,0m in~
11
m
lj
j
l
i
i xcxcxP
其中：
注,一般取,2
例 1,用外罚函数法求解：
01.
m in
1
2
2
2
1
xts
xxxf
解, 212221 1,0m in, xxxxP
即,
011
01,
1
2
1
2
2
2
1
1
2
2
2
1
xxxx
xxxxP
因此：
1122
12
111
11
1 xxx
xx
x
P
2
2
2 xxP
令,0
21
xPxP
得, 0
1 21
xx
最优值,
11
1
1
,
22
xP
当 时：
0,1 21 xx
1,,** xfxPxx
注,(1)x 往往不满足约束条件,x 都是从可行域外部趋向于 *x 的,因此叫外罚函数法．
(2)通过求解一系列无约束最优化问题来求解约束最优化问题的方法,又称为序列无约束极小化技术 SUMT.外罚函数法,又称 SUMT外点法．
外罚函数法算法
Step1,给出 nRx?
0 (可是不可行点 ),4100
罚因子,111 放大系数,10?CC,1?k
Step2,以
1?kx
为初始点求无约束问题：
xPxfxP kk ~,m in得.kk xx
Step3,若,~kk xP 则,*
kxx?
停； 否则转 step4
Step4,令,1 kk C,1 kk 转 step2.
例 2,用 SUMT外点法求解：
0.
22m in
2
2
1
2
12
4
1
xxts
xxxxf
取 05.0,10,1.0,1,2 10 Cx T
求解 222121241 22m in xxxxx k
迭代过程见下表：
１ 0.1 (1.4539,0.7608) 0.0935 0.1831
２ 1 (1.1687,0.7407) 0.5753 0.3908
３ 10 (0.9906,0.8425) 0.5203 0.1926
４ 100 (0.9507,0.8875) 1.9405 0.0267
k k? Tkx 1?
1?kf1~?kk xP?
收敛性分析引理 1,对于由 SUMT外点法产生的点列,1,?kx
k总有：
kkkk xPxP,,11
1~~ kk xPxP
kk xfxf 1
收敛性分析定理 1,设约束问题 (3)和无约束问题 (4)的整体最优解为 *x 和,1 kx
k
对正数序列,,
1 kkk
且,
k?
则由 SUMT外点法产生的点列
kx
的任何聚点 x~ 必是 (3)的整体最优解．
证,不妨设,~xx
k?
因为 *x 和 kx 分别为 (3)和 (4)的整体最优解，
且,0~ *?xP 所以有：
kkkkkk xPxPxfxPxfxf,~~ ***
kkxP?,? 为单调有界序列,设其极限为,0p
*,xfxPxf kkk
kxf? 亦为单调有界序列,设其极限为,0f
00,lim~lim fpxfxPxP kkkkkkk
k 0~lim
kk xP
xx k ~ 且xP~ 连续； 0~~ xP 即 x~ 为可行解
*x? 为最优解；xfxf ~*
xfxx k,~ 连续；*lim~ xfxfxf kk
xfxf ~* 即 x~ 为 (3)的整体最优解．
外罚函数法评价
(1) 如果有了求解无约束问题的好算法，利用外罚函数法求解约束问题很方便．
(2)每个近似解
kx?
往往不是可行解，这是某些实际问题所无法接受的,内罚函数法可以解决．
(3)由收敛性定理
k?
取越大越好,而
k?
越大将造成增广目标函数,xP 的 Hesse阵条件数越大，趋于病态，给无约束问题求解增加很大困难，甚至无法求解．乘子法可解决这个问题．
内罚函数法惩罚策略,在可行域的边界上筑起一道很高的
“围墙,,当迭代点靠近边界时，目标函数值陡然增大，以示惩罚，阻止迭代点穿越边界，
这样就可以把最优解,挡,在可行域内了．
注,惩罚策略只适合于不等式约束问题，
并且要求可行域的内点集非空．
不等式约束问题
2m in nRxxf?
mIixcst i?,2,10,
构造,xBrxfrxB ~,
其中,
m
i i xc
xB
1
1~ 或
m
i
i xcxB
1
ln~
分析,x 为可行域的内点时,xB~ 为有限正数，
几乎不受惩罚； x 接近边界时,xB~ 趋于无穷大，
施以很重的惩罚； 迫使极小点落在可行域内，
最终逼近极小点．
例 3,用内罚函数法求解,
0
01.
1
3
1
m in
2
1
2
3
1
x
xts
xxxf
解,
21
2
3
1
1
1
11
3
1,
xx
rxxrxB
令,
011 21
2
1
1
x
rx
x
B
01 2
22
xrxB
所以
r
rrx 1
当 0?r 时,
3
80,1 ** fx T
注,一般rxB,最优解很难用解析法求出，
需采用序列无约束最优化方法．
内罚函数法算法
Step1,给出 nRx?
0 (要求是可行点 ),4100
罚因子,1011?rr 缩小系数,1.0?CC,1?k
Step2,以
1?kx
为初始点求无约束问题：
xBrxfrxB kk ~,m in得.kk rxx?
Step3,若,~kk xBr 则,*
kxx?
停； 否则转 step4
Step4,令,
1 kk Crr,1 kk 转 step2.
例 4,用 SUMT内点法求解,
0
01.
1
3
1
m in
2
1
2
3
1
x
xts
xxxf
取 1.0,1.0,10,4,3 10crx T
迭代结果见下表：
１ 10 (2.0402,3.1623) 12.5290 12.7755
２ 1 (1.1473,0.3162) 3.6165 0.9951
３ 0.1 (1.0488,0.1000) 2.9667 0.3049
４ 0.01 (1.0157,0.0316) 2.7616 0.0953
５ 0.001 (1.0016,0.0316) 2.7046 0.0941
k kr Tkx 1?
1?kf1~?kk xBr
收敛性分析引理 2,对于由 SUMT内点法产生的点列,1,?kx
k
总有,
kkkk rxBrxB,,11
定理 2,设可行域 D 的内点集IixcRxD in,00
非空,xf 在 D 上存在极小点,*x 对严格单减正数列
kkk rrr1,且,0?kr 则由 SUMT外点法产生的点列
kx 的任何聚点 x~ 是约束问题 (2)的最优解．
证,由于,,*0 kk xfxfDDx
*,xfxfrxB kkk
由引理 2知
kk rxB,
单调减少且下有界，
于是它有极限，记作,~B 即：
,~,lim *xfBrxB kkk
若能证明,,~ *xfB? 则可得,*lim xfxf
kk
再由 f 的连续性，可得：
*lim~ xfxfxf kk
即 x~ 是 (2)的最优解．
再证,*,lim xfrxB
kkk
由xf 的连续性知,对于任意小的正数,k 存在
,0 取满足 *xx 的,0Dx? 使得：
2/* xfxf
由 0lim?
kk r
知,对于同一个,? 存在 K 当 Kk? 时
2/~xBrk
又因为xBrxfrxBrxB
kkkk
~,,
2/2/
~,** xBrxfxfxfrxB
kkk
乘子法引例,求解等式约束问题,
2222121 3,m in xxxxxf
0,2?xts
解,最优解,0,0* Tx?
分析, 2
2221222221 33,xxxxxxxxL
对于任何,,xL 关于 x 的极小点是不存在的．
正因为如此，才引进外罚函数法的．
问题,能否找到某个,*? 使 *x 恰好是*,?xP
的无约束极小呢？回答是否定的．
设想,能否在不改变最优解的前提下,以某个在最优解 *x 处梯度为零的函数来取代xf 呢？
启发,xPxL ~, (增广 Lagrange函数 )
通过求解增广 Lagrange函数的序列无约束问题来获得原约束问题的解．
等式约束问题的乘子法
1m in nRxxf?
0,?xCst
其中,,,,
21 Tl xcxcxcxCxf 和xci
二阶连续可微．?li?,2,1?
设 lR 为 Lagrange乘子向量,则对应 Lagrange
函数为,xCxfxL T,
设 *x 是,xL 的极小点,*? 是相应的乘子向量,
(1)可等价为,
0.
,m in *
xCts
xL?
启发,采用外罚函数法．
52,,,xCxCxLxM T构造：
我们将证明,? 适当大时,*x 是,,*xM 极小点．
但 *? 是未知的,在求 *x 的同时,采用迭代法求出
,*? 这是乘子法的基本思想．
定理３,设 *x 与 *? 满足 *x 为问题 (1)的严格局部极小点的二阶充分条件,则存在,0* 使对所有
,* *x 为,,*xM 的严格局部极小点；
反之,若 00?xC 且 0x 对某个 0? 是无约束问题
(5)的局部极小点,则 0x 是约束问题 (1)的局部极小点,
算法构造采用迭代法求点列,
k?
使,*k
设已有
k?
和,kx 则由一阶最优性条件有：
0,, kkkkkkx xCxCxfxM
要求 *xxk? 和 *k 且,0***xCxf
采用,
kkk xC 1
或, ljxc
kjjkjk,,2,11
例 5,用乘子法求解：
02.
m in
21
2
2
2
1
xxts
xxxf
解：
221212221 222,, xxxxxxxM
增广 Lagrange函数为：
令：
022 211
1
xxxxM
022 212
2
xxxxM
得：
22
2
21?
xx
所以,乘子迭代公式为：
2211 xxkk
即：
1
2
1
1
1
kk
取,10
所以：
11
20
11
1
1 kk
设,*
k
对上式取极限有：
11
20
11
1 **
得,2*
得,Tx 1,1*?
等式约束的乘子法 (PH算法 )
Step1,给出
110,,x
Step2,以
1?kx
为初始点求无约束问题：
xCxCxCxfxM TkTkkk 2,,m in得,kx
Step3,若,kxC 则,*
kxx?
停； 否则转 step4
Step4,当及放大系数,0,1C
,1,1,0 k?
,/ 1kk xCxC 转 step5;
否则令,
1 kk C
转 step5;
Step5,令,1,
1 kkxC kkkk
转 step2;
作 业
(1)用外罚函数法求解：
01.
1m in
2
2
2
2
1
xts
xxxf
(2)用内罚函数法求解：
0.
1m in 2
xts
xxf
§ 7.4 SQP方法基本思想无约束变尺度法是在牛顿法的基础上发展而来的，而牛顿法可以看作是求梯度零点（最优性条件）
的一种方法．
对于约束最优化问题，我们同样希望用牛顿法来求解 K-T点，并在此基础上发展形成了约束变尺度法．
SQP算法与有关算法相比具有许多显著的优点，
目前认为该方法是求解中小规模约束问题的十分有效的方法．
等式约束问题
1m in nRxxf?
mEixcst i?,2,10,
其 Lagrange函数为,xcxfxL T,
一阶最优性条件为, 0,xL
或者为,
xcxL
xAxgxL Tx
,
0,
其中xA 表示约束的 Jacobi矩阵：
xcxcxcxA mT,,21
上述方程组是含有 nm? 个方程和 nm? 个未知量的非线性方程组,用牛顿法解这个方程组可得：
k
k
k
k
k
k
d
dxxx
1
1
其中 kdx 和 kd? 是下面牛顿方程组的解：
kkkk xL
d
dxxL?
,,2
把这个方程组展开得：
k
kkx
k
T
kkkxx
xc
xL
d
dx
xA
xAxL?
,
0
,
考虑到 kkk d 1 以及
kTkkkkx xAxgxL,
可以将方程组改写成：
k
k
k
T
kkkxx
xc
xgdx
xA
xAxL
0
,
所得解为 kdx 和,1?k?
而以上方程组恰好是下面二次规划问题
dxxLdxxgdxdxq kkxxTkT?,21m in 2
0, kk xcdxxAst
的一阶必要条件,1?k? 是其最优 Lagrange乘子．
注,(1)SQP方法就是通过求解一系列二次规划问题产生收敛于问题最优解和 Lagrange乘子的迭代序列kx 和.k?
(2)二次规划问题中，约束是原问题约束的线性近似，但目标函数却不是原问题中目标函数的二次近似,这个函数的 Hesse阵为
,,2 kkxx xL 它不仅包含目标函数的二阶导数信息，而且还包含了所有约束函数的二阶导数信息．
一般约束最优化问题
2m in nRxxf?
Iixc
Eixcst
i
i
0
0.
每次迭代所要求解的二次规划子问题为,
Iixcdxc
Eixcdxcts
dxLdxgddq
ki
T
ki
ki
T
ki
kkxx
T
k
T
0
0.
3,
2
1
m in
2
注,(1)以上方法实质上是求等式约束问题的
Lagrange函数的平稳点,被称为拉格朗日－牛顿法,它最早是由 Wilson(1963)提出的．
(2)以上方法虽然收敛速度可达二阶,但是仅仅是局部收敛的,对初始点的选取要求较高,为了保证全局收敛性,必须定义某一衡量 kx 和 k? 的好坏,在原问题最优解处达到极小的效益函数,
然后针对效益函数沿由 (3)确定的方向进行线性搜索。
(3)Lagrange-Newton法最主要的缺点是要求计算
Lagrange函数的 Hesse阵,使其因为计算量太大而失去应用价值。 为了克服计算 Hesse阵的缺点，
借鉴无约束最优化中的拟牛顿法,在每次迭代中用一正定阵 kB 近似 Hesse阵,而随着迭代的进行将用拟牛顿公式对 kB 进行修正。 因此，人们常称这类算法为约束变尺度法。
(4)Lagrange-Newton法最重要的理论贡献是：
由它我们得知可通过逐步求解 (3)的二次规划子问题来求解一般的非线性约束问题。
SQP方法的一般迭代格式
Step1,给定,
0x
正定阵,
1 nnRB
令,1?k
Step2,求解二次规划子问题:,
kk BxQ
Iixcdxc
Eixcdxcts
dBdgddq
ki
T
ki
ki
T
ki
k
T
k
T
0
0.
4
2
1
m in
得解
kd
及其对应的乘子,
1?k?
Step3,针对所选的效益函数从点
kx
沿方向
kd
进行线搜索确定步长,
k?
并令,
1 kkkk dxx
Step4,利用
1?k?
等信息,采用某种拟牛顿公式对
kB
进行修正,得到,
1?kB
令,1 kk 转 Step2
注,上述算法中,当 IE 时，
即为无约束变尺度法的格式．
效益函数
Han(韩世平 )1977年提出用如下的 1l 精确罚函数作效益函数：
Ii
ii
Ei
ii xcxcxfxW,0m a x,
注,在线搜索中,使 W 下降,相当于兼顾了xf
的下降和违反约束的程度的降低．
两者的轻重以系数
i?
加以调节．
系数的调节
Powell(1977)对 i? 的自动调节公式如下：
设 k? 为二次规划 (4)的最优乘子向量，则：
2
2
1
,m a x
51
1 k
k
k
i
k
i
k
i
k
i
k
i
理论上可以证明,这样选取 i? 值,使 kd 为
,xW 的下降方向．
矩阵的修正令,
m
i
ii xcxfxL
1
,
其中
i?
为二次规划 (4)的最优乘子,记：
xxs
,,xLsxLy xx
其中?x 表示,
1?kx x
表示,
kx
为保持?B 的正定性,要求,0?sy T
现在线搜索是对,xW 进行,而不是对,xL
做的,因此未必有,0?sy T
Powell提出了下面的改进：
61,01 Bsyz
其中：
7
2.0
8.0
2.01
Bsssy
syBss
Bss
Bsssy
TT
TT
T
TT
B 的修正公式为：
8szzzBss BB s sBB T TT T
其中?B 表示,
1?kB B 表示,kB
约束变尺度法 (WHP法 )
Step1,给定,
0x
正定阵,
0B
给定,0 令,0?k
Step2,求解二次规划 (4),得
kd
及,
k?
转 Step3.
Step3,按 (5)求,
k?
并代入效益函数,作线搜索得,
k?
令,
1 kkkk dxx
Step4,计算,
1 kkk xxs
当
ks
时,则
1?kx
为近似最优解,停； 否则计算,,,
1 kkxkkxk xLxLy
按 (6),(7)求,
kz
代入 (8)得,
1?kB
令,1 kk 转
Step2.
信赖域 SQP算法基本思想对 SQP算法的一般格式：
在 Step2中,代替求解,,
kk BxQ
我们求解加上信赖域约束 kd 后的另一不再是二次规划的子问题来确定,
kd
然后用适当的方法估计
k?
（若所选效益函数需要这种信息的话）．
在 Step3中,代替沿
kd
对所选效益函数进行线搜索,我们采用信赖域方法处理．
注,(1)如果将信赖域约束
kd
直接加到二次规划问题kk BxQ,的约束中去,则所得问题可能因不可行而无解．
(2)这类子问题的缺点是它不再是一个二次规化问题,从而必须设计一特定的算法来解它．
下面介绍一种可用于一般约束问题,通过求解类似于无约束优化问题中简单信赖域子问题来确定 kd 的方法．
