共轭梯度法

一: 共轭方向法
共轭方向法是介于最速下降法与牛顿法之间的一个方法, 它仅需利用一阶导数信息, 但克服了最速下降法收敛慢的缺点, 又避免了存储和计算牛顿法所需要的二阶导数信息. 共轭方向法是从研究二次函数的极小化产生的, 但是它可以推广到处理非二次函数的极小化问题. 最典型的共轭方向法是共轭梯度法. 而拟牛顿法也是共轭方向法的一种.

共轭方向的概念是这么定义的: 设\(G\)是\(n \times n\)对称矩阵, \({d_1},{d_2}\)是\(n\)维非零向量, 如果\(d_1^TG{d_2} = 0\), 则称向量\({d_1},{d_2}\)是\(G – \)共轭的. 类似地, 设\({d_1},{d_2},…,{d_m}\)是\({R^n}\)中的任意一组非零向量. 若有\(d_i^TG{d_j} = 0,(i \ne j)\), 则称\({d_1},{d_2},…,{d_m}\)是\(G – \)共轭的.
显然地, 当\(G\)是\(n\)阶单位矩阵时, \(d_i^T{d_j} = 0,(i \ne j)\), 即是正交向量组. 因而共轭概念是正交概念的推广. 但要注意, 正交的向量不一定共轭, 共轭的向量不一定正交, 有时, 可能既共轭又正交.

为什么要引入共轭向量组呢, 因为它有如下重要的性质:
1). 若\({d_1},{d_2},…,{d_m}\)是一组\(G – \)共轭方向, 则它们一定是线性无关的;
2). 对于正定二次函数, 共轭方向之多经过\(n\)步精确线性搜索可达到整体最优解.

通常, 我们把从任意点出发, 依次沿某组共轭方向进行一维搜索求解的方法, 叫做共轭方向法. 由于共轭方向组的取法有很大的随意性, 用不同方式产生一组共轭方向就得到不同的共轭方向法. 如果利用迭代点处的负梯度向量为基础产生一组共轭方向, 这样的方法叫做共轭梯度法.

二: 共轭梯度法
为了满足共轭方向组的定义, 我们可以推出这样一组迭代公式:
\[\left\{ {\begin{array}{*{20}{c}}
{{d_0} = - {g_0}}&{}\\
{{d_{k + 1}} = - {g_{k + 1}} + {\beta _k}{d_{k,}}}&{k = 0,1,...,n - 2}\\
{{\beta _k} = \frac{{g_{k + 1}^TG{d_k}}}{{d_k^TG{d_k}}}}&{}
\end{array}} \right.\]
利用二次凸函数的结构和精确一维搜索的性质可以得到更简化的迭代形式:
\[\left\{ {\begin{array}{*{20}{c}}
{{d_0} = - {g_0}}&{}\\
{{d_{k + 1}} = - {g_{k + 1}} + {\beta _k}{d_{k,}}}&{k = 0,1,...,n - 2}\\
{{\beta _k} = \frac{{g_{k + 1}^T{g_{k + 1}}}}{{g_k^T{g_k}}}}&{}
\end{array}} \right.\]
上式是由Fletcher和Reeves于1964年提出来的, 通常称为Fletcher-Reeves共轭梯度法, 简称F-R法.
用F-R法求解二次凸优化问题时, 它具有二次终止性质, 但用F-R法来求解非二次函数, \(n\)步以后共轭梯度法产生的搜索方向\({d_k}\)不再共轭, 因此\(n\)步以后我们需要周期性地采用最速下降方向作为搜索方向, 即令\({d_{cn}} = – {g_{cn}},c = 1,2,…\). 这种方法叫做再开始共轭梯度法. 对于大型问题, 会经常地进行再开始. 再开始共轭梯度法允许采用近似线性搜索过程, 只是在采用近似线性搜索的同时, 要采用一定的检查措施, 以保证得到的搜索方向是下降方向. 而同样面临的问题是, 如果频繁地利用最速下降方法作为搜索方向, 将大大削弱共轭梯度法的效率, 从而使算法的性态变得更像最速下降法. 需要进一步采取措施克服这个困难. 因而一般来说F-R方法强烈地依赖于一维搜索的精确性, 当一维搜索不能保证有精确性时, 我们可用Polak-Ribiere-Polyak共轭梯度法, 简称P-R-P法. P-R-P法与F-R法不同的仅仅是步长的计算公式不同, \({\beta _k} = \frac{{g_{k + 1}^T({g_{k + 1}} – {g_k})}}{{g_k^T{g_k}}}\). P-R-P有自动再开始的显著优点. 当算法前进很少时, 会出现\({g_{k + 1}} \approx {g_k}\), 这时P-R-P公式产生\({\beta _k} \approx 0\). 因此\({d_{k + 1}} \approx – {g_{k + 1}}\), 即算法有自动再开始的趋势, 这样有利于克服进展缓慢的缺点. 一些实验结果表明, 对一些大型问题, P-R-P公式效果较好. 然而1984年Powell M J D提出了反例来说明在存在某些问题, P-R-P法不收敛, 而F-R法具有全局收敛性.

在实践中证明十分有效的无约束最优化方法, 除了共轭梯度法以外, 还有变尺度算法. 它们的结构原理都是基于二次函数模型产生下降方向, 然后由线性搜索选择在该方向上的步长. 变尺度算法也是一类方法的总称, 使用比较普遍的有DFP方法和BFGS方法, 这些方法是相当于迭代的每一轮的度量是变化的最速下降法, 因而得此名. 数值实验指出, BFGS算法是最好的变尺度算法, 当变量个数不超过100时, 通常BFGS法比共轭梯度法效果好. 但对于变量个数超过100的大规模无约束游湖问题, 共轭梯度法因其不要太大的存储量而更具优势.

信赖域法是目前正在发展中的一种无约束最优化方法. 它是针对共轭梯度法和变尺度法的缺点设计的.

[参考] 1. <最优化理论与方法>.袁亚湘院士著.
2.<运筹学>.习在筠等著

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>