非线性最小二乘法问题的一种解法--高斯-牛顿法.doc

1、1题目非线性最小二乘法问题的一种解法高斯牛顿法学生姓名学号113113001039学院理学院专业名称应用数学非线性最小二乘法问题的一种解法高斯牛顿法2目录前言11拟牛顿法及相关讨论12牛顿法13拟牛顿法231DFP公式232BFGS公式433限域拟牛顿法64针对二次非凸性函数的若干变形6参考文献719非线性最小二乘法问题的一种解法高斯牛顿法11非线性最小二乘法问题一种解法高斯牛顿法学生学号113113001039摘要非线性最小二乘法问题在工程技术、测绘等各个领域有着非常广泛的应用，我们考虑无约束非线性最小二乘问题的一种常见的解法高斯牛顿法。求解无约束优化问题的基本方法是牛顿法，本文从这点出发，

2、介绍此方法步骤，探讨此方法的收敛性，讨论它的收敛速度，并给出高斯牛顿法的一种修正阻尼高斯牛顿法。关键词非线性最小二乘；高斯牛顿法；收敛性；收敛速度前言非线性最小二乘问题结构特殊，不仅可以用一般的最优化问题求解的方法，还可以对一般的无约束优化问题求解方法进行改造，得到一些特殊的求解方法。而这些方法基本思想就是形成对目标函数的海森矩阵不同的近似。1非线性最小二乘法问题概述非线性最小二乘法模型为221212121MINXRXRXRXRXFTMII其一阶、二阶导数分别为XRXAXGXSXMXRXRXAXAXGMIIIT12其中TMXRXRXRXR,21称为在点X处的残向量，XRI为非线性函数，且XRX

3、RXAM,1，其中TXAAXM称为高斯牛顿矩阵，为XG中的线性项，XS为XG中的非线性项。2高斯牛顿法高斯牛顿法主要思想是省略非线性项XS从而形成对海森矩阵的近似。29非线性最小二乘法问题的一种解法高斯牛顿法22当XRI在目标函数最优解X处等于0，称XR为0残量；当XRI在目标函数最优解X处取值较小，称XR为小残量，这时用近似逼近使XS为0，即这时线性项XM去近似海森矩阵XG比较好，我们通过求解方程组KKKTKKRAGAA的最优解K，并将它作为搜索方向，此时迭代形式为KKKXX1这就是高斯牛顿法。21方向的下降性由于TKKAA半正定，所以KKTTKKTRAAA0即0KTKKTGRA所以高斯牛顿

4、法的搜索方向不可能是XF的上升方向，这就保证了高斯牛顿法的可行性。22收敛性和收敛速度先给出一个定理定理下列条件成立（1）设D为开凸集，XF在D上二次连续可微；（2）DX使0XRXAXG；（3）存在常数，使DYXYXYAXA,DYXYXYGXG,（4）XA满秩且存在常数M，使得DXMXMXHXA,139非线性最小二乘法问题的一种解法高斯牛顿法33则高斯牛顿法对所有的DX都有定义，且21KKKHHXSXHH其中XXHKK证明由于XA满秩，所以TKKAA正定，所以高斯牛顿法搜索方向是下降方向，从而对所有的DX都有定义。YXYAYAYAXAYAXAXAXAYAYAXAXAYMXMTTTTTT2YXY

5、MYGXMXGYSXS2YXMYMXMYMXMYMXMYHXH211112而20KKKKHHXGXGXG两边左乘KH，则KKKKKKKKKKKKKHSHHHSSHHXSXHHHHSHH120从而可以证明结论。我们从上面定理结论可以看出若S比较大，则高斯牛顿法一般不收敛。如果方法收敛，则当0S时，有21KKHH，从而高斯牛顿法二次收敛；当0S时，方法是线性收敛的。49非线性最小二乘法问题的一种解法高斯牛顿法44如果M正定且SH小于一个小于1的数，则方法局部收敛。我们可以简单推导一下设1SH，则由定理得到KKKHHCH1如果存在初始点的一个邻域使1HC，则可以得到12HH依次迭代下去，可以得到KK

6、KHH1当K时有0KH，因而方法收敛。23高斯牛顿法的步骤及例题STEP1给定初始点1X和精度，置1K；STEP2如果KKRA，则停止计算；否则计算KKTKKRAAA得到K；STEP3置KKKXX1，1KK。高斯牛顿方程组KKTKKRAAA的求解（1）对TKKAA进行TLL分解或者TLDL分解，化成方程组YLRALYTKK求解，L为三角矩阵，所以两个方程组进行前代和后代就可以求出K。（2）对增广矩阵RAT,作QR正交分解，Q为正交矩阵，01RR,1R为上三角矩阵，即KTKTRQRQRA,于是11RRAATTKK,高斯方程组的解可由59非线性最小二乘法问题的一种解法高斯牛顿法55NKTKRQR回

7、代得出。例设22211XXXXF，1RX，试讨论函数的极小值点。解令11XR，122XXR计算TKTXXKXXRXRAK12,1,21KKTKKRAAA即KKKKKXXXXX22321212322解出22321212232KKKKKKXXXXX则2232112122KKKKKKKXXXXXX当0时，迭代点01KX，则极小值点0X；当0，且1时，若假定初始近似KX充分小，则KKKKKXXXXX222322KKXX21212所以21KKKXXX迭代下去，有2KKPPKXXX当P时，有0PKX69非线性最小二乘法问题的一种解法高斯牛顿法66即迭代点列KX趋向于0；当1时，迭代点列不收敛。24高斯牛顿

8、法的优点和缺点优点（1）高斯牛顿法仅仅利用函数的一阶导数的信息直接得到海森矩阵的近似，给计算带来很大方便。（2）对于零残量问题（即0XR）有局部二阶收敛速度；（3）对于小残量问题（即XR较小或者XR接近线性）有较快的局部收敛速度；（4）对于线性最小二乘问题，一步达到极小点。缺点（1）对于不是很严重的大残量问题，收敛速度较慢；（2）对于严重的大残量问题（即XF较大或者XRI的非线性程度较高），高斯牛顿法一般不收敛；（3）XA不满秩时，搜索方向不一定下降，方法不一定有定义。3对高斯牛顿法的简单修正（1）阻尼高斯牛顿法给定局部最优解X的一个初始估计1X,则其第K次迭代的步骤为STEP1确定KKTKK

9、RAAA的解；STEP2确定步长K，使KKKKXFXF；STEP3置KKKKXX1。其中K由线性搜索确定的步长，在原来的高斯牛顿法的基础上添加了一个阻尼因子，确保XF每一步都是下降的。当KA满秩时，阻尼高斯牛顿法是收敛的；当KA不满秩时，方法或收敛于非平稳点或在未接近平稳点之前提前终止，即在某处迭代时，有0TKG,XF得不到进一步下降，迭代未达到精确值之前就终止。79非线性最小二乘法问题的一种解法高斯牛顿法77（2）MARQUARDTLEVENBERG法（ML法）通过求解方程组KKTKKRAIAA解出K，再进行迭代KKKXX1ML法具有全局收敛性，且在下列条件成立时局部二次收敛XF二次连续可微

10、，对给定的初始点1X水平集1XL有界，迭代产生的点列KX收敛于X，且XG正定，如果0XS,则方法局部二次收敛。在这里，就不详细证明，感兴趣的读者可以查阅相关资料。我们可以看出高斯牛顿法是存在它的缺点的，一方面KM对海森矩阵KXG的近似程度不好；另一方面当KA不满秩时，高斯牛顿法不一定有定义。所以高斯牛顿法仍然需要改进，一些研究者做出了很多的改进方案，例如拟牛顿修正形成的适应算法，还有杂交算法，分解式拟牛顿方法等等，所以仍需我们在这方面不断学习和探索，而且非线性最小二乘问题在工程技术等各个领域应用广泛，所以我们应该不断积累此类问题，从而推动其他领域的发展。参考文献1徐成贤，陈志平，李乃成近代优化方法M科学出版社2002,1982032袁亚湘，孙文瑜最优化理论与方法M科学出版社19973徐成贤，陈志平不精确高斯牛顿法的收敛性工程数学学报1997,144