共轭方向法.ppt

共轭方向法
第1页，本讲稿共76页
算法特点
（１）建立在二次模型上，具有二次终止性．
（２）有效的算法，克服了最速下降法的慢
收敛性，又避免了牛顿法的计算量大和局部收
性的缺点．
（３）算法简单，易于编程，需存储空间次迭代中得到的梯度信息来近似海
色阵，基于此导致了一类非常成功的拟牛顿法．
本节介绍Broyden族拟牛顿法：
DFP算法和BFGS算法．
第24页，本讲稿共76页
算法原理
最速下降法和阻尼牛顿法的迭代公式可统一为：
思考：
要使上面的算法比最速下降法快，比牛顿
法计算简单，且整体收敛性好，关键在于构造
矩阵列
要求：
的选取既能逐步逼近
又无需计算
二阶导数，
且具备以下条件：
第25页，本讲稿共76页
C1：
是对称正定阵．
C2：
由
经简单修正而得：
C3：
满足下面的拟牛顿方程．（推导如下）
设
是二次连续可微的，
第26页，本讲稿共76页
令：
则：
令：
因此：
（对二次函数为等式）
若
非奇异：
设想：
（拟牛顿方程）
这样
就可很好的近似
第27页，本讲稿共76页
拟牛顿算法
Step1:
给出
Step2:
计算
Step3:
Step4:
精确线搜索求
Step5:
Step6:
计算
若
停；
否则转
Step7.
Step7:
校正
使拟牛顿方程成立．
Step8:
转Step3.
第28页，本讲稿共76页
DFP校正公式
是
维待定向量．
要求：
所以：
令：
得：
因此：
所以：
（DFP校正公式）
第29页，本讲稿共76页
例6：
用DFP算法求解：
取
解：
(1)
第30页，本讲稿共76页
(2)
第31页，本讲稿共76页
注:
（１）DFP算法具有二次终止性．
（２）搜索方向是共轭方向：
第32页，本讲稿共76页
DFP校正公式的正定继承性
引理2:
设
为
正定阵，
且
则：
为正定阵的充要条件是
定理5:
在DFP算法中，
如果
正定，
则整个矩阵列
都正定．
第33页，本讲稿共76页
DFP算法的二次终止性
推论:
在上面定理条件下：
（1）
DFP算法至多经过
次迭代就可得到极
小点，即存在
有：
（2）
若
则
第34页，本讲稿共76页
BFGS校正公式
(称为关于
的BFGS校正公式或互补DFP公式)
由上式可得：
第35页，本讲稿共76页
对称秩一校正公式
要求：
要求Hesse逆近似也是对称的，
即：
取：
因此：
第36页，本讲稿共76页
注:
（1）通常不能保证
（2）分母可能取零,修正公式不再有意义．
的正定性．
（3）逼近
程度高，
近来用于信赖域算法，
取得了很好的效果．
第37页，本讲稿共76页
Broyden族
取
注：
得DFP校正．
注：
得BFGS校正．
得对称秩一校正．
其中：
第38页，本讲稿共76页
Broyden族算法性质
定理6:
设
在
上连续可微，
给定
在精确线搜索下，
由Broyden族算法产生的点
列
与参数
无关．
结论：
可将DFP算法的性质推广到整个Broyden族
第39页，本讲稿共76页
作　业
(1)用FR共轭梯度法求解：
(2)用DFP算法求解：
第40页，本讲稿共76页
第 五 章
无约束最优化方法
第41页，本讲稿共76页
第五章 无约束最优化
（f） min f(x) f : Rn→R
最优性条件
设 f 连续可微
必要条件：若x*－. 则▽f(x*)=0 (驻点)。
当 f 凸时， x*－. ←→ ▽f(x*)=0
注意： f(x) ≥f(x*)+ ▽Tf(x*)(x-x*),  x.
故 f(x*) ≤f(x)，  x. （ 由于▽Tf(x*) =0）
最速下降法
在迭代点 x(k) 取方向 d(k)= －▽f(x(k) )
精确一维搜索
最 速 下降法：梯度方向函数值变化最快的方向
第42页，本讲稿共76页
第五章 无约束最优化
最速下降法（续）
x(1), ε >0, k=1
|| ▽f(x(k) ) ||< ε?
Yes
stop. x(k) –解
No
d(k)= －▽f(x(k) )
解 min