朱建偉

(長江大學(xué)一年級教學(xué)工作部，湖北 荊州 434023)

求解無約束優(yōu)化問題的記憶梯度法收斂速度研究

朱建偉

(長江大學(xué)一年級教學(xué)工作部，湖北 荊州 434023)

給出了一個(gè)求解無約束優(yōu)化問題的記憶梯度法的收斂速度分析，在一致凸條件下證明了求解無約束優(yōu)化問題的記憶梯度法具有線性收斂性。

無約束優(yōu)化問題；記憶梯度法；一致凸；收斂速度

1 記憶梯度法

首先給出以下2個(gè)假設(shè)[1]：

H1: 目標(biāo)函數(shù)f在水平集L0={x∈Rn|f(x)≤f(x0)}上有下界。

H2: 梯度g在包含L0的開凸集B上一致連續(xù)。

求解無約束優(yōu)化問題的記憶梯度法算法描述如下:

步1 如果‖gk‖=0則停止，否則轉(zhuǎn)步2；

步2 令：

xk+1=xk+αkdk(βk,γk)

其中：

此處αk是由Armijo rule選取的；

步3k=k+1轉(zhuǎn)步1。

2 收斂速度分析

為了分析算法的收斂速度，假定：

H3:f(x)在Rn上二階連續(xù)可微，且一致凸。

引理1如果假設(shè)H3成立，則H1，H2成立，f(x)存在唯一的最優(yōu)解x*，且存在0lt;0≤M使得：

m‖y‖2≤yT2f(x)y≤M‖y‖2?x,y∈Rn

(1)

(2)

M‖x-y‖2≥(g(x)-g(y))T(x-y)≥m‖x-y‖2g(x)=f(x) ?x,y∈Rn

(3)

從而:

M‖x-x*‖2≥g(x)T(x-x*)≥m‖x-x*‖2?x∈Rn

(4)

由式(3)和式(4)以及Cauchy-Schwartz[2]不等式可得：

M‖x-x*‖≥‖g(x)‖≥m‖x-x*‖ ?x∈Rn

(5)

及:

‖g(x)-g(y)‖≤M‖x-y‖?x,y∈Rn

(6)

引理1的證明可參文獻(xiàn)[3]。

引理2如果H3成立，則算法產(chǎn)生無窮點(diǎn)列{xk}，且存在η使得：

(7)

證明由文獻(xiàn)[1]有：

由Cauchy-Schwartz不等式有：

(10)

由式(9)和式(10)即可得：

(11)

由式(8)可得：

記：

即式(7)成立。

定理1如果H3成立，則算法產(chǎn)生的無窮列{xk}，或者存在無窮子集K使得：

(12)

或者{xk}線性收斂到x*。

證明假設(shè)H1，H2成立，由引理1及式(5)即有xk→x*(k→+∞)。記：

如果{pk}無界，則式(12)成立。假設(shè)pk≤M0，由式(2)，(5)，(7)可得：

fk-fk+1≥(1-θ2)(fk-f*)

從而有:

fk+1-f*≤θ2(fk-f*)

(13)

進(jìn)一步由式(2)和式(13)得：

故{xk}線性收斂到x*。

[1]朱建偉.一個(gè)帶不精確線性搜索的記憶梯度法[J].長江大學(xué)學(xué)報(bào)(自然版)2009，6(2)，123～125.

[2]宋國棟.數(shù)學(xué)分析[M].北京：高等教育出版社，2001.

[3] Grippo L， Lampariello F，Lucidi S.A class of nonmonotone stability methods in unconstrained optimization[J].Numerische mathematik,1991,62: 779～805.

[編輯] 洪云飛

2009-08-21

國家自然科學(xué)基金項(xiàng)目(70371023)。

朱建偉(1966-)男，1987年大學(xué)畢業(yè)，講師，博士生，現(xiàn)主要從事最優(yōu)化理論與方法方面的教學(xué)與研究工作。

O224 [MR(2000)主題分類號]90C33

A

1673-1409(2009)04-N008-02