非內(nèi)點同倫方法求解雙層規(guī)劃問題

范曉娜,陳 燕,閆慶倫

(南京郵電大學(xué)理學(xué)院,江蘇南京 210023)

§1 引言

雙層規(guī)劃問題(BLPP)是一種優(yōu)化問題,它受到另一層優(yōu)化問題的約束.其通用形式如下:

其中(x,y)∈Rn+m和f,F:Rn+m →R,

雙層規(guī)劃也稱為雙層優(yōu)化,是指模型約束中包含子目標(biāo)函數(shù)和子約束條件的數(shù)學(xué)規(guī)劃.Bracken和McGill[1]在研究不平衡經(jīng)濟(jì)市場競爭中首次提出的.Cander和Norton[2]在科學(xué)報告中正式提出了雙層規(guī)劃.自1980年以來,雙層規(guī)劃在理論和算法上得到了廣泛的關(guān)注和迅速的發(fā)展,并逐漸形成了一個新的運籌學(xué)分支.目前,雙層規(guī)劃問題在工程設(shè)計,生態(tài),經(jīng)濟(jì)等領(lǐng)域有著廣泛的應(yīng)用,例如農(nóng)業(yè)信貸分配[3],經(jīng)濟(jì)規(guī)劃[4],交通運輸[5],優(yōu)化交通信號[6-7]等.

自20世紀(jì)70年代以來,研究人員提出了許多求解雙層規(guī)劃的算法.算法主要有幾種類型:(1)極點算法.它主要用于求解線性雙層規(guī)劃問題.其基本思想是:線性雙層規(guī)劃問題的最優(yōu)解必須在約束域的極點處得到.實際上,這是頂點枚舉法,可以用單純形法[8]解決;(2)分枝定界算法.它主要用于求解凸和線性雙層規(guī)劃問題.其基本思想是用問題的KKT條件代替底層問題,構(gòu)造一個等價于雙層規(guī)劃問題的KKT模型,然后利用分枝定界技術(shù)處理KKT問題的互補項,從而將該問題轉(zhuǎn)化為求解一個含有等式和不等式約束的一般優(yōu)化問題[9-14];(3)罰函數(shù)算法.該算法主要將懲罰函數(shù)原理應(yīng)用到非線性規(guī)劃理論中,通過使用不同的懲罰項將下層問題轉(zhuǎn)化為無約束的數(shù)學(xué)規(guī)劃問題,然后在上層目標(biāo)函數(shù)中加入懲罰項,將問題轉(zhuǎn)化為具有懲罰參數(shù)的單層問題[15-17];(4)K-T方法.該算法的基本思想是用其Kuhn-Tucker條件代替低層規(guī)劃問題,并將雙層規(guī)劃問題轉(zhuǎn)化為單層的非線性規(guī)劃問題.這個想法可以參考[18],這是解決BLPP的同倫方法.同倫方法的顯著優(yōu)點是它生成的算法在一定的較弱條件下具有全局收斂性.本文仍然考慮用同倫方法求解雙層規(guī)劃問題.主要任務(wù)是放寬對初始點的要求,并在無界集合上求解BLPP.

本文的其余部分安排如下:§2構(gòu)造了BLPP的同倫方程以及得到一些基本結(jié)果;§3在適當(dāng)條件下,證明了同倫曲線的有界性以及同倫路徑的點全局收斂于BLPP的KKT點;§4使用Euler-Newton算法[19]對同倫路徑進(jìn)行了數(shù)值跟蹤,給出一些數(shù)值結(jié)果,驗證了所論方法的有效性.

§2 BLPP的同倫方程和一些基本結(jié)果

考慮BLPP的f,g,F,Gi,i=1,2,……,m2為三次連續(xù)可微的凸函數(shù),從而G也是凸函數(shù).首先,考慮下層最優(yōu)化問題:

假設(shè)對于給定的x ∈Rn,集合{y ∈Rm:G(x,y)＜0}/=?,下層優(yōu)化問題相應(yīng)地轉(zhuǎn)化為以下的KKT系統(tǒng)[18].

其中w=(x,y,u)T,e=(1,……,1)T∈Rm2,t ∈(0,1].設(shè)～f(w)=f(x,y),～g(w)=g(x,y).符號定義如下:

在文獻(xiàn)[18]中,構(gòu)造的組合同倫方程如下:

假設(shè)1(C1)?t ∈[0,1],Ω1(t)是非空有界的;

在[18]中,要求起始點w(0)∈Ω1(1)滿足h(w,1)=0,這導(dǎo)致找到該點非常困難.為了克服這個困難,根據(jù)公式(1)構(gòu)造一個新的同倫方程:

為方便起見,將H(θ,θ(0),t),表示為Hθ(0),同倫方程的解集用下式表示

下面來介紹幾種適用于同倫方法的引理.

定義1設(shè)U ∈Rn為開集,φ:U →Rp為Cα(α ＞max{0,n-p})映射.若值域=Rp,?x ∈φ-1(y),則y ∈Rp是φ的一個正則值.

引理1[19](參數(shù)化Sard定理) 設(shè)?Rn,?Rm為開集,φ:×→Rk為Cα(α ＞max{0,n-k})映射;若0∈Rk是φ的一個正則值,則對于幾乎所有的a ∈～V,0是φa=φ(a,·)的一個正則值.

引理2[20](逆像定理) 設(shè)φ:U ∈Rn →Rp是Cα(α ＞max{0,n-p})映射,若0是φ的正則值,則φ-1(0)包含若干(n-p)-維的光滑流形.

引理3[20](一維光滑流形分類定理) 一維光滑流形與單位圓或單位區(qū)間同胚.

假設(shè)2(A1)?t ∈[0,1],Ω0是非空的,?yF(x,y)和?yG(x,y)是凸函數(shù);

備注1對于(A1),由于G是凸函數(shù)以及U=diag(u),u ≥0,故若?yF(x,y)和?yG(x,y)是凸函數(shù),則h(w,t)必須是凸函數(shù).(A1)和(A6)可以保證BLPP的同倫方法在無界集上的收斂性.如果集合Ω是有界的,則可以忽略條件(A1)和(A6).并且(A5)可以確保BLPP的下層問題具有唯一的解.

備注2假設(shè)2(A6)是文獻(xiàn)中的常見條件,它比以下強(qiáng)制性條件弱.

定義2[22]令C為Rn的圓錐,F:C →Rn為連續(xù)映射.如果存在u ∈C使得

那么稱F滿足C中的強(qiáng)制性條件.假設(shè)2(A6)與以下條件一致.

證當(dāng)t=1時,同倫方程(2)變形為如下形式:

§3 主要結(jié)果

引理5Hθ(0)定義如(2)式,假設(shè)2(A1),(A6)成立,則對于幾乎所有

上式的第一個方程兩邊同乘上(w(k)-z),有

其中第一個不等式是通過g是凸函數(shù)和假設(shè)2(A1)或參考備注1得出的.根據(jù)(4)式,得到第二個不等式.最后一個不等式成立是由于k →∞,有(1-tk)(w(0))Tv(0)+(w(k)-z)T(w(k)-w(0))＞0,上面所得結(jié)論與假設(shè)2(A6)相矛盾.因此,θ的分量w是有界的.

引理7(同倫曲線的有界性) 若假設(shè)2成立,則對幾乎所有,v(0),λ(0)T∈Ω01,0是Hθ(0)的正則值,則Γθ(0)在Ω1×(0,1]上是一條有界曲線.

將兩邊同除以‖(v(k),λ(k))‖且令k →∞,得到{?～gi(w),i ∈I(w*),?wh(w,t)}是線性相關(guān)的,與假設(shè)2中的(A3) 相矛盾,所以{λ(k)}是有界序列.

與假設(shè)2(A3)相矛盾,所以{v(k)}是有界序列.

根據(jù)上述等式,若極限(1-tk)v(k)i趨于無窮大,則它與假設(shè)2(A3)相矛盾.若極限(1-tk)v(k)i存在,則與假設(shè)2(A4)相反.因此序列{v(k)}也有界.

是非奇異的,因此θ(0)=(w(0),v(0),λ(0))是Hθ(0)(θ(0),1)=0的唯一解.所以Γθ(0)不可能返回點(θ(0),1).根據(jù)引理3,Γθ(0)只微分同胚于(0,1].

令(θ*,t*)為Γθ(0)的一個收斂點,則對于點(θ*,t*)有下面三種情況可能成立:

§4 數(shù)值例子

本文用非內(nèi)點同倫方法求解雙層規(guī)劃問題時,主要用Euler-Newton算法[19]對同倫路徑進(jìn)行數(shù)值追蹤并得出最終解.Euler-Newton算法主要追蹤的是由同倫方程Hθ(0)(θ,t)=0確定的一條從(θ(0),1)出發(fā)的光滑曲線.對下面所有的數(shù)值例子,選取的精確度參數(shù)為:ε3=10-6,并且下面例題的約束區(qū)域的選擇都是非空閉凸集:Ω={(x,y)∈Rn+m:g(x,y)≤0,G(x,y)≤0}.結(jié)果如表所示,其中A1表示本文提出的新的同倫方程所產(chǎn)生的BLPP的同倫方法,A2代表文獻(xiàn)[18]中的BLPP的同倫方法,IT代表迭代次數(shù),CPU表示程序運行的時間,x(0),y(0)表示初始點,列表中所示前兩個點是選取所研究問題的內(nèi)點即Ω(t) 中的點,第三個點選取的是僅滿足不等式約束中的點即Ω0中的點,在以下示例中表明,對于方法A1,可以采用僅滿足不等式約束的初始點進(jìn)行測試,但是對于方法A2,必須采用初始內(nèi)部點進(jìn)行測試.(x*,y*)表示問題的近似解,t*表示算法終止時對應(yīng)的同倫參數(shù)的值.實驗結(jié)果見下表,數(shù)值結(jié)果表明了該方法的有效性.

例4.1[18]

表1 例4.1的兩種同倫方法結(jié)果比較

例4.2[24]

表2 例4.2的兩種同倫方法結(jié)果比較

例4.3[24]

表3 例4.3的兩種同倫方法結(jié)果比較

例4.4[25]

表4 例4.4的兩種同倫方法結(jié)果比較

例4.5[25]

表5 例4.5的兩種同倫方法結(jié)果比較

例4.6[25]例4.5中的r=0.1改為r=0.

表6 例4.6的兩種同倫方法結(jié)果比較

從上面的數(shù)值結(jié)果可以看出,本文所給出解BLPP的同倫方法不僅擴(kuò)大了初始點的選取范圍,而且計算效率也較原來的內(nèi)點同倫方法有很大的提高.