無約束凸最佳化|梯度下降、最速下降、牛頓下降和各種分析

作者：由 anarion 發表于書法時間：2020-07-31

本文使用 Zhihu On VSCode 創作併發布

本文是我閱讀Boyd凸最佳化第九章的筆記，更多是給自己留個印象，而不是寫教程讓別人看懂。如果你的知識背景和我相似，你應該可以暢快地閱讀，否則可能有困難。你沒必要因此懷疑自己的能力，數學本來就是很複雜很細節的東西，沒有必要掌握每個細節。

本文思維導圖：

思維導圖

本文md文件連結：Anblogs

前置知識

對偶範數（Dual Norm）

定義這種範數如下：

$\|z\|_*=\sup_z\{z^Tx\;|\;\|x\|\le1\}$

這是對於一個給定的範數定義的，這個範數用來限制引數

的取值，

$\|x\|\le1$

。可以認為，對偶範數是對於一個任意範數定義的。衡量了在一個「對偶空間」中，向量

能夠向前「延伸」的最遠距離。

有一個很有用的結論。若原範數為

階範數，它的對偶範數為

階範數，則有

。

這個結論很好證明，利用「柯西不等式」的推廣「Holder不等式」：

$\|z\|_q\ge\|x\|_p\|z\|_q\ge z^Tx$

強凸函式（Strong Convexity）

我們定義一些函式為「強凸」的，這些函式滿足

$mI\preceq\nabla^2f(x)\preceq MI,m>0$

，也就是矩陣

$\nabla^2f(x)-mI$

和

$MI-\nabla^2 f(x)$

是正定矩陣。

對於任意函式

，若滿足中值定理的條件，有：

$f(y)=f(x)+\nabla f(x)^T(y-x)+\frac{1}{2}(y-x)^T\nabla^2f(z)(y-x)$

其中

$z\in[x,y]$

。帶入「強凸」的條件，得到強凸函式一定滿足的不等式：

$f(y)\ge f(x)+\nabla f(x)^T(y-x)+\frac{m}{2}||y-x||_2^2$

其中使用了不等式

$x^T(\nabla^2f(x)-mI)x\ge0$

。可以理解為，

強凸函式就是滿足這個不等式的函式

。

不等式右邊相對

取得最小值時，

的取值為

$\tilde y=x-\frac{1}{m}\nabla f(x)$

，這可以由簡單的求導得到，也可以作為「二次函式」的結論記住。

帶入

$\tilde y$

的值得到一個新的不等式，不等式右邊和

無關：

$f(y)\ge f(x)-\frac{1}{2m}||\nabla f(x)||_2^2$

至此，為最小值找到了一個下界，

$p^*\ge f(x)-\frac{1}{2m}||\nabla f(x)||_2^2$

。

把下界寫得更明顯一些，若梯度存在明顯上界

$||\nabla f(x)||_2^2\le(2m\epsilon)$

，則帶入可得更明顯的不等式：

$f(x)-p^*\le\epsilon$

可以透過相同的方法得到最優解

的一個上界：

$\begin{align}p^*&=f(x^*)\ge f(x)+\nabla f(x)^T(x^*-x)+\frac{m}{2}||x^*-x||^2_2\\&\ge f(x)-||\nabla f(x)||_2||x^*-x||_2+\frac{m}{2}||x^*-x||^2_2\end{align}$

利用

$p^*-f(x)\le0$

，簡單移項之後：

$\frac{m}{2}||x^*-x||_2^2-||\nabla f(x)||_2||x^*-x||_2=||x^*-x||_2(\frac{m}{2}||x^*-x||_2-||\nabla f(x)||_2)\le0$

得到了最優解的上界

$||x-x^*||_2\le\frac{2}{m}||\nabla f(x)||_2$

。

同理可以根據上界證明最小值的上界：

$p^*\le f(x)-\frac{1}{2M}||\nabla f(x)||_2^2$

廣義的下降演算法

最廣泛的下降演算法是，選擇一個「方向」

$\Delta x^{(k)}$

，計算得到

$x^{(k+1)}=x^{(k)}+t^{(k)}\Delta x^{(k)}$

，使得

$f(x^{(k+1)})<f(x^{(k)})$

成立。

根據凸函式的性質，我們知道，

$\Delta x$

必須滿足

$\nabla f(x^{(k)})^T\Delta x^{(k)}<0$

。這是由於，對於凸函式，當

$f(y)\ge f(x^{(k)})$

成立，

$\nabla f(x^{(k)})^T(y-x^{(k)})\ge0$

必成立（必要條件）。

我們於是有了最廣泛的「下降」演算法的流程：

從某起始點開始。

確定一個下降方向

$\Delta x^{(k)}$

。

解一個一元最佳化問題，確定下降步長

$t^{(k)}=\arg\min_tf(x^{(k)}+t\Delta x^{(k)})$

。

計算得到新的

$x^{(k+1)}$

，迴圈至收斂。

這裡有兩個可以變化的地方，分別是「選擇

$\Delta x$

的方法」和「選擇

的方法」。以下討論選擇

的方法，相對沒那麼複雜。選擇

$\Delta x$

的方法不同，會形成非常不同的演算法，在後文中更詳細講解。

精確查詢

最佳化問題

$t^{(k)}=\arg\min_t f(x^{(k)}+t\Delta x^{(k)})$

通常可以直接求解，不論如何，一元的最佳化問題也簡單很多。

用常見的線性迴歸損失函式舉例子，

$L(w)=||w^Tx^{(i)}-y^{(i)}||_2^2$

。帶入最佳化問題：

$\frac{d}{dt}L(w+t\Delta w)=\frac{dL}{d(w+t\Delta w)}\frac{d(w+t\Delta w)}{dt}=L$

令為0，得到最終結果

$t^*=(y^{(i)}-w^Tx^{(i)})/\Delta w^T x^{(i)}$

。其中

$x^{(i)},y^{(i)}$

可以「隨機」從資料集中取得，做的就是「隨機梯度下降」。

回溯法（Backtracking）

回溯法是另一種找

$t^{(k)}$

的方法，它在每一步迭代找的是「近似」的最優

$t^{(k)}$

，而不是「精確」的

$t^{(k)}$

。

將

初始化為一個較大的數字，如1。準備常量

$\alpha\in(0,0,5),\beta\in(0,1)$

，當滿足

$f(x+t\Delta x)>f(x)+\alpha t\nabla f(x)^T\Delta x$

時，不斷縮小

$t:=\beta t$

。

Backtrack

演算法的執行可以參考上圖。

$f(x+t\Delta x)$

是個一元函式，我們知道它在

處的切線可以由

$y=f(x)+t\nabla f(x)^T\Delta x$

表示，如圖中切線。現在切線的斜率上乘一個比1小的數字

$\alpha$

，得到「割線」，沒有切線那麼「斜」。

演算法啟動時，我們嘗試性沿著

$\Delta x$

方向走

這麼長的距離。我們想要控制

，防止走得太遠反而令函式值增大。以「割線」和函式的交點為分界，要是

過大，就縮小

$t=\beta t$

，控制

，保證演算法收斂。

在大多數情況下，「回溯」和「精確查詢」的效能相差不遠。

梯度下降（Gradient Descent）

梯度下降演算法，只是眾多下降演算法中的一個。這些演算法之間的大區別在於「選擇

$\Delta x$

」不同，而「選擇

」的操作常常獨立於此討論。

梯度下降十分簡單，就是選擇

$\Delta x=-\nabla f$

，選擇下降的方向為梯度的反方向。這似乎是理所當然的選擇，還有什麼比梯度的反方向更好呢？當然是可以有的，我們後面再說。

這裡就沒必要列出梯度下降的流程了，只是上面「廣義的下降演算法」流程做了一些小改變而已。

證明收斂

這裡對梯度下降應用經典的數學分析，證明演算法的正確性。如果你覺得這樣書卷氣太濃，可以跳過至後文更重要的部分。

假設目標函式是「強凸函式」，前文有推導強凸函式的有關結論，如果你剛才跳過了可以回去看看，或者直接跳過本證明。

記一次迭代中的函式

$\tilde f(t)=f(x-t\nabla f(x))$

，用於在每次迭代中確定

。則根據強凸函式的性質：

$\tilde f(t)\le f(x)-t||\nabla f(x)||_2^2+\frac{M}{2}t^2||\nabla f(x)||_2^2$

不等式右邊的最小值在

的時候取得，這是「二次函式」的簡單結論。於是得到一個更緊的上界：

$\tilde f(t)\le f(x)-\frac{1}{2M}||\nabla f(x)||_2^2$

若使用「精確查詢」確定

當使用精確查詢確定

時，每次迭代得到一個

$t_{exact}$

，是關於

的最佳化問題的最優解。則每次迭代更新值

$x^{(k+1)}$

依舊滿足不等式：

$f(x^{(k+1)})=\tilde f(t_{exact})\le f(x^{(k)})-\frac{1}{2M}||\nabla f(x^{(k)})||_2^2$

兩邊同時減去最小值

，並且和不等式

$||\nabla f(x)||_2^2\ge2m(f(x)-p^*)$

聯立：

$f(x^{(k+1)})-p^*\le f(x)-p^*-\frac{1}{2M}||\nabla f(x^{(k)})||_2^2\le f(x^{(k)})-p^*-\frac{1}{2M}(2m(f(x^{(k)})-p^*))$

整理一下：

$f(x^{(k+1)})-p^*\le(1-\frac{m}{M})(f(x^{(k)})-p^*)\le(1-\frac{m}{M})^k(f(x^{(0)})-p^*)$

要確定計算精度為

$\epsilon$

，也就是

$f(x^{(k)})-p^*\le\epsilon$

，只需要帶入上面的不等式，令

$\epsilon$

和不等式右邊相等，得到

的取值：

$\hat k=-\frac{\log f(x^{(0)}-p^*)-\log\epsilon}{\log(1-\frac{m}{M})}$

若使用「回溯」確定

這裡不詳細展開過程了，和上面類似，只是在不等式處有小小修改。給出最終結果：

$f(x^{(k+1)})-p^*\le c^k(f(x^{(0)})-p^*),c=1-\min\{2m\alpha,2\beta\alpha m/M\}<1$

梯度下降的問題

梯度下降對於變數的「尺度」（Scale）有很大依賴，也可以說是對「座標系」有很大依賴。要是座標系的尺度（Scale）沒有選擇好，演算法依舊會收斂，但是收斂的非常慢（

），使得演算法失去價值。

具體看下圖：

zigzag

這樣的「等高線圖」（Contour）是令

取得不同值時解出

得到的，我在後文中將「等高線的形狀」描述為「原始空間的形狀」或「取值的形狀」或「目標函式形狀」。這裡左圖的「形狀」是個「橢圓」，右圖是個「正圓」。

兩個變數尺度差別很大時，可能出現左圖這樣zigzag彎彎繞的情況。差別不大時，幾乎只需要一次迭代，一次對

的最佳化問題，就可以得到答案。

以下以具體例子看看這個問題。

條件數（Condition Number）

假設目標函式為

$f(x)=c^Tx-\sum_{i=1}^m\log(b_i-a_i^Tx)$

。為了表現出不同變數尺度對演算法的影響，做一個換元

$x=T\bar x$

，其中矩陣

為對角矩陣，元素從左上到右下依次為

$1,\gamma^{1/n},\gamma^{2/n},…,\gamma^{(n-1)/n}$

。目標函式變為

$\bar f(\bar x)=c^TT\bar x-\sum_{i=1}^m\log(b_i-a_i^TT\bar x)$

。

對這個函式使用梯度下降演算法，得到迭代次數和

$\gamma$

的關係如圖：

尺度關係

迭代次數取得最小值時，就是各個變數沒有縮放的時候！一旦

$\gamma$

不為0，迭代次數就會劇烈增加，因為

$\gamma$

導致的縮放指數級變化！

最速下降（Steepest Descent）

改變「選擇

$\Delta x$

」的方法，就得到不同的演算法。「最速下降」的概念應該是比「梯度下降」更大的，梯度下降可以看做最速下降的一種特殊情況。如果你對數學推理很反感，可以看看第一個h2標題，感受梯度下降如何與最速下降聯絡。

選擇

$\Delta x=-\nabla f$

似乎理所當然，最速下降用的是更加理所當然的直覺：

每次確定

$\Delta x$

的時候，保證

$\Delta x$

使得

下降最多

。

這是個最佳化問題：

$\arg\min_v\{\nabla f(x)^Tv|\;||v||=1\}$

。其中，

是為了滿足「單位向量」的規定。若對

的長度不加限制，就相當於將選擇

$\Delta x$

和選擇

合併到了一起，違背了我們的初衷，並不「高效」。

等價的最佳化問題是：

$\arg\min_v\{\nabla f^Tv|\;||v||\le1\}$

，讓

在一個「球」中取值，允許了一定的「長度選擇」，這個長度選擇在演算法收斂之前不會發生太大作用，演算法會經常選擇

上的解。

以上得到的下降方向稱為「歸一化的方向」

$\Delta x_{nsd}$

。我們透過一個仔細設定，選擇梯度的「對偶範數」為縮放係數

$||\nabla f(x)||_*$

，得到「未歸一化的方向」

$\Delta x_{sd}=||\nabla f(x)||_*\Delta x_{nsd}$

。「未歸一化」的意思是，

$||\Delta x||\le1$

不再成立。

選擇「對偶範數」作為係數的原因是，這樣可以簡單地描述

$\Delta x_{sd}$

和梯度的內積：

$\nabla f(x)^T\Delta x_{sd}=||\nabla f(x)||_*\nabla f(x)^T\Delta x_{nsd}=-||\nabla f(x)||_*^2$

綜上所述，演算法在選擇「下降方向」時的操作是

$\Delta x=||\nabla f(x)||_*\cdot\arg\min_v\{\nabla f(x)^Tv|\;||v||\le1\}$

。以下具體選擇「範數」，展示計算

$\Delta x_{nsd}$

和

$\Delta x_{sd}$

的過程。

二階範數和梯度下降

如果你看上面的數學推理有點懵，這裡聯絡梯度下降，看看如何從梯度下降導向最速下降，看看梯度下降又是如何為最速下降的特殊情況。

最速下降的變化在於

範數選擇的多種多樣，梯度下降就是選擇「二階範數」的最速下降，當然最速下降也可以選擇其他階或形式的「範數」。以下看看二階範數的最速下降的形式。

求

$\Delta x_{nsd}$

的最佳化問題為：

$\min\nabla f(x)^Tv\qquad s.t.\;||v||_2^2\le1$

這個最佳化問題的解就是

$\Delta x_{sd}=-\nabla f(x)$

，如果你不想看接下來的數學推理，看到這裡就好了。

由拉格朗日乘子法得到目標函式：

$L=\nabla f(x)^Tv+\lambda(||v||_2^2-1)$

對

求梯度：

$\nabla L=\nabla f(x)+\lambda2v$

得到

$v^*=-\frac{1}{2\lambda}\nabla f(x)$

，帶入到

中：

$L^*=-\frac{1}{2\lambda}||\nabla f^T||_2^2+\lambda(\frac{1}{4\lambda^2}||\nabla f^T||_2^2-1)=-(\lambda+\frac{1}{4\lambda}||\nabla f||_2^2)$

由簡單的均值不等式可以看出

$L^*\le-2\sqrt{\frac{1}{4}||\nabla f||_2^2}=-||\nabla f||_2$

，取等條件為

$\lambda=\frac{1}{2}||\nabla f||_2$

。對偶問題目標函式的最大值就是梯度的二階範數！由對偶問題和凸函式的性質，內積

$\nabla f^Tv$

在取得最優解時的值就是梯度的二階範數！

要得到最終解，還需要求「對偶範數」。由於取得是「二階範數」，對偶範數就是二階範數，

$\|\nabla f\|_*=\|\nabla f\|_2$

。帶入得到最終結果：

$\Delta x_{sd}=\|\nabla f\|_*\Delta x_{nsd}=-\nabla f(x)$

得到這樣的結果還是出人意料的。我本預想這會和

$-\nabla f$

差一個係數，還要順勢證明那個係數是正數，現在看來分毫不差！

範數和座標系變化

「梯度下降」就是「最速下降」在「二階範數」下的版本，我們來看更加廣泛的情況。

二階範數是簡單的向量內積，我們用「二次型」取代內積，定義一個「P範數」：

$\|x\|_P=\sqrt{x^TPx}$

$\Delta x_{nsd}$

的最佳化問題為：

$\min\nabla f(x)^Tv\qquad s.t.\;||v||_P^2\le1$

得到最終結果

$\Delta x_{sd}=-P^{-1}\nabla f(x)$

，省略具體過程了，和上面二階範數的情況類似。

利用矩陣和向量變換的知識加以理解。

是另一種內積，相當於將向量

先作對映

$P^{1/2}x=\bar x$

，令自變數去到另一個空間，從而使得

$x^TPx=\bar x^T\bar x$

。在

$\bar x$

代表的空間下，還是在對目標函式進行「梯度下降」。而

單位矩陣的情況就是「不變換」，是一種特殊情況。

無論是採用P範數還是其他範數，本質上都是進行座標系變換，將自變數對映到另一個空間，從而更好地進行「梯度下降」。梯度下降在原始空間中可能存在缺陷，正如前文所述，要是分量之間的尺度差異過大，收斂就會非常緩慢。這時，變換座標系就會很有用。

具體如何變換才是最有用的，這可能見仁見智了。一般來說，要使得「範數」定義的座標系的「形狀」和目標函式自變數取值空間的「形狀」相似，如「P範數」的形狀是「橢圓」、「一階範數」的形狀是「矩形」。使用和變數空間形狀相近的範數，可以「抵消」原始空間對演算法效率的影響，從而使得變換後的空間儘量接近「正圓」。

變換

而「最速下降」更多是一種總結，不是具體的演算法本身。

一階範數和座標軸下降法

再介紹一個常用的最速下降的演算法，也就是簡單地取一階範數作為求

$\Delta x_{nsd}$

時候的範數。

$\Delta x_{nsd}=\arg\min_v\{\nabla f(x)^Tv|\|v\|_1\le1\}$

寫出目標函式和它的梯度：

$L(v)=\nabla f^Tv+\lambda(\|v\|_1-1),\nabla L=\nabla f+\lambda\text{sign}(v)$

其中

$\text{sign}(v)$

就是向量

各個分量的符號

$(\pm)$

組成的向量，這是對「絕對值」求導得到的。將梯度令為0，得到對於每個分量，都應該有：

$\frac{\partial f}{\partial x_j}=-\lambda\text{sign}(v_j^*)$

這個表示式有很巧妙的「對稱」：

$v_j^*\propto-\text{sign}(\frac{\partial f}{\partial x_j})$

一階範數的「對偶範數」是「無窮階範數」，記

$\|\nabla f\|_*=\|\frac{\partial f}{\partial x_i}\|$

。可以看出結果：

$\Delta x_{sd}=-\frac{\partial f}{\partial x_i}e_i$

其中

為座標系的「基向量」，也就是令

$\Delta x_{sd}$

只有一個分量

非0，其餘分量均為0。上面的結果是「看出來的」，如果你不太安心，可以驗證

$\nabla f(x)^T\Delta x_{sd}=-||\nabla f(x)||_*^2$

確實成立。

這就是「座標軸下降法」，每次迭代只更新梯度最大的方向，保持其他方向不變。

前文說到，選擇範數就是要選擇和目標函式形狀相近的。當目標函式的形式和範數相近時，我們喜歡選擇這樣的範數。如L1正則中出現了「一階範數」，對應的模型經常使用座標軸下降法求解。

牛頓法

選擇範數實在是令人頭疼的事情，我們有時實在不知道目標函式的形狀最好使用什麼範數來描述。牛頓法就是會「自適應形狀」的演算法，相當於在每一步都會用一個橢圓來逼近當前位置目標函式的形狀。我們以下具體來看這個問題。

設定每一步

$\Delta x_{nt}=-\nabla^2f(x)^{-1}\nabla f(x)$

，可以驗證

$\nabla f(x)^T\Delta x_{nt}=-\nabla f^T\nabla^2f^{-1}\nabla f<0$

，這就是牛頓法。和前文的一些「最速下降法」的例子不同，牛頓法使用的是一個變化的矩陣

$\nabla^2f$

，也就是「Hessian矩陣」或「二階導數」。根據「凸函式」的性質，

$\nabla^2f$

一定是「正定矩陣」。

各種理解方式

有很多種理解牛頓法的方式，我列舉一些，希望能帶來直觀的認知。

最小化二階泰勒展開

目標函式的二階展開式如下：

$f(x+v)\approx\hat f(x+v)=f(x)+\nabla f(x)^Tv+\frac{1}{2}v^T\nabla^2f(x)v$

對

求最優解：

$\nabla_v\hat f(x+v)=\nabla f+\nabla^2 f v$

得到結果

$v^*=-\nabla^2f^{-1}\nabla f$

，就是牛頓法的「一步」。

由此看來，牛頓法是在最小化每一步的「二階近似」。如下圖，找到

$\hat f$

的最小值，就是離

最小值的更進一步。

二階近似

選擇特殊的P範數

牛頓法也可以看做選擇了特殊P範數的最速下降，對於P範數，我們在之前最速下降標題下舉過例子。

這裡讓矩陣

$P=\nabla^2f$

，則範數為

$\|u\|_{\nabla^2f}=\sqrt{u^T\nabla^2fu}$

。每次更新

時，都重新計算了

$\nabla^2f$

。如果認為P範數就是將變數對映到另一個空間從而更好地梯度下降，那麼牛頓法在每一步的對映都不同、都是根據函式當前的形狀決定的。範數的形狀越接近目標函式的形狀，梯度下降的效果就越好，則每一步都使用「二階展開」逼近的範數，效果肯定比始終不變的範數好很多。並且，越接近最優解，二階展開和真實目標函式之間的差異越小，從而每次迭代的效率越來越高。

牛頓法自適應不受座標系伸縮影響

牛頓法的每一步都會調整「範數」，這裡演示這樣的調整如何擺脫了梯度下降的「尺度問題」。

將變數

做線性變換