牛顿法和拟牛顿法

牛顿法和拟牛顿法

牛顿法和拟牛顿法 法和拟牛顿法

牛顿法和拟牛顿法

无约束优化问题

牛顿法和拟牛顿法

线搜索方法

dk ：搜索方向 （下降就可）： dk ▽f(xk) < 0 αk ： 搜索步长： 1） 精确搜索： f(x＋αd ) 达到最小 2） Wolfe 搜索： （两个条件）

牛顿法和拟牛顿法

精确搜索

牛顿法和拟牛顿法

Wolfe 非精确搜索

牛顿法和拟牛顿法

Wolfe 非精确搜索

牛顿法和拟牛顿法

线搜索方法的下降

方法收敛之关键：估计 搜索方向与最速下降方向的夹角

牛顿法和拟牛顿法

线搜索方法的收敛性

如果 f(x) 下方有界，如果搜索方向 定理 与最速下降法的夹角不靠近π/2,则由线搜索 方法产生的点列 xk 满足： || gk || → 0

牛顿法和拟牛顿法

搜索方向

最速下降法：

共轭梯度法：

牛顿法：

牛顿法和拟牛顿法

牛顿方向

牛顿方向

是如下问题的解

牛顿法和拟牛顿法

牛顿法的优缺点

收敛快 －－－ 二次收敛 程序简单

计算量大 －－－ 需要二阶导数 需要二阶导数 要求高 －－－ 需要二阶导数 需要计算Hesse矩阵，而此矩阵可能非正定， Hesse矩阵 需要计算Hesse矩阵，而此矩阵可能非正定， 能导致搜索方向不是下降方向。 可能导致搜索方向不是下降方向。

牛顿法和拟牛顿法

找替代牛顿法的方法

目标： 目标： 收敛快 程序简单 同时 不需要二阶导数 找： 的家伙！！！ 像牛顿 又不是牛顿 的家伙！！！

牛顿法和拟牛顿法

基本思想： 基本思想：

用不包含二阶导数的矩阵近似Hesse矩阵的逆 用不包含二阶导数的矩阵近似Hesse矩阵的逆。 矩阵近似 矩阵的逆。

牛顿法和拟牛顿法

拟牛顿条件

d

(k )

H k( k ) ) 1 f ( x ( k ) ) = f ( x

2

x ( k +1) = x ( k ) + λ k d ( k )

首先分析 f ( x ) 与一阶导数的关系：

2

( k ) 1

展开： 在点 x ( k +1) 处进行二阶 Taylor展开： 1 f ( x ) ≈ f ( x ( k +1) ) + f ( x ( k +1) )( x x ( k + 1) ) + ( x x ( k + 1) )T 2 f ( x ( k +1) )( x x ( k + 1) ) 2

f ( x ) ≈ f ( x ( k +1) ) + 2 f ( x ( k + 1) )( x x ( k +1) ) f ( x ( k ) ) ≈ f ( x ( k +1) ) + 2 f ( x ( k +1) )( x ( k ) x ( k +1) )

p ( k ) := x ( k +1) x ( k ) q ( k ) := f ( x ( k +1) ) f ( x ( k ) ) q

(k )

≈ f (x

2

( k +1)

)p

(k )

p ( k ) = H k + 1q ( k )

p ( k ) ≈ 2 f ( x ( k +1) ) 1 q ( k )

牛顿法和拟牛顿法

1.秩 1.秩1校正 2.DFP(Davidon-Fletcher-Powell)算法 2.DFP(Davidon-Fletcher-Powell)算法： 算法： 秩2校正 3.BFGS(Broyden-Fletcher-Goldfarb3.BFGS(Broyden-Fletcher-GoldfarbShanno)公式及 Shanno)公式及Broyden族 公式及Broyden族

H1 = I; H k + 1 = H k + H k

校正 矩阵

牛顿法和拟牛顿法

秩1校正

H k = α k z

p ( k ) = H k + 1q ( k )

(k )

z

( k )T

秩为 1

= (Hk + αk z z

( k ) ( k )T

)q ( k )

(k )

z

(k )

=

p

(k )

Hkq

( k )T

αk z

( k )T

q(k )

Hkq

(k )

αk (z

( k )T

q

(k ) 2

) =q

(p

(k )

)

H k =

( p ( k ) H k q ( k ) )( p ( k ) H k q ( k ) )T q

( k )T

(p

(k )

Hkq

(k )

)

> 0?

牛顿法和拟牛顿法

注释 在一定条件下，收敛且具有二次终止性。 在一定条件下，收敛且具有二次

牛顿法和拟牛顿法

牛顿法和拟牛顿法

牛顿法和拟牛顿法

牛顿法和拟牛顿法