第四章 无约束最优化方法

《第四章 无约束最优化方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章无约束最优化方法§4.1最速下降法问题提出问题：在点处，沿什么方向下降最快?分析：考查：显然当时，取极小值．因此：结论：负梯度方向使下降最快，亦即最速下降方向．最速下降法算法Step1:给出Step2:计算如果停．Step3:计算下降方向Step4:计算步长因子Step5:令转步２.分析：设是正定二次函数,由精确的线搜索确定的特别当：例1：用最速下降法求解：解：分析：(1)因此：最速下降法是整体收敛的，且是线性收敛的．(2)两个相邻的搜索方向是正交的．收敛性分析定理1:设在上存在且一致连续，则最速下降法产生的序列满足或者对某个有或者证明：对于

2、最速下降法，由以上定理立得．收敛性分析定理2:设二次连续可微，且其中是个正常数，对任何给定的初始点最速下降算法或有限终止，或者或者证明：用以上的结论：最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求．(2)有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛．最速下降法缺点(1)最速下降法是线性收敛的，并且有时是很慢的线性收敛．原因：①仅反映在处的局部性质．②相继两次迭代中搜索方向是正交的．小结(1)最速下降法是基本算法之一，而非有效的实用算法．最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目

3、标函数的高阶逼近．§4.2牛顿法基本思想利用目标函数在点处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点．算法构造问题：设二阶连续可微，海色阵正定．如何从因为正定，则有唯一极小点，用这个极小点作为所以要求：即：因此：这就是牛顿法迭代公式．注：这里牛顿法算法Step1:给出Step2:计算如果停．Step3:否则计算Step4:令转步２.并且求解方程得出例1：用牛顿法求解：解：牛顿法收敛定理定理1:设二次连续可微，是的局部极小点，正定．假定的海色阵满足Lipschitz条件，即存在使得对于所有有：其中是海色阵的元素．

4、则当充分靠近时，对于一切牛顿迭代有意义，迭代序列收敛到并且具有二阶收敛速度．牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小点．如果正定且初始点选取合适，算法二阶收敛．牛顿法缺点(1)(2)对多数问题算法不是整体收敛的．每次都需要计算计算量大．(3)每次都需要解方程组有时奇异或病态的，无法确定或不是下降方向．(4)收敛到鞍点或极大点的可能性并不小．阻尼牛顿法算法Step1:给出Step2:计算如果停．Step3:否则计算Step4:沿并且求解方程得出进行线搜索，得出Step5:令转Step2.阻尼牛顿法收敛定理定理2:设二阶连续可微，又

5、设对任意的存在常数使得在上满足：则在精确线搜索条件下，阻尼牛顿法产生的点列满足：(1)当是有限点列时，其最后一个点为的唯一极小点．(2)当是无限点列时，收敛到的唯一极小点．阻尼牛顿法收敛定理定理3:设二阶连续可微，又设对任意的存在常数使得在上满足：则在Wolfe不精确线搜索条件下，阻尼牛顿法产生的点列满足：且收敛到的唯一极小点．例2：用阻尼牛顿法求解：解：显然不是正定的，但：于是，沿方向进行线搜索，得其极小点从而迭代不能继续下去．带保护的牛顿法算法给出Step1:若为奇异的，转Step8，否则，Step2:令Step3:若为奇异的，转Step8，否

6、则，则转Step8，否则，Step4:若则转Step9，否则，Step5:沿方向进行线搜索，求出并令Step6:若停；Step7:令转Step1；Step8:令转Step5；Step9:令转Step5.例3：用带保护的牛顿法求解：解：显然不是正定的，但：于是，因为，故令，沿进行线搜索得：第二次迭代：而：使故令沿进行线搜索，得出于是:此时:Gill-Murray稳定牛顿法当正定时，总有Cholesky分解：当不是正定时，Gill-Murray(1974)提出了强迫正定的修改Cholesky分解，使得：其中是对角阵．然后解：问题1:如何建立有效的算法？

7、从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性§4.3共轭方向法与共轭梯度法算法特点（１）建立在二次模型上，具有二次终止性．（２）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点．（３）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法．共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关于共轭的．注：若则是正交的，因此共轭是正交的推广．定理1:设为阶正定阵，非零向量组关于共轭，则必线性无关．推论1:设为阶正定阵，非零向量组关于共轭，则向量构成的一组基．推论2:设为阶正定阵，非零向

8、量组关于共轭，若向量与关于共轭，则共轭方向法算法Step1:给出计算和初始下降方向Step2:如果停止迭代．Step3:计