袁梓翠, 呂一兵, 萬仲平

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

1.引言

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

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

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

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

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

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

本文所考慮的線性半向量二層規(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)解, 在接下來的內容中, 假設如下條件成立:

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

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

其中λ為給定的下層目標函數權重系數, 反映了上層決策者對下層各目標的偏好.

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

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

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

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

其中, λ ∈?為給定的下層目標函數權重系數.

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

其中u ∈Rp,v ∈Rm為相應的Lagrange乘子, λ為給定的下層目標函數的權重系數.

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

3.理論與算法

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

割平面算法:

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

4.算例

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

5.小結

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

值得指出的是, 本文所設計的割平面算法中, 割平面的構造依賴于相鄰頂點的獲取, 因此如能將高效的多面體相鄰頂點的獲取方法與本文所設計的割平面方法相結合, 有望極大提升割平面算法的計算效率.