趙靜

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

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

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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í)生活和工程技術(shù)領(lǐng)域中存在著大量的最優(yōu)化問(wèn)題。求解最優(yōu)化問(wèn)題的方法通常有很多種，見文獻(xiàn)[1]，主要包括一階收斂的梯度下降法、二階收斂的牛頓法、收斂率介于前兩者之間的 BFGS（Broyden，F(xiàn)letcher，Goldfrarb，Shanno）方法以及基于這些方法的各種修正方法。相比較而言，梯度法的優(yōu)點(diǎn)主要體現(xiàn)在簡(jiǎn)單，但缺點(diǎn)是收斂速度比較慢；而牛頓法的特點(diǎn)是收斂速度很快，而所需要的條件苛刻，主要體現(xiàn)在求二階導(dǎo)數(shù)。

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

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

2 重啟技術(shù)

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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.