共轭梯度
参考
主要参考这篇文章，非常推荐查看，文章最后还有个关于共轭梯度的图
Conjugate gradient method wiki
Gram-Schmidt方法 wiki
在介绍共轭梯度之前，我们先介绍一下Gram-Schmidt过程(革兰氏-施密特方法)，看它如何对向量组进行正交归一化。
首先定义投影操作：
其中表示向量u,v的在
上的内积。该运算符将向量
正交投影到向量
所跨越的线上。如果
，我们定义
。
Gram-Schmidt过程的工作原理如下：
该方法进行如下运算：为了计算，它首先将
正交投影到
上，然后从向量
中减去为
与每个投影之间的差，从而保证与空间中的所有向量(
)正交。
图来源wiki
最终原理图如下所示：
optimization图23.gif
什么是共轭？
对矩阵对称正定，而
是
中任意一组非零向量，若
，则称向量组
是相对于
共轭的。
由于矩阵是是对称
且正定的，则关于其的共轭内积可定义为：
。
(由于我们将要处理的是共轭而不是正交(时为正交)，所以在要运用Gram-Schmidt方法时需要运用共轭形式的内积。)
进入正题：
模型建立
假定待优化的函数：
(其中为待优化变量，
为正定矩阵，
为已知变量。)
下标k表示优化步数，负梯度为：
假设最优变量为，则优化问题可变为求方程
的解。梯度
也可以称作为每一步的残差。
算法推导
优化方向确定：
假定第一次优化方向为初始负梯度方向：
每一次优化方向与之前的优化方向正交，采用Gram-Schmidt方法进行向量正交化，每次优化方向根据当前步的梯度得出：
再令(这个
计算出来是个实数)，则有：
。
优化步长确定：
假定第步的优化步长为
。
对求导令导数为零有：
(行搜索)。
共轭梯度其实到这里已经证明结束了，但一般选择其化简式。所以接下来对等式进行化简：
误差定义为
与最优变量
的差值:
对残差有：
在得到最终的等式前，证明下面两个性质：
1.残差与之前的所有的方向正交
证明：
任取一个方向，并且
：
2.残差与之前的所有的残差正交
如果残差与搜索方向形成向量基正交，那么残差也会形成向量基。这意味着任何残差都与它先前的残差正交。
证明如下：
当时：
右乘：
基于残差的梯度步长：(求简化的)
由之前可得：
又由于：则：
(
)
又因为：
正交化步骤仅取决于先前的搜索方向：：(求简化的)
(更新
的值)
(的值为实数)
前乘值，求新的
值：
又因为：
用代替
有：
得到
变化一下得：
又因为：
可简化为：
其中：
伪代码：
在简化后：
repeat
until
(残差小于某个值便可以跳出来了。)
return
网友评论