拉格朗日松弛對偶問題的一個改進次梯度算法

何方國　(黃岡師范學院數理學院，湖北 黃岡 438000)

?

拉格朗日松弛對偶問題的一個改進次梯度算法

何方國(黃岡師范學院數理學院，湖北 黃岡 438000)

[摘要]拉格朗日松弛法是處理整數優化問題的一個重要方法。針對利用次梯度算法求解拉格朗日松弛對偶問題時容易出現收斂速度較慢及計算效率低等問題, 對次梯度算法進行了改進：結合當前次梯度和歷史次梯度的線性組合給出新的迭代方向，然后決定合適步長。同時證明了算法的收斂性及有效的消除迭代過程中的鋸齒現象。將改進的拉格朗日松弛的次梯度算法用于解決TSP問題，數值計算結果表明，改進的次梯度算法比普通次梯度算法收斂較快，說明了改進算法的有效性。

[關鍵詞]拉格朗日松弛算法；次梯度；優化問題；對偶

拉格朗日松弛算法(LR)已經成功的應用于許多優化問題，如網絡優化問題、生產調度問題、選址問題及其他整數優化問題等[1，2]。在拉格朗日松弛算法中, 求解拉格朗日對偶問題非常關鍵,一般采用次梯度優化算法來解決。但其方法在優化過程中容易出現收斂速度較慢及計算效率低的特點，這主要是在迭代過程中方向和步長的選擇影響著算法的性能。為此, 一些學者已提出了求解拉格朗日松弛問題的改進方法：文獻[3]給出了一種指數形式的拉格朗日對偶方法，并證明其收斂性；文獻[4]提出利用上次迭代的次梯度的信息來改進步長的次梯度算法；文獻[5]則將模糊的概念引入次梯度的求取中, 提出了模糊次梯度算法。這些方法在求解性能上都有所提高，但有的計算比較復雜。下面，筆者給出一個改進方法，并將改進的拉格朗日松弛的次梯度算法用于解決TSP問題來證實算法的有效性。

1算法描述

考慮如下有約束的優化問題：

minf(x)s.t.gi(x)≤0,i∈I,x∈X

(1)

其中,I= {1, 2,…,m}，X為一個有限集； f: Rn→R和gi:Rn→R分別為X上的連續凸函數。

(2)

其中，g(x)=(g1(x),g2(x),…,gm(x))T；L(x,λ)為拉格朗日函數；q(λ)是對偶函數。

對乘子λ最大化對偶函數q(λ), 得如下拉格朗日對偶問題：

(3)

顯然，對偶問題為原問題的最優值提供了一個下界，拉格朗日松弛算法就是通過求解對偶問題(3)而逐步逼近原問題(1)的最優解。由于q(λ)是一個分段凹函數[6], 在解決對偶問題(3)時通常采用次梯度算法。

定義1設f(x)是Rn上的凹函數且x0∈Rn，若對?x∈Rn，有：

f(x)≤f(x0)+ξT(x-x0)

則稱ξ是函數f(x)在x0處的次梯度。

定理1[7]設xλ是拉格朗日松弛問題(2)的最優解，則ξ=g(xλ)是q(λ)在λ處的次梯度。

次梯度算法解決問題(3)主要是通過下式迭代：

λk+1=λk+skξk

(4)

這里，λk+1是在第k+1次迭代時Lagrange乘子的值；sk表示沿次梯度方向的一個步長因子；ξk是q(λ)在λk點的次梯度。

由定理1知次梯度ξk=g(xλk), 其中：

(5)

次梯度算法對解決不可微的目標函數優化問題有明顯的優勢。當目標函數可微時，對于無約束問題次梯度法與梯度法具有同樣的搜索方向，但是次梯度法可以直接應用于更廣泛的問題。

在次梯度算法的迭代中，當λk點的次梯度ξk方向與前次點λk-1的次梯度ξk-1方向形成鈍角時, 會使得迭代點λk與λk-1的值很接近，和最速下降法類似，使得迭代的路線構成一個鋸齒形，因而收斂速度很慢[ 5]，這種現象稱為鋸齒現象。為了解決這一問題，與可微函數里共軛梯度一樣，有學者提出了共軛次梯度方法[6]。為改變迭代方向,Camerini[4]提出一個用偏轉次梯度方向dk代替λk點的次梯度ξk的改進方案：

dk=ξk+θkdk-1(θk≥0)

(6)

這里，θk是偏轉系數；ξk是λk點的次梯度；當前的迭代方向dk是次梯度ξk與上次迭代方向dk-1的一個線性組合。新的迭代計算公式如下：

λk+1=λk+skdk

(7)

這里，sk是合適的步長。

圖1　平面π及向量關系

筆者通過改變式(6)中的偏轉系數θk及確定式(7)中的步長sk得到一種改進的次梯度算法。通過式(7)，可以用λk-λk-1的方向代替dk-1的方向，當前的方向dk可以由向量λ*-λk的投影來近似代替，λ*代表對偶問題(3)式的最優解，又由式(6)，向量dk在向量dk-1和次梯度ξk決定的平面內(該平面記為π)，則dk是向量λ*-λk在平面π上的投影(見圖1)。

由于迭代過程中步長的決定應該是使λk盡可能接近最優解λ*, 受梯度算法中最優一維搜索的啟示，要達到這一目的，搜索方向需要與上次搜索方向正交，故有：

(λ*-λk)Tdk-1=0

(8)

由圖1可以得到：

λ*-λk=dk+nk

(nk)Tdk-1=0

考慮式(6)，則有：

(λ*-λk)Tdk-1=(dk)Tdk-1+(nk)Tdk-1=(ξk)Tdk-1+θk‖dk-1‖2=0

因此：

由于式(6)中θk≥ 0，故：

θk=-(ξk)Tdk-1‖dk-1‖2 (ξk)Tdk-1<00 其他ì?í????

(9)

為了確定式(7)中的sk, 與式(8)類似，有(λ*-λk+1)Tdk=0, 而λk+1=λk+skdk, 故：

(λ*-λk)Tdk=sk‖dk‖2

即：

(10)

由于：

(λ*-λk)Tdk=(λ*-λk)T(ξk+θkdk-1)

考慮式(8), 則有：

(λ*-λk)Tdk=(λ*-λk)Tξk

由于對偶函數q(λ)是凹函數，根據凹函數的定義有：

(λ*-λk)Tξk≥q(λ*)-q(λk)

即：

(λ*-λk)Tdk≥q(λ*)-q(λk)

令：

(λ*-λk)Tdk=αk(q(λ*)-q(λk))

(11)

這里，αk是一個適當正的參數，取1 ≤ak<2。

結合式(10)和式(11), 則有：

(12)

一般情況下最優解λ*是未知的，可以取函數q(λ)的一個盡可能小的上界來代替。因此，改進的拉格朗日對偶問題次梯度算法描述如下：

步1初始化: 選擇λ1≥ 0, 令k=1;

步2求解拉格朗日松弛問題:

并記最優解為xk；

步3對于確定的λk, 如果次梯度為0或滿足停止準則, 轉步5; 否則k=k+1;

步4利用(6)和(9)式求迭代方向, 利用(12)式求步長;

步5利用(7)式更新拉格朗日乘子λk, 轉步1;

步6xk和λk分別為原問題和對偶問題的目標解; 結束。

2算法收斂性

定理2設λ*是拉格朗日對偶問題(3)的最優解，{λk}是迭代產生的序列，若算法采用式(12)選擇步長，則有：

‖λ*-λk+1‖<‖λ*-λk‖

證明

‖λ*-λk+1‖2=‖λ*-λk-skdk‖2

由式(11)和式(12)，則有:

故‖λ*-λk+1‖<‖λ*-λk‖。

‖λ*-λk+1‖2=‖λ*-λk‖2-skαk(q(λ*)-q(λk))

(13)

由于‖λ*-λk‖是收斂的，對式(13)兩邊取極限則有：

定理3若算法的迭代方向式(6)中的θk由式(9)確定，則算法可以有效的消除鋸齒現象。

證明由于鋸齒現象產生是相鄰迭代方向成鈍角，考慮到：

圖2　向量間的關系

θk=-(ξk)Tdk-1‖dk-1‖2 (ξk)Tdk-1<00 其他ì?í????

如果(ξk)Tdk-1<0，即當前的次梯度方向ξk與前一次迭代方向dk-1成鈍角時，取θk> 0。由dk=ξk+θkdk-1,如圖2所示，由平行四邊形法則向量dk與dk-1的夾角小于向量ξk與dk-1的夾角；如果ξk與前一次迭代方向dk-1成銳角時，則迭代方向就是次梯度方向。故可以有效消除鋸齒現象。

3實例分析

考慮TSP問題(旅行商問題)，即在一個賦權完全圖中找一個過所有點的最小路徑并回到起點。令V= {1, 2, …，N}為點集，A為弧集，TSP問題可以描述為：

(14)

(15)

(16)

xij=0或1，且子圖(V,{(i,j)|xij=1}連通

(17)

圖3　一階樹的描述

這是一個有約束的整數規劃問題，aij表示節點i與j之間費用，當節點i和j之間有連接時xij=1，否則xij= 0。子圖(V, {(i,j)|xij=1})的連通性等價于完全圖中的一階樹。一階樹就是由點集{2, 3, …,N}生成的樹再加上與節點1關聯的2條弧，即一個一階樹就是只含一個單圈且單圈過節點1的生成子圖(見圖3)。

令X為完全圖中一階樹集，引入拉格朗日乘子ui和vj將問題松弛，得拉格朗日函數：

則拉格朗日對偶函數為：

(18)

拉格朗日對偶問題為：

(19)

如果把aij+ui+vj看成弧(i,j)上的權值，則優化問題(18)等價于求由節點{2, 3, …,N}生成的最小生成樹，然后加上和節點1關聯的弧，并使得和最小。求最小生成樹可以通過Prim算法解決。

對于拉格朗日對偶問題，利用改進次梯度算法求解，并與一般次梯度算法進行比較。一般次梯度算法步長sk=1, 在改進的次梯度算法中取ak=1, 由于直接獲取最優解L*比較困難, 一般可以利用較好的估計值代替該值[1]。由于重點是對一般次梯度算法與改進算法進行比較，為了便于計算，由其他算法得到了最優值L*。

表1　節點數為20的5個完全圖計算結果

通過Matlab編程進行計算, 次梯度為0或者(L*-Lk)/L*到一定精度時停止，求最小生成樹使用Prim算法。給出一個20個節點的完全圖，其權值為介于1到10均勻分布隨機數，生成5個完全圖，計算結果如表1所示。從表1結果可以看出, 改進次梯度算法的迭代次數比一般算法少得多，其收斂速度明顯快于一般次梯度算法。這是由于迭代步長和方向選擇的影響。如果當前的次梯度方向與前一次迭代方向成鈍角時，會明顯減低收斂速度，但是改進算法會改變迭代方向，使得當前迭代方向與前一次成銳角，因此收斂速度會優于一般次梯度方法。

4結語

次梯度優化算法是求解Lagrange松弛對偶問題的一種有效的算法。不同的迭代方向和步長策略對算法的收斂性有不同的影響。筆者在普通次梯度優化算法的基礎上, 提出了結合當前次梯度和歷史次梯度的線性組合給出新的迭代方向,并確定了改進次梯度算法中的合適步長。與傳統次梯度算法的比較，改進的次梯度算法收斂較快。

[參考文獻]

[1]Ali D, Jean-Philippe P R. An integrated supply chain problem: a nested lagrangian relaxation approach [J]. Annals of Operations Research，2015, 229: 303～323.

[2] Marshall L F. The Lagrangian Relaxation Method for Solving Integer Programming Problems[J]. Management Science, 2004, 50: 1861～1871.

[3] Xu Yifan, Li Duan. A nonlinear Lagrangian dual for integer programming[J]. Operations Research Letters,2002, 30: 401～407.

[4] Camerini P M, Fratta L, Maffioli F. On improving relaxation methods by modified gradient techniques[J]. Mathematical Programming Study, 1975, 3: 26～34.

[5] 周威, 金以慧. 利用模糊次梯度算法求解拉格朗日松弛對偶問題[J]. 控制與決策，2004, 19(11): 1213～1217.

[6] Sherali H D, Ulular O. A primal-dual conjugate subgradient algorithm for specially structured linear and convex programming problems [J]. Applied Mathematics and Optimization, 1989, 20: 193～221.

[7] 孫小玲，李端. 整數規劃[M]. 北京：科學出版社，2010.

[編輯]張濤

[文獻標志碼]A

[文章編號]1673-1409(2016)04-0001-05

[中圖分類號]O221

[作者簡介]何方國(1968-),男,博士,副教授，現主要從事圖論及優化方面的教學與研究工作；E-mail:hfg0118@126.com。

[基金項目]國家自然科學基金項目(71201064) 。

[收稿日期]2015-10-20

[引著格式]何方國.拉格朗日松弛對偶問題的一個改進次梯度算法[J].長江大學學報(自科版)，2016,13(4)：1～5.