最優(yōu)化理論 第六章 信賴域方法

§6.1信賴域方法的基本思想k 70年代提出的一種重要的優(yōu)化方法，它不同之前算法遵循的先確定搜索方向dk，再沿dk進(jìn)行一維搜索來確定步長(zhǎng)xk1xkdkk xk1必須位于當(dāng)前迭代點(diǎn)xk（信賴域）內(nèi)，即先確定步長(zhǎng)的取值范圍，然后在這個(gè)范圍內(nèi)通過求解信賴域子問題min

q(s)f(xk)gTs1sTGsk k 2

(6.1.1)s.t. shkskxk1xksk.注（kkk（）范數(shù)沒有特別限制，可根據(jù)需要隨意選取，但多數(shù)情形用

或（）k可22h采用自適應(yīng)方式調(diào)整，若q

(sf(xks近似程度k kh盡可能取大，否則將其縮小.而通常采用下述方式評(píng)價(jià)q

(sf(xks的逼近k程度.在算法迭代的第k步，定義k ff(xkf(xksk和qk

kkf(xk)q(sk)，kfkqk稱為預(yù)估下降量，并定義比值rfk，k qk.6.1（信賴域方法）1x0，容許誤差0，令hg

，置k0；0 0k2：若||g||xk；k步3g和G6.1.sk；k k步4：求f(xksk)和r的值，如果r0.25，則令h ||sk||/4，轉(zhuǎn)步6；k k 步5：如果r0.75且skh，則令h 2h，否則置h h；k k k kk6：若r0xk1xkxk1xksk；k7：置kk12.6取決rk0.在有些信賴域算法中，將步6中的rk0替換成了rk(0.§6.2信賴域算法的收斂性6.2.1Bn中的一個(gè)有界集，fC2B上滿足G(x)MM為正常數(shù)，若信賴域算法產(chǎn)生的點(diǎn)列{xkB，則{xk存在一個(gè)滿足一階和二階必要條件的x.k 證記hinfhhh0.k h0.這時(shí)，存在點(diǎn)列{xk一個(gè)子序列{xk}K1K

lim

.從算6.14K2K1，使對(duì)每個(gè)kK2，r0.25，且

lim h

0，從而

lim ||sk||0.x是子列{x}

的任一聚k kK2,k

k1

,k

kK2

3K2

limkK3,k

xkxx就是滿足定理要求的點(diǎn).Kgf(x)0{xk}K3

xk有kq(gk)f(xkk

)gk

12gTGg2 k kk. (6.2.1)2ggk 2 kggkgk由gkgk

是信賴域子問題的可行解，有1sk2gTGgk kkkqfq(sk)fq(skgk1sk2gTGgk kkkgkk k k k kgkk1212

2 g2kskg sk MkMsMskgk

skg

)，(6.2.2)12kMskgk注意到k且kK3時(shí)，12kMskgk

0，gk

0，我們有2

1，故g12qkg12

skg .2sk2sk2sk2skgk2skgkk2s2skqk

0，而由Taylor展開式知f

(sk

2，從而有

rfkkqkk

1kK3時(shí)，rk0.25g0.再證GG(x半正定.若不然，設(shè)是G的最小特征值，則0.設(shè)其對(duì)應(yīng)的單位k特征向量為v且滿足vTg0(否則可取v). 顯然skk

v是信賴域子問題的可行解，故有qfq(sk

v)sk

1sk2vTGv1sk2vTGv122

sk ，k k k

k 2 k 2 k 2由此可知，當(dāng)kkK3時(shí)，有qk

(sk2(sk2)(sk2)

2 0，/2再由f

(sk

2得rk

fkqk

.K情形二，h0. 這時(shí)存在點(diǎn)列{xk}一個(gè)子序列{xk}K1

lim

h0，infhkh0.6.15才能保證信賴域半徑不縮減，故存在無(wú)限子列kK12K2K1，使對(duì)每個(gè)kK2rk0.25.x是子列{xk}K的任一聚點(diǎn)，則存在2K3K2

limkK3,k

xkxx就是滿足定理要求的點(diǎn).f1f

fk0.25qkqk收斂.因而kK3

kK3

kK3x，定義

limkK3,k

qk0. (6.2.3)qsfsTg1sTGs，2并設(shè)滿足0h2sminq(s)s.t.

(6.2.4)3 的解. 注意到k,kK時(shí)，有xkx，因而對(duì)充分大的kK，xxs滿足3

hk，從而對(duì)充分大的kK3，有k k k q(xk)q(sk)fk k k kxxkxsxksf

G，因而有k k kq(s)fq(0).s0也是(6.2.4)的最優(yōu)解.注意到h0.s0相當(dāng)于無(wú)約束最優(yōu)化問題minsRn

q(s的極值.因而有q(0)0，2q(0g0，G半正定..定理6.2.2 若進(jìn)一步假定在定理6.2.1中的聚點(diǎn)x處有G正定，則算法產(chǎn)生的序列{xkxr1infh0.k，總有skh，并且具有局部二k k k階收斂速率.K證假設(shè)算法產(chǎn)生的序列有子序列{xk}K3

kK3

有r0.25,h

sk0,xkx.k k kk 考慮牛頓方向dkG1g.由G正定，因此當(dāng)k充分大時(shí)，dk有定義且為下降方向.若dk

skdkG1g

，從而有k qfq(sk)gTsk1(sk)TGsk1(Gsk)Tsk1k

2sk ，(6.2.5)2k k k k 2其中k是Gk的最小特征值.dkddkdk

k 2 k 2k若dk

ss

是信賴域子問題的可行解，由此得dkdkqfq(dkdk

)sk

(dk)TGdk k

2(dk)TGdk12 k 2s12 k 2k k 1212

(dk)TGdk

dk dk12k k 1 k212 s k dk

s kd

2ks .2因此，在任何情況下，都有q1sk ，由此推出r1(k)，但這與r0.252k 2k k k矛盾，矛盾表明沒有任何子序列屬于第一種情形.infhh0.kk1k

K，滿足

limkK3,k

xkx，若對(duì)子序列{xk}K3Kx0xk min{h/2,}，x0

中的某個(gè)充分大的k，有0這里xkx的條件0

xk

0所確定.注意到牛xk xk為初始點(diǎn).xk1xkG1gxk x足xk1x

xk

，于是，由xxk1xkx

1

xk

hkxxk{x|||xxk||h中，因而此時(shí)信賴域算法蛻變?yōu)榕ｎD算法.故對(duì)整個(gè)序xxkxkx.而且k充分大時(shí)，總有sk

，故由(6.2.5)知rk1.此時(shí)，信賴域算法完全蛻變?yōu)榕ｎD算法，故有局部二階收斂速率.注從這個(gè)定理的證明過程知，信賴域算法在迭代后期，將自動(dòng)轉(zhuǎn)化為牛頓算法，因而質(zhì).§6.3關(guān)于信賴域子問題最優(yōu)解的條件在下面的討論中，均采用l2范數(shù).定理6.3.1 對(duì)于二次函數(shù)q(s)fgTs1sTGs，k k k 2 k其中Gkn階對(duì)稱矩陣.我們有如下結(jié)論：

有極小點(diǎn)當(dāng)且僅當(dāng)Gkg

{Gs|sRn}；k qk(s有惟一極小點(diǎn)當(dāng)且僅當(dāng)Gkk 若Gk為半正定，則方程Gksgk的每個(gè)解均為qk(s的全局極小點(diǎn).k證（1）G半正定，且存在sRn，使得gk

kGks.s*sGks*Gksgk.這時(shí)，對(duì)任意dR，由q(s*ds*Taylor展開式，有nkkq(s*d)q(s*)(Gs*g

)Td1dTGdq(s*)1dTGdq(s*)，(6.3.1)k k k ks*是qk(s的全局極小點(diǎn).

2 k k

2 k ks*qk(s的極小點(diǎn)，則滿足極小點(diǎn)的二階必要條件，即有qk(s*)Gks*gk0k 且2q(s*)k

半正定.由于(6.3.1)d0成為嚴(yán)格不等式的充分必要條件是Gk正定，故qk(s有惟一極小點(diǎn)當(dāng)且僅當(dāng)Gk正定.滿足gk0且也是s.定理6.3.2 min

q(s)fgTs1sTGsk k k 2

(6.3.2)s.t. shk為(6.3.2)的最優(yōu)解的充分必要條件是

，且存在*0，使得且Gk*I半正定.

(Gk*I)s*gk，*(hk

s*)0， (6.3.3)證充分性.假設(shè)充分條件成立，則對(duì)一切||s||hk，有q(s)q(s*)fgTs1sTGs[f

gTs*1s*TGs*]k k k

2 k k k 2 k(ss*)T(G*I)s*1[sTGss*TGs*]k 2 k k1 T * T T2(ss*)(Gk*I)(ss*)

(s*2

s*ss)， (6.3.4)*(hk

s*0*(h2

s*20*s*Ts**h2，故由(6.3.4)及kkshk時(shí)，有qk(sqk(s*s*為信賴域問題的最優(yōu)解，充分性得證.kk.是(6.3.2)的最優(yōu)解.若

s*hks*qk(s的無(wú)約束極小點(diǎn)，故Gk半正定.取*0，則充分條件成立.若s*hks*是等式約束問題min

q(s)fgTs1sTGsk k k 2

(6.3.5)s.t. shk的解.因此，由條件極值的拉格朗日乘子法，存在*Lagranges*處的梯度L(s*)qk(s*)*s*gkGks**s*0.（6.3.下面證明Gk*I半正定.s*是（6.3.2）的解，故對(duì)任意滿足s

s*s，由(6.3.4)式可知，1(ss*)T(G*I)(ss*)0.2 kn T 2xTs*故對(duì)任意0xRxs*0ss*

x，則有||s||2||s*

2xTs*||x||2

x||2||s*||2，且T Tx(Gk*I)x(2xTs*)2(ss*)(Gk*I)(ss*)0，xTs*0x的點(diǎn)列{xi}，且對(duì)每個(gè)i有(xi)Ts*0，由二次函數(shù)的連續(xù)kxT(Gk

*I)x0，從而Gk

*I半正定.下面證明*0.假設(shè)不然，即有*0，這時(shí)，由Gk*IGk必定正n

.

是minqk(s的唯一極小sRnk 點(diǎn).s*滿足(G*I)s*gs?(I*G1)s*I*G1k k k k k值為1*/n1，故k k ||||s*||||s*||k k 推論 信賴域子問題（6.3.2）沒有滿足

shk的最優(yōu)解，當(dāng)且僅當(dāng)Gk正定且Gg1k khkGg1證若G正定且G1g h，則sG1g

是minq(s)的唯一極小點(diǎn)，而它又是k k k

k k k（6.3.2）的可行點(diǎn)，故它是（6.3.2）的唯一最優(yōu)解.反過來，如果（6.3.2）沒有滿足s

hks*必定在可行域的內(nèi)部.由于||s*||hk6.3.2*0且Gk半正定.若Gk奇異，則存在d0，使得Gkd0且||s*d||hk，由此可知Gk(s*d)gk，對(duì)應(yīng)于*0，由定理6.3.2s*d也是（6.3.2）的最優(yōu)解且滿足||s*d||hk，與假設(shè)矛盾，矛盾表明Gk非奇異，從而G正定.于是，由定理6.3.2可知，s*G1g且G1g h.k k k k k k§6.4Levenberg-Marquardt方法

q(s)fgTs1sTGsk k k 2

(6.4.1)s.t. shkLevenberg-Marquardt6.3.2結(jié)論的啟發(fā)，其核心思想是每次確定一個(gè)k0，使得GkkI正定，然后通過求解線性方程組(sk)Tsk(GkkI(sk)Tsk

hk .算法）01x00，容許誤差0，置k0；02g和G，若g

xk；k k k3：分解GkkIk4k，重復(fù)這一過程直到GkkI正定；4：由(GI)sgsk；k k k5f(xksk)q(skr的值；k k6：若rk0.25k14k8；7：若rk0.75k1k/2k1k；k8：若r0xk1xkxk1xksk；k9：置kk12.以試探的方式獲取.（2）可以證明()(GI)1g [gT(GI)2g

單調(diào)遞減.事實(shí)k k k k k上，利用函數(shù)矩陣的微分公式：dA(t)B(t)A(t)dB(t)dA(t)B(t)，dt dt dtA(t)A(t)，dA1(t)1 dA(tA(t)A(t)，dt dtdA2(t)dA1(t)A1(t)

A1

(t)

dA1(t)dA1(t)

A1

.我們有

dt dt dt dtgT(GI)3g gT(GI)3g sT(GI)1sgT(GuI)2gk kk'()k k kgT(GuI)2gk kks sg0sgT(GI)2g]1/20，若G

I正定，則有'()0.k k k k k

，這將使sk1變小，從而信賴域縮??；而r0.75時(shí)，令k /2，這將使sk§6.5折線步與雙折線步方法§6.5.1折線步方法（TheDoglegStepMethod）對(duì)于信賴域子問題

q(s)fgTs1sTGsk k k 2

(6.5.1)s.t. shk如果精確求出它的最優(yōu)解，計(jì)算成本比較高.類似于不精確線搜索方法，Powell（1970）提出一個(gè)簡(jiǎn)單易行、保證目標(biāo)函數(shù)有可接受下降量的方法，并稱其為折線步方法.k k 我們把(6.5.1)q(sdkg/||k k 稱為Cauchyminq(dk不難解出最優(yōu)步長(zhǎng)k h,

gTGg

0,

k k k

(6.5.2)k min{||g||3/gTGg,h}, gTGg

0. k k kk k k kkC 由此可知，Cauchyxk1xkdkC .為了獲得算Gxk1xkG1g.當(dāng)(6.5.2)中hk N k k k k時(shí)，有

g3 g3

g G1gskCk skC

k k k k ks，kgTGg gTGg gTG1gs，k

(gTGg

)(gTG1g) Ngk N4skk kk k kk k k k k kk k gk N4skg4其中 k 1.這是因?yàn)?gTGg)(gTG1g)k kk k k k1 1 1

1 2 1 2g4(gTG2G2g)2[(G2g)T(G2g)]2G2g G2g .k k k k k k k k k k k k k因而有

sCk sC2

k kssN2 ss

. (6.5.3)2折線步方法的基本思想是當(dāng)||sk||||xk1xk||hxk1xk1，否則，xk1就N N k NCauchyxk1xk1的連線與||xxk||h的邊界的交點(diǎn)，即確定[0,1，使C N kC N C C N 得||xk1(xk1xk1xk||hxk1xk1(xkC N C C N .§6.5.2雙折線步方法（TheDoubleDoglegStepMethod）Denns和Mi17算法的性態(tài)將得到改善.據(jù)此，他們提出了一種