最優(yōu)化理論 第七章 非線性最小二乘問(wèn)題

§7.1最小二乘問(wèn)題1（回歸方程問(wèn)題）設(shè)(titi,tiyi)T（i12,m）m個(gè)實(shí)驗(yàn)點(diǎn).現(xiàn)要根據(jù)12 ly與l個(gè)物理量t1,t2,,tl之間的關(guān)系式.yF(t1,t2,,tlx1x2,xnx1x2,xnn個(gè)待定參數(shù)(系數(shù)).因此問(wèn)題是如何通過(guò)m(mn個(gè)實(shí)驗(yàn)點(diǎn)，確定方程中的系數(shù).由于實(shí)驗(yàn)點(diǎn)問(wèn)題的方法進(jìn)行求解.一個(gè)合理的解決方法是將這些實(shí)驗(yàn)點(diǎn)到曲面距離最短的那個(gè)曲面作為所求曲面，從而求取該曲面方程.即求解無(wú)約束最優(yōu)化問(wèn)題mminxRni1

Fti,x)yi2，.（非線性方程組求解問(wèn)題）F1(x1,x2,,xn)0,F(x,x,,x)0,2 1 2 n............................m(1,2,,n)0可等價(jià)地轉(zhuǎn)化為求解無(wú)約束最優(yōu)化問(wèn)題mminF2(x,x,,x)，mxRn

i 1 2 ni1.m小于變量的個(gè)數(shù)nm等于變量的個(gè)數(shù)nm大于變量的個(gè)數(shù)n，則稱其為超定問(wèn)題.iinf(x)1r(x)Tr(x)1mi

r2(x), (7.1.1)xRn

2 2i1r(x)稱為殘量函數(shù)，i12,m.r(x)是仿射函數(shù)，即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當(dāng)某個(gè)ri(x是非仿射函數(shù)時(shí)，1i0m，則稱(7.1.1)為非線性最小二乘問(wèn)題.0n.但由于最小二乘問(wèn)題具有一定的特殊性，即目標(biāo)函數(shù)的表達(dá)式是由多個(gè)表達(dá)式的平方和組成，理應(yīng)有更簡(jiǎn)單、更有效的方法.這正是最小二乘解法要解決的問(wèn)題.§7.2 線性最小二乘問(wèn)題的解法由(7.1.2)可知，線性最小二乘問(wèn)題可寫成minf(x)1||Axb||21xTATAxbTAx1bTb， (7.2.1)xRn

2 2 2nATAf(x)1xTATAxbTAx1bTb是二次凸函數(shù).2 2x*為無(wú)約束最優(yōu)化問(wèn)題minf(xx*為xRn線性方程組ATAxATb0

(7.2.2)的解.由于二次凸函數(shù)必定有極小點(diǎn)，故線性方程組(7.2.2)必定可解. 事實(shí)上，若x*為minf(xf(x)x*滿足(7.2.2)x*是(7.2.2)的xRnxRnf(xx*處Taylor展開(kāi)，即有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)為最小二乘問(wèn)題(7.2.1)（Axb0）的法方程組或正.A必須列滿秩.對(duì)于通常系數(shù)矩陣是對(duì)稱矩陣的線性方程組，我們一般采用先將其系數(shù)矩陣進(jìn)行CholeskyLLTL是下三角矩陣，然后通過(guò)前代和回代求.增大了舍入誤差.針對(duì)法方程組(7.2.2)的特殊結(jié)構(gòu)，我們采用如下更為有效的求解方法.mnA列滿秩.我們首先對(duì)線性方程Axb0的增廣矩陣AbQR分解，設(shè)ARQ Q1QR，A bQR bQR b，O1 2 11O

11 1其中QmQ1是由Q的前nQ2是由Q的后mn列構(gòu)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個(gè)分量構(gòu)成的n維向量. 與方程組

(7.2.3)同解.R1為n階上三角矩陣，故線性方程組(7.2.3)通過(guò)簡(jiǎn)單回代就可以求解.線性最小二乘問(wèn)題的正交分解法）1n步1：對(duì)增廣矩陣A b進(jìn)行QR分解，得到R和b1n

1QTb；12R1xbn0，得線性最小二乘問(wèn)題(7.2.1)x*.§7.3Gauss-Newton法對(duì)于非線性最小二乘問(wèn)題inf(x)1r(x)Tr(x)1m

ir2(x). (7.3.1)ixRn

2 2i1記向量值函數(shù)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的計(jì)算量很大.x*處一般滿足ri(x*0（稱為零殘量問(wèn)題（，i,,,m，Hesn7.3.3J(x)TJ(x是Hessian矩陣2f(x)的比較好的近似，而且容易計(jì)算.為此，把牛頓方程改造為J(xk)TJ(xk)dJ(xk)Tr(xk)， (7.3.4)由(7.3.4)解出目標(biāo)函數(shù)的搜索方向dk，然后令xk1xkdk，Guass-Newton法.iir(xxk處線性化，然后用線性最小二乘問(wèn)題的解去逼近非線性最小二乘問(wèn)題的解.將r(xxk處Taylor一階展開(kāi)，有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法的構(gòu)造可知，對(duì)于零殘量問(wèn)題和小殘量問(wèn)題具有較好的局部收斂效中等式右端的第二項(xiàng)比第一項(xiàng)相對(duì)來(lái)的大時(shí)就有可能不收斂.mM(x)J(x)TJ(xR(x)r(x)2r(x).i ii 定理7.3.1設(shè)f(x)1r(x)Tr(x在開(kāi)凸集D上二階連續(xù)可微，存在x*D使得2f(x*0.xDJ(x)列滿秩，且存在正常數(shù)和xD，有||J(x||||M(x)1||.如果J(x)2f(x)均在D上Lipschitz連續(xù)，則Guass-NewtonxD有定義，且||xk1x*||||M(x*)1R(x*)||||xkx*||O(||xkx*||2). (7.3.5)J(xM(x)J(x)TJ(x正定，因此，Guass-Newton迭代對(duì)任意xD都有定義.對(duì)任意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||對(duì)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常數(shù).由此得||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*||較大）的問(wèn)題.（2）如果定理中的條件成立，且||M(x*)1R(x*||1，則Guass-Newton法具有局部收斂性，特別地，當(dāng)||R(x*||0時(shí)，算法具有局部二階收斂速率.J(xk)TJ(xk奇異時(shí)，由(7.3.4)dk不一定是下降方向，類似于牛頓法的修.dkf(xkdk)

f(xk)，因此，我們可以通過(guò)增加線搜索步驟來(lái)保證目標(biāo)函數(shù)的下降，即采用阻尼Guass-Newton法.§7.4Levenberg-Marquardt法Guass-Newton法并不能J(xk)TJ(xk奇異時(shí)，由(7.3.4)解出來(lái)的dk不一定是目標(biāo)函f(x的下降方向.針對(duì)這種缺陷，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）解出來(lái)的dkf(x)xk處的下降方向.事實(shí)上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法曾經(jīng)被稱為阻尼最小二乘法.事實(shí)上，Levenberg-Marquardt法是一類信賴域方法.7.4.1若dk是方程(7.4.1)0的解，則也是信賴域問(wèn)題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而對(duì)任意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因此，對(duì)任意滿足||d||||dk||d，有q(d)q(dk)1(dkd)TJ(xk)TJ(xk)(dkd)[(dk)TdkdTdk]k k 21(dkd)TJ(xk)TJ(xk)(