《数值最优化方法》课程教学课件（讲稿，打印版）最小二乘问题

最优化方法及其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⁄Ó{![⁄Ó{ê{¶). ƒuØK (7.1) Aœ5, ·Ç3˘ `zé{ƒ:˛, Ô·ç·‹aØK¶ )é{. ÈuØK (7.1), 8IºÍ f F›⁄ Hesse ©Oè: g(x) , ∇f(x) = ∇ 1 2 kF(x)k 2  = J(x) TF(x) = X m i=1 Fi(x)∇Fi(x), G(x) , ∇2 f(x) = X m i=1 ∇Fi(x)(∇Fi(x))T + X m i=1 Fi(x)∇2Fi(x) = J(x) T J(x) +X m i=1 Fi(x)∇2Fi(x) , J(x) T J(x) + S(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)

其中00使得对任意x∈C(xo),‖J(x)川≤B成 立.记0k为Gauss-Newton方向dW与负梯度方向-gk的夹角.利用 一致性条件(7.2)，我们有 grdgN F JdGN cos 0= llgkllldenl 川ENJF ‖JdeN2 、a2lv2 a2 ldeN JdgNl T之2IgNp=>0. 由于g(x)在C(xo)上Lipschitz连续，则由(7.3)的第二式得 (o2-1)gkdk≤[g(ck+a%d)-9Td4≤aLd2. Back Close

6/33 JJ II J I Back Close Ÿ• 0 0 ¶È?ø x ∈ L(x0), kJ(x)k ≤ β § ·. P θk è Gauss-Newton êï d GN k ÜKF›êï −gk Y. |^ òó5^á (7.2), ·Çk cos θk = − g T k d GN k kgkkkd GN k k = − F T k Jkd GN k kd GN k kkJ T k Fkk = kJkd GN k k 2 kd GN k kkJ T k Jkd GN k k ≥ α 2kd GN k k 2 β 2kd GN k k 2 = α 2 β 2 > 0. du g(x) 3 L(x0) ˛ Lipschitz ÎY, Kd (7.3) 1™ (σ2 − 1)g T k dk ≤ [g(xk + αkdk) − gk] T dk ≤ αkLkdkk 2

故 a% 02-1 gfdk L ldx2 将其代入(7.3)的第一式得 f-k1≥-1afd4≥mL 1-02(gdk)2 gl cos0 =01L 两边对k求级数，利用{f}单调不增有下界，得到 ●X 2aac 由此可得 lim g lim J()F(k)=0. k>o k→0∞ 证毕 Back Close

7/33 JJ II J I Back Close  αk ≥ σ2 − 1 L g T k dk kdkk 2 . ÚŸì\ (7.3) 1ò™ fk − fk+1 ≥ −σ1αkg T k dk ≥ σ1 1 − σ2 L (g T k dk) 2 kdkk 2 = σ1 1 − σ2 L kgkk 2 cos2 θk. ¸>È k ¶?Í, |^ {fk} ¸NÿOke.,  X ∞ k=1 kgkk 2 cos2 θk < ∞. ddå lim k→∞ gk = lim k→∞ J(xk) TF(xk) = 0. y.

定理7.2设单位步长的Gauss-Newton算法产生的迭代点列{ck} 收敛到(71)的局部极小点x*,而且J(x*)TJ(x)正定.则当J(z)TJ(x), S(x),[J(x)1J(c)]-1在x*的邻域内Lipschitz连续时，对充分大的k, 有 ck+1-x*‖≤l[J(e*)TJ(x*】厂llS(x*）川xk-x*‖+O(2ck-x*2). 证明由于J(x)TJ(x),S(x),[J(x)TJ(x)】-1在x*的邻域内Lipschitz 连续，故存在6>0及正数α，B,y使得对任意x,y∈N(x*,0)有， IS(z)-S()l≤ax-y IJ(x)TJ(x)-J(y)TJ(y)川≤lx-y, (7.4) l[J(x)J(x-1-[J(y)J(y]-‖≤ylx-y. 由于f(x)二阶连续可微，G(x)=J(x)J(x)+S(x)在N(x*,δ)上 Lipschitz连续，故对充分大的k和模充分小的h∈R”,有xk+h∈ Back Close

8/33 JJ II J I Back Close ½n 7.2 ¸†⁄ Gauss-Newton é{)Sì: {xk} ¬Ò (7.1) ¤‹4: x ∗ , Ö J(x ∗ ) T J(x ∗ ) ½. K J(x) T J(x), S(x), [J(x) T J(x)]−1 3 x ∗ çS Lipschitz ÎYû, Èø©å k , k kxk+1 − x ∗ k ≤ k[J(x ∗ ) T J(x ∗ )]−1 kkS(x ∗ )kkxk − x ∗ k + O(kxk − x ∗ k 2 ). y² du J(x) T J(x), S(x), [J(x) T J(x)]−1 3 x ∗ çS Lipschitz ÎY, 3 δ > 0 9Í α, β, γ ¶È?ø x, y ∈ N(x ∗ , δ) k,    kS(x) − S(y)k ≤ αkx − yk kJ(x) T J(x) − J(y) T J(y)k ≤ βkx − yk, k[J(x) T J(x)]−1 − [J(y) T J(y)]−1k ≤ γkx − yk. (7.4) du f(x) ÎYåá, G(x) = J(x) T J(x) + S(x) 3 N(x ∗ , δ) ˛ Lipschitz ÎY, Èø©å k ⁄ø© h ∈ Rn , k xk + h ∈

N(x*,6),且 g(k+h)=g(k)+G(Zk)h+O(lh2). (7.5) 由于xk→x*,对充分大的k,有xk,Tk+1∈N(x*,δ).令ek=xk一x*, hk=xk+1-xk,则 g(x*)=g(xk-ek)=0. 利用(7.5)， g(k)-G(Zk)ex:+O(llekl2)=0. 即 F-(J+S)ek+O(llekl2)=0. 注意到JF=-(JJ)(xk+1-x)=-JJhk.两边同乘(JJ)-1, -hk-ek-()Skek+(J-O(llekl2)=0. Back Close

9/33 JJ II J I Back Close N(x ∗ , δ), Ö g(xk + h) = g(xk) + G(xk)h + O(khk 2 ). (7.5) du xk → x ∗ , Èø©å k , k xk, xk+1 ∈ N(x ∗ , δ). - ek = xk − x ∗ , hk = xk+1 − xk, K g(x ∗ ) = g(xk − ek) = 0. |^ (7.5), g(xk) − G(xk)ek + O(kekk 2 ) = 0. = J T k Fk − (J T k Jk + Sk)ek + O(kekk 2 ) = 0. 5ø J T k Fk = −(J T k Jk)(xk+1 − xk) = −J T k Jkhk. ¸>”¶ (J T k Jk) −1 , −hk − ek − (J T k Jk) −1Skek + (J T k Jk) −1O(kekk 2 ) = 0

所以 k+1-x*=hk+ek=-(J)Skek+(JJ)O(llek2) 两边取2范数， l+1-x*‖≤Il(JRJ)-1 Sek‖+I(JgJ)1‖·O(Ilex2). 由于[J(x)TJ(x)-1在x*处连续，故在k充分大时， I(JJk)-‖≤2[J(x*)J(x*)]- (7.6) 从而 lx+1-x‖≤I(JJ)-1 Sk-x*‖+O(xk-x*2). (7.7） Back Close

10/33 JJ II J I Back Close §± xk+1 − x ∗ = hk + ek = −(J T k Jk) −1Skek + (J T k Jk) −1O(kekk 2 ). ¸> 2 âÍ, kxk+1 − x ∗ k ≤ k(J T k Jk) −1Skkkekk + k(J T k Jk) −1 k · O(kekk 2 ). du [J(x) T J(x)]−1 3 x ∗ ?ÎY, 3 k ø©åû, k(J T k Jk) −1 k ≤ 2k[J(x ∗ ) T J(x ∗ )]−1 k. (7.6) l kxk+1 − x ∗ k ≤ k(J T k Jk) −1Skkkxk − x ∗ k + O(kxk − x ∗ k 2 ). (7.7)