最优化理论 第七章 非线性最小二乘问题

§7.1最小二乘问题1（回归方程问题）设(titi,tiyi)T（i12,m）m个实验点.现要根据12 ly与l个物理量t1,t2,,tl之间的关系式.yF(t1,t2,,tlx1x2,xnx1x2,xnn个待定参数(系数).因此问题是如何通过m(mn个实验点，确定方程中的系数.由于实验点问题的方法进行求解.一个合理的解决方法是将这些实验点到曲面距离最短的那个曲面作为所求曲面，从而求取该曲面方程.即求解无约束最优化问题mminxRni1

Fti,x)yi2，.（非线性方程组求解问题）F1(x1,x2,,xn)0,F(x,x,,x)0,2 1 2 n............................m(1,2,,n)0可等价地转化为求解无约束最优化问题mminF2(x,x,,x)，mxRn

i 1 2 ni1.m小于变量的个数nm等于变量的个数nm大于变量的个数n，则称其为超定问题.iinf(x)1r(x)Tr(x)1mi

r2(x), (7.1.1)xRn

2 2i1r(x)称为残量函数，i12,m.r(x)是仿射函数，即r(x)aTxb，i i i i i.若令aT a

a

b11 1

11 12 1naT a a a b A

2

21 22

2，

aT a

a

bmm2

mn

mi inf(x)1(xb)T(xb)1i

(aTxb)2. (7.1.2)xRn

2 2i10当某个ri(x是非仿射函数时，1i0m，则称(7.1.1)为非线性最小二乘问题.0n.但由于最小二乘问题具有一定的特殊性，即目标函数的表达式是由多个表达式的平方和组成，理应有更简单、更有效的方法.这正是最小二乘解法要解决的问题.§7.2 线性最小二乘问题的解法由(7.1.2)可知，线性最小二乘问题可写成minf(x)1||Axb||21xTATAxbTAx1bTb， (7.2.1)xRn

2 2 2nATAf(x)1xTATAxbTAx1bTb是二次凸函数.2 2x*为无约束最优化问题minf(xx*为xRn线性方程组ATAxATb0

(7.2.2)的解.由于二次凸函数必定有极小点，故线性方程组(7.2.2)必定可解. 事实上，若x*为minf(xf(x)x*满足(7.2.2)x*是(7.2.2)的xRnxRnf(xx*处Taylor展开，即有f(x)f(x*)f(x*)T(xx*)1(xx*)T2f(x*)(xx*)，2注意到f(x*ATAx*ATb02f(x*ATAf(x

f(x*).我们一般称(7.2.2)为最小二乘问题(7.2.1)（Axb0）的法方程组或正.A必须列满秩.对于通常系数矩阵是对称矩阵的线性方程组，我们一般采用先将其系数矩阵进行CholeskyLLTL是下三角矩阵，然后通过前代和回代求.增大了舍入误差.针对法方程组(7.2.2)的特殊结构，我们采用如下更为有效的求解方法.mnA列满秩.我们首先对线性方程Axb0的增广矩阵AbQR分解，设ARQ Q1QR，A bQR bQR b，O1 2 11O

11 1其中QmQ1是由Q的前nQ2是由Q的后mn列构R为nbQTb.1于是，由法方程组(7.2.2)，我们有ATAxATb(QR)TQRx(QR)TbRTRxRTQTbRTRxRTb

0，11 11 11 1 1 1 1 1 1 1n其中bn是b的前n个分量构成的n维向量. 与方程组

(7.2.3)同解.R1为n阶上三角矩阵，故线性方程组(7.2.3)通过简单回代就可以求解.线性最小二乘问题的正交分解法）1n步1：对增广矩阵A b进行QR分解，得到R和b1n

1QTb；12R1xbn0，得线性最小二乘问题(7.2.1)x*.§7.3Gauss-Newton法对于非线性最小二乘问题inf(x)1r(x)Tr(x)1m

ir2(x). (7.3.1)ixRn

2 2i1记向量值函数rRnRm的JacobiJ(x)，即r1(x)

r1(x)r(x)T

x

x 1 1 n J(x) ，r(x) r(x)m m m f(xHessian矩阵可以写成

xn mmi f(x)r(x)r(x)J(x)Tr(x)，i m im 2f(x)[r(x)r(x)Tr(x)2r(x)]J(x)TJ(x)r(x)2r(x). (7.3.3)i i i i i i i i i (7.3.1)Hessian矩阵2f(x的计算量很大.x*处一般满足ri(x*0（称为零残量问题（，i,,,m，Hesn7.3.3J(x)TJ(x是Hessian矩阵2f(x)的比较好的近似，而且容易计算.为此，把牛顿方程改造为J(xk)TJ(xk)dJ(xk)Tr(xk)， (7.3.4)由(7.3.4)解出目标函数的搜索方向dk，然后令xk1xkdk，Guass-Newton法.iir(xxk处线性化，然后用线性最小二乘问题的解去逼近非线性最小二乘问题的解.将r(xxk处Taylor一阶展开，有iii i r(x)r(xkr(xk)T(xxki12,m，r(xr(xkJ(xk)(xxi i J(xk)TJ(xk)(xxk)J(xk)Tr(xk)，(7.3.4).法）1x0，容许误差0，置k0；2：如果||f(xk||xk；步373.，解出dk；4xk1xkdk，置kk12.m法的构造可知，对于零残量问题和小残量问题具有较好的局部收敛效中等式右端的第二项比第一项相对来的大时就有可能不收敛.mM(x)J(x)TJ(xR(x)r(x)2r(x).i ii 定理7.3.1设f(x)1r(x)Tr(x在开凸集D上二阶连续可微，存在x*D使得2f(x*0.xDJ(x)列满秩，且存在正常数和xD，有||J(x||||M(x)1||.如果J(x)2f(x)均在D上Lipschitz连续，则Guass-NewtonxD有定义，且||xk1x*||||M(x*)1R(x*)||||xkx*||O(||xkx*||2). (7.3.5)J(xM(x)J(x)TJ(x正定，因此，Guass-Newton迭代对任意xD都有定义.对任意k，有||xk1x*||||xkdkx*||||xkx*M(xk)1J(xk)r(xk)||||M(xk)1[f(xk)2f(xk)(x*xk)]M(xk)1R(xk)(x*xk)||. (7.3.6)由于||M(x)1||2f(xM(xR(xD上Lipschitzf(x*0，故||M(xk)1[f(xk)(M(xk)R(xk))(x*xk)]||O(||x*xk||2). (7.3.7)J(xDLipschitz0，使得||JyJ(x||||yx||对xyDxD有||J(x||，我们有||M(y)M(x)||||[J(y)J(x)]TJ(y)J(x)T[J(y)J(x)]||2||xy||，||M(y)1M(x)1||||M(y)1[M(x)M(y)]M(x)1||22||xy||，||R(xRy||||2fyMy[2fyM(x||2||xy||，其中0是2f(xLipschitz常数.由此得||M(xk)1R(xk)M(x*)1R(x*)||||M(xk)1||||R(xk)R(x*)||||M(xk)1M(x*)1||||R(x*)||[22||R(x*)||(2)]||xkx*||，故有||M(xk)1R(xk)(x*xk)||||M(x*)1R(x*)||||(x*xk)||O(||x*xk||2).(7.3.8)等式(7.3.7)和不等式(7.3.8)可知，不等式(7.3.5)成立.注从(7.3.5)可以看出：1 k T kT k k k Tk（1）如果 (d2

d)

J(x)

J(x

)(d

d)(d

d)d

，则Guass-Newton法即非线性程度较高（即||ri(x*||较大）的问题.（2）如果定理中的条件成立，且||M(x*)1R(x*||1，则Guass-Newton法具有局部收敛性，特别地，当||R(x*||0时，算法具有局部二阶收敛速率.J(xk)TJ(xk奇异时，由(7.3.4)dk不一定是下降方向，类似于牛顿法的修.dkf(xkdk)

f(xk)，因此，我们可以通过增加线搜索步骤来保证目标函数的下降，即采用阻尼Guass-Newton法.§7.4Levenberg-Marquardt法Guass-Newton法并不能J(xk)TJ(xk奇异时，由(7.3.4)解出来的dk不一定是目标函f(x的下降方向.针对这种缺陷，LevenbergMarquardt提出了如下修正方案，他们将Guass-Newton方程(7.3.4)改造为[J(xk)TJ(xk)I]dJ(xk)Tr(xk)， (7.4.1)0.J(xk)TJ(xkJ(xk)TJ(xkI必定是正定的，从而由（7.4.1）解出来的dkf(x)xk处的下降方向.事实上f(xk)Tdkf(xk)T[J(xk)TJ(xk)I]1f(xk)0.0dkGuass-Newtondk的方向接近于f(xk.由§6.4可知，(||J(xk)TJ(xkI]1f(xk||越大，||dk||越小，因此，Levenberg-Marquardt法曾经被称为阻尼最小二乘法.事实上，Levenberg-Marquardt法是一类信赖域方法.7.4.1若dk是方程(7.4.1)0的解，则也是信赖域问题minq(d)1||J(xk)dr(xk)||2k 2

(7.4.2)||dk||.k证由于dk是方程(7.4.1)的解，将其代入q(d，得kq(dk)1(dk)TJ(xk)TJ(xk)dkr(xk)TJ(xk)dk1r(xk)Tr(xk)k 2 21r(xk)Tr(xk)1(dk)TJ(xk)TJ(xk)dk(dk)Tdk，2 2而对任意dRn，有q(d)1r(xk)Tr(xk)dT[J(xk)TJ(xk)I]dk1(d)TJ(xk)TJ(xk)dk 2 21r(xk)Tr(xk)dTJ(xk)TJ(xk)dkdTdk1(d)TJ(xk)TJ(xk)d，2 2因此，对任意满足||d||||dk||d，有q(d)q(dk)1(dkd)TJ(xk)TJ(xk)(dkd)[(dk)TdkdTdk]k k 21(dkd)TJ(xk)TJ(xk)(