三步法求解下層最優(yōu)解不唯一的二層規(guī)劃

王　劍　胡鐵松　汪　琴

(武漢大學 水資源與水電工程科學國家重點實驗室， 武漢　430072)

?

三步法求解下層最優(yōu)解不唯一的二層規(guī)劃

王劍胡鐵松汪琴

(武漢大學 水資源與水電工程科學國家重點實驗室， 武漢430072)

摘要：下層最優(yōu)解不唯一的二層規(guī)劃存在樂觀和悲觀情形，基于此提出樂觀和悲觀可行解的定義，并設(shè)計了求解樂觀和悲觀最優(yōu)解的三步法．而后分別用三步法和以往的兩步法求解了4個下層最優(yōu)解不唯一和1個下層最優(yōu)解唯一的算例，計算結(jié)果表明了三步法的有效性．

關(guān)鍵詞：二層規(guī)劃；樂觀最優(yōu)解；悲觀最優(yōu)解

二層規(guī)劃可行上層決策對應(yīng)的下層規(guī)劃問題最優(yōu)解數(shù)目通常并非唯一，二層規(guī)劃的下層問題具有唯一解是一類特殊二層規(guī)劃問題，只有當對應(yīng)下層規(guī)劃為凸規(guī)劃且目標函數(shù)為嚴格凸函數(shù)時，其最優(yōu)解才唯一[1]．下層規(guī)劃最優(yōu)解不唯一的二層規(guī)劃的求解難點在于：對于一個可行的上層決策變量，其對應(yīng)下層最優(yōu)解的數(shù)目難以確定，目前尚缺乏一種解法可以求解出下層問題的所有最優(yōu)解并將其反饋到上層規(guī)劃．因此，研究與探討下層最優(yōu)解不唯一的二層規(guī)劃問題具有重要價值．

下層最優(yōu)解不唯一的二層規(guī)劃的最優(yōu)解尚無一個公認的定義，Lucchetti R, Mignanego F等[2]提出了三個定義，其中第一條和第二條定義分別對應(yīng)Dempe[3]提到的樂觀和悲觀形式二層規(guī)劃的最優(yōu)解，也是較為通用的解定義，而第三條定義條件非常嚴苛，因而使用得極少．另外有一些學者，通過對原二層規(guī)劃問題進行處理，使得下層問題最優(yōu)解唯一．Bialas和Karwan[4]提出在下層決策者配合上層決策者時，用f2+εf1來代替下層目標函數(shù)f2，其中f1為上層目標函數(shù)，ε為一個適當小的正數(shù)；相應(yīng)地Ben-Ayed O[5]提出在下層決策者不配合上層決策者時，用f2-εf1來代替下層目標函數(shù)f2．但兩者只是提出了一種思路，并沒有指出ε應(yīng)當如何選取，并且即使在替換了下層目標函數(shù)以后，也不能保證下層最優(yōu)解唯一．Dempe則提出了兩種正則化方法對原二層規(guī)劃進行擾動，第一種[6]是針對樂觀情形，在下層目標函數(shù)為凸函數(shù)，且上層目標函數(shù)正定的情況下，在下層目標函數(shù)中添加αF，α為一個適當小的正數(shù)，并用梯度法進行求解；第二種[7]是在下層規(guī)劃為凸規(guī)劃時，在目標函數(shù)中添加α‖x‖，并用聚束法進行求解．相類似地，P.Loridan和J.Morgan針對下層問題嚴格擬凸與否，提出了兩種ε-正則法[8-9]，并討論了一定條件下解的存在問題，也提出了幾個較為簡單的算法．但不論是Dempe還是P.Loridan和J.Morgan提出的方法都存在兩個問題：第一，對下層問題有一定的要求，針對的是較為簡單的二層規(guī)劃問題，提出的方法難以解決一個一般的下層最優(yōu)解不唯一的二層規(guī)劃問題；第二，改變了原二層規(guī)劃問題，并不能保證最后求得的解滿足下層問題的最優(yōu)性．

近年來有一類解法，上下層都采用啟發(fā)式算法進行求解，因為該類算法使用了兩次啟發(fā)式算法，可以歸類為兩步法，如基于遺傳算法的[10]，基于粒子群算法的[11]等．但用兩步法求解下層最優(yōu)解不唯一的二層規(guī)劃，下層規(guī)劃將隨機返回一個最優(yōu)解到上層，因而算法結(jié)果將不穩(wěn)定，無法保證求得樂觀最優(yōu)解或者悲觀最優(yōu)解．

本文從樂觀和悲觀二層規(guī)劃的定義出發(fā)，提出樂觀和悲觀可行解的定義，分析了這兩類可行解的求解思路，而后設(shè)計了三步法求解下層最優(yōu)解不唯一的二層規(guī)劃的樂觀和悲觀最優(yōu)解．下文將按照如下順序展開：第1部分描述二層規(guī)劃的相關(guān)數(shù)學定義及樂觀和悲觀最優(yōu)解，第2部分提出樂觀和悲觀可行解的定義和求解樂觀和悲觀最優(yōu)解的三步法，第3部分是算例及結(jié)果分析，第4部分是結(jié)論和未來工作．

1二層規(guī)劃的兩類最優(yōu)解

考慮如下形式的二層規(guī)劃問題(記為問題1)：

(1)

其中x∈Rn1，y∈Rn2，F(xiàn)，f：Rn1×Rn2→R，G：Rn1×Rn2→Rm1，g：Rn1×Rn2→Rm2.

1)約束域：

上下層約束條件的交集稱為約束域A，即：A={(x，y)|G(x，y)≤0，g(x，y)≤0}.

2)可行上層決策變量：

將滿足x∈A的上層決策變量x稱為可行上層決策變量，所有的可行上層決策變量的集合用X表示，它表示約束域A在上層決策空間的投影，即：X={x|(x，y)∈A}.

3)反應(yīng)集：

當二層規(guī)劃的可行上層決策變量x，對應(yīng)的下層問題的最優(yōu)解并非唯一時，下層問題返回的最優(yōu)解具有不確定性．此時，有兩種決策方式，相應(yīng)地有兩類最優(yōu)解．

1.1樂觀最優(yōu)解

樂觀決策者認為下層完全配合上層目標，總是將對上層目標最有利的最優(yōu)解返回給上層，這種情況下的二層規(guī)劃稱為樂觀二層規(guī)劃，得到的最優(yōu)解即為樂觀最優(yōu)解．

樂觀二層規(guī)劃的數(shù)學表達[3]：

(2)

1.2悲觀最優(yōu)解

P.Loridan和J.Morgan[12]提出在下層決策者不配合上層決策者時，上層決策者為了使得風險最小，認為下層決策者總是選擇最不利于上層的最優(yōu)解，這種情形下的二層規(guī)劃稱為悲觀二層規(guī)劃，得到的最優(yōu)解即為悲觀最優(yōu)解．

悲觀二層規(guī)劃的數(shù)學表達[3]：

(4)

2三步法求解樂觀和悲觀最優(yōu)解

2.1等價約束

對于任意一個固定的上層決策變量x，如果下層問題存在最優(yōu)解，那么下層問題一定存在唯一的最優(yōu)值f*，顯然，對于任意一個x′∈X有：{y|f(x′，y)=f*}={y|y∈ψ(x′)}．

2.2樂觀可行解

根據(jù)樂觀二層規(guī)劃的定義，對于一個x′∈X，當y是如下問題o的最優(yōu)解時，這個y才會被樂觀上層決策者接受，從而(x′，y)才是樂觀二層規(guī)劃的一個可行解，稱為樂觀可行解．

(7)

由于ψ(x′)數(shù)目無法確定，也無法全部求出，故用f(x′，y)=f*代替y∈ψ(x′)可以得到問題o的等價問題3：

(8)

2.3悲觀可行解

同理，根據(jù)悲觀二層規(guī)劃的定義，對于一個x′∈X，當y是如下問題p的最優(yōu)解時，(x′，y)是悲觀二層規(guī)劃的一個可行解，稱為悲觀可行解．

(9)

與樂觀可行解求解類似，可以得到問題p的等價問題4：

(10)

2.4樂觀&悲觀可行解求解

根據(jù)上文的分析，可以通過如下3個步驟求解樂觀和悲觀可行解：第1步，確定一個滿足x′∈X的x′；第2步，求解x′對應(yīng)下層規(guī)劃問題2的最優(yōu)值f*；第3步，求解x′對應(yīng)的問題3(4)，得到最優(yōu)解y，最終得到一個樂觀(悲觀)可行解(x′，y)．

2.5三步法求解樂觀&悲觀最優(yōu)解

上文給出了求解單個樂觀(悲觀)可行解的方法，如果使上層決策變量在X內(nèi)變化，并求解對應(yīng)的樂觀(悲觀)可行解，最后比較這些樂觀(悲觀)可行解的適應(yīng)度(上層目標函數(shù)值)大小，適應(yīng)度最小的樂觀(悲觀)可行解就是原二層規(guī)劃問題的樂觀(悲觀)最優(yōu)解，具體過程如圖1所示．

圖1　三步法運行過程　　　　圖2　兩步法迭代過程

2.6三步法和兩步法對比

新方法是一個求解策略，并不針對某一種特定的算法，為了使得算法適用性更廣，可以采用啟發(fā)式算法和新方法結(jié)合．新方法總共使用了3次啟發(fā)式算法，故而命名為三步法．為了方便對比，將兩步法的流程列入圖2，可以看出三步法和兩步法差別就在于是否有問題3(4)的求解，且兩步法在下層問題完成求解后直接返回了下層最優(yōu)解Y*，三步法返回的是下層最優(yōu)值f*，再經(jīng)過問題3(4)的求解返回Y*．

3算例及結(jié)果

為了驗證新方法的有效性，下面分別用基于粒子群的兩步法和三步法對5個算例進行求解．算例1，2，3節(jié)選自文獻，算例4，5為作者構(gòu)造算例；算例1，2，4，5下層最優(yōu)解不唯一，算例3下層最優(yōu)解唯一；算例4，5決策變量維數(shù)可變，計算時算例4包括1+2和2+3維，算例5包括2+2維和4+4維．為了方便對比，三步法和兩步法的問題1和問題2的的粒子數(shù)和迭代次數(shù)均相同．

算例1[3]：

圖3　算例1可行域　　　　圖4　算例1迭代過程

3種迭代都進行了多次計算，樂觀和悲觀迭代過程不盡相同，但收斂結(jié)果一致，上圖只是選取了其中一次；兩步法的迭代過程不盡相同，迭代也不一樣，上圖也只是選取了其中一次(下文算例同)．樂觀過程收斂代數(shù)為51，收斂最優(yōu)解為(-1.62e-23，2.22e-24)，最優(yōu)值為0；悲觀過程收斂代數(shù)為176，收斂最優(yōu)解為(2.66e-04，1.003 11)，最優(yōu)值為1.000 091；兩步法收斂代數(shù)為146代，收斂最優(yōu)解為(4.02e-09，-1)，最優(yōu)值為1．三步法順利求解了樂觀最優(yōu)解和悲觀最優(yōu)解，而兩步法也剛好求解出了悲觀最優(yōu)解，這是一個特例．

算例2[2]：

算例2反應(yīng)集為：ψ(x)={(y1，y2)|y1+y2=1，x+y1-y2≤1，0≤x≤2}，可行域如圖5所示，任意一個x對應(yīng)下層規(guī)劃有無窮多個最優(yōu)解．

樂觀最優(yōu)解為：(x*，y*)=(0，1)，對應(yīng)樂觀最優(yōu)值為1 000；悲觀最優(yōu)解為：(x*，y*)=(2，0)，對應(yīng)悲觀最優(yōu)值為200．三步法和兩步法的迭代過程如圖6所示．

圖5　例2可行域　　　　　　圖6　例2迭代過程

樂觀過程收斂代數(shù)為130，收斂最優(yōu)解為(-1.56e-03，1.001 06，-5.04e-04)，最優(yōu)值為1 000.870；悲觀過程收斂代數(shù)為126，收斂最優(yōu)解為(2.000 03，-2.94e-04，1.003 45)，最優(yōu)值為199.699 6；兩步法收斂代數(shù)為68代，收斂最優(yōu)解為(0.203 076 1，0.895 614 0，0.104 396)，最優(yōu)值為829.162 5．三步法分別求解了樂觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

算例3[13]：

圖7　算例3迭代過程

樂觀過程收斂代數(shù)為200，收斂最優(yōu)解為(-1.11e-03，29.995 2，-10.000 1，9.997 54)，最優(yōu)值為-2.934e-03；悲觀過程收斂代數(shù)為198，收斂最優(yōu)解為(-1.18e-03，29.995 5，-10.000 1，9.997 66)，最優(yōu)值為-2.658e-03；兩步法收斂代數(shù)為149代，收斂最優(yōu)解為(-1.07e-03，29.995 2，-10.000 1，9.997 56)，最優(yōu)值為-3.038e-03．3種迭代過程大同小異，收斂的最優(yōu)解和最優(yōu)值都較為接近，3種迭代運算應(yīng)該還有繼續(xù)收斂到更優(yōu)解的可能，但最優(yōu)解和最優(yōu)解的精度已經(jīng)很高．

算例4：

s.t.0≤xi≤4

yj≥0

算例4的反應(yīng)集為：

對于任意一個可行上層決策變量，下層最優(yōu)解均為無窮多個．樂觀最優(yōu)解為：

樂觀最優(yōu)值為0，悲觀最優(yōu)解為：

圖8　算例4迭代過程(左邊1+2維，右邊2+3維)

對于1+2維：樂觀過程收斂代數(shù)為105，收斂最優(yōu)解為(0，4.88e-04，4)，最優(yōu)值為2.387e-04；悲觀過程收斂代數(shù)為39，收斂最優(yōu)解為(2.001 68，1.998 83，3.08e-08)，最優(yōu)值為8.002 304；兩步法收斂代數(shù)為132代，收斂最優(yōu)解為(0.519 99，0，3.480 51)，最優(yōu)值為0.270 642 1．三步法分別求解了樂觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

對于2+3維：樂觀過程收斂代數(shù)為48，收斂最優(yōu)解為(0，0，3.50e-03，0，3.996 97)，最優(yōu)值為2.366e-04；悲觀過程收斂代數(shù)為199，收斂最優(yōu)解為(1.362 97，1.310 36，1.327 18，2.63e-08，0)，最優(yōu)值為5.336 414；兩步法收斂代數(shù)為195代，收斂最優(yōu)解為(0.494 50，0.273 02，0，6.046 59e-02，3.172 52)，最優(yōu)值為0.322 986 4．3種迭代運算應(yīng)該還有繼續(xù)收斂到更優(yōu)解的可能，但最優(yōu)解和最優(yōu)值的精度已經(jīng)很高，可以認為三步法分別求解了樂觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

算例5：

算例5的反應(yīng)集為：

圖9　算例5迭代過程(左邊是2+2維，右邊是4+4維)

對于2+2維：樂觀過程收斂代數(shù)為189，收斂最優(yōu)解為(1.05e-08，-3.20e-10，1.01e-08，-8.76e-10)，最優(yōu)值為2.125e-016；悲觀過程收斂代數(shù)為6，收斂最優(yōu)解為(1，-1，-11.056 0，11.056 0)，最優(yōu)值為246.471 4；兩步法收斂代數(shù)為132代，收斂最優(yōu)解為(0.421 2，1，0.435 6，1.570 8)，最優(yōu)值為3.835 109．三步法分別求解了樂觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

對于4+4維：樂觀收斂代數(shù)為144代，收斂最優(yōu)解(3.31e-10，3.57e-10，1.20e-08，4.80e-12，4.19e-09，-3.39e-08，2.89e-09，-4.73e-09)，最優(yōu)值為1.342e-15；悲觀過程收斂代數(shù)為35，收斂最優(yōu)解為(1，-1，1，1-11.056 1，11.560 4，-11.056 1，-11.056 0)，最優(yōu)值為492.945 5；兩步法收斂代數(shù)為89代，收斂最優(yōu)解為(0.799 921 9，0.497 671 3，-0.978 888 6，1.000 000，-4.068 758，-5.762 273，-1.364 951，1.570 795)，最優(yōu)值為56.934 84．三步法分別求解了樂觀最優(yōu)解和悲觀最優(yōu)解，而兩步法求解不了樂觀最優(yōu)解和悲觀最優(yōu)解的任意一種．

4結(jié)論

上述5個不同類型的算例的計算結(jié)果，不僅證明了三步法對于下層最優(yōu)解不唯一的二層規(guī)劃的適用性，也證明了對于下層最優(yōu)解唯一的二層規(guī)劃，三步法同樣能有效地求解出其最優(yōu)解，從而三步法對于二層規(guī)劃具有普遍適用性．

由于三步法中多次進行了單層求解運算，運算時間相對較長．未來將致力于解決三步法的運算時間問題，并且將三步法運用于實際二層規(guī)劃當中．

參考文獻：

[1]運籌學教學編寫組．運籌學[M]．北京：清華大學出版社，2005：143．

[2]Lucchetti R， Mignanego F， Pieri G. Existence Theorems of Equilibrium Points in Stackelberg[J]． Optimization, 1987, 18(6)：857-866．

[3]Dempe S. Foundations of Bilevel Programming[M]． Springer Science & Business Media, 2002．

[4]Bialas W F, Karwan M H. Two-level Linear Programming[J]． Management Science, 1984, 30(8)：1004-1020．

[5]Ben-Ayed O. Bilevel Linear Programming[J]． Computers & Operations Research, 1993, 20(5)：485-501．

[6]Dempe S, Schmidt H. On an Algorithm Solving Two-level Program Ming Problems with Nonunique Lower Level Solutions[J]． Computational Optimization and Applications, 1996, 6(3)：227-249．

[7]Dempe S. A bundle Algorithm Applied to Bilevel Programming Problems with Non-unique Lower Level Solutions[J]． Computational Optimization and Applications, 2000, 15(2)：145-166．

[8]Loridan P, Morgan J. ε-regularized Two-level Optimization Problems：Approximation and Existence Results[M]//Optimization. Springer Berlin Heidelberg, 1989：99-113．

[9]Loridan P, Morgan J. On Strict ε-solutions for a Two-level Optimization Problem[C]//Papers of the 19th Annual Meeting/Vortr?ge der 19. Jahrestagung. Springer Berlin Heidelberg, 1992：165-172．

[10] Sinha A, Malo P, Deb K. Test Problem Construction for Single-objective Bilevel Optimization[J]． Evolutionary Computation, 2014, 22(3)：439-477．

[11] Gao Y, Zhang G, Lu J, et al. Particle Swarm Optimization for Bi-level Pricing Problems in Supply Chains[J]． Journal of Global Optimization, 2011, 51(2)：245-254．

[12] Loridan P, Morgan J. Approximate Solutions for Two-level Optimization Problems[M]． Birkh?user Basel, 1988．

[13] Aiyoshi E, Shimizu K. A Solution Method for the Static Constrained Stackelberg Problem Via Penalty Method[J]． Automatic Control, IEEE Transactions on, 1984, 29(12)：1111-1114．

[責任編輯王康平]

收稿日期：2015-11-05

基金項目：國家自然科學基金(51479142,51339004)，湖北省水利重點科研項目(HBSLKL201304)，湖北水利科研項目(HBSLKY201401)

通信作者：胡鐵松(1964-)，男，教授，主要研究方向為運籌學．E-mail：tshu@whu.edu.cn

DOI：10.13393/j.cnki.issn.1672-948X.2016.02.023

中圖分類號：O224

文獻標識碼：A

文章編號：1672-948X(2016)02-0102-06

Three-step Method for Solving Bilevel Programming with Non-unique Lower Level Optimal Solutions

Wang JianHu TiesongWang Qin

(State Key Laboratory of Water Resources & Hydropower Engineering Science, Wuhan Univ., Wuhan 430072, China)

AbstractBased on optimistic and pessimistic bilevel programming with non-unique lower level optimal solutions, the definitions of optimistic and pessimistic feasible solution is proposed, three-step method for solving bilevel programming with non-unique lower level optimal solutions is also proposed. Finally, the proposed three-step method and two-step method proposed before have been applied to 5 benchmark problems. The numerical results demonstrate the feasibility and effectiveness of three-step method.

Keywordsbilevel programming;optimistic optimal solution;pessimistic optimal solution