當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

共轭梯度法笔记

發(fā)布時間：2023/12/20 编程问答 35 豆豆

生活随笔收集整理的這篇文章主要介紹了共轭梯度法笔记小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

預(yù)備知識

Hesse 矩陣

函數(shù) $f (x)$ 為自變量為為向量的實值函數(shù)，其中 $x = [x_1, x_2,...,x_n]$ ，則Hesse矩陣的定義為：
$H(f)=[?2f?x12?2f?x1?x2??2f?x1?xn?2f?x2?x1?2f?x22??2f?x2?xn?????2f?xn?x1?2f?xn?x2??2f?xn2]\Large H(f)=\left[\begin{array}{cccc} \frac{\partial^{2} f}{\partial x_{1}^{2}} & \frac{\partial^{2} f}{\partial x_{1} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{1} \partial x_{n}} \\ \frac{\partial^{2} f}{\partial x_{2} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{2}^{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{2} \partial x_{n}} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial^{2} f}{\partial x_{n} \partial x_{1}} & \frac{\partial^{2} f}{\partial x_{n} \partial x_{2}} & \cdots & \frac{\partial^{2} f}{\partial x_{n}^{2}} \end{array}\right]$

問題

求解線性方程（系數(shù)矩陣A對稱且正定）：
$Ax=b\Large Ax = b$
顯然， $x = A^{-1}b$ 。但是求矩陣的逆計算量太大，所以實際中使用迭代的方式求 $x$ 。

首先構(gòu)造一個二次函數(shù)：
$?(x)=12xTAx?bTx(1)\Large \phi(x) = \frac{1}{2}x^TAx-b^Tx \tag{1}$
對（1）求導(dǎo)，并令導(dǎo)數(shù)為0得：
$??(x)=Ax?b=0(2)\Large \nabla \phi(x)=A x-b=0 \tag{2}$
從（2）可以看出 $?(x)\phi(x)$ 的導(dǎo)數(shù)為0，就是線性方程 $A x = b$ 的解，即求 $?(x)\phi(x)$ 的極小值點。現(xiàn)在問題轉(zhuǎn)為求二次函數(shù)的極值問題。

二次函數(shù)求極值的方法（迭代方法）

迭代的方法都使用以下的原則：

最新的解 = 當(dāng)前解 + 步長 * 更新方向

最重要的就是要找到更新方向和步長。

1. 最速下降法（梯度下降法）（一階優(yōu)化方法）

梯度下降法選擇函數(shù)值下降最快的方向，即負梯度方向。則有：
$x(t+1)=x(t)?λ(t)??(x)\Large x^{(t+1)} = x^{(t)} - \lambda^{(t)}\nabla \phi(x)$
其中 $λ(t)\lambda^{(t)}$ 為步長，可以通過求 $λ(t)=argminf(x(t)?λ(t)??(x))\lambda^{(t)} = argmin f(x^{(t)}-\lambda^{(t)}\nabla \phi(x) )$ ，但由于計算代價太大，實際中設(shè)置步長為常數(shù)。

梯度下降法的收斂速度太慢，甚至可能比直接求矩陣的逆還慢。

2. 牛頓法（二階優(yōu)化方法）

給一個初始值 $x^{(t)}$ ，則 $?(x)\phi(x)$ 在 $x^{(t)}$ 處的二階泰勒展開為：
$f(x)=?(x(t))+??(x(t))(x?x(t))+12(x?x(t))T?2?(x(t))(x?x(t))\Large f(x) =\phi(x^{(t)}) + \nabla \phi(x^{(t)})(x-x^{(t)}) + \frac{1}{2}(x-x^{(t)})^T\nabla^2 \phi(x^{(t)})(x-x^{(t)})$
顯然 $f(x(t))=?(x(t))f(x^{(t)}) = \phi(x^{(t)})$ ， $f (x)$ 可以作為 $?(x)\phi(x)$ 在 $x^{(t)}$ 的近似，則問題就變?yōu)榍?span id="ze8trgl8bvbq" class="katex--inline"> $f (x)$ 的極值，對 $f (x)$ 求導(dǎo)等于0得：
$df(x)dx=??(x(t))+?2?(x(t))(x?x(t))=0x=x(t)??2?(x(t))?1??(x(t))\Large \frac{df(x)}{dx} = \nabla \phi(x^{(t)}) + \nabla^2 \phi(x^{(t)})(x-x^{(t)}) = 0 \\ \Large x = x^{(t)} - \nabla^2 \phi(x^{(t)})^{-1} \nabla \phi(x^{(t)})$
把求得得極值點 $x$ 作為 $x^{(t+1)}$ ，然后迭代求解。因此牛頓法，在迭代過程中需要求一階導(dǎo)和二階導(dǎo)，且 $?(x)\phi(x)$ 的Hesse矩陣可逆。更新公式如下：
$x(t+1)=x(t)?A?1??(x(t)\Large x^{(t+1)} = x^{(t)} - A^{-1}\nabla \phi(x^{(t)}$
但是牛頓法仍需要計算矩陣的逆，因此不適用。

3. 共軛梯度法

如果要使用共軛梯度法求解線性方程，必須要求系數(shù)矩陣對稱且正定。

共軛的定義：

對于一組向量 ${p^{(0)},p^{(1)},...,p^{(n-1)}\}$ ，如果任意兩個向量間( $\ne j)$ 滿足：
$(p(i))TAp(j)=0(3)\Large (p^{(i)})^T A p^{(j)} = 0 \tag{3}$
則稱這組向量與對陣正定矩陣A共軛。

共軛梯度法是介于梯度下降法和牛頓法之間的一種方法。共軛梯度法初始選擇負梯度方向進行更新，在后面的迭代中取負梯度方向和前一搜索方向的線性組合作為搜索方向。

對于優(yōu)化問題（1）的二維情況，如下圖：

其中 $x0x1→=???(x0)\overrightarrow{x_{0}x_{1}}=-\nabla \phi\left(x_{0}\right)$ 、 $x1x?→=?A?1??(x1)\overrightarrow{x_{1} x^{*}}=-A^{-1} \nabla \phi\left(x_{1}\right)$ 。于是有：
$x0x1→TAx1x?→=??(x0)AA?1??(x1)=??(x0)??(x1)=0\Large \begin{aligned} \overrightarrow{x_{0} x_{1}}^{T} A \overrightarrow{x_{1} x^{*}} &=\nabla \phi\left(x_{0}\right) A A^{-1} \nabla \phi\left(x_{1}\right) \\ &=\nabla \phi\left(x_{0}\right) \nabla \phi\left(x_{1}\right) \\ &=0 \end{aligned}$
這表明，兩次迭代的方向是一組共軛向量。從二維推廣到N維，只要找到一組共軛向量 ${p^{(0)},p^{(1)},...,p^{(n-1)}\}$ ，然后依次沿著每個向量方向優(yōu)化，最終在N次迭代以后就可以達到極小值。現(xiàn)在的問題是，如何找到一組共軛向量？

假設(shè)起始點為 $x^{(0)}$ 。首先，選 $p(0)=???(x(0))p^{(0)}=- \nabla \phi(x^{(0)})$ ，然后求后續(xù)的向量 $p^{(1)}, p^{(2)}...p^{(t)},...,p^{(n-1)}$ 。

當(dāng)t=1時，求 $p^{(1)}$ ，已知 $p^{(0)}$ 和 $??(x(1))\nabla\phi(x^{(1)})$ 。因為這兩個向量一定是線性無關(guān)的，所以可以在這兩個向量構(gòu)成的平面上尋找 $p^{(1)}$ ，則 $p(1)=???(x(1))+β1p(0)p^{(1)} = -\nabla\phi(x^{(1)}) + \beta_1 p^{(0)}$ 。將 $p^{(0)}, p^{(1)}$ 帶入（3）得：
$β1=(p(0))TA??(x(1))(p(0))TAp(0)\Large \beta_{1}=\frac{(p^{(0)})^{T} A \nabla \phi\left(x^{(1)}\right)}{(p^{(0)})^{T} A p^{(0)}}$
有了 $β1\beta_1$ ，就可以得到 $p^{(1)}$ 。依次類推，則有：
$p(t)=???(x(t))+βtp(t?1)\Large p^{(t)} = -\nabla\phi(x^{(t)})+\beta_t p^{(t-1)}$
其中：
$βt=(p(t?1))TA??(x(t))(p(t?1))TAp(t?1)\Large \beta_{t}=\frac{(p^{(t-1)})^{T} A \nabla \phi\left(x^{(t)}\right)}{(p^{(t-1)})^{T} A p^{(t-1)}}$
現(xiàn)在知道了每一次更新的方向 $p^{(t)}$ ，就可以計算出 $?(x(t))\phi(x^{(t)})$ 在該方向的最優(yōu)步長 $αt\alpha_t$ 。因為更新 $x^{(t)}$ 的公式為：
$x(t+1)=x(t)+αtp(t)\Large x^{(t+1)} = x^{(t)} + \alpha_t p^{(t)}$
則最優(yōu)的 $αt\alpha_t$ ，可以通過 $?(x(t+1))\phi(x^{(t+1)})$ 對 $αt\alpha_t$ 求導(dǎo)等于0計算，則有：
$αt=???(x(t))Tp(t)(p(t))TAp(t)\Large \alpha_{t}=-\frac{\nabla \phi\left(x^{(t)}\right)^{T} p^{(t)}}{(p^{(t)})^{T} A p^{(t)}}$
綜上，共軛梯度法的更新流程如下：
$αt←?(r(t))Tp(t)(p(t))TAp(t)x(t+1)←x(t)+αtp(t)r(t+1)←Ax(t+1)?bβt+1←(p(t))TAr(t+1)(p(t))TAp(t)p(t+1)←?r(t+1)+βt+1p(t)k←k+1\Large \alpha_{t} \leftarrow -\frac{(r^{(t)})^T p^{(t)}}{(p^{(t)})^{T} A p^{(t)}} \\ \Large x^{(t+1)} \leftarrow x^{(t)} + \alpha_t p^{(t)} \\ \Large r^{(t+1)} \leftarrow Ax^{(t+1)}-b \\ \Large \beta_{t+1} \leftarrow \frac{(p^{(t)})^{T} A r^{(t+1)}}{(p^{(t)})^{T} A p^{(t)}} \\ \Large p^{(t+1)} \leftarrow -r^{(t+1)}+\beta_{t+1} p^{(t)} \\ \Large k \leftarrow k+1$

其中， $r(t)=??(x(t))r^{(t)} = \nabla \phi(x^{(t)})$ ， $r^{(0)} = Ax^{(0)} - b, p^{(0)} = -r^{(0)}$ 。

共軛梯度法只需要一階導(dǎo)數(shù)信息，就可以計算步長和更新方向。收斂速度快，占用空間低，適用于求解大規(guī)模的線性方程。

總結(jié)

以上是生活随笔為你收集整理的共轭梯度法笔记的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： DEBUG、void、NULL、C库和A
下一篇： Linux：dup/dup2 文件描述符