求解无约束优化问题的记忆梯度法收敛速度研究

朱建伟

(长江大学一年级教学工作部，湖北 荆州 434023)

求解无约束优化问题的记忆梯度法收敛速度研究

朱建伟

(长江大学一年级教学工作部，湖北 荆州 434023)

给出了一个求解无约束优化问题的记忆梯度法的收敛速度分析，在一致凸条件下证明了求解无约束优化问题的记忆梯度法具有线性收敛性。

无约束优化问题；记忆梯度法；一致凸；收敛速度

1 记忆梯度法

首先给出以下2个假设[1]：

H1: 目标函数f在水平集L0={x∈Rn|f(x)≤f(x0)}上有下界。

H2: 梯度g在包含L0的开凸集B上一致连续。

求解无约束优化问题的记忆梯度法算法描述如下:

步1 如果‖gk‖=0则停止，否则转步2；

步2 令：

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

其中：

此处αk是由Armijo rule选取的；

步3k=k+1转步1。

2 收敛速度分析

为了分析算法的收敛速度，假定：

H3:f(x)在Rn上二阶连续可微，且一致凸。

引理1如果假设H3成立，则H1，H2成立，f(x)存在唯一的最优解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的证明可参文献[3]。

引理2如果H3成立，则算法产生无穷点列{xk}，且存在η使得：

(7)

证明由文献[1]有：

由Cauchy-Schwartz不等式有：

(10)

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

(11)

由式(8)可得：

记：

即式(7)成立。

定理1如果H3成立，则算法产生的无穷列{xk}，或者存在无穷子集K使得：

(12)

或者{xk}线性收敛到x*。

证明假设H1，H2成立，由引理1及式(5)即有xk→x*(k→+∞)。记：

如果{pk}无界，则式(12)成立。假设pk≤M0，由式(2)，(5)，(7)可得：

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

从而有:

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

(13)

进一步由式(2)和式(13)得：

故{xk}线性收敛到x*。

[1]朱建伟.一个带不精确线性搜索的记忆梯度法[J].长江大学学报(自然版)2009，6(2)，123～125.

[2]宋国栋.数学分析[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

国家自然科学基金项目(70371023)。

朱建伟(1966-)男，1987年大学毕业，讲师，博士生，现主要从事最优化理论与方法方面的教学与研究工作。

O224 [MR(2000)主题分类号]90C33

A

1673-1409(2009)04-N008-02