一類非線性二層規(guī)劃的Frank_Wolfe方法

1、第卷第期年月自然科學(xué)版）湖北大學(xué)學(xué)報(bào)（），（）文章編號(hào)：一類非線性二層規(guī)劃的方法張濤，呂一兵（）長江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北荊州摘要：利用下層問題的最優(yōu)性條件將下層為線性規(guī)劃的一類非線性二層規(guī)劃轉(zhuǎn)化為相應(yīng)的單層規(guī)劃，同時(shí)取互補(bǔ)條件為罰項(xiàng)，得到該類問題的單層罰問題；然后利用方法對(duì)單層罰問題進(jìn)行求數(shù)值實(shí)驗(yàn)表明該方法是可行的解非線性二層規(guī)劃；最優(yōu)解；方法關(guān)鍵詞：文獻(xiàn)標(biāo)志碼：中圖分類號(hào)：引言二層規(guī)劃是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題，其數(shù)學(xué)模型可以表示為：，（，（，；），（）（），其中，分別稱為上層目標(biāo)函數(shù)以，（，分別為上層決策變量及下層決策變量）（）及下層目標(biāo)函數(shù)對(duì)二層規(guī)劃的求解是比較困難的，即使最簡(jiǎn)

2、單的情況即所有的函數(shù)為線性函數(shù)，也是難問題、求解非線性二層規(guī)劃就更加困難了，目前求解非線性二層規(guī)劃的方法主要包括分支定界法下降方，以及信賴域方法等事實(shí)上，由于非線性二層規(guī)劃的復(fù)雜性質(zhì)其算法設(shè)計(jì)一般針對(duì)的是具有法某種特殊結(jié)構(gòu)的非線性二層規(guī)劃問題在本文中，考慮如下形式的二層二次規(guī)劃問題：（，（，）（），是下面問題的解，（，（）（），（），其中（，均為已知向量，）（）分別為上層和下層的目標(biāo)函數(shù)，（）（）為對(duì)稱矩陣，下層規(guī)劃問題的決，分別為上層、策變量），對(duì)于二層二次規(guī)劃問題（考慮以下層問題的最優(yōu)性條件代替下層問題，同時(shí)取互補(bǔ)條件為罰項(xiàng)，從而得到該類非線性二層規(guī)劃的相應(yīng)單層規(guī)劃問題由于相應(yīng)的單層規(guī)劃為

3、二次規(guī)劃問題，因此考慮用在本文接下來的內(nèi)容中，首先介紹相關(guān)的概念以及算法的理論基方法進(jìn)行求解）然后，設(shè)計(jì)二層二次規(guī)劃問題（的并以數(shù)值實(shí)驗(yàn)驗(yàn)證算法的可行性；最后對(duì)本礎(chǔ)；方法，文進(jìn)行小結(jié)收稿日期：）基金項(xiàng)目國家自然科學(xué)基金項(xiàng)目（資助；教育部重點(diǎn)實(shí)驗(yàn)室開放基金項(xiàng)目（資助；湖北省教育廳重點(diǎn)項(xiàng)）目（資助），作者簡(jiǎn)介：張濤（男碩士湖北大學(xué)學(xué)報(bào)（自然科學(xué)版）第卷主要結(jié)果令，其中則下層目標(biāo)函數(shù)（即為：，），（）（）（定義稱集合為二層二次規(guī)劃問題的約束域，）定義稱集合使得（是上層決策變量的可行域，存在，）為了討論方便，我們假設(shè)是非空緊的假設(shè)是負(fù)定矩陣因此對(duì)每個(gè)給定的上層決策變量，下層規(guī)劃問題存在唯一的解，不妨記

4、為（而且下層問題存在最優(yōu)解，）（定義稱集合為二層二次規(guī)劃問題的可行域，），）（盡管約束域是一個(gè)凸多面體，但二層二次規(guī)劃問題的可行域因此二層二次一般不再是凸集，規(guī)劃問題是非凸規(guī)劃問題下面給出二層二次規(guī)劃問題的最優(yōu)性條件，這也是求解二層二次規(guī)劃算法的理論基礎(chǔ)，定理，（為二層二次規(guī)劃問題最優(yōu)解的充分必要條件是存在，）使得（是下面規(guī)劃問題的解，），（，）（）（），）在問題（的約束條件中除互補(bǔ)外，其余均為線性約束，筆者考慮以互補(bǔ)條件為罰項(xiàng)，用精確罰函數(shù)的方）法求解即問題（轉(zhuǎn)化為：，（，（）（）（），（）（）其中：為罰因子），對(duì)于模型（與（等證明了如下的定理）定理如果問題（的可行域非空，且對(duì)于某個(gè)，問題（

5、有解，則必存在使得對(duì)）問題（與（有相同的非空最優(yōu)解集于所有的，），從定理可以看出欲求解非線性規(guī)劃（只需求解相應(yīng)的單層規(guī)劃（而模型（的求解方法建），立在如下命題的基礎(chǔ)上為敘述方便，不妨記模型（的目標(biāo)函數(shù)為其中：（）（，則相應(yīng)的約束條件記為：），其中，為如下分塊矩陣：，）此時(shí)模型（等價(jià)的記為：，（），（）（）假設(shè)（為問題（的任一可行點(diǎn)，在（處取的一階則問題（轉(zhuǎn)換為：（）展開，（）（），）對(duì)于問題（與（之間的關(guān)系有如下的命題），定理設(shè)問題（有最優(yōu)解（則有如下結(jié)果：（）（）（）（如果則（是問題（的點(diǎn)（），（）（）（）（）（）如果則（的一個(gè)可行下降方向（）不成立，是問題（），定理的證明（因?yàn)閱栴}（有最優(yōu)

6、解（則必存在行向量，使得：（）（），（），第期張濤等：一類非線性二層規(guī)劃的方法其中：，（）（）（）（）（），（）（）（）（）（）（）（）（）（）（）（）（），（）（）（又因?yàn)椋ǎ?，（）（）（）（）（）則（）（）（則有由此，存在使和，（），（）（），（）這就證明了如果則（是問題（的點(diǎn)（）（），（）（）（）（如果則有：（）不成立，（）（）（）（）（）（）（）（）因?yàn)椋閱栴}（的最優(yōu)解，故對(duì)于問題（與（的任一可行點(diǎn)（有：（）（）（）（）（），即：（）（）（）（）（）這就證明了（的一個(gè)下降方向，同時(shí)（的可行方向是顯然的為問題（為問題（）（），（從定理中的結(jié)論（進(jìn)一步有，如果（這時(shí)可從（出發(fā)，沿方向（）

7、，（）即求進(jìn)行精確線性搜索使得：（）（）（）（），（）（）（并?。ㄒ陨暇褪莻鹘y(tǒng)的步驟（）（）（）（）算法及數(shù)值實(shí)驗(yàn)）基于上述討論，可形成如下求解問題（的算法，具體的算法步驟如下算法：以及誤差限；給定罰因子，）轉(zhuǎn)化為（式；將二層二次規(guī)劃（）式中的互補(bǔ)松弛條件取為罰項(xiàng)，得到如下單層規(guī)劃將（，（，），（，（）（），），）的目標(biāo)函數(shù)在可行域的點(diǎn)處線性展開得到：將規(guī)劃（，）（，（，），（）（），），），）式的最優(yōu)解為檢驗(yàn)是否滿足終止條件，如果有（假設(shè)（，（）則為（式的點(diǎn)；否則沿方向進(jìn)行精確線性搜索，即求，滿足：，（），同時(shí)令轉(zhuǎn)，（：為驗(yàn)證本算法的可行性，我們考慮如下二層二次規(guī)劃問題，）（，（），）文獻(xiàn)

8、中最優(yōu)解，（）將（式的下層問題用其條件代替同時(shí)取互補(bǔ)松弛條件為罰項(xiàng)得到如下單層規(guī)劃：，（），各變量均大于、等于零，（）湖北大學(xué)學(xué)報(bào)（自然科學(xué)版）第卷，對(duì)于上式不妨令（取初始可行點(diǎn)罰因子誤差限，（，），）在初始可行點(diǎn)對(duì)（式的目標(biāo)函數(shù)線性展開，同時(shí)求解可得到（，），取方向經(jīng)檢驗(yàn)知不滿足終止條件，沿搜索可得到新的展開點(diǎn)（，），在該點(diǎn)展開求解可得到取方向經(jīng)檢驗(yàn)，（，）知不滿足終止條件，沿搜索得到新的展開點(diǎn)（，），），）在該點(diǎn)展開求解得到檢驗(yàn)可知：則為（，（，）二層二次規(guī)劃（的最優(yōu)解即，（從數(shù)值實(shí)驗(yàn)我們可以看出求解二層二次規(guī)劃的同時(shí)如果誤差限取的方法是可行的，更小，則得到的解將更加逼近原最優(yōu)解小結(jié)從算法的收斂性及算例實(shí)現(xiàn)的過程可知從非線性