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

張濤,呂一兵

(長江大學(xué) 信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

0 引言

二層規(guī)劃是一種具有遞階結(jié)構(gòu)的系統(tǒng)優(yōu)化問題，其數(shù)學(xué)模型可以表示為:

其中，x∈Rn1,y∈Rn2分別為上層決策變量及下層決策變量.F(x,y),f(x,y)分別稱為上層目標函數(shù)以及下層目標函數(shù).

對二層規(guī)劃的求解是比較困難的，即使最簡單的情況即所有的函數(shù)為線性函數(shù)，也是NP-難問題.求解非線性二層規(guī)劃就更加困難了，目前求解非線性二層規(guī)劃的方法主要包括分支定界法[1]、下降方法[2]以及信賴域方法[3]等.事實上，由于非線性二層規(guī)劃的復(fù)雜性質(zhì)[4]，其算法設(shè)計一般針對的是具有某種特殊結(jié)構(gòu)的非線性二層規(guī)劃問題.

在本文中，考慮如下形式的二層二次規(guī)劃問題:

(1)

其中F(x,y),f(x,y)1分別為上層和下層的目標函數(shù)，c1,c2∈Rn1,d1,d2∈Rn2,b∈Rm均為已知向量，R,Q∈R(n1+n2)×(n1+n2)為對稱矩陣，A∈Rm×n1,B∈Rm×n2.x∈Rn1,y∈Rn2分別為上層、下層規(guī)劃問題的決策變量.

對于二層二次規(guī)劃問題(1)，考慮以下層問題的K-T最優(yōu)性條件代替下層問題，同時取互補條件為罰項，從而得到該類非線性二層規(guī)劃的相應(yīng)單層規(guī)劃問題.由于相應(yīng)的單層規(guī)劃為二次規(guī)劃問題，因此考慮用Frank-Wolfe方法進行求解.在本文接下來的內(nèi)容中，首先介紹相關(guān)的概念以及算法的理論基礎(chǔ);然后，設(shè)計二層二次規(guī)劃問題(1)的Frank-Wolfe方法，并以數(shù)值實驗驗證算法的可行性;最后對本文進行小結(jié).

1 主要結(jié)果

令

其中Q0∈Rn2×n2,Q1∈Rn2×n1,Q2∈Rn1×n1,則下層目標函數(shù)f(x,y),即為:

定義1 稱集合S={(x,y)|Ax+By≤b}為二層二次規(guī)劃問題的約束域.

定義2 稱集合P={x|存在y,使得(x,y)∈S}是上層決策變量x的可行域.

為了討論方便，我們假設(shè)S是非空緊的.假設(shè)Q0是負定矩陣.因此對每個給定的上層決策變量x∈P，下層規(guī)劃問題存在唯一的解，不妨記為y(x)，而且下層問題存在最優(yōu)解[6].

定義3 稱集合IR={(x,y)|(x,y)∈S,y=y(x)}為二層二次規(guī)劃問題的可行域.

盡管約束域S是一個凸多面體，但二層二次規(guī)劃問題的可行域IR一般不再是凸集，因此二層二次規(guī)劃問題是非凸規(guī)劃問題.下面給出二層二次規(guī)劃問題的最優(yōu)性條件，這也是求解二層二次規(guī)劃算法的理論基礎(chǔ).

定理1[1](x*,y*)∈S為二層二次規(guī)劃問題最優(yōu)解的充分必要條件是存在w*∈Rm,u*∈Rm,v*∈Rn1≥0,使得(x*,y*,w*,u*,v*)是下面規(guī)劃問題的解.

(2)

在問題(2)的約束條件中除互補外，其余均為線性約束，筆者考慮以互補條件為罰項，用精確罰函數(shù)的方法求解.即問題(2)轉(zhuǎn)化為:

(3)

其中:M>0為罰因子.

對于模型(2)與(3)，Liu等[5]證明了如下的定理.

定理2 如果問題(2)的可行域非空，且對于某個M0>0,問題(3)有解，則必存在M*≥M0使得對于所有的M≥M*，問題(2)與(3)有相同的非空最優(yōu)解集.

從定理2可以看出欲求解非線性規(guī)劃(2)，只需求解相應(yīng)的單層規(guī)劃(3)，而模型(3)的求解方法建立在如下命題的基礎(chǔ)上.為敘述方便，不妨記模型(3)的目標函數(shù)為F′(z),其中:z=(x1…xn1,y1…yn2,u1…um,v1…vn2,w1…wm)T，則相應(yīng)的約束條件記為:

A′z=α,z≥0.

其中A′,α為如下分塊矩陣:

此時模型(3)等價的記為:

minF′(z),s.t. A′z=α,z≥0

(4)

假設(shè)z(k)為問題(4)的任一可行點，在z(k)處取F′(z)的一階Taylor展開，則問題(4)轉(zhuǎn)換為:

(5)

對于問題(4)與(5)之間的關(guān)系有如下的命題.

定理3 設(shè)問題(5)有最優(yōu)解y(k)，則有如下結(jié)果:

則有

又因為

則

因為y(k)為問題(5)的最優(yōu)解，故對于問題(4)與(5)的任一可行點z(k)有:

即:

這就證明了y(k)-z(k)為問題(4)的一個下降方向，同時y(k)-z(k)為問題(4)的可行方向是顯然的.

并取z(k+1)=z(k)+ak(y(k)-z(k)).

以上就是傳統(tǒng)的Frank-Wolfe步驟.

2 算法及數(shù)值實驗

基于上述討論，可形成如下求解問題(1)的算法，具體的算法步驟如下.

算法:Step1. 給定罰因子M，以及誤差限ε>0;

Step2. 將二層二次規(guī)劃(BQP)轉(zhuǎn)化為(2)式;

Step3. 將(2)式中的互補松弛條件取為罰項，得到如下單層規(guī)劃

(6)

Step4. 將規(guī)劃(6)的目標函數(shù)在可行域的點zk=(xk,yk,uk,wk,vk)處線性展開得到:

(7)

為驗證本算法的可行性，我們考慮如下二層二次規(guī)劃問題[3-4]:

(8)

文獻中最優(yōu)解x=0.843 8,y=(0.765 7,0).

將(8)式的下層問題用其KT條件代替同時取互補松弛條件為罰項得到如下單層規(guī)劃:

(9)

從數(shù)值實驗我們可以看出求解二層二次規(guī)劃的Frank-Wolfe方法是可行的，同時如果誤差限取的更小，則得到的解將更加逼近原最優(yōu)解.

3 小結(jié)

從算法的收斂性及算例實現(xiàn)的過程可知從非線性二層規(guī)劃的任何一個可行點，利用本文中的算法都可以得到相應(yīng)的局部最優(yōu)解.如何將本文中的算法進行改進，得到問題的全局最優(yōu)解值得繼續(xù)研究.

參考文獻：

[1] Bard J F. Practical bilevel optimization algorithms and application[M].London:Kluwer Academic Publishers,1998.

[2] Vicente L, Savard G, Judice J.Decent approaches for quadratic bilevel programming[J].Journal of Optimization Theory and Applications, 1994,81(2):379-399.

[3] 劉國山，韓繼業(yè)，汪壽陽. 雙層優(yōu)化問題的信賴域算法[J].科學(xué)通報, 1998,43(4):383-387.

[4] Deng X. Complexity issues in bilevel linear programming[M].London:Kluwer Academic Publishers,1998:149-164.

[5] Dempe S. Foundation of bilevel programming[M].London:Kluwer Academic Publishers,2002.

[6] Shi C, Zhang G, Lu J.On the definition of linear bilevel programming solution[J].Applied Mathematics and Computation,2005,160:169-173.