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

第第4章章 无约束非线性规划无约束非线性规划哈尔滨工程大学哈尔滨工程大学 理学院理学院戴运桃戴运桃Email:共轭方向法是介于最速下降法与牛顿法之间的一类方共轭方向法是介于最速下降法与牛顿法之间的一类方法。它仅需利用一阶导数信息，但克服了最速下降法法。它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了存储和计算牛顿法所需要的收敛慢的缺点，又避免了存储和计算牛顿法所需要的二阶导数信息。因而简便、易实现、且十分适合大规二阶导数信息。因而简便、易实现、且十分适合大规模（稀疏）优化问题的计算，通常只经过较少的迭代模（稀疏）优化问题的计算，通常只经过较少的迭代次数就能获得满足所要求精度的近似解。次数就能获得满足所要求精度的近似解。共轭方向法共轭方向法共轭梯度法共轭梯度法定义定义1 1 设A是nn对称矩阵,若Rn 中的两个方向d 1 和d2满足 (d 1)T Ad 2=0 （1）则称这两个方向关于A共轭,或称它们关于A正交.则称这组方向是A共轭共轭,或称它们为A的的k个共轭方向个共轭方向共轭梯度法共轭梯度法先讨论对于二次凸函数的共轭梯度法,考虑问题求解方法 综上分析,在第一个搜索方向取负梯度的前提下,重复使用公式3,5-7就能伴随计算点的增加,构造出一组搜索方向.注意,初始搜索方向选择最速下降方向十分重要,如果选择别的方向作为初始方向,其余方向均按FR方法构造,则极小化正定二次函数时,这样构造出来的一组方向并不能保证共轭性.注意注意,在在FR法中法中,初始搜索方向必须取最速下降方向初始搜索方向必须取最速下降方向 定理定理 3 对于正定二次函数,具有精确一维搜索的Fletcher-Reeves法在mn次一维搜索后即终止,并且对所有i(1 i m),下列关系成立:证明:显然m1,下用归纳法(对i)证之.设对某个im,这些关系均成立,我们证明对于i+1也成立.先证2),由迭代公式两端左乘A,再加上b,得其中由于故（3）当ji时,根据归纳假设,式(3)等号右端各项均为0再证1),运用当j=i时,把 k代入上式第一个等号的右端,立得当ji时,由前面已经证明的结论和归纳假设,式中第2个等号右端显然为0,因此最后证3),易知综上,对i+1,上述三种关系成立定理定理4 对于正定二次函数,FR法中因子i具有下述表达式证明:FR共轭梯度法(对二次凸函数)共轭梯度法步骤共轭梯度法步骤3,如果j n,转步4,否则,转5例 用FR法求解下列问题令第一次迭代，目标函数f(x)在点x处的梯度第2次迭代目标函数在点x 处的梯度(2)构造搜索方向d .先计算因子(2)1令一般迭代格式l用于一般函数的共轭梯度法非线性共轭梯度法-PRP(Polak-Ribiere-Polyar-SW(Sorenson-Wolfe-Daniel -Dixon拟牛顿法拟牛顿法牛顿法成功的关键在于利用了Hesse矩阵提供的曲率信息，而计算Hesse矩阵工作量大，并且有的目标函数的Hesse矩阵很难计算，甚至不好求出，这就导致仅利用目标函数一阶导数的方法。什么是拟牛顿法牛顿法的迭代公式为记则上式称为拟牛顿条件拟牛顿条件(方程方程)，也称为割线方程割线方程.怎样确定满足这个条件的H k+1?对称秩对称秩1 1校正校正Hk称为校正矩阵校正矩阵.确定Hk的一个方法是令(2)(3)从而(4)利用(2),(4-5),(1)可写成(5)(6)-秩秩1 1校正公式校正公式利用秩1校正极小化函数f(x),在第k次迭代中,令搜索方向(7)确定后继点DFP校正是第一个拟牛顿校正，是校正是第一个拟牛顿校正，是1959年由年由Davidon提出提出的，后来由的，后来由Fletcher和和Powell(1963)解释和发展的解释和发展的.BFGS校正是目前最流行的也是最有效的拟牛顿校正，它是由校正是目前最流行的也是最有效的拟牛顿校正，它是由Broyden,Fletcher,Goldfarb和和Schanno在在1970年各自独立年各自独立提出的拟牛顿法。提出的拟牛顿法。对称秩对称秩2 2校正校正DFP(Davidon-Fletcher-Power)公式DFP算法例 用DFP方法求解下列问题初始点及初始矩阵分别为第1次迭代令搜索方向得到令第2次迭代令得到令于是得最优解于是得最优解