牛顿法和拟牛顿法.pptx

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

当然初始点离最小点越近越好 2、确定搜索方向 Sk ，使目标函数从 xk 沿此方向下降 3、在xk 方向上进行一维搜索在由 xk 出发的射线 x=xk+αkSk (αk≥0)上选取步长 αk ,使一元（ α ）函数 f(xk+αkSk ) 在α =αk处取最小值它是一个单变量函数极小 问题由此得到新点 xk+1=xk+ αk Sk (αk≥0) 4、检验xk+1 是否最优解共同缺点在于有多重局部解存在时，不一定能 找出全局最优解Summary变量轮换法特点： 可靠性较高，属于直接法，只需目标函数值信息，不需要目 标函数导数 程序简单，易于掌握但是搜索效率低，且 越接近极值点，搜索速度越慢单纯形法特点：是不需要复杂的导数运算，它朝最优点的 移动完全由上一个单纯形的结果所定，计算机上使用时贮 存少但由于步长固定，故缺少加速的方法单纯形：指多维空间的凸多 边形的顶点数比空间维数多 ，如正四面体Summary最速下降法特点： 前 后两步迭代的搜索方向 相互正交，对f（x)的 尺度太灵敏，收敛缓慢 ，容易在x空间上产生 大量的摆动，可能产生 锯齿现象共轭梯度法 特点： 增大了很少的计算量 结合了梯度向量的信息 及前一次迭代的梯度向 量信息，优点在于仅仅 需要在每部计算中存储 少量的信息，可应用到 大问题上直接 搜索法方法简单，但收敛速度一般比较慢，需 要计算大量的函数值牛顿法需要最少的迭代 缺点：有多重局部解存在时，牛顿法不一定能找出全局 最优解 2.需要解一组含有n个对称线性方程的方程组 3.需要求一阶、二阶偏导数，实际过程中可能不存在 4.使用到单元步长时，可能不收敛Summary拟牛顿法 不必用解析法更新汉森矩阵，也不需要用计算机 花费时间用于由离散方法求二阶偏导数矩阵，还可避免每次 更新H的求逆运算。