第六章 使用导数的最优化方法

第六章

使用导数的最优化方法§

6.1牛顿法基本思想利用目标函数在点处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点．算法构造问题：设二阶连续可微，海色阵正定．如何从因为正定，则有唯一极小点，用这个极小点作为所以要求：即：因此：这就是牛顿法迭代公式．注：牛顿法是一种下降法,这里牛顿法算法Step1:给出Step2:计算如果停．Step3:否则计算Step4:令转步２.并且求解方程得出例1：用牛顿法求解：解：牛顿法收敛定理定理1:设二次连续可微，是的局部极小点，正定．假定的海色阵满足Lipschitz条件，即存在使得对于所有有：其中是海色阵的元素．则当充分靠近时，对于一切牛顿迭代有意义，迭代序列收敛到并且具有二阶收敛速度．牛顿法优点(1)(2)具有二次终止性.对正定二次函数，迭代一次就可以得到极小点.如果正定且初始点选取合适，算法二阶收敛．牛顿法缺点(1)(3)可能会出现在某步迭代时目标函数值每次都需要计算计算量大．(4)每次都需要解方程组有时奇异或病态，无法确定(2)可能不收敛，或收敛到鞍点．反而上升的情形，即阻尼牛顿法算法Step1:给出Step2:计算如果停．Step3:否则计算Step4:沿并且求解方程得出进行一维搜索，得出Step5:令转Step2.阻尼牛顿法收敛定理定理2:设二阶连续可微，又设对任意的存在常数使得在上满足：则在精确一维搜索下，阻尼牛顿法产生的点列满足：(1)当是有限点列时，其最后一个点为的唯一极小点．(2)当是无限点列时，收敛到的唯一极小点．阻尼牛顿法收敛定理定理3:设二阶连续可微，又设对任意的存在常数使得在上满足：则在Wolfe不精确一维搜索下，阻尼牛顿法产生的点列满足：且收敛到的唯一极小点．牛顿法的其他修正方法（1）Goldsetin和Price(1967)的修正方案其思想是将牛顿法与最速下降法相结合，当牛顿方向与负梯度方向的夹角太大时(如大于90度)，就用负梯度方向取代牛顿方向牛顿法的其他修正方法（2）Fiacco和McCormick(1968)的修正方案其思想是当海赛矩阵非正定时，采用负曲率下降方向，作为搜索方向上式的意思是当负曲率方向与负梯度方向的夹角小于90度时，采用负曲率方向；否则采用与负曲率方向相反的方向.牛顿法的其他修正方法（3）正则化修正方案§

6.2共轭方向法与共轭梯度法算法目标和要求（１）产生的搜索方向是下降方向．（２）不必计算Hesse矩阵，只计算目标函数值和梯度值.（３）具有二次终止性.正交方向及其性质正交方向及其性质建沿两个相互正交的方向，进行精确一维搜索，即可得到最优解正交方向及其性质定义1:设是中任一组非零向量，如果：则称是一组正交方向.性质1:定义2:设维向量组线性无关，向量集合称为与生成的维线性流形．当其维数为n-1时，又称为超平面．线性流形可看成线性子空间从原点的一个移位．定理1:设向量组是一组正交方向,对正定二次函数由任意开始，依次进行次精确一维搜索,得到则：（１）（２）是在线性流行上的极小点．推论:当时，为正定二次函数在上的极小点．共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关于共轭的．注：若则是正交的，因此共轭是正交的推广．定理2:设为阶正定阵，非零向量组关于共轭，则必线性无关．推论1:设为阶正定阵，非零向量组关于共轭，则向量构成的一组基．推论2:设为阶正定阵，非零向量组关于共轭，若向量与关于共轭，则共轭方向法算法Step1:给出计算和初始下降方向Step2:如果停止迭代．Step3:计算使得Step4:采用某种共轭方向法计算使得：Step5:令转Step2.定理3:设为阶正定阵，向量组关于共轭，对正定二次函数由任意开始，依次进行次精确线搜索，得到则：（１）（２）是在上的极小点．推论:当时，为正定二次函数在上的极小点．共轭方向法基本定理共轭梯度法记：左乘并使得：（Hestenes-Stiefel公式）取：共轭梯度法基本性质定理4:对于正定二次函数，采用精确一维搜索的共轭梯度法在步后终止，且对成立下列关系式：（共轭性）（正交性）（下降性）系数的其他形式（１）FR公式（1964）（2）PRP公式（1969）FR（或FRP）共轭梯度法算法Step1:给出Step2:计算如果停．Step3:Step4:解一维搜索Step5:转Step2.或例：用FR共轭梯度法求解：解：化成形式(1)(2)共轭梯度法的下降性和二次终止性定理5设f(x)具有连续的一阶偏导数，并设共轭梯度法的一维搜索是精确的，若则搜索方向dk是xk处的下降方向.定理6若一维搜索是精确的，则共轭梯度法具有二次终止性.FR共轭梯度法收敛定理定理7:假定在有界水平集上连续可微，且有下界，那么采用精确一维搜索的FR共轭梯度法产生的点列至少有一个聚点是驻点，即：(1)当是有穷点列时，其最后一个点是的驻点．(2)当是无穷点列时，它必有聚点，且任一聚点都是的驻点．对于正定二次函数，共轭梯度法至多n步终止。如算法没有n步终止，说明目标函数不是正定二次函数或目标函数没有进入一个正定二次函数的区域，此时共轭方向已没有意义，因此搜索方向应重新开始，即令dn=-gn

.这种每n步重新开始新一轮共轭梯度法的策略，称为n步重新开始策略。实际计算表明，n步重新开始的FR算法要优于原FR算法。对于FRP算法,当gk≈gk-1

,有k-1=0;因此dk≈-gk

,即算法自动重新开始。试验表明，对于大规模问题，FRP算法优于FR算法。再开始FR共轭梯