一种新的三项共轭梯度法求解非线性方程组

A New Three-Term Conjugate Gradient Method for Solving Nonlinear Equations

摘要: 本文在现有的三项共轭梯度法的基础上，设计了一种新的共轭梯度法JG求解非线性方程组问题，并在一定的假设条件下证明了JG算法的充分下降性和全局收敛性。通过数值实验的结果我们可以看到，JG算法与PRP算法相比具有更好的性质。

Abstract: Based on the existing three-term conjugate gradient method, this paper designs a new conjugate gradient method JG to solve the problem of nonlinear equations, and proves the sufficient descent and global convergence of JG algorithm under certain assumptions. From the results of numerical experiments, we can see that JG algorithm has better properties than PRP algorithm.

1. 引言

我们考虑如下非线性方程组：

$h\left(x\right)=0,x\in R^n$ (1)

其中 $h\left(x\right)=0$ 单调并连续可微。令 $F\left(x\right)=\frac{1}{2}{\Vert h\left(x\right)\Vert }^2$ ，则(1)式等价于求解(2)式的全局最优解：

$\min F\left(x\right),x\in R^n$ (2)

通常求解非线性方程组的迭代公式为：

$x_{k+1}=x_k+{\alpha }_k{d}_k$

其中 ${\alpha }_k$ 为沿搜索方向上的步长， $d_k$ 为搜索方向。

随着共轭梯度法的发展，产生了一系列的求解 $d_k$ 和 ${\alpha }_k$ 的方法 [1] [2] [3] [4] [5] ，例如标准的Wolfe线搜索：

$\begin{array}{l}F\left(x_{k+1}\right)-F\left(x_k\right)\le c_1{\alpha }_k{g}_k^{\text{T}}{d}_k\\ g_{k+1}^{\text{T}}{d}_k\ge c_2{g}_k^{\text{T}}{d}_k\end{array}$

其中 $0<c_1<c_2<1$ 为任意常数， $g_k:=\nabla F\left(x_k\right)$ 。

我们利用Yuan和Lu [6] 给出的一种新的线搜索：

$-g{\left(x_k+{\alpha }_k{d}_k\right)}^{\text{T}}{d}_k\ge \sigma {\alpha }_k\Vert g\left(x_k+{\alpha }_k{d}_k\right)\Vert {\Vert d_k\Vert }^2$ (3)

其中 ${\alpha }_k=\max \left\{s,\rho s,{\rho }^{2}s,\cdots \right\}$ ， $\sigma ,s>0$ ， $\rho \in \left(0,1\right)$ 。在一定的假设条件下，得到全局收敛性和超线性收敛。

Zhang [7] 提出了一种三项共轭梯度算法：

$d_k=\{\begin{array}{l}-g_k+{\beta }_k^{PRP}{d}_{k-1}-v_k{y}_k\text{if}k\ge 1\\ -g_k\text{if}k=0\end{array}$

其中 $g_k=g\left(x_k\right)$ ， ${\beta }_k^{PRP}=\frac{g_{k-1}^{\text{T}}{y}_k}{{\Vert g_{k-1}\Vert }^2}$ ， $v_k=\frac{g_k^{\text{T}}{d}_{k-1}}{{\Vert g_{k-1}\Vert }^2}$ ， $y_k=g_k-g_{k-1}$ 。由 $d_k$ 的定义易得：

$d_k^{\text{T}}{g}_k=-{\Vert g_k\Vert }^2$

根据上述算法及线搜索，本文给出一种新的三项共轭梯度算法JG：

$d_k=\{\begin{array}{l}-g_k+\frac{g_k^{\text{T}}{y}_k^{*}{d}_{k-1}-g_k^{\text{T}}{d}_{k-1}{y}_k^{*}}{\mu \Vert d_{k-1}\Vert \Vert y_k^{*}\Vert +v{\Vert y_k^{*}\Vert }^2+{\Vert g_{k-1}\Vert }^2+\eta \Vert g_{k-1}\Vert \Vert d_{k-1}\Vert +r{\Vert d_{k-1}\Vert }^2}\text{if}k\ge 1\\ -g_k\text{if}k=0\end{array}$ (4)

其中 $\mu >0$ ， $v>0$ ， $\eta >0$ ， $r>0$ ， $y_k^{*}=g_k-\frac{\Vert g_{k-1}\Vert }{\Vert g_k\Vert }{g}_{k-1}$ 。

2. 算法

新的三项共轭梯度算法JG的步骤如下：

Step 0：令初始点 $x_0\in R$ ， $\mu >0$ ， $v>0$ ， $\eta >0$ ， $r>0$ ； $\rho ,\epsilon \in \left(0,1\right)$ 。 $k:=1$ ；

Step 1：若 $\Vert g\left(x\right)\Vert \le \epsilon$ ，停止；否则转到Step 2；

Step 2：通过(4)式计算搜索方向 $d_k$ ；

Step 3：选择满足条件(3)的步长 ${\alpha }_k$ ；

Step 4：令迭代公式为 $w_k=x_k+{\alpha }_k{d}_k$ ；

Step 5：若 $\Vert g\left(x\right)\Vert \le \epsilon$ ，停止，令 $x_{k+1}=w_k$ ；否则令

$x_{k+1}=x_k-\frac{g{\left(w_k\right)}^{\text{T}}\left(x_k-w_k\right)}{{\Vert g\left(w_k\right)\Vert }^2}g\left(w_k\right)$ (5)

Step 6：令 $k:=k+1$ ，转Step 1。

注：(5)式 [8] 为 $x_k$ 在超平面 $H_k=\left\{x\in R^n|\langle g\left(w_k\right),x-w_k\rangle =0\right\}$ 上的投影。

3. 充分下降性和全局收敛性

我们给出如下两个假设条件：

假设1：(1)式的解集非空。

假设2： $g\left(x\right)$ 在 $R^n$ 上Lipschitz连续，即存在 $L>0$ 使得

$\Vert g\left(x\right)-g\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in R^n$ (6)

于是可以得到

$\Vert g_k\Vert \le \varsigma$

其中 $\varsigma >0$ 。

引理1：(4)式中的 $d_k$ 满足：

$g_{k+1}{d}_{k+1}\le -{\Vert g_{k+1}\Vert }^2$ (7)

和

$\Vert g_k\Vert \le \Vert d_k\Vert \le \left(1+\frac{2}{\mu }\right)\Vert g_k\Vert$ (8)

证明：由 $d_k$ 的定义可以直接得(7)式的结果，而利用(7)式可以得到(8)式的左半部分，接下来证明(8)式的右半部分。

$\begin{array}{c}\Vert d_k\Vert =\Vert -g_k+\frac{g_k^{\text{T}}{y}_k^{*}{d}_{k-1}-g_k^{\text{T}}{d}_{k-1}{y}_k^{*}}{\mu \Vert d_{k-1}\Vert \Vert y_k^{*}\Vert +v\Vert y_k^{*}\Vert +{\Vert g_{k-1}\Vert }^2+\eta \Vert g_{k-1}\Vert \Vert d_{k-1}\Vert +r{\Vert d_{k-1}\Vert }^2}\Vert \\ \le \Vert -g_k\Vert +\Vert \frac{g_k^{\text{T}}{y}_k^{*}{d}_{k-1}-g_k^{\text{T}}{d}_{k-1}{y}_k^{*}}{\mu \Vert d_{k-1}\Vert \Vert y_k^{*}\Vert +v\Vert y_k^{*}\Vert +{\Vert g_{k-1}\Vert }^2+\eta \Vert g_{k-1}\Vert \Vert d_{k-1}\Vert +r{\Vert d_{k-1}\Vert }^2}\Vert \\ \le \Vert -g_k\Vert +\frac{2\Vert g_k^{\text{T}}\Vert \Vert y_k^{*}\Vert \Vert d_{k-1}\Vert }{\mu \Vert d_{k-1}\Vert \Vert y_k^{*}\Vert }=\left(1+\frac{2}{\mu }\right)\Vert g_k\Vert \end{array}$

得证，故(8)式成立。 □

引理2：若假设1，假设2均成立， $\left\{x_k\right\}$ 和 $\left\{w_k\right\}$ 是由算法JG产生的点列，可得：

${\alpha }_k\ge \min \left\{s,\frac{\rho }{L+\sigma \Vert g\left({\hat{w}}_k\right)\Vert }\frac{{\Vert g\left(x_k\right)\Vert }^2}{{\Vert d_k\Vert }^2}\right\}$

其中 ${\hat{w}}_k=x_k+{\hat{\alpha }}_k{d}_k$ ， ${\hat{\alpha }}_k={\alpha }_k{\rho }^{-1}$ 。

证明：这里 ${\alpha }_k$ 由(3)式给出，如果 ${\alpha }_k\ne s$ ，那么 ${\hat{\alpha }}_k={\alpha }_k{\rho }^{-1}$ 不满足(3)式，即：

$-g{\left(x_k+{\alpha }_k{d}_k\right)}^{\text{T}}{d}_k<\sigma {\alpha }_k\Vert g\left(x_k+{\alpha }_k{d}_k\right)\Vert {\Vert d_k\Vert }^2$

成立。

由Lipschitz条件和(7)式：

${\Vert g_k\Vert }^2\le -g_k^{\text{T}}{d}_k\le {\left(g\left({\hat{w}}_k\right)-g\left(x_k\right)\right)}^{\text{T}}{d}_k+\sigma {\hat{\alpha }}_k\Vert g\left({\hat{w}}_k\right)\Vert {\Vert d_k\Vert }^2\le {\hat{\alpha }}_k\left(L+\sigma \Vert g\left({\hat{w}}_k\right)\Vert \right){\Vert d_k\Vert }^2$

则

${\alpha }_k\ge \frac{\rho }{L+\sigma \Vert g\left({\hat{w}}_k\right)\Vert }\frac{{\Vert g\left(x_k\right)\Vert }^2}{{\Vert d_k\Vert }^2}$

得证。 □

引理3：若假设1，假设2均成立， $\left\{x_k\right\}$ 是由算法JG产生的点列，若 $x_{*}$ 是(1)的解，即 $h\left(x_{*}\right)=0$ 成立，那么：

${\Vert x_{k+1}-x_{*}\Vert }^2\le {\Vert x_k-x_{*}\Vert }^2-{\Vert x_{k+1}-x_k\Vert }^2$ (9)

和

${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{\Vert x_{k+1}-x_k\Vert }^2}<\infty$ (10)

均成立。

证明：由g和超平面 $H_k$ 的单调性，可得：

$\langle g\left(w_k\right)-g\left(x_{*}\right),x_{*}-w_k\rangle =\langle g\left(w_k\right),x_{*}-w_k\rangle \le 0$

$x_{k+1}$ 为 $x_k$ 在 $M_k=\left\{x\in R^n|\langle g\left(w_k\right),x-w_k\rangle \le 0\right\}$ 上的投影。如果 $x_{*}$ 在 $M_k$ 上，则 $\langle x_k-x_{k+1},x_{k+1}-x_{*}\rangle \ge 0$ 。可得：

${\Vert x_k-x_{*}\Vert }^2={\Vert x_k-x_{k+1}\Vert }^2+{\Vert x_{k+1}-x_{*}\Vert }^2+2\langle x_k-x_{k+1},x_{k+1}-x_{*}\rangle \ge {\Vert x_k-x_{k+1}\Vert }^2+{\Vert x_{k+1}-x_{*}\Vert }^2$

整理得：

${\Vert x_{k+1}-x_k\Vert }^2\le {\Vert x_k-x_{*}\Vert }^2-{\Vert x_{k+1}-x_{*}\Vert }^2$

故(9)式成立。令 $k\to +\infty$ ，对该式进行累加，得(10)式成立，得证。 □

由(3)、(5)二式，得：

$\Vert x_{k+1}-x_k\Vert =\frac{\left|g{\left(w_k\right)}^{\text{T}}\left(x_k-w_k\right)\right|}{\Vert g\left(w_k\right)\Vert }=\frac{-{\alpha }_{k}g{\left(w_k\right)}^{\text{T}}{d}_k}{\Vert g\left(w_k\right)\Vert }\ge \sigma {\alpha }_k^2{\Vert d_k\Vert }^2$

由(10)式可知，当 $k\to +\infty$ 时：

$\Vert x_{k+1}-x_k\Vert \to 0$

综上可得：

$\underset{k\to +\infty }{\lim }{\alpha }_k{d}_k=0$ (11)

定理1若假设1，假设2均成立，序列 $\left\{{\alpha }_k,d_k,x_{k+1},g_{k+1}\right\}$ 由算法JG产生，则有

$\underset{k\to \infty }{\lim }\inf \Vert g_k\Vert =0$ (12)

证明：若(12)式不成立，则存在 $\delta >0$ 使得对任意 $K\ge 0$ 都有 $\Vert g_k\Vert \ge \delta$ 。结合式(8)，有：

$c_3\delta \le c_3\Vert g_k\Vert \le \Vert d_k\Vert \le c_4\Vert g_k\Vert \le c_4\zeta$

这里 $0<c_3<1$ ， $c_4=1+\frac{2}{\mu }$ 。由引理2可得：

$\begin{array}{c}{\alpha }_k\Vert d_k\Vert \ge \min \left\{s,\frac{\rho }{L+\sigma \Vert g\left({\hat{w}}_k\right)\Vert }\frac{{\Vert g\left(x_k\right)\Vert }^2}{{\Vert d_k\Vert }^2}\right\}\Vert d_k\Vert \\ \ge \min \left\{c_3\delta s,\frac{\rho \delta }{c_4\zeta \left(L+\sigma \varsigma \right)}\right\}>0\end{array}$

与(11)式矛盾，故(12)式成立，得证。 □

4. 数值实验

下面我们将JG算法与PRP算法作比较，选取九个测试函数 [9] 进行测试，结果见表1：

Table 1. Test functions

表1. 测试函数

数值实验的参数设置： $\mu =0.0001$ ， $v=0.0001$ ， $\eta =0.0001$ ， $r=0.0001$ ， $\epsilon ={10}^{-5}$ ，终止条件为 $\Vert g\left(x\right)\Vert \le {10}^{-5}$ ，其中CI为循环次数；CT为计算次数；GN为梯度值的范数。结果见表2：

Table 2. Numerical results

表2. 数值结果

我们根据计算次数(CT)给出图1，可以直观看到在相同条件下，算法JG所需迭代次数更少，图1如下所示：

Figure 1. Algorithm JG and algorithm PRP performance chart (CT)

图1. JG算法与PRP算法的性能比较(CT)

5. 结论

针对求解非线性单调方程组，本文采用文献6的线搜索，给出了一个三项共轭梯度算法JG，并且在一定的假设条件下得到了充分下降性和全局收敛性，从数值实验的结果可以看到，JG算法在与PRP算法比较起来具有更好的性质。