求解二次雙層規(guī)劃問題的全局最優(yōu)解

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

(長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院,長春 130012)

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

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

求解二次雙層規(guī)劃問題的全局最優(yōu)解

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

(長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院,長春 130012)

針對現(xiàn)有的一些逼近算法在計(jì)算過程中有時(shí)得到的解為不可行解,甚至遠(yuǎn)離真正全局最優(yōu)解的問題,給出一種解二次雙層規(guī)劃非孤立全局最優(yōu)解的算法.數(shù)值實(shí)例結(jié)果表明， 該算法行之有效.

全局優(yōu)化； 二次雙層規(guī)劃； 非孤立最優(yōu)解

0 引 言

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

其中:X?n1,Y?n2均為緊凸集;F:n1+n2→和f:n1+n2→分別稱為上層和下層目標(biāo)函數(shù),都是實(shí)值函數(shù);G:n1+n2→m1,g:n1+n2→m2為向量實(shí)值函數(shù);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)}}稱為下層合理反應(yīng)集；IR={x∈X,y∈Y: (x,y)∈Ω,y∈M(x)}稱為誘導(dǎo)域.

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

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

其中:x∈n1,y∈n2為優(yōu)化變量;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為實(shí)矩陣; 且(l3)n2×n2是對稱正定矩陣; (L3)n2×n2是對稱陣.

假設(shè):

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

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

1 二次雙層規(guī)劃問題的等價(jià)轉(zhuǎn)化

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

則下層問題轉(zhuǎn)化為下列參數(shù)二次規(guī)劃問題：

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

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

其中:

從而二次雙層規(guī)劃問題(2)轉(zhuǎn)化為r個(gè)二次規(guī)劃問題(6),由引理2知問題(2)存在全局最優(yōu)解.解問題(6)每個(gè)問題的最優(yōu)解,其中的最小解即為問題(2)的最優(yōu)解.

任意一個(gè)二次多項(xiàng)式函數(shù)都可分解為兩個(gè)正系數(shù)二次多項(xiàng)式函數(shù)之差,即

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

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

2 主要結(jié)果

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

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

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

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

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

3 算法及其收斂性

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

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

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

2) 在不失當(dāng)前任何可行解的情況下,對拆分集的尺度進(jìn)行有效縮減.縮減操作是利用問題的單調(diào)結(jié)構(gòu)所進(jìn)行的特殊切割.在求解問題(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].設(shè)ei表示第i個(gè)分量是1、 其他分量全為0的向量.

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

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

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

得

而

矛盾.

例1

例1的轉(zhuǎn)化及計(jì)算結(jié)果列于表1.由表1可見,全局最小值點(diǎn)為

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

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

表1 例1的計(jì)算結(jié)果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.

(責(zé)任編輯： 趙立芹)

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—),女,漢族,碩士,副教授,從事最優(yōu)化理論與算法的研究,E-mail: Xujunyan1964@126.com.通信作者： 劉慶懷(1961—),男,漢族,博士,教授,從事最優(yōu)化理論與算法的研究,E-mail:liuqh6195@126.com.

國家自然科學(xué)基金(批準(zhǔn)號(hào)： 10771020)和吉林省自然科學(xué)基金(批準(zhǔn)號(hào)： 20101597).

O224

A

1671-5489(2014)05-0937-06