拉格朗日松弛對(duì)偶問(wèn)題的一個(gè)改進(jìn)次梯度算法

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

?

拉格朗日松弛對(duì)偶問(wèn)題的一個(gè)改進(jìn)次梯度算法

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

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

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

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

1算法描述

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

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

(1)

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

(2)

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

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

(3)

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

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

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

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

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

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

λk+1=λk+skξk

(4)

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

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

(5)

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

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

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

(6)

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

λk+1=λk+skdk

(7)

這里，sk是合適的步長(zhǎng)。

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

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

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

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

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

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

即：

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

令：

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

(11)

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

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

(12)

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

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

步2求解拉格朗日松弛問(wèn)題:

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

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

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

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

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

2算法收斂性

定理2設(shè)λ*是拉格朗日對(duì)偶問(wèn)題(3)的最優(yōu)解，{λk}是迭代產(chǎn)生的序列，若算法采用式(12)選擇步長(zhǎng)，則有：

‖λ*-λ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‖是收斂的，對(duì)式(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成鈍角時(shí)，取θk> 0。由dk=ξk+θkdk-1,如圖2所示，由平行四邊形法則向量dk與dk-1的夾角小于向量ξk與dk-1的夾角；如果ξk與前一次迭代方向dk-1成銳角時(shí)，則迭代方向就是次梯度方向。故可以有效消除鋸齒現(xiàn)象。

3實(shí)例分析

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

(14)

(15)

(16)

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

(17)

圖3　一階樹(shù)的描述

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

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

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

(18)

拉格朗日對(duì)偶問(wèn)題為：

(19)

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

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

表1　節(jié)點(diǎn)數(shù)為20的5個(gè)完全圖計(jì)算結(jié)果

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

4結(jié)語(yǔ)

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

[參考文獻(xiàn)]

[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] 周威, 金以慧. 利用模糊次梯度算法求解拉格朗日松弛對(duì)偶問(wèn)題[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.

[編輯]張濤

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

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

[中圖分類號(hào)]O221

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

[基金項(xiàng)目]國(guó)家自然科學(xué)基金項(xiàng)目(71201064) 。

[收稿日期]2015-10-20

[引著格式]何方國(guó).拉格朗日松弛對(duì)偶問(wèn)題的一個(gè)改進(jìn)次梯度算法[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自科版)，2016,13(4)：1～5.