牛顿法和拟牛顿法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,4.6.5,牛顿法,拟牛顿法,&,x,1,x,2,0,Penalty method,实际化工过程数学模型：求解复杂、计算量大,数值算法实现模型求解：迭代形式逐渐逼近最优解,x,*，,求解过程：在可行域范围或非可行域内按照一定策略搜索最优值的问题 。,初始点 更新点 最优解,X,*,判断所得点是否足够接近,，满足则停止搜索,系统思想,迭代法共同特点：,对求解变量的数值进行逐步改进，使之从开始不能满足方程的要求，逐渐逼近方程所要求的解，每一次迭代所提供的信息（表明待解变量的数值同方程的解尚有距离的信息），用来产生下一次改进值，迭代方案有多种，这就形成了不同的迭代方法。,变量轮换 单纯形法,最速下降法 共轭梯度法,牛顿,法,&,拟牛顿法,系统思想,一,.,牛顿法,1.,问题提出,最速下降法：当前迭代点,Xk,迭代简单，但容易产生锯齿现象，使得收敛缓慢，即,一,阶逼近函数得到的模型比较粗糙。,提高逼近阶数,牛顿法：二阶逼近函数算法，快速收敛,牛顿迭代,最速下降,图,4-12,从目标函数值近似值的观点,比较最速下降法和牛顿法,一、牛顿法,将,f,(x,k+1,),在,x=x,k,处一阶泰勒展开：,目标函数趋于零,一,.,牛顿法,将,f,(x,k+1,),在,x=x,k,处二阶泰勒展开：,目标函数趋于零,一,.,牛顿法,一维搜索简化公式,一,.,牛顿法,推广到多元函数情况，即得到求解多元函数极小的牛顿迭代算法：,一,.,牛顿法,Newton,迭代公式,其中,1.,牛顿法几何解释,几何直观解释：最密切的二次曲线逼近,2.Newton,算法,Step1,:,给初始点,x,0,精度,0,k=0,Step2:,计算,Step3:,由方程组,H(x,k,),x,k,=-h,k,解出,x,k+1,当,H,k,可逆时，,x,k+1,=x,k,-H,k,-1,.h,k,Step4:,例,1.,设,分析,:,搜索方向,解：,故,求在点,处,的,搜索,方向,.,故需要写出,的表达式,.,故,所以,进而得,因此所求的牛顿方向为,由,例,2,：,用牛顿法求解：,解：,因,所以迭代终止,最优点为,:,3.,牛顿法优缺点,(1),对正定二次函数，迭代一次就可以得到,极小点,(2),如果,正定且初始点选取合适，,算法,很快收敛,优点,(2),收敛性与初始点的选取依赖很大,(3),每次都需要计算海森阵,计算量大,(4),每次都需要解方程组,方程组有时奇异或病态的，,无法确定,或,不是下降方向,(1),要求函数二阶可微,.,缺点,二,.,阻尼牛顿法,Newton,法改进,这样往往可以克服上述缺点,.,针对缺点中的,(2),在求新迭代点时，不直接用公式进行迭代，而是以 作为搜索方向进行一维搜索，求步长 ，使,1.,基本思想,2.,阻尼牛顿法算法,Step1:,给出,Step2:,计算,如果,停,否则计算,并令,Step4:,令,转,Step2,.,Step3:,沿,进行线搜索，,得最优步长,3.,收敛性定理,定理,3.7,二次连续可微，,正定,设,是由阻尼牛顿法得到的迭代点列,.,记,必有聚点,且任何聚点,有界,若水平集,满足,则,1.,分析：,Newton,法,优点：高收敛速度（二阶收敛）,缺点：对初始点目标函数要求高，计算量，存 储量大（需要计算、存储,hessian,矩阵及其逆矩阵）,拟牛顿法,模拟牛顿法给出的一个“保优去劣”的算法,考虑,Newton,迭代公式：,搜索方向为,进行改进：一、避免求逆矩阵，用,则上式变为,此时搜索方向为,步长因子为,二、更大的灵活性，一般化,这样的,H,k,存在？,1,、为保证 总是下降方向，要求每一个,G,k,均称为正定矩阵,2,、为易于计算，要求有简单的迭代形式，最简单的迭代关系为,拟牛顿条件,分析：,H,k,-1,需满足的条件，并利用此条件确定,G,k,由归纳法，若,由,H,k,可求,H,k+1,则在,x,k+1,点，,Taylor,展开,想到,在确定拟牛顿方程式的,H,k+1,时，若矩阵,H,k+1,对称，则需要待定（,n+n,2,)/2,个未知数，,n,个方程，所以拟牛顿方程一般有无穷个解，故由拟牛顿方程确定的一族算法，通常称之为拟牛顿法,拟,Newton,算法,1,、给定初始点,x0,正定矩阵,H,0,精度,0,k=0,2,、计算搜索方向,3,、令,x,k+1,=x,k,+t,k,.s,k,其中,t,k,为,f(x,k,+t,k,S,k,)=min f(x,k,+ts,k,),4,、若 ，则,x,k+1,为最优解，否则转步骤,5,5,、,按照校正公式,G,k+1,=G,k,+,G,k,计算,G,K+1,使得,G,k+1,满足拟牛顿条件或拟,Newton,方程：,G,k+1,*,y,k,=d,k,令,k=k+1,转步骤,2,DFP,算法,1,、,DFP,算法提出：,(1)Davidon (2)Fletcher&Powell (3),多变量无约束优化,2,、,如何确定,G(k)?,秩,2,校正法,根据拟,Newton,条件：,G,k+1,y,k,=d,k,我们有,满足上述方程的解很多，可如下确定一组解,则我们可以取,即,由此得到,G,k,的,DFP,校正公式,性质：,H,0,0,则可以推出,H,k,0,正交继承性,DFP,算法步骤,将拟,Newton,法第,5,步骤改为,:,5,、按,DFP,校正公式,计算,G,k,k=k+1,转步骤,2,BFGS,算法,Summary,非线性问题规划求解,变量轮换法,单纯形法,最速下降法,共轭梯度法,牛顿法,拟牛顿法,无约束最优化问题,有约束最优化问题,单变量函数的优化,一维搜索,多变量函数的优化策略,系统思想,Summary,函数值搜索（零阶法）,变量轮换法,单纯形法,梯度信息搜索（一阶法）,最速,下降法,共轭,梯度法,二阶近似值搜索（二阶法）,牛顿法,拟牛顿法,无约束多变量函数的优化策略,1,、选择初始,点,x,0,。,当然初始点离最小点越近越好,。,2,、确定搜索方向,S,k,，,使目标函数从,x,k,沿,此方向下降,。,3,、,在,x,k,方向,上进行一维搜索。在由,x,k,出发,的,射线,x=x,k,+,k,S,k,(,k,0),上,选取步长,k,使,一元（,）函数,f(x,k,+,k,S,k,),在,=,k,处,取最小值。它是一个单变量函数极小问题。由此得到新,点,x,k+1,=x,k,+,k,S,k,(,k,0,),4,、,检验,x,k+1,是否,最优解。,共同缺点在于有,多重局部解存在时,，不一定,能找出全局最优解,Summary,变量轮换法,特点：,可靠性较高，属于直接法，只需目标函数值信息，不需要目标函数导数。程序简单，易于掌握。但是搜索效率低，且越接近极值点，搜索速度越慢。,单纯形法特点：,是,不需要复杂的导数运算，它朝最优点的移动完全由上一个单纯形的结果所定，计算机上使用时贮存少。但由于步长固定，故缺少加速的方法。,单纯形：指多维空间的凸多边形的顶点数比空间维数多，如正四面体,Summary,最速下降法,特点：前后两步迭代的搜索方向相互正交，对,f,（,x),的尺度太灵敏，收敛缓慢，容易在,x,空间上产生大量的摆动，可能产生锯齿现象,共轭梯度法,特点：,增大了很少的计算量,结合了梯度向量的信息及前一次迭代的梯度向量信息，优点在于仅仅需要在每部计算中存储少量的信息，可应用到大问题上,直接 搜索法方法简单，但收敛速度一般比较慢，需要计算大量的函数值,牛顿,法需要最少的迭代,缺点：有多重局部解存在时，牛顿法不一定能找出全局最优解,2.,需要解一组含有,n,个对称线性方程的方程组,3.,需要求一阶、二阶偏导数，实际过程中可能不存在,4.,使用到单元步长时，可能不收敛,Summary,拟牛顿法 不必用解析法更新汉森矩阵，也不需要用计算机花费时间用于由离散方法求二阶偏导数矩阵，还可避免每次更新,H,的求逆运算。,谢谢观赏,