在

处的

Hesse

矩阵。

设

可逆，则可得与方程

(1)

类似的迭代公式 ：

(2)

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

原始 牛顿法虽然具有二次终止性（即用于二次凸函数时，经有限次迭代必达极小点），但是要求初始

< br>点需要尽量靠近极小点，否则有可能不收敛。因此人们又提出了阻尼牛顿法

[1]

。这种方法在算法形

式上等同于所有流行的优化方法，即确定搜 索方向，再沿此方向进行一维搜索，找出该方向上的极小

点，然后在该点处重新确定搜索 方向，重复上述过程，直至函数梯度小于预设判据

。具体步骤列为

算法

1

。

算法

1

：

(1)

给定初始点

，

.

，设定收敛判据

(2)

计算

和

.

(3)

若

<

，则停止迭代，否则确定搜索方向

.

(4)

从

出发，沿

做一维搜索，

令

.

(5)

设

，转步骤

(2).

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

拟牛顿法

(Quasi- Newton Method)

如同上一节指出，牛顿法虽然收敛速度快，但是计算过程中需要计算目标函数的二阶偏导数，难度较

大。更为复杂的是目标函数的

Hesse

矩阵无法保 持正定，从而令牛顿法失效。为了解决这两个问题，

人们提出了拟牛顿法。这个方法的基 本思想是不用二阶偏导数而构造出可以近似

Hesse

矩阵的逆 的

正定对称阵，

从而在

拟牛顿

的条件下优化目标函 数。构造方法的不同决定了不同的拟牛顿法。

首先分析如何构 造矩阵可以近似

Hesse

矩阵的逆：

设第

k

次迭代之后得到点

，将目标函数

在

处展成

Ta ylor

级数，取二阶近似，得到

因此

令

记

(3)

，则

< br>同时设

Hesse

矩阵

可逆，则 方程

(3)

可以表示为

(4)

因此，只需计算目标函数的一阶导数，就可以依据方程

(4)

估计该处的

Hesse

矩阵的逆。也即，为了

用不包含二阶导数的矩阵

近似牛顿法中的

Hes se

矩阵

必须满足

阵，

的逆矩

(5)

方程

(5)

< br>也称为拟牛顿条件。不加证明的，下面给出两个最常用的

构造公式

DFP

公式

设初始的矩阵

为单位矩阵

，然后通过修正

，即

DFP

算法中定义校正矩阵为

因此

可以 验证，这样产生的

保证正定，且满足拟牛顿条件。

BFGS

公式

(6)

对于二次凸函数而言可以

BFGS

公式有时也称为

DFP

公式的对偶公式。

这是因为其推导过程与方程

(6)

完全一样，

只需要用矩

阵

取

代

，同时将

和

互换，最后可以得到

(7)

这个公式要优于

DFP

公式，因此目前得到了最为广泛的应用。

利 用方程

(6)

或

(7)

的拟牛顿法计算步骤列为

算法

2

。

算法

2

：

(1)

给定初始点

，

.

，设定收敛判据

(2)

设

，计算出目标函数

在

(3)

确定搜索方向

处的梯度

.

：

(4)

从

.

出发，沿

做一维搜索，满足

令

.

(5)

若

，则停止迭代，得到最优 解

，否则进行步骤

(6).

(6)

若

，则令

，回到步骤

< br>(2)

，否则进行步骤

(7).

(7)

令

，

，

，利用方程

(6)

或

(7)

计算

，设

，回到步骤

(3)

。

限域拟牛顿法

(Limited Storage Quasi-Newton Method)

2

的步骤

(3)

中，为了确定第

需要知道对称正定矩阵

次搜 索方向，

，因此

对于

维的问题，存储空间至少是

，

对于大型计算而言，

这显然是一个极大的缺点。

作为比较，共轭梯度法只需要存储

3

个

维向量。

为了解 决这个问题，

Nocedal

首次提出了基于

< br>BFGS

公式的限域拟牛顿法

(L-BFGS)[2]< /p>

。

L-BFGS

的基本思想是存储有限次数（如

更新矩阵

，如果

次）的

>

的话就舍弃< /p>

次以前的

，也即

L-BFGS

首先将方程

(7)

写为乘法形式：

次。如果

，则

L- BFGS

等价于标准的

BFGS

公式。

其中

(8)

，

是

的矩阵。乘法形式下

舍弃

等价于置

，

。容易得出，给

定

后，

BF GS

的矩阵更新可以写为