應(yīng)用數(shù)學(xué)-我光盤課件

第三章 最速下降法和法最速下降方法及其法及其修正 法及其實(shí)現(xiàn)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.1實(shí)現(xiàn)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2實(shí)現(xiàn)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1023ii第三章 最速下降法和法本章無約束優(yōu)化問題min

??(??)

(3.1)??∈R??的最速下降法和 法及其改進(jìn)算法.

其中最速下降法是求解無約束優(yōu)化問題最簡單和最古老的方法之一,

雖然時(shí)至今日它不再具有實(shí)用性,

但它卻研究其它無約束優(yōu)化算法的基礎(chǔ),

許多有效算法都是以它基礎(chǔ)通過改進(jìn)或修正而得到的.

此外,

法也是一種經(jīng)典的無約束優(yōu)化算法,

并且因其收斂速度快以及具有自適應(yīng)性等優(yōu)點(diǎn)而至今仍受到科技工作者的青睞.1第三章 最速下降法和

法回3.1

最速下降方法及其實(shí)現(xiàn)3.1

最速下降方法及其 實(shí)現(xiàn)在第2

章關(guān)于無約束優(yōu)化問題下降類算法的一般框架時(shí)提及,用不同的方式確定搜索方向或搜索步長,就會(huì)得到不同的算法.最速下降法是用負(fù)梯度方向????

=

????(????)

(3.2)作為搜索方向的(因此也稱為梯度法).設(shè)??(??)在????

附近連續(xù)可微,????

為搜索方向向量,

????

=

???(????).

由

展開式得??(????

+

??????)

=

??(????)

+

??????

????

+

??(??),

??

>

0.??那么目標(biāo)函數(shù)??(??)在????

處沿方向????

下降的變化率為??→0????→0lim

=lim

??

??(????

+

??????)

?

??(????)

??????

????

+

??(??)????=

????????

=

‖????‖‖????‖

cos

??ˉ??,其中

??ˉ

是??

與????

??

??

??的夾角.顯然,對(duì)于不同的方向??

,函數(shù)變化率取決于它與????

夾角的余弦值.

要使變化率最小,

只有cos

??ˉ

=

?1,

即

??ˉ

=

??

時(shí)才??

??·2

·第三章 最速下降法和

法

回

3.1

最速下降方法及其 實(shí)現(xiàn)能達(dá)到,亦即????

應(yīng)該取(3.2)中的負(fù)梯度方向,這也是將負(fù)梯度方向叫作最速下降方向的由來.下面給出最速下降法的具體計(jì)算步驟.算法3.1

(最速下降法)步

0

選取初始點(diǎn)??0

∈

R??,

容許誤差

0

≤

??

?

1.

令??

:=

1.步

1

計(jì)算

????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出

????

作為近似最優(yōu)解.步

2

取方向????

=

?????.步

3

由線搜索技術(shù)確定步長因子????.步

4

令????+1

:=

????

+

????????,

??

:=

??

+

1,

轉(zhuǎn)步

1.說3

中步長因子????

的確定即可使用精確線搜索方法,也可以使用非精確線搜索方法,在理論上都能保證其全局收斂性.若采用精確線搜索方法,即??≥0??(????

+

????????)

=

min

??(????

+

??????),·3

·回3.1

最速下降方法及其實(shí)現(xiàn)法第三章 最速下降法和那么????

應(yīng)滿足d????′(??)=

d

??(??????+

????

)|??=??

?????? ??

????=

???(??

+

??

??

)

??

=

0.由(3.2)有?????(????+1)

???(????)

=

0,即新點(diǎn)????+1

處的梯度與舊點(diǎn)????

處的梯度是正交的,也就是說迭代點(diǎn)列所走的路線是鋸齒型的,故其收斂速度是很緩慢的(至多線性收斂速度).由????

=?????

及(2.16),即?????????

?????(?????)????‖‖????‖

‖????‖‖

?

????‖??????????

=

‖??=

??

=

1,

? ????

=

0,故條件(2.15)必然滿足(0

≤????

≤??

???,??

>0).從而直接應(yīng)用定理2.22和定理2.3

即得到最速下降法的全局收斂性定理:定理

3.1

設(shè)目標(biāo)函數(shù)??(??)

連續(xù)可微且其梯度函數(shù)???(??)

是

Lipschitz連續(xù)的,{??

??

}由最速下降法產(chǎn)生,其中步長因子????

由精確線搜索,或由·4

·3.1

最速下降方法及其實(shí)現(xiàn)第三章 最速下降法和

法

回Wolfe

準(zhǔn)則,或由Armijo

準(zhǔn)則產(chǎn)生.則有l(wèi)im

‖???(????)‖

=

0.??→∞下面的定理給出了最速下降法求解嚴(yán)格凸二次函數(shù)極小值問題時(shí)的收斂速度估計(jì),其證明可參閱有關(guān)文獻(xiàn),此處省略不證.定理

3.2

設(shè)矩陣??

∈

R??×??

對(duì)稱正定,

??

∈

R??.

記

??1

和

????

分別是??

最大和最小特征值,??

=??1/????.考慮如下極小化問題min

??(??)

=

????

??

+

1????

????.2設(shè)

{

??

??

}

是用精確線搜索的最速下降法求解上述問題所產(chǎn)生的迭代序列,則對(duì)于所有的??,下面的不等式成立*‖????+1

?

??

‖??

≤(?

??

?

1)???

+

1*‖????

?

??

‖??

,(3.3)√其中,

??*

是問題的唯一解,

‖??‖??

=

????

????.·5

·第三章 最速下降法和

法

回

3.1

最速下降方法及其 實(shí)現(xiàn)由上面的定理可以看出,若條件數(shù)??

接近于1(即??

的最大特征值和最小特征值接近時(shí)),最速下降法是收斂很快的.但當(dāng)條件數(shù)??

較大時(shí)(即??

近似于下面時(shí)),算法的收斂速度是很緩慢的.給出基于Armijo

非精確線搜索的最速下降法程序.程序3.1

(最速下降法程序)f

unct

i

on [

x

,

val

,

k]

=gr

ad(

f

un,

gf

un,

x

0

)%功能:%輸入:%輸出:用最速下降法求解無約束問題:

min f

(

x

)x0是初始點(diǎn), f

u

n

,

gfun分別是目標(biāo)函數(shù)和梯度x,

val

分別是近似最優(yōu)點(diǎn)和最優(yōu)值,

k是迭代次數(shù).maxk=5000;

%最大迭代次數(shù)rho=

0

.

5

;

sigma=

0

.

4

;k=0;

epsilon=

1

e

-

5;while(

k?maxk)g=f

eval(gfun,x

0);

%計(jì)算梯度d=-g;

%計(jì)算搜索方向·6

·實(shí)現(xiàn)第三章 最速下降法和

法

回

3.1

最速下降方法及其i

f

(

n

o

r

m

(

d

)

?

e

p

s

i

l

o

n

)

,

br

eak;

endm=0;

mk=0;while(m?20) %Armijo搜索if(feval(fun,x0+rho^m*d)?feval(fun,x0)+sigma*rho^m*g’*d)mk=m;

br

eak;endm=m+1;endx0=x0+rho^mk*d;k=k+1;endx=x0;val=f

eval(

f

un,

x

0

)

;·7

·實(shí)現(xiàn)第三章 最速下降法和

法

回

3.1

最速下降方法及其例3.1

利用程序3.1

求解無約束優(yōu)化問題??∈R21min

??(??)

=

100(??2

?

??2)2

+

(??1

?

1)2.該問題有精確解??*

=(1,1)??

,??(??*)=0.解首先建立兩個(gè)分別計(jì)算目標(biāo)函數(shù)和梯度的m

文件:f

unct

i

on

f=fun(

x)f=

100

*(

x(

1

)

^

2

-

x(

2

)

)

^

2

+(

x(

1

)

-

1

)

^

2

;f

unct

i

on

g=gfun(

x)g=[

400*

x(

1)*(

x(

1)

^

2

-

x(

2

)

)

+

2

*(

x(

1

)

-

1

)

,-200*(

x(

1)

^

2

-

x(

2))]’;利用程序3.1,

終止準(zhǔn)則取為‖???(????)‖≤10?5.取不同的初始點(diǎn),數(shù)值結(jié)果如下表.表3.1

最速下降法的數(shù)值結(jié)果.·8

·第三章 最速下降法和法回3.1

最速下降方法及其實(shí)現(xiàn)初始點(diǎn)(??0)迭代次數(shù)(??)目標(biāo)函數(shù)值(??(????))(0.0,

0.0)??11591.1630

×

10?10(2.0,

1.0)??6111.1416

×

10?10(1.0,

?1.0)??15511.2251

×

10?10(?1.0,

?1.0)??14999.2536

×

10?11(?1.2,

1)??14351.1985

×

10?10(10,

?10)??10241.0156

×

10?10·9

·由上表可以看出,最速下降法的收斂速度是比較緩慢的.說明上述程序的調(diào)用方式是:x

0

=[-

1

.

2

1]’;[x,val,k]=grad(’fun’,’gfun’,x0)其中fun,gfun

分別是求目標(biāo)函數(shù)值及其梯度的M

函數(shù)文件.第三章 最速下降法和法回3.2法及其實(shí)現(xiàn)3.2跟最速下降法一樣,法及其 實(shí)現(xiàn)法也是求解無約束優(yōu)化問題最早使用的經(jīng)典算法之一.其基本思想是用迭代點(diǎn)????

處的一階導(dǎo)數(shù)(梯度)和二階導(dǎo)數(shù)

(Hesse陣)對(duì)目標(biāo)函數(shù)進(jìn)行二次函數(shù)近似,然后把二次模型的極小點(diǎn)作為新的迭代點(diǎn),并不斷重復(fù)這一過程,直至求得滿足精度的近似極小點(diǎn).下面來推導(dǎo)

法的迭代公式.

設(shè)

??(??)

的

Hesse

陣

??(??)

=

?2??(??)連續(xù),截取其在????

處的展開式的前三項(xiàng)得??

??????

??

??1??

(??)

=

??

+

????

(??

?

????)

+

2(??

?

??

)??

??

(??

?

??

),其中????

=??(????),????

=???(????),????

=?2??(????).求二次函數(shù)????(??)的穩(wěn)定點(diǎn),得?????(??)

=

????

+

????(??

?

????)

=

0.若

????

非奇異,

那么解上面的線性方程組

(記其解為

????+1)

即得

法的迭代公式????+1

=

????

?

???1

????

.

(3.4)??·10

·第三章 最速下降法和法回3.2法及其實(shí)現(xiàn)在迭代公式(3.4)中每步迭代需要求Hesse

陣的逆???1

,在實(shí)際計(jì)算中可??通過先解??????

=?????

得????,然后令????+1

=????

+????

來避免求逆.這樣,可以寫出基本

法的步驟如下:算法

3.2

(基本 法)步

0

給定終止誤差值

0

≤

??

?

1,

初始點(diǎn)??0

∈

R??.

令??

:=

0.步

1

計(jì)算????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出??*

≈

????.步

2

計(jì)算

????

=

?2??(????),

并求解線性方程組得解????:??????

=

?????.步

3

令????+1

=

????

+

????,

??

:=

??

+

1,

轉(zhuǎn)步

1.法最突出的優(yōu)點(diǎn)是收斂速度快，具有局部二階收斂性.下面的定理表明了這一性質(zhì).定理

3.3

設(shè)函數(shù)

??(??)

有二階連續(xù)偏導(dǎo)數(shù),

在局部極小點(diǎn)

??*

處,??(??*)=?2??(??*)是正定的且??(??)在??*

的一個(gè)鄰域內(nèi)是Lipschitz

連續(xù)·11

·第三章 最速下降法和

法

回的.如果初始點(diǎn)??0

充分靠近??*,那么對(duì)一切??,3.2

法及其 實(shí)現(xiàn)迭代公式(3.4)是適4??定的,并當(dāng){??

??

}為無窮點(diǎn)列時(shí),其極限為??*,且收斂階至少是二階的.證由??(??*)的正定性及??

二次連續(xù)可微可知,存在??*

的一個(gè)鄰域

??(??*),

使得對(duì)任意的

??

∈

??(??*),

都有

??(??)

是一致正定的.

特別地,‖??(??)?1‖

在

??1(??*)

上有界,

即存在常數(shù)

??

≥

0,

使得

‖??(??)?1‖

≤

??,???

∈??1(??*).又由??(??)的連續(xù)性可知,存在鄰域??(??*),使得1

1‖??(??)

?

??(??*)‖

≤

,

???

∈

??(??*)

?

??

(??*).·12

·回3.2法及其實(shí)現(xiàn)第三章 最速下降法和

法因此,當(dāng)??0

∈??(??*)時(shí),有‖??1

?

??*‖0=

‖??0

?

??*

?

???1??0‖0≤

‖???1‖‖??(??0)

?

??(??*)

?

??0(??0

?

??*)‖?1∫??10? ??(??*

***+

??(??

?

??

))(??

?

??

)d??

?

??

0(??0

?

??

)≤

‖??0

‖∫?1*

*

*≤

??

‖??(??

+

??(??0

?

??

))

?

??(??

0)‖‖??0

?

??

‖d??≤

??(?∫?01‖??(??*

+

??(??0

?

??*))

?

??(??

*)‖d??∫?00+)?*

*1‖??(??0)

?

??(??

)‖d??

‖??0

?

??

‖0≤

1‖??

?

??*‖.2(3.5)上式特別說明,??1

∈??(??*).類似地,利用歸納法原理,可證明對(duì)于所有的·13

·回3.2法及其實(shí)現(xiàn)法第三章 最速下降法和??

≥1

有??+1‖??

?

??*‖

≤2‖??1??—

??*‖.因此{(lán)??

??

}???(??*),且????

→??*

(??

→∞).進(jìn)一步,類似于(3.5)的推導(dǎo),可得∫?10‖????+1

?

??*‖

≤

??

‖??(??*

+

??(????

?

??*))

?

??(??

??)‖‖????

?

??*‖d??*=

??(‖????

?

??

‖),即{??

??

}超線性收斂于??*.若??(??)在??*

的一個(gè)鄰域內(nèi)Lipschitz

連續(xù),則·14

·回3.2法及其實(shí)現(xiàn)法第三章 最速下降法和由上式得‖????+1

?

??*‖

≤

??(?

∫?10∫?0‖??(??*

+

??(????

?

??*))

?

??(??*)‖d??)?*

*1‖??(??

)

?

??(??

??)‖d??

‖????

?

??

‖1

)???d??

+

10+(?∫?≤

????‖????

?

??

‖*

22=??3????

‖??

?

??*‖2,即{

??

??

}

二次收斂于??*.

證畢.

口上述定理

,

初始點(diǎn)需要足夠“靠近”極小點(diǎn),

否則有可能導(dǎo)致算法不收斂.

由于實(shí)際問題的精確極小點(diǎn)一般是不知道的,

因此初始點(diǎn)的選取給算法的實(shí)際操作帶來了很大的

.

為了克服這一索技術(shù)以得到大范圍收斂的算法,

即所謂的阻尼 法.,可引入線搜給出一個(gè)基于Armijo

搜索的阻尼

法如下:·15

·第三章 最速下降法和

法回3.2法及其實(shí)現(xiàn)算法

3.3

(阻尼 法)步

0

給定終止誤差值

0

≤

??

?

1,

??

∈

(0,

1),

??

∈

(0,

0.5).

初始點(diǎn)??0

∈R??.令??

:0.步

1

計(jì)算????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出??*

≈

????.步

2

計(jì)算

????

=

?2??(????),

并求解線性方程組得解????:??????

=

?????步

3

記????

是滿足下列不等式的最小非負(fù)整數(shù)??:(3.6)????(????

+

????????)

≤

??(????)

+

??????????

????.(3.7)步

4

令????

=

??????,

????+1

=

????

+

????????,

??

:=

??

+

1,

轉(zhuǎn)步

1.給出算法3.3

的全局收斂性定理如下:定理

3.4

設(shè)函數(shù)??(??)

二次連續(xù)可微且存在常數(shù)??

>

0,

使得????

?2??(??)??

≥

??‖??‖2,

???

∈

R??,

??

∈

??(??0),(3.8)·16

·第三章 最速下降法和

法

回

3.2

法及其 實(shí)現(xiàn)其中

??(??0)

=

{??|??

(??)

≤

??(??0)}.

設(shè)

{

??

??

}

是由算法

3.3

產(chǎn)生的無窮點(diǎn)列,則該點(diǎn)列收斂于??

在水平集??(??0)中的唯一全局極小點(diǎn).證由條件(3.8)知,??

是水平集??(??0)上的一致凸函數(shù),因此一定存在唯一的全局極小點(diǎn)??*,且??*

是???(??)=0

的唯一解.由于??

是凸函數(shù),故水平集??(??0)是一個(gè)有界閉凸集.注意到算法3.3的步3,序列{??(????)}是單調(diào)下降的.故顯然有{??

??

}???(??0).由(3.6)和(3.8)不難得到‖????‖

≤

??‖????‖,其中??

>0

是某個(gè)常數(shù).設(shè)??ˉ

是{??

??

}的任意一個(gè)極限點(diǎn),則有????

→??

(??ˉ).??記

????

是負(fù)梯度方向

?????

與

方向

????

=

????1????

的夾角.

由上式和(3.6),(3.8)可推得cos

????

=?????????

????

??????????

??=

≥

??‖????‖2‖????‖‖????‖

‖????‖‖????‖

‖????‖‖????‖=??‖????‖

≥

??‖????‖

??>

0.·17

·回3.2法及其實(shí)現(xiàn)第三章 最速下降法和

法則由定理2.2

可得??→∞lim

????

=

0,即{

??

??

}

的極限點(diǎn)都是穩(wěn)定點(diǎn).

由??

的凸性知,

穩(wěn)定點(diǎn)亦即(全局)

極小點(diǎn).故由極小點(diǎn)的唯一性知,

{

??

??

}

收斂于??

在水平集??(??0)

上的全局極小點(diǎn).證畢. 口為了分析算法3.3

的收斂速度,需要用到下面的引理,其詳細(xì)的證明過程可參見文獻(xiàn)[4].引理

3.1

設(shè)函數(shù)

??

:

R??

→

R

二次連續(xù)可微,

點(diǎn)列

{

??

??

}

由算法

3.3產(chǎn)生.設(shè){??

??

}→??*

且??(??*)=0,??(??*)正定.那么,若lim??→∞‖??(????)????

+

????‖

=

0,‖????‖(3.9)則(1)當(dāng)??

充分大時(shí),步長因子????

≡1.(2)點(diǎn)列{??

??

}超線性收斂于??*.定理3.5

設(shè)定理3.4

的條件成立,點(diǎn)列{??

??

}由算法3.3

產(chǎn)生.則{??

??

}超線性收斂于??

的全局極小點(diǎn)??*.此外,若Hesse

陣??(??)在??*

處Lipschitz

連續(xù),則收斂階至少是二階的.·18

·第三章 最速下降法和

法

回

3.2

法及其 實(shí)現(xiàn)證

定理

3.4

已證明

{

??

??

}

→

??*

且

??(??*)

=

???(??*)

=

0.

又由算法3.3

的步

2

顯然有條件

(3.9)

成立.

故由引理

3.1(1)

可知對(duì)于充分大的

??,????

=1

滿足算法中的線搜索式.因此,由定理3.3

立即得到{??

??

}至少二階收斂于??*.證畢.下面 給出基于Armijo

非精確線搜索的阻尼法口.程序.程序

3.2

(阻尼 法程序)f

unction [

x,

val,

k]

=dampnm(

fun,

gfun,

Hess,

x0)%功能:

用阻尼 法求解無約束問題:

min f

(

x

)%輸入:%%輸出:x0是初始點(diǎn), f

u

n

,

gf

un,

Hess

分別是求目標(biāo)函數(shù)值,

梯度,

Hesse

陣的函數(shù)x,

val

分別是近似最優(yōu)點(diǎn)和最優(yōu)值,

k是迭代次數(shù).maxk=100;%給出最大迭代次數(shù)rho=

0

.

55

;

sigma=0

.4

;k=0;

epsilon=

1

e

-

5;while(

k?maxk)·19

·實(shí)現(xiàn)第三章 最速下降法和

法

回

3.2

法及其gk=f

eval(gfun,x

0);

%計(jì)算梯度Gk=feval(Hess,x0);

%計(jì)算Hesse陣dk=-Gk“gk;

%解方程組Gk*dk=-gk,

計(jì)算搜索方向i

f(n

o

r

m(g

k)?e

p

s

i

l

o

n),

br

eak;

end

%檢驗(yàn)終止準(zhǔn)則m=0;

mk=0;while(m?20)

%用Armijo搜索求步長if(

feval(

fun,x0+rho^m*dk)?feval(

fun,x0)

+sigma*rho^m*gk’*dk)mk=m;

br

eak;endm=m+1;endx0=x0+rho^mk*dk;k=k+1;endx=x0;·20

·回3.2法及其實(shí)現(xiàn)第三章 最速下降法和

法v

a

l

=

f

e

v

a

l

(

f

u

n

,

x

)

;例3.2

利用程序3.2

求解無約束優(yōu)化問題??∈R21min

??(??)

=

100(??2

?

??2)2

+

(??1

?

1)2.該問題有精確解??*

=(1,1)??

,??(??*)=0.解除了例3.1

中建立的兩個(gè)計(jì)算目標(biāo)函數(shù)和梯度的m

文件之外,還需建立求Hesse

陣的m

文件:f

unction

He=Hess(x)n=l

engt

h(

x);He=zeros(

n,

n);He=[

1200*x(

1)

^2-

400*x(2)+2, -

400

*

x(

1

)

;-

400

*

x(

1

)

,

200

];利用程序3.2,終止準(zhǔn)則取為‖???(????)‖≤10?5.取不同的初始點(diǎn),數(shù)值結(jié)果如下表.·21

·第三章 最速下降法和法回3.2法及其實(shí)現(xiàn)表3.2

阻尼法的數(shù)值結(jié)果.初始點(diǎn)(??0)迭代次數(shù)(??)目標(biāo)函數(shù)值(??(????))(0,

0)??139.6238

×

10?15(0.5,

0.5)??113.5183

×

10?19(2,

2)??141.6322

×

10?14(?1,

?1)??203.6221

×

10?17(1,

10)??14.9309

×

10?28(10,

10)??473.3426

×

10?17(20,

20)??733.0386

×

10?17由上表可以看出,

阻尼 法的收斂速度是比較令人滿意的.說明上述程序的調(diào)用方式是:x

0

=[-

1.

2

1]’;·22

·法及其實(shí)現(xiàn)第三章 最速下降法和

法

回

3.3

修正[x,val,k]=dampnm(’fun’,’gfun’,’Hess’,x0)其中fun,gfun,Hess

分別是求目標(biāo)函數(shù)值和它的梯度及其Hesse

陣的M

函數(shù)文件.3.3

修正 法及其 實(shí)現(xiàn)從上一節(jié)的分析可知,

法具有不低于二階的收斂速度,

這是它的優(yōu)點(diǎn).

但該算法要求目標(biāo)函數(shù)的

Hesse

陣

??(??)

=

?2??(??)

在每個(gè)迭代點(diǎn)????

處是正定的,

否則難以保證 方向????

=

????1????

是??

在????

處的下降方向.

為克服這一缺陷,

可對(duì) 法進(jìn)行修正.??修正的途徑之一是將牛頓法和最速下降法結(jié)合起來,構(gòu)造所謂的“基本思想是:當(dāng)?2??(????)正定時(shí),采用-最速下降混合算法”,其方向作為搜索方向;否則,若?2??(????)

奇異,

或者雖然非奇異但 方向不是下降方向,

則采用負(fù)梯度方向作為搜索方向.

寫出詳細(xì)的計(jì)算步驟如下:算法3.4

(-最速下降混合算法)·23

·第三章 最速下降法和

法

回

3.3

修正 法及其 實(shí)現(xiàn)步

0

給定初始點(diǎn)??0

∈

R??,

終止誤差

0

≤

??

?

1.

令??

:=

0.3.4

產(chǎn)生的迭代序列,且存在{??

??

}的一個(gè)極限點(diǎn)??*,使得??(??*)正定.則·24

·步

1

計(jì)算

????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出

????

作為近似極小點(diǎn).步

2

計(jì)算

????

=

?2??(????).

解方程組??????

+

????

=

0.(3.10)若(4.10)有解????

且滿足????

????

<0,轉(zhuǎn)步3;否則,令????

=?????

轉(zhuǎn)步3.??步

3

由線搜索技術(shù)確定步長因子????.步

4

令????+1

=

????

+

????????,

??

:=

??

+

1,

轉(zhuǎn)步

1.對(duì)于算法3.4,利用定理2.2,

定理2.3

以及引理3.1

不難證明下面的收斂性定理.定理3.6

設(shè)對(duì)任意的??0

∈R??,水平集??(??0)={??

|

??

(??)≤??

(??0)}有界,且函數(shù)??

在包含??(??0)的一個(gè)有界閉凸集上二次連續(xù)可微.{??

??

}由采用精確線搜索,或Wolfe

準(zhǔn)則,或Armijo

準(zhǔn)則確定步長因子的算法第三章 最速下降法和法回3.3

修正法及其實(shí)現(xiàn)有l(wèi)im inf

‖????‖

=

0,??→∞以及

{

??

??

}

超線性收斂于

??*.

進(jìn)一步,

若

??(??)

在

??*

處是

Lipschitz

連續(xù)的,則收斂速度至少是二階的.上述的修正 法克服了 法要求

Hesse

陣

??(????)

=

?2??(????)

正定的缺陷.

克服這一缺陷還有其它的方法和途徑.

例如,

引進(jìn)阻尼因子????

≥0,即在每一迭代步適當(dāng)?shù)剡x取參數(shù)????

使得矩陣????

=??(????)+??????正定.

寫出算法步驟如下:算法

3.5

(修正 法)步

0

給定參數(shù)??

∈

(0,

1),

??

∈

[0,

1],

??

∈

(0,

0.5),

終止誤差

0

≤

??

?

1.初始點(diǎn)??0

∈R??.令??

:=0.步

1

計(jì)算

????

=

???(????),

????

=

‖????‖1+??.

若

‖????‖

≤

??,

停算,

輸出

????作為近似極小點(diǎn).·25

·法及其實(shí)現(xiàn)第三章 最速下降法和

法

回

3.3

修正步

2

計(jì)算

Hesee

陣

????

=

?2??(????).

解線性方程組(????

+

??????)??

=

?????,得解????.步

3

令????

是滿足下列不等式的最小非負(fù)整數(shù)??:(3.11)????(????

+

????????)

≤

??(????)

+

??????????

????.(3.12)令????

=??????,????+1

:=????

+????????.步

4

令??

:=

??

+

1,

轉(zhuǎn)步

1.下面的定理給出了算法3.5

的全局收斂性,其證明可參看文獻(xiàn)[4].定理

3.7

設(shè)函數(shù)

??

:

R??

→

R

有下界且二次連續(xù)可微,

??(??)

=?2??(??)半正定且Lipschitz

連續(xù).則由算法3.5

產(chǎn)生的迭代序列{??

??

}的任何極限點(diǎn)都是問題(3.1)的解.已有研究證明,當(dāng)目標(biāo)函數(shù)的Hesse

陣??(??)=?2??(??)在極小點(diǎn)??*處奇異時(shí),法的收斂速度可能會(huì)降低為線性收斂速度.下面給出奇異解的概念.·26

·第三章 最速下降法和

法

回

3.3

修正 法及其 實(shí)現(xiàn)定義

3.1

若在問題(3.1)

的極小點(diǎn)??*

處

Hesse

陣

??(??*)

奇異,

則稱??*

是問題(3.1)的奇異解.當(dāng)問題(3.1)有奇異解時(shí),其解可能不唯一,此時(shí)集,即??

=

{??*

|??(??*)

=

min

??(??),

??

∈

R??}.用??

表示其解定義

3.2

設(shè)??*∈

??

,

函數(shù)??

:R??

→R+.

若存在??*的鄰域??(??*)

及常數(shù)??

>

0,

使得??(??)

≥

??dist(??,

??

)

,

??

∈

??(??*),

(3.13)其中

dist(??,

??

)

表示點(diǎn)

??

到集合??

的距離,

則稱函數(shù)??

在鄰域??(??*)

內(nèi)對(duì)問題(3.1)

解集合??

提供了一個(gè)局部誤差界.下面的定理給出了算法3.5

的局部收斂速度的估計(jì),其證明可參看文獻(xiàn)[?].·27

·第三章 最速下降法和

法

回

3.3

修正 法及其

實(shí)現(xiàn)定理

3.8

設(shè)定理

3.7

的條件成立.

若由算法

3.5

產(chǎn)生的迭代序列{??

??

}有子列{????

:??

∈??

}收斂于??*

∈??

,且函數(shù)‖??(??)‖在??*

的某鄰域內(nèi)對(duì)問題(3.1)提供了一個(gè)局部誤差界,則當(dāng)??

∈??

充分大時(shí),????

≡1,且子列{????

:??

∈??

}二階收斂于??*,即存在常數(shù)??

>0

使得dist(????+1,

??

)

≤

??dist(????,

??)

2

.下面

給出算法

3.5

(修正 法)

的

程序.程序

3.3

(修正

法 程序)f

unct

i

on [

x,

val,

k]

=revisenm(

fun,

gfun,

Hess,

x

0

)%

功能:

用修正

法求解