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

洪云飞 (长江大学期刊社，长江大学信息与数学学院，湖北 荆州 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。……