標籤：

數學最優化梯度下降

梯度下降法和共軛梯度法有何異同？

01-05

一道考研題

@姓顏色的小學生 的答案蠻有見解的，我稍微用數學細化一下看這個問題的角度。

------------------------------------------------------------------------------------

首先，我們的問題是解決二次函數極值問題，其中Q是positive definite

$min_{x in R^n} frac{1}{2} x^T Q x - b^Tx$ (1)

接著介紹Q-conjugate：給定一個positive definite2矩陣Q，我們說非零向量x,y 關於是Q-conjugate，如果他們滿足，

$x^TQy = 0$ (2)

如果我們能找到n個Q-conjugate的向量用 ${d_1, d_2, cdots d_n}$ 表示，一個重要結論是

如果向量是Q-conjugate, 他們線性無關 (3)

所以空間任意向量 x可以用這組向量基表示

$x = sum_{i=1}^{n} a_i d_i$ (4)

將（4）代入（1）可得, 變數從 ${x in R^n }$ 變成了 ${a_1 cdots a_n in R^n}$ ,

因為 ${d_1,d_2, cdots d_n}$ 是Q-conjugate，所以由（2）得 $d_iQd_j =0 ext{quad if quad} i eq j$ , 所以上式可以繼續簡化為

$min_{a_1 cdots a_n in R^n} frac{1}{2} sum_{i=1}^{n} a_i^2d_i^TQd_i - sum_{i=1}^{n} a_ib^Td_i$ (5)

將求和符號提出來，可以得到

$min_{a_1 cdots a_n in R^n} frac{1}{2} sum_{i=1}^{n} igg( a_i^2d_i^TQd_i - a_ib^Td_i igg)$ (6)

其實，現在我們的變數 $a_1,a_2 cdots a_n$ 已經被分開了，我們分別優化他們即可，為了看的更清楚一些，我們稍微改寫一下，把求和分開來寫

這樣，我們分別求第一項 $min_{a_1 in R^n}frac{1}{2}igg( a_1^2d_1^TQd_1 + a_1b^Td_1 igg)$ 的最小值，然後第二項，即可。

第一項是一個二次函數，求最小值我們直接求導即可：

$a_1d_1^TQd_1 - b^Td_1 = 0$

可得 $a_1 = frac{b^Td_1}{d_1^TQd_1}$ , 同樣可得

$a_i = frac{b^Td_i}{d_i^TQd_i}$ (7)

所以最優解 $x^* = sum_{i=1}^{n}a_id_i$ , 將(7)代入可得

$x^* = sum_{i=1}^{n} frac{b^Td_i}{d_i^TQd_i} d_i$ (8)

現在我們重新溫習一下，conjuage gradient method(用在quadratic function上) （來自wiki Conjugate gradient method）:

是不是和我們求的（7）式一樣，只不過我們的conjugate notation 是 $d_i$ 他們是 $p_i$ .

所以本質上，就是把目標函數分成許多方向，然後不同方向分別求出極值在綜合起來。我稍微推導了一下公式，讓他更一目了然。

RemarK: 真正用conjugate gradient method的時候，我們需要找到一組conjugate的Basis, 一般使用的方法就是用當下的gradient (d_k) ，使用 Gram-Schmidt procedure 變成conjugate來用，所以其實conjugate gradient method 的一個版本是：

最後附上參考文獻，裡面關於conjugate gradient method講的蠻清楚的：
1&> & Bertsekas D

---------------------------------------------------------------------------------------

看我寫的這麼辛苦，從知識的喜悅中脫離一下，點個讚唄，想一起了解學習凸優化和非凸優化的可以關注我，我以後會多寫一些自己的學習體會，大家可以一起交流。

我的專欄：非凸優化學習之路 - 知乎專欄

第一篇文章是：從Nesterov的角度看：我們為什麼要研究凸優化？ - 知乎專欄

第二篇文章是：非凸優化基石：Lipschitz Condition - 知乎專欄

第三篇文章是：當我們談論收斂速度時，我們都在談什麼？ - 知乎專欄

或許你看了也會有啟發，哈哈。

共軛方向法（不一定是共軛梯度）的思想就是在N維優化問題中，每次沿一個方向優化得到極小值，後面再沿其他方向求極小值的時候，不會影響前面已經得到的沿那些方向上的極小值，所以理論上對N個方向都求出極小值就得到了N維問題的極小值。這組方向由於兩兩共軛，所以就叫他共軛方向法。

梯度下降法每次都直接選取當前點的梯度方向，所以就有可能按下葫蘆浮起瓢：這次求出的極小值點在之前搜索過的方向上又不是極小值了，這樣就導致收斂速度比較慢甚至不收斂。

最速下降：實在沒什麼好說的， $x_{n+1} = x_n - delta_n abla F(x_n)$ ,until $Delta F(x) < delta$

共軛梯度：區別在於方向限制在初始點的共軛方向空間內

p.s.

隨機梯度：相對上面兩者每次用所有樣本計算下降方向，每次隨機選1個或batch個樣本

牛頓法：二階Talor展開，方向 $-H_k^{-1} g_k$

pseudo-Newton (BFGS為例)： $Hleftarrow B$ ， $B_0=I$ ， $B_{k+1} = B_k + frac{Delta_k xDelta_k^T x}{Delta_k^T x Delta_k heta} + frac{B_kDelta_kx(B_kDelta_kx)^T} {Delta_k^TxB_kDelta_kx}$

最速下降法（梯度下降）：Method of steepest descent

共軛梯度法：Conjugate gradient method

最速下降法以殘向量作為解的修正方向，收斂速度可能很慢；cg的修正方向是之前平面的梯度，求出的殘向量與之前的都正交，理論上只需要n次就得到精確解。但兩個都是對對稱正定矩陣來的。。

這些搜索方法都是確定一個搜索方向然後再用一個合適的步長來保證收斂性，不同的是梯度下降在尋找搜索方向的時候只利用了空間中當前點的信息，共軛梯度下降還利用了之前的搜索路徑信息

推薦閱讀：

※二維坐標平面上有n個隨機點，如何求解這些點的最小外接矩形呢？
※梯度下降為什麼步長要乘以導數？
※正態分布里為什麼會出現自然底數e和圓周率pi呢？
※真正的數學建模高手是什麼境界...？
※數學中國論壇的美賽輔助報名靠譜嗎？

TAG:數學 | 最優化 | 梯度下降 |