如何理解共轭梯度法

• 原文: https://zhuanlan.zhihu.com/p/64227658
• 发布日期: 2019-04-29
• 分类: 数学方法 / 物理数学工具箱

这篇文章本来只是随手写的讲稿, 最近知乎的编辑器用得比较顺手就直接搁这排版了. 写完吧觉得也还算可, 就没删干脆发出来算了. 有兴趣可以随便看看, 但质量不算高别抱太大期待.

只能说是一篇超短、超易懂超感性的入门文章.

方法的目的就是通过迭代求得多元二次函数 $f\left(x_1,x_2,\cdot \cdot \cdot ,x_n\right)$ 的极值点.

二次函数的 general 形式即:

\begin{align} & f\left( {x}_{1},{x}_{2},\cdot \cdot \cdot ,{x}_{n} \right)={\lambda }_{1}x_{1}^{2}+{\lambda }_{2}x_{2}^{2}+\cdot \cdot \cdot +{\lambda }_{n}x_{n}^{2} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +{\alpha }_{1}{x}_{1}{x}_{2}+{\alpha }_{2}{x}_{1}{x}_{3}+\cdot \cdot \cdot +{\alpha }_{n\text{-1}{x}_{1}{x}_{n} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +{\beta }_{1}{x}_{n}{x}_{1}+{\beta }_{2}{x}_{n}{x}_{2}+\cdot \cdot \cdot +{\beta }_{n\text{-1}{x}_{n}{x}_{n-1} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +{\gamma }_{1}{x}_{1}+{\gamma }_{2}{x}_{2}+\cdot \cdot \cdot +{\gamma }_{n}{x}_{n}+c. \\ \end{align}

希腊字母和最后的 $c$ 都是常系数.

若记 $x=\left[\begin{array}{c}{x}_1\\ x_2\\ \cdot \cdot \cdot \\ x_n\end{array}\right]$ 则函数写作二次型 f\left( {x}_{1},{x}_{2},\cdot \cdot \cdot ,{x}_{n} \right)=f\left( x \right)=\frac{1}{2}{x}^{\text{T}Ax-{b}^{\text{T}x+c.

注意上式中 $A$ 是 $n$ 维实矩阵, $b$ 是 $n$ 维实向量, $c$ 就是个实数, 也就是说每一项都是实数.

以三维为例,一定要展开的话就是这种感觉:

\begin{align} & f\left( {x}_{1},{x}_{2},{x}_{3} \right)=f\left( x \right)=\frac{1}{2}{x}^{\text{T}Ax-{b}^{\text{T}x+c \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{1}{2}\left[ {x}_{1},{x}_{2},{x}_{3} \right]\left[ \begin{matrix} {a}_{11} & {a}_{12} & {a}_{13} \\ {a}_{21} & {a}_{22} & {a}_{23} \\ {a}_{31} & {a}_{32} & {a}_{33} \\ \end{matrix} \right]\left[ \begin{matrix} {x}_{1} \\ {x}_{2} \\ {x}_{3} \\ \end{matrix} \right]-\left[ {b}_{1},{b}_{2},{b}_{3} \right]\left[ \begin{matrix} {x}_{1} \\ {x}_{2} \\ {x}_{3} \\ \end{matrix} \right]+c \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{1}{2}{a}_{11}x_{1}^{2}+\frac{1}{2}{a}_{22}x_{2}^{2}+\frac{1}{2}{a}_{33}{x}^{2} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ +\frac{1}{2}\left( {a}_{12}+{a}_{21} \right){x}_{1}{x}_{2}+\frac{1}{2}\left( {a}_{13}+{a}_{31} \right){x}_{1}{x}_{3}+\frac{1}{2}\left( {a}_{23}+{a}_{32} \right){x}_{2}{x}_{3} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ -{b}_{1}{x}_{1}-{b}_{2}{x}_{2}-{b}_{3}{x}_{3}+c. \\ \end{align}

很显然 $A$ 可以写成实对称矩阵, 那就这么写.

为啥? 因为实对称矩阵好.

不难证明这个多元函数的导数为 $\frac{\text{d}f\left(x\right)}{\text{d}x}=Ax-b$, 方法很多, 下面随便说三个.

当然还是以三维为例, 可推广性是显然的.

1. 傻不拉几嗯算法:

强行展开算会发现上式成立.

其中求导的定义是 \frac{\text{d}{\text{d}x}\equiv \nabla =\left( \frac{\partial }{\partial {x}_{1},\frac{\partial }{\partial {x}_{2},\frac{\partial }{\partial {x}_{3} \right)=\sum\limits_{i=1}^{3}{\vec{e}_{i}\frac{\partial }{\partial {x}_{i}.

顺带一提全微分可以看着两个矢量的内积: \text{d}f\left( x \right)=\nabla f\cdot \text{d}x=\sum\limits_{i=1}^{3}{\frac{\partial f}{\partial {x}_{i}\text{d}{x}_{i}. 而这么一来幂级数展开就可以看作是 f\left( \vec{a}+\Delta \vec{x} \right)=\sum\limits_{n=0}^{\infty }{\frac{1}{n!}{\left( \Delta \vec{x}\cdot {\nabla }_{\vec{a} \right)}^{n}f\left( {\vec{a} \right)}.

2. 标量对矢量求导法:

\frac{\text{d}{x}^{\text{T}Ax}{\text{d}x}=\left[ \begin{matrix} \frac{\partial {x}^{\text{T}Ax}{\partial {x}_{1} \\ \frac{\partial {x}^{\text{T}Ax}{\partial {x}_{2} \\ \frac{\partial {x}^{\text{T}Ax}{\partial {x}_{3} \\ \end{matrix} \right]=\left[ \begin{matrix} 2{a}_{11}{x}_{1}+2{a}_{12}{x}_{2}+2{a}_{13}{x}_{3} \\ 2{a}_{12}{x}_{1}+2{a}_{22}{x}_{2}+2{a}_{23}{x}_{3} \\ 2{a}_{13}{x}_{1}+2{a}_{23}{x}_{2}+2{a}_{33}{x}_{3} \\ \end{matrix} \right]=2Ax.

\frac{\text{d}{b}^{\text{T}x}{\text{d}x}=\left[ \begin{matrix} \frac{\partial {b}^{\text{T}x}{\partial {x}_{1} \\ \frac{\partial {b}^{\text{T}x}{\partial {x}_{2} \\ \frac{\partial {b}^{\text{T}x}{\partial {x}_{3} \\ \end{matrix} \right]=\left[ \begin{matrix} {b}_{1} \\ {b}_{2} \\ {b}_{3} \\ \end{matrix} \right]=b.

所以就有 $\frac{\text{d}f\left(x\right)}{\text{d}x}=Ax-b.$

3. 观察后偷懒法:

下面总之要注意实数的转置就是它自己, 故会 {b}^{\text{T}x={x}^{\text{T}b 或 {x}^{\text{T}Ay={y}^{\text{T}Ax 之类的.

显然 \frac{\text{d}{x}^{\text{T}b}{\text{d}x}=\left[ \begin{matrix} \frac{\partial {x}^{\text{T}b}{\partial {x}_{1} \\ \frac{\partial {x}^{\text{T}b}{\partial {x}_{2} \\ \frac{\partial {x}^{\text{T}b}{\partial {x}_{3} \\ \end{matrix} \right]=\left[ \begin{matrix} {b}_{1} \\ {b}_{2} \\ {b}_{3} \\ \end{matrix} \right]=b 事实上这个结论也很符合直觉.

进一步可以发现这些 \frac{\text{d}{x}^{\text{T}b}{\text{d}x}=b\Rightarrow \frac{\text{d}{x}^{\text{T}Ay}{\text{d}x}=Ay\Rightarrow \frac{\text{d}{y}^{\text{T}Ax}{\text{d}x}=Ay.

那这么一来不就有 \frac{\text{d}{x}^{\text{T}Ax}{\text{d}x}=Ax+Ax=2Ax 了吗?

因为上面有俩 $x$ 嘛, 先对左边的求导再对右边的求导, 即所谓的莱布尼茨公式.

再加上\frac{\text{d}{b}^{\text{T}x}{\text{d}x}=b.

最后得到你懂的.

所谓共轭梯度法, 最大的优势就是每个方向都走到了极致, 也即是说寻找极值的过程中绝不走曾经走过的方向, 那么 $n$ 空间的函数极值也就走 $n$ 步就解决了. 假如是二维空间, 那就直走两步, 跟最速下降法比优势是不言而喻的.

求极值就是一阶导数为零的问题: $\frac{\text{d}f\left(x\right)}{\text{d}x}=Ax-b=0\Rightarrow Ax=b.$

梦回垃圾线代, 又要求解 $Ax=b.$

记当前所处的位置为 $x_t$ 而 $x^{\ast }$为真正的解, 再定义误差向量 $e_t=x^{\ast }-x_t$, 如下所示:

绿箭头末端就是要求的点.满足什么条件才叫某个方向彻底走到了极致呢?

如果说当前的误差跟上一步的方向正交是不是就意味着上一步的那个方向再也不用走了?

若将下一步要走的方向记作 $r_t$, 那误差与上一步方向正交的要求写出来就是 r_{t-1}^{\text{T}{e}_{t}=0.

所谓迭代, 就是根据当前位置与上一步的信息不断地得到新的方向和新的步长来走下去.

按前面的说法那下一步只要随便找一个跟上一步正交的方向走就是了.

但实际上我们根本办不到让上一步满足 r_{t-1}^{\text{T}{e}_{t}=0 的这个要求,

你要真那么牛批不直接一步到位走到终点算了?

但我们有一个等价的做法, 那就是将要求改为共轭正交 r_{t-1}^{\text{T}A{e}_{t}=0.

其中矩阵 $A$ 是一个常对称矩阵, 也就是作用在右边向量的一个线性变换罢了.

下一个方向如果跟经过线性变换的前面所有方向都正交的话, 那么某种意义上我们永远不会走重复的方向. 但因为涉及到两个 $n$ 维线性空间之间的变换, 所以在这个空间里面看他走过的路似乎每一步都并不是正交的. 那怎么知道这个做法是不是真的像我说的这样走到了极致呢? 你可以数数一共走了几步嘛, 对于 $n$ 维空间只用走 $n$ 步才是我们真正的目的啊. 当你走完了 $n-1$ 步之后, 将有 $n-1$ 线性无关的向量在经过线性变换之后要求与下一个方向正交, 而你的空间只有 $n$ 维, 那么最后一个方向就是确定的了, 所以就只用走 $n$ 步.

上面那是说给线代学得很差的人听的, 既然你线代那么差, 那能不能听懂你都只能装听懂了. 而对线性空间稍微有些了解的人就不难发现这实际上就只是一个重新定义内积的过程罢了···

什么是实内积?

无非就是实线性空间 $V$ 到实数域 $\mathbb{R}$ 上的一个双线性映射罢了, 即 $⟨\cdot ,\cdot ⟩:V\times V\to \mathbb{R}.$

在比较弱智的矩阵版本线性代数里无非是定义了 \left\langle x,y \right\rangle \equiv {x}^{\text{T}y, 有内积后线性空间才有了方向的概念, 更进一步说也是这之后才有的正交的概念. 那你完全可以定义 \left\langle x,y \right\rangle \equiv {x}^{\text{T}Ay 嘛, 没有任何区别··· 只是这个新的内积带来的方向和原来的那个不同罢了. 如果你能理解这点, 那我们这个内积其实就不涉及两个线性空间了, 而是只涉及定义了共轭内积的那个线性空间上的运算.

听不懂就听不懂罢, 我一般也不会要求非数学系本科生能听懂这些···

但要是想搞懂的话可以参考下文:

https://zhuanlan.zhihu.com/p/445465637所谓迭代, 就是根据当前位置与上一步的信息不断地得到新的方向和新的步长来走下去.

下面我们来确定这个步长 ${\alpha }_t:$

现在要满足的要求是 r_{t}^{\text{T}A{e}_{t+1}=0.

利用关系 $e_t=x^{\ast }-x_t\Rightarrow e_{t+1}=x^{\ast }-x_{t+1}=e_t+x_t-x_{t+1},$

可得 r_{t}^{\text{T}A{e}_{t+1}=r_{t}^{\text{T}A\left( {e}_{t}+{x}_{t}-{x}_{t+1} \right)

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =r_{t}^{\text{T}A\left( {e}_{t}-{\alpha }_{t}{r}_{t} \right)

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =r_{t}^{\text{T}A{e}_{t}-{\alpha }_{t}r_{t}^{\text{T}A{r}_{t}=0.

\Rightarrow {\alpha }_{t}=\frac{r_{t}^{\text{T}A{e}_{t}{r_{t}^{\text{T}A{r}_{t} 再结合 $A{x}^{\ast }-b=0,\nabla f\left(x\right)=Ax-b,$

可得 {\alpha }_{t}=\frac{r_{t}^{\text{T}A{e}_{t}{r_{t}^{\text{T}A{r}_{t}=\frac{r_{t}^{\text{T}A\left( {x}^{*}-{x}_{t} \right)}{r_{t}^{\text{T}A{r}_{t}=\frac{r_{t}^{\text{T}\left( b-A{x}_{t} \right)}{r_{t}^{\text{T}A{r}_{t}=-\frac{r_{t}^{\text{T}\nabla f\left( {x}_{t} \right)}{r_{t}^{\text{T}A{r}_{t}.

现在消除了前面未知误差 $e$, 于是就能确定这一步的步长了.

还有一种方法就是求方向导数:

先这样看 $f\left(x_{t+1}\right)=f\left(x_t+{\alpha }_t{r}_t\right)\equiv g\left({\alpha }_t\right),$ 然后令 \frac{\text{d}g\left( {\alpha }_{t} \right)}{\text{d}{\alpha }_{t}=0\Rightarrow {\alpha }_{t}=-\frac{r_{t}^{\text{T}\nabla f\left( {x}_{t} \right)}{r_{t}^{\text{T}A{r}_{t}. 会不会算啊? $\begin{align} & \frac{\text{d}g\left( {\alpha }_{t} \right)}{\text{d}{\alpha }_{t}=\frac{\text{d}f\left( {x}_{t}+{\alpha }_{t}{r}_{t} \right)}{\text{d}\left( {x}_{t}+{\alpha }_{t}{r}_{t} \right)}\frac{\text{d}\left( {x}_{t}+{\alpha }_{t}{r}_{t} \right)}{\text{d}{\alpha }_{t} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ =\nabla f{\left( {x}_{t}+{\alpha }_{t}{r}_{t} \right)}^{\text{T}{r}_{t} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ ={\left[ A\left( {x}_{t}+{\alpha }_{t}{r}_{t} \right)-b \right]}^{\text{T}{r}_{t} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ ={\left[ \nabla f\left( x \right)+A{\alpha }_{t}{r}_{t} \right]}^{\text{T}{r}_{t}=\nabla f{\left( x \right)}^{\text{T}{r}_{t}+{\alpha }_{t}{\left( A{r}_{t} \right)}^{\text{T}{r}_{t}. \\ \end{align}$

好的现在来确定方向 $r_t:$

至于第一个方向怎么选取呢? 理论上是随便选, 不过当然选负梯度方向是坠吼滴.

给一组向量, 要得到正交化的向量, 是不是直接就想到了大一线性代数就学过的施密特正交化?

不过现在的正交是共轭正交了, 但基本上差不多是一个意思, 按照施密特正交化的原理去推导出共轭正交的一组向量就是了.

这样方向将被如此确定: {r}_{t}=-\nabla f\left( {x}_{t} \right)+\sum\limits_{i<t}{\frac{r_{i}^{\text{T}A\nabla f\left( {x}_{t} \right)}{r_{i}^{\text{T}A{r}_{i}{r}_{i}.

怎么理解上面的式子呢? 其实就是每一步的方向都是在起点的负梯度方向的基础上做修改, 也就是说进行施密特正交化的线性无关组是每一步终点的负梯度构成的. 这里开始才有了梯度, 有梯度又是共轭正交所以叫做共轭梯度法. Well, that makes a whole lot of sense.

就拿 {r}_{t}=-\nabla f\left( {x}_{t} \right)+\sum\limits_{i<t}{\frac{r_{i}^{\text{T}A\nabla f\left( {x}_{t} \right)}{r_{i}^{\text{T}A{r}_{i}{r}_{i} 这个式子说事吧:

下一步的方向第一部分是当前位置的负梯度 $-\nabla f\left(x_t\right)$ , 然后我们要在这个基础上把他在其他方向上的共轭分量减掉: -\nabla f\left( {x}_{t} \right)-\sum\limits_{i<t}{\frac{r_{i}^{\text{T}A\left[ -\nabla f\left( {x}_{t} \right) \right]}{\left\| {r}_{i} \right\|_{A}^{2}{r}_{i}.

式子第二项分母是共轭模的平方, 有共轭正交就可以共轭内积这一说吧? 自然, 共轭模. 这个自己类比一下考虑考虑吧. 这样就像是在计算 $-\nabla f\left(x_t\right)$ 在 $r_i$ 方向的分量, 然后再乘以这个方向.

这样消除其他方向上的分量, 这个矢量就肯定跟其他方向正交了吧?

消除其他方向上的共轭分量, 这个矢量肯定就跟其他方向共轭正交了吧?

互联网上搜索共轭梯度法最后得到的公式似乎都不尽相同对吧?

比如说该用到施密特正交化的方向迭代部分怎么就没有连加符号了呢? 然后步长优化也有或多或少的区别, 甚至梯度的算法都能用一个式子迭代出来. 这是不是说明大家讲的并不是同一种方法呢?

实际上共轭梯度法就是这么个思路, 最基本的就是我上面讲到的部分. 至于那些更简洁的结果都只是进行了更深一步的优化, 在理解了共轭 + 梯度这个核心思路之后那些数学上的优化是不难理解的, 上面都搞明白了的话可以随便网上找一篇文章都看的懂了. 考虑到一节课的时间并不富裕这部分就不予以讨论了.