[数学]最优化方法第四章课件.ppt
第四章第四章无约束最优化方法无约束最优化方法 4.1 4.1 最速下降法最速下降法问题提出问题：在点处，沿什么方向下降最快?分析：考查：显然当时，取极小值因此：结论：负梯度方向使下降最快，亦即最速下降方向最速下降法算法Step1:给出Step2:计算如果停Step3:计算下降方向Step4:计算步长因子Step5:令转步.分析：设是正定二次函数,由精确的线搜索确定的特别当：例1：用最速下降法求解：解：分析：(1)因此：最速下降法是整体收敛的，且是线性收敛的(2)两个相邻的搜索方向是正交的收敛性分析定理1:设在上存在且一致连续，则最速下降法产生的序列满足或者对某个有或者证明：对于最速下降法，由以上定理立得收敛性分析定理2:设二次连续可微，且其中是个正常数，对任何给定的初始点最速下降算法或有限终止，或者或者证明：用以上的结论：最速下降法优点(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求(2)有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛最速下降法缺点(1)最速下降法是线性收敛的，并且有时是很慢的线性收敛原因：仅反映在处的局部性质相继两次迭代中搜索方向是正交的小结(1)最速下降法是基本算法之一，而非有效的实用算法最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近 4.2 4.2 牛顿法牛顿法基本思想利用目标函数在点处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点算法构造问题：设二阶连续可微，海色阵正定如何从因为正定，则有唯一极小点，用这个极小点作为所以要求：即：因此：这就是牛顿法迭代公式注：这里牛顿法算法Step1:给出Step2:计算如果停Step3:否则计算Step4:令转步.并且求解方程得出例1：用牛顿法求解：解：牛顿法收敛定理定理1:设二次连续可微，是的局部极小点，正定 假定的海色阵满足Lipschitz条件，即存在使得对于所有有：其中是海色阵的元素 则当充分靠近时，对于一切牛顿迭代有意义，迭代序列收敛到并且具有二阶收敛速度牛顿法优点(1)(2)对正定二次函数，迭代一次就可以得到极小点如果正定且初始点选取合适，算法二阶收敛牛顿法缺点(1)(2)对多数问题算法不是整体收敛的每次都需要计算计算量大(3)每次都需要解方程组有时奇异或病态的，无法确定或不是下降方向(4)收敛到鞍点或极大点的可能性并不小阻尼牛顿法算法Step1:给出Step2:计算如果停Step3:否则计算Step4:沿并且求解方程得出进行线搜索，得出Step5:令转Step2.阻尼牛顿法收敛定理定理2:设二阶连续可微，又设对任意的存在常数使得在上满足：则在精确线搜索条件下，阻尼牛顿法产生的点列满足：(1)当是有限点列时，其最后一个点为的唯一极小点(2)当是无限点列时，收敛到的唯一极小点阻尼牛顿法收敛定理定理3:设二阶连续可微，又设对任意的存在常数使得在上满足：则在Wolfe不精确线搜索条件下，阻尼牛顿法产生的点列满足：且收敛到的唯一极小点例2：用阻尼牛顿法求解：解：显然不是正定的，但：于是，沿方向进行线搜索，得其极小点从而迭代不能继续下去带保护的牛顿法算法给出Step1:若为奇异的，转Step8，否则，Step2:令Step3:若为奇异的，转Step8，否则，则转Step8，否则，Step4:若则转Step9，否则，Step5:沿方向进行线搜索，求出并令Step6:若停；Step7:令转Step1；Step8:令转Step5；Step9:令转Step5.例3：用带保护的牛顿法求解：解：显然不是正定的，但：于是，因为，故令，沿进行线搜索得：第二次迭代：而：使故令沿进行线搜索，得出于是:此时:Gill-Murray稳定牛顿法当正定时，总有Cholesky分解：当不是正定时，Gill-Murray(1974)提出了强迫正定的修改Cholesky分解，使得：其中是对角阵 然后解：问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性 4.3 4.3 共轭方向法共轭方向法与共轭梯度法与共轭梯度法算法特点（）建立在二次模型上，具有二次终止性（）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点（）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关于共轭的注：若则是正交的，因此共轭是正交的推广定理1:设为阶正定阵，非零向量组关于共轭，则必线性无关推论1:设为阶正定阵，非零向量组关于共轭，则向量构成的一组基推论2:设为阶正定阵，非零向量组关于共轭，若向量与关于共轭，则共轭方向法算法Step1:给出计算和初始下降方向Step2:如果停止迭代Step3:计算使得Step4:采用某种共轭方向法计算使得：Step5:令转Step2.共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生成的维超平面引理1:设是连续可微的严格凸函数，维向量组线性无关，则：是在上唯一极小点的充要条件是：证：构造：分析：是(1)维严格凸函数(2)是在上的极小点的充要条件是是在上的极小点定理2:设为 阶正定阵，向量组关于共轭，对正定二次函数由任意开始，依次进行次精确线搜索：则：（）（）是在上的极小点推论:当时，为正定二次函数在上的极小点共轭梯度法记：左乘并使得：（Hestenes-Stiefel公式）取：共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在步后终止，且对成立下列关系式：（共轭性）（正交性）（下降条件）系数的其他形式（）FR公式（1964）（2）PRP公式（1969）FR共轭梯度法算法Step1:给出Step2:计算如果停Step3:Step4:由精确线搜索求Step5:转Step2.例4：用FR共轭梯度法求解：解：化成形式(1)(2)例5：用FR共轭梯度法求解：解：化成形式(1)(2)FR共轭梯度法收敛定理定理4:假定在有界水平集上连续可微，且有下界，那么采用精确线搜索下的FR共轭梯度法产生的点列至少有一个聚点是驻点，即：(1)当是有穷点列时，其最后一个点是的驻点(2)当是无穷点列时，它必有聚点，且任一聚点都是的驻点再开始FR共轭梯度法算法Step1:给出Step2:计算如果停，Step4:否则Step3:由精确线搜索求并令：计算若令转Step2;如果停.Step5:若令转step2.Step6:计算Step7:如果令转step2,否则转step3.作业：FR共轭梯度法（上机）上机实现FR共轭梯度法并求解Rosenbrock函数，初始点选线搜索分别采用黄金分割法与强Wolfe线搜索，并对比 4.4 4.4 拟牛顿法拟牛顿法基本思想本质上是基于逼近牛顿法的方法牛顿法每次都计算1959年,Davidon提出设想仅用每次迭代中得到的梯度信息来近似海色阵，基于此导致了一类非常成功的拟牛顿法本节介绍Broyden族拟牛顿法：DFP算法和BFGS算法算法原理最速下降法和阻尼牛顿法的迭代公式可统一为：思考：要使上面的算法比最速下降法快，比牛顿法计算简单，且整体收敛性好，关键在于构造矩阵列要求：的选取既能逐步逼近又无需计算二阶导数，且具备以下条件：C1：是对称正定阵C2：由经简单修正而得：C3：满足下面的拟牛顿方程（推导如下）设是二次连续可微的，令：则：令：因此：（对二次函数为等式）若非奇异：设想：（拟牛顿方程）这样就可很好的近似拟牛顿算法Step1:给出Step2:计算Step3:Step4:精确线搜索求Step5:Step6:计算若停；否则转Step7.Step7:校正使拟牛顿方程成立Step8:转Step3.DFP校正公式是 维待定向量要求：所以：令：得：因此：所以：（DFP校正公式）例6：用DFP算法求解：取解：(1)(2)注:（）DFP算法具有二次终止性（）搜索方向是共轭方向：DFP校正公式的正定继承性引理2:设为正定阵，且则：为正定阵的充要条件是定理5:在DFP算法中，如果正定，则整个矩阵列都正定DFP算法的二次终止性推论:在上面定理条件下：（1）DFP算法至多经过次迭代就可得到极小点，即存在有：（2）若则BFGS校正公式(称为关于的BFGS校正公式或互补DFP公式)由上式可得：对称秩一校正公式要求：要求Hesse逆近似也是对称的，即：取：因此：注:（1）通常不能保证（2）分母可能取零,修正公式不再有意义的正定性（3）逼近程度高，近来用于信赖域算法，取得了很好的效果Broyden族取注：得DFP校正注：得BFGS校正得对称秩一校正其中：Broyden族算法性质定理6:设在上连续可微，给定在精确线搜索下，由Broyden族算法产生的点列与参数无关结论：可将DFP算法的性质推广到整个Broyden族作业(1)用FR共轭梯度法求解：(2)用DFP算法求解：
