大二下課件-最優(yōu)化4-2my

罰函數(shù)法與乘子minf(x)

ci(x)

i

,l}ci(x)

i

,經(jīng)濟(jì)解把目標(biāo)函數(shù)看為價(jià)格，約束條件看為某種〝規(guī)定〞的超范圍的高〝罰款〞政策，例如關(guān)稅政策。這樣總代價(jià)罰當(dāng)罰款高到一定程度時(shí)，用最小總代價(jià)所買到的東規(guī)定的范圍內(nèi)。于是約束問題轉(zhuǎn)化成為無約束問題。為達(dá)此目的，可逐次加大罰款求極小。圖形解uf(x)x∈R1約束范圍為S。改造u

f

xx使u*的無約束極小點(diǎn)成為u的約束極小點(diǎn)，如圖所示SSu=fSS圖4.2.1

f(x,x)x2x

x1x2-2 其最優(yōu)解x*令

1 1x2

xxF(x,

)=

xx 函數(shù)F(,2的性態(tài)極壞，無法用有效的無約束優(yōu)化MinMinf(x,x)x2x1212 x1x2-22P(x.x,)x2x2(xx2 其中是很大的正數(shù)x(x()x()122當(dāng)(x(),x()

(x*,

,l}minf(x,l}

ci(x)

i

P(x,)f(x)P(x,)f(x)P(x)，P(x,)f(x)l|c(x)|iP(x)l|c(x)|i當(dāng)x罰因子越大，懲罰越重因此當(dāng)充分大時(shí)，要使P(x,)取極P(x)應(yīng)分小，P(x,)的極小點(diǎn)充 近可行域 近最優(yōu)解,minf(,P(P(x,)f(x)P(x),P(x)ci(x)i|c(x)ic(x)i

ci(x)

i

P(P(x)m|min(0,ci(x)) m(|c(x)|c(x)ii2)當(dāng)x為可行解時(shí)，ci(x)0,P(x,)f(x)，不受懲罰；ci(x)ci(x)0,P(x)0,P(x,)f(x)P(x)，越大，懲罰越重因此當(dāng)充分大時(shí)，要使P(x,)取極小值P(x)應(yīng)充分小，P(x,)的極小點(diǎn)充分minfminf(x) ci(x)ci(x)iI{l,l},可行域D{xRn|c(x)0,iE,

(x)

0,iI} P(x,P(x,)f(x)P(x), P(xP(x)l|c(x)iilm|min(0,c(x))i1,當(dāng)xD當(dāng)xD

0，0P(x,)f(x)P(x)稱為約束問題的增廣目標(biāo)函數(shù)P(x)稱為約束問題的罰函數(shù)，參數(shù)通常取=2

0稱為罰因子求解約束問題轉(zhuǎn)化為求增廣目標(biāo)函數(shù)的系列無約束minP(x,k其中{k}為正的數(shù)列且

minf(x)x2x2 x11 最優(yōu)解x*f(x*)P(x,)

x2x2[min(0,x

x2

x1 x2x2(x x1 P

x1 2x2(x x

2x2令P

P得x() , x(

0. 它是minP(x,)的最優(yōu)解，最優(yōu)P(x,

( )2

)2 1

1 1當(dāng)x1(

故x(x*,P(x,f(x*)14.2.14.2.2出當(dāng) P(x,)的最優(yōu)解x()趨向于極限x*。x*即為原約束問題的最優(yōu)解x()往往不滿足約束條件4.2.1x(x(

2， 214.2.2

x() 1， x()都是從可行域外部趨向于最優(yōu)解x*因此稱通過求解一系列無約束最優(yōu)化問題來求解約束最優(yōu)化問題的方法又稱序列無約束極小化技術(shù)（SUMT，2已知約束問題制誤差>0和罰因子的放大c1（可取104,c0Step1給定初始點(diǎn)x0(可以不是可行點(diǎn))和初因子1（可取1。令k1minP(x,k)minP(x,k)f(x)kP(x)其中P(x)如前xkx(kStep3若kP(x)xk為問題停止。否則令

ck

k1

f(x,x)x2x

x1

-2取11

10,

,kf(x1,x2123456789 f(x1,x2 - -100.0000000023456789

f(x)

x2x2 x11kf(x1,x212--3--4--5-6-7-8-9-kf(x1,x21--2-3-4-5--6--7--8--9--例

f

(x2)4(x2x)2 x2x minminP(x,k)f(x)kP(x)min(x2)4(x2x)2(x2x P4(x2)P4(x2)4(x32x)x(x x2121 21P2(x2x)(x x221k122

10,kf(x1,x212 f(x1,x212kf(x1,x21--2例用外點(diǎn)法

f(x)

1

1)3x

1

P(x,

)f(x)(min(0,c(x))2min(0,

)2 1(x1)3x(min(0,x1)2min(0,

)2 P(x,kf1∞10kf(x1,x212-3-4-5-6-78收斂引理4.2.1對(duì)于由SUMT外點(diǎn)法產(chǎn)生的點(diǎn){xk}，k1,總PP(xk1,k1)P(xk,kPP(xk)P(xk1ff(xk1)f(xkminminf(x) ci(x)ci(x)iI{l,l},1,i|min(0,c(x))mili|c(x)lP(x)minP(x,)f(x)kP(x)的整體最優(yōu)解為x*和xk（k1）,對(duì)正數(shù)序列{kk

SUMT外點(diǎn)法產(chǎn)生的點(diǎn)列{xk}的任何聚點(diǎn)x必是一

minminf(x),xRn ci(x)0,i1,,當(dāng)x行D{x的

|

(x)

因此，可構(gòu)造如下的增廣目標(biāo)函數(shù)B(x,r)f(x)rB(x)，mBmB(x)ln(cii1ci(x) mB(x)稱為內(nèi)罰函數(shù)或函數(shù)（Barrier 參數(shù)r>0仍稱為罰因子。我們?nèi)≌臄?shù)列rk且

0，則求解minB(x,rk)f(x)rkB(x)其中B(x)如前面B(x)B(x)m i1ci(x)

mm

(x))稱為內(nèi)罰函數(shù)法SUMT算 內(nèi)罰函數(shù)已知不等式約束問題，其可行域的內(nèi)點(diǎn)集

，控制誤差1

0和罰因子的縮小系數(shù)0<c<1(可取)Step 以xk1minB(x,rk)f(x)rkB(x)得最優(yōu)解xkx(rk)Step 若rkB(xk,則xk為不等式約束問

k1例 minf(x,

)1(x1)3 1x1

x2增廣目標(biāo)函數(shù)B(x,x,r)1(x1)3

r( 1)

x1 增廣目標(biāo)函數(shù)B(x,x,r)1(x

1)3xr(ln(x1lnx)

令

B(B(x1,x2,r)31

B1

2 2所以

(1

r r)T當(dāng)r0x*

83例 minf(x,

)1(x1)3 1x1

x2 B(x,x,r)1(x1)3

r( 1)

x1 取x34)T

10,

0.1,迭代 k kfkrkB(xk112345所以最優(yōu)解

，最優(yōu)f*

f5

270引理 對(duì)于由SUMT內(nèi)點(diǎn)法產(chǎn)生的點(diǎn)xk(kB(xk1,rk1)B(xk,rk即增廣目標(biāo)函數(shù)B(xkrk)k定 設(shè)不等式約束問題的可行 D的內(nèi)點(diǎn)DxRn|c(x)0,iI}非空

在D存 小點(diǎn)x*，對(duì)嚴(yán)格單減的正數(shù)列

: r且r0， k SUMTxk的任何聚點(diǎn)x是不與外點(diǎn)法的收斂定理一樣,本定理中的最優(yōu)指說罰函數(shù)法--方法簡(jiǎn)單、易懂混合罰函數(shù)當(dāng)初始點(diǎn)x0等式約束和不被x0滿足的那些不等式約束采用外罰函數(shù)、而對(duì)被x0滿足的那些不等式i(c(x))ir2l(min(0,c(x)))21p(x,r)f(x)rln(ci(x))I1I2

|ci(x0|ci(x0

0,iII0,iI罰函數(shù)法由于增廣目標(biāo)函數(shù)的Hesse矩陣2P(x,)和2B(xr)的條件數(shù)隨的增大r少而造成在求解系列無約束問題數(shù)因子和r時(shí)往往處于進(jìn)退維谷的境乘子性質(zhì)，其原因是由罰因子

(或

0)能不能找到*，使(x**)就是L(x)的極小點(diǎn)例

f(x)

x23xx

x2

最優(yōu)解x*00)TL(x,)

x23xx2 x2(3)xx 對(duì)于任何,L(x)關(guān)于x的極小點(diǎn)是不存在的等式約束問題的乘子minfminf(x),xRn C(x)其中C(x)

(x), ,

(x))Tf(x)和ci(x)(i ,l)是二次連續(xù)可微函數(shù)2M(x,,)2M(x,,)L(x,)C(x)TC(x)增廣Lagange函數(shù) C(x)

,xM(x*,*,xlL(x*,*)c(x*l

(x*)， 其中x*是M(x*,)的穩(wěn)定點(diǎn)xTxT(ABBT)x 充分BTx0，故xTBBTx因此xTAx0必要 先證明存在一個(gè)數(shù)xRn

0，對(duì)任意的xT(A*BBT

0,(x

用反證法，假設(shè)不成立xT(AkBBTxT(AkBBT)x kk，

由于xk為有界序列x必有收斂子列xki，其極限為x

1 xT(AkBBT)x 得 xT(AkBBT)x 上式兩端取極限，ki， TTxAxlimi2BT TTxAxlimi2BT limBTBTx0,(xT故TxAx0,(xT引理中的條件T

Ax

相，故結(jié)論成立其次，設(shè)*，則對(duì)任意的xRnxT(ABBT)xxT(A*BBT)x于是必要性得證412在等式約束問題中，

等式約束問（）

fx)與cix)(1

l)是二階連續(xù)可微函x* *L(x*,*)i于任意非零向量zRn且zTi

(

0,

,lminminf(x),xRn C(x)均xzT2L(x*,*)zx則x*是等式約束問題的嚴(yán)格局部極小點(diǎn)426等式約束問題中412

Rn和

Rl）

fx)與cix)(1

l)是二階連續(xù)可微）存

x*

*零，即L(x*,*)i()對(duì)于任意非零向量zRn且zTc(x*) ix zT2L(x*,*)zx則存在一個(gè)數(shù)

0，對(duì)所有

*x*是無約束MM(x,*,)L(x,*)C(x)TC(2反之，若C(x0)0，且x0對(duì)某個(gè)0是M(x,, 的局部小點(diǎn)，則x0是等式約束問題的局部極小點(diǎn) 由M(x,,)的定義xM(x,,)xL(x,)A(x)C(x)其中A(x)為以ci(x)為列的矩陣x x M(x,,2**x L(x,)A(x)A(x2*** 由二階充分條件，對(duì)每個(gè)滿足A(x*Z0

Z0的向量xM(x,,2 xLxM(x,,2 xL(x,)A(x)A(x2 **x由引有

xZT2M(x*,*,)Zx又由Cx*0

xM(x,,)xL(x,)A(x)C(x) M(x*,*,)L(x*,*) 故x*為M(x*,)的嚴(yán)格局部極小點(diǎn)反之，因x0是M(x,0,)的局部極小點(diǎn)且C(x00，則對(duì)任意與x0充分靠近的可行解x，M(x0,0,)M(x,0,但C(x0MM(x0,0,)f(x0M(x,0,)f(x)

0,C(x)由M(x0,0,M(x,0,)f(x0)f(x)即x0為約束問題等式問題的局部極小minf(x)x23xx122 x2M(xM(x,,) (3)x22122x2因?yàn)?/p>

3，所以當(dāng)

2時(shí)M(x,,)M(x,,)* 212x22反之，求解無約束問minminM(x,,) 2 (21222令2x1(2)x2(3)得x

3)T 0因?yàn)?3，從而x0,0)Tx*，即為原約束問0由上述定理看到，乘子法并不要求罰因子趨于無窮大，只要求大于某個(gè)正數(shù)*，就能保證無約束問題minM(x*,)的最優(yōu)解為原等式約束問題的最優(yōu)解。如何求得*

，使

*對(duì)每個(gè)k求解無約束問題minM(xk,)設(shè)其最優(yōu)解為xkk為k1，再求解M(xk1,)的極小點(diǎn)因此得到兩個(gè)點(diǎn)列{xk}與 如何修正k才能做到這點(diǎn)呢xM(xk,k,f(xk)xM(xk,k,f(xk)C(xk)(k(C(xkxM(xk,k,f(xk)C(xk)(k(C(xk因?yàn)橐?/p>

x*,

且f(x*)C(x*)*所以采k1kC(xk或(k1)

(k)

cj(xk

,lj1,,l修正k若k

C(xC(xk0

k 當(dāng)xxM(xk,k,f(xk)C(xk)(k(C(xk

x*時(shí)，Cx*

0，即x*為可行中令kf(x*)C(x*)*即x*KTM(x,,M(x,,)L(x,)kk2C(x)C(x)T的最優(yōu)解xk為等式約束問題的最優(yōu)解且k為相C(xk) 必要性是顯然的。下面證充分性M(x,M(x,,)L(x,)kk2C(x)C(x)T的最優(yōu)解且C(xk)0，則對(duì)任意的x

x

|C(x)

0f(x)M(x,k,)M(xk,k,)f(xk)即xk又因C(xk)故f(xk)C(xk

0。

(xk)即k為與最優(yōu)解xk相應(yīng)的最優(yōu)Lagrange乘子向量此定理給出了乘子法的終止準(zhǔn)則，CC(xk)C(xk)/C(xkC(xk)/C(xk1算法423 等式約束問題的乘子法——PH算 因子1及其放大系0,1)k=1

最優(yōu)解C(x)C(x)2kTkT最優(yōu)解C(x)C(x)2kTkTf(x) C(x)minM(x,k,k 算法4.2.3 最初時(shí)Powell和Hestenes幾乎同時(shí)各自獨(dú)立地提出（1969年，故簡(jiǎn)稱為PH算法24.2.1求2

f(x,x)x2x

x1

-2M(xM(x1,x2,, 2 (xx2)22(xx2)2121212令M

(x

M

(x

xxx2122將換為k，再把x1x2的值代入乘子迭代公k

2),

C(xk kk k顯然，當(dāng)kk1k

0時(shí)k收斂，且kk 2k設(shè)k，對(duì)上式取極**1**1*在x

2 2取10*2得原問題的最 x*(x*x*)T

2

6 minP(x,k)

x1x21x21

2

(x

2

minM(x,k,k1x21

2(x

(x

2

k0.052：k：

k0

0,k

k(x1

kkXk(外罰函數(shù)法Xk(乘子法0（0.0714，(0.07141(0.15072(0.1538，3(0.1904，(0.24094(0.2162(0.24875(0.2318(0.249960.2406(0.24997(0.24528(0.24759(0.2487(0.2492(0.2496(0.2498(0.2499(0.2499(0.2499

f(x,x)x2x

11,c11,c108，乘子法1kf(x1,x21231kf(x1,x2123456789kf(x1,x21234567

f(x,x)x2x

x1

乘子1,c10,108，=0.6,1kf(x1,x21---2--3456789

f(x,x)x2x

x1

乘子11,c10,108，=0.5,k f(x1,x21 2 3 4 5 6 7 8 91.18877-.83011305804236.43183不等式約束問題的乘子minminf(x),xRn ci(x)0,i,引進(jìn)輔助變量ziminminf(x),xRn c(x)z20,iii,

m)則可使用前段等式約束問題乘子法。此時(shí)增廣MM(x,z,f(x)m(c(x) )2 i2(i先考慮MzM(x,,)minM(xz,,)zizi(i(ci(x2i1,zM(x,

(x)

時(shí)

z2i

c(，M(x,z,M(x,z,f(x)m(c(x) )2 i2i否則zi0， 2i1max(0,c(x) iii,MM(x,z,f(x)m(c(x) )2 i2(i i(ci(x) 2i c(x)z 22222 ii(z ibic(x)i c(x)時(shí) z2i c(， zi否則zi故

000 2i1max(0,c(x) iii,MM(x,z,f(x) m(c(x) )2i(i2 2i1max(0,c(x) iii,得不等式約束問題的增廣目標(biāo)函數(shù)f(x)M(x,,1mmax(0,c( 22iii 2i1max(0,c(x) iii,kk ) )i()2i,1,(k1(k1)im ix)imm2c(x)212ii1min1min(m)i22 i1一般約束問題的乘子minminf(x),xRn ci(x)0,i ,lci(x)0,il ,時(shí)kikicixk),i 1, lk1ima0,(i) xk(f(x)M(x,,1mmax(0,c( i222iliilc(x)2l2 (x)lc(x)2kikjl1mmin(c(x ki)21則終止

k算法 一般約束問題的乘子法——PHR算 選定初始點(diǎn)x0、初始乘子向量1、初始子1及其c>1、控制誤差k=1

0與常數(shù) 以xk1minM(x,k,kM(x,,f(x)

max(0,c(x))22m2ilm

ll

(x)2

ll

c2(x)i得最優(yōu)解xkiS1klc(x)21klc(x)2ikmmin(c(x2 ki)

/k

時(shí)，轉(zhuǎn)Step5;否則令k

kikikic(x),iikk1imax0,( )c(x ,l),il, 轉(zhuǎn)Step2以上算法是Rockfellar在PH算法的基礎(chǔ)上（1973年P(guān)HR算法2例 用PHR2 min(x2x2 s.t.xx f(x)M(f(x)M(x,,1mmax(0,c( 22iiiM,,, x2x 1max(0,(x

2 ＝＝

2,

x1

2 x2x2

(xx2)2, xx2