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

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

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

中的两个方向d1

和d2满足(d1)T

Ad2=0（1）则称这两个方向关于A共轭,或称它们关于A正交.则称这组方向是A共轭,或称它们为A的k个共轭方向定义1设A是n×n对称矩阵,若Rn中的两个方向d1和最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题求解方法共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题求解方法最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件

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

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

定理3

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

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

i

m),下列关系成立:定理3对于正定二次函数,证明:显然m1,下用归纳法(对i)证之.

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

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

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

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

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

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

对称秩1校正

Hk称为校正矩阵.确定

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

对称秩2校正DFP校正是第一个拟牛顿校正，是1959年由Davidon提DFP(Davidon-Fletcher-Power)公式DFP(Davidon-Fletcher-Power)公式最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件DFP算法DFP算法最优化理论第4章4无约束优化共轭梯度法拟牛顿法课件例

用DFP方法求解下列问