第四章-无约束最优化方法课件.ppt
,4.1 最速下降法,问题提出,问题：,在点,处，,沿什么方向,下降最快?,分析：,考查：,显然当,时，,取极小值,因此：,结论：,负梯度方向使,下降最快，,亦即最速,下降方向,最速下降法算法,Step1:,给出,Step2:,计算,如果,停,Step3:,计算下降方向,Step4:,计算步长因子,Step5:,令,转步.,分析：,设,是正定二次函数,由精确的线搜索确定的,特别当：,例1：,用最速下降法求解：,解：,分析：,(1),因此：,最速下降法是整体收敛的，,且是线性收敛的,(2),两个相邻的搜索方向是正交的,收敛性分析,定理1:,设,在,上存在且一致连续，,则最速下降法产生的序列,满足或者对某个,有,或者,证明：,对于最速下降法，,由以上定理立得,收敛性分析,定理2:,设,二次连续可微，,且,其中,是个正常数，,对任何给定的初始点,最速下降算法或有限终止，,或者,或者,证明：,用以上的结论：,最速下降法优点,(1),程序设计简单，计算量小，存储量小，,对初始点没有特别要求,(2),有着很好的整体收敛性，即使对一般的,目标函数，它也整体收敛,最速下降法缺点,(1),最速下降法是线性收敛的，并且有时是,很慢的线性收敛,原因：,仅反映,在,处,的局部性质,相继两次迭代中搜索,方向是正交的,小结,(1),最速下降法是基本算法之一，而非有效,的实用算法,最速下降法的本质是用线性函数来近似,目标函数，,要想得到快速算法，需要考,虑对目标函数的高阶逼近,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 共轭方向法与共轭梯度法,算法特点,（）建立在二次模型上，具有二次终止性,（）有效的算法，克服了最速下降法的慢,收敛性，又避免了牛顿法的计算量大和局部收,性的缺点,（）算法简单，易于编程，需存储空间小等,优点，是求解大规模问题的主要方法,共轭方向及其性质,定义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 拟牛顿法,基本思想,本质上是基于逼近牛顿法的方法,牛顿法每次都计算,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算法求解：,
