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

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

?

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

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

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

[關(guān)鍵詞]拉格朗日松弛算法；次梯度；優(yōu)化問題；對偶

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

1算法描述

考慮如下有約束的優(yōu)化問題：

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

(1)

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

(2)

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

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

(3)

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

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

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

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

定理1[7]設(shè)xλ是拉格朗日松弛問題(2)的最優(yōu)解，則ξ=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)

次梯度算法對解決不可微的目標(biāo)函數(shù)優(yōu)化問題有明顯的優(yōu)勢。當(dāng)目標(biāo)函數(shù)可微時，對于無約束問題次梯度法與梯度法具有同樣的搜索方向，但是次梯度法可以直接應(yīng)用于更廣泛的問題。

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

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

(6)

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

λk+1=λk+skdk

(7)

這里，sk是合適的步長。

圖1　平面π及向量關(guān)系

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

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

(λ*-λ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

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

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

即：

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

令：

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

(11)

這里，αk是一個適當(dāng)正的參數(shù)，取1 ≤ak<2。

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

(12)

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

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

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

并記最優(yōu)解為xk；

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

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

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

步6xk和λk分別為原問題和對偶問題的目標(biāo)解; 結(jié)束。

2算法收斂性

定理2設(shè)λ*是拉格朗日對偶問題(3)的最優(yōu)解，{λk}是迭代產(chǎn)生的序列，若算法采用式(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)確定，則算法可以有效的消除鋸齒現(xiàn)象。

證明由于鋸齒現(xiàn)象產(chǎn)生是相鄰迭代方向成鈍角，考慮到：

圖2　向量間的關(guān)系

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

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

3實例分析

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

(14)

(15)

(16)

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

(17)

圖3　一階樹的描述

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

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

則拉格朗日對偶函數(shù)為：

(18)

拉格朗日對偶問題為：

(19)

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

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

表1　節(jié)點數(shù)為20的5個完全圖計算結(jié)果

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

4結(jié)語

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

[參考文獻]

[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] 孫小玲，李端. 整數(shù)規(guī)劃[M]. 北京：科學(xué)出版社，2010.

[編輯]張濤

[文獻標(biāo)志碼]A

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

[中圖分類號]O221

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

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

[收稿日期]2015-10-20

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