第13章懲罰函數(shù)法

第十三章 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}，構(gòu)造關(guān)于cxP(x)P(c(x))

c(x)c(x),p:c(x) Px)是對x的不可行性的一種度量，并且Px0xS。我們稱Px)為外點(diǎn)懲罰項(xiàng)，F(xiàn)x,fxPx為外點(diǎn)罰函數(shù)，其中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)的最優(yōu)解。例1.1.1

mins.t.xx*2是最優(yōu)解?，F(xiàn)在如(1.1)構(gòu)造懲罰函數(shù)，取=2 xF(x,)xP(x) x(2x),xF(x,) x 12(x2),x1Fx(x,0x211

minFx,x(211

0x(2 1.1.1設(shè)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知，當(dāng)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)當(dāng)k0Pk)是(CNP)1.1.2知，當(dāng)kPxk 得最優(yōu)解xkk終止判別。若kPxk，停，否則k1ck，k=k+12注 若可解出含有參數(shù)的無約束優(yōu)化問題(UNP)的最優(yōu)解關(guān)于的表達(dá)式x()，那x*limx( minf(x,x)(x3)2(x s.t.x1x2解：如(1.1.1)構(gòu)造罰函數(shù)，取=2F(x,x,)(x3)2(x2)2(xx 2F2(x3)2(xx4)，F(xiàn)2(x2)2(xx2

F(xx,)xF0,

0得minFx, 53

5332 532 2 1 22 x

Px((x(x(

022 (2定理 設(shè)f(x),gi(x),i1,,m,hj(x),j1,,l是連續(xù)函數(shù)，(CNP)的可行域S非空x0Rn，(CNP)的解集合由最優(yōu)解組成。若存在0S{x|gi(x),i1,,m,|hj(x)|,j1,,是有界集，則求解(CNP)的外點(diǎn)罰函數(shù)法關(guān)于是收斂的，并且kPxk0*證明：若{xkx1,xKPxK0xKS，于是對(CNP)的任一可行解x，由P(x)=0知

f(x)F(x,K)F(xK,K)f(xK1.1.1知，{Fxk,k和{fxk是單調(diào)增序列，并且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是連續(xù)函數(shù)，由(1.3.3)Px)0xS，再在(1.3.1)令k(kJ得f(x*)f(x)f(根據(jù)(1.3.1)F*f*fxPx0fxFx,kFxk,kfxF*，F(xiàn)*f*，再由(1.3.3)得kPxk0。 minf(s.t.gi(x)0,i1,,fxgxi1,mgxgx),

x))T，則(CNP1)設(shè)(CNP1)S內(nèi)部非空，即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的最優(yōu)解為x(r)。當(dāng)r0時，x(r)趨于(CNP1)的最優(yōu)解。例2.1.1 min1(x1)3 s.t.x1x2G(x,x,r)1(x1)3x

1

rx1 2

1)2

，G1x4 (x x 因?yàn)镚(x1x2,r)關(guān)于x為凸函數(shù)，因此由x0,x0得minGxr)的最優(yōu)解 x(r)(12r 1,x(r) 下面討論r變化時fx(r)),Bx(rGx(r),r的變化情況。 設(shè)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 設(shè)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，縮小系數(shù)0c1>0k=1終止判別。若rB(xk)，停，否則 cr，k=k+1，轉(zhuǎn)2 k 注 若可解出含有參數(shù)r的無約束優(yōu)化問題(UNP)r的最優(yōu)解關(guān)于r的表達(dá)式x(r)，那x*limx(rr2.2.1fxgixi1,m是連續(xù)函數(shù)，(CNP1)S有界并且內(nèi)部非空。若用內(nèi)點(diǎn)罰函數(shù)法求解(CNP2)時0)產(chǎn)生無限序列{xk}和rk}，并且{xk}存在收斂子列，則{xk}的任一收斂子列收斂于(CNP1)的最優(yōu)解，并且rkBxk)0。是單調(diào)減序列，并且GxkrkGxkrkG*fxkf*

fxkfx*)，即{Gxkrk)}fxk)}有下界，故設(shè)G*f*f( 設(shè){xk}kJ是{xk的收斂子列，xkx(kJ)，則由fxgixi1,m的連續(xù)性得fxf*xSf*fx*，由(