最優(yōu)化理論 第三章 一維搜索

如前所述，最優(yōu)化算法的迭代格式為kxk1xkdk，k因而算法的關(guān)鍵就是選擇合適的搜索方向，然后再確定步長(zhǎng)因子k.若設(shè)()f(xkdk)，k xk出發(fā)，沿dk方向搜索，希望找到，使得((0k 是所謂的一維搜索或線搜索(linesearch)問(wèn)題.如果求得的k，滿足f(xkdk)minf(xkdk)

或(

)min()，k 0 k 0則稱其為精確一維搜索，相應(yīng)的k稱為最優(yōu)步長(zhǎng)因子.如果選取的k，使目標(biāo)函數(shù)獲得可以接受的改善，即kf(xk)f(xkdk)0，k則稱其為非精確一維搜索.§3.1一維搜索的基本框架確定包含最優(yōu)解的初始搜索區(qū)間；采用某些區(qū)間分割技術(shù)或插值方法不斷縮小搜索區(qū)間，最后得到可以接受的解.設(shè)，*[0是函數(shù)()的最小值點(diǎn)，即(*)min(.若存在00，使

*[ab]，則稱[ab為一維極小化問(wèn)題min()的搜索區(qū)0間.是探測(cè)，試圖找到函數(shù)值呈“高－低－高”變化的三點(diǎn).若一個(gè)方向不成功，就退回來(lái)，再沿相反方向探測(cè).確定初始搜索區(qū)間的進(jìn)退法）1：取初始步長(zhǎng)h，置初始值10，1(1，并置k0；2：置1h，(kk1；4：若k1，則置2,2hh2，否則取amin{,2}，bmax{,2}，停止計(jì)算.確定了初始搜索區(qū)間[ab后，接下來(lái)就是采用具體的一維搜索方法確定出*.為此，我們先給出如下概念.設(shè)，[ab.若存在*[ab()在[a,*]上單調(diào)減少，而在[*b[ab]是函數(shù)()的單峰區(qū)間，()是[ab]上的單峰函數(shù).(是區(qū)間[ab上的一個(gè)單峰函數(shù)，1,2[a,b，且12.則有（1）當(dāng)(1)(2)時(shí)，（2）當(dāng)(1)(2)時(shí)，

[a,2]是()的單峰區(qū)間；[1b是()的單峰區(qū)間..§3.2精確一維搜索的收斂理論§3.2.1采用精確線搜索下降算法的收斂性2.1xk處沿下降方向dk進(jìn)行精確一維搜索時(shí)，函數(shù)值下降量的估計(jì).定理3.2.1 設(shè)dk是f(x)在xk處的下降方向，是minf(xkdk)的解，如果存在M，使得不等式

k 0f2(xkdk)M對(duì)任意0成立，則有不等式12Mkf(xk)f(xkdk)12Mk證由定理假設(shè)，對(duì)任意0，有

f(xk)

dk,

f(xk).k k k kTk 2 k2f(x

)f(x

)f(x)d

Md ，2f(xk)Tdk特別地，上述不等式對(duì)其右端二次函數(shù)的極小點(diǎn)

2Mdk2

也成立，而且只要搜索方向dkf(xxk處的下降方向，即f(xk)Tdk0，就有0.因此，當(dāng)dkf(x)xk處的下降方向時(shí)，我們有k k k k k k kTk 2 k2f(x

)f(x

kd

)f(x

)f(x

)f(x)d

Md212M21(f(xk)Tdk)212M2

f(xk)

(f(xk)Tdk)22 222 Mdk2

f(xk) dk12M f(xk12M

dk,

f(xk).定理3.2.2 設(shè)f(x)在開集Dn上連續(xù)可微，設(shè)xD是采用精確線搜索的下降算（即保證f(xk1)f(xk)和f(xk)Tdk0對(duì)任意k成立產(chǎn)生的點(diǎn)列{xk}的一個(gè)聚點(diǎn)，K是滿足limxkx的指標(biāo)集.M0||dk||M對(duì)任意kKd1 xK1 1是序列{dk的任一聚點(diǎn)，則有f(x)Td0.f(xD上二次連續(xù)可微，則還有dT2f(x)Td0.

2K1是滿足

dlimdkkK2

.假設(shè)定理結(jié)論不成立，即f(x)Td0，由于f(xk)Tdk0，注意到kKlimxkx,limdkd，2xK2 kK22可得f(x)Td0.結(jié)合前面的假設(shè)可知，必存在正數(shù)0，使得f(x)Td0，xN(xK3K2xN(xkK3時(shí)，有

f(x)Tdk/20.由于xkx||dkM，使得對(duì)所有0及xK13所有kKxkdkN(x)，于是3f(x)f(x)[f(xk1)f(xk)][f(xk1)f(xk)]0k00

kK3k[f(xk?dk)f(xk]f(xk?dkT?dkk

(0k

kK3kK3

kK3f(xf(x為有限值矛盾，矛盾表明必有f(x)Td0.0同樣地，若dT2f(x)d0不成立，則必有dT2f(x)d0.類似地，有00f(x)f(x)[f(xk?dk)f(xk]0kK3[f(x

?d

?)2

(dk)T2

f(xk

k?

]

kK3k Kk K3

(dk)T2

f(xk

k?

k

?)k k K

()，2此矛盾表明必有dT2f(x)d0.定理3.2.3 設(shè)f(x)在水平集L{xf(x)f(x0)}上存在且一致連續(xù)，采用精確線搜索的下降算法產(chǎn)生的方向dk與f(xk)的夾角k滿足：k/2，其中是一個(gè)給定的小于/2的正數(shù)，則或者對(duì)某個(gè)kf(xk0limf(xk，或者有l(wèi)im||f(xk||0.

k證若對(duì)某個(gè)k有f(xk0，或者有l(wèi)imf(xk，則結(jié)論成立.故不妨設(shè)對(duì)任意kk都有f(xk0且下降序列f(xk)}有下界，因此limf(xk存在，從而有klim[f(xk1)f(xk)]0.k下面用反證法證明lim||f(xk||0.k假設(shè)lim||f(xk||00KkK都k 1 11有||f(xk||成立，故對(duì)任意kK，都有1k 1f(xk)Tdk||dk||||f(xk)||coscos(/2)sink 1由于f(xkdk)f(xk)f(k)Tdk

（kxkxkdk之間）f(xk)f(xk)Tdk[f(k)f(xk)]Tdkk k f(xk)Tdk

k k f(x

||d

||dk||

)f(x

)||， 再注意到f(xL上一致連續(xù)，故存在，使得當(dāng)0||dk||時(shí)，有1||f(k)f(xk)||/2，1若在上面的不等式中取 ，則對(duì)任意kK，都有f(xk

||dk||dkd )f(xk||dk||

1f(xk)Tdk||dk||

1)f(xk)2

21，11故對(duì)任意kK1，有11f(x

)f(xk

dk ||dk||) f(x

)21， 但這與limf(xk1f(xk0矛盾，矛盾表明必有l(wèi)im||fxk|| k k§3.2.2采用精確線搜索下降算法的收斂速率引理3.2.4 設(shè)函數(shù)()在閉區(qū)間[0,b]上二次連續(xù)可微，且(0)0.若()在

[0,b]證構(gòu)造輔助函數(shù)()(0)M，它有唯一零點(diǎn)(0)/M.注意到 ()d(0)Md() 0 0即()的圖像總位于()之下，再由()是單調(diào)上升函數(shù)可知，()的零點(diǎn)*必位于(零點(diǎn)的右邊，即*(0)/M.3.2.5f(x)nxdn和，有f(xd)f(x)f(x)Td21(1t)[dT2f(xtd)d]dt.0 證f(xdf(x1df(xtd1[f(xtd)Td]d(1 0 00(1t)f(xtd)Td10

1(1t)d[f(xtd)Td]0f(x)Td21[dT2f(xtd)d](1t)dt.0引理3.2.6f(xx*的鄰域內(nèi)二階連續(xù)可微，若存在0和0mM，使當(dāng)xx*

yn，都有my2yT2f(x)yMy2，則當(dāng)xx*時(shí)，必有1mxx*2f(x)f(x*)1Mxx*2，2 2f(x)mxx*.證由引理f(x)f(x*)f(x*)T(xx*)1(1t)[(xx*)T2f(tx(1t)x*)(xx*)]dt，0由于f(x*0，再利用引理?xiàng)l件，我們立刻得到1mxx*2f(x)f(x*)1Mxx*2.2 2又由于故有

f(x)f(x)f(x*)12f(tx(1t)x*)(xx*)]dt，0

xx*(xx*)Tf(x)1(xx*)T2f(tx(1t)x*)(xx*)]dtmxx*2，0由此即得f(x)mxx*.k定理3.2.7設(shè)采用精確線搜索的下降算法產(chǎn)生的點(diǎn)列{xkf(x的極小點(diǎn)x*，f(xx*的某一鄰域內(nèi)二階連續(xù)可微，搜索方向dk與f(xk的夾角/2，k且存在0和0mM，使當(dāng)

xx*

yn，都有則{xkR線性收斂.

my2yT2f(x)yM

y2，證由于limxkx*k充分大時(shí)，有k

/2，

xk1x*

2.我們不妨假設(shè)搜索方向dk都是單位向量從而有界，則存在0，使得kxk()dkx*k記(f(xkdk，由于

xk1x*dk

.kxk()dkx*k故當(dāng)0k時(shí)，有

xkx*

，xkdkx*

xk()dkx*

kk(xkx*)()dk(1)(xkx*)kkkxk()dkx*(1)(xkx*)(1)，k又注意到(0)f(xk)Tdk0，且2()(dk)T2f(xkdk)dkMdk2

M([0,k])，k 3.2.4知，(f(xkdk在[0,上的極小點(diǎn)k f(xk)coskf(xf(xk)coskf(xk)k

，M M M M為cosk0.若記k

f(xk)/M

.xkxkdkxkxk與k kkxk1xkdk kkxkx*

maxxkx*,

xk1x*，3.2.53.2.6k f(xk1)f(xk)f(xkdk)f(xk)f(xkdk)f(xkk 1f(xk)Tdk2 (1t)(dk)T2f(xktdk)dkdtk k0 k

(f(xk)T)dk1M2k 2 k

f(xk)cos1M2f(xk)1M2k k 2 k k 2 kf(xk)2f(xk)2 ()f(xk) M2M 2 M2222M f(22M

2 2m2M2m

xkx*m[f(x)f(x*)]m[f(x)f(x*)]( )[f(x

m2 k2M M M))f(x*)]，

k k

m2 kf(x

)f(x*)f(x

)f(x)f(x

)f(x*)[1( )][f(xM

)f(x*)]，m 1令[1( )2]2，顯然01，且有Mf(xkf(x*2f(xk1f(x*2kf(x0f(x*，3.2.6，我們有xkx*22[f(xk)f(x*)]22k[f(x0)f(x*)]22k，m m其中

2[2[f(x0)f(x*)]m

k，由此即得迭代點(diǎn)列{xk線性收斂.§3.3 精確一維搜索方法§3.3.1 0.618法0.618Fibonacci搜索區(qū)間，當(dāng)區(qū)間長(zhǎng)度縮到一定程度后，區(qū)間內(nèi)各點(diǎn)均可作為近似解.這類方法十分簡(jiǎn)便，僅需計(jì)算函數(shù)值，尤其適合于非光滑及導(dǎo)數(shù)表達(dá)式復(fù)雜或?qū)懖怀龅那樾?1設(shè)()f(xkdk是搜索區(qū)間[ab上的單峰函數(shù).k次迭代時(shí)搜索區(qū)間為[ak,bk]，現(xiàn)取兩個(gè)試探點(diǎn)kk[ak,bk，且kk，計(jì)算(k和(k1（1）若(k(k，則最優(yōu)解*[akkak1akbk1k；（2）若(k(k，則最優(yōu)解*[k,bkak1kbk1bk.由于兩個(gè)試探點(diǎn)kk中必定有一個(gè)落入縮短的區(qū)間[ak1bk1，我們希望在下一次我們要求kk滿足下列條件：kk到搜索區(qū)間的端點(diǎn)等距，即bkkkak；每次迭代，搜索區(qū)間長(zhǎng)度的縮短率相同.即(bkak)，其中是與k無(wú)關(guān)的常數(shù)；因此有bkkkak(bkak)，由此得kak(1)(bkak)，kak(bkak).不妨設(shè)[ak1,bk1akk]，此時(shí)k含在[ak1bk1中.k1滿足：k1ak1(bk1ak1)ak(kak)a[a(ba)a]a2(ba)，k k k k k k k k為了減少計(jì)算量，我們希望k1與k重合，這樣，新的試探點(diǎn)k1處的函數(shù)值就不必重新計(jì)算，即要求21

k,bk的情形也有類似結(jié)論.解方程21，并取正值，得

15 152由此，0.618法的計(jì)算公式具體為：

0.618(bkak).0.618法也稱黃金分割法.3.2（0.618法）1：確定初始搜索區(qū)間[a1b1和容許誤差0，計(jì)算初始兩個(gè)試探點(diǎn)令1(1和2(1，置k1；34；kk，1(kk1ak10.618(bk1ak1，令2(k15；4kk，，令1(k15；5：置kk12.0.618法要求一維搜索的函數(shù)是單峰，而實(shí)際上很多情形都不是單峰.這個(gè)時(shí)候往往容..值都進(jìn)行比較..經(jīng)仍不能保證迭代過(guò)程不丟掉極小點(diǎn).§3.3.2Fibonacci法通過(guò)選擇試探點(diǎn)，并利用試探點(diǎn)處的函數(shù)值信息，可以不斷縮短搜索區(qū)間.在函數(shù)值計(jì)Fibonacci法的動(dòng)機(jī).設(shè)函數(shù)值計(jì)算總次數(shù)為nLnLn的上確界.Li的上確界為Ui，即Ui表示當(dāng)允許計(jì)算i次函數(shù)值時(shí)，初始區(qū)間長(zhǎng)度的上確界（當(dāng)i,,,n..如果只允許計(jì)算零次或一次函數(shù)值，區(qū)間不會(huì)得到縮短，故有U0U11.下面考慮允許計(jì)算n[ab的長(zhǎng)度的上確界Un.設(shè)最初的兩個(gè)試探點(diǎn)為11n2次函數(shù)值，而極小點(diǎn)可能位于[a1或[1b.若極小點(diǎn)位于[a1中，由于我們僅可在此區(qū)間中再計(jì)算n2次函數(shù)值，故有1aUn2；若極小點(diǎn)位于[1bn21處的函數(shù)值，因而

b1Un1；LnbaUn1Un2，從而UnUn1Un2.大家知道，由遞歸關(guān)系給出的數(shù)列稱為Fabonacci數(shù)列，從上一段分析看出，顯然有UnFn.因此若某種取點(diǎn)方式能保證在計(jì)算函數(shù)值nFn1，或等價(jià)地，把搜索區(qū)間縮減為最初區(qū)間的1Fn，那么就有理由認(rèn)為這種取點(diǎn)方式是最優(yōu)的.FabonacciFabonacci.因.FFabonacci法中探測(cè)點(diǎn)的取法如下：FFaF

a)a

a)，k k1

k k

k knk1FaF

，

1,2,,n1，k k k knk1n次函數(shù)值計(jì)算后，最終區(qū)間縮為初始區(qū)間的1/Fn.n時(shí)，0.618Fibonacci法也是線性收斂的.0.618法與其近似，故應(yīng)用上將它們統(tǒng)稱為優(yōu)選法.§3.3.3 二分法二分法是求(0的根的一種簡(jiǎn)單方法.它每次將區(qū)間對(duì)分，再利用連續(xù)函數(shù)的零2，因此它也具有線性收斂速率.但當(dāng)?shù)谋磉_(dá)式很難求或(不可微時(shí)，方法的應(yīng)用遇到困難..3.3（二分法）1：確定初始搜索區(qū)間[a1b1和容許誤差0，計(jì)算試探點(diǎn)1a1b12，置k1；2：若bkak，則停止計(jì)算，輸出k；3：計(jì)算'(k，若'(k0，則令ak1akbk1k，否則令ak1k，4：令k1ak1bk12，置kk12.一點(diǎn)二次插值法（牛頓插值法）(Taylor二階展開式的極小點(diǎn)k1作為()極小點(diǎn)更好的近似解.設(shè)

)2.k k k 2 k kkq((()(0，解之得k

(k).因此，牛頓法的1 1 1

k 迭代公式為

(k),

k0,1,. （3.3.1）

kk )k僅有局部收斂性，特別是當(dāng)(k0時(shí)，有(k1(k.二點(diǎn)二次插值法（一）設(shè)已給兩點(diǎn)12，利用(1),(2)以及(1)或(2)進(jìn)行插值.設(shè)二次插值函數(shù)形式為

令q()a2bc(), 1 1 1 12 2 2 q()a2bc2 2 2 q'()2ab(),由此解得

1 1 1a(1)(2)(1)(12), ()2 1 2b()(1)(2)(1)(12), 1

(

)2 11 2故q()的駐點(diǎn)為b2a

1

(12)(1) .()()2(1) 1 2 12

(kk1)(k)

，k1,2,. （3.3.2）k

()( )2(k) k k1 kk1 注要保證(k1(k，必須要求a0，即(1)(1)(21)(2).I）1：給出初始點(diǎn)1，初始步長(zhǎng)h0(0,1，容許誤差0；計(jì)算1(1，1'(1；2：若'(10，則置hh；3：置21h，計(jì)算2(2；4：若211'(21)，則置h2h3；5：計(jì)算11

)2

1 2 1 2[211'(21)]

()，'

)；6：若||1，1，1，hh，2.（二）設(shè)已給兩點(diǎn)1,2，利用(1)或(2)以及(1)和(2)進(jìn)行插值.令q()a2bc(), 1 1 1 1q(1)2a1b(1),q()2ab(),解之得

2 2 2b2a

12(1)(2)

(1).由此得到一般迭代格式為

kk1

k(),k

k1,2,. （3.3.3）

k

k)(k1)注要保證(k1)(k)，必須要求(kk1)((k)(k1))0.(3.3.1)比較，在迭代格式(3.3.2)中，2

(k)(k1)(k)

k kkk1k；而迭代格式(3.3.3)中，3 k k k(k)(k1)()，kkk1

)3.2 k k .設(shè)()三階連續(xù)可微，*滿足(*)0,(*)0，則二點(diǎn)二次插值公式產(chǎn)生的序列{k

收斂到*，且收斂速率的階為12

51.618.三點(diǎn)二次插值法設(shè)已給兩點(diǎn)1,2，3，對(duì)二次插值函數(shù)利用(1)(2)以及(3進(jìn)行插值.再用插值多項(xiàng)式的駐點(diǎn)近似()的駐點(diǎn).其一般迭代格式為

)1

(k2k1)(k1k)(kk2)

.（3.3.4）2

k)k2

kk2

k1

)k三點(diǎn)二次插值法具有如下收斂性質(zhì).設(shè)()四階連續(xù)可微，*滿足(*)0,(*)0，則上述插值法產(chǎn)生的序列{k收斂到*，且收斂速率的階約為1.32.三點(diǎn)二次插值法）1：用進(jìn)退法確定“高－低－高”三個(gè)點(diǎn)123，計(jì)算i(ii123，給出容許誤差0；2A2[1(232(313(12)]A0，則輸出2；3：計(jì)算[(22)(22)(22)]/A，1 2 3 2 3 1 3 1 2若(1)(3)0，停止計(jì)算，則輸出2；4：若|2|，則停止計(jì)算，輸出；5：計(jì)算(，若(1)(2067；6：若2，則置12,12，2,2，否則置3,3，轉(zhuǎn)2.7：若2，則置32,32，2,2，否則置1,1，轉(zhuǎn)2.§3.4 不精確一維搜索方法一維搜索是最優(yōu)化算法的基本組成部分.前述的精確一維搜索往往需要花費(fèi)大量計(jì)算.另外，在很多算法如牛頓算法和擬牛頓算法，其收斂速率.因此，另一種變通的方法是在每次一維搜索過(guò)程中，保證目標(biāo)函數(shù)都有一個(gè)滿意的下降就夠了，這就是所謂的不精確一維搜索.便于操作的準(zhǔn)則..Armijo-Goldstain準(zhǔn)則針對(duì)函數(shù)值究竟下降多少才算滿意，Armijo在1966年提出一個(gè)評(píng)價(jià)準(zhǔn)則.令()f(xkdk，并假設(shè)dk是f(x)xk處的下降方向，即有'(0)0.由于()在點(diǎn)0處的切線為(0)'(0)，故對(duì)任意數(shù)(0,1)，(0)'(0)是曲線()的經(jīng)過(guò)點(diǎn)(0,(0)的一條割線，基于這個(gè)事實(shí)，Armijo提出如下準(zhǔn)則，一個(gè)可以接受的步長(zhǎng)應(yīng)該滿足：k k ((0(0f(xkdkf(xkf(xk)Tdk k k其中012是給定的數(shù).xkdk處函數(shù)的圖像在相應(yīng)割線圖像的下方，這時(shí)我們就認(rèn)為函數(shù)值的下降量是可以接受的.kGoldstainArmijo準(zhǔn)則并不能排除步長(zhǎng)k改進(jìn)量都不大，影響算法的整體效率. 他提出如下補(bǔ)充準(zhǔn)則：k k ((01)(0f(xkdkf(xk1)f(xk)Tdk，(3.4.2)k k .越趨近于12，則可接受區(qū)間越小.方法）1：計(jì)算(0)和(0)(0,1/2)t1，在搜索區(qū)間[0,max中給定初始點(diǎn)0，令a00b0maxk0.2：計(jì)算(k，若(k(0k(0，3；否則令ak1akbk1k4.3：若

(k)(0)(1)k(0)，kak1kbk1bk4.步4：若bk1

，則取

ak1bk1，否則取k1 2

tk

.kk1，轉(zhuǎn)步2.Wolfe-Powell準(zhǔn)則Armijo-Goldstain準(zhǔn)則有時(shí)候會(huì)將最佳步長(zhǎng)因子排斥在可接受區(qū)間之外.為此，Wolfe-Powell給出了一個(gè)簡(jiǎn)單的替代準(zhǔn)則：k k ()(0)(0)或f(xkdk)f(xk)f(xk)Tdk k k k ()(0)或f(xkdk)Tdkf(xk)Tdk,(,1)k k 準(zhǔn)則(3.4.3)的幾何解釋是在可接受點(diǎn)處的切線斜率大于或等于初始斜率的倍.由于(,1)，因而可接受點(diǎn)處的切線更平坦些.Wolfe-Powell準(zhǔn)則中(3.4.3)式換為kf(xkdk)Tdkf(xk)Tdk, (3.4.4)k則當(dāng)?shù)闹翟叫?，Wolfe-Powell準(zhǔn)則越接近精確搜索，工作量也越大.應(yīng)該指出的是不精確搜索，不要求過(guò)小的0.1，0.4.Wolfe-Powell準(zhǔn)則下可接受步長(zhǎng)因子存在的，我們有如下命題.k3.4.1f(xf(xk)Tdk0，使得Wolfe-Powell準(zhǔn)則(3.4.1)和(3.4.4)滿足.k1 證令()f(xkdk)，則()f(xkdk)Tdk. 令滿足1 考慮集合

A{0|1(0)()0}.由于(有下界，且(0)f(xk)Tdk0A非空.A，即對(duì)所有0，都有(1(00，因而()(0)

()d(0)，0 1當(dāng)時(shí)，可推得(f(xA.令|0[0,0.由的定義及(的連續(xù)性，必有(1(0，故0()1(0)(0)，再由()10[1,1]0()(0)，從而有

()(0)

或f(xkdk)Tdk

f(xk)Tdk，(,1].再由(1(00，可得()(0)()d(0)，0 1故有((01(0(0(0，由(的連續(xù)性知，存在20，當(dāng)[2,2時(shí)，有()(0)(0)f(xkdk)f(xkf(xk)Tdk.令min{1,2}，則當(dāng)[,時(shí)，準(zhǔn)則(3.4.1)和(3.4.4)同時(shí)成立.1(0,12),，令a0，計(jì)算(a和(a，給定初始試探點(diǎn)0a，置k0.2：計(jì)算(k，若(k(0k(03；否則計(jì)算(a，并取k1

(a)2'(a)kk)(a)'(a)(kk

，a)]令bk4.3：計(jì)算'(k，若(k(0，則停止迭代并輸出k；否則，如果(ka)((k)(a))0，則取

ka

()，kk

k (

)(a) kak，(a)(k)；否則，當(dāng)右邊界b未定時(shí)，取k1kh，并令h2*h；當(dāng)右邊界b已定時(shí)，取k1kb2.4：令kk12.注這里k的迭代用了兩點(diǎn)二次插值公式，主要是考慮到插值法的局部超線性收斂性，以及單步計(jì)算成本低廉的特性.時(shí)，有

(k)(0)k(0)，a0，則顯然滿足(k1(ka0，則由程序步驟可知，這時(shí)(a)(0)0,(a)(0)a(0)，故由和ka可知(k)(a)(0)(ka)(0)(

ka)(a)(0)(k

a)(a)，仍然滿足(k1)(k)的條件，且保證k1a.二(k)(0)k(0)，(k)(0)0，因此，非凸函數(shù)并不一定滿足(k1)(k)的條件，也不能保證k1k.為此，在程序中我們加入了(ka)((k(a大于零與否的判定條件.簡(jiǎn)單準(zhǔn)則和后退方法在牛頓類算法中，我們有時(shí)僅采用Armijo準(zhǔn)則f(xkkdk)f(xk)kf(xk)Tdk， (3.4.1)k.其基本思想是置1，若xkdk3.4.，則令，繼續(xù)檢k3.4.xkdk34.1011/2.不精確一維搜索的收斂性定理kdk與f(xk的夾角/2對(duì)每個(gè)kk(0,2)是常數(shù).定理3.4.2設(shè)在下降算法2.1中步長(zhǎng)k滿足Armijo-Goldstein準(zhǔn)則或Wolfe-Powell準(zhǔn)則，0若f(xLx|f(xf(x)上一致連續(xù)，則或者對(duì)某個(gè)k有f(xk0，或者有l(wèi)imf(xk，或者有l(wèi)im||f(xk||0.0k k證若對(duì)某個(gè)k有f(xk0，或者有l(wèi)imf(xk，則結(jié)論成立.故不妨設(shè)對(duì)任意kk都有f(xk0且下降序列f(xk)}有下界，因此limf(xk存在，從而有klim[f(xk1)f(xk)]0，kk于是，由Armijof(xk)Tdk0(k.k下面用反證法證明lim||f(xk||0.k假設(shè)lim||f(xk||00KkK都k 1 1有f(xk)

成立，故對(duì)任意kK1，由k/2，有coskcos(2)sin，再由k f