资源描述：
《牛顿法和拟牛顿法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、§4.6.5牛顿法拟牛顿法&x1x20Penaltymethod实际化工过程数学模型：求解复杂、计算量大数值算法实现模型求解：迭代形式逐渐逼近最优解x*，求解过程：在可行域范围或非可行域内按照一定策略搜索最优值的问题。初始点更新点最优解X*判断所得点是否足够接近，满足则停止搜索系统思想迭代法共同特点：对求解变量的数值进行逐步改进，使之从开始不能满足方程的要求，逐渐逼近方程所要求的解，每一次迭代所提供的信息（表明待解变量的数值同方程的解尚有距离的信息），用来产生下一次改进值，迭代方案有多种，这就形成了不同的迭代方法。变量轮换单纯形法最速下降法共轭梯度法牛顿法&拟牛顿法系统思想一.牛顿法1
2、.问题提出最速下降法：当前迭代点Xk,迭代简单，但容易产生锯齿现象，使得收敛缓慢，即一阶逼近函数得到的模型比较粗糙。提高逼近阶数牛顿法：二阶逼近函数算法，快速收敛牛顿迭代最速下降图4-12从目标函数值近似值的观点比较最速下降法和牛顿法一、牛顿法将f(xk+1)在x=xk处一阶泰勒展开：目标函数趋于零一.牛顿法将f(xk+1)在x=xk处二阶泰勒展开：目标函数趋于零一.牛顿法——一维搜索简化公式一.牛顿法推广到多元函数情况，即得到求解多元函数极小的牛顿迭代算法：一.牛顿法——Newton迭代公式其中1.牛顿法几何解释几何直观解释：最密切的二次曲线逼近2.Newton算法Step1:给初始
3、点x0,精度ε>0,k=0Step2:计算Step3:由方程组H(xk)△xk=-hk解出xk+1,当Hk可逆时，xk+1=xk-Hk-1.hkStep4:例1.设分析:搜索方向解：故求在点处的搜索方向.故需要写出的表达式.故所以进而得因此所求的牛顿方向为由例2：用牛顿法求解：解：因所以迭代终止,最优点为:3.牛顿法优缺点(1)对正定二次函数，迭代一次就可以得到极小点．(2)如果正定且初始点选取合适，算法很快收敛．优点(2)收敛性与初始点的选取依赖很大．(3)每次都需要计算海森阵计算量大．(4)每次都需要解方程组方程组有时奇异或病态的，无法确定或不是下降方向．(1)要求函数二阶可微.缺
4、点二.阻尼牛顿法—Newton法改进这样往往可以克服上述缺点.针对缺点中的(2),在求新迭代点时，不直接用公式进行迭代，而是以作为搜索方向进行一维搜索，求步长，使1.基本思想2.阻尼牛顿法算法Step1:给出Step2:计算如果停．否则计算并令Step4:令转Step2.Step3:沿进行线搜索，得最优步长3.收敛性定理定理3.7二次连续可微，正定．设是由阻尼牛顿法得到的迭代点列.记必有聚点,且任何聚点有界,若水平集满足则1.分析：Newton法优点：高收敛速度（二阶收敛）缺点：对初始点目标函数要求高，计算量，存储量大（需要计算、存储hessian矩阵及其逆矩阵）拟牛顿法——模拟牛顿法
5、给出的一个“保优去劣”的算法考虑Newton迭代公式：搜索方向为进行改进：一、避免求逆矩阵，用则上式变为此时搜索方向为步长因子为二、更大的灵活性，一般化这样的Hk存在？1、为保证总是下降方向，要求每一个Gk均称为正定矩阵2、为易于计算，要求有简单的迭代形式，最简单的迭代关系为拟牛顿条件分析：Hk-1需满足的条件，并利用此条件确定Gk由归纳法，若由Hk可求Hk+1,则在xk+1点，Taylor展开想到在确定拟牛顿方程式的Hk+1时，若矩阵Hk+1对称，则需要待定（n+n2)/2个未知数，n个方程，所以拟牛顿方程一般有无穷个解，故由拟牛顿方程确定的一族算法，通常称之为拟牛顿法拟Newton
6、算法1、给定初始点x0,正定矩阵H0,精度ε>0,k=02、计算搜索方向3、令xk+1=xk+tk.sk,其中tk为f(xk+tkSk)=minf(xk+tsk)4、若，则xk+1为最优解，否则转步骤55、按照校正公式Gk+1=Gk+△Gk,计算GK+1使得Gk+1满足拟牛顿条件或拟Newton方程：Gk+1*yk=dk令k=k+1,转步骤2DFP算法1、DFP算法提出：(1)Davidon(2)Fletcher&Powell(3)多变量无约束优化2、如何确定△G(k)?——秩2校正法根据拟Newton条件：Gk+1yk=dk,我们有满足上述方程的解很多，可如下确定一组解则我们可以取即
7、由此得到Gk的DFP校正公式性质：H0>0,则可以推出Hk>0正交继承性DFP算法步骤将拟Newton法第5步骤改为:5、按DFP校正公式计算Gk,k=k+1,转步骤2BFGS算法Summary非线性问题规划求解变量轮换法单纯形法最速下降法共轭梯度法牛顿法拟牛顿法无约束最优化问题有约束最优化问题单变量函数的优化——一维搜索多变量函数的优化策略系统思想Summary函数值搜索（零阶法）变量轮换法单纯形法梯度信息搜索（一阶法）最速下降法共轭梯度法二
