求解二次雙層規劃問題的全局最優解

徐俊彥,高瑩瑩,苗 壯,劉慶懷

(長春工業大學 基礎科學學院,長春 130012)

(P) min{H(w): h(w)≥0,w∈[a,b]}.

(P1) max{h(w): H(w)≤γ-ε,w∈[a,b]}.

求解二次雙層規劃問題的全局最優解

徐俊彥,高瑩瑩,苗 壯,劉慶懷

(長春工業大學 基礎科學學院,長春 130012)

針對現有的一些逼近算法在計算過程中有時得到的解為不可行解,甚至遠離真正全局最優解的問題,給出一種解二次雙層規劃非孤立全局最優解的算法.數值實例結果表明， 該算法行之有效.

全局優化； 二次雙層規劃； 非孤立最優解

0 引 言

雙層規劃問題(bilevel programming problems,BLPP)的一般形式為

其中:X?n1,Y?n2均為緊凸集;F:n1+n2→和f:n1+n2→分別稱為上層和下層目標函數,都是實值函數;G:n1+n2→m1,g:n1+n2→m2為向量實值函數;n1,n2,m1,m2∈.

Ω={x∈X,y∈Y:G(x,y)≥0,g(x,y)≥0}稱為約束域(或松弛可行集)；C(x)={y∈Y:g(x,y)≥0}稱為下層可行集(固定x)；M(x)={y∈Y:y∈argmin{f(x,y):y∈C(x)}}稱為下層合理反應集；IR={x∈X,y∈Y: (x,y)∈Ω,y∈M(x)}稱為誘導域.

文獻[1-4]給出了求BLPP的最優解問題.由于求BLPP的最優解問題較難,因此,目前的多數算法是求解其穩定點,而實際問題要求找到最優解.文獻[5-8]基于參數規劃理論和轉化技術給出了求解BLPP問題的一些算法.上述算法都是在各層函數均為凸函數情形下給出的.本文給出求解上層目標及約束函數為非凸的二次多項式雙層規劃問題最優解的算法,該算法融入了非孤立最優解的思想,克服了現有的一些逼近算法在計算過程中有時得到的解為不可行解,甚至遠離真正全局最優解的問題.

考慮如下二次雙層規劃問題(quadratic bilevel programming problems,QBLPP):

其中:x∈n1,y∈n2為優化變量;L6,l6,G6j∈,j=1,2,…,m1； (L1)n1×n1,(L2)n2×n1,(L3)n2×n2,(L4)1×n1,(L5)1×n2,(l1)n1×n1,(l2)n2×n1,(l3)n2×n2,(l4)1×n1,(l5)1×n2,(G1j)n1×n1,(G2j)n2×n1,(G3j)n2×n2,(G4j)1×n1,(G5j)1×n2(j=1,2,…,m1)和(g1)m2×n1,(g2)m2×n2,(g3)m2×1為實矩陣; 且(l3)n2×n2是對稱正定矩陣; (L3)n2×n2是對稱陣.

假設:

引理1[9]若對于每個x∈X,f和g都是關于y∈C(x)二次連續可微的,且f是關于y∈C(x)嚴格凸的,C(x)為凸緊集,則M(·)為實值連續閉的函數.

引理2[9]若引理1的假設成立,F為實值連續函數,X和由G(x,y)≥0定義的集合均為緊集,并且?x∈X,使得G(x,y(x))≥0,則問題(1)存在全局最優解.

1 二次雙層規劃問題的等價轉化

對下層問題,將x作為參數向量做如下變換:

則下層問題轉化為下列參數二次規劃問題：

根據引理1知下層問題可解.應用解參數二次規劃問題的算法[10]解式(4),可得x在不同區域的合理反應集為：

整理式(3),(5),并代入式(2)的上層得

其中:

從而二次雙層規劃問題(2)轉化為r個二次規劃問題(6),由引理2知問題(2)存在全局最優解.解問題(6)每個問題的最優解,其中的最小解即為問題(2)的最優解.

任意一個二次多項式函數都可分解為兩個正系數二次多項式函數之差,即

(P) min{H(w):h(w)≥0,w∈[a,b]}.

顯然,H(w)是遞增的二次函數,且所有系數均為正數； 而hj(w)可分解為兩個增函數uj(w)和vj(w)的差,即

2 主要結果

設w*是問題(P)的非孤立可行解,對問題(P)的任意非孤立可行解w,如果H(w*)=min{H(w):w∈S*},則稱w*是問題(P)的非孤立最優解,其中S*為問題(P)的所有非孤立可行解集.假設：

(H2) 集合{w∈[a,b]:h(w)>0}≠?.

(H3)H(a)<γ-ε,h(a)≤0.

為解問題(P),考慮下列輔助問題:

(P1) max{h(w):H(w)≤γ-ε,w∈[a,b]}.

由H(w)連續,且{w∈[a,b]:H(w)≤γ-ε}=cl{w∈(a,b):H(w)<γ-ε}知,問題(P1)是正則的； 由H(w)為連續增函數知,問題(P1)沒有孤立可行點,解問題(P1)比解問題(P)更簡單.下面給出問題(P)和問題(P1)的關系.用min(P)和max(P1)分別表示問題(P)和問題(P1)的最優值.

定理1假設(H1)～(H3)成立,則有:

1) 若w0是問題(P1)的任一可行解,h(w0)>0,則w0是問題(P)的一個非孤立可行解,且H(w0)≤γ-ε; 特別地,若max(P1)>0,則問題(P1)的最優點w′是問題(P)的非孤立可行解,且H(w′)≤γ-ε;

證明： 1)由h(a)≤00,因而w是問題(P)的可行解.又因為w0是問題(P1)的任一可行解,所以H(w0)≤γ-ε.故w0是問題(P)的一個非孤立可行解,且H(w0)≤γ-ε.

3 算法及其收斂性

1) 拆分可行集,設W=(Wj)n1+1=[a,b],Wj=[aj,bj],分支規則如下：

① 選擇W=W1×W2×…×Wn1+1的最長邊；

② 令Wj表示包含所選最長邊的矩形,ω表示該邊的中點；

2) 在不失當前任何可行解的情況下,對拆分集的尺度進行有效縮減.縮減操作是利用問題的單調結構所進行的特殊切割.在求解問題(P1)分支定界算法的給定階段,令W=[a,b]?X0是感興趣的拆分集.在集合Bγ∩[a,b]中尋找問題(P)的非孤立可行解,其中Bγ={w:H(w)≤γ-ε,uj(w)-vj(w)≥0,j=1,2,…,m1+1}.縮減操作的目的是用較小的矩形[a′,b′]?[a,b]代替[a,b],且使得Bγ∩[a′,b′]=Bγ∩[a,b].滿足這樣條件的矩形[a′,b′]記為red[a,b].設ei表示第i個分量是1、 其他分量全為0的向量.

下面給出求解問題(P)的算法.

6) 若V(P1)k≥ε,計算λk=max{α:H(ak+α(bk-ak))≤γ-ε},令wk=ak+λk(bk-ak).

定理2算法1在有限步迭代后終止,可得到問題(P)的ε-非孤立最優解,或證明問題(P)是不可行的.

得

而

矛盾.

例1

例1的轉化及計算結果列于表1.由表1可見,全局最小值點為

x1=0.75,x2=0.75,y1=0,y2=0,y3=1,

全局最小值為F=-1.875,f=4.25.表明本文算法有效、 可行,收斂于非孤立全局最優解.

表1 例1的計算結果Table 1 Computational results of example 1

[1]Chinchuluun A,Pardalos P M,HUANG Hongxuan.Multilevel (Hierarchical) Optimization: Complexity Issues,Optimality Conditions,Algorithms [C]//Advances in Applied Mathematics and Global Optimization in Honor of Gilbert Strang.Advances in Mechanics and Mathematics Series.Vol.17.Berlin: Springer,2009: 197-222.

[2]CAO Dong,CHEN Mingyuan.Capacitated Plant Selection in a Decentralized Manufacturing Environment: A Bilevel Optimization Approach [J].Eur J Oper Res,2006,169(1): 97-110.

[3]Tuy H,Migdalas A,Hoai-Phuong N T.A Novel Appraoach to Bilevel Nonlinear Programming [J].J Glob Optim,2007,38(4): 527-554.

[4]Tuy H,Hoai-Phuong N T.A Robust Algorithm for Quadratic Optimization under Quadratic Constraints [J].J Glob Optim,2007,37(4): 557-569.

[5]Faísca N P,Kouramas K I,Saraiva P M,et al.A Multi-parametric Programming Approach for Constrained Dynamic Programming Problems [J].Optimization Letters,2008,2(2): 267-280.

[6]Faísca N P,Saraiva P M,Rustem B,et al.A Multi-parametric Programming Approach for Multilevel Hierarchical and Decentralised Optimisation Problems [J].Computational Management Science,2009,6(4): 377-397.

[7]K?ppe M,Queyranne M,Ryan C T.Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs [J].J Optim Theory Appl,2010,146(1): 137-150.

[8]Dempe S,Mordukhovich B S,Zemkoho A B.Necessary Optimality Conditions in Pessimistic Bilevel Programming [J].Optimization,2014,63(4): 505-533.

[9]Vicente L.Bilevel Programming [D].Coimbra: University of Coimbra,1992.

[10]Dua V,Bozinis N A,Pistikopoulos E N.A Multiparametric Programming Approach for Mixed-Integer Quadratic Engineering Problems [J].Comput Chem Eng,2002,26(4/5): 715-733.

(責任編輯： 趙立芹)

GlobalOptimizationforQuadraticBilevelProgrammingProblem

XU Junyan,GAO Yingying,MIAO Zhuang,LIU Qinghuai
(SchoolofBasicScience,ChangchunUniversityofTechnology,Changchun130012,China)

A parametric algorithm was proposed for solving the nonisolated global optimal solution of quadratic bilevel programming problem in view of most existing approximate methods for solving these problems sometimes providing an infeasible solution,or a solution far from the ture optimum.The algorithm overcomes these limitations.Numerical results presented show the effectiveness of this method.

global optimization; quadratic bilevel programming; nonisolated optimal solution

2013-12-02.

徐俊彥(1964—),女,漢族,碩士,副教授,從事最優化理論與算法的研究,E-mail: Xujunyan1964@126.com.通信作者： 劉慶懷(1961—),男,漢族,博士,教授,從事最優化理論與算法的研究,E-mail:liuqh6195@126.com.

國家自然科學基金(批準號： 10771020)和吉林省自然科學基金(批準號： 20101597).

O224

A

1671-5489(2014)05-0937-06