第三章 最速下降法和法最速下降方法及其法及其修正 法及其實現

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.1實現

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

2實現

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

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

??(??)

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

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

雖然時至今日它不再具有實用性,

但它卻研究其它無約束優化算法的基礎,

許多有效算法都是以它基礎通過改進或修正而得到的.

此外,

法也是一種經典的無約束優化算法,

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

法回3.1

最速下降方法及其實現3.1

最速下降方法及其 實現在第2

章關于無約束優化問題下降類算法的一般框架時提及,用不同的方式確定搜索方向或搜索步長,就會得到不同的算法.最速下降法是用負梯度方向????

=

????(????)

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

附近連續可微,????

為搜索方向向量,

????

=

???(????).

由

展開式得??(????

+

??????)

=

??(????)

+

??????

????

+

??(??),

??

>

0.??那么目標函數??(??)在????

處沿方向????

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

=lim

??

??(????

+

??????)

?

??(????)

??????

????

+

??(??)????=

????????

=

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

cos

??ˉ??,其中

??ˉ

是??

與????

??

??

??的夾角.顯然,對于不同的方向??

,函數變化率取決于它與????

夾角的余弦值.

要使變化率最小,

只有cos

??ˉ

=

?1,

即

??ˉ

=

??

時才??

??·2

·第三章 最速下降法和

法

回

3.1

最速下降方法及其 實現能達到,亦即????

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

(最速下降法)步

0

選取初始點??0

∈

R??,

容許誤差

0

≤

??

?

1.

令??

:=

1.步

1

計算

????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出

????

作為近似最優解.步

2

取方向????

=

?????.步

3

由線搜索技術確定步長因子????.步

4

令????+1

:=

????

+

????????,

??

:=

??

+

1,

轉步

1.說3

中步長因子????

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

+

????????)

=

min

??(????

+

??????),·3

·回3.1

最速下降方法及其實現法第三章 最速下降法和那么????

應滿足d????′(??)=

d

??(??????+

????

)|??=??

?????? ??

????=

???(??

+

??

??

)

??

=

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

???(????)

=

0,即新點????+1

處的梯度與舊點????

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

=?????

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

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

‖????‖‖

?

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

=

‖??=

??

=

1,

? ????

=

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

≤????

≤??

???,??

>0).從而直接應用定理2.22和定理2.3

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

3.1

設目標函數??(??)

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

是

Lipschitz連續的,{??

??

}由最速下降法產生,其中步長因子????

由精確線搜索,或由·4

·3.1

最速下降方法及其實現第三章 最速下降法和

法

回Wolfe

準則,或由Armijo

準則產生.則有lim

‖???(????)‖

=

0.??→∞下面的定理給出了最速下降法求解嚴格凸二次函數極小值問題時的收斂速度估計,其證明可參閱有關文獻,此處省略不證.定理

3.2

設矩陣??

∈

R??×??

對稱正定,

??

∈

R??.

記

??1

和

????

分別是??

最大和最小特征值,??

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

??(??)

=

????

??

+

1????

????.2設

{

??

??

}

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

?

??

‖??

≤(?

??

?

1)???

+

1*‖????

?

??

‖??

,(3.3)√其中,

??*

是問題的唯一解,

‖??‖??

=

????

????.·5

·第三章 最速下降法和

法

回

3.1

最速下降方法及其 實現由上面的定理可以看出,若條件數??

接近于1(即??

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

較大時(即??

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

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

(最速下降法程序)f

unct

i

on [

x

,

val

,

k]

=gr

ad(

f

un,

gf

un,

x

0

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

min f

(

x

)x0是初始點, f

u

n

,

gfun分別是目標函數和梯度x,

val

分別是近似最優點和最優值,

k是迭代次數.maxk=5000;

%最大迭代次數rho=

0

.

5

;

sigma=

0

.

4

;k=0;

epsilon=

1

e

-

5;while(

k?maxk)g=f

eval(gfun,x

0);

%計算梯度d=-g;

%計算搜索方向·6

·實現第三章 最速下降法和

法

回

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

·實現第三章 最速下降法和

法

回

3.1

最速下降方法及其例3.1

利用程序3.1

求解無約束優化問題??∈R21min

??(??)

=

100(??2

?

??2)2

+

(??1

?

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

=(1,1)??

,??(??*)=0.解首先建立兩個分別計算目標函數和梯度的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,

終止準則取為‖???(????)‖≤10?5.取不同的初始點,數值結果如下表.表3.1

最速下降法的數值結果.·8

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

最速下降方法及其實現初始點(??0)迭代次數(??)目標函數值(??(????))(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

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

0

=[-

1

.

2

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

分別是求目標函數值及其梯度的M

函數文件.第三章 最速下降法和法回3.2法及其實現3.2跟最速下降法一樣,法及其 實現法也是求解無約束優化問題最早使用的經典算法之一.其基本思想是用迭代點????

處的一階導數(梯度)和二階導數

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

法的迭代公式.

設

??(??)

的

Hesse

陣

??(??)

=

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

處的展開式的前三項得??

??????

??

??1??

(??)

=

??

+

????

(??

?

????)

+

2(??

?

??

)??

??

(??

?

??

),其中????

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

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

=?2??(????).求二次函數????(??)的穩定點,得?????(??)

=

????

+

????(??

?

????)

=

0.若

????

非奇異,

那么解上面的線性方程組

(記其解為

????+1)

即得

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

=

????

?

???1

????

.

(3.4)??·10

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

陣的逆???1

,在實際計算中可??通過先解??????

=?????

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

=????

+????

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

法的步驟如下:算法

3.2

(基本 法)步

0

給定終止誤差值

0

≤

??

?

1,

初始點??0

∈

R??.

令??

:=

0.步

1

計算????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出??*

≈

????.步

2

計算

????

=

?2??(????),

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

=

?????.步

3

令????+1

=

????

+

????,

??

:=

??

+

1,

轉步

1.法最突出的優點是收斂速度快，具有局部二階收斂性.下面的定理表明了這一性質.定理

3.3

設函數

??(??)

有二階連續偏導數,

在局部極小點

??*

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

的一個鄰域內是Lipschitz

連續·11

·第三章 最速下降法和

法

回的.如果初始點??0

充分靠近??*,那么對一切??,3.2

法及其 實現迭代公式(3.4)是適4??定的,并當{??

??

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

二次連續可微可知,存在??*

的一個鄰域

??(??*),

使得對任意的

??

∈

??(??*),

都有

??(??)

是一致正定的.

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

在

??1(??*)

上有界,

即存在常數

??

≥

0,

使得

‖??(??)?1‖

≤

??,???

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

1‖??(??)

?

??(??*)‖

≤

,

???

∈

??(??*)

?

??

(??*).·12

·回3.2法及其實現第三章 最速下降法和

法因此,當??0

∈??(??*)時,有‖??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

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

·回3.2法及其實現法第三章 最速下降法和??

≥1

有??+1‖??

?

??*‖

≤2‖??1??—

??*‖.因此{??

??

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

→??*

(??

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

?

??*‖

≤

??

‖??(??*

+

??(????

?

??*))

?

??(??

??)‖‖????

?

??*‖d??*=

??(‖????

?

??

‖),即{??

??

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

的一個鄰域內Lipschitz

連續,則·14

·回3.2法及其實現法第三章 最速下降法和由上式得‖????+1

?

??*‖

≤

??(?

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

+

??(????

?

??*))

?

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

*1‖??(??

)

?

??(??

??)‖d??

‖????

?

??

‖1

)???d??

+

10+(?∫?≤

????‖????

?

??

‖*

22=??3????

‖??

?

??*‖2,即{

??

??

}

二次收斂于??*.

證畢.

口上述定理

,

初始點需要足夠“靠近”極小點,

否則有可能導致算法不收斂.

由于實際問題的精確極小點一般是不知道的,

因此初始點的選取給算法的實際操作帶來了很大的

.

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

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

搜索的阻尼

法如下:·15

·第三章 最速下降法和

法回3.2法及其實現算法

3.3

(阻尼 法)步

0

給定終止誤差值

0

≤

??

?

1,

??

∈

(0,

1),

??

∈

(0,

0.5).

初始點??0

∈R??.令??

:0.步

1

計算????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出??*

≈

????.步

2

計算

????

=

?2??(????),

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

=

?????步

3

記????

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

+

????????)

≤

??(????)

+

??????????

????.(3.7)步

4

令????

=

??????,

????+1

=

????

+

????????,

??

:=

??

+

1,

轉步

1.給出算法3.3

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

3.4

設函數??(??)

二次連續可微且存在常數??

>

0,

使得????

?2??(??)??

≥

??‖??‖2,

???

∈

R??,

??

∈

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

·第三章 最速下降法和

法

回

3.2

法及其 實現其中

??(??0)

=

{??|??

(??)

≤

??(??0)}.

設

{

??

??

}

是由算法

3.3

產生的無窮點列,則該點列收斂于??

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

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

是???(??)=0

的唯一解.由于??

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

??

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

≤

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

>0

是某個常數.設??ˉ

是{??

??

}的任意一個極限點,則有????

→??

(??ˉ).??記

????

是負梯度方向

?????

與

方向

????

=

????1????

的夾角.

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

????

=?????????

????

??????????

??=

≥

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

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

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

≥

??‖????‖

??>

0.·17

·回3.2法及其實現第三章 最速下降法和

法則由定理2.2

可得??→∞lim

????

=

0,即{

??

??

}

的極限點都是穩定點.

由??

的凸性知,

穩定點亦即(全局)

極小點.故由極小點的唯一性知,

{

??

??

}

收斂于??

在水平集??(??0)

上的全局極小點.證畢. 口為了分析算法3.3

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

3.1

設函數

??

:

R??

→

R

二次連續可微,

點列

{

??

??

}

由算法

3.3產生.設{??

??

}→??*

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

+

????‖

=

0,‖????‖(3.9)則(1)當??

充分大時,步長因子????

≡1.(2)點列{??

??

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

設定理3.4

的條件成立,點列{??

??

}由算法3.3

產生.則{??

??

}超線性收斂于??

的全局極小點??*.此外,若Hesse

陣??(??)在??*

處Lipschitz

連續,則收斂階至少是二階的.·18

·第三章 最速下降法和

法

回

3.2

法及其 實現證

定理

3.4

已證明

{

??

??

}

→

??*

且

??(??*)

=

???(??*)

=

0.

又由算法3.3

的步

2

顯然有條件

(3.9)

成立.

故由引理

3.1(1)

可知對于充分大的

??,????

=1

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

立即得到{??

??

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

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

3.2

(阻尼 法程序)f

unction [

x,

val,

k]

=dampnm(

fun,

gfun,

Hess,

x0)%功能:

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

min f

(

x

)%輸入:%%輸出:x0是初始點, f

u

n

,

gf

un,

Hess

分別是求目標函數值,

梯度,

Hesse

陣的函數x,

val

分別是近似最優點和最優值,

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

0

.

55

;

sigma=0

.4

;k=0;

epsilon=

1

e

-

5;while(

k?maxk)·19

·實現第三章 最速下降法和

法

回

3.2

法及其gk=f

eval(gfun,x

0);

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

%計算Hesse陣dk=-Gk“gk;

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

計算搜索方向i

f(n

o

r

m(g

k)?e

p

s

i

l

o

n),

br

eak;

end

%檢驗終止準則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法及其實現第三章 最速下降法和

法v

a

l

=

f

e

v

a

l

(

f

u

n

,

x

)

;例3.2

利用程序3.2

求解無約束優化問題??∈R21min

??(??)

=

100(??2

?

??2)2

+

(??1

?

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

=(1,1)??

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

中建立的兩個計算目標函數和梯度的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,終止準則取為‖???(????)‖≤10?5.取不同的初始點,數值結果如下表.·21

·第三章 最速下降法和法回3.2法及其實現表3.2

阻尼法的數值結果.初始點(??0)迭代次數(??)目標函數值(??(????))(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由上表可以看出,

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

0

=[-

1.

2

1]’;·22

·法及其實現第三章 最速下降法和

法

回

3.3

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

分別是求目標函數值和它的梯度及其Hesse

陣的M

函數文件.3.3

修正 法及其 實現從上一節的分析可知,

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

這是它的優點.

但該算法要求目標函數的

Hesse

陣

??(??)

=

?2??(??)

在每個迭代點????

處是正定的,

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

=

????1????

是??

在????

處的下降方向.

為克服這一缺陷,

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

奇異,

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

則采用負梯度方向作為搜索方向.

寫出詳細的計算步驟如下:算法3.4

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

·第三章 最速下降法和

法

回

3.3

修正 法及其 實現步

0

給定初始點??0

∈

R??,

終止誤差

0

≤

??

?

1.

令??

:=

0.3.4

產生的迭代序列,且存在{??

??

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

·步

1

計算

????

=

???(????).

若

‖????‖

≤

??,

停算,

輸出

????

作為近似極小點.步

2

計算

????

=

?2??(????).

解方程組??????

+

????

=

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

且滿足????

????

<0,轉步3;否則,令????

=?????

轉步3.??步

3

由線搜索技術確定步長因子????.步

4

令????+1

=

????

+

????????,

??

:=

??

+

1,

轉步

1.對于算法3.4,利用定理2.2,

定理2.3

以及引理3.1

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

設對任意的??0

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

|

??

(??)≤??

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

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

??

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

準則,或Armijo

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

修正法及其實現有lim inf

‖????‖

=

0,??→∞以及

{

??

??

}

超線性收斂于

??*.

進一步,

若

??(??)

在

??*

處是

Lipschitz

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

Hesse

陣

??(????)

=

?2??(????)

正定的缺陷.

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

例如,

引進阻尼因子????

≥0,即在每一迭代步適當地選取參數????

使得矩陣????

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

寫出算法步驟如下:算法

3.5

(修正 法)步

0

給定參數??

∈

(0,

1),

??

∈

[0,

1],

??

∈

(0,

0.5),

終止誤差

0

≤

??

?

1.初始點??0

∈R??.令??

:=0.步

1

計算

????

=

???(????),

????

=

‖????‖1+??.

若

‖????‖

≤

??,

停算,

輸出

????作為近似極小點.·25

·法及其實現第三章 最速下降法和

法

回

3.3

修正步

2

計算

Hesee

陣

????

=

?2??(????).

解線性方程組(????

+

??????)??

=

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

3

令????

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

+

????????)

≤

??(????)

+

??????????

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

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

:=????

+????????.步

4

令??

:=

??

+

1,

轉步

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

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

3.7

設函數

??

:

R??

→

R

有下界且二次連續可微,

??(??)

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

連續.則由算法3.5

產生的迭代序列{??

??

}的任何極限點都是問題(3.1)的解.已有研究證明,當目標函數的Hesse

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

·第三章 最速下降法和

法

回

3.3

修正 法及其 實現定義

3.1

若在問題(3.1)

的極小點??*

處

Hesse

陣

??(??*)

奇異,

則稱??*

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

=

{??*

|??(??*)

=

min

??(??),

??

∈

R??}.用??

表示其解定義

3.2

設??*∈

??

,

函數??

:R??

→R+.

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

及常數??

>

0,

使得??(??)

≥

??dist(??,

??

)

,

??

∈

??(??*),

(3.13)其中

dist(??,

??

)

表示點

??

到集合??

的距離,

則稱函數??

在鄰域??(??*)

內對問題(3.1)

解集合??

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

的局部收斂速度的估計,其證明可參看文獻[?].·27

·第三章 最速下降法和

法

回

3.3

修正 法及其

實現定理

3.8

設定理

3.7

的條件成立.

若由算法

3.5

產生的迭代序列{??

??

}有子列{????

:??

∈??

}收斂于??*

∈??

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

的某鄰域內對問題(3.1)提供了一個局部誤差界,則當??

∈??

充分大時,????

≡1,且子列{????

:??

∈??

}二階收斂于??*,即存在常數??

>0

使得dist(????+1,

??

)

≤

??dist(????,

??)

2

.下面

給出算法

3.5

(修正 法)

的

程序.程序

3.3

(修正

法 程序)f

unct

i

on [

x,

val,

k]

=revisenm(

fun,

gfun,

Hess,

x

0

)%

功能:

用修正

法求解