单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,牛顿法与修正牛顿法,1,牛顿法与修正牛顿法1,6,、评价,4,、优缺点,5,、修正牛顿法,3,、迭代步骤,1,、思想来源,2,、基本思想,牛顿法和,修正牛顿法,2,6、评价4、优缺点5、修正牛顿法3、迭代步骤1、思想来源,1,、思想来源,梯度法相邻两次搜索方向总是相互正交，搜索路线呈锯齿形，使得其在极小点附近，收敛速度越来越慢。人们试图找到这样一种方向：,它直接指向最优点,，使得从任意选定的初始点出发，沿此方向迭代,一次就能达到极小点,。,3,1、思想来源梯度法相邻两次搜索方向总是相互正交，搜索路线呈锯,2,、基本思想,在求目标函数 的极小值时，先将它在 点附近展开,成泰勒级数的二次函数式，然后求出函数的极小值点，并以此点作,为欲求目标函数的极小值点 的一次近似值,。,设目标函数是连续二阶可微的，将函数在点 按泰勒级数,展开，并取到二次项：,4,2、基本思想4,对,x,求导，其极值点必满足一阶导数为零，所以，,得到,式中,，,为,Hessian,矩阵的逆矩阵。,5,对x求导，其极值点必满足一阶导数为零，所以，5,在一般情况下，不一定是二次函数，因而 也不可能是 的极值点。但是在 点附近，函数 和 是近似的，所以可以用 点作为下一次迭代，即得,如果目标函数 是正定二次函数，那么 是个常矩阵，逼近式,1,是准确的。因此由 点出发只要迭代一次既可以求 的极小点。,6,在一般情况下，不一定是二次函数，因而,式与一维搜索公式 比较，则有搜索 方 向 ，步长因子,牛顿法的迭代算式,其中 称为,牛顿方向。,7,式与一维搜索公式,3,、迭代步骤,一,给定,初始点 ，计算精度,，令,k=0,；,二,计算 点的梯度 、,及其逆矩阵 。,三,构造搜索方向,8,3、迭代步骤8,四,沿 方向进行一维搜索，得迭代点,五,收敛判断：,若 ，则 为近似最优点，迭代停止，,输出最优解 和 终止计算。,若不满足，令,k=k+1,，转第二步继续迭代。,9,四 沿 方向进行一维搜索，得迭代点9,例：,用牛顿法求函数,的极小值。,解：,(1),取初始点,(2),计算牛顿方向,10,例：解：10,故,(3),极小值,11,故(3)极小值11,4,、优缺点,数学分析表明，牛顿法具有很好的局部收敛性质，对,二次函数,来说，仅,一步,就达到优化点，,但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛；,牛顿法必须求,一阶、二阶导数及求逆阵,，这对较复杂的目标函数来说，是较困难的。,12,4、优缺点12,5,、修正牛顿法,当目标函数为非二次函数时，目标函数在 点展开所得的二次函数是该点附近的一种近似表达式，所求的极小点，当然也是近似的，需要继续迭代。但是当目标函数严重非线性时，用式 进行迭代则不能保证一定收敛，即在迭代中可能会出现 ，所得到的下一点不如原来的好。这和初始点的选择是否恰当有很大的关系。,13,5、修正牛顿法 当目标函数为非二次函数,为了克服牛顿法的上述缺陷，可以通过在迭代中引入步长因子和一维搜索加以解决，即令,式中，,-,一维搜索所得的,最优步长因子,。,因而将 称为,牛顿方向。,经过这种修改后的算法称为,修正牛顿法,。,也称,牛顿方向法,or,阻尼牛顿法。,14,为了克服牛顿法的上述缺陷，可以通过在迭代中,举例,：,用修正牛顿法求解下列无约束优化问题，已知,解：,因为,所以,15,举例：用修正牛顿法求解下列无约束优化问题，已知解：15,由,修正牛顿法,，得,带入原函数,对 求导,解得,代入,因为 故迭代终止；,所以,最优解,为,16,由修正牛顿法，得16,6,、牛顿法的评价,由于采用了目标函数的,二阶导数,信息，收敛速度比梯度法快。,牛顿法迭代公式与一般迭代公式的,区别,在于，,没有最优步长因子,。这使得在接近最优点时，由于步长不能调节，可能会错过最优点，造成算法的稳定性欠佳，甚至造成不能收敛而导致计算失败。为了克服这一点，提出了,修正牛顿法,，它既保持了牛顿法收敛快的特性，有放宽了对初始点选择的要求，保证每次迭代的结果都是目标函数值下降。,需要计算,Hessian,矩阵,及其,逆矩阵,，内存占用、计算量大；此外二阶导数不存在，或者逆矩阵不存在的情况不能应用。,17,6、牛顿法的评价由于采用了目标函数的二阶导数信息，收敛速度比,