最小二乘问题的求解方法一、最小二乘问题的概念二、线性最小二乘法三、非线性最小二乘法四、最小二乘问题的Matlab求解1/20
1/20 一、最小二乘问题的概念 二、线性最小二乘法 三、非线性最小二乘法 四、最小二乘问题的Matlab求解 最小二乘问题的求解方法
一、最小二乘问题的概念如下最优化问题称为非线性最小二乘问题m(P)min f(x)=rr(x)r(x)=Er(x)xeEni=1其中r(x)=(r(x), r(x),.., rm(x), xeE是x的非线性函数。如果r(x)是线性函数,即r(x)= Ax-b,则称问题(P)是线性最小二乘问题求解最小二乘问题等价于求解方程组：r;(x)=0 i=1,2,..,m最小二乘问题在数据拟合，参数估计和函数逼近等方面有广泛的应用。2/20
2/20 一、最小二乘问题的概念 = = = m i i T x E P f x r x r x r x n 1 2 （ ） min ( ) ( ) ( ) ( ) 是 的非线性函数。 其 中 （ ， ， ， ， x r x r x r x r x x E n = m T 1 2 ( ) ( ) ( ) ( )) 如下最优化问题称为非线性最小二乘问题。 则称问题(P)是线性最小二乘问题。 最小二乘问题在数据拟合，参数估计和函数逼近 等方面有广泛的应用。 求解最小二乘问题等价于求解方程组： ri (x) = 0 i = 1,2, ,m 如果r(x)是线性函数，即r(x) = Ax − b
二、线性最小二乘法(P) min (x)=rT(x)r(x) = Ax-bl1.问题Ae Rmxn,xeR",beRm页（P）的最优解A'Ax*=A'b2.性质x*是问题证：f(x) = (Ax-b)"(Ax -b)= xTAT Ax - 2bT Ax + bT b若x*是问题的最优解，则Vf(x*) = 2A' Ax* - 2A'b = 0即ATAx* = A'b3/20
3/20 二、线性最小二乘法 (P) min f (x) r (x)r(x) T = x *是问题（P）的最优解 m n n m A R x R b R , , A Ax A b T T = * 2 1. 问题 = Ax − b 2. 性质 x A Ax b Ax b b f x Ax b Ax b T T T T T = − + = − − 2 ( ) ( ) ( ) ( ) 2 2 0 * * f x = A Ax − A b = T T 证： 若x *是问题的最优解， 则 A Ax A b T T = 即 *
若x*满足ATAx*=A'b,则Vx=x*+Ax-bl =A(x*+8)-b=[(Ax *-b)+ AS} [(Ax *-b)+ AS]=Ax* -b + A8 + 28' A'(Ax* -b)=Ax* -b + A + 28T(A" Ax* - A'b)Ax*-b +A8 ≥Ax*-b故f(x)=Ax-b在x=x*处取得最小值4/20
4/20 x x δ * 则 = + 2 2 * Ax − b = A(x + ) − b 2 ( ) 2 * 2 * Ax b A A Ax b T T = − + + − * 2 2 = Ax − b + A 故 在 处取得最小值. 2 * f (x) = Ax − b x = x 2 ( ) 2 * 2 * Ax b A A Ax A b T T T = − + + − [(Ax * b) A ] [(Ax * b) A ] T = − + − + 若 x *满足A T Ax* = A T b， 2 * Ax − b
二、线性最小二乘法(P) min f(x)=rT(x)r(x) = Ax-bl1.问题Ae Rmxn,xe R"n,be Rm2.性质x是问题（P）的最优解>A'Ax*=A'b若(ATA)可逆x* =(AT A)-I ATbx* =(A)-1b若A为可逆方阵LetAERnxmwithn>m,thenmatrixATAispositivesemidefinite,Ifrank(A)=mthenATAispositivedefinite.5/20
5/20 二、线性最小二乘法 (P) min f (x) r (x)r(x) T = x *是问题（P）的最优解 m n n m A R x R b R , , A Ax A b T T = * 2 1. 问题 = Ax − b 2. 性质 * 1 ( ) T T x A A A b − = * 1 x A b ( )− = 若(ATA)可逆 若A为可逆方阵
2x + 2x2 = 3例1 给定方程组xi－2x,=1,试用最小二乘法求此【x, +4x,=3方程组的近似解。解 令 f(x) =(2x +2x -3) +(xi -2x2 -1) +(xi +4x2 -4),则原问题化为min f(x) 。xeE2232记A=-21一.x=X234L14则 f(x) =(Ax -b)(Ax-b)。310766.. x* =(A'A)-ATb =:ATA=ATb=162416L3]6/20
6/20 + = − = + = 给定方程组 ,试用最小二乘法求此 4 3 2 1 2 2 3 1 2 1 2 1 2 x x x x x x 方程组的近似解。 ( ) (2 2 3) ( 2 1) ( 4 4) , 2 1 2 2 1 2 2 令 f x = x1 + x2 − + x − x − + x + x − 则原问题化为 min2 f (x) 。 xE 记 ， = = = − 313 , , 1 4 1 2 2 2 21 b xx A x 则 f (x) = (Ax − b)T (Ax − b)。 例1 解 , 6 24 6 6 A A = T ， = 16 10 A b T x A A A b T 1 T * ( )− = 。 = 3134
三、非线性最小二乘法m(P)min f(x)=rT(x)r(x)= Er?(x)XeEni=1其中r(x)=(r(x), r(x),.., rm(x)T, xe E"是x的非线性函数。非线性最小二乘问题是无约束最优化的特殊情形，由于目标函数有特殊结构，因此可以对一股无约束最优化方法进行改造，得到一些更有效的特殊方法7/20
7/20 三、非线性最小二乘法 = = = m i i T x E P f x r x r x r x n 1 2 （ ） min ( ) ( ) ( ) ( ) 是 的非线性函数。 其 中 （ ， ， ， ， x r x r x r x r x x E n = m T 1 2 ( ) ( ) ( ) ( )) 非线性最小二乘问题是无约束最优化的特殊情 形，由于目标函数有特殊结构，因此可以对一 般无约束最优化方法进行改造，得到一些更有 效的特殊方法
f(x)的梯度为mg(x) = Vf(x)=2Zr; (x)Vr; (x) = 2J(x) r(x)i1Oror其中axOxn称为r(x)的Jacobi矩阵J(x) =·Ormormaxaxf(x)的Hessian矩阵为mG(x) =2E(Vr; (x)Vr; (x)T +r; (x)V'r; (x)i=1m其中S(x)=Zr; (x)V’r; (x)= 2[J(x) J(x) + S(x)li=18/20
8/20 其中 = n m m n x r . x r x r . x r J x 1 1 1 1 ( ) f (x)的梯度为 g(x) = f (x) = = m i i i r x r x 1 2 ( ) ( ) 2J(x) r(x) T = f (x)的Hessian矩阵为 = = + m i i i T i i G x r x r x r x r x 1 2 ( ) 2 ( ( ) ( ) ( ) ( )) 2[J(x) J(x) S(x)] T = + = = m i i i S x r x r x 1 2 其 中 ( ) ( ) ( ) 称为r(x)的Jacobi矩阵
从而，解问题（P）的牛顿法为：xk+1 = xk - [J(xh) J(x*)+ S(x*)}-1 J(x*)r(x*)小在标准假设下，该牛顿法具有局部二阶收敛性：存在的问题：Hessian矩阵中的二阶信息项S(x)通常难以计算或者花费的工作量很大。采取措施：或者忽略S(x)，或者用一阶导数信息逼近S(x)，以简化计算，获得有效的算法。Gauss-Newton 法------忽略S(x)x*+1 =xh - [J(x*) J(x*)}"J(x*)r(x*)X9/20
9/20 从而，解问题（P）的牛顿法为： 2[ ( ) ( ) ( )] ( ) ( ) k 1 k k T k k 1 k T k x x J x J x S x J x r x + − = − + 在标准假设下，该牛顿法具有局部二阶收敛性； 存在的问题： Hessian矩阵中的二阶信息项 S(x)通常难以计算或者花费的工作量很大。 采取措施： 或者忽略S(x)，或者用一阶导数 信息逼近S(x)，以简化计算，获得有效的算法。 Gauss-Newton 法-忽略S(x) 2[ ( ) ( )] ( ) ( ) k 1 k k T k 1 k T k x x J x J x J x r x + − = −
由于牛顿法在标准假设下是局部二阶收敛的，因此Gauss-Newton法的成功将依赖于所忽略的G(x)中的二阶信息项S(x)在G(x)中的重要性。可以证明：如果S(x*)=O，则Gauss-Newton法也是二阶收敛的。如果S(x*)相对于J(x*)T J(x*)是小的，则Gauss-Newton法是局部Q线性收敛的。如果S(x*)太大，则Gauss-Newton法可能不收敛。10/20
10/20 由于牛顿法在标准假设下是局部二阶收敛的，因此， Gauss-Newton 法的成功将依赖于所忽略的G(x)中 的二阶信息项S(x)在G(x)中的重要性。 可以证明： 如果S(x * )=0， 则Gauss-Newton 法也是 二阶收敛的。 如果S(x * )相对于J(x*) T J(x*) 是小的，则 Gauss-Newton 法是局部Q线性收敛的。 如果S(x * )太大，则Gauss-Newton 法可 能不收敛