关　哲，于宪伟

(渤海大学 数理学院，辽宁 锦州 121000)



一种新的求解无约束规划的共轭梯度法

关哲，于宪伟*

(渤海大学 数理学院，辽宁 锦州 121000)

摘要：研究无约束优化问题的共轭梯度法，推导出一种新的共轭梯度法，算法在新Wolfe线搜索条件下具有充分下降性与全局收敛性.

关键词：共轭梯度法；无约束优化；全局收敛性；Wolfe线搜索

共轭梯度法是求解无约束优化问题的重要方法之一，基于其算法简单，存储量小的特点，常用于求解大规模优化问题.

考虑无约束优化问题:

(1)

其中f:Rn→R连续可微，对于为问题(1)的共轭梯度法，一般采用如下的迭代格式：

(2)

(3)

其中：gk=f(xk)是f在xk处的梯度，αk是由线性搜索产生的步长，βk是标量，由αk和βk的选取不同，可以产生不同的共轭梯度法.常用的共轭梯度法有：FR算法[1]、PRP算法[2-3]、HS算法[4]、DY算法[5]、LS算法[6]、CD算法[7]，参数公式分别为：

此外还有许多学者对共轭梯度法进行深入研究，并取得丰硕成果[8-13].步长αk步长通常用非精确线性搜索求得，常用的线搜索有Armijio型线搜索和Wolfe型线搜索[14-18]：

标准的Armijio型线搜索：

αk=max{ρj,j=0,1,2,…},

(4)

其中:ρ∈(0,1),δ∈(0,0.5).

标准的Wolfe线搜索：

(5)

(6)

其中参数0<δ<σ<1.

(7)

(8)

(9)

当线性搜索精确时，式(9)等价于FR公式.

文献[19]对广义Wolfe线搜索进行改进，得到如下线搜索：

笔者对标准Wolfe线搜索做出如下改进.将搜索条件(6)改为：

(10)

1算法及性质

算法1

步1给定初始值x1∈Rn，ε>0，d1=-g1，令k：=1；

步2如果‖gk‖≤ε，则停止，否则转步3；

步3由线搜索式(5)和式(10)求出步长αk，由式(2)得出xk+1；

(11)

由式(3)有dk=-gk+βkdk-1，等式两端分别与gk做内积，并结合式(9)可得：

由数学归纳法知命题1成立.

2算法的全局收敛性

本文做如下假设Η：

(i)水平集Ω={x∈Rn|f(x)≤f(x1)}有界，……