第13章惩罚函数法

第十三章 minf(s.t.gi(x)0,i1,,hj(x)0,j1,,fxgixi1,mhjx),j1,l g(x)max{0,g(x)},i1,,

ci(x)

i1,,

，c(x)(c(x),, ( (x) im1,,m 则(CNP)SxRn|cx0}对(CNP)SxRn|cx0}，构造关于cxP(x)P(c(x))

c(x)c(x),p:c(x) Px)是对x的不可行性的一种度量，并且Px0xS。我们称Px)为外点惩罚项，Fx,fxPx为外点罚函数，其中0Pxcx))

|ci(x)

hj( ，其 ，

j F(x,)f(x)max{0,gi(

hj(x)j

Px)

c maxcxmax{max{0,gxi1,m,hx),j1,l 1iml F(x,)f(x)max{max{0,gi(x)},i1,,m,hj(x),j1,,x即c(x())0，从而使x()趋于(CNP)的最优解。例1.1.1

mins.t.xx*2是最优解。现在如(1.1)构造惩罚函数，取=2 xF(x,)xP(x) x(2x),xF(x,) x 12(x2),x1Fx(x,0x211

minFx,x(211

0x(2 1.1.1设012xkx(kk1,2，则F(x1,1)F(x2,2),P(x1)P(x2),f(x1)f(x2证明xkx(kPx0和01F(x1,1)F(x2,1)f(x2)1P(x2)f(x2)2P(x2)F(x2,f(x1)1P(x1)

f(x2)1P(x2)f(x2)1P(1.1.1知，当Px(越来越小。1.1.2xkx(kkPxkxk是minf(s.t.P(x)

0F(xk,k)F(x,k)f(xk)f(x)k(P(xk)P(x))f(xk)f(fxkfxxkPk)当k0Pk)是(CNP)1.1.2知，当kPxk 得最优解xkk终止判别。若kPxk，停，否则k1ck，k=k+12注 若可解出含有参数的无约束优化问题(UNP)的最优解关于的表达式x()，那x*limx( minf(x,x)(x3)2(x s.t.x1x2解：如(1.1.1)构造罚函数，取=2F(x,x,)(x3)2(x2)2(xx 2F2(x3)2(xx4)，F2(x2)2(xx2

F(xx,)xF0,

0得minFx, 53

5332 532 2 1 22 x

Px((x(x(

022 (2定理 设f(x),gi(x),i1,,m,hj(x),j1,,l是连续函数，(CNP)的可行域S非空x0Rn，(CNP)的解集合由最优解组成。若存在0S{x|gi(x),i1,,m,|hj(x)|,j1,,是有界集，则求解(CNP)的外点罚函数法关于是收敛的，并且kPxk0*证明：若{xkx1,xKPxK0xKS，于是对(CNP)的任一可行解x，由P(x)=0知

f(x)F(x,K)F(xK,K)f(xK1.1.1知，{Fxk,k和{fxk是单调增序列，并且f(x*)F(x*,k)F(xk,k)f(xk 即{Fxk,k和fxk有上界，故{Fxk,k和fxkF(xk,k)F*，f(xk)f则再由k

kP(xk)F(xk,k)f(xk)F*f* P(xk)

kxkSS为紧集，因此xk}存在收敛子列{xk}kJxkx(kJ。由已知fxPx是连续函数，由(1.3.3)Px)0xS，再在(1.3.1)令k(kJ得f(x*)f(x)f(根据(1.3.1)F*f*fxPx0fxFx,kFxk,kfxF*，F*f*，再由(1.3.3)得kPxk0。 minf(s.t.gi(x)0,i1,,fxgxi1,mgxgx),

x))T，则(CNP1)设(CNP1)S内部非空，即intSxRn|gx0}，在intSgx的单 gx0(充分小 B(x)B(g(x)),g(x) ，xint g(g(

f(x)rB( g(G(x,r)f(x)g( mBx)-lngixllG(x,r)f(x)rlngi(

F(x, 记(UNP)r的最优解为x(r)。当r0时，x(r)趋于(CNP1)的最优解。例2.1.1 min1(x1)3 s.t.x1x2G(x,x,r)1(x1)3x

1

rx1 2

1)2

，G1x4 (x x 因为G(x1x2,r)关于x为凸函数，因此由x0,x0得minGxr)的最优解 x(r)(12r 1,x(r) 下面讨论r变化时fx(r)),Bx(rGx(r),r的变化情况。 设rr0，xkx(r),B(xk)0,k1,2， G(x1,r1)G(x2,r2)，B(x1)B(x2)，f(x1)f(x2证明xkx(rBx0rr0 G(x2,r)G(x1,r)f(x1)rB(x1)f(x1)rB(x1)G(x1,r 得第一个不等式。由Gx2rGx1r和Gx1rGx2r rr0得第二个不等式。由Gx1rGx2r f(x1)rB(x2)f(x2)rB(x2)f(x2)rB( 定理2.1.2 设xkx(r)，B(xk)，则xk是 minf(s.t.B(x)

0G(xk,r)G(x,r)f(xk)f(x)r(B(xk)B(x))f(xk)f( fxk

x0intSr1>0，缩小系数0c1>0k=1终止判别。若rB(xk)，停，否则 cr，k=k+1，转2 k 注 若可解出含有参数r的无约束优化问题(UNP)r的最优解关于r的表达式x(r)，那x*limx(rr2.2.1fxgixi1,m是连续函数，(CNP1)S有界并且内部非空。若用内点罚函数法求解(CNP2)时0)产生无限序列{xk}和rk}，并且{xk}存在收敛子列，则{xk}的任一收敛子列收敛于(CNP1)的最优解，并且rkBxk)0。是单调减序列，并且GxkrkGxkrkG*fxkf*

fxkfx*)，即{Gxkrk)}fxk)}有下界，故设G*f*f( 设{xk}kJ是{xk的收敛子列，xkx(kJ)，则由fxgixi1,m的连续性得fxf*xSf*fx*，由(