G.Jerry的共軛梯度法筆記-有解無憂

該筆記初衷為期末復習所用，參考出處均已注明，涉及個人理解部分如果有不對之處，還請批評指正，俺會虛心接受滴！

1.應用范圍

目標函式 $min f(x)=1/2*x^TQx+b^Tx+c, x=(x_1,x_2,...,x_n)^T$ 的無約束績效問題，

2.相關定義

定義1 設Q為n階實對稱正定矩陣，若n維方向x和y滿足 $x^TQy=0$ ，則稱方向x和y是Q-共軛的，

3.原理

將函式改寫成如下形式：

如果每個子函式 ${f_i}\left( {?{x_i}} \right)$ 都能取得最小值，那么f(x)也能取得最小值，假設梯度下降一共需要n階(也就是迭代次數啦)，每個 ${f_i}\left( {?{x_i}} \right)$ 對應一個階梯，每階的方向和步長都使 ${f_i}\left( {?{x_i}} \right)$ 取得最小值，

我們當然希望階梯數n越少越好，那么如何找到所需最少的階梯數呢？當階梯數最少時，每階的方向和步長都不同，且每階都無法由其他的階梯組合而成，也就是說，每次梯度下降的方向必須是線性無關的，梯度下降的次數才會最少，迭代次數才會最少，

我們是有辦法找到一組線性無關的方向向量（即Rn中的一組基{p1,p2,…,pn}）的哦！首先在初始點(記為x1)選取負梯度方向為p1(就是x1點的方向啦)，然后尋找與p1共軛的方向為p2，再尋找與p1和p2共軛的方向為p3，…，由此經過n次尋找到f(x)的最小值，

也就是說，我們需要找到合適的基{p1,p2,…,pn}，從而確定方向、步長的迭代式，滿足 $\frac{?{d(f({x_i} + \alpha {p_i})}}{?{d\alpha }} = {p_i}^T\triangledown f\left( {?{x_{i + 1}}} \right) = 0$ ，i∈{1,2,…,n}，

好巧不巧，當? ${\left[ {?{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right]^T}Q\left[ {?{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right] = diag\{ {\vartriangle _1},{\vartriangle _2}, \ldots ,{\vartriangle _n}\}$ 時，選擇方向 ${p_{i + 1}} = - \triangledown f\left( {?{x_{i + 1}}} \right) + {\lambda _i}{p_i}$ ，其中 ${\lambda _i} = \frac{?{?{p_i}^TQ\triangledown f\left( {?{x_{i + 1}}} \right)}}{?{?{p_i}^TQ{p_i}}}$ (常數)，步長為 ${\alpha _{\text{i}}} = \frac{?{ - {p_i}^T\triangledown f\left( {?{x_i}} \right)}}{?{?{p_i}^TQ{p_i}}}$ (常數)，可以滿足上述條件，

當 ${\left[ {?{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right]^T}Q\left[ {?{p_1}{\text{ }}{p_2}{\text{ }} \ldots {\text{ }}{p_n}} \right] = diag\{ {\vartriangle _1},{\vartriangle _2}, \ldots ,{\vartriangle _n}\}$ 時，就可以使 $\frac{?{d(f({x_i} + \alpha {p_i})}}{?{d\alpha }} = {p_i}^T\triangledown f\left( {?{x_{i + 1}}} \right) = 0$ ，i∈{1,2,…,n}成立了，

已知 $df\left( x \right) = \triangledown f\left( x \right) = Qx + b$ ，那么 $\triangledown f\left( {?{x_{i + 1}}} \right) - \triangledown f\left( {?{x_{j + 1}}} \right) = Q\left[ {?{x_{i + 1}} - {x_{j + 1}}} \right]$ 總是成立，i∈{1,2,…,n}，j∈{1,2,…,i}（簡單來說，i表示當前迭代次數，j表示i次之前的每個迭代次數，顯然i≠j），(正是這個獨特的導數和梯度條件，使得共軛梯度法的使用范圍有限制！)整理一下就是 $\triangledown f\left( {?{x_{i + 1}}} \right) = \triangledown f\left( {?{x_{j + 1}}} \right) + Q\left[ {?{x_{i + 1}} - {x_{j + 1}}} \right]$ ，這非常容易湊成共軛關系：

這里僅僅得到了基需要滿足的條件(即它們必須具有關于Q共軛的性質)，然而，在迭代程序中，程式需要的是pi+1與pi的關系式，以及λi+1與λi的關系式，所以要根據基的共軛特性，找出方向和步長的迭代式，

根據恒成立等式 ${p_i}^TQ{p_{i + 1}} = 0$ ，嘗試構造出一類方向迭代式： ${p_{i + 1}} = - \triangledown f\left( {?{x_{i + 1}}} \right) + {\lambda _i}{p_i}$ ，顯然當 ${\lambda _i} = \frac{?{?{p_i}^TQ\triangledown f\left( {?{x_{i + 1}}} \right)}}{?{?{p_i}^TQ{p_i}}}$ 時，

${p_i}^TQ{p_{i + 1}} = - {p_i}^TQ\triangledown f\left( {?{x_{i + 1}}} \right) + {\lambda _i}{p_i}^TQ{p_i} = - {p_i}^TQ\triangledown f\left( {?{x_{i + 1}}} \right) + \frac{?{?{p_i}^TQ\triangledown f\left( {?{x_{i + 1}}} \right)}}{?{?{p_i}^TQ{p_i}}}{p_i}^TQ{p_i}$ =0總是成立，這樣就確定下方向迭代式了，

通過恒成立等式 ${p_j}^TQ{p_{i + 1}} = 0$ 可以確定步長迭代式，顯然當 ${\alpha _{\text{i}}} = \frac{?{ - {p_i}^T\triangledown f\left( {?{x_i}} \right)}}{?{?{p_i}^TQ{p_i}}}$ 時，下式成立：

其中 $\triangledown f{\left( {?{x_j}} \right)^T}\triangledown f\left( {?{x_{i + 1}}} \right) = 0$ 可由 ${p_j}^T\triangledown f\left( {?{x_{i + 1}}} \right) = - \triangledown f{\left( {?{x_j}} \right)^T}\triangledown f\left( {?{x_{i + 1}}} \right) + {\lambda _{j - 1}}{p_{j - 1}}^T\triangledown f\left( {?{x_{i + 1}}} \right) = 0 + 0$ 推出，

本來這里就結束了，但是大聰明們發現方向 ${p_{i + 1}} = - \triangledown f\left( {?{x_{i + 1}}} \right) + {\lambda _i}{p_i}$ 中的 ${\lambda _i} = \frac{?{?{p_i}^TQ\triangledown f\left( {?{x_{i + 1}}} \right)}}{?{?{p_i}^TQ{p_i}}}$ 是可以簡化的，于是將其簡化為

這樣方向就可以簡單寫為了，嘻嘻，

4.步驟

首先，找到初始點 ${x_1}$ ，當 ${x_1}$ 梯度不為零時，根據步長和方向的規則

逐次迭代出下一個點 ${x_2},{x_3},...,{x_n}$ ，(若某點梯度為零，那找到極小點咯，就不需要繼續迭代咯！)

2021.09.25

注：文中的“顯然”只是我猜想大聰明們在構造它們的時候覺得“顯然”，我個人覺得一點都不“顯然”！

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302956.html

標籤：AI

上一篇：HCNP Routing&Switching之路由控制-策略路由

下一篇：【Halcon影像】形狀模板匹配