牛顿法 二阶梯度法

§3.3牛顿法（二阶梯度法）一原始牛顿法基本思想：是利用二次函数（二次曲线）来逐点去近似或逼近原目标函数，然后求出这个二次函数的极小点作为对原目标函数求优的下一个迭代点通过若干次的重复迭代，使迭代点逐步逼近原目标函数极小点。xxfxk1x*0x*设已知一维目标函数的初始点过A点作一与原目标函数相切的二次曲线——抛物线，求此抛物线的极小点的坐标，将代入原目标函数求得值或B点，过B再作与相切的二次曲线求C直到求出。xfxxkkfA,xfxxk1xk1xfxkf1xfx*设只有连续一，二阶偏导数，在点邻域取的泰勒二次多项式求此函数的极小点可由求得这是一维问题，同理对于n维问题有xfxkxfxxxxxxxkfxffkkkkk221xk0xk上式中XXXXXXfXXkkTkTkkXfkXkf221XXkkHf2nXfHxxXjik1,2,......ji,2因此上式有：当时，可求的极值点，当矩阵为正定时，有极小值。由（1）得0xxxH(2)XXXkkkXHfX(1))(21XfXHkXkfXXXXXXfXXkkTkTkk因为（1）式可写为其中：XXXHXgfXTTxx21XXgXfkkxkxXXff因为是二次函数，故是线性函数。令由（2）式则有若为可逆矩阵，上式两边左乘则有下式：xX0X0XXXkkkXHfXkHXHk1得：当为二次函数时，X就是01XIXXHknkXfkXXHXkkfkX1xfx*是一个常数矩阵则牛顿法的一般迭代公式是：迭代方向XkHXXHXXkkkfk11XXHskkfk1该方向为牛顿方向在迭代公式中没有步长因子，或看作是步长恒等于1。通过这种迭代，逐次向极小点逼近。试用牛顿法1.0,0060410021212221xxxxxxxxf给定初始点的无约束最优解，例：求目标函数二、修正牛顿法（阻尼牛顿法）在上面的牛顿法中，存在一个问题，由于迭代式中没有步长因子，或者说步长=1，所以有时函数值反而有所增大，即因而可能造成点列的发散，而使计算失败。从而要对古典（原始）牛顿法做修正，提出修正牛顿法。kxxkkff1方法：步长改用最优步长因子，将迭代式改写为：应为kXXHXXkkkkfk11skXXHskkfk1sxxkkkk1为》0此时初始点无论如何选择，则可得到最优结果。)()(min)()()()()()(kkkkkksxfsxfkk步骤如下：（1）任选初始点，给定精度置k=0（2）计算点的梯度和海赛矩阵的逆矩阵（3）检验是否满足精度要求，若满足停止迭代，否则进行（4）步xkfRxn)0(0xk（4）令（5）从出发沿牛顿方向进行一维搜索求出最优步长（6）令K=K+1转步骤（2）XXHskkfk1xksk)()(min)()()()()()(kkkkkksxfsxfksxxkkkk1使用牛顿法的条件：n（变量较多时）因次较高，海赛矩阵是奇异矩阵，逆矩阵不存在，不能使用牛顿法。例：用牛顿法求函数的最优解，初始点102214212211xxxxxf1000-50TXDFP变尺度法由于梯度法和牛顿法具有以上的缺点，能不能找到一种方法能拟补上两种方法的缺点，从而综合上两种方法的各自优点，提出了如下变尺度法的基本思路。基本思想：在牛顿法中探索方向设法构造出一个对称正定矩阵来代替XXHskkfk1Ak)(在迭代中逐渐逼近简化牛顿法的计算，且收敛快。变尺度法是用来逼近所以称拟牛顿法，迭代公式为：XHk1XHk1Ak)(XHk1SXXAXXkkkkkkkkf1-----步长由求出探索方向（1）)(min)()()()()()()(kkkkkksxfsxfkXASkkfk------n*n阶对称正定矩阵，是变化的，递推形式为（2）-----校正矩阵，它与，向量有关。综上可知：当是梯度迭代公式当是牛顿迭代公式以上两种方法是变尺度法的特例EAAkkk1Ekxxkk,1XXkkff和1IAkXHAkk1怎样找出，先分析的关系，设为一般形式的目标函数，并且有连续的一、二阶偏导数，在点的泰勒近似展开为梯度为AkxfxH和xfxkxxxxxxfxkkTkTkxHkxkfxf21)()()(xxgxxxkkkkkkxHxHfxfg令则有两边左乘xxkk1111xxxgxgkkkkkkHfgggkkk1xxxkkk1xxHgkkk)(XHk1这样找到了与及之间的关系，用来代替既有迭代开始，可选择如果构造出后，再如果可表示为（2）式gxHxkkk1XHk1xkgkAkXHk1gAxkkkIAAk0AkAk1EAAkkk1------校正矩阵，可用统一的公式表示。经过三个人的修改的校正矩阵的公式即所谓DFP公式为：EkEkgAgAggAgxxxEkkTTTkkkTTkkkkkkk)()()()()()()()()()()()(因为为n*n阶对称正定矩阵，固有式中有后就可按（2）式求出AkgAgAggAgxxxEkkTTkkkTTkkkkkkk)()()()()()()()()()()()(gggkkk1xxxkkk1EkAk1有后就可按（1）求出新方向探索最后得出DFP变尺度法的迭代公式归结为Ak1Sk1XASkkkf111EAAxAssxsxsxxAxxkkkkkkkkkkkkkkkkkkkkffff111min适用条件：容易求出f(x)的梯度n100时此方法最好。所以又发展了BFGS比DFP更为成功，方法：只是公式不同，其余完全相同。Ek))()()()()()()()(()(1)()()()()()()()()(AgxxgAgxgAgxxxxgxEkTkTkkkTkTTkkTkkkkkkkTkkk两种变尺度法的计算步骤一样为：（1）任选初始点，给定精度维数n（2）置k=0，（单位矩阵）探索方向为，（3）进行一维搜索求，Rxn)0(0IkAA0gAXASkkkkkf)()()()1(kkkksxx)(k)(min)()()()()()()(kkkkkksxfsxf（4）计算，如果小于给定精度，则为极小点，停止迭代，否则转下一步。（5）检查迭代次数，若k=n维数则并转第二步，若kn则进行下一步。（6）构造新的探索方向为此计算令k=k+1转向步骤（3）Xgkfk11gk1xk1xxn10gAXASkkkkkf11111Egxkkk,,EAAkkk1