一种基于再开始技术求解无约束优化问题的共轭梯度法

洪云飞 (长江大学期刊社，长江大学信息与数学学院，湖北 荆州 434023)

陈 忠，吕一兵 (长江大学信息与数学学院，湖北 荆州 434023)

一种基于再开始技术求解无约束优化问题的共轭梯度法

洪云飞 (长江大学期刊社，长江大学信息与数学学院，湖北 荆州 434023)

陈 忠，吕一兵 (长江大学信息与数学学院，湖北 荆州 434023)

无约束优化问题；共扼梯度法；再开始技术；收敛性

考虑无约束优化问题：

(1)

其中，F:Rn→R为连续可微函数，求解该问题的一种迭代算法形式为：

xk+1=xk+αkdkk=1,2,…

(2)

(3)

其中gk=f(xk)，dk为搜索方向，而akgt;0是通过某种线搜索获得的步长。纯量βk的选取应满足共轭性，即当f(x)为严格凸二次函数且采用精确线搜索时，搜索方向dk关于f(x)的海赛阵共轭。此外，当f(x)为严格凸二次函数时，共扼梯度法在精确线搜索下具有有限步终止性，但对一般连续可微目标函数，这一性质很难保证。 当βk选取不同的公式就得到不同的共轭梯度法，比较著名的是FR[1]方法、PRP[1]方法、HS[1]方法和LS[1]方法：

(4)

(5)

(6)

(7)

(8)

其中μ∈(0,1)，这样就定义了一族带参数μ的共轭梯度法。显然如果取μ为0和1，则分别对应了HS方法和LS方法。对αk的选择一般有精确线搜索和非精确线搜索2种。下面着重考虑非精确线搜索的情形。

设αk满足强Wolfe线搜索原则，即：

1 算法描述

算法描述如下：

步1 给定x1∈Rn，ε∈(0,1)，选取μ∈(0,1)；-d1=-g1=-f(x1)，令k=1；

步2 若‖g(xk)‖lt;ε，则停止。求得αk使其满足强Wolfe条件，由式(2)求得xk+1。

2 收敛性分析

引理1[2]设目标函数f(x)在D⊂Rn上连续可微且下方有界，其导数g(x) Lipchitz连续即Mgt;0，对y,z∈D，均有‖g(y)-g(x)‖≤M‖y-z‖，则对满足Wolfe条件的任何αkgt;0均有：

(9)

证明用反证法。不失一般性，设对任意k均有gk≠0，假设结论不成立，则∃γgt;0，使得‖gk‖ gt;γ，对所有k≥1。

根据引理1有：

将上式累加，由于f(x)在D上下方有界，故有：

因此当k充分大后，|βk|lt;clt;1成立，则：

‖dk+1‖=‖-gk+1+βk+1dk‖≤‖gk+1‖+|βk+1|‖dk‖≤L+c‖dk‖

这与Zoutendijk条件[3]矛盾，故结论得证。

f(xk)-f(xk+αkdk)≥m‖αkdk‖2

对于一致凸函数，算法还有如下结论：

又由引理2可知：

f(xk)-f(xk+1)≥m‖xk-xk+1‖2

将上式累加，由于f(x)下有界，所以有：

故有：

‖xk-xk+1‖→0

0≥f(xk)-f(x1)≥g(x1)T(xk-x1)+c‖xk-x1‖2

[1]戴或虹,袁亚湘.非线性共扼梯度法[M].上海：上海科技出版社,2000.

[2]洪云飞，喻娟，陈忠. 对共轭梯度法中标量βk的一种修正[J].青海师范大学学报(自然科学版)，2008(4)：18-20.

[3]Zoutendijk G.NonlinearProgramming,ComputationalMethods[M].Amsterdam:North-Holland,1970：37-86.

[4]喻娟，陈忠.求解无约束优化问题的一种新的共轭梯度法[J].长江大学学报(自然科学版)，2007，4(4)：N12-13.

[编辑] 李启栋

10.3969/j.issn.1673-1409(N).2012.03.002

O224

A

1673-1409(2012)03-N004-03

2012-01-17

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

洪云飞(1979-)，男，2001年大学毕业，硕士，讲师，现主要从事最优化理论与算法方面的教学与研究工作。