牛顿法 二阶梯度法

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,3.3,牛顿法（二阶梯度法）,一,原始牛顿法,基本思想：是利用二次函数（二次曲线）,来逐点去近似或逼近原目标函数 ，然后求出这个二次函数的极小点 作为对原目标函数求优的下一个迭代点 通过若干次的,重复迭代，使迭代点逐步逼近原目标函数极小点 。,设,已知一维目标函数 的初始点,过,A,点作一与原目标函数 相切的二次曲线,抛物线 ，求此抛物线的极小点的坐标 ，将 代入原目标函数 求得 值或,B,点，过,B,再作与 相切的二次曲线求,C,直到求出 。,设 只有连续一，二阶偏导数，在,点邻域取 的泰勒二次多项式,求此函数的极小点 可由,求得,这是一维问题，同理对于,n,维问题有,上,式,中,因此上式有：,当 时，可求 的极值点，当,矩阵为正定时，有极小值。,由（,1,）得,因为（,1,）式可写为,其中：,因为 是二次函数，故 是线性函数。,令 由（,2,）式则有,若 为可逆矩阵，上式两边左乘,则有下式：,得：,当 为二次函数时，,X,就是,是,一个常数矩阵,则牛顿法的一般迭代公式是：,迭代方向,该,方向为牛顿方向,在迭代公式中没有步长因子，或看作是步长恒等于,1,。,通过这种迭代，逐次向极小点逼近,。,试用牛顿法,二、修正牛顿法（阻尼牛顿法）,在,上面的牛顿法中，存在一个问题，由于迭代式中没有步长因子，或者说步长,=1,，所以有时函数值反而有所增大，即 因而可能造成点列的发,散，而使计算失败。从而要对古典（原始）牛顿法做修正，提出修正牛顿法。,方法：步长改用最优步长因子 ，将迭代式改写为：,应为,为,0,此时初始点无论如何选择，则可得到最优结果。,步骤如下：,（,1,）任选初始点 ，给定精度,置,k=0,（,2,）,计算 点的梯度和海赛矩阵的逆,矩阵,（,3,）,检验是否满足精度要求，,若满足停止迭代，否则进行（,4,）步,（,4,）令,（,5,）从 出发沿牛顿方向 进行一,维搜索,求出最优步长,（,6,）令,K=K+1,转步骤（,2,）,使用牛顿法的条件：,n,（,变量较多时）因次较高，海赛矩阵是奇异矩阵，逆矩阵不存在，不能使用牛顿法。,例：用牛顿法求函数,的最优解，初始点,DFP,变尺度法,由于梯度法和牛顿法具有以上的缺点，能不能找到一种方法能拟补上两种方法的缺点，从而综合上两种方法的各自优点，提出了如下变尺度法的基本思路。,基本思想：在牛顿法中探索方向,设法构造出一个对称正定矩阵 来代替,在迭代中逐渐逼近,简化牛顿法的计算，,且收敛快。,变尺度法是用 来逼近,所以称拟牛顿法，迭代公式为：,-,步长由,求出,探索方向,（,1,）,-n*n,阶对称正定矩阵，是变化的，递推形式为 （,2,）,-,校正矩阵，它与 ，,向量有关。,综上可知：当 是梯度迭代公式,当 是牛顿迭代公式,以上两种方法是变尺度法的特例,怎样找出 ，先分析 的关系，设 为一般形式的目标函数，并且有连续的一、二阶偏导数，在点,的泰勒近似展开为,梯度为,令 则有,两边左乘,这样找到了 与 及,之间的关系，用 来代替,既有,迭代开始，可选择,如果构造出 后，再如果 可表示为（,2,）式,-,校正矩阵，可用统一的公式表示。,经过三个人的修改的校正矩阵 的公式即所谓,DFP,公式为：,因为 为,n*n,阶对称正定矩阵，固有,式中,有 后就可按（,2,）式求出,有 后就可按（,1,）求出 新方向探索,最后得出,DFP,变尺度法的迭代公式归结为,适用条件：容易求出,f(x),的梯度,n100,时此方法最好。,所以又发展了,BFGS,比,DFP,更为成功，方法：只是 公式不同，其余完全相同。,两种变尺度法的计算步骤一样为：,（,1,）任选初始点 ，给定精度,维数,n,（,2,）置,k=0,， （,单位矩阵）,探索方向为，,（,3,）进行一维搜索求 ，,（,4,）计算 ，如果 小于给定精度，则 为极小点，停止迭代，否则转下一步。,（,5,）检查迭代次数，若,k=n,维数则,并转第二步，若,kn,则进行下一步。,（,6,）构造新的探索方向,为此计算,令,k=k+1,转向步骤（,3,）,