最优化论文

1题目：非线性最小二乘法问题的一种解法--高斯-牛顿法学生姓名：聂倩云学号：113113001039学院：理学院专业名称：应用数学非线性最小二乘法问题的一种解法--高斯-牛顿法2目录前言................................................................11.拟牛顿法及相关讨论...............................................12.牛顿法............................................................13.拟牛顿法..........................................................23.1DFP公式.....................................................23.2BFGS公式....................................................43.3限域拟牛顿法................................................64.针对二次非凸性函数的若干变形......................................6参考文献：..........................................................719非线性最小二乘法问题的一种解法--高斯-牛顿法11非线性最小二乘法问题一种解法--高斯-牛顿法学生：聂倩云学号：113113001039摘要：非线性最小二乘法问题在工程技术、测绘等各个领域有着非常广泛的应用，我们考虑无约束非线性最小二乘问题的一种常见的解法：高斯-牛顿法。求解无约束优化问题的基本方法是牛顿法，本文从这点出发，介绍此方法步骤，探讨此方法的收敛性，讨论它的收敛速度，并给出高斯-牛顿法的一种修正：阻尼高斯牛顿法。关键词：非线性最小二乘；高斯-牛顿法；收敛性；收敛速度前言非线性最小二乘问题结构特殊，不仅可以用一般的最优化问题求解的方法，还可以对一般的无约束优化问题求解方法进行改造，得到一些特殊的求解方法。而这些方法基本思想就是形成对目标函数的海森矩阵不同的近似。1.非线性最小二乘法问题概述非线性最小二乘法模型为221212121minxrxrxrxrxfTmii其一阶、二阶导数分别为xrxAxgxSxMxrxrxAxAxGmiiiT12其中Tmxrxrxrxr,,,21称为在点x处的残向量，xri为非线性函数，且xrxrxAm,,1，其中TxAxAxM称为高斯-牛顿矩阵，为xG中的线性项，xS为xG中的非线性项。2.高斯-牛顿法高斯-牛顿法主要思想是省略非线性项xS从而形成对海森矩阵的近似。29非线性最小二乘法问题的一种解法--高斯-牛顿法22当xri在目标函数最优解x处等于0，称xr为0残量；当xri在目标函数最优解x处取值较小，称xr为小残量，这时用近似逼近使xS为0，即这时线性项xM去近似海森矩阵xG比较好，我们通过求解方程组kkkTkkrAgAA的最优解k，并将它作为搜索方向，此时迭代形式为kkkxx1这就是高斯-牛顿法。2.1方向的下降性由于TkkAA半正定，所以kkTTkkTrAAA0即0kTkkTgrA所以高斯-牛顿法的搜索方向不可能是xf的上升方向，这就保证了高斯-牛顿法的可行性。2.2收敛性和收敛速度先给出一个定理：定理：下列条件成立（1）设D为开凸集，xf在D上二次连续可微；（2）Dx使0xrxAxg；（3）存在常数，使DyxyxyAxA,,DyxyxyGxG,,（4）xA满秩且存在常数M，使得DxMxMxHxA,,139非线性最小二乘法问题的一种解法--高斯-牛顿法33则高斯-牛顿法对所有的Dx都有定义，且21kkkhhxSxHh其中xxhkk证明：由于xA满秩，所以TkkAA正定，所以高斯-牛顿法搜索方向是下降方向，从而对所有的Dx都有定义。yxyAyAyAxAyAxAxAxAyAyAxAxAyMxMTTTTTT2yxyMyGxMxGySxS2yxMyMxMyMxMyMxMyHxH211112而20kkkkhhxGxgxg两边左乘kH，则kkkkkkkkkkkkkhSHHhSSHhxSxHhhhSHh120从而可以证明结论。我们从上面定理结论可以看出：若S比较大，则高斯-牛顿法一般不收敛。如果方法收敛，则当0S时，有21kkhh，从而高斯-牛顿法二次收敛；当0S时，方法是线性收敛的。49非线性最小二乘法问题的一种解法--高斯-牛顿法44如果M正定且SH小于一个小于1的数，则方法局部收敛。我们可以简单推导一下：设1SH，则由定理得到kkkhhch1如果存在初始点的一个邻域使1hc，则可以得到12hh依次迭代下去，可以得到kkkhh1当k时有0kh，因而方法收敛。2.3高斯-牛顿法的步骤及例题Step1：给定初始点1x和精度，置1k；Step2：如果kkrA，则停止计算；否则计算kkTkkrAAA得到k；Step3：置kkkxx1，1kk。高斯-牛顿方程组kkTkkrAAA的求解：（1）对TkkAA进行TLL分解或者TLDL分解，化成方程组yLrALyTkk求解，L为三角矩阵，所以两个方程组进行前代和后代就可以求出k。（2）对增广矩阵rAT,作QR正交分解，Q为正交矩阵，01RR,1R为上三角矩阵，即kTkTrQRQrA,于是11RRAATTkk,高斯方程组的解可由59非线性最小二乘法问题的一种解法--高斯-牛顿法55nkTkrQR回代得出。例：设22211xxxxf，1Rx，试讨论函数的极小值点。解：令11xr，122xxr计算TkTxxkxxrxrAk12,1,21kkTkkrAAA即kkkkkxxxxx22321212322解出22321212232kkkkkkxxxxx则2232112122kkkkkkkxxxxxx当0时，迭代点01kx，则极小值点0x；当0，且1时，若假定初始近似kx充分小，则kkkkkxxxxx222322kkxx21212所以21kkkxxx迭代下去，有2kkppkxxx当p时，有0pkx69非线性最小二乘法问题的一种解法--高斯-牛顿法66即迭代点列kx趋向于0；当1时，迭代点列不收敛。2.4高斯-牛顿法的优点和缺点优点：（1）高斯-牛顿法仅仅利用函数的一阶导数的信息直接得到海森矩阵的近似，给计算带来很大方便。（2）对于零残量问题（即0xr）有局部二阶收敛速度；（3）对于小残量问题（即xr较小或者xr接近线性）有较快的局部收敛速度；（4）对于线性最小二乘问题，一步达到极小点。缺点：（1）对于不是很严重的大残量问题，收敛速度较慢；（2）对于严重的大残量问题（即xf较大或者xri的非线性程度较高），高斯-牛顿法一般不收敛；（3）xA不满秩时，搜索方向不一定下降，方法不一定有定义。3对高斯-牛顿法的简单修正（1）阻尼高斯—牛顿法给定局部最优解x的一个初始估计1x,则其第k次迭代的步骤为Step1：确定kkTkkrAAA的解；Step2：确定步长k，使kkkkxfxf；Step3：置kkkkxx1。其中k由线性搜索确定的步长，在原来的高斯-牛顿法的基础上添加了一个阻尼因子，确保xf每一步都是下降的。当kA满秩时，阻尼高斯-牛顿法是收敛的；当kA不满秩时，方法或收敛于非平稳点或在未接近平稳点之前提前终止，即在某处迭代时，有0Tkg,xf得不到进一步下降，迭代未达到精确值之前就终止。79非线性最小二乘法问题的一种解法--高斯-牛顿法77（2）MarquardtLevenberg法（ML法）通过求解方程组kkTkkrAIAA解出k，再进行迭代：kkkxx1ML法具有全局收敛性，且在下列条件成立时局部二次收敛：xf二次连续可微，对给定的初始点1x水平集1xL有界，迭代产生的点列kx收敛于x，且xG正定，如果0xS,则方法局部二次收敛。在这里，就不详细证明，感兴趣的读者可以查阅相关资料。我们可以看出高斯-牛顿法是存在它的缺点的，一方面kM对海森矩阵kxG的近似程度不好；另一方面当kA不满秩时，高斯-牛顿法不一定有定义。所以高斯-牛顿法仍然需要改进，一些研究者做出了很多的改进方案，例如拟牛顿修正形成的适应算法，还有杂交算法，分解式拟牛顿方法等等，所以仍需我们在这方面不断学习和探索，而且非线性最小二乘问题在工程技术等各个领域应用广泛，所以我们应该不断积累此类问题，从而推动其他领域的发展。参考文献：[1]徐成贤，陈志平，李乃成.近代优化方法[M].科学出版社.2002,198-203.[2]袁亚湘，孙文瑜.最优化理论与方法[M].科学出版社.1997.[3]徐成贤，陈志平.不精确高斯-牛顿法的收敛性.工程数学学报.1997,14(4).