牛顿法和拟牛顿法

本文格式为Word版，下载可任意编辑——牛顿法和拟牛顿法

牛顿法和拟牛顿法

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

牛顿法和拟牛顿法

无约束优化问题

牛顿法和拟牛顿法

线探寻方法

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)

Hk(k))1f(x(k))=f(x

2

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

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

2

(k)1

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

f(x)≈f(x(k+1))+2f(x(k+1))(xx(k+1))f(x(k))≈f(x(k+1))+2f(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)=Hk+1q(k)

p(k)≈2f(x(k+1))1q(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;Hk+1=Hk+Hk

校正矩阵

牛顿法和拟牛顿法

秩1校正

Hk=αkz

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

(k)

z

(k)T

秩为1

=(Hk+αkzz

(k)(k)T

)q(k)

(k)

z

(k)

=

p

(k)

Hkq

(k)T

αkz

(k)T

q(k)

Hkq

(k)

αk(z

(k)T

q

(k)2

)=q

(p

(k)

)

Hk=

(p(k)Hkq(k))(p(k)Hkq(k))Tq

(k)T

(p

(k)

Hkq

(k)

)

0?