Global Convergence of Some Improved Conjugate Gradient Methods

LIN Sui-hua

doi:10.13718/j.cnki.xdzk.2021.07.011

Message Board

Dear readers, authors and reviewers,you can add a message on this page. We will reply to you as soon as possible!

A class of modified parameter formulas of PRP, HS and LS conjugated gradient methods is proposed, and their search direction automatically possesses the sufficient descent property. The global convergence of the algorithms is proved under the standard WWP line search and the new modified WWP line search. Preliminary numerical experiments show that these algorithms are effective.

HTML

解极小化问题min{f(x)| x ∈ $\mathbb{R} $ⁿ}的迭代法有多种，其中共轭梯度法由于无须用到▽²f(x)等n阶矩阵数据，存储需求少而特别适合大规模优化问题^[1-18]. 传统共轭梯度法的迭代格式为：

其中：d_k为搜索方向，α_k为步长因子，β_k为参数，g_k=▽f(x_k)，s_k= x_k+1- x_k. 不同的β_k参数公式对应不同的共轭梯度法. 著名的PRP，HS，LS，FR，DY，CD方法的参数公式如下：

其中：y_k-1= g_k- g_k-1，‖·‖为欧氏范数. 基于β_k≥0在某些类型共轭梯度法收敛性分析中的重要性，文献[5-14]均对β_k采取相应的非负修正策略，如文献[5]对β_k^PRP截值得到β_k^PRP+=max{β_k^PRP，0}≥0；文献[7-8]则从β_k^PRP与β_k^FR，β_k^HS与β_k^DY，β_k^LS与β_k^CD凸组合的方式，得到β_k^PRP，β_k^HS，β_k^LS的非负修正公式如下：

其中

相应的WYL，MHS，MLS方法都具有较好的收敛性.

类似地，β_k^PRP，β_k^HS，β_k^LS也可修正为：

其中：

这一修改方式能确保β_k≥0，但却无法满足充分下降条件：∃c∈(0，1)，使

然而某些类型共轭梯度法的收敛性依赖于充分下降条件，因此文献[11]定理1只得将“满足充分下降条件”作为预设前提. 事实上VPRP，VHS，VLS方法不满足充分下降性，其全局收敛性仍无法保证.

受文献[9-10, 16-17]充分下降性策略的启发，我们修改(3)式的分母，得到

其中常数μ＞2. 我们将讨论(1)，(2)式迭代法的收敛性，其中参数β_k取自(5)，(6)或(7)式，步长因子α_k考虑采用经典的weak Wolfe-Powell(WWP)线搜索^[2]及文献[18]针对BFGS和PRP方法设计的modified weak Wolfe-Powell(MWWP)线搜索.

记参数为δ，σ的WWP线搜索条件为WWP(δ，σ)条件：

其中：δ∈(0，$\frac{1}{2}$)，σ∈(δ，1).

记参数为δ₁，δ，σ的MWWP线搜索条件为MWWP(δ₁，δ，σ)条件：

其中：δ∈(0，$\frac{1}{2}$)，δ₁∈(0，δ)，σ∈(δ，1).

将β_k^V₁，β_k^V₂，β_k^V₃统称为β_k^V，对应的算法V₁，V₂和V₃也统称为算法V.

1. 算法及性质

算法 V-WWP

步骤 1  设定初值x₁∈$\mathbb{R} $ⁿ，μ＞2，0＜δ₁＜δ＜σ＜1，ε＞0，d₁=- g₁，k=1. 若‖ g_k‖≤ε，则停止.

步骤 2  计算α_k满足WWP(δ，σ)条件(8)和(9)式.

步骤 3  由(1)式计算x_k+1. 若‖ g_k+1‖≤ε，则停止.

步骤 4  由(5)，(6)或(7)式计算β_k+1，由(2)式计算d_k+1.

步骤 5  置k=k+1，转步骤2.

在算法V-WWP框架中，将步骤2改为计算α_k满足MWWP(δ₁，δ，σ)条件(10)和(11)式，则得到V-MWWP算法.

定理 1  算法V-WWP生成的序列β_k，g_k，d_k满足0≤β_k和充分下降条件(4).

证  ∀k≥2，由-‖ g_k‖‖ g_k-1‖≤ g_k^T g_k-1≤‖ g_k‖‖ g_k-1‖，可得

又有

从而，可得0≤β_k^V₁，0≤β_k^V₂，0≤β_k^V₃. 根据算法V-WWP步骤(4)β_k的取法，可得0≤β_k.

取c=1- $\frac{2}{\mu }$，则c∈(0，1). 当k=1时，显然

对k≥2情形，若g_k^T d_k-1=0，将g_k^T与(2)式两端作内积，可得

若g_k^Td_k-1≠0，则由(12)-(15)式，可得

从而可得

进一步可得

定理1得证.

2. 原理与假设

证明算法的收敛性需要用到以下假设和引理.

假设：

(i) f(x)在水平集Ω={ x ∈ $\mathbb{R}$ⁿ|f(x)≤f(x₁)}下方有界，Ω有界.

(ii) ▽f(x)在Ω的某邻域N上Lipschitz连续，即存在常数L＞0，使得

引理 1^{[3, 6]} 考虑满足如下条件的任一共轭梯度法(1)-(2)：

(a) β_k≥0.

(b) 搜索方向满足充分下降条件(4).

(c) 以下Zoutendijk条件成立：

(d) β_k满足性质(*)：设0＜r≤‖ g_k‖≤ r，存在常数b＞1和λ＞0，对∀k≥2有

若假设(i)和(ii)成立，则该迭代全局收敛.

以下算法收敛性分析中均假设‖ g_k‖≠0，否则算法已得到f(x)的稳定点而终止.

3. 全局收敛性

定理 2  若假设(i)和(ii)成立，则算法V-WWP生成的序列g_k，d_k满足Zoutendijk条件(17).

证  由(8)式和定理1，知f_k+1≤f_k+δα_kg_k^Td_k＜f_k，递推可得f_k+1＜f_k＜…＜f₁. 再由假设(i)可知，序列{f_k}单调有界从而收敛，即$\mathop {\lim }\limits_{k \to \infty } {f_{k + 1}}$为常数.

由(9)式和假设(ii)，可得

从而可得

由(8)，(18)式可得

(19) 式两端对k=1，2，…求和，可得

从而可知(17)式成立，定理2得证.

定理 3  若假设(i)和(ii)成立，β_k，g_k，d_k为算法V-WWP生成的序列，则β_k满足性质(*).

证  由(9)式和定理1，可得

从而可得

根据算法V-WWP步骤(4)β_k的取法，可知

假设∀k≥1，0＜r≤‖ g_k‖≤ r，其中r和r为常数. 取

则由σ∈(0，1)，c=1-$\frac{2}{\mu }$∈(0，1)，知b＞1，λ＞0.

由(12)和(20)式，可得

设‖ s_k-1‖≤λ，则由(16)，(20)式及

可得

定理3得证.

由定理1-3以及引理1，可得如下定理4.

定理 4  若假设(i)和(ii)成立，g_k为算法V-WWP生成的序列，则$\mathop {\lim \;\inf }\limits_{k \to \infty } \left\| {{\mathit{\boldsymbol{g}}_k}} \right\| = 0$.

定理 5  若α_k满足MWWP(δ₁，δ，σ)条件，则α_k也满足WWP(δ-δ₁，σ)条件.

证  设α_k由MWWP(δ₁，δ，σ)线搜索产生，其中δ∈(0，$\frac{1}{2}$)，δ₁∈(0，δ)，σ∈(δ，1)，则由(10)和(11)式，可得

显然δ-δ₁∈ (0，$\frac{1}{2}$)，由(21)和(22)式，可知α_k也满足参数为δ-δ₁，σ的WWP线搜索条件. 定理5得证.

由定理5，类似定理4的证明过程，可得算法V-MWWP全局收敛，即如下定理6成立.

定理 6  若假设(i)和(ii)成立，g_k为算法V-MWWP生成的序列，则$\mathop {\lim \;\inf }\limits_{k \to \infty } \left\| {{\mathit{\boldsymbol{g}}_k}} \right\| = 0$.

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	HESTENES M R, STIEFEL E. Methods of Conjugate Gradients for Solving Linear Systems[J]. Journal of Research of the National Bureau of Standards, 1952, 49(6): 409. doi: 10.6028/jres.049.044 CrossRef Google Scholar
[2]	戴彧虹. 非线性共轭梯度法[M]. 上海: 上海科学技术出版社, 2000. Google Scholar
[3]	HAGER W W W W, ZHANG H C. A Survey of Nonlinear Conjugate Gradient Methods[J]. Pacific Journal of Optimization, 2006, 2(1): 35-58. Google Scholar
[4]	HAGER W W, ZHANG H C. A New Conjugate Gradient Method with Guaranteed Descent and an Efficient Line Search[J]. SIAM Journal on Optimization, 2005, 16(1): 170-192. doi: 10.1137/030601880 CrossRef Google Scholar
[5]	POWELL M J D. Convergence Properties of Algorithms for Nonlinear Optimization[J]. SIAM Review, 1986, 28(4): 487-500. doi: 10.1137/1028154 CrossRef Google Scholar
[6]	GILBERT J C, NOCEDAL J. Global Convergence Properties of Conjugate Gradient Methods for Optimization[J]. SIAM Journal on Optimization, 1992, 2(1): 21-42. doi: 10.1137/0802003 CrossRef Google Scholar
[7]	WEI Z X, YAO S W, LIU L Y. The Convergence Properties of Some New Conjugate Gradient Methods[J]. Applied Mathematics and Computation, 2006, 183(2): 1341-1350. doi: 10.1016/j.amc.2006.05.150 CrossRef Google Scholar
[8]	SHENGWEI Y, WEI Z X, HUANG H. A Note about WYL's Conjugate Gradient Method and Its Applications[J]. Applied Mathematics and Computation, 2007, 191(2): 381-388. doi: 10.1016/j.amc.2007.02.094 CrossRef Google Scholar
[9]	HUANG H, LIN S H. A Modified Wei-Yao-Liu Conjugate Gradient Method for Unconstrained Optimization[J]. Applied Mathematics and Computation, 2014, 231: 179-186. doi: 10.1016/j.amc.2014.01.012 CrossRef Google Scholar
[10]	黎勇, 韦增欣. 一种自动充分下降的共轭梯度法[J]. 西南师范大学学报(自然科学版), 2016, 41(5): 36-40. Google Scholar
[11]	黎勇. 一类修正PRP共轭梯度法的全局收敛性及其数值试验结果[J]. 西南大学学报(自然科学版), 2011, 33(11): 23-28. Google Scholar
[12]	林穗华. 一类充分下降共轭梯度法的全局收敛性[J]. 吉林大学学报(理学版), 2017, 55(4): 874-880. Google Scholar
[13]	林穗华. 基于Wolfe线搜索的修正共轭梯度算法[J]. 安徽大学学报(自然科学版), 2018, 42(2): 47-53. Google Scholar
[14]	关哲, 于宪伟. 标准Wolfe线搜索下修正的DY共轭梯度法[J]. 西南师范大学学报(自然科学版), 2016, 41(1): 31-34. Google Scholar
[15]	赛·闹尔再, 张慧玲. 修正LS共轭梯度方法及其收敛性[J]. 西南师范大学学报(自然科学版), 2016, 41(7): 20-26. Google Scholar
[16]	李春念, 袁功林. 求解无约束问题的修正PRP共轭梯度算法[J]. 西南大学学报(自然科学版), 2018, 40(9): 67-75. Google Scholar
[17]	YUAN G L, WEI Z X, LI G Y. A Modified Polak-Ribière-Polyak Conjugate Gradient Algorithm for Nonsmooth Convex Programs[J]. Journal of Computational and Applied Mathematics, 2014, 255: 86-96. Google Scholar
[18]	YUAN G L, WEI Z X, LU X W. Global Convergence of BFGS and PRP Methodsunder a Modified Weak Wolfe-Powell Line Search[J]. Applied Mathematical Modelling, 2017, 47: 811-825. Google Scholar
[19]	ANDREI N. An Unconstrained Optimization Test Functions Collection[J]. Advanced Modeling and Optimization, 2008, 10(1): 147-161. Google Scholar
[20]	DOLAN E D, MORÉ J J. Benchmarking Optimization Software with Performance Profiles[J]. Mathematical Programming, 2002, 91(2): 201-213. doi: 10.1007%2Fs101070100263 CrossRef Google Scholar

Message Board

Global Convergence of Some Improved Conjugate Gradient Methods

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors