在强wolfe线搜索下具有全局收敛性的一个共轭梯度法

5期

Vol. 33 No. 5

钦州学院学报

JOURNAL OF QINZHOU UNIVERSITY

2018年5月May,2018

在强WO价线技奈下具有全局 收故性的

一

个共乾梯皮法

李智群，陆静，张爽

(钦州学院理学院，广西钦州535011)

[摘

要

]根据改进的m5方法，提出了一个新的求解无约束优化问题的共辊梯度法，该算法在强《^/6

型线搜索下具有充分下降性和全局收敛性，数值实验结果表明该算法是有效的。

[关键词]无约束优化;共轭梯度法;充分下降性;全局收敛性;数值实验

[中图分类号]0224 [文献标识码]A [文章编号]1673 -8314(2018)05 -0023-04

求解无约束优化问题的最有效数值方法之一 是非线性共轭梯度法（简称共轭梯度法），因为共 轭梯度法具有结构简单，需求储存少的特点，是解 决无约束优化问题的常用有效方法，特别适合解 决大规模的无约束优化问题。无约束优化问 题是：

文章考虑的线搜索是强型线搜索，步长

a4.满足：

f(xk+akdk) ^f(xk) +dakgltTdk

\\g{xk+akdk) Tdk | 1 其中 0<5(4)(5)

min^%) | x e R\"}

(1)

PKP方法、方法是目前数值表现较好的共 轭梯度法，这两个方法的理论性质和计算表现很 类似，但收敛性质不是很好[1]。

许多研究者在著名的共轭梯度法基础 上提出了新的改进方法。文献[2]提出的新 的改进pkp方法为im方法，其参数公式为：

Sk ( Sk其中/:/r—k为一阶连续可微的非线性函 数。共轭梯度法一般的迭代公式为：

XM =xk+^kdk

(2)

其中A为由某线搜索决定的步长，< 为搜索

方向，其计算公式为：

_(~gk

4 iuA

其

中

&

U彡2 ⑶

A =—

IUI

II

II gk II

~Sk-\\,

II ^

(6)

=▽/(〜）具为参数。不同的 文献[3 ]在文献[2 ]的基础上，提出了一个新 的改进方法，得到的参数公式为：

gl\\gk-q参数表达式A对应着不同的共轭梯度法，较著名的共轭梯度法参数有A™ =

I

gk Jk-\\

T

I

\"二,

gk-1

I

=

gkTYk-\\I

d

，式中 私-sv/1]。

II8^ II ^ (7)

上面两种改进方法在强型线搜索下具

new 一____2

I

SkSk-i

I

2^k-\\ ,[收稿日期]2018-01-02

[基金项目]国家自然科学基金：蛋白质经带电石墨烯纳米孔输运的模拟研究（11704210);广西自然科学基金:半连

续动力系统理论之于红树林害虫治理的研究（2016GXNSFAA380102)。

[作者简介]李智群（1979-),女，广西贵港人，钦州学院理学院讲师。

24

钦州学院学报

第33卷

有全局收敛性，数值检验结果也较好。

受文献[2-3]的启发，本文提出新的改进

方法的参数公式：

^ =-l-2〇-

gl-idk-'

II

II2

(13)

上式依次类推得：

I

gl[gk-MPRP ■

II II

IIII

2^A：-l |

t-i

X(20-j=〇)^

(8)

II gk II

gld,,^-t^=-2+S(20-)^

尸0 (14)

故有

专」^

1_2o_ IkJI

= -2+

1 ~2a显然

1算法及其性质

(15)

算法i

步1给出初始点^ ,々：=

步2若|| & |丨矣心则停止；

步3计算步长叫满足强w〇Z/e型线搜索(4)、

(5)；

步4 令％H=%+

aA，gi+i=尽(％a);

步5依据公式（8)计算参数'按公式

(3)计算<4+1，令A：: =A+1,转到步2。引理1

算法1产生的序列04，^}，当^ e

(0,1)时有

gkTdk^-C II gk \\\\2,k^l,0(9)

成立。

证明当 A=1 时乂 =-g,，知 ||2<〇成立。

当W1时，设对任意的A：-1有<0,

则

由

执

胃

‘有

II gk I

gkgk-igkTdk=~ \\\\gk II2+-

HU

-{glgh-Hdk-x II-gj:

(10)

上式两边除以|| A || 2得

gldk

(I gk I-1 +gUk-i

\\glgk~\\ \\(glgk~

II gk-r II ' II g4-, II 4 II g, II

gjdk-i:-l+lr,

\\gTkgk-\\\\^glgk-\\)\\ gldk.Ik/c-! II211^ II2/ II ^-1II2 (11)

因为CK1--

I SkSk-i Hi) ^

(12)

II gk^ IIz II ^ II

所以由（5)、（11)及（12)式得

-1+2(7

1 , n, -----------Sk-l^k-l ^ Sk^k

II

II2

II g, II

令 ^ = 2-^；，当 cr^O,丁 时,0降性。

2算法的全局收敛性

为了分析收敛性，需对目标函数/(幻作如下

假设条件：

假设（A)水平集11 =伽

有界；

假设(B)/U)的梯度函数贫⑷在O内 ^连续，即存在常数i>0,使得对任意a;

I g(x)-g(y) | | x-ye (1有

||

(16)

引理2W-W考虑形如⑵和⑶的方法，若假 设(A)和（B)成立，步长因子％由《;〇诉型线搜索 方法得到，且对所有的A:有g/<<〇，那么

Lv ------------(gJdk)r2

||

<+0°4S1 II dk (17)

(17)式称为 Zoiiterac^/A:条件。文献[2 ]指出

邱

c条件（17)式在精确

线搜索、

线搜索和强wW/e型线搜

索下都成立，其相关的证明在文献[7]。

GiZ6ert和yVocecW 8]曾经给出一个重要的性质（* ) 〇

性质（*)考虑形如(2)和(3)的方法,并假定

°II

(is)

我们说方法具有性质（*),如果存在常数

1和A>0,使对所有的有下式成立：

\\/3k\\^b,以及

第5期 李智群，陆静，张爽:在强线搜索下具有全局收敛性的一个共轭梯度法

25

II sk-\\ II 其中 -1

\\/3k | ^―,

对于收敛性分析，Gittert和yVocecfo^81证明了 一个重要的引理。

引理3 [8]考虑形如(2)和(3)的共轭方法，且 满足下列条件：，

Sk =Xk~Xk-lO

算法1中的参数■具有性质（*)，即有 定理1考虑形如(2)和(3)的方法，执

若假设（B)成立，则参数灼MPfiP具有性质

(a) A>〇;

(b) 搜索方向^具有充分下降性质(9);(C ) 7祕671啦7[：条件成立；((1)性质（*)成立。

如果假设（A)和（B)成立，那么形如（2)和 (* )。

证明令6 = ¥，A

7

AbLy

-则有

tI

I glgk-x I

、

Sk \\ Sk 丨丨

I, 2^-l ,

MPRP _

'

II

Sk-l

II

I

II gk-i I

II gk II

丨丨

I. . gTkgk-lII Sk

n

1

S；

丨I SVi丨丨

H

II 2

II gk II

II II + s：

__________gk II \\ 8k8^\\ \\gk-1 I____________ II Sk-I II

n II2

II gk II

II gk II + }II Sk L II 8^ II 2

gk-i I

II gk^ I

_2||gt V_2y2_L

U V _

如果I卜m I丨矣A，那么

II II

gk IIII

II II

gk—.,I\\ SkSk-1

rT\"\\S=

!l- --------77^4-1

gk-i III II

(\"

m

id

£=

II gk-\\ II 2

IkJI (iA-II gt-i II 2II ~\\gkTI

Sk-x

s；

g^i

2

g, (LX —.I

ii

■i

2II II

~gigk-i l

•s

ii

ii

gk-\\ 2

ii

gk (L\\ + gk-i

II II gk-gk-i

II

s

II II

•5

II II

g^iII2

s=

2 II gk II

LA2 一

gt-i---LXy1ii2、y2II

2b

(3)的共轭方法是全局收敛的。

根据引理3可知算法1具有全局收敛性。

3数值实验

本文算法的数值实验结果如表1，算法的参

数5 = 0_01,£7 = 0.1，= 10—5,终止条件为|丨心|丨矣 心或迭代次数不超过1〇4。

表

1

数值实验

ProblemDimnewMPRPNI/NF/NGNI/NF/NGJENSAM215/85/2611/30/20BARD320/44/3117/41/29GAUSS34/9/54/9/5GULF31/2/21/2/2BOX31/51/21/51/2KOWOSB4563/2236/955563/2236/955

0SB1

51/51/21/51/2BIGGS6109/436/1798/260/145SINGX414/176/9414/176/94PEN125/18/125/18/12PEN2420/96/3617/140/34VARDIM23/9/73/9/7VARDIM5010/52/3610/52/36TRIG

3106/638/178106/638/178TRIG50209/2063/301209/2113/302

BV1013/27/1713/27/17IE35/12/75/12/7IE

50

6/13/7

6/13/7

26

续表

钦州学院学报 第33卷

由表可知，算法1基本保持参数为氏_的算

ProblemIETRIDTRIDTRIDBANDLINLINLINLINLIN1LIN1LINO

Dim1003100200325050010002104

newNI/NF/NG6/13/814/36/1931/69/3731/162/367//121/3/31/3/31/3/31/3/31/51/21/3/31/3/3

MPRPNI/NF/NG6/13/818/86/2431/69/3731/162/367/63/111/3/31/3/31/3/31/3/31/51/21/3/31/3/3

法，是有效的。相对于参数为汍_的算法，算法1 的一个特点是&〇，另一个特点是搜 索方向在强《w/e线搜索下保持的充分下降性的 参数〇■范围较小。

参考文献

[1 ]戴或虹，袁亚湘.非线性共轭梯度法[M ].上海:上海科学技 术出版社,2001.

[2] WEI Z, YAO S,LIU L. The convergence properties of some con­

表中PraWem表亦测试冋题的名称;Dim表;^ 目标函数变量的维数;表示算法1

表

示与强线搜索一起的算法;yv//yvF/yvG 分别表示迭代次数/目标函数值计算次数/目标函 数梯度值计算次数。

jugate gradient methods[ J]. Applied Mathematics and Computa­

tion, 2006 (183) ：1341-1350.[3] HUANG H D,LI Y J,WEI Z X. Global convergence of a modi­

fied PRR conjugate gradient method [ J ]. Journal of Mathematical Research & Exposition,2010(30) ： 141-148.[4] Wolfe P. Convergence conditions for ascent methods. SIAM Re­

view, 1969( 11) ：226-235.[5] Wolfe P. Convergence conditions for ascent methods. II: Some

correction，SIAM Review,1971(31) :185-188.[6] Zoutendijk G. Nonlinear Programning( Abadie J,ed. ) [ M]. Am­

sterdam ：North-Holland, 1970.[7] Z F Li, J. Chen,N Y Deng, convergence properties gradient meth­

od with Goldstein line search. J. China Agric. Univer, 1996(4)：

15-18.

[8 ] Glibert J C, Nocedal J. Global convergence properties of conju­

gate gradient methods for optimization [ J ] . SIAM. J. Optimiza­tion, 1992(2) ：21-42.

A New Conjugate Gradient Method of Global Convergence

under the Strong wolfe Line Search

Abstract ： Base on the improved PRP conjugate gradient method, a new conjugate gradient method is presented for uncon­

strained optimization problems. The algorithm possesses sufficient descent property and global convergence under the strong wolfe line search. The numerical results show that the algorithm is effective.

Key words ： unconstrained optimization ； conjugate gradient method ； sufficient descent property ； global convergence ； numerical experiment

「责任编辑黄立壮]

LI Zhiqun,LU Jing,ZHANG Shuang

(College of Science, Qinzhou University, Qinzhou 535011 , China)