最优化理论与算法(第十章).doc
14页
第十章 罚函数法罚函数是利用目标函数与约束函数一起构成的具有惩罚性质的函数当约束条件被破坏时，施以惩罚，可以想象，当这种惩罚很大时，将迫使迭代点趋于可行点§10.1 外罚函数法对一般非线性规划问题：定义违反约束度函数：min / ( x )\c (x) = 0 i = 1,…,mS.T < i eI C (X) > 0 i = M ，…，Mi e+1c(-)(X) = c (x) i = 1,・・・Mi i ec(-)(x) = min{0,c (x)} i = m ，•…m i i e+1罚函数一般表示为： P ( X) = / ( X ) + h(c (-)( x ))(10.1)10.2)(10.3)(10.4)其中H (c(-)( X))是惩罚项，这个函数一般具有H(0) = 0 , lim H(c) = +3C匚+3较常用的形式为： P (X) = / (x) +C ||c (-) (X)f ( a > 0称为罚因子) (10.5)注：1)在上式中，范数常取为||・||，若取为H或H会导致p(x)不光滑2 3 12)当取||・||和> 1时，p(X)的光滑性可由2(c(-)(x))2 = (min{0,c (x)})2i直接验证。
事实上，在“转折点”处，可证得左、右导数均为0,由此可得(C(-)(X))2光滑性，从而P(X)光滑Courant 函数是最早使用的罚函数，也是最方便最重要的一种罚函数其形式为P(XQ)= /(x) +a ||c(-)(x)10.6)=/ (X)+a见 C2( X) + a迟(min{0,c (x)})2iii=1' me+1以下考虑一般的罚函数问题P(xQ)二 f (x) +叫”(-)(x)|$10.7)并且以后总用xQ)表示罚问题min P (x)xeRn &的解引理1设Q >Q > 0，则必有21f (x(Q )) > f (x(Q ))21|c(-)(x(Q2))卜 ||c(-)(x(Q]))|注：随着罚因子的增大，惩罚的力度加大， x(Q )将越来越靠近可行域(相当于取点范围不断减小)自然 f (x(Q ))会不断增加引理2令5=| |c (-)(x(Q ))|，则x(Q )是约束问题 min f ( x)xeRns.t ||c(-)(x) <8的最优解10.8)证明：用反证法证明若不然，容易构造出一个关于罚函数问题更好的解，导致矛盾由于原问题等价于min f (x)xeRnst ||c (-)(x) = 010.9)而当8 很小时，(10.8)是(10.9)的近似，从而 x(Q) 可看成是原问题的近似解。
特别地，当II c(-)(x(q ))11= 0时，x(Q)是原问题的精确解罚函数法的基本思想是：每次迭代增大罚因子Q，直到II c(-)(x)||缩小到给定的范围内由于要求解一系列无约束问题，故也称为 SUMT 外点法(Sequential Unconstrained Minimization Technique)外罚函数算法1)给出 x e Rn，q > 0，s > 0， k = 1112)利用初始值x，求解无约束问题(罚函数问题)minP (x)得到x(q ) k xeRn Qk k3)若 II c(-)(xQ ))1 | min || c(-)(x) ||xeRn则算法必有限终止证明：若定理不成立，则必有q T+2，且对一切k都有kII c(-)(x)(c )1 |>s (10.10)k而由定理条件，存在x & Rn，使得II c(-)(x)11<8 (10.11)由于 f(x) +q ||c(-)(x)1 h>f(x(q ))+q ||c(-)(x(q ))1 卜k k k k> f (x(q )) +q ||c(-)(x(q )) IP1 k k0 >1 c(-)(x)1 卜-II c(-)(x(q )) Ih> — [f (x(q )) — f (x)0k Q 1k这与(10.10)，(10.11)两式矛盾，原定理得证。
注：由此定理知，若问题有可行点，则对任给的8 >0，算法都必有限终止于问题的解，且II c(-)(x(Q ))11=5 <8 ok定理10.2如果算法不有限终止，则必有min || c(-)(x) ||>8，且xeRnlim 11 c(-) (x(q )) 11= min 11 c(-) (x) 11k fg k xeRn而｛x(Q )｝的任何聚点x*都是问题kmin f ( x)xeRn ( 10.12)s.t || c(-)(x)||= min || c(-)(y) ||yeRn的解由上述两定理直接得到如下推论：推论 设原问题有可行解，则算法或有限终止于一个近似解，或产生的点列｛x ｝其任何聚点都是原 k问题的解定理10.3若对某个确定的b > 0，无约束问题的最优解x9 ) e X，则xQ)必为原问题的最优解注：序列罚函数方法得到的点列｛x ｝是从可行域X的外部逐渐靠近X，一旦进入可行域X，算法k即终止，因此该方法称为SUMT外点法或外罚函数法§10.2 内点罚函数(障碍函数法)考虑不等式约束问题：min f ( x)/I 、 (10.13)s.t c (x) > 0(i = 1,…，m)i内点罚函数法的特点是：罚函数在可行域边界上的取值为无穷。
如果初始点为可行域内点，则此后 产生的点均为内点，罚函数相当于在约束域边界上竖起了一道墙，使迭代点一旦接近边界便碰壁而 回，故也称之为障碍函数法障碍函数法只适合不等式约束问题，不能用于等式约束问题常用的障碍函数主要有两种：m1P(x) = f (x) +b -1 -(倒数障碍函数) (10.14)1 c ( x)i =1 iP(x) = f (x)-b-1 近Inc (x)(对数障碍函数) (10.15)ii=1下面考虑一般内点罚函数形式：10.16)10.17)P (x) = f (x) +b-i 近 h(c (x))bii=1其中b > 0称罚因子，h(c)满足：lim h(c) =ct0+h(c ) > h(c ), Vc < c 1 2 1 2仍记x(b)为问题min P ( x)bxeRn的解由于内点罚函数方法的特点，若初始点是严格内点，则x(b)也必然是内点注：对内点罚函数问题minP (x)，并不是求它在整个空间Rn上的极小，而是求P (x)在可行域X bbxeRn的内部区域X =｛xIc (x)>0,i = 1,...m｝上的极小事实上，对数罚函数在X以外无意义，而倒0 i 0数罚函数除边界上无意义外，在其余处处有意义。
但在X以外，罚函数中某些项为负，且可取绝对 0值任意大的负值，从而 P .(x ) 趋于，从而在全空间的极小不存在所以以后提到障碍函数极小，总是在 X 中的极小但由于极小点在约束域内部，因而就具有了无约束的特性：如在极小点处梯度 0为 0；另外，由于迭代点列始终位于约束域内部，因此搜索方向的选取与无约束情形一样，只要是下降方向就是可行方向仅有的差别是在进行一维搜索时要适当控制步长，以免迭代点跑到约束域X 的外面去0 类似于外罚函数法，有如下结果：引理3设◎ >◎ > 0，则必有21f (xQ )) < f (xQ ))21区 h(c (x(Q ))) '区 h(c (x(Q )))i 2 i 1i=1 i=1直观解释：Q越大，则—i越小，实施的惩罚越小，xQ)就越能靠近边界由于可选择的范围增大, 因而f (x(q ))随着Q的增大而下降引理4令§=^h(c (x(Q)))，则xQ)也是问题ii=1的最优解min f ( x)s.t 迟h(c (x)) <6ii=1显然当6 充分大时，(10.19)是min f ( x)s.t 瓦 h(c (x))
由上面的分析可以看到：1)若Q> 0非常大，且6=区h(c (x(Q)))也非常大时，(10.19)ii=1是原问题很好的近似，因此它的最优解xQ)可视为原问题的近似解2)若Q > 0非常大但6有界时，由内点罚函数的定义知在xQ)附近罚函数与f (x)十分接近，于是xQ)也是原问题的近似解基于以上分析，有下述内点罚函数算法：1)2)3)给出初始内点xi,初始罚因子> 0，允许误差沦0，置 k :二1利用初始值x求解：min P (x)得x(q )，令x = x(q ) ok Q k k+1 kxeX 0 k若Q-1近h(c (x )) <8则停止，x 为近似解；否则Q ：= 10Q ； k := k +1，转2) k i k +1 k +1 k +1 ki=1对内点罚函数算法，有如下收敛性定理： 定理10・4设函数f (x)在可行域X上有下界，则算法在£ > 0时必有限终止；当不有限终止时(此时8 =0)，有lim 丄 £ h(c (x )) = 0，lim f (x ) = inf f (x)ks Q . [ i k+1 kT8 k xeX0k i=1 0注: 1) 一般地，在求解子问题minP (x)时，只需近似求解即可，进而产生出基于子问题近似求解 Qk的内点罚函数方法。
2)关于初始内点的求法有专门的讨论，可参见席少霖著《非线性最优化方法》§10.3 乘子罚函数(广义乘子法)考察 Courant 外罚函数PQ(x)= f(x)+Q2= f (x) + Q区(c(-)(x))210.20)i=1若x*是原约束问题的K-T点，由10.21)VP (x) = Vf (x) + 2q 乞(c(-) (x))Vc(-) (x) Qi=1注意到x*可行，故有VP (x) = Vf (x*)由于x*是K-T点，一般不满足Vf (x*) = Oo这意味着无 Q论Q取什么值，都不会有VP (x*) = 0这一结论意味着：希望取一个较大的Q，然后从罚函数问 Q题直接求出x*是不可能的因此，只好让Q不断增加，Q " 求得｛x(Q )｝但当Q非常大以 k k k k后，罚函数问题Hesse矩阵呈现病态(条件数很大)，这将导致数值不稳定为了克服这一缺陷，引入参数i = 0 >0(i = m ，…m)i i e+1P(x) = f (x) + 区乙([(c (x)-0 )(-)]2 -0 2) (10.。
