共轭梯度法的地位与范畴

凸优化在机器学习中应用非常广泛, 发展到今天, 理论已经非常成熟.
凸优化可以再细分为 无约束优化, 等式约束优化 和 不等式约束优化

通常我们可以把约束问题转化为无约束问题来处理, 所以, 无约束最优化是优化问题的基础.

一言以蔽之, 无约束最优化问题的形式是

其中, 为目标函数, 是定义域, 求 的最小值点

在统计分析中, 参数估计都可以写成这个形式, 比如之前提到的负对数似然函数, 再如线性回归的最小二乘法

但是一般情况下, 很少能像线性回归一样直接写出参数的表达式, 因而无法得到封闭解(解析解).
我们需要借助数值方法迭代计算

常用的无约束最优化方法有:

• 最速下降法
• 牛顿法
• 共轭梯度法
• 变尺度法(拟牛顿法)

牛顿法的海森矩阵类似二次泰勒展开, 可以克服最速下降法法的锯齿现象(zigzag). 但求解海森矩阵的逆计算量很大甚至根本无法计算, 因此, 出现了迭代公式简单的 共轭梯度法 和 变尺度法. 概括说变尺度法是利用梯度的微分形式来近似海森矩阵的逆, 而共轭梯度法是利用共轭方向作为搜索方向, 减少了计算量, 思想简单, 却颇为巧妙.

共轭梯度法的数学原理

剩余的篇幅将围绕正定二次函数 试图从数学原理直观深入地解释 共轭梯度法:

其中 是 正定矩阵, 为 维向量, c是常数.

思想

正定函数 经过配方, 可改写成如下形式:

因此, 是 的最小值点, 此时:

其中, 定义

表示向量在 G 度量意义下的范数

对角单位矩阵也是正定阵, 考虑 的特殊情况

配方得 是极小值点, 考察梯度方向

可以发现, 任一点的负梯度恰好对准 , 一次一维搜素就可以直接得到极小点.

推广

不加证明给出一个定理: 在 定义域中, 依次按照 个非零正交方向搜索, 必然能够到达极小值点.

对于

使

共轭

对于 正定对称阵 , 向量 , 若内积满足:

则称它们关于 共轭.

, 也作关于 正交

不加证明给出结论, 两个对应在 空间正交的向量, 在 空间共轭, 当 退化为单位阵时, 共轭就是正交.

所以, 在 定义域中, 依次按照 个非零正交方向搜索, 最多经过 次迭代, 必然能够到达极小值点. 另外, 共轭和正交很相似; 互相共轭的方向也线性无关; 线性无关的向量可以转化成互相共轭的向量(方法类似施密特标准正交化).

算法

好了, 理论准备完毕, 下面介绍算法步骤

1. 任选初值 和方向向量 ,

2. 沿 方向直线搜索:
   

3. 计算 在 梯度 ; 若 则停止迭代. 是 的极小值点.

4. 求一个共轭方向 , s.t. 然后 , 转第 2 步

那么, 如何找出共轭方向呢?

共轭梯度法构造共轭方向

最容易想到的方法线性代数中学过, 我们可以从 个线性无关的向量组构造共轭向量. 共轭梯度法是一种完全不同的方法.

1. 任选初值 和方向向量 ,

2. 沿 方向直线搜索:
   

3. 计算 在 梯度 ; 若 则停止迭代. 是 的极小值点.

4. 构造共轭方向 , 只需如下两步:
   
   , 然后令 , 转第 2 步

算法的神奇之处在于, 对于正定二次函数, 最多迭代 次就可以得到极小点.

证明

可以证明, 与 关于 共轭.

证明:

同理, 可以用数学归纳法证明 两两共轭.

即证 不相等的任意; 和 关于共轭

证明:

令 , 假设

推广

即得证

使用和总结

我们一般使用的共轭梯度法称为 Fletcher Reeves 共轭梯度法, 它由 计算

在 的时候, 算法完全等同于最速下降法, 所以共轭梯度法的速度一定不低于最速下降法, 它是最速下降法的改进.

此外, 新手使用共轭梯度法时值得注意的是, 由于共轭梯度法非常依赖初始梯度方向, 拥有因为不能精确计算 而造成的累积误差, 在非二次函数使用共轭梯度法时往往要将 重设置为初始点再次迭代.

水平有限, 欢迎指教