線性半向量二層規(guī)劃問題的割平面方法

袁梓翠, 呂一兵, 萬仲平

(1.長江大學(xué)信息與數(shù)學(xué)學(xué)院, 湖北荊州 434023;2.武漢大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 湖北武漢 430072)

1.引言

二層規(guī)劃是一類具有遞階結(jié)構(gòu)的優(yōu)化問題.由于能夠恰當(dāng)描述實(shí)際問題中的層次關(guān)系, 二層規(guī)劃展現(xiàn)出了廣泛的應(yīng)用前景, 同時(shí)各種二層規(guī)劃問題也越來越引起研究者的關(guān)注.

半向量二層規(guī)劃是上層為單目標(biāo), 下層為多目標(biāo)的一類二層規(guī)劃問題[1].由于半向量二層規(guī)劃可以較為全面地反映決策者的意愿, 因此越來越引起研究者的關(guān)注.

在半向量二層規(guī)劃問題的最優(yōu)性條件方面, LIU和WAN[2]利用標(biāo)量化方法將悲觀半向量二層規(guī)劃問題轉(zhuǎn)化為一個(gè)非光滑單層約束優(yōu)化問題, 同時(shí)基于Mordukhovich廣義微分, 研究了悲觀半向量二層規(guī)劃問題的最優(yōu)性條件; Dempe[3]等基于非光滑優(yōu)化問題的最優(yōu)性條件, 得出了半向量二層規(guī)劃問題的一階最優(yōu)性必要條件.

在半向量二層規(guī)劃問題的算法設(shè)計(jì)方面, 基于線性多目標(biāo)規(guī)劃的邊緣罰函數(shù)方法, 任愛紅[4]等將一類半向量二層規(guī)劃問題轉(zhuǎn)化為帶互補(bǔ)約束的單層優(yōu)化問題, 并在偏靜態(tài)條件下構(gòu)造了半向量二層規(guī)劃的精確罰問題, 并給出了罰函數(shù)算法; 劉君娥[5]等利用線性規(guī)劃的對偶理論,將樂觀線性半向量二層優(yōu)化問題轉(zhuǎn)化為不可微單層優(yōu)化問題, 通過構(gòu)建單層問題的松弛問題得到原線性半向量二層規(guī)劃問題最優(yōu)值的一個(gè)下界; 呂一兵等[6]以下層互補(bǔ)約束為罰項(xiàng), 構(gòu)造了線性半向量二層規(guī)劃問題的罰問題.通過分析罰問題最優(yōu)解的特征, 設(shè)計(jì)了一種求解其全局最優(yōu)解的極點(diǎn)搜索算法; 另外, 呂一兵等[7]以下層問題最優(yōu)性條件代替下層問題, 進(jìn)而構(gòu)造了半向量二層規(guī)劃問題的罰問題, 并設(shè)計(jì)出相應(yīng)的罰函數(shù)算法.

值得指出的是, 目前有關(guān)半向量二層規(guī)劃問題的算法研究更多的局限于得到問題的局部最優(yōu)解.在筆者前期相關(guān)研究工作中[6], 設(shè)計(jì)了線性半向量二層規(guī)劃問題全局最優(yōu)解的極點(diǎn)搜索方法, 但是該極點(diǎn)搜索方法需要得到約束域(多面體)的全部頂點(diǎn).不同于文[6]中的極點(diǎn)搜索方法, 本文將設(shè)計(jì)線性半向量二層規(guī)劃問題的割平面方法, 以得到問題的全局最優(yōu)解.本文所設(shè)計(jì)的割平面方法的思路為, 首先利用加權(quán)法將下層向量優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題, 同時(shí)基于下層問題的K-K-T最優(yōu)性條件, 將原問題轉(zhuǎn)化為相應(yīng)的單層規(guī)劃問題; 然后通過分析所構(gòu)造單層規(guī)劃問題最優(yōu)解的特征, 同時(shí)基于割平面思想, 設(shè)計(jì)了一種求解線性半向量二層規(guī)劃問題全局最優(yōu)解的算法; 最后利用算例對所設(shè)計(jì)算法的可行性進(jìn)行分析.值得指出的是, 由于所設(shè)計(jì)的割平面算法只需求解一系列線性規(guī)劃問題, 因此具有較好的應(yīng)用前景.

2.線性半向量二層規(guī)劃數(shù)學(xué)模型與預(yù)備知識

本文所考慮的線性半向量二層規(guī)劃問題, 可以表述為,

其中, x ∈Rn,y ∈Rm,A ∈Rp×n,B ∈Rp×m,c1∈Rn,c2∈Rm,D ∈Rl×m,b ∈Rp.記z ={(x,y)|Ax+By ≤b,x ≥0,y ≥0} 為上述問題的約束域, T = {x ∈Rn|?y ∈Rm,Ax+By ≤b,x ≥0,y ≥0}為約束域z 在上層決策空間的投影.對于給定的x ∈T, z(x)={y|(x,y)∈z}為下層問題的可行集.記P(x)為如下下層問題,

的若有效解集.由上述記號,問題(2.1)的可行集可以表述為:IR={(x,y)|(x,y)∈z,y ∈P(x)}.

定義2.1(x?,y?)∈IR為問題(2.1)的全局最優(yōu)解,如果對任意的(x,y)∈IR,有F(x?,y?)≤F(x,y).

為了保證問題(2.1)存在最優(yōu)解, 在接下來的內(nèi)容中, 假設(shè)如下條件成立:

(H1)z為非空緊集, 且P(x)?.

對于給定的上層決策變量x ∈T, 下層問題(2.2)為線性多目標(biāo)規(guī)劃問題.由多目標(biāo)規(guī)劃的相關(guān)理論[8,9], y為問題(2.2)的若有效解, 當(dāng)且僅當(dāng)存在λ ∈? =使得y為如下問題(2.3)的最優(yōu)解,

其中λ為給定的下層目標(biāo)函數(shù)權(quán)重系數(shù), 反映了上層決策者對下層各目標(biāo)的偏好.

值得指出的是, 半向量二層規(guī)劃問題(2.1)本質(zhì)上屬于下層有不唯一最優(yōu)解的二層規(guī)劃問題.對于該類二層規(guī)劃問題, 其最優(yōu)解定義一般有“樂觀最優(yōu)解”和“悲觀最優(yōu)解”.在上述問題(2.3)中, λ反映了上層決策者對下層各目標(biāo)的偏好, 即上層決策者可以影響或支配下層決策者.這就意味著, 本文主要考慮問題(2.1)的“樂觀最優(yōu)解”.

問題(2.3)為單目標(biāo)優(yōu)化問題.關(guān)于線性多目標(biāo)規(guī)劃問題(2.2)的弱有效解集與單目標(biāo)規(guī)劃問題(2.3)的最優(yōu)解集之間的關(guān)系, 有如下結(jié)果:

命題2.1[8]對于給定的(x,λ) ∈T ×?, ψ(x,λ)為問題(2.3)的最優(yōu)解集, 則有P(x) =ψ(x,λ):=∪{ψ(x,λ)|λ ∈?}.

基于上述命題2.1, 可以將問題(2.1)轉(zhuǎn)化為如下問題(2.4),

其中, λ ∈?為給定的下層目標(biāo)函數(shù)權(quán)重系數(shù).

對于上述問題(2.4), 基于下層問題的K-K-T 最優(yōu)性條件, 可以將問題(2.4)轉(zhuǎn)化為如下非凸、不可微優(yōu)化問題,

其中u ∈Rp,v ∈Rm為相應(yīng)的Lagrange乘子, λ為給定的下層目標(biāo)函數(shù)的權(quán)重系數(shù).

在下面的內(nèi)容中, 將著重分析上述單層規(guī)劃問題(2.5)最優(yōu)解的相關(guān)特征, 同時(shí)基于割平面思想, 設(shè)計(jì)一種求解線性半向量二層規(guī)劃問題全局最優(yōu)解的割平面算法.

3.理論與算法

綜上所述, 可設(shè)計(jì)如下求解線性半向量二層規(guī)劃問題的割平面算法.

割平面算法:

在上述算法中, 引入頂點(diǎn)對應(yīng)的割平面, 每次割去z中都不含問題(2.1)可行解的部分, 而剩下的部分z1是非退化的多面體; 再從新的約束域出發(fā), 在z1中重復(fù)以上步驟.每重復(fù)一次都將割去z的一個(gè)頂點(diǎn), 由于z的頂點(diǎn)個(gè)數(shù)是有限的, 因此經(jīng)過有限次循環(huán)后可以找到一個(gè)頂點(diǎn)是原問題的全局最優(yōu)解.

4.算例

為驗(yàn)證所設(shè)計(jì)算法的可行性, 利用上述算法求解如下線性半向量二層規(guī)劃問題[6], 其中x ∈R,y ∈R2.

5.小結(jié)

本文研究了線性半向量二層規(guī)劃問題全局最優(yōu)解的求解問題.基于線性半向量二層規(guī)劃問題的最優(yōu)解可在其約束域的頂點(diǎn)處取得這一特征, 通過構(gòu)造割平面, 設(shè)計(jì)了求解其全局最優(yōu)解的割平面方法.由于所提出算法只需求解一系列線性規(guī)劃問題, 因此具有較好的應(yīng)用前景.

值得指出的是, 本文所設(shè)計(jì)的割平面算法中, 割平面的構(gòu)造依賴于相鄰頂點(diǎn)的獲取, 因此如能將高效的多面體相鄰頂點(diǎn)的獲取方法與本文所設(shè)計(jì)的割平面方法相結(jié)合, 有望極大提升割平面算法的計(jì)算效率.