当前位置：文档之家 › 非线性方程组问题的一个三项共轭梯度算法

非线性方程组问题的一个三项共轭梯度算法

  • 格式：pdf
  • 大小：336.02 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

非线性共轭梯度法

非线性共轭梯度法

非线性共轭梯度法
（Nonlinear Conjugate Gradient Method）
非线性共轭梯度法是一种基于梯度的迭代优化方法，用于求解无约束最优化问题，即求解目标函数f(x)的最小值。

它可以用来求解深度神经网络中参数的最优化。

非线性共轭梯度法的基本思想是利用梯度下降法的思路，但是在每次迭代时都会调整步长，使得每次迭代可以尽可能地朝着最优解方向前进。

该方法有两个重要特征：1）步长调整。

2）共轭梯度（CG）。

步长调整：在每次迭代中，搜索方向不仅可以与梯度方向一样，而且也可以与之前的搜索方向有一定的关系。

通过调整步长，可以把搜索方向调整到最优方向，从而更快地收敛到最优解。

共轭梯度：对于多维的优化问题，搜索空间是一个高维空间，如果每次都沿着梯度方向搜索，就容易陷入局部最优解。

为了避免这种情况，非线性共轭梯度法引入了共轭搜索方向，即在每次迭代中，新的搜索方向都与上一次的搜索方向有一定的关系。

这样做的好处是，在不断地迭代中，法线方向也可以被搜索到，从而可以跳出局部最优解，有效地收敛到全局最优解。

共轭梯度法程序

共轭梯度法程序

一、共轭梯度法共轭梯度法（Conjugate Gradient）是共轭方向法的一种，因为在该方向法中每一个共轭向量都是依靠赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。

由于此法最先由Fletcher和Reeves （1964）提出了解非线性最优化问题的，因而又称为FR 共轭梯度法。

由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用于实际问题中。

共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便，效果好。

二、共轭梯度法的原理设有目标函数f（X）=1/2X T HX+b T X+c 式1 式中，H作为f（X）的二阶导数矩阵，b为常数矢量，b=[b1,b2,b3,...b n]T 在第k次迭代计算中，从点X（k）出发，沿负梯度方向作一维搜索，得S(K)=-∆f（X（k））式2 X(k+1)=X(k)+ɑ(k)S(k) 式3在式中，ɑ（k）为最优步长。

设与S(k）共轭的下一个方向S(k+1)由点S(k）和点X(k+1)负梯度的线性组合构，即S (k+1)=-∆f （X （k+1））+β(k)S (k) 式4 根据共轭的条件有[S (k)]T ∆2f （X (k)）S (k+1)=0 式5 把式2和式4带入式5，得-[∆f(X (k))]T ∆2f （X (k)）[-∆f （X （k+1））+β(k)S (k) ]=0 式6 对于式1，则在点X (k)和点X (k+1)的梯度可写为∆f(X (k))=HX (k)+b 式7 ∆f （X （k+1）)=HX (k+1)+b 式8 把上面两式相减并将式3代入得ɑ(k)H S (k)=∆f （X （k+1）)-∆f(X (k)) 式9 将式4和式9两边分别相乘，并代入式5得-[∆f （X （k+1）)+β(k)∆f(X (k))]T [∆f （X （k+1）)-∆f(X (k)]=0 式10 将式10展开，并注意到相邻两点梯度间的正交关系，整理后得 β（k ）=22||))((||||))1((||k X f k X f ∆+∆ 式11把式11代入式4和式3，得 S （k+1）=-∆f （X (k)）+β（k ）S （k ）X (k+1)=X （k ）+ɑ（k ）S （k ）由上可见，只要利用相邻两点的梯度就可以构造一个共轭方向。

共轭梯度法

共轭梯度法

最速下降法1.最速下降方向函数f(x)在点x处沿方向d的变化率可用方向导数来表示。

对于可微函数，方向导数等于梯度与方向的内积，即：Df(x;d) = ▽f(x)T d,因此，求函数f(x)在点x处的下降最快的方向，可归结为求解下列非线性规划：min ▽f(x)T ds.t. ||d|| ≤ 1当 d = -▽f(x) / ||▽f(x)||时等号成立。

因此，在点x处沿上式所定义的方向变化率最小，即负梯度方向为最速下降方向。

2.最速下降算法最速下降法的迭代公式是x(k+1) = x(k) + λk d(k) ,其中d(k)是从x(k)出发的搜索方向，这里取在x(k)处的最速下降方向，即d = -▽f(x(k)).λk是从x(k)出发沿方向d(k)进行一维搜索的步长，即λk满足f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).计算步骤如下：(1)给定初点x(1) ∈ R n，允许误差ε> 0，置k = 1。

(2)计算搜索方向d = -▽f(x(k))。

(3)若||d(k)|| ≤ε，则停止计算；否则，从x(k)出发，沿d(k)进行一维搜索，求λk，使f(x(k) + λk d(k)) = min f(x(k)+λd(k)) (λ≥0).(4)令x(k+1) = x(k) + λk d(k)，置k = k + 1，转步骤(2)。

共轭梯度法1.共轭方向无约束问题最优化方法的核心问题是选择搜索方向。

以正定二次函数为例，来观察两个方向关于矩阵Ａ共轭的几何意义。

设有二次函数：f(x) = 1/2 (x - x*)T A(x - x*) ,其中A是n×n对称正定矩阵，x*是一个定点，函数f(x)的等值面1/2 (x - x*)T A(x - x*) = c是以x*为中心的椭球面，由于▽f(x*) = A(x - x*) = 0，A正定，因此x*是f(x)的极小点。

共轭梯度法

共轭梯度法
线性无关，由线性代数知识知
必有
p
T j
∇f
(X
n
)
=0(源自j=0,1,L,
n
− 1)
因为A正定，所以f (X ) 是凸函数，故 X n 是惟一的全局 极小点。
从而
∇f (Xk ) = AXk + b
=
AX
j+1
+
λ* j+1
Apj+1
+L+
λ* k −2
Apk−2
+
λ* k −1
Apk
−1
+
b
=
∇f
(X
⎡6 ⎢⎣17
12⎤ 17⎥⎦
⎢⎣⎡−
90 289
−
210⎤ 289⎥⎦
T
−
210⎤⎡ 3 289⎥⎦⎢⎣−1
−11⎥⎦⎤⎢⎣⎡−
90 289
−
210⎤T 289⎥⎦
= 17 10
X2
=
X1
+
λ1 p1
=
⎡ 26 ⎢⎣17
38 ⎤ T 17 ⎥⎦
+ 17 10
⎢⎣⎡−
90 289
−
210 ⎤ T 289 ⎥⎦
= [1
1]T
∇f ( X 2 ) = [0 0]T
练习： 试用共轭梯度法二次函数
min
f
(x)
=
x12
+
1 2
x22
+
1 2
x32
的极小点。取初始点为x( 0 ) = (1,1,1)T
3 、非二次函数的共轭梯度法
一般地，我们有：
⎧ X k+1 = X k + λk pk

非线性优化算法-牛顿法_DFP_BFGS_L-BFGS_共轭梯度算法

非线性优化算法-牛顿法_DFP_BFGS_L-BFGS_共轭梯度算法

统计学梯度下降法（SGDs）易于实现，然而它有两个主要的缺陷。

第一个缺陷是它需要手动调谐大量的参数，比如学习速率和收敛准则。

第二个缺陷是它本质上是序列方法，不利于并行计算或分布式计算。

（然而，在计算资源如RAM受限的情况下，序列方法倒是一个不错的选择。

）这里介绍一些非线性优化算法：牛顿算法，伪牛顿算法和共轭梯度法。

其中，伪牛顿算法包括DFP、BFGS和L-BFGS算法。

考虑如下的无约束最小化问题：min x f(x)（1）其中x=(x1,…,x N)T∈ℝN. 为简便起见，这里假设f是凸函数，且二阶连续可导。

记（1）的解为x∗.牛顿算法（Newton‘s Method）基本思想：在现有的极小点估计值的附近对f(x)做二阶泰勒展开，进而找到下其中g(k)=∇f(x)|x(k)是梯度矩阵，H(k)=∇2f(x)|x(k)是海森矩阵。

牛顿算法是一种具有二次收敛性的算法。

对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的领域，则其收敛速度也是很快的，这是牛顿算法的主要优点。

但牛顿算法由于迭代公式中没有步长因子，而是定步长迭代，所以对于非二次函数，有时会出现f(x(k+1))>f(x(k))的情况，这表明牛顿算法不能保证函数值稳定地下降。

由此，人们提出了阻尼牛顿算法，在原始牛顿算法的第4步中，采用一维搜索（line search）算法给d(k)加一个步长因子λ(k)，其中：λ(k)=arg minλ∈ℝf(x(k)+λd(k))（2）一维搜索算法将另作介绍。

拟牛顿算法（Quasi-Newton Methods）基本思想：不直接计算二阶偏导数，而是构造出近似海森矩阵（或海森矩阵的逆）的正定对称阵，在拟牛顿条件下优化目标函数。

下文中，用B表示对H的近似，用D表示对H−1的近似，并令s(k)=x(k+1)−x(k)，y(k)=g(k+1)−g(k).⒈拟牛顿条件（割线条件）对f(x)做二阶泰勒展开可得：y(k)≈H(k+1)×s(k)（3）或s(k)≈(H(k+1))−1×y(k)（4）⒉DFP算法核心：通过迭代的方法，对(H(k+1))−1做近似。

求解非线性无约束优化问题的两种方法的分析

求解非线性无约束优化问题的两种方法的分析

垫墼兰￡望叁兰堑圭兰垒篁塞１第一章预备知识§１．１共轭梯度方法§１．１．１引言共轭梯度法足最优化中最常用的方法之一。

它具有算法简便，存储需求小等优点，十分适合于大规模优化问题．在石油勘探，大气模拟，航天航空等领域出现的特大规模的优化问题是常常利用共轭梯度法求解。

在所有需要计算导数的优化方法中，最速下降是最简单的，但它速度太慢。

拟牛顿方法收敛速度很快，被广泛认为是非线性规划的最有效的方法。

但拟牛顿法需要存储矩阵以及通过求解线性方程组来计算搜索方向，这对于求解诸如上述问题等一些大规模问题几乎是不太可能办到的，共轭梯度法在算法的简便性，所需存储量等方面均与最速下降法差别不大，而收敛速度比最速下降法要快。

非线性共轭梯度法的收敛性分析的早期工作主要由Ｆｌｅｔｃｈｅｒ，Ｐｏｗｅｌｌ，Ｂｅａｌｅ等学者给出的，近年来，Ｎｏｃｅｄａｌ，Ｇｉｌｂｅｒｔ，Ｎａｚａｒｅｔｈ等学者在收敛性方面得到了不少的结果，使得共轭梯度法的研究由又热了起来．我国的学者也在共轭梯度法的理论研究中也取得了一定的成绩。

例如中科院应用数学所的韩继业，戴口等．§１．１．２共轭方向法共轭梯度法最本质的是共轭性质，共轭性是正交的一种推广。

定义１．１．２．１：设Ｗ∈咿×ｎ对称正定，ｄｌ，ｄ２，…，ｄ。

是咿中的一组非零向量，如果盯Ａｄｊ＝０，（ｉ≠Ｊ）．（１．１）则称ｄ１，ｄ２，…，ｄ。

是相互Ａ一共轭。

显然可见，如果ｄｌ，ｄ２，…，ｄ。

相互Ａ一共轭，则它们是线性无关的。

设Ｊ是单位阵则知，一共轭就是正交。

一般共轭方向法步骤如下：算法１．１．２．１：（一般共轭方向法）给出∞＋的初始点Ｘｌ，步ｌ：计算ｇｌ＝ｇ（Ｘ１）．步２：计算ｄｌ，使（ｆ｛’９ｌ＜０．步３：令女＝１．步４：计算口ｋ和Ｘｋ＋１，使得ｆ（ｘｋ－Ｆ‘１ｋｄｋ）。

Ｉ。

ｊ１１，‰十“呶），Ｘｋ＋１＝Ｘｋ＋ｖ。

ｋｄｋ．步５：计算以＋ｌ使得ｄ矗１Ｇｄｊ＝０，Ｊ＝１，２，…ｋ．步６：令ｋ：＝ｋ＋１，转步４．共轭方向法的一个基本性质是：只要执行精确线性搜索，就能得到二次终止性，这就足下面的共轭方向法基本定理。

共轭梯度法在优化问题中的应用

共轭梯度法在优化问题中的应用共轭梯度法是一种高效的优化算法，在许多优化问题中都得到了广泛的应用。

它是一种迭代方法，用于解决最小化二次函数的优化问题。

在本文中，我将介绍共轭梯度法的原理和算法，并探讨它在优化问题中的应用。

一、共轭梯度法的原理共轭梯度法的核心思想是通过迭代的方式，找到一个与之前迭代步骤方向相互垂直的搜索方向，以加快收敛速度。

在每一次迭代中，共轭梯度法根据当前的搜索方向更新搜索点，直到找到最优解或达到预定的收敛标准。

具体来说，共轭梯度法从一个初始搜索点开始，计算对应的梯度，并沿着负梯度方向进行搜索。

通过一定的方法找到一个与之前搜索方向相互垂直的新搜索方向，并以一定步长更新搜索点。

迭代过程将重复进行，直到满足收敛标准或达到最大迭代次数。

二、共轭梯度法的算法共轭梯度法的算法包括以下几个步骤：1. 初始化搜索点x0和梯度g0，设置迭代次数k=0。

2. 计算当前搜索方向d_k=-g_k（k为当前迭代次数）。

3. 通过一维搜索方法找到最佳步长α_k。

4. 更新搜索点x_k+1 = x_k + α_k * d_k。

5. 计算更新后的梯度g_k+1。

6. 判断是否满足收敛标准，若满足则算法停止，否则转到步骤7。

7. 计算新的搜索方向β_k+1。

8. 将迭代次数k更新为k+1，转到步骤3。

这个算法保证了每一次迭代中的搜索方向都是彼此相互垂直的，从而加快了收敛速度。

三、共轭梯度法的应用共轭梯度法在优化问题中有广泛的应用，特别是在二次规划、线性规划和非线性规划等领域。

在二次规划问题中，共轭梯度法可以高效地求解线性系统Ax=b，其中A是一个对称正定的矩阵。

由于共轭梯度法的特性，它只需要进行n 次迭代，其中n是问题的维度，就能得到精确的解。

这使得共轭梯度法在大规模线性系统求解中具有重要的应用价值。

在线性规划问题中，共轭梯度法可以用于求解带有线性约束的最小二乘问题。

共轭梯度法通过将线性约束转化为一系列的正交子空间，从而在求解最小二乘问题时能够更快地收敛。

共轭梯度法


证明：采用数学归纳法, 不过, 还是省略它
(5.8)意味着 d iT Qd j 0, j i, i 1, 2, , n - 1 即Broyden 族在用精确搜索求解凸二次函数极小化问题 时, 所产生的方向关于矩阵Q相互共轭.属于共轭方向法.
前面讨论的共轭方向法 需要在算法之初 产生 n个共轭方向，因而需要很大的存贮量，而且 不能用来求解非二次问题.
j 0 k
dT j Qp k 1 d Qp j
T j
d j,
(5.5)
步2 若k n - 2, 则停止, 否则, 令k : k 1, 转步1.
容易验证, 由算法5.1产生的向量组 d 0 , d1 , , d n-1 R n 关于矩阵Q相互共轭
下面的定理解释了第四章介绍的Broyden 族具有二次终 止性的根本原因 :
其中 k 是待定参数, 适当选取 k , 使得 d kT Qd k -1 0.
一般地, 搜搜方向的计算公式为： - f ( x0 ), dk - f ( xk ) k d k -1 , k 0 k 1 (5.10)
在下面我们来推导 (5.10) 参数 k 的计算公式 :
d k -f ( xk ) k d k -1
其中 k 是由精确搜索得到的步长. 即满足
于是求得
d kT-1Qf ( xk ) k T dk -1Qd k -1
在该计算式中含矩阵Q, 为减少计算量及使共轭梯度能 用于求解非二次函数的优化问题, 在计算式中消除 Q.
由上面的条件得到
T T T p0 Qp1 - p0 Qf ( x1 ) p0 Qp 0 0
等值线
f ( x1 )
由此解得 所以 p Qf ( x1 ) T p0 Qp 0

共轭梯度法总结

共轭梯度法总结
共轭梯度法总结
一、什么是共轭梯度法
共轭梯度法（Conjugate Gradient Method），是一种用于求解线性方程组的迭代优化算法，它是一种搜索梯度的迭代算法。

共轭梯度法的基本思想是沿梯度的反方向搜索，并在每一步令搜索的方向接近更新的局部梯度。

它是一种非常有效的求解有约束的非线性优化问题的方法，是求解线性方程组的有效算法。

共轭梯度法可以看作是一种极小化函数的迭代方法，它最主要的思想是不断更新梯度的方向，从而寻找函数值最小的点。

二、共轭梯度法的原理
共轭梯度法是一种迭代优化算法，它以凸二次型函数为例，可以用来求解最小值问题。

它的基本思想是：
（1）首先求得函数的梯度，即每一步优化的搜索方向，使梯度变为最小；
（2）以梯度的反方向搜索，令搜索的方向接近更新的局部梯度，而不是与旧的梯度成正比的步长；
（3）逐步更新搜索的方向为新的梯度；
（4）重复这个过程，直到所有的自变量满足限制条件。

三、共轭梯度法的优缺点
共轭梯度法最大的优点是它具有收敛速度快，可以在有限的迭代步数内收敛到最优解；另外，它还具有计算量小，不需要计算精确的
Hessian矩阵的优点。

共轭梯度法的缺点是它不能用来求解非凸优化问题，因为它只能求解凸优化问题；另外，它也不能用于强不可约的优化问题。

非线性代数方程(组)的解法


06
应用举例与算法实现
应用举例
经济学
非线性方程组在经济学中广泛应用于描述市场均衡、消费者行为等问题。例如，求解供需平衡价格时，可以通过构建 非线性方程组来表示供给和需求函数，进而求解市场均衡价格。
工程学
在机械、电子等工程领域，非线性方程组常用于描述系统的动态行为。例如，在控制系统中，通过建立非线性状态方 程来描述系统的状态变化，可以求解系统的稳定性、响应特性等问题。
拟牛顿法是对牛顿法的改进，通过近 似计算雅可比矩阵或其逆矩阵来减少 计算量。常见的拟牛顿法有BFGS方 法、DFP方法等。程序设计时，需要 实现拟牛顿法的迭代过程，包括选择 合适的拟牛顿公式、更新近似矩阵等 步骤。
信赖域方法
信赖域方法是一种全局收敛的非线性 方程组求解算法，其基本思想是在每 次迭代中构造一个信赖域，然后在该 区域内寻找使目标函数充分下降的试 探步。程序设计时，需要实现信赖域 方法的迭代过程，包括构造信赖域、 求解子问题、更新信赖域半径等步骤 。
04
解析解法分离变量法源自01 适用于可将方程中的变量分离为两个或多个独立 函数的情况。
02 通过将方程两边同时积分，得到各变量的通解。 03 需要注意积分常数的确定，以及解的合理性验证。
行波法
01
适用于可化为行波形式的非线性方程。
02
通过引入行波变换，将原方程化为关于行波参数的常微分方 程。
03
步骤
1. 选定适当的坐标轴，将方程的变量表 示为坐标轴上的点。
等倾线法
定义：等倾线法是一种通过绘 制等倾线（即斜率相等的线） ，从而找出方程解的方法。
步骤
1. 将方程转化为斜率形式， 即 y' = f(x, y)。
3. 通过观察等倾线的交点、 切线等性质，可以判断方程 的解的存在性、唯一性等。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

2. 公式和算法
建议的三项共轭梯度公式如下：
d k +1
k= 0 −qk +1 , T T qk +1 yk d k − qk +1d k yk = (2.1) −q + , k ≥1 k +1 δ d y + δ q 2 + δ d T q 1 k k 2 k 3 k k
q= q ( xk +1 ) , = qk q ( xk ) , = yk qk +1 − qk ， δ1 > 0, δ 2 > 0, δ 3 > 0 是常数。上述公式的思想是受文章[7] k +1
2 1 q ( x ) , ⋅ 表示欧式范数。则非线性方程组问题 (1.1) 就转化为了一个最小值的优化问题 2 (1.2)，我们将对(1.2)提出其求解的新算法。求解一个最优化问题，常采用数值迭代方法，一般的迭代公 式定义为
xk + = xk + α k d k , 1
(1.3)
迭代点 xk +1 (或称为下一个迭代点)；依次类推，根据(1.3)产生一个迭代序列 { xk } ，设计算法主要是分析迭 代序列 { xk } 是否收敛到某一聚点 x∗ 或得到 E ( xk ) → 0 ？ 本文将针对(1.2)设计一个新的三项共轭梯度法，众所周知共轭梯度算法是一类非常有效的求解目标 函数最小值的优化方法[1] [2] [3] [4] [5]，特别是对大规模优化问题，其搜索方向定义形式是：
d k 是搜索方向， α k 表示步长， xk 代表第 k 次迭代点(或称为当前点)，有了 d k 和 α k ，产生第 k + 1 个
− q ( xk +1 ) , d k +1 = −q ( xk +1 ) + β k d k
0 k= k ≥1
β k ∈ R 表示共轭梯度参数，它是共轭梯度法设计的关键。鉴于此方法设计简单、程序容易实现，很多学
k →+∞
成立。 此定理被称为算法 1 的全局收敛性定理。
4. 数值实验
为验证建议的三项共轭梯度算法是有效的，本节将对下面的问题(见表 1)利用计算机编写程序计算。 我们将利用 Matlab R2009a 编写程序代码，程序是在 Windows 7 系统、CPU 为 Intel (R) Xeon (R)， E5507 2.27 GHz、64 位操作系统、6.00GB 内存上运行。算法中的参数选取分别是： δ1 = 0.02 ， δ = 0.002 ，
摘
要
本文设计一个三项共轭梯度算法，用来求解非线性方程组问题，建议的算法优点是：(1) 搜索方向的充 分下降性；(2) 搜索方向的信赖域特点；(3) 算法能保证具有全局收敛性；(4) 算法能成功求解一千维 以上的非线性方程组问题。
文章引用: 黄玲花. 非线性方程组问题的一个三项共轭梯度算法[J]. 运筹与模糊学, 2017, 7(1): 31-36. https:///10.12677/orf.2017.71004
Operations Research and Fuzziology 运筹与模糊学, 2017, 7(1), 31-36 Published Online February 2017 in Hans. /journal/orf https:///10.12677/orf.2017.71004
Open Access
1. 引言
本文研究下面的非线性方程组问题：
q= ( x ) 0, x ∈ ℜn , min E ( x ) , x ∈ ℜn ,
其中 E ( x ) =
(1.1)
q : ℜn → ℜn 是连续可微函数，不难看出问题(1.1)的求解等价于求解如下形式的最小值优化问题模型：
(1.2)
Nr. 1 2 3 4 5 6 7 8 9 10 名称 Exponential function 2 Trigonometric function Logarithmic function Broyden Tridiagonal function Trigexp function Strictly convex function 1 Variable dimensioned function Extended Freudentein and Roth function Discrete boundary value problem Troesch problem
T qk +1d k +1 = − q k +1 2
(3.1)
和
β1 qk ≤ d k ≤ β 2 qk
β 2 ≥ β1 > 0 是常数。
(3.2)
证明：根据(2.1)的定义形式， k = 1 时，不难获得(3.1)和(3.2)。下面讨论 k > 1 时的情况，同样利用(2.1)有
T T qk T T +1 yk d k − qk +1 d k yk = − + qk d q q +1 k +1 k +1 k +1 δ1 d k yk + δ 2 qk 2 + δ 3 d kT qk T T T T qk 2 +1 yk qk +1 d k − qk +1 d k qk +1 yk = − qk +1 + 2 δ1 d k yk + δ 2 qk + δ 3 d kT qk
qk +1 yk d k + qk +1 yk d k
δ1 d k yk + δ 2 qk δ1 d k yk + δ 2 qk
2
2 qk +1 yk d k
2
2 ≤ 1 + Fk +1 , + δ3 d q δ1
T k k
33
黄玲花
最后一个不等式利用了
1
δ1 d k yk + δ 2 qk
T T qk +1 yk d k − qk +1 d k yk
δ1 d k yk + δ 2 qk
2
+ δ 3 d kT qk + δ 3 d kT qk
≤ −qk +1 +
T T qk +1 yk d k − qk +1 d k yk
δ1 d k yk + δ 2 qk
2
+ δ 3 d kT qk
= − qk +1 ,
从而获得(3.1)。根据(3.1)的结果，易得
T − = q k +1 qk +1d k +1 ≥ − qk +1 d k +1 , 2
2
取 β1 ∈ ( 0,1) ，则(3.2)式的左边成立。关于(3.2)的右边不等式，需要再次利用(2.1)来获得 +1 + ≤ qk +1 + = qk +1 +
th st th
Received: Feb. 6 , 2017; accepted: Feb. 21 , 2017; published: Feb. 24 , 2017
Abstract
This paper designs a three-term conjugate gradient algorithm for nonlinear equations problems and the proposed algorithm has four advantages: (1) the sufficient descent property is satisfied for the search direction; (2) the trust region feature holds for the direction too; (3) the global convergence of the proposed algorithm is possessed; (4) the new algorithm can successfully solve nonlinear equations problems with 1000 dimensions.
δ= δ= 0.6 ， α = 10−4 。表 2 中第一行参数含义分别是：NI 代表迭代次数，Nq 代表函数值次数，Dim 2 3
代表所检验问题的维数， Cpu-Time 代表程序在计算机上运行的 CPU 时间， Val 代表程序终止时的范数值。
Table 1. Problems name 表 1. 问题名称
q ( x ) − q ( y ) ≤ L x − y , ∀x, y ∈ ℜn ，
L > 0 是 Lipschitz 常数。
根据假设 A 和获得的引理 3.1，便可以证明算法 1 的全局收敛性结论。此结论的证明与参考文献[7] 的证明过程相似，我们就不再详述。 定理 3.1：若迭代序列 { xk , d k , α k , qk } 是由算法 1 产生的且假设 A 的条件满足，则关系式 lim inf qk = 0
( xk − tk ) q t ( k) 2 q ( tk )
T
(2.3)
步骤 6：置 k = : k + 1 ，转到步骤 1。 注：线搜索技术(2.2)是文献[7]最先给出，(2.3)是投影技术，由文献[9]给出。
3. 信赖域特点、充分下降性以及全局收敛性
我们首先通过下面的引理证明算法 1 的信赖域的特点和充分下降性。 引理 3.1：(2.1)产生的搜索方向 d k 满足
黄玲花
关键词
方程组问题，三项共轭梯度，全局收敛性
Copyright © 2017 by author and Hans Publishers Inc. This work is licensed under the Creative Commons Attribution International License (CC BY). /licenses/by/4.0/