🚀 優質資源分享 🚀

學習路線指引（點擊解鎖）知識定位人群定位

🧡 Python實戰微信訂餐小程序 🧡	進階級	本課程是python flask+微信小程序的完美結合，從項目搭建到騰訊云部署上線，打造一個全棧訂餐系統。
💛Python量化交易實戰💛	入門級	手把手帶你打造一個易擴展、更安全、效率更高的量化交易系統

我們在上一篇博客《數值優化：算法分類及收斂性分析基礎》介紹了數值優化算法的歷史發展、分類及其收斂性/復雜度分析基礎。本篇博客我們重點關注一階確定性優化算法及其收斂性分析。

1 梯度下降法

1.1 算法描述

梯度下降法[1]是最古老的一階方法，由Cauchy在1847年提出。
梯度下降法的基本思想是：最小化目標函數在當前迭代點處的一階泰勒展開，從而近似地優化目標函數本身。具體地，對函數f:Rn→Rf:Rn→Rf:\mathbb{R}^n \rightarrow \mathbb{R}，將其在第ttt輪迭代點wtwtw^t處求解下述問題：

minwf(w)=minw[f(wt)+?f(wt)T(w?wt)]minwf(w)=minw[f(wt)+?f(wt)T(w?wt)]\underset{w}{\text{min}}f(w) = \underset{w}{\text{min}} \left[ f(w^t) + \nabla f(w^t)T (w-w^t) \right]
上式右端關于自變量www是線性的，并且使得?f(wt)Tw?f(wt)Tw\nabla f(w^t)Tw最小的方向與梯度?f(wt)?f(wt)\nabla f(w^t)的方向相反。于是梯度下降法的更新規則如下：

wt+1=wt?η?f(wt)wt+1=wt?η?f(wt)w^{t+1} = w^t - \eta \nabla f(w^t)
其中η>0η>0\eta>0是步長，也常被稱作學習率。

梯度下降法描述如下：

1.2 收斂性分析

針對不同性質的目標函數，梯度下降法具有不同的收斂速率。由于梯度下降法只適用于梯度存在的函數（沒有梯度需要考慮使用次梯度的方法），這里考慮梯度下降法對于光滑凸函數和光滑強凸函數的收斂速率。

光滑凸函數收斂性 假設目標函數f:Rd→Rf:Rd→Rf: \mathbb{R}^d \rightarrow \mathbb{R}是凸函數，且ββ\beta-光滑，當步長η=1βη=1β\eta = \frac{1}{\beta}時，梯度下降法具有O(1t)O(1t)\mathcal{O}(\frac{1}{t})的次線性收斂速率：

f(wt)?f(w?)?2β∥w0?w?∥2tf(wt)?f(w?)?2β‖w0?w?‖2tf(w^t) - f(w^*) \leqslant \frac{2\beta \lVert w^0 - w^*\rVert2}{t}
光滑強凸函數收斂性 假設目標函數f:Rd→Rf:Rd→Rf: \mathbb{R}^d \rightarrow \mathbb{R}是αα\alpha-強凸函數，且ββ\beta-光滑，當步長η=1βη=1β\eta = \frac{1}{\beta}時，梯度下降法具有O(e?tQ)O(e?tQ)\mathcal{O}(e^{-\frac{t}{Q}})的線性收斂速率：

f(wt)?f(w?)?β2e?tQ∥w0?w?∥2f(wt)?f(w?)?β2e?tQ‖w0?w?‖2f(w^t) - f(w^*) \leqslant \frac{\beta}{2}e^{-\frac{t}{Q}} \lVert w^0 - w^*\rVert2
其中Q=βαQ=βαQ = \frac{\beta}{\alpha}，一般被稱為條件數。

通過以上兩個定理可知，強凸性質會大大提高梯度下降法的收斂速率。進一步地，強凸性質越好(即αα\alpha越大)，條件數QQQ越小，收斂越快。

而光滑性質在凸和強凸兩種情形下都會加快梯度下降法的收斂速率，即ββ\beta越小（強凸情景下，條件數QQQ越小），收斂越快。可以說凸情形中的光滑系數和強凸情形中的條件數在一定程度上刻畫了優化問題的難易程度。

2 投影次梯度下降法

2.1 算法描述

梯度下降法有兩個局限，一是只適用于無約束優化問題，二是只適用于梯度存在的目標函數。投影次梯度法[2]可以解決梯度下降法的這兩個局限性。

投影次梯度下降法相比梯度下降法，具有次梯度選擇和約束域投影兩個特性：

• 次梯度選擇 選取當前迭代點wtwtw^t的次梯度集合?f(wt)?f(wt)\partial f(w^{t)中隨機選取一個次梯度gtgtg}t，按照梯度下降更新vt+1=vt?ηgtvt+1=vt?ηgtv^{t+1} = v^t - \eta g^t
  得到vt+1vt+1v^{t+1}。
• 約束域投影 確定vt+1vt+1v^{{t+1}是否屬于約束域WW\mathcal{W}，如果屬于則直接將其做為wt+1wt+1w}{t+1}；如果不屬于，則需尋找vt+1vt+1v^{{t+1}到約束域WW\mathcal{W}的投影，也就是WW\mathcal{W}中離vt+1vt+1v}{t+1}最近的點。如下圖所示：
  
  尋找投影的過程可以經由投影映射ΠW(???)ΠW(???)\Pi_{\mathcal{W}}(\space \cdot \space)來完成：

wt+1=ΠW(vt+1)=arg minv∈W∥v?vt+1∥wt+1=ΠW(vt+1)=arg minv∈W‖v?vt+1‖\begin{aligned}
w^{t+1} &= \Pi_{\mathcal{W}}(v^{t+1}) \
&= \underset{v\in \mathcal{W}}{\text{arg min}}\lVert v - v^{t+1}\rVert
\end{aligned}
投影次梯度下降法描述如下：

2.2 收斂性分析

在一定步長的選取規則下，投影次梯度法是收斂的，并且收斂速度也依賴于目標函數的凸性和光滑性。

對于ββ\beta-光滑的凸/強凸函數，當步長為1β1β\frac{1}{\beta}時，投影次梯度下降法的收斂率和梯度下降法相同，對于凸函數是O(1t)O(1t)\mathcal{O}(\frac{1}{t})，強凸函數是O（e?tQ）O（e?tQ）\mathcal{O}（e^{-\frac{t}{Q}}）。

不過，由于投影次梯度算法適用于有次梯度存在的目標函數，因而不僅適用于光滑函數的優化，也適用于Lipschitz連續函數的優化。對于Lipschitz連續函數，投影次梯度下降法收斂。對于凸函數，步長η=O(1t√)η=O(1t)\eta = \mathcal{O}(\frac{1}{\sqrt{t}})時，收斂速率為O(1t√)O(1t)\mathcal{O}(\frac{1}{\sqrt{t}})；對于強凸函數，步長η=O(1t)η=O(1t)\eta = \mathcal{O}(\frac{1}{t})時，收斂速率為O(1t)O(1t)\mathcal{O}(\frac{1}{t})。可以看到其收斂速率在凸和強凸兩種情形相比光滑函數顯著降低，都是次線性。

3 近端梯度下降法

3.1 算法描述

近端梯度法[3]是投影次梯度法的一種推廣，適用于如下形式的部分不可微的凸目標函數的優化問題：

minw∈Wf(w)=l(w)+R(w)minw∈Wf(w)=l(w)+R(w)\underset{w \in \mathcal{W}}{\text{min}} f(w) = l(w) + R(w)
其中l(w)l(w)l(w)是其中的可微凸函數部分，R(w)R(w)R(w)是不可微的凸函數（例如L1L1L_1正則項）。算法的基本思想是先按照可微的lll函數進行一步梯度下降更新：

vt+1=wt?ηt?l(wt)vt+1=wt?ηt?l(wt)v^{t+1} = w^t - \eta^t \nabla \mathcal{l}(w^t)
然后再經過近端映射proxR(???)proxR(???)\text{prox}_R(\space \cdot \space)做為本輪最終的迭代更新：

wt+1=proxR(vt+1)=arg minv∈W[R(v)+12∥v?vt+1∥2]wt+1=proxR(vt+1)=arg minv∈W[R(v)+12‖v?vt+1‖2]\begin{aligned}
w^{t+1} &= \text{prox}_{R}(v^{t+1}) \
&= \underset{v\in \mathcal{W}}{\text{arg min}}\left[ R(v) + \frac{1}{2}\lVert v - v^{t+1}\rVert2 \right]
\end{aligned}
近端梯度下降法描述如下：

3.2 收斂性分析

如下定理所示，近端梯度下降法可以達到線性收斂速率。

近端梯度下降法收斂性 假設目標函數中的lll函數是RdRd\mathbb{R}^{d上的αα\alpha-強凸函數，且ββ\beta-光滑；RRR函數是RdRd\mathbb{R}}d上的凸函數， 當步長η=1βη=1β\eta = \frac{1}{\beta}時，近端梯度下降法具有O(e?tQ)O(e?tQ)\mathcal{O}(e^{-\frac{t}{Q}})的線性收斂速率：

f(wt)?f(w?)?β2e?tQ∥w0?w?∥2f(wt)?f(w?)?β2e?tQ‖w0?w?‖2f(w^t) - f(w^*) \leqslant \frac{\beta}{2}e^{-\frac{t}{Q}} \lVert w^0 - w^*\rVert2
其中Q=βαQ=βαQ = \frac{\beta}{\alpha}為lll函數的條件數。

4 Frank-Wolfe算法

4.1 算法描述

Frank-Wolfe算法[4]是投影次梯度下降法的另一個替代算法。投影次梯度算法雖然適用于有約束優化問題，但是如果投影的計算很復雜，投影次梯度下降的效率將會稱為瓶頸。為了解決此問題，不同于投影次梯度下降法中先進行梯度下降再對約束域進行投影的做法，Frank-Wolfe算法在最小化目標函數的泰勒展開時就將約束條件考慮進去，直接得到滿足約束的近似最小點，即：

vt=argminv∈W[f(wt)+?f(wt)T(v?wt)]=argminv∈W?f(wt)Tvvt=argminv∈W[f(wt)+?f(wt)T(v?wt)]=argminv∈W?f(wt)Tv\begin{aligned}
v^t & = \text{argmin}_{v\in\mathcal{W}}\left[ f(w^t) + \nabla f(w^t)T(v - w^t) \right]\
& = \text{argmin}_{v\in \mathcal{W}} \nabla f(w^t)Tv
\end{aligned}
為了使算法的解更穩定，Frank-Wolfe算法將求解上述子問題得到的vtvtv^{t與當前狀態wtwtw}t做線性加權：

wt+1=(1?γt)wt+γtvtwt+1=(1?γt)wt+γtvtw^{t+1} = (1-\gamma^t)wt + \gamma^tvt
如下圖所示：

\

Frank-Wolfe算法描述如下：

4.2 收斂性分析

Frank-Wolfe算法收斂速率如下列定理所示：

Frank-Wolfe法收斂性 假設目標函數中的fff函數是RdRd\mathbb{R}^{d上的凸函數，且ββ\beta-光滑，當加權系數γt=2t+1γt=2t+1\gamma}t = \frac{2}{t+1}時，Frank-Wolfe算法具有O(1t)O(1t)\mathcal{O}(\frac{1}{t})的次線性收斂速率：

f(wt)?f(w?)?2βD2tf(wt)?f(w?)?2βD2tf(w^t) - f(w^*) \leqslant \frac{2\beta D^2}{t}
其中D=supw,v∈W∥w?v∥D=supw,v∈W‖w?v‖D = \underset{w, v \in \mathcal{W}}{\text{sup}}\lVert w - v \rVert。
由于Frank-Wolfe算法的收斂速率和投影次梯度下降法相同，可以依據要解決問題中的投影計算是否困難，在兩種算法中選擇一種使用。

5 Nesterov加速法

5.1 算法描述

考慮以上所有的一階算法。在Lipschitz連續的條件下，梯度下降法達到了一階算法的收斂速率下界。然而對于光滑函數，一階方法的收斂速率的下界小于梯度下降法的收斂速率。一階方法在凸情形下的收斂率下界為O(1t2)O(1t2)\mathcal{O}(\frac{1}{t^{2})，強凸情形下的下界為O(e?tQ√)O(e?tQ)\mathcal{O}(e}{-\frac{t}{\sqrt{Q}}})；而梯度下降法在凸情形下的收斂率為O(1t)O(1t)\mathcal{O}(\frac{1}{t})，強凸情形下的收斂率為O(e?tQ)O(e?tQ)\mathcal{O}(e^{-\frac{t}{Q}})。這說明我們可以針對光滑函數設計收斂速率更快的一階方法。

Nesterov在1983年對光滑度目標函數提出了加快一階優化算法收斂的方法[5]。我們這里以梯度下降法為例，介紹Nesterov加速法的具體實現。
Nesterov算法的基本原理如下圖所示：

\

當任意時刻ttt，對當前狀態wtwtw^{t進行一步梯度迭代得到輔助變量vt+1vt+1v}{t+1}：

vt+1=wt?ηt?f(wt)wt+1vt+1=wt?ηt?f(wt)wt+1v^{t+1} = w^t - \eta^t \nabla f(w^t)
w^{t+1}
然后將新的輔助變量和上一輪迭代計算的輔助變量vtvtv^{t做線性加權，做為第t+1t+1t+1輪迭代的參數wt+1wt+1w}{t+1}。對于凸和強凸的目標函數，線性加權系數有所不同。

具體地，對于強凸的目標函數，加權規則如下：

wt+1=(1+γt)vt+1?γtvtwt+1=(1+γt)vt+1?γtvtw^{t+1} = (1 + \gamma^t)v{t+1} - \gamma^t v^t
其中γt=1?Q√1+Q√γt=1?Q1+Q\gamma^t = \frac{1-\sqrt{Q}}{1 + \sqrt{Q}}，QQQ為條件數。

對于凸的目標函數，加權規則如下：

wt+1=(1?γt)vt+1+γtvtwt+1=(1?γt)vt+1+γtvtw^{t+1} = (1 - \gamma^t)v{t+1} + \gamma^t v^t
其中γt=1?λtλt+1γt=1?λtλt+1\gamma^t = \frac{1 - \lambda^t}{\lambda{t+1}}，λ0=0λ0=0\lambda^0 = 0, λt=1+1+4(λt?1)2√2λt=1+1+4(λt?1)22\lambda^t = \frac{1 + \sqrt{1 + 4{(\lambda^{t-1})}2}}{2}。

Nesterov加速算法描述如下：

5.2 收斂性分析

Nesterov證明了用以上方法加速之后的梯度下降法的收斂速率可以達到針對光滑目標函數的一階方法的收斂速率下界:

光滑凸函數收斂性 假設目標函數f:Rd→Rf:Rd→Rf: \mathbb{R}^d \rightarrow \mathbb{R}是凸函數，并且ββ\beta-光滑，當步長η=1βη=1β\eta = \frac{1}{\beta}時，Nesterov加速法能夠將收斂速率提高到O(1t2)O(1t2)\mathcal{O}({\frac{1}{t^2}})（不過仍是次線性收斂速率）：

f(wt)?f(w?)?2β∥w0?w?∥2t2f(wt)?f(w?)?2β‖w0?w?‖2t2f(w^t) - f(w^*) \leqslant \frac{2\beta \lVert w^0 - w^*\rVert2}{t^2}
光滑強凸函數收斂性 假設目標函數f:Rd→Rf:Rd→Rf: \mathbb{R}^d \rightarrow \mathbb{R}是αα\alpha-強凸函數，并且ββ\beta-光滑，當步長η=1βη=1β\eta = \frac{1}{\beta}時，Nesterov加速法能夠將收斂速率提高到e?tQ√e?tQ\mathcal{e^{-\frac{t}{\sqrt{Q}}}}（不過仍是線性收斂速率）：

f(wt)?f(w?)?α+β2e?tQ√∥w0?w?∥2f(wt)?f(w?)?α+β2e?tQ‖w0?w?‖2f(w^t) - f(w^*) \leqslant \frac{\alpha + \beta}{2}e^{-\frac{t}{\sqrt{Q}}} \lVert w^0 - w^*\rVert2
其中Q=βαQ=βαQ = \frac{\beta}{\alpha}為條件數。

6 坐標下降法

6.1 算法描述

坐標下降法[6]是另外一種常見的最小化實值函數的方法。其基本思想是，在迭代的每一步，算法選擇一個維度，并更新這一維度，其它維度的參數保持不變；或者將維度分為多個塊，每次只更新某塊中的維度，其它維度保持不變。坐標下降法的更新公式如下：

wt+1j=arg minz∈Wjf(wt1,…,wtj?1,z,wtj+1,…,wtd)wjt+1=arg minz∈Wjf(w1t,…,wj?1t,z,wj+1t,…,wdt)w^{t+1}_j = \underset{z\in \mathcal{W}_j}{\text{arg min}}f(w^t_1,…,wt_{j-1}, z, w^{t_{j+1},…,w}t_d)
其中，WjWj\mathcal{W}_j為第jjj個維度塊的約束域。

對于維度的選擇，坐標下降法一般遵循以下本征循環選擇規則（Essential Cyclic Rule）：存在一個常數r?dr?dr\geqslant d，使得對任意的sss，對于每一個維度jjj，在第sss輪和第s+r?1s+r?1s + r - 1輪之間都至少選擇一次。最常見的方法是循環選擇規則，即對于任意j=1,…,dj=1,…,dj=1,…,d，分別在第j,d+j,2d+j,…j,d+j,2d+j,…j, d + j, 2d + j,…次算法迭代中選擇維度jjj（即每隔ddd輪選擇一次）。

坐標下降法的算法描述如下所示：

6.2 收斂性分析

可以證明對于強凸并且光滑的目標函數，循環坐標下降法具有線性的收斂速率[6]。

參考

• [1] Cauchy A. Méthode générale pour la résolution des systemes d’équations simultanées[J]. Comp. Rend. Sci. Paris, 1847, 25(1847): 536-538.

• [2]
  Levitin E S, Polyak B T. Constrained minimization methods[J]. USSR Computational mathematics and mathematical physics, 1966, 6(5): 1-50.

• [3] Parikh N, Boyd S. Proximal algorithms[J]. Foundations and Trends in optimization, 2014, 1(3): 127-239.

• [4] Frank M, Wolfe P. An algorithm for quadratic programming[J]. Naval research logistics quarterly, 1956, 3(1‐2): 95-110.

• [5] Nesterov Y E. A method for solving the convex programming problem with convergence rate O (1/k^ 2)[C]//Dokl. akad. nauk Sssr. 1983, 269: 543-547.

• [6]
  Wright S J. Coordinate descent algorithms[J]. Mathematical Programming, 2015, 151(1): 3-34.

  • 1 梯度下降法

• 1.1 算法描述

• 1.2 收斂性分析

• 2 投影次梯度下降法

• 2.1 算法描述

• 2.2 收斂性分析

• 3 近端梯度下降法

• 3.1 算法描述

• 3.2 收斂性分析

• 4 Frank-Wolfe算法

• 4.1 算法描述

• 4.2 收斂性分析

• 5 Nesterov加速法

• 5.1 算法描述

• 5.2 收斂性分析

• 6 坐標下降法

• 6.1 算法描述

• 6.2 收斂性分析

• 參考

  __EOF__

  [外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Wd9NuL9B-1655009379066)(https://blog.csdn.net/orion-orion)]獵戶座 - 本文鏈接： https://blog.csdn.net/orion-orion/p/16367015.html

• 關于博主： 本科CS系蒟蒻，機器學習半吊子，并行計算混子。
• 版權聲明： 歡迎您對我的文章進行轉載，但請務必保留原始出處哦(^▽)。
• 聲援博主： 如果您覺得文章對您有幫助，可以點擊文章右下角**【[推薦](javascript:void(0)😉】**一下。

總結

以上是生活随笔為你收集整理的数值优化：经典一阶确定性算法及其收敛性分析的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。