共轭梯度法
误差和残差
误差: 和梯度法介绍的 不同(当然这应该也不叫误差),
误差是迭代算法在某个迭代过程中得到的点与极小点的差距, 即 或 这里采用前者, 并记 并且对于收敛的序列
可以证明
这也就是为什么我们可以在梯度法中采用那样的停机条件了.
残差: 残差是迭代过程中得到的某个点 对应的函数值与极小点对应的函数值之差.
但是我们在此并不采用函数而是采用导函数即
因为
的性质对我们来说非常有用. 对于二次型函数 有
于是
或者
后者表明了对于二次型函数残差实际上是误差 在线性变换 下得到的, 同时 处的残差 实际上是该处的负梯度,
这便是采用导函数而不采用原函数的目的, 即即使不知道极小点 也能计算残差,
同时这也是使用梯度范数作为停机条件的另一个说明.
一般意义的共轭方向法
为了使共轭概念引入得更为自然，我们暂时先不引入向量共轭的概念。不过相比最速下降法与牛顿法，下面引入共轭法的过程实际上有点像先射箭后画靶子。
对于一个函数
假如我们已经知道了它的极小点 现在我们抛开函数 仅考虑从初值点 到达 的方式,
并且是有规律可循的方式.
显然最简单的方式就是在
处沿着向量
的方向直接移动, 当然这对我们的问题解决毫无用处; 如果已知 的坐标为 的坐标为
那么另一种简单且容易想到的方式就是从 出发, 每次沿着某个坐标轴的方向移动
( 与该坐标轴一致) 的距离, 一共需要前进
次, 显然这 次前进的方向 是两两正交的;
事实上, 不一定要沿着坐标轴的方向, 只需要保证这 次前进的方向
是两两正交并且步长满足一定条件, 那么在第 次就一定能到达极小点, 并且
在经过某个正交变换后其实可以变为 .
这是共轭法的核心思想.
举个例子, 比如, 在
中这种方法前进的轨迹为以 为体对角线的长方体的三条棱,
在 中前进的轨迹为以
为对角线的矩形的两条邻边.
现在我们想用这种方式来设计一种算法,
首先要找出这种方法的特殊性质以及它的迭代公式.
性质1 已知两两正交的向量 从初值点 开始, 沿着向量 前进一定距离到达 最终到达 设 那么对任意 和 正交.
PROOF 显然 于是
上述性质用语言表述就是, 某点和极小点之间的误差与上一次的前进方向正交.
实际上
而 同时
因此给每个方向赋予步长 后, 能到达 中的任意一点. 于是在已知
条件下, 一定存在 使得
那任务就是求步长了.
如果考虑 误差的意义,
前进的过程实际上是消除误差的过程,
每一次前进消除了当前点与目标点的一个维度/方向的误差(或者说，找到了这个维度上的最优解),
次之后消除了所有方向的误差(找到所有维度上的最优解)自然就达到目标点了.
现在利用误差和前进方向求出步长
注意到
于是由性质1有 因此 采用一般意义下的内积定义方式就有 但是这并没什么用, 在求函数极小点的时候, 如果要用此公式求出
就要知道 但是我们都知道 了, 还求什么极小点呢,
问题就直接解决了, 因为只有在知道极小点的情况下才能知道 这也就是先射箭后画靶子了. 显要把
换成仅当前条件下就能求出的量.
在给出最终解决办法之前, 我们可以拾起之前抛开的 了, 同样, 为了便于研究,
选择二次型函数, 即 为了避免使用需要极小点(虽然能直接求出极小点
但我们就是认为极小点是未知的)的误差 , 考虑利用残差(残差本质也是一种误差,
同时两者只有一个线性变换的关系), 如果能够让分子变成 那么就可以达到目的了.
于是更改内积的定义, 即定义 -内积
其中
可以验证定义的该内积符合内积需要满足的一般性质.
为了区别一般意义下的内积的正交, 称满足 的 关于 共轭(conjugate).
于是修正过定义后, 就有 其中
借助性质1就有 即 现在就可以给出一般的共轭方向法了:
给定初值点 和一系列关于
共轭的向量
二次型函数的共轭方向法的迭代公式为
纵观探索的整个过程, 共轭法实际上就是在给定的内积的定义下,
从初值点分别沿着一步步沿着
个正交的方向前进, 逐步消除初值点与极小点 个方向的误差, 找到每个维度的最优解,
最终到达极小点的过程.
若无特殊说明, 表示一般意义下的内积, 表示 -内积, 表示没有明确定义的内积,
仅仅是
的一个函数.
性质分析
性质2
性质3 对任意 成立.
共轭梯度法
一般意义的共轭梯度法还不够具体, 因为构造关于 共轭的向量的方法可能不止一种,
构造出来的向量也不尽相同, 这其中最有效的构造方式之一是Schmidt正交化方法,
又称为Gram-Schmidt过程,
它可以将任意一组线性无关的向量变成两两正交的向量).
Schmidt正交化方法 :
已知 线性无关.
令 对所有 满足 为 的线性组合, 并且令
的系数为 并使
得到 个方程,
解出线性组合的系数即可. 若设
且已知有
两两正交, 于是得到的 的方程为
得
于是就有下面的递推关系式: 如果想得到标准正交基, 只需要置 即可.
但是算法还是不够具体, 在应用Schmidt正交化方法之还要先产生 个线性无关的向量, 这样的算法太过"自由".
我们希望在算法执行过程中随着迭代的进行产生关于 共轭的向量 ,
而不是预先把这些向量给出来. 基于此想法, 就有共轭梯度法:
用上一个搜索方向与当前迭代点的梯度组成 共轭方向,
最简便的方式便是选择这两个向量的线性组合, 初始方向 选用负梯度即可, 于是记 令 根据 有 于是我们就可以给出共轭梯度法的迭代步骤了：
1: 置 选择初始值
2: 计算 若
则停止迭代; 反之置
3: 计算
4: 计算
5: 计算 若满足停机条件停止迭代; 否则置
6: 计算
7: 置 转第 步.
上面在导出搜索方向时只满足了相邻的两个搜索方向 共轭, 可以证明共轭梯度法的搜索方向两两
共轭.
非二次型函数的共轭梯度法
对于一般的非二次型函数,
第一想法肯定是利用Taylor展开用二次型函数进行拟合,
但是共轭法设计的初衷是找一种不用计算黑塞矩阵且速度介于最速下降法与牛顿法之间的迭代算法,
如果要用二次型函数拟合每次迭代还需要计算黑塞矩阵,
于是有必要对共轭梯度法进行修正, 消除每次迭代中求黑塞矩阵的环节.
显然 和 的求解需要用到黑塞矩阵,
而在前面已经说明过
实际上是最优步长, 因此求
的过程可以变为对 的一维搜索.
对于
有三种知名的修正公式:
Hestenes-Stiefel公式
在
两边同时乘 并减 就有 于是
因此迭代公式中的 可以写为
这是Hestenes-Stiefel公式.
有点像中值定理/割线法.
Polak-Ribière公式
PR公式在HS公式的基础上化简了分母. 注意到利用性质1得到的 的性质,
于是借此化简Hestenes-Stiefel公式就得到 同时由 两边同乘
并由 就有 因此 这是 Polak-Ribière 公式.
摆脱了上一次的搜索方向， 只需要用本次的梯度和上次的梯度。
Fletcher-Reeves公式
FR公式在PR公式的基础上又化简了分子.
对于 在两边同乘
得
借助性质3以及性质1就有 于是 这是FR公式.
得到上面三种公式的代数变形是在二次型函数的条件下进行的,
对于非二次型函数, 三者并不相等.
该选哪一个?
与目标函数有关, 不同公式适用于不同的目标函数. 当一维搜索不精确时,
建议采用 HP 方法. Powell 指出 FR
公式的性能最为突出(在全局收敛特性的分析下), 并给出了新的公式:
还能在 步骤之内收敛至极小点吗?
显然不能. 并且随着迭代的进行,
搜索的方向与前面的迭代过程中的搜索方向之间将不再是 共轭的了, 因为 的 个向量必然会线性相关,
自然就不能满足两两 -正交了,
因为正交的前提是线性无关. 虽然不能保证所有的搜索方向之间是 共轭的, 但我们可以让每 个搜索方向之间两两 共轭 ,即每迭代 或
次后就重新将搜索方向初始化为该点的梯度, 然后采用相同的方法继续迭代,
直到达到了想要的精度.
