機(jī)器人中的數(shù)值優(yōu)化|【六】線性共軛梯度法，牛頓共軛梯度法

往期回顧

機(jī)器人中的數(shù)值優(yōu)化|【一】數(shù)值優(yōu)化基礎(chǔ)
機(jī)器人中的數(shù)值優(yōu)化|【二】最速下降法，可行牛頓法的python實(shí)現(xiàn)，以Rosenbrock function為例
機(jī)器人中的數(shù)值優(yōu)化|【三】無約束優(yōu)化，擬牛頓法理論與推導(dǎo)
機(jī)器人中的數(shù)值優(yōu)化|【四】L-BFGS理論推導(dǎo)與延伸
機(jī)器人中的數(shù)值優(yōu)化|【五】BFGS算法非凸/非光滑處理
關(guān)于牛頓-共軛梯度法，筆者認(rèn)為對(duì)其最直接和最根本的認(rèn)識(shí)，這篇帖子寫得特別好，可以參考東雲(yún)正樹的 如何理解共軛梯度法 一文。

為什么要用Conjugate Gradient method？

從前面的系列我們知道，對(duì)于一個(gè)凸的無約束優(yōu)化，我們總是希望通過梯度，基于這樣那樣的方法來到達(dá)最優(yōu)點(diǎn)。在前面基本的梯度下降方法中，我們每次計(jì)算一個(gè)梯度，并根據(jù)線性搜索得到的一個(gè)較為不錯(cuò)的步長，向前優(yōu)化一步。在Newton-CG method中我們不禁要提問了：有沒有一種可以有確定的搜索次數(shù)，而且次數(shù)還比較少的方法呢？這個(gè)方法就是Newton-CG method。我們知道在向量中存在標(biāo)準(zhǔn)正交集的概念，在優(yōu)化問題中，我們也存在共軛梯度的概念，關(guān)于共軛梯度的具體定義和推導(dǎo)可以進(jìn)一步查閱相關(guān)的資料。本質(zhì)上，就是把原來隨機(jī)走梯度的過程，變?yōu)樵谕箚栴}空間中“正交”的梯度向量上，每個(gè)向量只走一步，且是最優(yōu)的一步的過程。

從上面的例子我們可以看到，綠色為共軛梯度法，紅色為梯度下降法，我們其實(shí)要做的工作就是在橢圓的切向和法向各走“最優(yōu)”的一步，一步到位即可。

Gram-Schmitd正交化/施密特正交化

理解共軛梯度法，首先我們要回顧一個(gè)東西，那就是施密特正交化。利用施密特正交化，我們可以從空間中的一組向量得到互相正交的一組向量集。如果我們有一組互不平行的向量$[{\alpha }_1,{\alpha }_2,{\alpha }_3,{\alpha }_4,{\alpha }_5,...]$,利用一下公式可以得到正交基：
$${\beta }_1={\alpha }_1$$
$${\beta }_2={\alpha }_2?\frac{({\beta }_1,{\alpha }_2)}{({\beta }_1,{\beta }_1)}{\beta }_1$$
$${\beta }_3={\alpha }_3?\frac{({\beta }_1,{\alpha }_3)}{({\beta }_1,{\beta }_1)}{\beta }_1?\frac{({\beta }_2,{\alpha }_3)}{({\beta }_2,{\beta }_2)}{\beta }_2$$
$${\beta }_4={\alpha }_4?\frac{({\beta }_1,{\alpha }_4)}{({\beta }_1,{\beta }_1)}{\beta }_1?\frac{({\beta }_2,{\alpha }_4)}{({\beta }_2,{\beta }_2)}{\beta }_2?\frac{({\beta }_3,{\alpha }_4)}{({\beta }_3,{\beta }_3)}{\beta }_3$$
$$...$$

線性共軛梯度法

對(duì)于如下的一個(gè)問題
$$argmi{n}_{x}f(x)=\frac{1}{2}{x}^{T}Ax?b^{T}x$$
我們要求其無約束優(yōu)化。這里我們可以引入共軛梯度的概念，其概念類似于正交向量，對(duì)于一個(gè)正交向量$u,v$，有$u^{T}v=0$。一個(gè)矩陣$A$,如果存在向量$u,v$，有$u^{T}Av=0$，則我們認(rèn)為$u,v$關(guān)于$A$共軛。在下降過程中，如果我們每一步選擇的下降方向都是一個(gè)獨(dú)立的共軛向量，且一共有$n$個(gè)共軛向量，則最多需要$n$步即可下降到最優(yōu)點(diǎn)。

回顧優(yōu)化過程，最核心的公式為
$$x_{k+1}=x_k+\alpha u_k$$
其中$u_k$為下降方向，$\alpha$為步長。將$x_{k+1}$代入最優(yōu)化目標(biāo)公式，我們有
$$argmi{n}_{x}f(x_{k+1})=argmi{n}_{x}f(x_k+\alpha u_k)$$
假設(shè)下降方向已經(jīng)確定了，我們要確定最優(yōu)步長
$$argmi{n}_{x}f(x_k+\alpha u_k)=argmi{n}_x\frac{1}{2}(x_k+\alpha u_k{)}^{T}A(x_k+\alpha u_k)?b^T(x_k+\alpha u_k)$$
對(duì)$\alpha$求導(dǎo)，有
$$argmi{n}_x{f}^{\prime }(x_k+\alpha u_k)=0$$
解得
$$\alpha =\frac{b^T{u}_k?x_k^{T}A{u}_k}{u_k^{T}A{u}_k}$$
這里的$\alpha$是最優(yōu)步長的一個(gè)“尺度”，也就是scalar。那么問題來了，我們想要每次下降都能夠是共軛方向的，怎么辦呢？

設(shè)每次迭代之后的誤差量為
$$r_k=A{x}_k?b$$
令
$$u_k=?r_k+{\beta }_k{u}_{k?1}$$
兩邊乘以$u_{k?1}^{T}A$有
$$u_{k?1}^{T}A{u}_k=?u_{k?1}^{T}A{r}_k+u_{k?1}^{T}A{\beta }_k{u}_{k?1}$$
因?yàn)槲覀兿胍玫降氖枪曹椃较?#xff0c;所以認(rèn)為$u_{k?1}^{T}A{u}_k=0$
$$?u_{k?1}^{T}A{r}_k+u_{k?1}^{T}A{\beta }_k{u}_{k?1}=0$$
$${\beta }_k=\frac{r_k^{T}A{u}_{k?1}}{u_{k?1}^{T}A{u}_{k?1}}$$
在這里我們就可以得到一個(gè)縮放標(biāo)量${\beta }_k$可以迭代計(jì)算共軛向量，最后得到的算法如下所示

優(yōu)化線性共軛梯度法

進(jìn)一步的，我們可以提出更高效的線性共軛梯度法。首先引入一些定理（這里的$p$就是$u$）

根據(jù)前面的公式，有
$$\alpha =\frac{b^T{u}_k?x_k^{T}A{u}_k}{u_k^{T}A{u}_k}=\frac{?r_k^T{u}_k}{u_k^{T}A{u}_k}$$
由于$u_k=?r_k+{\beta }_k{u}_{k?1}$
$$\alpha =\frac{?r_k^T(?r_k+\beta u_{k?1})}{u_k^{T}A{u}_k}$$
由于$r_k^T{u}_{k?1}=0$
有
$${\alpha }_k=\frac{r_k^T{r}_k}{u_k^{T}A{u}_k}$$
由于${\alpha }_{k}A{p}_k=r_{k+1}?r_k$
繼續(xù)代入有
$${\beta }_{k+1}=\frac{r_{k+1}^T{r}_{k+1}}{r_k^T{r}_k}$$

下一節(jié)中，將介紹牛頓共軛梯度法