第十章罚函数法
罚函数是利用目标函数与约束函数一起构成的具有惩罚性质的函数。当约束条件被破坏时，施以惩罚，可以想象，当这种惩罚很大时，将迫使迭代点趋于可行点。
§101外罚函数法
对一般非线性规划问题：
mi
fx
st
cix0cix0
i1meime1m
定义违反约束度函数：
ci

x

ci

x
i1
me
ci
x

mi
0
ci
x
i

me1
m。
罚函数一般表示为：Pxfxhcx
（101）
（102）（103）（104）
其中hcx是惩罚项，这个函数一般具有
较常用的形式为：
h00，limhc。c
Pxfxcx（0称为罚因子）
（105）
注：1在上式中，范数常取为，若取为或会导致Px不光滑。
2

1
2当取和1时，Px的光滑性可由2cx2mi
0cix2
直接验证。事实上，在“转折点”处，可证得左、右导数均为0，由此可得cx2光滑性，从而
Px光滑。
Coura
t函数是最早使用的罚函数，也是最方便最重要的一种罚函数。其形式为
pxfxcx22
me
m
fxci2xmi
0cix2
i1
me1
（106）
f以下考虑一般的罚函数问题
pxfxcx
（107）
并且以后总用x表示罚问题
的解。
mi
xR

P
x
引理1设210，则必有
fx2fx1
cx2cx1。
注：随着罚因子的增大，惩罚的力度加大，x将越来越靠近可行域（相当于取点范围不断减小），
自然fx会不断增加。
引理2令cx，则x是约束问题
mi
fx
xR
stcx
（108）
的最优解。
证明：用反证法证明。若不然，容易构造出一个关于罚函数问题更好的解，导致矛盾。
由于原问题等价于
mi
fx
xR
stcx0
（109）
而当很小时，（108）是（109）的近似，从而x可看成是原问题的近似解。特别地，当
cx0时，x是原问题的精确解。
罚函数法的基本思想是：每次迭代增大罚因子，直到cx缩小到给定的范围内。由于
要求解一系列无约束问题，故也称为SUMT外点法Seque
tialU
co
strai
edMi
imizatio
Tech
ique。外罚函数算法
1）给出x1R
，10，0，k1。
2）
利用初始值
xk
，求解无约束问题（罚函数问题）
mi
xR

P
k

x
得到
x
k

。
f3）若cxk，停止，得近似解xxk；否则xk1xk；k110k；kk1；转2）
关于此算法有如下收敛性结果：
定理101若算法中允许误差满足mi
cx
xR
则算法必有限终止。
证明：若定理不成立，则必有k，且对一切k都有cxk
（1010）
而由定理条件，存在xR
，使得
cx
（1011r