最优化方法及其Matlab程序设计 第七章非线性最小二乘问题 Back Close
1/33 JJ II J I Back Close Å`zê{9Ÿ Matlab ßSO 1‘Ÿ öÇ5ŶØK
非线性最小二乘问题是科学与工程计算中十分常见的一类问题， 并在经济学等领域有广泛的应用背景.不但如此，约束优化问题还可 以通过KKT条件与非线性方程组建立起重要的关系.本章，我们主要 讨论非线性最小二乘问题的一些求解算法及其收敛性质 §7.1 Gauss-Newton法 非线性最小二乘问题是求向量x∈R”使‖F(x)川2最小，其中，映 射F:R”→Rm是连续可微函数.非线性最小二乘问题在工程设计、 财政金融等方面的实际问题中有着广泛的应用 记F(c)=(F(c),2(x),·,Fm(c)T.则非线性最小二乘问题可 以表示为 盟fi)=FeP-专∑r (7.1) Back Close
2/33 JJ II J I Back Close öÇ5ŶØK¥âÆÜÛßOé•õ©~ÑòaØK, ø3²LÆ +çk2çA^µ. ÿXd, Â`zØKÑå ±œL KKT ^áÜöÇ5êß|Ô·Âá'X. Ÿ, ·ÇÃá ?ÿöÇ5ŶØKò ¶)é{9Ÿ¬Ò5ü. §7.1 Gauss-Newton { öÇ5ŶØK¥¶ï˛ x ∈ Rn ¶ kF(x)k 2 Å, Ÿ•, N F : Rn → Rm ¥ÎYåáºÍ. öÇ5ŶØK3ÛßO! „7K ê°¢SØK•kX2çA^. P F(x) = (F1(x), F2(x), · · · , Fm(x))T . KöÇ5ŶØKå ±L´è min x∈Rn f(x) = 1 2 kF(x)k 2 = 1 2 X m i=1 F 2 i (x). (7.1)
显然，该问题本身就是一个无约束优化问题，因此可以套用无约束优 化问题的数值方法如牛顿法、拟牛顿法等方法求解。基于问题（⑦1） 的特殊性，我们在这些优化算法的基础上，建立更适合本类问题的求 解算法 对于问题(7.1)，目标函数f的梯度和Hesse阵分别为： Vfa-V(r(训P）-rrd)-∑r(Vr(. Gpey-iaivkiar+siappe =J(x)TJ(x)+F(x)V2Fi() J(x)J(x)+S(x), Back Close
3/33 JJ II J I Back Close w, TØK “¥òáÃÂ`zØK, œdå±@^ÃÂ` zØKÍäê{X⁄Ó{
其中 J()=F(a)=(VF(x),.,VEm(a))T,S()=>F(a)V2F:(a). 1=1 利用牛顿型迭代算法，我们便得到求解非线性最小二乘问题的迭代算 法 Tk+1=k-(J+Sk)F(k). 在标准假设下，容易得到该算法的收敛性质.缺点是S(x)中VF(x) 的计算量较大.如果忽略这一项，便得到求解非线性最小二乘问题的 Gauss-.Newton迭代算法： Tk+I=k+dew, 其中 dN=-[及J]JRF(cx) Back Close
4/33 JJ II J I Back Close Ÿ• J(x) = F 0 (x) = (∇F1(x), · · · , ∇Fm(x))T , S(x) = X m i=1 Fi(x)∇2Fi(x). |^⁄Ó.Sìé{, ·ÇB¶)öÇ5ŶØKSìé {: xk+1 = xk − J T k Jk + Sk −1 J T k F(xk). 3IObe, N¥Té{¬Ò5ü. ":¥ S(x) • ∇2Fi(x) Oé˛å. XJ—˘òë, B¶)öÇ5ŶØK Gauss-Newton Sìé{: xk+1 = xk + d GN k , Ÿ• d GN k = − J T k Jk −1 J T k F(xk)
称为Gauss-Newton方向.容易验证d是优化问题 02F)+d? 的最优解.若向量函数F(x)的Jacobian矩阵是列满秩的，则可以保 证Gauss-Newton方向是下降方向.如同牛顿法一样，若采取单位步长， 算法的收敛性难以保证.但如果在算法中引入线搜索步长规则，则可 以得到如下的收敛性定理 定理7.1设水平集C(xo)有界，J(x)=F(x)在C(xo)上Lipschitz 连续且满足一致性条件 IJ(x)y≥alyl,Hy∈Rn, (7.2) 其中，a>0为一常数.则在Volfe步长规则下 f(k+axdk)<f+o1akgidk, (7.3) g(xk+adk)Tdk≥o2g呢d, Back Close
5/33 JJ II J I Back Close °è Gauss-Newton êï. N¥y d GN k ¥`zØK min d∈Rn 1 2 kF(xk) + Jkdk 2 Å`). eï˛ºÍ F(x) Jacobian › ¥˜ù, Kå± y Gauss-Newton êï¥e¸êï. X”⁄Ó{ò, eʸ†⁄, é{¬Ò5J±y. XJ3é{•⁄\Ç|¢⁄5K, Kå ±Xe¬Ò5½n. ½n 7.1 Y²8 L(x0) k., J(x) = F 0 (x) 3 L(x0) ˛ Lipschitz ÎYÖ˜vòó5^á kJ(x)yk ≥ αkyk, ∀ y ∈ R n , (7.2) Ÿ•, α > 0 èò~Í. K3 Wolfe ⁄5Ke f(xk + αkdk) ≤ fk + σ1αkg T k dk, g(xk + αkdk) T dk ≥ σ2g T k dk, (7.3)