牛顿法

一: 最速下降法
下降法的迭代格式为\({x_{k + 1}} = {x_k} – {\alpha _k}{d_k}\), 其中\({d_k}\)为下降方向, 设\({g_k} = \nabla f({x_k}) \ne 0\), 则下降方向要满足\(d_k^T{g_k} < 0\). 当步长确定时, \(d_k^T{g_k}\)的值越小, 即\({\rm{ - }}d_k^T{g_k}\)的值越大, 函数下降得越快. 由Cauchy-Schwartz不等式\(\left| {d_k^T{g_k}} \right| \le \left\| {{d_k}} \right\|\left\| {{g_k}} \right\|\), 当且仅当\({d_k} = - {g_k}\)时, \(d_k^T{g_k}\)的值最小. 从而\( - {g_k}\)是最速下降方向. 则最速下降法的迭代格式为\({x_{k + 1}} = {x_k} - {\alpha _k}{g_k}\).

这里要注意的是, 最速下降方向只是算法的局部性质. 对于许多问题, 最速下降法并非”最速下降”, 而是下降非常缓慢. 数值试验表明, 当目标函数的等值线接近于一个圆(球)时, 最速下降法下降较快, 而当目标函数的等值线是一个扁长的椭圆时, 最速下降法开始几步下降较快, 后来就出现锯齿现象, 下降就十分缓慢. 其原因是这样的, 由于一维搜索满足\(g_{k + 1}^T{d_k} = 0\), 即\(g_{k + 1}^T{g_k} = d_{k + 1}^T{d_k} = 0\). 表明在相邻两个迭代点上函数的两个梯度方向是互相直交的, 这就产生了锯齿形状, 当接近极小点时, 步长越小, 前进越慢.
当目标函数是二次函数时, 最速下降法的收敛速度由对应于某个等值线的椭球的最长轴与最短轴之比决定. 这个比值越大, 最速下降法下降越慢.

二: 牛顿法
牛顿法的基本思想是利用目标函数的二次Taylor展开, 并将其极小化. 也可以想成是一个一点二次插值法进行局部拟合.

带步长因子的牛顿法, 算法如下:
Step1: 选取初始数据, 取初始化点\({x_0}\), 终止误差\(\varepsilon < 0\);
Step2: 计算\({g_k}\), 若\(\left\| {{g_k}} \right\| < \varepsilon \), 停止迭代, 输出\({x_k}\). 否则进入Step3;
Step3: 解方程组构造牛顿方向, 即解\({G_k}d = - g_k^{}\), 求出\({d_k}\).
Step4: 进行一维搜索, 求\({\alpha _k}\)使得\(f({x_k} + {\alpha _k}{d_k}) = \mathop {\min }\limits_{\alpha \ge 0} f({x_k} + {\alpha _k}{d_k})\). 令\({x_{k{\rm{ + }}1}}{\rm{ = }}{x_k}{\rm{ + }}{\alpha _k}{d_k}\), \(k: = k + 1\), 转Step2.
牛顿法面临的主要困难是Hess矩阵\({G_k}\)不正定. 这时候二次模型不一定有极小点, 甚至没有平稳点. 当\({G_k}\)不定时, 二次模型函数是无界的. 为了克服这些困难, 人们提出了很多修正措施.

[参考] 1. <最优化理论与方法>袁亚湘院士著.

发表评论

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

*

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