最優(yōu)化理論與算法(第三章)

1、第三章 牛頓法3.1 最速下降法一、最速下降法在極小化算法中，若每次都以迭代點(diǎn)處的負(fù)梯度方向?yàn)樗阉鞣较?，產(chǎn)生的算法稱為最速下降法，它是無(wú)約束最優(yōu)化算法中最簡(jiǎn)單、最基本的算法。算法描述：1） 給出初始點(diǎn)，允許誤差，；2） 計(jì)算，若，Stop 令 ；3） 由一維搜索確定步長(zhǎng)因子，使得 4） 令，go to 2).二、最速下降算法的收斂性定理3.1 設(shè)，則最速下降算法產(chǎn)生的點(diǎn)列的每個(gè)聚點(diǎn)均為駐點(diǎn)。證明：設(shè)是的一個(gè)聚點(diǎn)，則存在子序列，使得 令，由，知是收斂序列，故有界，且 由定理2.6有 故有 。定理3.2 設(shè)二次連續(xù)可微，且，則對(duì)任何給定的初始點(diǎn)，最速下降算法或有限終止，或，或。證明：不妨設(shè)，。由定

2、理2.5有 于是 令，由為單調(diào)下降序列，則要么，要么 。最速下降算法若采用不精確一維搜索，仍有下列總體收斂性定理。定理3.3 設(shè)，則采用不精確一維搜索得到的點(diǎn)列的每個(gè)聚點(diǎn)均為駐點(diǎn)。證明：直接由定理2.14可得。注：1) 最速下降算法的收斂性也可由前述關(guān)于模式算法收斂性結(jié)果定理2.7直接獲得；2）最速下降算法的主要優(yōu)點(diǎn)是方法簡(jiǎn)單、直觀，有好的總體收斂性，但收斂很慢。三、最速下降算法的收斂速度1. 先考慮二次函數(shù)情形定理3.4 對(duì)極小化問(wèn)題，其中為對(duì)稱正定矩陣，分別為的最大與最小特征值。設(shè)是最優(yōu)解，則最速下降算法的收斂速度至少是線性的，且下面的界成立：，其中（為矩陣的條件數(shù)）。證明：由，有。故其中

3、使 ， 若設(shè) ， 其中。則有 ，而， 利用這些，可知 ， （要求） 設(shè)是的特征值，而是對(duì)應(yīng)得標(biāo)準(zhǔn)特征向量（兩兩正交的單位向量）。令，則上式可進(jìn)一步表示為： （將作用到內(nèi)每一項(xiàng)） （由是標(biāo)準(zhǔn)正交向量組）對(duì)，可適當(dāng)選取，使。事實(shí)上，只須令即可求得 從而 。顯然單調(diào)上升。由，及，即得。由 及 即得 . 再由 最后得 .由，并注意到是正定二次函數(shù)（）， 則有。再由為嚴(yán)格凸二次函數(shù)（正定二次型），故當(dāng)且僅當(dāng)時(shí)，由此可推得必有 . 再注意到，則有從而定理第一式得證。下面再證定理第二式，記，。由是對(duì)稱正定的，故有由，則 故有 ， 注意到： 因而有 最后得 （其中）。 這表明：最速下降算法至少具有線性收斂速度

4、。定理3.5（Kantorovich不等式）設(shè)是階對(duì)稱正定矩陣，和分別為其最大和最小特征值，則，有。證明：參見袁亞湘等最優(yōu)化理論與方法第三章附錄，略。 以上對(duì)特殊形式的二次函數(shù)的收斂速度進(jìn)行討論，對(duì)一般的二次函數(shù)利用Kantorovich不等式可得類似的結(jié)論，其證明思路如下：設(shè)是極小點(diǎn)，則滿足且可表示為 記 ，則與僅相差一個(gè)常數(shù)，它們有相同的最優(yōu)解，且使用最速下降算法時(shí)，每次迭代方向產(chǎn)生的迭代序列均完全相同?，F(xiàn)在考察對(duì)的極小化，這時(shí)最速下降算法的迭代公式為： （這里為最優(yōu)步長(zhǎng)因子）其中。直接計(jì)算可得：（由Kantorovich不等式）故有： （1）由（1）即得： （或）。由正定，當(dāng)且僅當(dāng)時(shí)，利

5、用一致凸性，可證必有：。這表明：算法產(chǎn)生的點(diǎn)列是整體收斂到的。由（1）有： （2）注意到： ，由（2）有 （3）再令（），則，注意到即有： ，從而有： ，（令）最后得： ，定理證畢。當(dāng)目標(biāo)函數(shù)為非二次函數(shù)時(shí)，最速下降算法的收斂速度依然是線性的。定理3.6 設(shè)滿足定理2.8的假設(shè)條件，若最速下降算法產(chǎn)生的點(diǎn)列收斂于，則收斂速度至少是線性的。3.2 牛頓法一、牛頓算法的基本思路牛頓算法的基本思路是：利用目標(biāo)函數(shù)在當(dāng)前迭代點(diǎn)處的二次近似的極小點(diǎn)作為的近似極小點(diǎn)。設(shè)是當(dāng)前迭代點(diǎn)，正定，則記 ，其中，極小化得進(jìn)而得牛頓算法的迭代公式: .關(guān)于牛頓算法的若干評(píng)注 牛頓算法可視為橢球范數(shù)下的最速下降算法。

6、事實(shí)上，歐氏空間中一般范數(shù)下的方向?qū)?shù)定義為： （它顯然與范數(shù)有關(guān)）顯然，的最優(yōu)解就是函數(shù)在處對(duì)應(yīng)于范數(shù)的最速下降方向。容易理解，這個(gè)解與所取的范數(shù)有關(guān)。a) 當(dāng)取歐氏范數(shù)（2范數(shù)）時(shí)，可證是最速下降方向；b) 若取橢球范數(shù)，最速下降方向則為。事實(shí)上，即 ，有（意味著為方向?qū)?shù)下界）另一方面，若取時(shí)方向?qū)?shù)達(dá)到下界，故是對(duì)于橢球范數(shù)的最速下降方向。 牛頓算法實(shí)際上就是非線性方程組的牛頓迭代法。由于等價(jià)于求解非線性方程組 設(shè)是當(dāng)前迭代點(diǎn)，若，則是方程組的解，否則將在處線性化，得 將上述線性方程組的解作為 的近似解，得 故有 ，這恰好就是牛頓迭代公式。二、牛頓法的收斂性定理3.7 設(shè)，充分靠近極小

7、點(diǎn)，而，正定，若進(jìn)一步假設(shè)Hessian矩陣滿足Lipschitz條件。則由牛頓法產(chǎn)生的序列收斂于，且具有二階的收斂速度。證明：由 及滿足Lipschitz條件，可得故有 （*）由于，正定，故當(dāng)充分靠近時(shí)，正定，且有上界。事實(shí)上，設(shè)是的特征值，且最大，最小，則的特征值為，且，（這里矩陣范數(shù)取譜范數(shù)）。又特征值是特征多項(xiàng)式系數(shù)的連續(xù)函數(shù)（參見蔣爾雄線性代數(shù)P39定理10），故當(dāng)時(shí)，存在m, M使得 ， （相當(dāng)于特征值一致有界）因而當(dāng)時(shí) （這里分別表示的最小、最大特征值）。由以上分析及（*）式，則有 （*）只要，則有，即，迭代點(diǎn)列收斂，且由（*）式知，算法具有二階收斂的速度。 關(guān)于算法的評(píng)價(jià)1）優(yōu)

8、點(diǎn)：當(dāng)初始點(diǎn)離最優(yōu)解很近時(shí)，收斂速度快；算法簡(jiǎn)單；不需要用一維搜索。2) 缺點(diǎn)：局部收斂，不正定時(shí)，不能保證牛頓方向是下降方向。事實(shí)上，當(dāng)為正定時(shí)，牛頓方向滿足：（下降方向），但若非正定，則不能保證是下降方向。由以上分析可知，固定的步長(zhǎng)因子不能保證目標(biāo)函數(shù)有合理的改善，甚至不能保證算法下降，因此有必要對(duì)牛頓算法作一些改進(jìn)，一個(gè)最直接的改進(jìn)是：在牛頓算法中加入一維搜索。三、帶步長(zhǎng)因子的牛頓法阻尼牛頓法1算法1）取初始點(diǎn)，允許誤差，置；2）計(jì)算，若，停止迭代，；否則 go to 3)；3) 構(gòu)造牛頓方向：從求出；4）沿進(jìn)行一維搜索，使得滿足：；5）令， 轉(zhuǎn)2）。2總體收斂性定理3.8 設(shè)二階連續(xù)可

9、微，且對(duì)任意的，存在常數(shù)，使得在水平集上滿足， ，則在精確一維搜索條件下，帶步長(zhǎng)因子的牛頓法產(chǎn)生的迭代點(diǎn)列滿足：1） 當(dāng)為有窮點(diǎn)列時(shí)，對(duì)某個(gè)，有；2） 當(dāng)為無(wú)窮點(diǎn)列時(shí)，收斂到的唯一極小點(diǎn)。證明：由定理?xiàng)l件知，在上一致凸。故在中若有極小點(diǎn)，則必唯一，且在中的穩(wěn)定點(diǎn)必是的極小點(diǎn)。下證收斂到的穩(wěn)定點(diǎn)。由在上一致凸，知是有界閉凸集，再由單調(diào)下降，可知，故是有界點(diǎn)列，于是存在極限點(diǎn)及子列使.再由單調(diào)有界（有界性是由于：閉有界，且在上連續(xù)）可知： （這里是指整個(gè)序列）且 （這里是子序列）由精確一維搜索的極小化算法的收斂定理2.7，有 （整個(gè)序列） （*）從而 ，即是的穩(wěn)定點(diǎn)，它也是極小點(diǎn)?，F(xiàn)在實(shí)際上還只證

10、明了的子序列收斂到，下證整體收斂到。事實(shí)上，若不收斂到，則存在一個(gè)子序列使（，是給定的正數(shù)）注意到是有界點(diǎn)列，故存在收斂子列 ，使 （由閉有界）從而 由（*）式進(jìn)一步得 從而也是的平穩(wěn)點(diǎn),也是極小點(diǎn)，但顯然，這與的極小點(diǎn)唯一矛盾，故必有 。在上面證明過(guò)程中，直接引用了精確一維搜索的極小化算法的收斂定理2.7，因此必須指出定理2.7的條件是滿足的。事實(shí)上，1）由有界閉，故在上一致連續(xù)，且；2）由 得：。3.3 修正的牛頓法 上面帶步長(zhǎng)因子的牛頓法實(shí)際上還不能克服牛頓算法的全部缺陷，因?yàn)檫€有可能出現(xiàn)：1) 不存在；2）不正定，故可能不是下降方向。為此人們對(duì)牛頓法提出了多種方式的修改。一、Golds

11、teinPrice修正方案當(dāng)非正定時(shí)，采用最速下降方向替代牛頓方向。若進(jìn)一步將搜索方向與負(fù)梯度方向的角度準(zhǔn)則結(jié)合起來(lái)，則有這樣搜索方向總滿足注：按照這種方法選取搜索方向，再加上一維搜索（精確或非精確）可以保證算法的總體收斂性，但也可能失去牛頓法快速收斂的特點(diǎn)。 二、Goldfeld修正方案若不正定，則用來(lái)修正。通過(guò)適當(dāng)選取，可以使正定。事實(shí)上，只要將取得稍大于的最小特征值的模即可。利用特征值的圓盤定理可以求得最小特征值的模： 注：用此方法可求出，但通常得到的遠(yuǎn)大于最小特征值的模，導(dǎo)致與相差甚遠(yuǎn)，這是一個(gè)缺陷。而實(shí)際求出的全部特征值計(jì)算量又太大，因此，這個(gè)方法更多的是理論的價(jià)值。 三、基于的Ch

12、olesky分解的方案先作的Cholesky分解 然后令 ，其中而，為中對(duì)角元，為給定的小正數(shù)。注：這種處理方法簡(jiǎn)單，但有下列缺陷：1） 當(dāng)不可逆或的主子式為零時(shí)，的Cholesky分解不存在（分解過(guò)程將進(jìn)行不下去）。如， 其Cholesky分解不存在。2） 即使的分解存在，其計(jì)算過(guò)程也可能數(shù)值不穩(wěn)定。如，當(dāng)時(shí)，與均無(wú)界，計(jì)算過(guò)程中小的誤差會(huì)導(dǎo)致結(jié)果的巨大差別。因而數(shù)值不穩(wěn)定，同時(shí)還可能出現(xiàn)與的差別很大。如的Cholesky分解為， 由的處理方式得 可見與（從而與）相差甚遠(yuǎn)。四、Gill 和Murray修正方案GillMurray修正法也稱為強(qiáng)迫矩陣正定的Cholesky分解法，它在的分解過(guò)程

13、中進(jìn)行適當(dāng)修正，使總為正，從而分解過(guò)程可以持續(xù)下去，但最終得到的分解式不是真正的，而是的近似。其要點(diǎn)在于：1）在分解過(guò)程中，增加了保證分解得到的因子矩陣元素一致有界的措施。在過(guò)程完成時(shí)，得到： （其中是非負(fù)對(duì)角陣）2）在整個(gè)計(jì)算過(guò)程中，為了保證及因子矩陣元素一致有界，必須對(duì)的元素進(jìn)行調(diào)整，否則算法進(jìn)行不下去，但必須指出的是，所有調(diào)整都只涉及的對(duì)角元（通常是將其增大），這就保證了： ，即與僅差一個(gè)對(duì)角陣。3）可以證明，當(dāng)充分正定時(shí)，有?？蓞㈤喯倭刂蔷€性最優(yōu)化P80，或徐成賢等著近代優(yōu)化方法P62。定理3.9 設(shè)在上二階連續(xù)可微，且存在使為有界閉凸集，若初始點(diǎn)，則由GillMurray修正牛頓

14、法產(chǎn)生的點(diǎn)列滿足：1) 若是有限點(diǎn)列時(shí)，它的最后一個(gè)點(diǎn)必為的平穩(wěn)點(diǎn)；2) 若是無(wú)窮點(diǎn)列時(shí)，它必有聚點(diǎn)，且任一聚點(diǎn)均為的平穩(wěn)點(diǎn)。證明：參閱鄧乃揚(yáng)著無(wú)約束最優(yōu)化計(jì)算方法。注：一般.用到的GillMurray修改牛頓法除了強(qiáng)迫正定的Cholesky分解法外，在鞍點(diǎn)處還用到負(fù)曲率方向，因而它是一個(gè)對(duì)牛頓法改造的最徹底、最具有實(shí)用價(jià)值的方法。3.4 負(fù)曲率方向法一、負(fù)曲率方向負(fù)曲率方向法是修正牛頓法的又一種形式。當(dāng)不正定時(shí)，利用負(fù)曲率方向可找到下降方向，尤其在鞍點(diǎn)處，即： ， 而不是半正定時(shí)（當(dāng)然也不是正定的）此時(shí)若采用負(fù)曲率方向作為搜索方向，可以使目標(biāo)函數(shù)下降。定義3.10 設(shè)在開集上二階連續(xù)可微，1

15、）若至少有一個(gè)負(fù)特征值，則稱為不定點(diǎn)；2）設(shè)是一個(gè)不定點(diǎn)，若方向滿足：，則稱為在 處的負(fù)曲率方向； （若是負(fù)曲率方向，顯然也是）3）如果，則稱向量對(duì)為不定點(diǎn)處的下降對(duì)； 若不是一個(gè)不定點(diǎn)，則稱滿足：，的向量對(duì) 為點(diǎn)處的下降對(duì)。下降對(duì)的例子 令 ，其中是對(duì)應(yīng)于的負(fù)特征值的特征向量。注：1） 由定義可見：當(dāng)且僅當(dāng)，時(shí)，處不存在下降對(duì)。因此，一旦在該點(diǎn)不存在下降對(duì)，那么該點(diǎn)必滿足極小點(diǎn)的二階必要條件（但仍不一定是極小點(diǎn)）。2）若是鞍點(diǎn)，則負(fù)曲率方向必為下降方向。事實(shí)上，設(shè)為負(fù)曲率方向，由容易看出：當(dāng)很小時(shí)，。3）若為一般點(diǎn)，且負(fù)曲率方向滿足，則與均為下降方向。4）若，則是下降方向；若，則是下降方向。

16、由上述分析，一旦找到負(fù)曲率方向，則總存在一個(gè)下降方向。而唯一難找到下降方向的情形是：且時(shí)。二、Gill-Murray穩(wěn)定牛頓法基本思想：將修改Cholesky分解與負(fù)曲率方向相結(jié)合。當(dāng)不正定時(shí)，采用修改Cholesky分解強(qiáng)迫矩陣正定；而當(dāng)時(shí)，采用負(fù)曲率方向使函數(shù)值下降。1）負(fù)曲率方向的求法（與修改的Cholesky分解相聯(lián)系，計(jì)算相對(duì)容易）2）Gill-Murray穩(wěn)定牛頓法算法步驟（參閱袁亞湘等著最優(yōu)化理論與方法）。3）收斂性定理（證明參閱鄧乃揚(yáng)著無(wú)約束最優(yōu)化計(jì)算方法）。三、Fiacco-Mccormick方法Fiacco-Mccormick是最早利用負(fù)曲率方向修正牛頓法的學(xué)者，他們利用精

17、確一維搜索以及Cholesky分解。1）當(dāng)正定時(shí)，產(chǎn)生下降方向（牛頓方向）；2）當(dāng)不定時(shí)，通過(guò)求解，其中獲得 ，然后令，得負(fù)曲率方向（也是下降方向）。該方法的主要缺陷是：可能存在數(shù)值不穩(wěn)定，甚至分解不存在。四、二階Armijo步長(zhǎng)準(zhǔn)則Mccormick方法設(shè)是當(dāng)前迭代點(diǎn)，是下降方向?qū)?，迭代格式為：這不是沿一個(gè)方向進(jìn)行線搜索，也不是與的組合方向，而是一種曲線搜索策略。算法終止：不存在下降方向?qū)r(shí)，算法終止。此時(shí)，意味著且，故是一個(gè)滿足二階必要條件的點(diǎn)。若產(chǎn)生無(wú)窮點(diǎn)列，則在對(duì)下降方向?qū)Ω郊虞^強(qiáng)條件時(shí)，算法總體收斂。在該方法中使用的非精確步長(zhǎng)準(zhǔn)則實(shí)際上屬于簡(jiǎn)單步長(zhǎng)準(zhǔn)則，但不是Armijo一階準(zhǔn)則，而

18、是Armijo二階步長(zhǎng)準(zhǔn)則。令 求，它是使下式滿足的最小整數(shù)。令。五、二階Armijo步長(zhǎng)準(zhǔn)則Goldfarb方法設(shè)是當(dāng)前迭代點(diǎn)，是處的下降方向?qū)?。令這實(shí)際上是Mccormick方法的一種特殊形式。仍然采用Armijo簡(jiǎn)單步長(zhǎng)準(zhǔn)則，選擇最小的正整數(shù),使得，其中，與是預(yù)先給定的常數(shù)。六、二階Wolfe-Powell步長(zhǎng)準(zhǔn)則More-Sorensen方法形式：。采用非精確搜索確定步長(zhǎng)，步長(zhǎng)準(zhǔn)則采用Wolfe-Powell準(zhǔn)則的推廣形式，即所謂二階Wolfe-Powell準(zhǔn)則。關(guān)于上述內(nèi)容的詳細(xì)討論可參閱袁亞湘等著最優(yōu)化理論與方法的相應(yīng)章節(jié)。3.6 信賴域方法一、信賴域算法1牛頓法的基本思想 在當(dāng)前

19、迭代點(diǎn)附近用二次函數(shù)逼近，并以地極小點(diǎn)修正，得。如果不限定的范圍，實(shí)際上是用在全空間逼近，而用的極小點(diǎn)代替地極小點(diǎn)。容易理解，這樣得到的迭代點(diǎn)往往不能使有較大的改進(jìn)，有時(shí)不僅不能得到改進(jìn)，反而變得更糟。2信賴域方法的基本思想 信賴域方法是上世紀(jì)70年代提出的一種重要的優(yōu)化方法，它針對(duì)上面提及的牛頓方法的缺陷，在子問(wèn)題中，明確要求必須位于當(dāng)前迭代點(diǎn)的鄰域（信賴域）內(nèi)。在算法每次迭代中，求解下述信賴域子問(wèn)題：注: 1) 由于從信賴域子問(wèn)題求出的必須滿足，故稱為有限步長(zhǎng)方法；2）范數(shù)沒有特別限制，可根據(jù)需要隨意選取，但多數(shù)情形用或兩種范數(shù)；3）可用有限差分近似，也可用后面即將介紹的擬牛頓方法構(gòu)造其近

20、似。在信賴域算法中，信賴域半徑采用自適應(yīng)方式調(diào)整，若與近似程度好，則盡可能取大，否則將其縮小。而通常采用下述方式評(píng)價(jià)與的逼近程度：在算法迭代的第步，定義 稱實(shí)際下降量 稱預(yù)估下降量定義比值： 越接近1，表明近似程度好，應(yīng)加大，否則相反。3信賴域算法（算法模式）1）初始步：給出初始點(diǎn)，令2）第步：給出和，計(jì)算和 解信賴域模型（子問(wèn)題），求出 求和的值 如果，令 （縮減信賴域半徑） 如果且，令 （增大信賴域半徑） 否則，置 （信賴域半徑不變） 若，置；否則置。注：求解信賴域子問(wèn)題得到的稱為試探步。由可見，求出的試探步最后是否移動(dòng)，取決是否大于0。在有些信賴域算法中，將中的替換成了。二、信賴域算法的

21、收斂性定理3.11 設(shè)是中的一個(gè)有界集，信賴域算法產(chǎn)生的點(diǎn)列。若進(jìn)一步假設(shè)且在上滿足：。則存在一個(gè)滿足一階和二階必要條件的聚點(diǎn)。證明：由算法分析可知，算法產(chǎn)生的點(diǎn)列必存在一個(gè)子序列，要么滿足：1），（因而）；要么滿足 2），（表示相應(yīng)子列的下確界）。設(shè)是這樣子序列的任一聚點(diǎn)，并設(shè)，下面證明就是滿足定理要求的點(diǎn)。a) 若此序列滿足條件1）用反證法，設(shè)，對(duì)中的任何，考慮該點(diǎn)的最速下降方向，有1）當(dāng)時(shí)，注意到是信賴域子問(wèn)題的可行解，因而有 （*） 注意到且時(shí)，從而有 。故有 。2）當(dāng)時(shí)，由（*）式仍然有：故當(dāng)且時(shí)（此時(shí)），有 （由）再由Taylor展開式 進(jìn)而得： ，這與時(shí)，矛盾，從而有（即一階必要

22、條件滿足）。再證半正定。若不然，設(shè)是的最小特征值，則。設(shè)其對(duì)應(yīng)的單位特征向量為，且滿足（否則可?。ｏ@然是信賴域子問(wèn)題的可行解，故 從而有 （注意）再由Taylor公式， 得到 ，又與矛盾。從而是半正定的，即滿足極小點(diǎn)的一階和二階必要條件。b) 若子序列是第二種情形注意到下降算法的特點(diǎn)，有故級(jí)數(shù)收斂。因而 （*）對(duì)應(yīng)于，定義 并設(shè)滿足 又設(shè)是下述信賴域子問(wèn)題 的解。注意到時(shí)，因而滿足（）。從而 取，注意，以及，因而有。 （由（*）式，）這說(shuō)明也是的最優(yōu)解。注意到，此時(shí)約束不起作用。因而相當(dāng)于無(wú)約束問(wèn)題的極值。因而有，半正定，由此即知，半正定。即在處滿足一、二階必要條件。定理證畢。關(guān)于定理3.1

23、1中兩類子序列必出現(xiàn)一類的補(bǔ)充證明設(shè)算法產(chǎn)生的點(diǎn)列為，相應(yīng)的有序列與。1）若充分大時(shí)，均有，則顯然存在滿足第一類條件的子列；2）若充分大時(shí)，均有，則顯然存在滿足第二類條件的子列；因而下面僅考慮與總是相間出現(xiàn)的情形。這種情形下，必存在一個(gè)子序列，當(dāng)時(shí)，有（這里可取為使成立的指標(biāo)的全體）。若時(shí)，不大于零，則存在的一個(gè)子列使得 。再?gòu)闹腥缦聵?gòu)造子列：先選出的首項(xiàng)，設(shè)為；由于與總是相間出現(xiàn)。故必有，使，又一定有使得，對(duì)應(yīng)得到，仿此得到的一個(gè)子序列。顯然具有如下特點(diǎn)：1），有且；2）中任兩個(gè)相鄰項(xiàng)之間，必定存在一個(gè)指標(biāo)，使。設(shè)與是中相鄰兩項(xiàng)。是兩項(xiàng)對(duì)應(yīng)的下標(biāo)。設(shè)是從出發(fā)回溯得到的第一個(gè)使的下標(biāo)，由信賴域

24、半徑的自適應(yīng)調(diào)整規(guī)則，顯然有（見下圖），圖中箭頭表示的升降趨勢(shì)。由及，立即可得。這恰好表明由這樣的構(gòu)成的子列滿足： 且 即若時(shí)，不大于零，則可構(gòu)造出一個(gè)子序列使得且。這正好是第一種情形，故兩種情形至少會(huì)出現(xiàn)一種。若進(jìn)一步加上較強(qiáng)的條件，可得到信賴域算法的二階收斂結(jié)果。定理3.11 若進(jìn)一步假定在定理3.10中的聚點(diǎn)處，有正定，那么算法產(chǎn)生的序列整體有：，對(duì)充分大的，總有；并且收斂速度是二階的。證明：假設(shè)算法產(chǎn)生的子序列屬于第一種情形，即 考慮牛頓方向。由正定，因此當(dāng)充分大時(shí)，有定義且為下降方向。1）若，則（即牛頓步為信賴域子問(wèn)題的最優(yōu)解） 其中，是的最小特征值。2）若，則是信賴域子問(wèn)題的可行解

25、。 綜合1）與2）可知，在任何情況下，都有。又由 得 （*）這與矛盾，從而子序列不屬于第一種情形，而屬于第二種情形。故 （注：到現(xiàn)在為止，結(jié)論還僅限于子序列）若對(duì)子序列中的某個(gè)充分大的，有這里由牛頓收斂定理中要求初始點(diǎn)充分靠近的條件：所確定。注意到牛頓法收斂定理的條件現(xiàn)在全部滿足，為初始點(diǎn)。由于 滿足 （由牛頓收斂定理的證明）而且由 知在信賴域中，因而此時(shí)信賴域算法蛻變?yōu)榕ｎD算法。故而對(duì)整個(gè)序列有。注意到：及（*）式知。由信賴域半徑的自適應(yīng)調(diào)整規(guī)則，當(dāng)充分大時(shí)，始終有單調(diào)增，故有 （注意這里是對(duì)整個(gè)序列，而不僅指子序列）。而且充分大時(shí)，總有。此時(shí)，信賴域算法完全蛻變?yōu)榕ｎD算法，故有二階收斂速度

26、。注：這個(gè)定理的證明過(guò)程知，信賴域算法在迭代后期，將自動(dòng)轉(zhuǎn)化為牛頓算法，因而具有二階收斂速度；而在算法的開始階段，對(duì)初始點(diǎn)無(wú)特殊要求，因而具有全局收斂性質(zhì)。三、關(guān)于信賴域子問(wèn)題最優(yōu)解的條件在下面的討論中，均采用范數(shù)。定理3.12 考慮二次函數(shù) 其中為對(duì)稱矩陣。則 （1）有極小點(diǎn)當(dāng)且僅當(dāng)為半正定，且屬于矩陣的值空間，即；（2）有惟一極小點(diǎn)當(dāng)且僅當(dāng)正定；（3）若為半正定，則方程的每個(gè)解均為的全局極小點(diǎn)。證明：(1) 假定為半正定，且屬于的值空間。即存在，使得，令 ， 則有 。顯然， 有 （*）故是的（全局）極小點(diǎn)。反之若是的極小點(diǎn)，則滿足極小點(diǎn)的二階必要條件： ，且半正定，（1）得證。（2）注意到

27、：當(dāng)且僅當(dāng)正定時(shí)，（*）對(duì)一切，成為嚴(yán)格不等式。故有惟一極小點(diǎn)當(dāng)且僅當(dāng)正定。（3 再注意到（*）當(dāng)及半正定時(shí)總成立，故當(dāng)滿足時(shí)，也是的極小點(diǎn)。定理3.13 考慮信賴域問(wèn)題： （1）則為該問(wèn)題解的充要條件是，且存在，使得： ， 且半正定。證明： 充分性： 設(shè)有及，使得 ，且半正定。由前一定理，可知是二次函數(shù)的極小點(diǎn)。因此，對(duì)一切，有 從而有 （2）由 及，由（2）知，當(dāng)時(shí)，有 。即為信賴域問(wèn)題的解，充分性得證； 必要性：設(shè)是（1）的解，(a) 若，則是的無(wú)約束極小，故半正定。取，即知 ，滿足所有條件；(b) 若，則也是等式約束問(wèn)題 （3）的解。因此，由條件極值的拉格朗日乘子法，存在，使得Lagr

28、ange函數(shù)的梯度在處為，即：可見，與滿足： （4）下證：及半正定。由于是（1）的解，故當(dāng)時(shí)，（2）式成立。由（4）式，在（2）中用代替，并整理得即對(duì)任意的，當(dāng)時(shí)，有由此可證：，有從而半正定?，F(xiàn)證。 假定，則由半正定，必正定，且其最小特征值。令 則為的唯一的無(wú)約束極小。由于滿足故 。而的最大特征值為，又 故 即也是（1）的唯一極小點(diǎn)，這與為（1）的極小點(diǎn)矛盾。故必有。注：以上所說(shuō)極小點(diǎn)均指全局最小點(diǎn)。推論 問(wèn)題（1）沒有滿足的解，當(dāng)且僅當(dāng)為正定，且。證明：若正定，且，則是唯一的無(wú)約束極小點(diǎn)。而它又是（1）的可行解，故它也（1）唯一極小點(diǎn)，因而在邊界上不再有其它解。反過(guò)來(lái)，若（1）在邊界上無(wú)解，

29、故（1）的解均在約束域內(nèi)部（因?yàn)椋?）總是有解的），設(shè)是（1）的解，且，由定理3.13知：存在，使得 ， 且半正定。而由知，必有，且半正定。這時(shí)若為奇異的，則存在，使 ，且 于是滿足。 取，則與滿足定理3.13的充分性條件，故是(1)的解。但它在邊界上，與其在邊界上無(wú)解的條件矛盾，故非奇異。因而必正定。再由，因而也是的無(wú)約束極小，故有，即 或 因而有 。注：由以上分析可知：若正定，且，則為（1）的解。否則（1）必有一解在邊界上，由定理3.13，應(yīng)存在參數(shù)，使得半正定且使的解滿足：。四、 Levenberg-Marquardt方法上面一般地討論了信賴域方法的算法模式并證明了算法的收斂性定理。而關(guān)

30、于如何求解信賴域子問(wèn)題尚未涉及，因而僅是算法模式而不是具體算法，下面給出幾種具體的信賴域算法。根據(jù)上一段關(guān)于信賴域子問(wèn)題解的最優(yōu)性條件的討論，我們知道對(duì)信賴域問(wèn)題： 是其最優(yōu)解的充要條件是，且存在使得： 且 半正定?；谏鲜鼋Y(jié)果，Levenberg-Marquardt算法的核心思想是每次確定一個(gè)，使正定，然后求解確定，并令信賴域半徑 。Levenberg-Marquardt算法1）初始步：給出，置2）第次迭代(1) 對(duì)給出和，計(jì)算和，若，stop。(2) 檢驗(yàn)是否正定。若不正定，置，重復(fù)這一過(guò)程直到正定。 (3) 由計(jì)算出。 (4) 求，和的值。 (5) 若，置；若，置； 否則，置。(6) 若 ，置；否則，置。(7) 令，go to (1)。注：1）在每次迭代中以試探的方式獲取。2）信賴域子問(wèn)題的最優(yōu)解總在信賴域邊界上達(dá)到，因?yàn)椴皇鞘孪却_定，而是以