最优化理论4无约束优化共轭梯度法拟牛顿法

第4章无约束非线性规划哈尔滨工程大学理学院戴运桃Email:peach0040@126.com共轭方向法是介于最速下降法与牛顿法之间的一类方法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存储和计算牛顿法所需要的二阶导数信息。因而简便、易实现、且十分适合大规模（稀疏）优化问题的计算，通常只经过较少的迭代次数就能获得满足所要求精度的近似解。共轭方向法共轭梯度法定义1

设A是n×n对称矩阵,若Rn

中的两个方向d1

和d2满足(d1)T

Ad2=0（1）则称这两个方向关于A共轭,或称它们关于A正交.则称这组方向是A共轭,或称它们为A的k个共轭方向共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题求解方法

综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式3,5-7就能伴随计算点的增加,构造出一组搜索方向.注意,初始搜索方向选择最速下降方向十分重要,

如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性.注意,在FR法中,初始搜索方向必须取最速下降方向

定理3

对于正定二次函数,具有精确一维搜索的Fletcher-Reeves法在m

n次一维搜索后即终止,并且对所有i(1

i

m),下列关系成立:证明:显然m1,下用归纳法(对i)证之.

设对某个i<m,这些关系均成立,我们证明对于i+1也成立.先证2),由迭代公式两端左乘A,再加上b,得其中由于故（3）当j<i时,根据归纳假设,式(3)等号右端各项均为0再证1),运用当j=i时,把

βk代入上式第一个等号的右端,立得当j<i时,由前面已经证明的结论和归纳假设,式中第2个等号右端显然为0,因此最后证3),易知综上,对i+1,上述三种关系成立定理4

对于正定二次函数,FR法中因子

i具有下述表达式证明:FR共轭梯度法(对二次凸函数)共轭梯度法步骤3,如果j<n,转步4,否则,转5例

用FR法求解下列问题令第一次迭代，目标函数f(x)在点x处的梯度第2次迭代目标函数在点x处的梯度(2)构造搜索方向d.先计算因子

(2)1令一般迭代格式用于一般函数的共轭梯度法－非线性共轭梯度法----PRP(Polak-Ribiere-Polyar-----SW(Sorenson-Wolfe----Daniel-----Dixon拟牛顿法牛顿法成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致仅利用目标函数一阶导数的方法。什么是拟牛顿法牛顿法的迭代公式为记则上式称为拟牛顿条件(方程)，也称为割线方程.怎样确定满足这个条件的Hk+1?

对称秩1校正

Hk称为校正矩阵.确定

Hk的一个方法是令(2)(3)从而(4)利用(2),(4-5),(1)可写成(5)(6)---秩1校正公式利用秩1校正极小化函数f(x),在第k次迭代中,令搜索方向(7)确定后继点DFP校正是第一个拟牛顿校正，是1959年由Davidon提出的，后来由Fletcher和Powell(1963)解释和发展的.BFGS校正是目前最流行的也是最有效的拟牛顿校正，它是由Broyden,Fletcher,Goldfarb和Schanno在1970年各自独立提出的拟牛顿法。

对称秩2校正DFP(Davidon-Fletche