最优化课件Y05_拟牛顿法.pdf

第5讲拟牛顿法

原理
对称秩1算法
DFP算法
BFGS算法
原理

一、思路
−1
牛顿法: XXHkkkk+1 =−∇f ()X
−1 −1
阻尼牛顿法: XXkkkkk+1 =−λ H ∇f ()X Pkk=−H ∇f ()X kNewton方向
需要计算Hessen矩阵及其逆矩阵,不方便。
-1
设想用若干便于计算的(对称正定)矩阵Gk逐步逼近 Hk (或Bk 逼近Hk)
拟牛顿法: XXGfXkkkkk+1 = −∇λ() Pkkk= −∇GfX() 拟Newton方向
(Quasi-Newton Method)
二、Gk构造依据
−1
∇−∇=−f ()XfXQXXkkkk++11 ()( ) Q [(∇−∇=−f X kkkk++11 )f ()]XXX
−1
∇−∇=−f ()XfXHXXkkkk++11 ()( )Hkk++11[(∇−∇=−fX ) fX ()] kkk X +1 X
要使拟Newton方向较好近似Newton方向,下列基本条件应当满足:
(1)Pk= -Gk∇ f(Xk) 是下降方向
(2)Gk+1满足拟牛顿方程
∇−∇=f ()XfXBXXkkkkk++11 () (+1 −) GfXfXXXkk++11[(∇−∇=−) ()] kkk+1
(3)Gk 与Gk+1之间有某种简单的迭代关系。
T T
对条件(1),需要−∇<fX()kk P 0即 k [ k XfGXf k ]<∇−∇ 0)()(
,Gk 正定即可满足要求。
= + EGG
对条件(3),常用 BBEkkk+1 = + k+1 kk
其中Ek容易计算,称为校正矩阵。记
k = ∇ k+1 −∇ XfXfY k )()( = kk +1 − XXS k
拟牛顿方程即为 YBESkkkk= ()+ ()GEYSkkkk+ =
拟牛顿条件: EkkSYBS= k− kk EkkYSGY= k− kk
三、拟牛顿法基本步骤
(1)选初始点X0 ,初始正定矩阵G0 (通常为单位矩阵I),置k=0;
(2) Pk= -Gk∇ f(Xk )
(3)一维搜索:min f(Xk +λPk) . λ≥0;Xk+1= Xk+ λk Pk
(4)如果Xk+1 满足迭代终止准则,输出Xk+1,计算终止;否则,转( 5);
;
(5)构造Ek,满足拟 Newton条件,令Gk+1 =Gk+ Ek
T
(6)若∇f(Xk+1 ) Gk+1 ∇f(Xk+1 )>0,则k=k+1 ,转(2);否则,
令Pk+1 =-∇f(Xk+1) ,k=k+1,转(3)。
四、变尺度法主要特点
(1)只需用到函数的一阶梯度;(Newton法用到二阶Hessen阵)
(2)下降算法,故全局收敛;
(3)不需求矩阵逆;(计算量小)
(4)一般可达到超线性收敛;(速度快)
(5)有二次终结性。
初期迭代方向近似梯度法,下降较快;后期迭代方向近似牛顿法,收敛较快。
注:满足拟Newton条件的校正矩阵Ek 可构造出无穷多种(但并非每种都有良
好性质),每种对应一种特殊的拟Newton法。即,拟Newton法是一族算法。
对称秩1算法

一、Ek构造
T
Ekk= α UUkk
αk为待定数, Uk为待定向量。Ek秩为 1→对称秩1校正
⎡ uuu u ⎤
⎡uu00⎤⎡⎤⎛⎞⎛⎞u0⎛⎞u000( 1L n−1)
⎢⎥⎢⎥⎜⎟⎜⎟⎜⎟()⎢⎥
uu11u1u1u1u0u1L un−1
⎢⎥[]uu01LLunn−−1==⎢⎥⎜⎟u0⎜⎟u1 ⎜⎟u1 ⎢⎥
⎢⎥MM⎢⎥⎜⎟⎜⎟M⎜⎟M⎢()M ⎥
uuuu⎢⎥
⎣nn−−11⎦⎢⎥⎣⎦⎝⎠⎝⎠n1⎝⎠n1−⎣uunn−−10u1L u−1⎦
∴r = 1
将其代入拟Newton条件:
T
αkkUUkYk=− kS kkGY
T 11
注意到 U Y 是数,可令于是
k k αk ==TT
UYkk Yk()Sk− GkYk
⎧US =−GY
kkkk T
⎨ T
()SGkk−−Y()SkGkYkk
αkkUYk= 1
⎩ Ek = T
YSkk()− G kYk
二、对称秩1算法的性质
(1)Ek对称,故 Gk 对称。
(2)对正定二次函数:
(a)搜索方向共轭,是一种共轭方向法,从而算法具备有限收敛性。
-1
(b)Gn =Q
(5)超线性收敛。
T
()(