基于重啟技術(shù)的加速鄰近梯度算法

趙靜

摘要：加速鄰近梯度法是在梯度法基礎(chǔ)上的一個改進，雖然效率比梯度法有明顯提高，但仍存在收斂軌跡出現(xiàn)往回迭代的情況。為了克服該缺點，提出了把重啟技術(shù)應(yīng)用在加速鄰近梯度法上的方法，并通過數(shù)值例子進行了比對，證明了該技術(shù)的有效性。

關(guān)鍵詞： 加速鄰近梯度法；固定重啟；自適應(yīng)重啟；優(yōu)化；參數(shù)

中圖分類號：TP301.6 文獻標(biāo)識碼：A 文章編號：1009-3044（2014）26-6190-04

Abstract： The accelerated proximal gradient method is upgraded from gradient method. Although the efficiency of the accelerated proximal gradient method is apparently better than that of the gradient method， the trajectory of the accelerated proximal gradient method may oscillate. To overcome this drawback， restart techniques are applied to the accelerated proximal gradient method. Numerical examples show that the techniques are useful.

Key words： accelerated proximal gradient method； fixed restart； adaptive restart； optimization； parameter

現(xiàn)實生活和工程技術(shù)領(lǐng)域中存在著大量的最優(yōu)化問題。求解最優(yōu)化問題的方法通常有很多種，見文獻[1]，主要包括一階收斂的梯度下降法、二階收斂的牛頓法、收斂率介于前兩者之間的 BFGS（Broyden，F(xiàn)letcher，Goldfrarb，Shanno）方法以及基于這些方法的各種修正方法。相比較而言，梯度法的優(yōu)點主要體現(xiàn)在簡單，但缺點是收斂速度比較慢；而牛頓法的特點是收斂速度很快，而所需要的條件苛刻，主要體現(xiàn)在求二階導(dǎo)數(shù)。

在實際應(yīng)用時，二階方法往往不適用于求解大規(guī)模問題，主要體現(xiàn)在兩個方面：（1） 通過以求解線性方程組求解得到下降方向，而求解線性方程組在遇上條件數(shù)較差的系數(shù)矩陣時仍然可能耗費較多的時間；（2） 二階導(dǎo)數(shù)根本就不存在。因此，隨著大規(guī)模問題求解的需要，近些年學(xué)術(shù)界出現(xiàn)了對一階最優(yōu)化方法研究的濃厚興趣，主要集中在讓一階方法保持原有優(yōu)點的基礎(chǔ)上利用一定的計算技術(shù)提高算法的效率這一方面。

然而，加速鄰近梯度法類似于梯度法，迭代軌跡會呈現(xiàn)出“波紋”，即在迭代過程中會出現(xiàn)反復(fù)的情況。雖然可以通過參數(shù)的選取獲得較好的算法效率，但是這需要取決于對參數(shù)的優(yōu)化估計。換句話說，選擇好的參數(shù)q可以一定程度上消除迭代過程反復(fù)的現(xiàn)象，獲得較好的收斂效果。

2 重啟技術(shù)

為克服加速鄰近梯度法的缺點，使得算法的效率不依賴于參數(shù)q的選擇，Brendan和 Emmanuel提出了重啟技術(shù)[7]。 所謂重啟，是指在滿足某個條件時，以此次迭代產(chǎn)生的最后一個點作為新的迭代點重新啟動。重啟技術(shù)分為兩種：（1） 固定重啟：以固定的迭代次數(shù)為重啟的標(biāo)準(zhǔn)；（2） 自適應(yīng)重啟：當(dāng)?shù)?dāng)向壞方向發(fā)展時就重新啟動。在加速鄰近梯度法的基礎(chǔ)上，加入重啟方法之后，其算法效率可以進一步提升。 特別地，自適應(yīng)重啟加速鄰近梯度法可以不依賴于對參數(shù)的估計。該方法可用于求解不適用二階方法的大規(guī)模問題。

不論是加速鄰近梯度法還是加入固定重啟技術(shù)之后，如果要獲得較好的算法效率就必須依賴對參數(shù)的估計。兩者本質(zhì)上區(qū)別并不是特別大，即使加入固定重啟后的加速鄰近梯度法存在微弱的優(yōu)勢。

自適應(yīng)重啟是根據(jù)算法的迭代情況自動確定何時重啟算法，可以有效地克服這個缺點。根據(jù)條件的不同，自適應(yīng)重啟可分為兩種上述表中APG、FRAPG、ARAPG分別代表加速鄰近梯度法、基于固定重啟技術(shù)的加速鄰近梯度法以及基于自適應(yīng)重啟技術(shù)的加速鄰近梯度法。q表示APG的參數(shù)，k表示FRAPG重啟的迭代步數(shù)間隔，F(xiàn)表示基于函數(shù)重啟，G表示基于梯度重啟。

數(shù)值結(jié)果表明，所有算法隨問題規(guī)模的增大所耗費的計算機時間迅速增加。加速鄰近梯度法嚴(yán)重依賴于對參數(shù)q的選擇，特別當(dāng)q=0時算法的速度很慢?；诠潭ㄖ貑⒓夹g(shù)的加速鄰近梯度法相對于未加入重啟技術(shù)的加速鄰近梯度法有一定的速度優(yōu)勢，但是其也依賴于重啟的迭代步數(shù)間隔?；谧赃m應(yīng)重啟技術(shù)的加速鄰近梯度法存在非常明顯的速度優(yōu)勢，其特點迭代次數(shù)少，費時少。特別地，基于梯度重啟的加速鄰近梯度法相較于基于函數(shù)重啟的加速鄰近梯度法迭代次數(shù)和費時更少。

4 結(jié)束語

本文利用加速鄰近梯度法及其重啟技術(shù)求解了一類無約束問題，并通過數(shù)值例子展示了算法的實際計算效果。結(jié)果表明，基于重啟技術(shù)的加速鄰近梯度法在計算時間上數(shù)倍優(yōu)于未加入重啟技術(shù)的加速鄰近梯度法。特別地，基于自適應(yīng)重啟技術(shù)的加速鄰近梯度法優(yōu)勢非常明顯，其特點迭代次數(shù)少，費時少，而且不需要依賴于參數(shù)的選擇，適合大規(guī)模問題的計算。

參考文獻：

[1] 陳寶林.最優(yōu)化理論與算法（第2版）[M].北京：清華大學(xué)出版社，2005.

[2] Nesterov Y.A method of solving a convex programming problem with convergence rate O（1/k2） [J].Soviet Mathematics Doklady，1983，（27）：372-376.

[3] Tseng P.On accelerated proximal gradient methods for convex-concave optimization [DB/OL]. http：//pages.cs.wisc.edu/～brecht/cs726docs/Tseng.APG.-pdf，2008.

[4] Zuo W，Lin Z.A generalized accelerated proximal gradient approach for total-variation-based image restoration[J].IEEE Transactions on Image Processing，2011，20（10）：2748-2759.

[5] Dennis J，Schnabel R.Numerical Methods for Unconstrained Optimization and Nonlinear Equations[M].U.S.： Society for Industrial & Applied Mathematics，1987.

[6] Becker R，Candès E，Grant M.Templates for convex cone problems with applications to sparse signal recovery[J].Mathematical Programming Computation.2011，3（3）：165-218.

[7] ODonoghue B，Candès E.Adaptive restart for accelerated gradient schemes[DB/OL].arXiv preprint arXiv：1204.3982，2012.

[8] Andrei N.An unconstrained optimization test functions collection[J]. Advanced Modeling and Optimization，2008，10（1）：147-161.