当前位置：文档之家 › 一类改进的谱共轭梯度法

一类改进的谱共轭梯度法

  • 格式：docx
  • 大小：40.60 KB
  • 文档页数：9

一类改进的谱共轭梯度法

景书杰;李亚敏;牛海峰

【摘 要】谱共轭梯度法有两个方向控制参数,是解决大规模无约束优化问题的有效方法.本文提出了一个改进的谱参数θk,它不同于现有的θk.新算法在任何线搜索下都满足著名的共轭条件:dTk yk-1=0.新方法的搜索方向在任何线搜索下都是充分下降的.在一般假设下,我们证明该方法在改进的Wolfe线搜索是全局收敛的.

【期刊名称】《洛阳师范学院学报》

【年(卷),期】2019(038)002

【总页数】5页(P1-5)

【关键词】无约束优化;谱共轭梯度法;下降条件;谱参数;Wolfe线搜索

【作 者】景书杰;李亚敏;牛海峰

【作者单位】河南理工大学数学与信息科学学院,河南焦作454000;河南理工大学数学与信息科学学院,河南焦作454000;河南理工大学数学与信息科学学院,河南焦作454000

【正文语种】中 文

【中图分类】O221.2

0 引言

考虑无约束优化问题

(0.1)

其中f(x)在Rn→R上是连续可微的函数，Rn表示n维欧式空间. 我们定义g(x)=▽f(x)是f(x)在xk处的梯度向量，且令gk=g(xk).

由于非线性共轭梯度法(简称CG法)迭代简单有效，全局收敛性和低内存需求，故它是解决问题(0.1)的最有效的迭代方法之一，特别是在科学和工程计算中的大规模优化问题中. 在解决问题(0.1)的迭代算法中得到序列{xk}，它的一般迭代格式如下

xk+1=xk+αkdk

(0.2)

其中xk是当前迭代点，αk为步长.

这里βk∈Rn为共轭参数，不同的CG法是由不同形式的共轭参数βk决定. 本文被以下共轭参数所吸引：它们的βk公式[1-4]如下

这里代表Euclidean范数，yk:=gk+1-gk.

PRP和HS是公认的最有效的两个CG法，但它们的收敛性都不是很好. 已有很多关于收敛性的研究[5-11]. 这些CG法都有良好的收敛性和数值表现，然而它们构造复杂且难以理解，不像经典的CG法[1-4,12-15], 形式简单，容易应用，所以工程师们也很少把它们应用到科学和生产等研究中. 因此，Rivaie等[16]给出了一个形式简单的共轭参数为方便起见，我们称它为RMIL法.

2012年，Rivaie等[16]提出RMIL法的共轭参数，定义为

(0.3) 这里yk-1=gk-gk-1.显然

(0.4)

Rivaie等[16]验证了该方法产生的搜索方向dk是充分下降的，并在精确线搜索下建立了该算法的全局收敛性. 数值试验表明，RMIL法具有线性收敛速率，比其它CG法更有效.

2001年，Birgin 和Martinez[17]提出了谱共轭梯度法(SCG法)，即将谱梯度方法和CG法的思想结合起来，搜索方向dk的迭代格式如下

(0.5)

其中

这里θk是谱参数；sk-1=xk-xk-1；yk-1=gk-gk-1. 令人惊奇的是, SCG法在很多情况下优于经典的CG法. 但SCG法产生的搜索方向dk不满足下降条件并且没有证明算法是否是全局收敛性的. 故已有学者对此进行研究，使其修正的SCG法产生搜索方向dk是下降方向，并在一般假设下建立算法的全局收敛性.

Zhang等在文献 [18] 给出一个修正的FR共轭梯度法(MFR)，搜索方向dk如下

dk=-θkgk+βkdk-1

其中

显然，对k≥1，有成立. 即搜索方向dk是不依赖于任何线搜索的充分下降方向.

Zhang等[18]证明了MFR法对于一般的目标函数在Wolfe线搜索或Armijo线搜索下也具有全局收敛性.

2008年，Yu等[19]修正谱Perry共轭梯度法得到一个新的SCG法，称为DSP-CG法.的公式如下

这里

数值试验表明，对于任何的线搜索DSP-CG法都是下降方法. Yu等[19]证明了DSP-CG法对一般目标函数在Wolfe线搜索下是全局收敛性的.

最近，Deng等[20]改进了SCG算法，给出混合的θk和βk公式，定义为:

这里η是一个给定的小常数. 参数θk和βk的选择使得搜索方向dk既是充分下降的也是拟牛顿方向. 在Armijo线搜索下验证了改进的SCG算法的全局收敛性. 数值试验证实了改进的SCG算法比现存的算法更有效和稳定.

本文将展示一个改进的谱参数θk，进而结合文献 [16] 中的构造一个新的SCG法，我们称它为SRMIL法. 该方法的搜索方向dk不需要任何线搜索都是充分下降的.

我们建立了在修正的Wolfe线搜索下SRMIL法的全局收敛性.

1 谱参数θk及算法下降性

下面我们给出谱参数θk的选取方法. 我们给出的谱参数θk不依赖于任何线搜索而满足著名的共轭条件：给式(0.3)的两边同乘yk-1，可得

因此

所以

(1.1)

本文用SRMIL法解决问题(0.1)，该方法中xk和dk的迭代格式分别选用(0.2)和(0.5). 用式(0.3)计算βk，用式(1.1)计算θk. 故有SRMIL法满足著名的共轭条件.

算法:

Step 0： 给定初始值x0∈Rn，ε>0，令

0

Step 1： 计算gk； 若则停止，否则转Step 2.

Step 2： 计算步长αk>0，使其满足修正的Wolfe线搜索[21]：

(1.2)

Step 3： 利用式(0.3)，式(0.5)，式(1.1)，分别计算

Step 4： 令xk+1=xk+αkdk，求gk+1，并用(0.3)试求令令

k:=k+1，转Step 1.

基本假设H[22]

(H1)目标函数f(x)在水平集

l0={x∈Rn|f(x)≤f(x0)} 上有下界，其中x0为初始点.

(H2)目标函数f(x)在水平集l0的一个邻域N内连续可微，且梯度函数g(x)满足Lipschitz连续，即存在常数L>0，使

(1.3)

引理1.1 若假设 H 成立，则修正的 Wolfe 线搜索(1.2)是可行的，故必存在αk>0满足条件(1.2).

证明 类似于文献 [19] 中引理1的证明，这个结果的证明是显然的.

下面给出算法的充分下降条件.

引理1.2 设序列{gk}和{dk}由算法生成，则对任意k≥0，

(1.4)

和

(1.5)

成立.

证明 用数学归纳法证明.(i)当k=0时，有d0=-g0，则有成立.

(ii)假设有成立. 当k=k+1时，由式(0.4)，式(0.5)和式(1.1)有

(1.6)

综上，式(1.4)得证.

由式(1.6)，显然有式(1.5)成立.

2 全局收敛性

引理2.1[23] 若假设H成立，则由算法生成的序列{gk}和{dk}满足Zoutendijk条件

(2.1)

证明 由式(1.2)和式(1.3)，可得

因此

将上式的两边取平方得

由式(1.2)和假设H，可得

<+∞

定理2.1 若假设H成立，序列{gk}由迭代算法(0.2)和(0.5)产生，则有

(2.2)

证明 我们用反证法证明，反设结论不成立，则必存在常数γ>0，使得

对式(0.5)变形得

(2.3)

把(2.3)的两边取平方模，并移项得

上式两边除以得

再利用式(1.5)，得

(2.4) 注意到当k=0时，d0=-g0，所以，由式(2.4)得

所以

显然，这与引理2.1中的(2.1)矛盾，故

参考文献

【相关文献】

[1] Polak E,Ribiere G. Note Sur la Convergence de Methodes de Directions

Conjugees[J].Rev. Francaise Informat. Recherche Operationelle, 1969, 16(3): 35-43.

[2] Polyak B T. The Conjugate Gradient Method in Extreme Problems[J]. USSR

Computational Mathematics and Mathematical Physics, 1969, 9(4): 94-112.

[3] Hestenes M R,Steifel E. Method of Conjugate Gradient for Solving Linear Equations[J]. J.

Res. Nat. Bur. Stand., 1952, 49: 409-436.

[4] Liu Y,Storey C. Efficient Generalized Conjugate Gradient Algorithms Part 1: Theory[J]. J.

Comput. Appl. Math., 1992, 69(1):129-137.

[5] 戴彧虹,袁亚湘．非线性共轭梯度法[M]．上海： 上海科学技术出版社,2000．

[6] Hager W W,Zhang H. A New Conjugate Gradient Method with Guaranteed Descent

and an Efficient Line Search[J]. SIAM J.Optim., 2005, 16:170-192.

[7] Hager W W,Zhang H. A Survey of Nonlinear Conjugate Gradient Methods,Pacific

J.Optim.,2006,2:35-58.

[8] Yuan G,Lu X. A Modified PRP Conjugate Gradient Method,Ann. Oper. Res., 2009,

166:73-90.

[9] Wei Z X,Li G Y, Qi L Q. New Nonliner Conjugate Gradient Formulas for Large-scale

Unconstrained Optimization Problems[J]. Appl. Math. Comput., 2006, 179(2): 407-430.

[10] Dai Z F,Wan F H . Another Improved Wei-Yao-Liu Nonlinear Conjugate Gradient

Method with Sufficient Descent Property[J]. Appl. Math. Comput.,2012, 218(14): 7421-7430.

[11] Huang H,Lin S H .A Modified Wei-Yao-Liu Conjugate Gradient Method for

合集下载

预处理共轭梯度法

预处理共轭梯度法

预处理共轭梯度法

引言

预处理共轭梯度法是一种用于解决线性方程组问题的迭代方法。它在处理大规模稀疏方程组时表现出色，相比于传统的直接解法更具有高效性和稳定性。本文将对预处理共轭梯度法进行全面、详细、完整且深入地探讨。

什么是共轭梯度法

共轭梯度法是一种迭代优化方法，用于求解对称和正定的线性方程组Ax=b。它的基本思想是通过找到一组相互”共轭”的搜索方向来加速迭代过程。

预处理共轭梯度法的介绍

预处理共轭梯度法是对共轭梯度法的改进和优化。它通过在每一步迭代中应用预处理矩阵M来加速收敛过程。预处理矩阵通常是原方程系数矩阵A的逆或近似逆。预处理共轭梯度法的核心算法可以分为以下几个步骤：

步骤1：初始化

• 设定初始解x0和残差r0=b-Ax0。

• 计算初步搜索方向d0=M*r0。

步骤2：迭代计算

• 对于第k次迭代：

– 计算步长αk。

– 更新解：xk+1 = xk + αk * dk。

– 计算新的残差：rk+1 = rk - αk * Adk。

– 计算新的搜索方向：dk+1 = Mk+1 * rk+1。

步骤3：收敛判断

• 判断残差rk+1的范数是否满足收敛条件，若满足则终止迭代。 预处理矩阵的选择

预处理矩阵的选择是预处理共轭梯度法的关键。常见的预处理矩阵选择方法有以下几种：

1. 不完全因式分解预处理

不完全因式分解预处理是通过对系数矩阵的若干个元素进行保留或丢弃，得到一个近似逆矩阵。常见的不完全因式分解预处理方法有不完全LU分解、不完全Cholesky分解等。

2. 迭代求解预处理

迭代求解预处理方法是通过迭代方法求解预处理矩阵的逆。常见的迭代求解预处理方法有Jacobi预处理、Gauss-Seidel预处理等。

3. 基于特征值的预处理

基于特征值的预处理方法是通过对系数矩阵的特征值进行分析，选择适当的预处理矩阵。常见的基于特征值的预处理方法有谱条件预处理、谱平滑预处理等。

预处理共轭梯度法的收敛性和稳定性

求解无约束优化问题的下降谱共轭梯度法

求解无约束优化问题的下降谱共轭梯度法

第２７卷　Ｖｏ１．２７　第５期　Ｎｏ．５　重庆理工大学学报（自然科学）　Ｊｏｕｒｎａｌ　ｏｆ　Ｃｈｏｎｇｑｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ）　２０１３年５月　Ｍａｙ　２０１３　ｄｏｉ：１０．３９６９／ｊ．ｉｓｓｎ．１６７４－８４２５（ｚ）．２０１３．０５．０２７　求解无约束优化问题的下降谱共轭梯度法　黄　海　（广西民族师范学院数学与计算机科学系，广西崇左５３２２００）　摘　要：提出一种新的谱共轭梯度法，在Ｗｏｌｆｅ线搜索下算法具有下降性和全局收敛性。　实验结果表明：该方法具有较好的数值表现，适合于求解非线性无约束优化问题。　关键词：无约束优化；谱共轭梯度法；全局收敛　中图分类号：０２２１　文献标识码：Ａ　文章编号：１６７４—８４２５（２０１３）０５—０１２４—０５　Ａ　Ｄｅｓｃｅｎｔ　Ｓｐｅｃｔｒａｌ　Ｃｏｎｊｕｇａｔｅ　Ｇｒａｄｉｅｎｔ　Ｍｅｔｈｏｄ　ｆｏｒ　Ｕｎｃｏｎｓｔｒａｉｎｅｄ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ＨＵＡＮＧ　Ｈａｉ　（Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｍａｔｈｅｍａｔｉｃｓ　ａｎｄ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｇｕａｎｇｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ　ｆｏｒ　Ｎａｔｉｏｎａｌｉｔｉｅｓ，Ｃｈｏｎｇｚｕｏ　５３２２００，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｎｅｗ　ｓｐｅｃｔｒａｌ　ｃｏｎｊｕｇａｔｅ　ｇｒａｄｉｅｎｔ　ｍｅｔｈｏｄ　ｉｓ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ｔｈｅ　ｍｅｔｈｏｄ　ｉｓ　ｐｒｏｖｅｄ　ｔｏ　ｂｅ　ｄｅｓｃｅｎｓｉｖｅ　ａｎｄ　ｇｌｏｂａｌｌｙ　ｃｏｎｖｅｒｇｅｎｔ　ｉｆ　ｔｈｅ　Ｗｏｌｆｅ　ｌｉｎｅ　ｓｅａｒｃｈ　ｉｓ　ｕｓｅｄ．Ｐｒｅｌｉｍｉｎａｒｙ　ｅｘｐｅｒｉｍｅｎｔｓ　ｒｅ－　ｓｕｈｓ　ｓｈｏｗ　ｔｈａｔ　ｔｈｅ　ｎｅｗ　ｍｅｔｈｏｄ　ｗａｓ　ｅｆｆｅｃｔｉｖｅ，ｓｕｉｔａｂｌｅ　ｆｏｒ　ｓｏｌｖｉｎｇ　ｎｏｎｌｉｎｅａｒ　ｕｎｃｏｎｓｔｒａｉｎｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｐｒｏｂｌｅｍｓ．　Ｋｅｙ　ｗｏｒｄｓ：ｕｎｃｏｎｓｔｒａｉｎｅｄ　ｏｐｔｉｍｉｚａｔｉｏｎ；ｓｐｅｃｔｒａｌ　ｃｏｎｊｕｇａｔｅ　ｇｒａｄｉｅｎｔ　ｍｅｔｈｏｄ；ｇｌｏｂａｌ　ｃｏｎｖｅｒｇｅｎｃｅ　考虑无约束优化问题ｍｉｎ｛　）ｌ　∈Ｒ　｝，其中　ｆ：Ｒ　一　为一阶连续可微的非线性目标函数。共　轭梯度法是求解此类大规模非线性优化问题的一　类有效方法。自２０世纪６０年代Ｆｌｅｔｃｈｅｒ和　Ｒｅｅｖｅｓ提出解决非线性优化问题的共轭梯度法以　来，相关研究至今依然很活跃　。共轭梯度法　的一般迭代格式为　＋１＝　＋Ｏｔ　ｄ　（１）　ｄ　＝－ｇｋ＋　ｄ ，　：　ｃ２　ｄ　＋　ｄ　一１，　＞１　（２）　其中：　为步长；ｄ　为搜索方向；ｇ　＝ｖｆ（Ｘｋ）；卢　为参数。不同的参数　对应着不同的共轭梯度　法。几种著名方法的参数计算公式¨　如下：　ＩＩ　ｇ　Ｉｌ　＝　＝ｇ—ｒ（ｇｋ　，，ｅ，ｋ，Ｉ１Ｙｋ　口　一　一１　ｌｌ　ｇ　一１　ｌＩ　其中：ｙ　＝ｇ　一ｇ　；ｌｌ・ｌｌ为欧氏范数。　在迭代格式（２）下，ＤＹ方法具有独特的内在　性质：卢　：　，这一等价式在算法的收敛性　分析中起到很重要的作用，使得ＤＹ方法有着良好　昙　：　苫　基金资助项目（１１１６１００３），广西教育厅科研项目（２ｃ）１０１２Ｍｓ２１５）　昙　１然科９６９－－　警　器　法研究ｃ作者简介：黄海（　），男，广西武鸣人，副教授，主要从事最优化埋化与力　九。

求解大规模无约束优化问题的共轭梯度法

求解大规模无约束优化问题的共轭梯度法

求解大规模无约束优化问题的共轭梯度法

共轭梯度法是求解大规模无约束优化问题的一种重要方法，具有快速收敛、少存储、高效率等优势。本文起首介绍了共轭梯度法的基本原理及算法流程，接着对其收敛性进行了证明。随后，分析了共轭梯度法在实际应用中存在的一些问题，并提出了相应的解决方案。在此基础上，本文进一步探讨了共轭梯度法在无约束优化问题中的应用，并通过实例验证了其有效性。最后，本文对共轭梯度法的进步趋势进行了展望，指出其在大规模数据处理和机器进修领域中可能会有广泛的应用前景。

关键词：共轭梯度法；大规模无约束优化问题；收敛性；实际应用；进步趋势

一、引言

在科学探究和工程实践中，浩繁问题都可以转化为优化问题，因此优化问题的求解一直是探究热点之一。对于大规模无约束优化问题，由于其非线性、高维度、复杂性等特点，传统的优化算法往往难以胜任。共轭梯度法作为一种有效的优化方法，可以在这种状况下发挥重要作用。

二、共轭梯度法的基本原理及算法流程

共轭梯度法是求解无约束优化问题的一种迭代法，其基本思想是利用共轭梯度方一直加速迭代过程。详尽而言，该方法通过一系列的迭代步骤，不息更新查找方向和步长，以期找到最优解。其迭代流程如下：

（1）给出初始点 $x^{(0)}$，初始查找方向 $d^{(0)}$，初始步长 $\alpha^{(0)}$；

（2）计算 $x^{(k+1)}=x^{(k)}+\alpha^{(k)}d^{(k)}$；

（3）计算 $g^{(k+1)}=\nabla f(x^{(k+1)})$，其中

$f(x)$ 是目标函数的梯度；

（4）计算 $\beta^{(k+1)}=\frac{\left \| g^{(k+1)}

\right \|^2}{\left \| g^{(k)} \right \|^2}$；

（5）计算 $d^{(k+1)}=-g^{(k+1)}+\beta^{(k+1)}d^{(k)}$；

一种改进的非线性共轭梯度法

一种改进的非线性共轭梯度法

一种改进的非线性共轭梯度法

崔少勇;李廷锋;孙惠娟

【期刊名称】《河北联合大学学报（自然科学版）》

【年(卷),期】2008(030)002

【摘 要】共轭梯度法是求解大规模无约束优化问题的一种有效方法,对DY共轭梯度法的搜索条件进行了改进,并证明在新的Wolfe搜索条件下DY共轭梯度法具有全局收敛性,此方法的改进,为求解大规模无约束优化问题以及各种算法在今后的研究提供了参考.

【总页数】3页(P78-80)

【作 者】崔少勇;李廷锋;孙惠娟

【作者单位】河南大学,数学与信息科学学院,河南,开封,475004;河南大学,数学与信息科学学院,河南,开封,475004;河南大学,数学与信息科学学院,河南,开封,475004

【正文语种】中 文

【中图分类】O232

【相关文献】

1.求解非线性方程组的一种新共轭梯度法 [J], 王博朋;袁功林;胡午杰

2.改进的多参数非线性共轭梯度法的全局收敛性 [J], 黄海;林穗华

3.一种求解非线性无约束优化问题的充分下降的共轭梯度法 [J], Tsegay Giday

Woldu;张海斌;张鑫;张芳

4.一种新的三项共轭梯度法求解非线性方程组 [J], 廖若沙;

5.求解非线性方程组的一种三项共轭梯度法 [J], 胡午杰; 袁功林 因版权原因，仅展示原文概要，查看原文内容请购买