拟牛顿法及相关讨论

  • strict warning: Non-static method view::load() should not be called statically in /home/vasp/wwwroot/drupal-6.33/sites/all/modules/views/views.module on line 906.
  • strict warning: Declaration of views_handler_argument::init() should be compatible with views_handler::init(&$view, $options) in /home/vasp/wwwroot/drupal-6.33/sites/all/modules/views/handlers/views_handler_argument.inc on line 744.
  • strict warning: Declaration of views_plugin_row::options_validate() should be compatible with views_plugin::options_validate(&$form, &$form_state) in /home/vasp/wwwroot/drupal-6.33/sites/all/modules/views/plugins/views_plugin_row.inc on line 134.
  • strict warning: Declaration of views_plugin_row::options_submit() should be compatible with views_plugin::options_submit(&$form, &$form_state) in /home/vasp/wwwroot/drupal-6.33/sites/all/modules/views/plugins/views_plugin_row.inc on line 134.

使用导数的最优化算法中,拟牛顿法是目前为止最为行之有效的一种算法,具有收敛速度快、算法稳定性强、编写程序容易等优点。在现今的大型计算程序中有着广泛的应用。本文试图介绍拟牛顿法的基础理论和若干进展。

牛顿法 (Newton Method)

牛顿法的基本思想是在极小点附近通过对目标函数TeX Embedding failed!做二阶Taylor展开,进而找到TeX Embedding failed!的极小点的估计值[1]。一维情况下,也即令函数TeX Embedding failed!

TeX Embedding failed!

则其导数TeX Embedding failed!满足

TeX Embedding failed!

因此

TeX Embedding failed!       (1)

TeX Embedding failed!作为TeX Embedding failed!极小点的一个进一步的估计值。重复上述过程,可以产生一系列的极小点估值集合TeX Embedding failed!。一定条件下,这个极小点序列TeX Embedding failed!收敛于TeX Embedding failed!的极值点。

将上述讨论扩展到TeX Embedding failed!维空间,类似的,对于TeX Embedding failed!维函数TeX Embedding failed!

TeX Embedding failed!

其中TeX Embedding failed!TeX Embedding failed!分别是目标函数的的一阶和二阶导数,表现为TeX Embedding failed!维向量和TeX Embedding failed! TeX Embedding failed! TeX Embedding failed!矩阵,而后者又称为目标函数TeX Embedding failed!TeX Embedding failed!处的Hesse矩阵。 设TeX Embedding failed!可逆,则可得与方程(1)类似的迭代公式:

TeX Embedding failed!     (2)

这就是原始牛顿法的迭代公式。

原始牛顿法虽然具有二次终止性(即用于二次凸函数时,经有限次迭代必达极小点),但是要求初始点需要尽量靠近极小点,否则有可能不收敛。因此人们又提出了阻尼牛顿法[1]。这种方法在算法形式上等同于所有流行的优化方法,即确定搜索方向,再沿此方向进行一维搜索,找出该方向上的极小点,然后在该点处重新确定搜索方向,重复上述过程,直至函数梯度小于预设判据TeX Embedding failed!。具体步骤列为算法1
 

算法1:

(1)  给定初始点TeX Embedding failed!,设定收敛判据TeX Embedding failed!TeX Embedding failed!.

(2)  计算TeX Embedding failed!TeX Embedding failed!.

(3)  若TeX Embedding failed! < TeX Embedding failed!,则停止迭代,否则确定搜索方向TeX Embedding failed!.

(4)  从TeX Embedding failed!出发,沿TeX Embedding failed!做一维搜索,

TeX Embedding failed!

TeX Embedding failed!.

(5)  设TeX Embedding failed!,转步骤(2).
 

在一定程度上,阻尼牛顿法具有更强的稳定性。

拟牛顿法 (Quasi-Newton Method)
 

如同上一节指出,牛顿法虽然收敛速度快,但是计算过程中需要计算目标函数的二阶偏导数,难度较大。更为复杂的是目标函数的Hesse矩阵无法保持正定,从而令牛顿法失效。为了解决这两个问题,人们提出了拟牛顿法。这个方法的基本思想是不用二阶偏导数而构造出可以近似Hesse矩阵的逆的正定对称阵, 从而在"拟牛顿"的条件下优化目标函数。构造方法的不同决定了不同的拟牛顿法。

首先分析如何构造矩阵可以近似Hesse矩阵的逆:

设第k次迭代之后得到点TeX Embedding failed!,将目标函数TeX Embedding failed!TeX Embedding failed!处展成Taylor级数,取二阶近似,得到

TeX Embedding failed!

因此

TeX Embedding failed!

TeX Embedding failed!,则

TeX Embedding failed!      (3)

TeX Embedding failed!

同时设Hesse矩阵TeX Embedding failed!可逆,则方程(3)可以表示为

TeX Embedding failed!      (4)

因此,只需计算目标函数的一阶导数,就可以依据方程(4)估计该处的Hesse矩阵的逆。也即,为了用不包含二阶导数的矩阵TeX Embedding failed!近似牛顿法中的Hesse矩阵TeX Embedding failed!的逆矩 阵,TeX Embedding failed!必须满足

TeX Embedding failed!      (5)

方程(5)也称为拟牛顿条件。不加证明的,下面给出两个最常用的TeX Embedding failed!构造公式

DFP公式

设初始的矩阵TeX Embedding failed!为单位矩阵TeX Embedding failed!,然后通过修正TeX Embedding failed!给出TeX Embedding failed!,即

TeX Embedding failed!

DFP算法中定义校正矩阵为

TeX Embedding failed!

因此

TeX Embedding failed!      (6)

可以验证,这样产生的TeX Embedding failed!对于二次凸函数而言可以保证正定,且满足拟牛顿条件。

BFGS公式

BFGS公式有时也称为DFP公式的对偶公式。这是因为其推导过程与方程(6)完全一样,只需要用矩阵TeX Embedding failed!取 代TeX Embedding failed!,同时将TeX Embedding failed!TeX Embedding failed!互换,最后可以得到

TeX Embedding failed!       (7)

这个公式要优于DFP公式,因此目前得到了最为广泛的应用。

利用方程(6)或(7)的拟牛顿法计算步骤列为算法2

算法2:

(1)  给定初始点TeX Embedding failed!,设定收敛判据TeX Embedding failed!TeX Embedding failed!.

(2)  设TeX Embedding failed!,计算出目标函数TeX Embedding failed!TeX Embedding failed!处的梯度TeX Embedding failed!.

(3)  确定搜索方向TeX Embedding failed!

TeX Embedding failed!.

(4)  从TeX Embedding failed!出发,沿TeX Embedding failed!做一维搜索,满足

TeX Embedding failed!

TeX Embedding failed!.

(5)  若TeX Embedding failed!,则停止迭代,得到最优解TeX Embedding failed!,否则进行步骤(6).

(6)  若TeX Embedding failed!,则令TeX Embedding failed!,回到步骤(2),否则进行步骤(7).

(7)  令TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!,利用方程(6)或(7)计算TeX Embedding failed!,设TeX Embedding failed!,回到步骤(3)。
 

限域拟牛顿法(Limited Storage Quasi-Newton Method)
 

算法2的步骤(3)中,为了确定第TeX Embedding failed!次搜索方向,需要知道对称正定矩阵TeX Embedding failed!,因此 对于TeX Embedding failed!维的问题,存储空间至少是TeX Embedding failed!,对于大型计算而言,这显然是一个极大的缺点。作为比较,共轭梯度法只需要存储3个TeX Embedding failed!维向量。为了解决这个问题,Nocedal首次提出了基于BFGS公式的限域拟牛顿法(L-BFGS)[2]。

L-BFGS的基本思想是存储有限次数(如TeX Embedding failed!次)的更新矩阵TeX Embedding failed!,如果TeX Embedding failed! > TeX Embedding failed!的话就舍弃TeX Embedding failed!次以前的TeX Embedding failed!,也即L-BFGS的记忆只有TeX Embedding failed!次。如果TeX Embedding failed!,则L- BFGS等价于标准的BFGS公式。

首先将方程(7)写为乘法形式:

TeX Embedding failed!      (8)

其中TeX Embedding failed!TeX Embedding failed!TeX Embedding failed! TeX Embedding failed! TeX Embedding failed!的矩阵。乘法形式下"舍弃"等价于置TeX Embedding failed!TeX Embedding failed!。容易得出,给 定TeX Embedding failed!后,BFGS的矩阵更新可以写为

TeX Embedding failed!,则

TeX Embedding failed!
         TeX Embedding failed!
         TeX Embedding failed!
         TeX Embedding failed!
         TeX Embedding failed!
         TeX Embedding failed!          (9)

 

TeX Embedding failed! > TeX Embedding failed!,则

TeX Embedding failed!
         TeX Embedding failed!
         TeX Embedding failed!
         TeX Embedding failed!
         TeX Embedding failed!         (10)

方程(9)和(10)称为狭义BFGS矩阵(special BFGS matrices)。仔细分析这两个方程以及TeX Embedding failed!TeX Embedding failed!的定义,可以发现L-BFGS方法中构造TeX Embedding failed!只需要保留TeX Embedding failed!TeX Embedding failed!维向量:TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!以及TeX Embedding failed!(对角阵)。

快速计算TeX Embedding failed!

L-BFGS算法中确定搜索方向TeX Embedding failed!需要计算TeX Embedding failed!,下列算法可以高效地完成计算任务:

算法3:

IF TeX Embedding failed! Then

   TeX Embedding failed! = 0; TeX Embedding failed! = TeX Embedding failed!

ELSE

   TeX Embedding failed! = TeX Embedding failed!; TeX Embedding failed! = TeX Embedding failed!

ENDIF

TeX Embedding failed!;

DO TeX Embedding failed! = (TeX Embedding failed!-1),0,-1

   TeX Embedding failed!;

   TeX Embedding failed!;

   TeX Embedding failed!储存TeX Embedding failed!;

   TeX Embedding failed!;

ENDDO

TeX Embedding failed!;

DO TeX Embedding failed! = 0, (TeX Embedding failed!-1)

   TeX Embedding failed!;

   TeX Embedding failed!;

   TeX Embedding failed!;

ENDDO

完整的程序包可从下列网址下载:

http://www.ece.northwestern.edu/~nocedal/software.html

针对二次非凸函数的若干变形

对于二次凸函数,BFGS算法具有良好的全局收敛性。但是对于二次非凸函数,也即目标函数Hesse矩阵非正定的情况,无法保证按照BFGS算法构造的拟牛顿方向必为下降方向。为了推广BFGS公式的应用范围,很多工作提出了对BFGS公式稍作修改或变形的办法。下面举两个例子。

Li-Fukushima方法[3]

Li和Fukushima提出新的构造矩阵TeX Embedding failed!的方法:

TeX Embedding failed!

TeX Embedding failed!          (11)

其中

TeX Embedding failed!
TeX Embedding failed!
 

TeX Embedding failed!的定义见算法2中步骤(7),而

TeX Embedding failed!

除此之外,算法2中步骤(3)的一维搜索采用如下方式:

给定两个参数TeX Embedding failed!TeX Embedding failed!,找出最小的非负整数j,满足

TeX Embedding failed!

TeX Embedding failed!,步长TeX Embedding failed!

Xiao-Wei-Wang方法[4]

Xiao、Wei和Wang提出了计入目标函数值TeX Embedding failed!的另一种TeX Embedding failed!的构造方法:

TeX Embedding failed!,其中

TeX Embedding failed!

TeX Embedding failed!的构造方法与方程(7)和(11)形式相同:

TeX Embedding failed!        (12)
相应的TeX Embedding failed!
而一维搜索则采用弱Wolfe-Powell准则:

给定两个参数TeX Embedding failed!TeX Embedding failed!,找出步长TeX Embedding failed!,满足

TeX Embedding failed!          (13)

TeX Embedding failed!       (14)

如果TeX Embedding failed! = TeX Embedding failed!满足方程(13)、(14),则取TeX Embedding failed! = TeX Embedding failed!

可以看出,这两种方法只是改变了TeX Embedding failed!的定义方式,其他则与标准的BFGS方法完全一样。因此将二者推广到限域形式是非常直接的,这里不再给出算法。对于二次非凸函数的拟牛顿方法还在进一步发展当中,上述的两个例子并不一定是最佳算法。

一维搜索

使用导数的优化算法都涉及到沿优化方向TeX Embedding failed!的一维搜索。事实上一维搜索算法本身就一个非常重要的课题,分为精确一维搜索以及非精确一维搜索。标准的拟牛顿法或L-BFGS均采用精确一维搜索。与前者相比,非精确一维搜索虽然牺牲了部分精度,但是效率更高,调用函数的次数更少。因此 Li-Fukushima方法和Xiao-Wei-Wang方法中均采用了这类算法。不加证明的,本节分别给出两类范畴中各自的一个应用最为广泛的例子, 分别是二点三次插值方法Wolfe-Powell准则

二点三次插值方法

在精确一维搜索各种算法中,这种方法得到的评价最高。其基本思想是选取两个初始点TeX Embedding failed!TeX Embedding failed!,满足TeX Embedding failed! < TeX Embedding failed!; TeX Embedding failed! < TeX Embedding failed!; TeX Embedding failed! > TeX Embedding failed!。这样的初始条件保证了在区间TeX Embedding failed!中存在极小点。利用这两点处的函数值TeX Embedding failed!TeX Embedding failed!(记为TeX Embedding failed!TeX Embedding failed!)和导数值TeX Embedding failed!TeX Embedding failed!(记为TeX Embedding failed!TeX Embedding failed!)构造一个三次多项式TeX Embedding failed!,使 得TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!处与目标函数TeX Embedding failed!有相同的函数值和导数值,则设TeX Embedding failed!,那么通过4个边界条件可以完全确定TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!4个参数。之后找 出TeX Embedding failed!的零点TeX Embedding failed!,作为极小点的一个进一步的估计。可以证明,由TeX Embedding failed!出发,最佳估计值的计算公式为

TeX Embedding failed!          (15)

为了避免每次都要求解4维线性方程组的麻烦,整个搜索过程可以采用算法4

算法4:

(1)  给定初始点TeX Embedding failed!TeX Embedding failed!,满足TeX Embedding failed! < TeX Embedding failed!,计算函数值TeX Embedding failed!TeX Embedding failed!和导数值TeX Embedding failed!TeX Embedding failed!,并且TeX Embedding failed! < TeX Embedding failed!TeX Embedding failed! > TeX Embedding failed!,给定允许误差TeX Embedding failed!

(2)  计算如下方程,得到最佳估计值TeX Embedding failed!

TeX Embedding failed!        (16)

TeX Embedding failed!        (17)

(3)  若TeX Embedding failed!,则停止计算,得到点TeX Embedding failed!;否则进行步骤(4)。

(4)  计算TeX Embedding failed!TeX Embedding failed!。若TeX Embedding failed!,则停止计算,得到点TeX Embedding failed!,

TeX Embedding failed! < TeX Embedding failed!,则令TeX Embedding failed!,转步骤(2);

TeX Embedding failed! > TeX Embedding failed!,则令TeX Embedding failed!,转步骤(2)。
 

利用三次函数插值,方程(16)、(17)并不是唯一的方法,也可以利用下式计算TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!三个参数:

TeX Embedding failed!
TeX Embedding failed!         (18)
TeX Embedding failed!

然后利用(15)式寻找最佳点TeX Embedding failed![5]。此外,即使TeX Embedding failed! < TeX Embedding failed!,一般而言也可以用(15)式外推寻找TeX Embedding failed!(参见[5])。

Wolfe-Powell准则

不等式(13)、(14)给出了这种非精确一维搜索算法。如果我们将不等式(14)用下式替换:

TeX Embedding failed!     (19)

也即
 

TeX Embedding failed!

则不等式(13)、(19)称为强Wolfe-Powell准则。其重要性在于当TeX Embedding failed!时,该方法过渡为精确一维搜索算法[6]。算法如下[5]

算法5:

(1)  给定两个参数TeX Embedding failed!TeX Embedding failed!TeX Embedding failed!为初始点(相应于TeX Embedding failed!),TeX Embedding failed!为猜想点(可设为1)。计算两点处的函数值TeX Embedding failed!TeX Embedding failed!和导数值TeX Embedding failed!TeX Embedding failed!。给定最大循环次 数TeX Embedding failed!,设TeX Embedding failed!

(2) 若TeX Embedding failed!TeX Embedding failed!违反不等式(13)或者不等式(19)的右半段,则缩小搜索范围的上限TeX Embedding failed!,否则转步骤(5);

(3)  若TeX Embedding failed! > TeX Embedding failed!,利用二次插值方法寻找最佳点TeX Embedding failed!

TeX Embedding failed!

TeX Embedding failed!,计算TeX Embedding failed!TeX Embedding failed!;设TeX Embedding failed!,若TeX Embedding failed!转步骤(2),否则转步骤(5);

TeX Embedding failed!,转步骤(4);

(4)  利用式(16)、(17)(或者式(15)、(18))寻找最佳点TeX Embedding failed!。令TeX Embedding failed!,计算TeX Embedding failed!TeX Embedding failed!;设TeX Embedding failed! = TeX Embedding failed!,若TeX Embedding failed!,转步骤(2),否则转步骤(5);

(5)  若TeX Embedding failed!满足不等式(19)的左半段,则停止计算,得到最佳点TeX Embedding failed!;否则转步骤(6);

(6)  利用式(16)、(17)(或者式(15)、(18))寻找最佳点TeX Embedding failed!,并计算TeX Embedding failed!以及TeX Embedding failed!;设TeX Embedding failed!,若TeX Embedding failed!转步骤(2),否则转步骤(7);

(7)  停止计算得到目前最佳估计值TeX Embedding failed!
 

需要补充说明的是步骤(4)可以有不同的估算方法,例如

TeX Embedding failed!      (20)
 

此外,点TeX Embedding failed!处的导数值TeX Embedding failed!,因为在一维搜索中,TeX Embedding failed!相当于待求步长TeX Embedding failed!。在大多数情况下,TeX Embedding failed! = TeX Embedding failed!以及TeX Embedding failed! = TeX Embedding failed!可以取得很好的效果。Wolfe-Powell准则的几何意义可以参考文献[5][6]。

参考文献

【1】  陈宝林  《最优化理论与算法(第二版)》 (清华大学出版社 2005) 第9-10章.
【2】  J. Nocedal, Math. Comput. 35, 773 (1980).
【3】  D.H. Li and M. Fukushima, J. Comput. Appl. Math. 129, 15 (2001).
【4】  Y. Xiao, Z. Wei and Z. Wang, Comput. Math. Appl. 56, 1001 (2008).
【5】  www.cs.toronto.edu/~delve/methods/mlp-ese-1/minimize.ps.gz
【6】  W. Sun and Y.X. Yuan, Optimization theory and methods (Springer 2006), p. 104.