Advances in Applied Mathematics
Vol.05 No.04(2016), Article ID:18976,6 pages
10.12677/AAM.2016.54071

A New Conjugate Gradient Method

Yong Li1, Gonglin Yuan2

1School of Mathematics and Statistics, Baise University, Baise Guangxi

2Department of Mathematics and Information Science, Guangxi University, Nanning Guangxi

Received: Oct. 27th, 2016; accepted: Nov. 9th, 2016; published: Nov. 18th, 2016

Copyright © 2016 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

ABSTRACT

This paper has designed a new parameter formula. The conjugate gradient algorithm which based on the parameter formula is global convergence with WWP line search under appropriate conditions. Preliminary numerical results turn out that this new method is effective.

Keywords:Unconstrained Optimization, Conjugate Gradient Method, Global Convergence

一种新的共轭梯度法

黎勇1,袁功林2

1百色学院数学与统计学院,广西 百色

2广西大学数学与信息科学学院,广西 南宁

收稿日期:2016年10月27日;录用日期:2016年11月9日;发布日期:2016年11月18日

摘 要

本文设计了一个新的参数公式,在适当条件下,建立在此参数公式上的共轭梯度算法在WWP线搜索下全局收敛。初步的数值实验结果表明新算法是有效的。

关键词 :无约束优化,共轭梯度法,全局收敛性

1. 引言

考虑无约束优化问题,共轭梯度法是解决此类问题的一种非常有效方法。共轭梯

度法是一种迭代算法,因为简便、存储需求小的优势而往往被用来求解大规模的优化问题,它的迭代公式通常如下:

(1)

其中是搜索步长,是搜索方向,通常定义如下:

(2)

这里的,表示目标函数在点处的梯度,其中上连续可微。则是一个参数。通过改变这个参数的不同选取,可以获得不同的带参数共轭梯度算法,人们经常讨论的参数公式有以下这些 [1] :

研究者普遍认为PRP方法是目前数值表现最好的共轭梯度法之一,但收敛性质比较一般。文献 [2] 举例指出:即使按照Curry原则进行选取步长,PRP共轭梯度法对一般的非凸函数也未必收敛;因此,很多研究者都对PRP共轭梯度法进行了修正改进,文献 [3] [4] [5] [6] [7] 均是对进行非负修正,其中文献 [5] 提出的参数公式

受到了广泛关注。建立在这一参数公式基础上的共轭梯度算法不仅收敛效果好,而且数值结果也比较理想 [4] [5] 。在此基础上文献 [6] 提出了一种修正的WYL共轭梯度法

该方法能够自动保证参数公式的非负性,而且不依赖任何线搜索,可以自动保证充分下降性,因而收敛效果也比较好。我们在文献 [7] 中提出的修正的PRP共轭梯度法

(3)

借鉴了文献 [6] 的思路。若对参数公式(3)的分母加一个非负的量,选择参数为

(4)

则可以得到一个新的共轭梯度法。

下面将建立并讨论新算法和算法的收敛性。新算法采用弱Wolfe-Powell(WWP)线搜索,步长满足:

(5)

(6)

其中是满足的常数。

2. 算法与假设

算法1

步1:给出。令。若,则停止。

步2:计算步长因子,使满足WWP线搜索(5)、(6)。

步3:令。若,则停止。

步4:按(4)式计算公式,其中,利用(3)式计算

步5:令,转步2。

假设:

假设(i) 水平集有界。

假设(ii) 函数的某邻域内连续可微,并且它的梯度函数Lipschitz连续。即存在一个正的常数,对任意

。(7)

3. 全局收敛性

引理1. 若,其中,则

证明:因为,所以

由Cauchy-Schwarz不等式可得

引理2 (性质*)。考虑算法1,假设(i)、(ii)成立,若

(8)

则存在常数,使对所有,有

以及

证明:取,则

而若,则由Lipschitz连续性知

引理3 [8] 。考虑共轭梯度方法(1)和(2),步长因子满足线搜索WWP (5)、(6),若:

1)

2) 充分下降条件成立;

3) 性质(*)成立;

4) 假设(ⅰ)(ⅱ)成立;

则算法全局收敛。

在共轭梯度法的讨论中,充分下降条件

,(9)

是一个很重要的性质。

根据以上3个引理,在假设充分下降条件可以满足的前提下,容易得出本文所给的共轭梯度法在WWP线搜索下全局收敛的结论。

定理1. 若假设(i) (ii)成立,且(9)式成立,序列由算法1生成,则

4. 数值试验

为了考查新算法的数值表现,本文选取26个函数进行数值实验,部分测试函数来自CUTE函数库。数值试验程序我们利用Fortran语言编写。表1列出的计算结果是在参数,线搜索参数

Table 1. The results of numerical experiment

表1. 数值实验结果

;终止条件是迭代次数,或者的时候分别对3000维和6000维进行测试时取得的。表1中的是算法终止时的函数值,表示算法终止时梯度范数值,表示迭代次数,表示计算次数。

上表中的测试结果表明新算法是有效的,特别是对于高维问题,新算法表现出了较好的处理能力,所以对于大规模优化问题的求解,新算法有能力解决此类问题。

基金项目

国家自然科学基金项目(No.11661001, No.11661009);广西自然科学基金(No.2014GXNSFAA118030);广西教育厅科研项目(No.YB2014389)。

文章引用

黎勇,袁功林. 一种新的共轭梯度法
A New Conjugate Gradient Method[J]. 应用数学进展, 2016, 05(04): 614-619. http://dx.doi.org/10.12677/AAM.2016.54071

参考文献 (References)

  1. 1. Lu, S., Wei, Z. and Mo, L. (2011) Some Global Convergence Properties of the Wei-Yao-Liu Conjugate Gradient Method with Inexact Line Search. Applied Mathematics and Computation, 217, 7132-7137. http://dx.doi.org/10.1016/j.amc.2011.01.097

  2. 2. Huang, H. and Lin, S. (2014) A Modified Wei-Yao-Liu Conjugate Gradient Method for Unconstrained Optimization. Applied Mathematics and Computation, 231, 179-186. http://dx.doi.org/10.1016/j.amc.2014.01.012

  3. 3. 黎勇. 一类新的修正PRP共轭梯度法[J]. 武汉理工大学学报(交通科学与工程版), 2012, 36(2): 437-440.

  4. 4. 戴彧虹, 袁亚湘. 非线性共轭梯度法[M]. 上海: 上海科技出版社, 1999.

  5. 5. Powell, M.J.D. (1984) Nonconvex Minimization Calculations and the Conjugate Gradient Method. Springer-Verlag, Berlin, 122-141. http://dx.doi.org/10.1007/bfb0099521

  6. 6. Hager, W.W. and Zhang, H. (2006) A Survey of Nonlinear Conjugate Gradient Methods. Pacific journal of Optimization, 2, 35-58.

  7. 7. Wei, Z., Yao, S. and Liu, L. (2006) The Convergence Properties of Some New Conjugate Gradient Methods. Applied Mathematics and Computation, 183, 1341-1350. http://dx.doi.org/10.1016/j.amc.2006.05.150

  8. 8. Huang, H., Wei, Z. and Yao, S. (2007) The Proof of the Sufficient Descent Condition of the Wei-Yao-Liu Conjugate Gradient Method under the Strong Wolfe-Powell Line Search. Applied Mathematics and Computation, 189, 1241- 1245. http://dx.doi.org/10.1016/j.amc.2006.12.006

期刊菜单