一類線性半向量二層規(guī)劃問題全局最優(yōu)解的搜索算法

王 媛，呂博慧，呂一兵*

(1.長江大學(xué) 信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023； 2.中央電視臺財經(jīng)頻道，北京 100020)

0 引言

近年來，二層規(guī)劃在工程設(shè)計、交通、管理等領(lǐng)域應(yīng)用廣泛[1-3]，并且其研究價值也越來越高[4-5].半向量二層規(guī)劃是上層為標(biāo)量優(yōu)化，下層為向量優(yōu)化的一類二層規(guī)劃問題[6].

對于線性半向量二層規(guī)劃問題， Lü Y B等[7]采用下層問題的最優(yōu)值轉(zhuǎn)化方法設(shè)計了原問題近似最優(yōu)解的算法；隨后，呂一兵等[8]以下層問題的對偶間隙為罰項，構(gòu)造了原問題的罰問題，并設(shè)計了相應(yīng)的罰函數(shù)算法.對于非線性半向量二層規(guī)劃問題， Ren A H等[9]在Benson方法和線性規(guī)劃對偶理論的基礎(chǔ)上，將原問題轉(zhuǎn)化為單層問題進(jìn)而設(shè)計了罰函數(shù)算法；Dempe S等[10]采用最優(yōu)值轉(zhuǎn)化方法將原問題轉(zhuǎn)化為二層單目標(biāo)規(guī)劃問題，同時基于非光滑優(yōu)化問題的最優(yōu)性條件[11-13]得到了原問題最優(yōu)解的一階必要性條件，然而遺憾的是文獻(xiàn)[10]并沒有給出數(shù)值算法；Gadhi N等[14]由非光滑Mangasarian-Fromowitz約束規(guī)格給出了等價的單層優(yōu)化問題，進(jìn)而得到了原問題的最優(yōu)性條件.

一般而言，在半向量二層規(guī)劃問題中，對于給定的上層決策變量，其下層問題往往有多個最優(yōu)解.在本文采用樂觀最優(yōu)解[15]，其數(shù)學(xué)模型可以表述為：

(1)

在問題(1)中，下層問題為:

(2)

在接下來的內(nèi)容中，將設(shè)計問題(1)的極點(diǎn)搜索算法[16].其基本思路是首先采用標(biāo)量化方法將問題(1)轉(zhuǎn)化為一般的二層規(guī)劃問題，通過對偶原理給出問題(2)的最優(yōu)性條件；然后用該條件代替問題(2)，進(jìn)而將原問題轉(zhuǎn)化為單層規(guī)劃問題；隨后基于所得到的單層規(guī)劃問題可行域的基本性質(zhì)，建立可行域頂點(diǎn)與最優(yōu)解之間的關(guān)系，并給出相應(yīng)的頂點(diǎn)搜索算法，最后給出算例來驗(yàn)證所設(shè)計算法.

1 相關(guān)定義及理論結(jié)果

S={(x,y)|Ax+By≤b,x≥0,y≥0}表示問題(1)的容許集，Πy={x∈Rn|?y∈Rm,Ax+By≤b,x≥0,y≥0}表示S在上層決策空間中的投影.在上層決策變量x給定的情況下，S(x)表示下層問題(2)的弱有效解集.

定義1 如果(x,y)∈IR={(x,y)|(x,y)∈S,y∈S(x)}，那么(x,y)為問題(1)的可行解.

定義2 (x*,y*)∈IR為問題(1)的全局最優(yōu)解，若對任意(x,y)∈IR，有:

C1x+C2y≤C1x*+C2y*.

在之后的內(nèi)容中，假設(shè)以下條件成立.

(A)問題(1)的容許集S為非空緊集.

(3)

給定(x,λ)∈Πy×Ω ，ψ(x,λ) 表示問題(3)的最優(yōu)解集.下面給出問題(2)的最優(yōu)解集與問題(3)的最優(yōu)解集之間的關(guān)系[14].

命題1[8]假設(shè)條件(A)滿足，則有:S(x)=ψ(x,Ω)=∪{ψ(x,Ω)|λ∈Ω)}.

由命題1就能將問題(1)轉(zhuǎn)化為如下問題，

(4)

定義5 問題(4)的全局最優(yōu)解為(x*,λ*,y*)∈IR1，如果對任意(x,λ,y)∈IR1有C1x+C2y≤C1x*+C2y*.

定理1 存在ω≥0,ω∈Rp，使得:

ωTB=λTD,

(5)

ωT(Ax+By-b)=0.

(6)

是S1中的點(diǎn)(x,λ,y)為可行點(diǎn)(即(x,λ,y)∈IR1)的充分必要條件.

證明給定可行的x>0,λ>0，下層問題為，

則可以得出問題(P)的對偶問題為，

必要性 假設(shè)(x,λ,y)∈IR1，對于x>0,λ>0，y為問題(P)的最優(yōu)解，由對偶原理可得，問題(D)存在最優(yōu)解ω≥0，滿足ωTB=λTD和ωT(b-Ax)=λTDy，就有ωTBy=λTDy=ωT(b-Ax)，即ωT(Ax+By-b)=0，必要性得證.

充分性 如果存在ω≥0，式(5)和式(6)成立，則ω是(D)的可行解.因?yàn)?x,λ,y)∈S1，則(P)的可行解是x,λ,y，由弱對偶性可得ωT(b-Ax)≥λTDy=ωTBy，綜合式(6)，可知上式取等式，可以得到y(tǒng)和ω分別是問題(D)和(P)的最優(yōu)解，那么就使得(x,λ,y)∈IR1，因此就證明了該條件的充分性.

推論1 存在ω>0，ω∈Rp，使得:

是S1中的點(diǎn)(x,λ,y)為可行點(diǎn)的必要條件.

推論2 存在ω*≥0,使得(x*,λ*,y*,ω*)為下列問題的最優(yōu)解，

(7)

是(x*,λ*,y*)為問題(4)最優(yōu)解的充要條件.

定理2 問題(4)的可行集IR1是容許集S1的弱擬凸子集.

證明設(shè)(x1,λ1,y1)∈S1,(x2,λ2,y2)∈S1且有α,0≤α≤1,使得(x,λ,y)=α(x1,λ1,y1)+(1-α)(x2,λ2,y2)∈IR1.通過定理1，存在ω∈Rp,ω≥0,使得：

ωTB=λTD,ωT(Ax+By-b)=αωT(Ax1+By1-b)+(1-α)ωT(Ax2+By2-b)=0.

(8)

因?yàn)?x1,λ1,y1)∈S1，(x2,λ2,y2)∈S1，則：b-Ax1-By1≥0，b-Ax2-By2≥0.

于是：

ωT(Ax1+By1-b)=0 ，ωT(Ax2+By2-b)=0.

(9)

由式(7)有ωTB≥α(λ1)TD,(ωTB)i≥α[(λ1)TD]i,故存在βi，0≤βi≤1，使得βi(ωTB)i=α[(λ1)TD]i,i=1,2,…,m.令：

則βωTB=α(λ1)TD.記βωT=α(ω1)T,則：

ω1≥0,α(ω1)TB=α(λ1)TD.

(10)

于是有：ωT-α(ω1)T=ωT-βωT=(E-β)ωT≥0.(E為單位矩陣).

令(1-α)(ω2)T=ωT-α(ω1)T,則：

ω2≥0，ωT=α(ω1)T+(1-α)(ω2)T.

(11)

由式(7)、(9)、(10)得：

α((ω1)TB-(λ1)TD)+(1-α)((ω2)TB-(λ2)TD)=0,(ω1)TB-(λ1)TD=0.

故有(ω2)TB=(λ2)TD，將式(10)帶入式(8)得：

(ω1)T(Ax1+By1-b)=0 ，(ω2)T(Ax2+By2-b)=0.

通過定理1，(x1,λ1,y1)∈IR1(x2,λ2,y2)∈IR1，則IR1是弱擬凸子集.

注2 定理2可以推出S1的若干個面組成了IR1.

為了描述的方便，給出如下定義：

于是:

推論3IR1的極點(diǎn)必是S1的極點(diǎn).

推論4S1的一個極點(diǎn)必定是最優(yōu)解，如果問題(1)存在最優(yōu)解.

注3 通過推論4可以得到，如果原問題最優(yōu)解，并且S1的極點(diǎn)是有限的，那么只要檢驗(yàn)這有限個極點(diǎn)是否可行，最終可以推演得出可行極點(diǎn)的最小值，那么就能找到問題(1)的最優(yōu)解.

定理4 問題(1)的可行集IR1是連通的.

注4 通過IR1的連通性，可以知道如果我們使用搜索算法尋找問題(1)的極最優(yōu)解的時候，只需要搜索IR1相鄰的極點(diǎn)就行.

2 算法

根據(jù)以上性質(zhì)，設(shè)計出了下列求解問題(1)的算法.

第1步 寫出ω的基解:

注5 由定理1可以得到問題(4)的可行解的充要條件，根據(jù)該原理，就需要求出式(5)的非基礎(chǔ)解系(ω1，ω2，…，ωp).

第2步 在給定充分大的正數(shù)α的條件下，求解如下的規(guī)劃問題，

若(LPi)的可行集非空，則其最優(yōu)值就是Fi；若(LPi)的可行集是空集，則Fi=-；其中i=1,2,…,p.

注6 對于每個ωi，第2步就可以得到(6)的基可行解(xl1,λl1,yl1),(xl2,λl2,yl2)，…,(xlp,λlp,ylp)，那么問題的可行極點(diǎn)就是該基可行解.

第3步 若max{F1,F2,…,Fm}=F(xk,λk,yk)，則(xk,λk,yk)為問題(1)的最優(yōu)解.

3 數(shù)值結(jié)果

為了驗(yàn)證算法的可行、有效性，考慮如下半向量二層規(guī)劃問題.

例1 考慮如下問題，其中x∈R3,y∈R3.

-x1-2x2-18x3-3y1-9y2-8y3)

s.t. 15x1-7x2+3x3+2y1-7y2+3y3≤200，7x1+7x2+6x3+y1+13y2+y3≤140，

2x1+2x2-x3+14y1+2y2+2y3≤240，-3x1+6x2+12x3+4y1-8y2+y3≤140，

4x1-7x2+7x3+2y1+4y2-7y3≤45，4x1+5x2+x3-7y1-6y2+y3≤800，

x1,x2,x3≥0,y1,y2,y3≥0.

將其轉(zhuǎn)化為如下形式:

λ3(x1+2x2+18x3+3y1+9y2+8y3)

s.t. 15x1-7x2+3x3+2y1-7y2+3y3≤200，7x1+7x2+6x3+y1+13y2+y3≤140，

2x1+2x2-x3+14y1+2y2+2y3≤240，-3x1+6x2+12x3+4y1-8y2+y3≤140，

4x1-7x2+7x3+2y1+4y2-7y3≤45，4x1+5x2+x3-7y1-6y2+y3≤800，

x1,x2,x3≥0,y1,y2,y3≥0.

首先,得到矩陣：

運(yùn)用算法求解，即:

第1步

(ω1)T=(1，0，0，0，0，0),(ω2)T=(0,1，0，0，0，0),(ω3)T=(0，0，1，0，0，0)，

(ω4)T=(0，0，0，0，1，0),(ω5)T=(0，0，0，0，0，1)，(ω6)T=(0，0，0，0，0，1).

第2步

α(ω1)TB=(2α，-7α，3α)≥(4λ1+4λ2+3λ3,7λ1+2λ2+9λ3,7λ1+4λ2+8λ3).

是不成立的，令F1=-.

α(ω2)TB=(α，13α,α)≥(4λ1+4λ2+3λ3,7λ1+2λ2+9λ3,7λ1+4λ2+8λ3)

x1+7x2+6x3+y1+13y2+y3=140，5x1-7x2+3x3+2y1-7y2+3y3≤200，

x1+7x2+6x3+y1+13y2+y3≤140，2x1+2x2-x3+14y1+2y2+2y3≤240，

-3x1+6x2+12x3+4y1-8y2+y3≤140,4x1-7x2+7x3+2y1+4y2-7y3≤45，

4x1+5x2+x3-7y1-6y2+y3≤800,x1,x2,x3≥0,y1,y2,y3≥0.

求解(LP2)問題得到(x2,λ,y2)T=(11.938 40,0.000 00,0.000 00,λ,14.177 09,2.786 012,6.035 973)T,于是F2=364.008 0.

α(ω3)TB=(14α,2α,2α)≥(4λ1+4λ2+3λ3,7λ1+2λ2+9λ3,7λ1+4λ2+8λ3)

x1+2x2-x3+14y1+2y2+2y3=240，5x1-7x2+3x3+2y1-7y2+3y3≤200，

7x1+7x2+6x3+y1+13y2+y3≤140，2x1+2x2-x3+14y1+2y2+2y3≤240，

-3x1+6x2+12x3+4y1-8y2+y3≤140，4x1-7x2+7x3+2y1+4y2-7y3≤45，

4x1+5x2+x3-7y1-6y2+y3≤800,x1,x2,x3≥0,y1,y2,y3≥0.

求解(LP3)問題得到(x3,λ,y3)T=(11.938 40,0.000 00,0.000 00,λ,14.177 09,2.786 012,6.035 973)T,于是F3=364.008 0.

α(ω4)TB=(4α，-8α,α)≥(4λ1+4λ2+3λ3,7λ1+2λ2+9λ3,7λ1+4λ2+8λ3)

是不成立的，則F4=-.

α(ω5)TB=(2α,4α,-7α)≥(4λ1+4λ2+3λ3,7λ1+2λ2+9λ3,7λ1+4λ2+8λ3)

是不成立的，則F5=-.

α(ω6)TB=(-7α，-6α,α)≥(4λ1+4λ2+3λ3,7λ1+2λ2+9λ3,7λ1+4λ2+8λ3)

是不成立的，則F6=-.

第3步 總結(jié)可以得到F3=364.008 0,最優(yōu)解為

(x3,y3)T=(11.938 40,0.000 00,0.000 00;14.177 09,2.786 012,6.035 973)T.

例2 考慮如下問題，其中x∈R1,y∈R1.

s.t. 0≤x≤3，

s.t. -x-y≤-3，

-x+2y≤0，

2x+y≤12，

-3x+2y≥-4，

y≥0.

表1 算例最優(yōu)解情況Tab.1 Examples of optimal solutions

例3 考慮如下問題，其中x∈R1,y∈R2.

s.t.y2≤100,x+y2≤170,x+y1+y2≤240,y1+y2≤170,-x+y1+y2≤130,-x+y2≤60,

-x-y1+y2≤20,-y1+y2≤60,x+y1-y2≤130,x≤100,x+y1≤170,y1≤100,-x+y1≤60,

-x≤-10,-x-y1≤-50，-y≤-10，x-y1≤60,x-y2≤60,x+y1-y2≤130,y1-y2≤60,

-x+y1-y2≤20,-x-y2≤-50，-x-y1-y2≤-90，-y1-y2≤-170,x-y1-y2≤20,-y2≤-10.

表1是采用所設(shè)計的搜索算法求得例2、例3得到的結(jié)果.

4 結(jié)語

運(yùn)用標(biāo)量化方法將所考慮的半向量二層規(guī)劃問題轉(zhuǎn)化為二層單層規(guī)劃問題.通過分析轉(zhuǎn)化后的二層單目標(biāo)規(guī)劃問題的可行集與容許集、容許集極點(diǎn)與最優(yōu)解之間的關(guān)系，進(jìn)而設(shè)計了求解原問題全局最優(yōu)解的搜索算法.數(shù)值結(jié)果表明，所設(shè)計的極點(diǎn)搜索算法是可行的.