張博,高岳林

(1.北方民族大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,寧夏 銀川750021;2.寧夏科學(xué)計(jì)算與智能信息處理協(xié)同創(chuàng)新中心,寧夏 銀川750021)

1.引言

分式規(guī)劃問題是非線性全局優(yōu)化的一個(gè)重要分支,而二次比式和規(guī)劃問題是又一類特殊的分式規(guī)劃問題.在現(xiàn)實(shí)生活中,許多實(shí)際問題均可抽象為二次比式和規(guī)劃模型,且在投資問題、運(yùn)輸方案、經(jīng)濟(jì)效益、生產(chǎn)管理等領(lǐng)域有著廣泛的應(yīng)用背景.數(shù)十年來它吸引了許多專家和學(xué)者的高度關(guān)注;其次,從研究的觀點(diǎn)來看,二次比式和規(guī)劃問題對(duì)理論分析和計(jì)算求解的方式提出了挑戰(zhàn).本文主要考慮以下形式的二次比式和規(guī)劃問題(QFP):

這里,p≥2,H1i(x),H2i(x)均為二次函數(shù)其表達(dá)式如下：

其中,b∈Rn,A∈Rm×n,Qsi∈Rn×n,qsi∈Rn,psi∈R,s=1,2,X是非空有界閉集.根據(jù)H2i(x)的連續(xù)性以及介值定理可知,對(duì)任意的x∈X有H2i(x)>0或者H2i(x)<0.如果存在某一個(gè)i∈{1,2,···,p}使得H2i(x)<0,用替代使得所有分式項(xiàng)的分母項(xiàng)均大于零;為了方便起見,假設(shè)此時(shí),H1i(x)<0,H2i(x)>0,用替代其中M是一個(gè)充分大的正數(shù),滿足對(duì)所有的x∈X,H1i(x)+MH2i(x)≥0,問題(QFP)的本質(zhì)不變.因此,這里不失一般性,假定對(duì)所有的i=1,2,···,p,均有H1i(x)≥0,H2i(x)>0.

此外,對(duì)于問題(QFP)可能擁有多個(gè)局部最優(yōu)解,這樣會(huì)干擾尋找全局最優(yōu)解,使問題的難度增加,因此研究此類問題是必要的.本文為上述比式和規(guī)劃問題建立了一個(gè)分支定界算法.首先,通過線性代數(shù)矩陣滿秩分解的知識(shí)將原問題中通項(xiàng)的分子和分母的二次函數(shù)分別轉(zhuǎn)化為相應(yīng)的兩項(xiàng)乘積和的形式,然后利用求解兩項(xiàng)線性乘積和規(guī)劃的知識(shí)[1]并結(jié)合一些線性化技巧分別構(gòu)造問題目標(biāo)函數(shù)中通項(xiàng)的下界,并基于此技巧構(gòu)造出能夠?yàn)樵瓎栴}提供可靠下界的線性松弛規(guī)劃問題.最后,利用分支定界的思想以及文[2]的可行域縮減技術(shù)設(shè)計(jì)出關(guān)于本文問題的一個(gè)新的分支定界算法.

到目前為止,已經(jīng)有許多全局優(yōu)化算法可以用來求解比式和規(guī)劃問題.當(dāng)通項(xiàng)中的分子和分母都為線性函數(shù)時(shí),那么文[3-9]給出了不同的求解方法,當(dāng)問題為非線性比式和規(guī)劃問題時(shí),ZHANG,CHEN和JIA[10]提出了一種基于單調(diào)優(yōu)化理論的算法用于求解此類問題.JIAO和LIU[11]構(gòu)造了一種區(qū)間劃分壓縮算法并用求解二次比式和規(guī)劃問題.最近,JIAO和LIU[13]他們又提出了一種基于參數(shù)線性松弛規(guī)劃問題來確定下界的方法,并構(gòu)造了相應(yīng)的分支定界算法來求解二次比式和規(guī)劃問題.文[14]為廣義多項(xiàng)式比式和問題,GAO,Mishra和SHI討論了函數(shù)比之和的最大化問題,推廣了一種求解線性比和問題的算法,并給出了問題的復(fù)雜性.文[15]給出了一種基于單純形剖分的確定性非線性比式和問題全局優(yōu)化算法.關(guān)于其他類型非線性比式和規(guī)劃問題還可以參考文[16-17].

本文后續(xù)章節(jié)布局如下:第二節(jié)給出問題預(yù)處理時(shí)必要的兩個(gè)引理;第三節(jié)利用已知的兩個(gè)引理得出原問題的一個(gè)等價(jià)問題并給出等價(jià)問題的線性松弛過程;第四節(jié)給出了新的分支定界算法以及相應(yīng)的超矩形剖分方法和縮減技術(shù),并證明了算法的收斂性;第五節(jié)通過數(shù)值實(shí)驗(yàn)說明了我們提出的算法是有效可行的;第六節(jié)為結(jié)論.

2.預(yù)備知識(shí)

為了求解問題(QFP),我們首先將其轉(zhuǎn)化為一個(gè)具有特殊結(jié)構(gòu)的等價(jià)問題以便建立線性松弛問題,為了驗(yàn)證這種轉(zhuǎn)化的可能性,我們首先引入以下引理:

引理2.1[12]對(duì)任意矩陣Q滿足秩(Q)=1,存在兩個(gè)向量α和β,使得Q=αβT.

引理2.2[12]對(duì)任意矩陣Qsi∈Rn×n,假定秩(Qsi)=rsi,則一定存在兩個(gè)向量αsij和βsij,使得

3.等價(jià)問題以及線性松弛規(guī)劃

根據(jù)以上兩個(gè)引理2.1 和2.2 我們知道,對(duì)每一個(gè)i=1,2,···,m,s=1,2,二次函數(shù)Hsi(x)都可轉(zhuǎn)化為以下形式:

那么問題(QFP)可以進(jìn)一步轉(zhuǎn)化為以下等價(jià)問題:

其中,αsij∈Rn,βsij∈Rn,qsi∈Rn,psi∈R,i=1,2,···,p,s=1,2,X是非空有界閉集.

為了獲得問題(QFP)的分支定界算法,我們需要確立線性松弛規(guī)劃子問題,用于估計(jì)問題(QFP)最優(yōu)值的下界,具體方法如下:

首先,求解以下2n個(gè)線性規(guī)劃問題:

從而得到包含可行域X的初始超矩形

然后,對(duì)每一個(gè)i=1,2,···,p,s=1,2,j=1,2,···,rsi,繼續(xù)求解以下線性規(guī)劃問題:

根據(jù)式(3.2)和(3.3)很容易得到

再由(3.4)-(3.7),不難得出

這里,

為了方便起見,這里記

定理3.1令則對(duì)所有的x∈X ∩H,當(dāng)εk→0時(shí),hsij(x)?

證對(duì)所有的x∈X ∩H,由式(3.8)得:

同樣有(x)?hsij(x)→0.證畢.

不失一般性,對(duì)任意的x∈Hk ?H,i=1,2,···,m,定義

定理3.2對(duì)任意的以下結(jié)論成立:

證(i)對(duì)任意的x∈Hk,以及i=1,2,···,p,根據(jù)(3.10)可知,當(dāng)s=1 時(shí),

同理,根據(jù)式(3.11)可知,當(dāng)s=2時(shí),因?yàn)镠2i(x)>0,所以(x)≥H2i(x)>0.雖然H1i(x)≥0,但是存在x∈Hk使得(x)<0,以及G(x)<0,此種情況下,顯然G(x)>G(x),滿足結(jié)論(i);當(dāng)H1i(x)≥0即0 時(shí),同樣滿足結(jié)論(i).

基于上述討論,可以知道,對(duì)每一個(gè)i=1,2,···,p,H1i(x),H2i(x),(x)都是大于零的并且都是連續(xù)的,所以它們?cè)谟薪玳]集X,H以及剖分后的子區(qū)域Xk,Hk上都是有界并且是非負(fù)的,那么分別存在相當(dāng)大的正數(shù)N1i,N2i使得記根據(jù)式(3.12)可知

那么,根據(jù)上述討論,我們就得到了問題(QFP)的非線性松弛規(guī)劃子問題(NLRP(Hk)):

顯然,(NLRP(Hk))可以轉(zhuǎn)化為(QFP)的一個(gè)線性松弛規(guī)劃子問題(LRP(Hk)):

綜上所述,我們知道在算法迭代到第k步時(shí),只要在此步所對(duì)應(yīng)的超矩形Hk上求解問題(LRP(Hk)) 的最優(yōu)值v(LRPk),那么這個(gè)最優(yōu)值同時(shí)也是原問題(QFP) 在Hk上全局最優(yōu)值v(QFP)的一個(gè)下界,即v(LRPk)≤v(QFP).

定上界的操作是在分支的過程中不斷產(chǎn)生問題(QFP)的可行點(diǎn)來完成的.通過求解原問題在Hk上的一個(gè)有效下界v(LRPk),它的最優(yōu)解是原問題在Hk上的一個(gè)可行點(diǎn),而我們通過在分支定界的過程中不斷增加滿足可行域X的可行點(diǎn),以達(dá)到更新上界的目的.

4.超矩陣的剖分和縮減

在這一節(jié),我們給出超矩形的分支、縮減步驟對(duì)應(yīng)的算法(RPF)和算法(RSA).

首先,為了便于本文算法的分支,這里采用二分法的思想.令Hk=[lk,uk]∈H表示當(dāng)前所要剖分的超矩形,用xk表示問題(QFP)當(dāng)前最優(yōu)解,顯然xk∈X ∩Hk.假設(shè)xk∈Hk,對(duì)超矩形Hk=[lk,uk],我們給出算法(RPF)用來對(duì)其剖分:

算法(RPF):

步1計(jì)算ω=max{(xkj?lkj)(ukj?xkj):j=1,2,···,n},

若ω=0,

令ukμ?lkμ=max{ukj?lkj:j=1,2,···,n},

否則,找出第一個(gè)xkj∈arg maxω,記作xkμ=xkj.

記x′=(lk1,lk2,···,lkj?1,xkμ,lkj+1,···,lkn)T,x′′=(uk1,uk2,···,ukj?1,xkμ,ukj+1,···,ukn)T.

步2通過x′與x′′的連線或它們連線所在的平面將超矩形Hk剖分為兩個(gè)子超矩形Hk1=[lk1,uk1]和Hk2=[lk2,uk2],則這兩個(gè)子超矩形分別為:

其次,為了提高算法的收斂速度,這里使用文[10]中的超矩形縮減技術(shù).假設(shè)問題(QFP)中的所有線性不等式約束的展開形式為:∑aijxj≤bi,i=1,2,···,m,文[10]中的超矩形縮減技術(shù)可以表述為算法(RSA):

算法(RSA):

令I(lǐng)k:={1,2,···,m},

步1對(duì)每一個(gè)i=1,2,···,m,

分別計(jì)算rUi=

步2若rLi >bi,停止.問題(QFP)在Hk上沒有可行解(Hk被刪除);

若rUi≤bi,令I(lǐng)k:=Ik?{i},問題(QFP)的第i個(gè)線性不等式約束被刪除;

否則,對(duì)每一個(gè)j=1,2,···,n

若aij >0,令

否則aij <0,令

為了方便起見,我們把該算法產(chǎn)生的新的超矩形仍然記為Hk,它是原來超矩形的子集.

5.新的分支定界算法及其收斂性

最后,基于上述討論,本文求解問題(QFP)全局最優(yōu)解的分支定界算法總結(jié)如下:

步0(初始化)

步0.1構(gòu)造包含可行域X的n維超矩形H0=H=[l,u];令分支的所有活躍節(jié)點(diǎn)的集合記為Q0={H0},上界為U0=+∞,將本文上述所有可行點(diǎn)都放入集合W中,所需容忍度?>0.

步0.2解線性規(guī)劃問題(LRP(H0)),如果不可行,那么原問題無解;否則,記得到的最優(yōu)值和最優(yōu)解分別為L(H0),(x0,y0),置L0=L(H0);如果x0∈X,令W=W ∪{x0},U0=G(x0),若U0?L0≤?,那么稱x0為問題(QFP)的?-全局最優(yōu)解,迭代終止;否則,置k=1,轉(zhuǎn)入步1.

步1(超矩形的分支和縮減)

在Qk中挑選出當(dāng)前最小下界所對(duì)應(yīng)的超矩形Hk,超矩形Hk直接經(jīng)過剖分算法(RPF)的分解可產(chǎn)生形如第四節(jié)中的兩個(gè)新的子超矩形Hk1和Hk2;然后運(yùn)用算法(RSA)分別對(duì)Hk1和Hk2按以下步驟縮減,為了方便起見,我們把縮減后的超矩形記為Hki,i∈Γ,其中Γ是縮減后超矩形的指標(biāo)集合.

步1.1運(yùn)用算法(RSA)對(duì)Hk1進(jìn)行縮減.

若Hk1被刪除,則Qk=Qk{Hk},轉(zhuǎn)到步1.2;

否則,令Qk=Qk{Hk}∪Hk1;

求解線性松弛規(guī)劃問題(LRP(Hk1)),得到最優(yōu)值記為Lk1,最優(yōu)解記為(xk1,yk1);

若xk1∈X,讓W(xué)=W ∪xk1,轉(zhuǎn)到步1.2;

步1.2運(yùn)用算法(RSA)對(duì)Hk2進(jìn)行縮減,

若Hk2被刪除,

若Hk1已經(jīng)被刪除,轉(zhuǎn)到步3;

若Hk1沒有被刪除,轉(zhuǎn)到步2;

否則令Qk=Qk ∪Hk2;

求解線性松弛規(guī)劃問題(LRP(Hk2)),得到最優(yōu)值記為Lk2,最優(yōu)解記為(xk2,yk2);

若xk2∈X,讓W(xué)=W ∪xk2,轉(zhuǎn)到步2;

步2(定界)

如果W=?,那么Uk=+∞;如果W≠?,那么Uk=min{G(x):x∈W},當(dāng)前的最優(yōu)解為xk∈arg minG;

如果Qk=?,那么Lk保持不變;如果Qk≠?,那么Lk=min{L(H):H∈Qk};

步3(剪枝規(guī)則)

讓Qk+1=Qk{H:Uk?L(H)>ε,H∈Qk}.若Qk=?,迭代終止:Uk是(QFP)的?-全局最優(yōu)值,xk是?-全局最優(yōu)解,否則,置k=k+1,轉(zhuǎn)到步1.

下面為了說明我們算法是收斂的,給出定理5.1并給予相應(yīng)的證明.

定理5.1設(shè)問題(QFP)的可行域X是n維的,且超矩形的剖分是耗盡的,那么以下兩個(gè)結(jié)論成立:

(i)如果算法在迭代過程中有限步終止,則問題(QFP)的全局最優(yōu)解將在算法終止時(shí)得到;

(ii) 如果算法在有限步不能終止,則將產(chǎn)生可行解組成的序列{xk}并且它的每一個(gè)聚點(diǎn)x?必是問題(QFP)的全局最優(yōu)解.

證(i)若算法是有限步終止,那么根據(jù)終止準(zhǔn)則可知Uk?Lk

假設(shè)此時(shí)的全局最優(yōu)解是x?,我們知道

因此,將式(5.1)和(5.2)聯(lián)立可得

故(i)得證.

(ii)如果算法的迭代是無限的,則通過求解問題(LRPk)可產(chǎn)生原問題的可行解序列{xk},以及對(duì)應(yīng)的序列{(xk,yk)}.根據(jù)步1,隨著可行域的不斷加細(xì)我們有

因?yàn)橄陆缧蛄衶Lk=(xk,yk)}是單調(diào)不減且有界的,且上界序列{Uk=G(xk)}是單調(diào)不增且有界,故原問題的上下界都是收斂的.對(duì)式(5.3) 兩邊取極限可得

于是,令L=那么式(5.4)將轉(zhuǎn)化為

不失一般性,假設(shè)算法在迭代過程中形成的超矩形序列{Hk=[lk,uk]}滿足xk∈Hk以及Hk+1∈Hk.由于算法在每步迭代中剖分超矩形都是沿著最長邊來剖分的,這保證了超矩形盡最大可能的加細(xì),那么在這個(gè)過程中也會(huì)形成關(guān)于x的序列{xk}同時(shí)滿足根據(jù)函數(shù)G(x)的連續(xù)性,就會(huì)有

所以,序列{xk}的每一個(gè)聚點(diǎn)x?都是問題(QFP)的全局最優(yōu)解.

6.數(shù)值實(shí)驗(yàn)

在這一節(jié),我們用幾個(gè)其他文獻(xiàn)中已知的算例來測(cè)試文中算法的有效性.本文所有的線性規(guī)劃問題均選用單純形法求解,算法所有測(cè)試過程均用MATLAB9.0.0.341360(R2016a) 在Inter(R)Core (TM)i5-3570K,CPU@3.2GHz,4GB 內(nèi)存,64 位Windows7 操作系統(tǒng)的計(jì)算機(jī)上運(yùn)行.

算例1[11,14,16]:

算例2[11,13]:

算例3[13,14,16]:

算例4[14,16]:

算例5[11,17]:

算例1-5的計(jì)算結(jié)果我們已呈現(xiàn)在表6.1中,算法運(yùn)行過程中的容忍度分別為10?3,10?5,10?2,10?2,10?6,顯然從表6.1中我們知道這些容忍度分別為其他各個(gè)文獻(xiàn)中所用容忍度的最大值,足以與其他算法對(duì)比.通過表6.1可以看出,本文算法總體來說比文[11,13,17]計(jì)算效果要好,與文[14]相比,我們算法僅在算例3表現(xiàn)的更好,其他算例表現(xiàn)略差,雖然總體計(jì)算能力低于文[16]中的算法,但是我們所提出的算法是有效可行的.

為了進(jìn)一步說明本文算法的性能,對(duì)于算例6,我們也進(jìn)行了若干的偽隨機(jī)試驗(yàn)并呈現(xiàn)在了表6.2中,下文也做出了對(duì)應(yīng)的說明.

表6.1 算例1-5 利用本文算法產(chǎn)生的數(shù)值結(jié)果

表6.2 算例6 利用本文算法產(chǎn)生的數(shù)值結(jié)果

算例6:

這里,A,b,αsij,βsij,qsi,psi,s=1,2,i=1,2,···,p,j=1,2,···,r,的每個(gè)元素都是在[0,1]上偽隨機(jī)產(chǎn)生的,r表示矩陣的秩.

表6.1和表6.2中,表頭的符號(hào)分別是:E:算例編號(hào);R:計(jì)算方法;x?:原問題的最優(yōu)解;G(x?):目標(biāo)函數(shù)的最優(yōu)值;I:平均迭代次數(shù);?:容忍度;t:迭代終止時(shí)CPU平均運(yùn)行時(shí)間;p:目標(biāo)函數(shù)中二次比式的個(gè)數(shù);r:目標(biāo)函數(shù)分子和分母中矩陣的秩,這里假設(shè)它們秩都相等;m:線性約束的個(gè)數(shù);n:目標(biāo)函數(shù)的維數(shù).

通過表6.2的計(jì)算結(jié)果,可以知道當(dāng)m,r和n固定不變時(shí),隨著p的增加,算法的平均迭代次數(shù)I在緩慢增加,但是迭代時(shí)間t增加的很快;當(dāng)p,r和n固定不變時(shí),約束條件增多時(shí),I和t都是快速減少的;當(dāng)p和m保持不變時(shí),隨著維數(shù)n的增加,I和t都是急劇增加的,此時(shí)若將矩陣的秩變小,那么相應(yīng)的I和t也在減少;當(dāng)約束條件的個(gè)數(shù)m相對(duì)于決策變量個(gè)數(shù)n非常大時(shí),因?yàn)檫@樣形成的可行域非常狹小,所以能夠在很少的迭代步驟找到最優(yōu)解,但是每一步的迭代時(shí)間都很長;當(dāng)決策變量個(gè)數(shù)n相對(duì)于約束條件的個(gè)數(shù)m很大時(shí),形成的可行域范圍很大,迭代時(shí)間和步驟都變大.