二次型优化问题 - 6 - 共轭梯度法

本文介绍二次型优化方法中比较优秀的迭代方法——共轭梯度法。

问题描述

重述我们需要优化的问题：

f({bf{x} }) = frac{1}{2}{bf{x^TAx} } - { {bf{b} }^{bf{T} } }{bf{x} } {bf{c} } tag{1} label{1}

矩阵bf{A}正定对称
目标为优化bf{x}，使得f(bf{x})取得最小值

最速下降法的问题

贪心计算局部最小值
没有全局视野，没有使用真正的模型建模
导致优化过程需要反复迭代才能逐步逼近最优值

轭

轭是一个汉字，读作è，本意是指驾车时套在牲口脖子上的曲木，引申义是束缚，控制。该文字在《仪礼·既夕礼》和《荀子·正论》等文献均有记载。 ——百度百科

数学中很多轭相关的内容，此处的共轭表示相互约束，在某个条件下可以相互作用的意思。

共轭梯度法思想来源

为解决最速下降法来回往复的问题，人们开始思考是否有可以直接在需要优化的二次函数定义下直接对其进行优化，是否可以通过有限步计算得到真正的最优解
那么假设我们使用关于该问题精确的模型而不是近似的局部最优模型，我们如果可以在某个N维空间中，分别计算出最优解的各个维度的坐标，就可以达到上述目的
那么如何设计这个空间，如何可以分步计算并且可以整合成真正的结果，是共轭梯度法来解决的问题
该方法的核心思想是建立一组N维空间线性无关的一组基，理论上这组基的线性组合可以表示空间中任意一点，共轭梯度法通过多次计算，精确求解目标在空间中位置在这组基空间中的各个系数分量，达到求解最优值的目的
该方法和最速下降法却别在精确建模，有了上帝视角，每次迭代计算将该方向需要调整的分量值调整到极致，也就是说之后的计算再也不用考虑该方向上的运动分量了，这是一个精确求解问题的过程，不是逐步简单建模向最优值挪动的逼近过程

共轭基的定义

设bf{A}为n阶实对称正定矩阵，如果有两个n维列向量bf{s}_1和bf{s}_2满足

则称向量bf{s}_1和bf{s}_2对于矩阵bf{A}共轭。如果bf{A}为单位矩阵，则式eqref{2}即成为bf{s}_1bf{s}_2，这样两个向量的点积为零，此二向量在几何上是正交的，它是共轭的一种特例。

设A为对称正定矩阵，若一组非零向量bf{s}_1,bf{s}_2,…,bf{s}_n满足

则称向量系

为关于矩阵A共轭。若

之间线性无关，那么我们称该向量集合为n维空间中关于矩阵A的一组共轭基。

共轭基的作用

假设有一组关于矩阵bf{A}的共轭基bf{D}：

bf{D}={ {bf{d}_1},{bf{d}_2},…,{bf{d}_n}} tag{4}

设二次型函数eqref{1}的极值为bf{x}^*，用bf{D}表似为：

因为函数极值处在各个方向的导数为0有：

我们计算{bf{d}}_i^T{bf{A}}{{bf{x}}^*}，根据不同共轭基之间相互共轭：

得到：

对于{lambda _i}的求解，我们已知的变量为bf{b}和bf{A}，如果我们已经得到了空间中关于bf{A}的共轭基（任意一组），我们都可以直接解得{lambda _i}
这是一个令人振奋的结论，所以我们当前的工作重点转为了如何快速地求得一组关于bf{A}的共轭基

根据定义获取共轭基

有了定义，我们不难想到暴力获取共轭基的方法：

这套方法下来，我们就可以得到根据定义计算出来的共轭基，带入eqref{8}计算得到极值，没有任何问题
但事实上这个运算量与代数法解{bf{A}}{{bf{x}}} = {bf{b}}的过程具有相当的运算复杂度，没有给该优化问题带来性能收益

共轭梯度法

此算法核心步骤与最速下降法相同，分别为寻找共轭方向与计算运动步长。

寻找共轭方向

由于计算梯度简单，寻找共轭梯度的过程依附于梯度方向的计算。

优化目标为bf{x}^*，初始位置为bf{x}_1，需要求得的共轭基为 bf{D}={ {bf{d}_1},{bf{d}_2},…,{bf{d}_n}}
计算初始bf{x}_1位置的梯度，第一个共轭基为梯度的反方向：

第i个梯度若要剔除掉第j个共轭基(j<i)beta_j 分量：

因此第k个共轭基为：

目前，我们如果可以确定每一次迭代移动的bf{x}_i的位置，求得bf{g}_i，那么就可以根据第1到第i-1个共轭基确定当前第i个共轭基
因此当前我们的目标是在有了共轭方向后，如何确定在该方向上的运动距离

确定运动距离

已经运动到了

的位置，下一个前进方向为

，前进步长

，误差为

，也就是说：

这里介绍两种求前进步长{alpha _k}的思路。

方法一

确定第k步的运动步长{alpha _k}，也就是一个共轭基的系数，限制该系数的条件为：

当前共轭基的方向bf{d}_{k}与误差向量bf{e}_{k 1}=bf{x}^*-x_{k 1}共轭：

有：

方法二

对

中的

求导，使得导数为0，计算

用{{bf{x}}_k}表示{{bf{x}}_{k 1}}:

对f({{bf{x}}_{k 1}})中{alpha _k}求导:

使导数为0，有:

此时我们已经计算得到了一系列计算共轭梯度的方法，能够依次求得一套共轭基了，但是其中有些步骤仍然可以继续简化计算。

简化计算与一些推论

推论一

第k步计算的梯度bf{g}_k和前k-1步的共轭向量{bf{d}_1,bf{d}_1,...,bf{d}_{k-1}}正交:
证明，当

式eqref{18}左边由于bf{d}_i计算过程eqref{13}为0，右边由于不同的共轭向量间两两共轭值为0，所以最终的值也为0
因此证明了：第 k 步计算的梯度 bf{g}_k 和前k-1步的共轭向量 { bf{d}_1,bf{d}_1,...,bf{d}_{k-1}}正交。

推论二

第k步计算的梯度bf{g}_k和前k-1步的梯度{bf{g}_1,bf{g}_1,...,bf{g}_{k-1}}正交:
证明，当i < j
由eqref{11}得：

有：

根据推论一，式eqref{20}值为0
证得结论：第k步计算的梯度bf{g}_k和前k-1步的梯度{bf{g}_1,bf{g}_1,...,bf{g}_{k-1}}正交。
那么对于两个不同的梯度bf{g}_i, bf{g}_j(i ne j)，那么二者必分前后，因此各个梯度之间相互正交，即{bf{G}} = { {{bf{g}}_{1,}}{{bf{g}}_2},...,{{bf{g}}_n}} 组成了n维空间中的一组正交基