互補(bǔ)約束問題的松弛規(guī)劃

互補(bǔ)約束問題的松弛規(guī)劃

1mpcc的算法相互限制問題（pmc）是一種特殊的限制優(yōu)化問題。與一般限制優(yōu)化問題相比，其基本限制不僅包括等式限制和等式限制，還包括相對復(fù)雜的相互限制。mpc的一般形式如下。且假設(shè)f,g,h,G,H均二次連續(xù)可微.互補(bǔ)約束問題因其特殊的約束條件,使得它與一般約束最優(yōu)化問題具有很大的區(qū)別[1,2],象MFCQ,LICQ等一般約束最優(yōu)化問題的約束規(guī)范條件在MPCC中已不再成立,而且MPCC的可行域結(jié)構(gòu)也復(fù)雜得多,我們不能簡單地應(yīng)用已有的求解約束最優(yōu)化問題的方法和理論去求解MPCC.因此,解決此類問題的算法成為近幾年運(yùn)籌學(xué)研究的熱點(diǎn),出現(xiàn)了象內(nèi)點(diǎn)罰算法(PIPA)[3],磨光二次規(guī)劃(SSQP)算法[4],分片逐步二次規(guī)劃(PSQP)算法[3]以及牛頓捆集信賴域算法(Newton,Trust-Region)并得到如下收斂性質(zhì):設(shè)z與H.Scheel和S.Scholtes不同,G.H.Lin和M.Fukushima(2005)通過技巧性地同時改造兩個約束條件(3)與(4)式,在ε>0的情況下,得到了一種新的松弛規(guī)劃子問題(二)[8]:并在較弱的條件下得到了與(一)相同的收斂結(jié)果.在以上松弛規(guī)劃算法的啟發(fā)下,本文運(yùn)用烏力吉關(guān)于互補(bǔ)問題乘子法的思想[9,10],構(gòu)造了一種全新的松弛子問題.與以上松弛算法中所用到的松弛子問題相比,該子問題的約束條件都有明顯的減少.接下來,文中引入了一種基于逐步二次規(guī)劃(SQP)方法的新算法,通過對該松弛子問題有技巧地應(yīng)用SQP方法,在不需要迭代序列的聚點(diǎn)滿足嚴(yán)格互補(bǔ)的較弱條件下獲得了該算法的全局收斂性.貫穿全文,我們約定:下標(biāo)表示向量的分量,上標(biāo)表示迭代序列的序號.設(shè)F(z)為向量函數(shù),定義集合D2般約束優(yōu)化問題在本節(jié),首先給出MPCC的一些常用一階最優(yōu)性條件:(1)B穩(wěn)定點(diǎn)[11]:前面提到,對于MPCC問題,一般約束優(yōu)化問題的約束規(guī)范條件LICQ和MFCQ等均不再成立.事實(shí)上,若我們把MPCC看成一般約束優(yōu)化問題,在可行點(diǎn)線性無關(guān).注意到(2)W穩(wěn)定點(diǎn)[12]:設(shè)易見,若當(dāng)可行點(diǎn)z滿足條件(10)-(12)時,稱為MPCC的W穩(wěn)定點(diǎn),其中μ=(μ(3)C穩(wěn)定點(diǎn)[12]:可行點(diǎn)(4)M穩(wěn)定點(diǎn)[13]:可行點(diǎn)(5)S-B穩(wěn)定點(diǎn)[12]:可行點(diǎn)命題2.1設(shè)3種新的松弛子問題我們在R稱λ為乘子參數(shù),稱為關(guān)于函數(shù)min(u,v)在變量u(或v)的乘子.引入殘量函數(shù)再引入乘子參數(shù)的殘量這樣,(13)也可寫成命題3.2函數(shù)l(u,v,λ)和證明l(u,v,λ)的連續(xù)可微性以及▽l(u,v,λ)的形式(14)易見.由(13)式易見φ(u,v,λ)為了書寫方便,以下我們記一般互補(bǔ)問題為NCP(G,H).定義函數(shù)L(z,λ),χ(z),φ(z,λ),μ(z,λ)和θ(z,λ)如下且稱χ(z)為NCP(G,H)在z的乘子,由引理3.1易見命題3.3(ⅰ)(ⅱ)命題3.4函數(shù)L(z,λ)和θ(z,λ)在R證明由命題3.2知,函數(shù)l(u,v,λ)和υ(u,v,λ)連續(xù)可微,又由假設(shè)函數(shù)F(z),G(z)也連續(xù)可微,注意到L(z,λ)和θ(z,λ)是由l(u,v,λ),υ(u,v,λ)與F(z),G(z)復(fù)合而成,故由復(fù)合函數(shù)的求導(dǎo)法則,我們很容易得到函數(shù)L(z,λ)和θ(z,λ)的連續(xù)可微性.且由式(14),有由命題3.3及函數(shù)θ(z,λ)的表達(dá)式,我們考慮MPCC問題的如下松弛子問題:其中δ>0稱為松弛迭代參數(shù),λ稱為乘子迭代參數(shù).設(shè)F為MPCC問題的可行域,從命題3.3容易看出,對任意z∈F和δ>0,只要在(Re(δ))中取λ=χ(z),則(z,λ)∈F,這里Fδ表示問題Re(δ)的可行域.因此,我們稱Re(δ)為MPCC問題的松弛形式.4基于二次規(guī)劃的松弛問題基于MPCC的松弛子問題Re(δ),我們給出求解MPCC問題的一種松弛算法.該算法的基本思想是對松弛子問題Re(δ)實(shí)施逐步二次規(guī)劃法.首先,我們來討論求解目標(biāo)函數(shù)下降方向的子問題.在第k個迭代步,設(shè)參數(shù)為δk,并令解得,其中Q由于二次規(guī)劃Sub(δ為構(gòu)造以下算法,我們考慮松弛子問題Re(δ)的如下L算法4.1(一般互補(bǔ)約束問題的松弛逐步二次規(guī)劃算法)步0(初始步)給出初始點(diǎn)(z步1(終止準(zhǔn)則)若滿足給定的終止條件,則算法停止;否則轉(zhuǎn)步2.步2(確定下降方向及其乘子)從子問題Sub(δ步4(線搜索)確定步長t步5(產(chǎn)生新的迭代點(diǎn))步6(修正松弛迭代參數(shù))并修正其中的參數(shù)步7(修正矩陣并循環(huán))修正Q5關(guān)于線性時值的證明本節(jié)證明算法4.1的全局收斂性.首先給出如下兩個基本假設(shè)[4]假設(shè)1存在正常數(shù)α,γ,對每個k,對稱正定矩陣滿足不等式假設(shè)2存在充分大的下標(biāo)在算法4.1中,由于對稱正定矩陣Q引理5.1在算法4.1的迭代過程中,當(dāng)d證明為書寫方便,記w=(z,λ),并令由函數(shù)g,h,L,θ的連續(xù)可微性易知,罰函數(shù)由于d我們再對(23)式兩邊同時乘以d而由(24)-(25)及(27),(29)有又從算法4.1步3注意到σ于是,由Q引理5.2在假設(shè)1和假設(shè)2成立的條件下,設(shè)證明由假設(shè)2知,乘子序列{μ所以序列{Q從而‖d引理5.3若則證明我們對(23)-(29)同時取極限,因?yàn)楹瘮?shù)f,h,g,G,H連續(xù)可微,所以此時成立.由于函數(shù)f,g,h,L,θ的連續(xù)可微性,我們可以得到以下引理:引理5.4設(shè)則必存在K證明易見,與函數(shù)T復(fù)合而成.由于函數(shù)Y為關(guān)于t的凸函數(shù),因此必存在一個向量又由凸分析的知識[14],我們知道序列{η由函數(shù)Y的凸性及函數(shù)T的連續(xù)可微性,我們有引理5.5在假設(shè)1和假設(shè)2成立的條件下,若證明由算法4.1中步6可知,0<J由算法的迭代過程可知,此時集合{k|‖d利用引理5.2及假設(shè)1和假設(shè)2,由于序列{Q所以由算法4.1,我們必有否則,設(shè)當(dāng)k>C時,由步5可得設(shè)集合因?yàn)镵否則有此時我們?nèi)匀∷杂?41),(42),對(43)兩邊同時取極限,得又由假設(shè)(40)知,上式左邊為+∞而右邊為一個實(shí)數(shù),這樣我們得出矛盾.所以假設(shè)(40)不成立,我們有結(jié)論(39).當(dāng)此時與最初的假設(shè)(38)式矛盾.設(shè)數(shù)列即由引理5.3,引理5.4,我們可找到K由于0<a<1,所以與(38)式矛盾綜上,由(44)以及(45)得假設(shè)(38)不成立,所以定理5.6在假設(shè)1和假設(shè)2成立的條件下,令下標(biāo)集合即以及由Γ的選取易知與引理5.3的證明過程相同,我們