凸约束优化问题的杂交三阶投影HS-PRP方法

A Hybrid Three-Term Projected HS-PRP Method for Optimization with Convex Constraint

摘要: 本文提出了一种杂交三阶投影HS-PRP共轭梯度法求解凸约束优化问题并证明了该算法的全局收敛性，该方法是求解无约束优化问题的三阶HS共轭梯度法的推广。数值实验结果表明，该算法是有效的。

Abstract: In this paper, we propose a hybrid third-term projected HS-PRP conjugate gradient method for solving convex constrained optimization problems and establish its global convergence, which is a generalization of the third-term HS conjugate gradient method for unconstrained optimization. Numerical experimental results show that the algorithm is effective.

1. 引言

自共轭梯度法被提出以来，因其具有良好的收敛性质，且所需存储量小，因此被广泛用于求解大规模无约束优化问题。

共轭梯度法的基本迭代格式如下：

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

$d_k=\{\begin{array}{l}-g_k,k=0\\ -g_k+{\beta }_k{d}_k,k>0\end{array}$,

其中 ${\alpha }_k$ 为步长因子，由某种线搜索确定； $d_k$ 为搜索方向， ${\beta }_k$ 为共轭参数， $g_k=\nabla f\left(x_k\right)$。

共轭参数 ${\beta }_k$ 的经典选取方式有Fletcher-Reeves [1]，Polak-Ribière-Polyak [2]，Hestenes-Stiefel [3]，Dai-Yuan [4]，Conjugate Descent [5]，Liu-Storey [6] 六种，其具体表达式如下：

${\beta }_k^{FR}=\frac{{\Vert g_k\Vert }^2}{{\Vert g_{k-1}\Vert }^2}$, ${\beta }_k^{PRR}=\frac{g_k^{\text{T}}\left(g_k-g_{k-1}\right)}{{\Vert g_{k-1}\Vert }^2}$, ${\beta }_k^{HS}=\frac{g_k^{\text{T}}\left(g_k-g_{k-1}\right)}{d_{k-1}^{\text{T}}\left(g_k-g_{k-1}\right)}$,

${\beta }_k^{DY}=\frac{{\Vert g_k\Vert }^2}{d_{k-1}^{\text{T}}\left(g_k-g_{k-1}\right)}$, ${\beta }_k^{CD}=-\frac{{\Vert g_k\Vert }^2}{g_{k-1}^{\text{T}}{d}_{k-1}}$, ${\beta }_k^{LS}=-\frac{g_k^{\text{T}}\left(g_k-g_{k-1}\right)}{g_{k-1}^{\text{T}}{d}_{k-1}}$.

其中 $\Vert \cdot \Vert$ 表示Euclidean范数， $y_{k-1}=g_k-g_{k-1}$。由于分子不同，可将这六种经典的共轭梯度法分为两类。第一类如FR、CD和DY方法，其共轭参数 ${\beta }_k$ 有共同的分子 ${\Vert g_k\Vert }^2$，虽然它们具有良好的全局收敛性，但数值表现一般；第二类如PRP、HS和LS方法，其共轭参数 ${\beta }_k$ 有共同的分子 $g_k^{\text{T}}\left(g_k-g_{k-1}\right)$，虽然它们拥有良好的数值表现，但对全局收敛的条件要求较强。为得到数值实验和理论结果都较好的共轭梯度法，许多学者对这些经典方法做了修正 [7] [8] [9] [10]。

2007年，Zhang等人在 [11] [12] [13] 的基础上，提出了三阶HS共轭梯度法 [14]，即TTHS方法，搜索方向 $d_k$ 的取法如下：

$d_k=-g_k+{\beta }_k^{HS}{d}_{k-1}+{\theta }_k{y}_{k-1}$, ${\theta }_k=\frac{g_k^{\text{T}}{d}_{k-1}}{d_{k-1}^{\text{T}}{y}_{k-1}}$.

该方法的优点在于：生成的搜索方向 $d_k$ 总满足 $g_k^{\text{T}}{d}_k=-{\Vert g_k\Vert }^2$，即不依赖任何线搜索而具有充分下降性。为了得到TTHS方法在标准Wolf线搜索下的全局收敛性，Zhang等人提出了以下两种算法。一种是截断TTHS方法(CTTHS方法)：

$d_k=\{\begin{array}{l}-g_k,\text{}\text{if}{s}_k^{\text{T}}{y}_k\ge {\epsilon }_1{\Vert g_k\Vert }^r{s}_k^{\text{T}}{s}_k,\\ -g_k+{\beta }_k^{HS}{d}_{k-1}+{\theta }_k{y}_{k-1},\text{if}{s}_k^{\text{T}}{y}_k\ge {\epsilon }_1{\Vert g_k\Vert }^r{s}_k^{\text{T}}{s}_k,\end{array}$

其中 ${\epsilon }_1$ 和 $\gamma$ 是任意正常数。另一种是改进的TTHS方法(MTTHS方法)：

$d_k=\{\begin{array}{l}-g_k\text{if}k=0,\\ -g_k+{\beta }_k^{MHS}{d}_{k-1}-{\theta }_k^M{z}_{k-1}\text{if}k>0,\end{array}$

其中

${\beta }_k^{MHS}=\frac{g_k^{\text{T}}{z}_{k-1}}{d_{k-1}^{\text{T}}{z}_{k-1}}$, ${\theta }_k^M=\frac{g_k^{\text{T}}{d}_{k-1}}{d_{k-1}^{\text{T}}{z}_{k-1}}$, $z_{k-1}=y_{k-1}+t{\Vert g_k\Vert }^{\gamma }{s}_{k-1}$.

t和 $\gamma$ 为任意正常数， $y_{k-1}=g_k-g_{k-1}$, $s_{k-1}=x_k-x_{k-1}$。

为保证MTTHS方法在修改的Armijo线搜索下的全局收敛性，考虑做如下修改：

$d_k=\{\begin{array}{l}-g_k\text{if}k=0,\\ -g_k+{\beta }_k^{MHS}{d}_{k-1}-{\theta }_k^M{z}_{k-1}\text{if}k>0,\end{array}$

其中

${\beta }_k^{MHS}=\frac{g_k^{\text{T}}{z}_{k-1}}{d_{k-1}^{\text{T}}{z}_{k-1}}$, ${\theta }_k^M=\frac{g_k^{\text{T}}{d}_{k-1}}{d_{k-1}^{\text{T}}{z}_{k-1}}$, $z_k=y_k+t_k{s}_k$,

其中

$y_k=g_{k\text{+1}}-g_k$, $s_k=x_{k+1}-x_k$, $r\ge 0$, $t_k=1+\max \left\{\frac{-y_k^{\text{T}}{s}_k}{{\Vert s_k\Vert }^2},0\right\}$.

1990年，Touati-Ahmed和Storey首次引入了杂交共轭梯度法 [15]，其共轭参数 ${\beta }_k$ 的取法为： ${\beta }_k^{TS}=\max \left\{0,\min \left\{{\beta }_k^{FR},{\beta }_k^{PRP}\right\}\right\}$，杂交共轭梯度法的提出，使得共轭梯度法的理论性质和数值试验都表现得更佳。随后，许多学者对杂交共轭梯度法做了进一步研究，见文献 [16] [17]。

在杂交共轭梯度法的启发下，本文考虑杂交三项HS-PRP共轭梯度法：

$d_k=\{\begin{array}{l}-g_k\text{if}k=0,\\ -g_k+{\beta }_k{s}_{k-1}-{\theta }_k{z}_{k-1}\text{if}k>0,\end{array}$

其中

${\beta }_k=\frac{g_k^{\text{T}}{z}_{k-1}}{\max \left\{s_{k-1}^{\text{T}}{z}_{k-1},\mu {\Vert g_{k-1}\Vert }^2\right\}}$, ${\theta }_k=\frac{g_k^{\text{T}}{s}_{k-1}}{\max \left\{s_{k-1}^{\text{T}}{z}_{k-1},\mu {\Vert g_{k-1}\Vert }^2\right\}}$, $z_k=y_k+t_k{s}_k$.

其中

$y_k=g_{k\text{+1}}-g_k$, $s_k=x_{k+1}-x_k$, $t_k=1+\max \left\{\frac{-y_k^{\text{T}}{s}_k}{{\Vert s_k\Vert }^2},0\right\}>0$, $\mu$ 为任意正常数。

我们注意到，上述共轭梯度法旨在求解无约束优化问题，该方法并不适合直接用于求解约束优化问题。2021年，Zhou提出了一种求解凸约束优化问题的投影PRP方法 [18]，利用投影的性质证明了该算法在修改的Armijo线搜索下具有全局收敛性。本文的目的是推广杂交三阶HS-PRP共轭梯度法求解凸约束优化问题，并证明该算法在修改的Armijo线搜索下的全局收敛性。

本文其余部分组织如下：第二部分详细介绍了求解凸约束优化问题的杂交三阶投影HS-PRP共轭梯度法；第三部分证明该算法的全局收敛性；第四部分给出数值实验结果。

2. 杂交三阶投影HS-PRP共轭梯度法

本文的目的是推广求解无约束优化问题的杂交三阶HS-PRP共轭梯度法用于求解以下凸约束优化问题：

$\underset{x\in \Omega }{\min }f\left(x\right)$. (1)

其中 $\Omega \subseteq R^n$ 是闭凸集， $f\left(x\right)$ 为 $R^n\to R$ 的光滑函数。显然，若 $x^{*}$ 是问题(1)的局部极小点，那么 $x^{*}$ 一定是满足定义2.1的稳定点。

定义2.1. $x^{*}\in \Omega$ 是问题(1)的稳定点当且仅当： $g{\left(x^{*}\right)}^{\text{T}}\left(x-x^{*}\right)\ge 0$, $\forall x\in \Omega$。

定义2.2. 从 $R^n$ 到闭凸集 $\Omega$ 的投影算子为：

$P_{\Omega }=\arg \underset{y\in \Omega }{\min }\Vert y-x\Vert$. (2)

令

$r_k=P_{\Omega }\left(x_k-g_k\right)-x_k$. (3)

显然， $x_k$ 是问题(1)的稳定点当且仅当 $r_k=0$。

算法1. (杂交三阶投影HS-PRP方法)

步0. 取初始点 $x_0\in \Omega$, $\delta >0$, $\mu >0$, $\rho \in \left(0,1\right)$, $0<{\lambda }_{\min }<{\lambda }_{\max }<\infty$。选取一个正序列 $\left\{{\eta }_k\right\}$ 满足： ${\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{\eta }_k}\le \eta <\infty$。令

$d_0=-g_0$, $k:=0$. (4)

步1. 若 $r_k=0$, 则停止计算；否则，转步2。

步2. 按如下公式计算 $d_k$

$d_k=\{\begin{array}{l}-g_k\text{if}k=0,\\ -g_k+{\beta }_k{s}_{k-1}-{\theta }_k{z}_{k-1}\text{if}k>0,\end{array}$ (5)

其中

${\beta }_k=\frac{g_k^{\text{T}}{z}_{k-1}}{\max \left\{s_{k-1}^{\text{T}}{z}_{k-1},\mu {\Vert g_{k-1}\Vert }^2\right\}}$, ${\theta }_k=\frac{g_k^{\text{T}}{s}_{k-1}}{\max \left\{s_{k-1}^{\text{T}}{z}_{k-1},\mu {\Vert g_{k-1}\Vert }^2\right\}}$, $z_k=y_k+t_k{s}_k$. (6)

其中

$y_k=g_{k\text{+1}}-g_k$, $s_k=x_{k+1}-x_k$, $t_k=1+\max \left\{\frac{-y_k^{\text{T}}{s}_k}{{\Vert s_k\Vert }^2},0\right\}>0$. (7)

步3. 计算 ${\alpha }_k=\max \left\{{\sigma }_k{\rho }^j,j=0,1,2,\cdots \right\}$ 满足：

$f\left(P_{\Omega }\left(x_k+{\alpha }_k{d}_k\right)\right)\le f\left(x_k\right)-\delta {\Vert {\alpha }_k{d}_k\Vert }^2+{\eta }_k$, (8)

其中 ${\sigma }_k\in \left[{\lambda }_{\min },{\lambda }_{\max }\right]$。

步4. 令 $x_{k+1}:=P_{\Omega }\left(x_k+{\alpha }_k{d}_k\right)$, $k:=k+1$, $s_k=x_{k+1}-x_k=P_{\Omega }\left(x_k+{\alpha }_k{d}_k\right)-x_k$，转步1。

注2.2.

1) 由(3)可知，若 $g_k=0$，则 $r_k=0$，则 $x_k$ 是问题(1)的稳定点；

2) 若 $\max \left\{s_{k-1}^{\text{T}}{z}_{k-1},\mu {\Vert g_{k-1}\Vert }^2\right\}=0$，则 $\Vert g_{k-1}\Vert =0$，这也就意味着 $x_{k-1}$ 是问题(1)的稳定点；

3) 由 $d_k$ 的定义可知：

$d_k^{\text{T}}{g}_k=-\Vert g_k\Vert {}^2$ ； (9)

4) 由投影算子的连续性和 ${\eta }_k>0$ 可知线搜索(8)对任意充分小的 $\alpha >0$ 都成立。线搜索(8)来自文献 [19]。

接下来我们将介绍投影算子的一些重要性质，这些性质对我们后面证明该算法的全局收敛性非常有用。引理2.3和引理2.4来自文献 [20]。

引理2.3. 若 $z\in \Omega$，则有：

${\left(P_{\Omega }\left(x\right)-x\right)}^{\text{T}}\left(z-P_{\Omega }\left(x\right)\right)\ge 0,\forall x\in R^n$, (10)

$\Vert P_{\Omega }\left(x\right)-P_{\Omega }\left(y\right)\Vert \le \Vert x-y\Vert ,\forall x,y\in R^n$, (11)

引理2.4. 对任意 $x\in \Omega$, $\frac{\Vert P_{\Omega }\left(x-\alpha g\left(x\right)\right)-x\Vert }{\alpha }$ 在 $\alpha >0$ 上非增。

引理2.5. 对任意 $x_k\in \Omega$。有：

$g_k^{\text{T}}\left(x_k-P_{\Omega }\left(x_k-\alpha g_k\right)\right)\ge \frac{{\Vert P_{\Omega }\left(x_k-\alpha g_k\right)-x_k\Vert }^2}{\alpha },\forall \alpha >0$, (12)

证明：由(10)和 $x_k\in \Omega$ 可知：

$\begin{array}{l}{g}_k^{\text{T}}\left(x_k-P_{\Omega }\left(x_k-\alpha g_k\right)\right)\\ =\frac{1}{\alpha }{\left(x_k-P_{\Omega }\left(x_k-\alpha g_k\right)+P_{\Omega }\left(x_k-\alpha g_k\right)-\left(x_k-\alpha g_k\right)\right)}^{\text{T}}\left(x_k-P_{\Omega }\left(x_k-\alpha g_k\right)\right)\\ =\frac{{\Vert P_{\Omega }\left(x_k-\alpha g_k\right)-x_k\Vert }^2}{\alpha }+\frac{1}{\alpha }{\left(P_{\Omega }\left(x_k-\alpha g_k\right)-\left(x_k-\alpha g_k\right)\right)}^{\text{T}}\left(x_k-P_{\Omega }\left(x_k-\alpha g_k\right)\right)\\ \ge \frac{{\Vert P_{\Omega }\left(x_k-\alpha g_k\right)-x_k\Vert }^2}{\alpha }\end{array}$

证毕。

3. 全局收敛性

在这一部分，我们将讨论算法1在以下假设条件下的全局收敛性。首先，我们定义水平集：

${\Omega }_1=\left\{x|f\left(x\right)\le f\left(x_0\right)+\eta \right\}\cap \Omega$, (13)

其中 $\eta$ 满足(4)。显然 $x_k\in {\Omega }_1$ 对任意 $k\ge 0$ 都成立。

假设A.

1) 由(13)定义的水平集 ${\Omega }_1$ 是有界的；

2) 存在 ${\Omega }_1$ 的某些凸邻域N，使得梯度函数 $g\left(x\right)$ 在 $N\cap \Omega$ 上Lipschitz连续，即存在常数 $L>0$，使得：

$\Vert g\left(x\right)-g\left(y\right)\Vert \le L\Vert x-y\Vert ,\forall x,y\in N\cap \Omega$ (14)

由假设A可知存在常数 $M>0$，使得：

$g\left(x\right)\le M,\forall x\in N\cap \Omega$ (15)

显然，由线搜索(8)和(4)我们可以得到：

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

引理3.1. 设 $\left\{x_k\right\}$ 是由算法1产生的序列且假设A成立，则对任意的 $k\ge 0$，有：

$\Vert z_k\Vert \le \Vert y_k\Vert +t_k\Vert s_k\Vert \le \left(L+t_k\right)\Vert s_k\Vert$. (17)

$\begin{array}{c}{s}_k^{\text{T}}{z}_k=s_k^{\text{T}}{y}_k+t_k{\Vert s_k\Vert }^2\\ =\{\begin{array}{l}{s}_k^{\text{T}}{y}_k+{\Vert s_k\Vert }^2\ge {\Vert s_k\Vert }^2,s_k^{\text{T}}{y}_k\ge 0\\ s_k^{\text{T}}{y}_k+{\Vert s_k\Vert }^2-s_k^{\text{T}}{y}_k={\Vert s_k\Vert }^2,s_k^{\text{T}}{y}_k<0\end{array}\end{array}$. (18)

由(18)可知： $s_k^{\text{T}}{z}_k\ge {\Vert s_k\Vert }^2$。

引理3.2. 若假设A成立，则存在常数 $C>0$ 使得：

$\Vert d_k\Vert \le C,\forall k\ge 0$. (19)

证明：由(5)、(6)、(15)、(17)、(18)可知：

$\begin{array}{c}\Vert d_k\Vert \le \Vert g_k\Vert +\frac{2\Vert g_k\Vert \Vert z_{k-1}\Vert }{\max \left\{s_{k-1}^{\text{T}}{z}_{k-1},\mu {\Vert g_{k-1}\Vert }^2\right\}}\Vert s_{k-1}\Vert \\ \le \Vert g_k\Vert +\frac{2\Vert g_k\Vert \Vert z_{k-1}\Vert }{s_{k-1}^{\text{T}}{z}_{k-1}}\Vert s_{k-1}\Vert \\ \le M+\frac{2M\left(L+t_{k-1}\right)\Vert s_{k-1}\Vert }{{\Vert s_{k-1}\Vert }^2}\Vert s_{k-1}\Vert \\ =M+2M\left(L+t_{k-1}\right)\end{array}$

令 $C=M+2M\left(L+t_{k-1}\right)$ 即得(19)，证毕。

定理3.3. 设 $\left\{x_k\right\}$ 是由算法1产生的序列且假设A成立，则有：

$\underset{k\to \infty }{\lim \inf }\Vert r_k\Vert =0$. (20)

证明：反证法，假设结论不成立，则存在常数 $\tau >0$ 使得：

$\Vert r_k\Vert \ge \tau ,\forall k\ge 0$. (21)

由(21)可知存在常数 $\epsilon >0$，使得：

$\Vert g_k\Vert \ge \epsilon ,\forall k\ge 0$. (22)

否则存在无限子集 $K\subseteq \left\{0,1,2,\cdots \right\}$ 使得：

$\underset{k\in K,k\to \infty }{\lim }\Vert r_k\Vert =\underset{k\in K,k\to \infty }{\lim }\Vert P_{\Omega }\left(x_k-g_k\right)-x_k\Vert \le \underset{k\in K,k\to \infty }{\lim }\Vert g_k\Vert =0$. (23)

最后一个不等式由(11)和 $P_{\Omega }\left(x_k\right)=x_k$ 可得，因此上式与(21)矛盾，即(22)成立。

1) 若 $\underset{k\to \infty }{\lim \sup }{\alpha }_k>0$，由(9)和(16)可得： $\underset{k\to \infty }{\lim \inf }\Vert g_k\Vert =0$。这与(22)式矛盾。

2) 若 $\underset{k\to \infty }{\lim \sup }{\alpha }_k=0$，则存在 ${{\alpha }^{\prime }}_k=\frac{{\alpha }_k}{\rho }$ 不满足不等式(8)，即：

$f\left(P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)\right)-f\left(x_k\right)>-\delta {\Vert {{\alpha }^{\prime }}_k{d}_k\Vert }^2+{\eta }_k>-\delta {\Vert {{\alpha }^{\prime }}_k{d}_k\Vert }^2$. (24)

由拉格朗日中值定理和引理2.5可得：

$\begin{array}{l}\frac{f\left(P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)\right)-f\left(x_k\right)}{{{\alpha }^{\prime }}_k}\\ =\frac{g{\left({\xi }_k\right)}^{\text{T}}\left(P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)-x_k\right)}{{{\alpha }^{\prime }}_k}\\ =\frac{g_k^{\text{T}}\left(P_{\Omega }\left(x_k-{{\alpha }^{\prime }}_k{g}_k\right)-x_k\right)}{{{\alpha }^{\prime }}_k}+\frac{{\left(g\left({\xi }_k\right)-g_k\right)}^{\text{T}}\left(P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)-x_k\right)}{{{\alpha }^{\prime }}_k}\\ +\frac{g_k^{\text{T}}\left(P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)-P_{\Omega }\left(x_k-{{\alpha }^{\prime }}_k{g}_k\right)\right)}{{{\alpha }^{\prime }}_k}\\ =\frac{g_k^{\text{T}}\left(P_{\Omega }\left(x_k-{{\alpha }^{\prime }}_k{g}_k\right)-x_k\right)}{{{\alpha }^{\prime }}_k}+{\Delta }_k\\ \le -\frac{{\Vert P_{\Omega }\left(x_k-{{\alpha }^{\prime }}_k{g}_k\right)-x_k\Vert }^2}{{{\alpha }^{\prime }}_k^2}+{\Delta }_k,\end{array}$

其中 ${\xi }_k$ 介于 $x_k$ 和 $P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)$ 之间。上述不等式结合(24)可得：

$\frac{{\Vert P_{\Omega }\left(x_k-{{\alpha }^{\prime }}_k{g}_k\right)-x_k\Vert }^2}{{{\alpha }^{\prime }}_k^2}\le \left|{\Delta }_k\right|+\delta {{\alpha }^{\prime }}_k{\Vert d_k\Vert }^2$. (25)

由(11)和(15)可得：

$\begin{array}{c}\left|{\Delta }_k\right|\le \Vert g\left({\xi }_k\right)-g_k\Vert \Vert \frac{P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)-x_k}{{{\alpha }^{\prime }}_k}\Vert +\Vert g_k\Vert \Vert \frac{P_{\Omega }\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)-P_{\Omega }\left(x_k-{{\alpha }^{\prime }}_k{g}_k\right)}{{{\alpha }^{\prime }}_k}\Vert \\ \le \Vert g\left({\xi }_k\right)-g_k\Vert \Vert d_k\Vert +M\Vert d_k+g_k\Vert \\ \le C\Vert g\left({\xi }_k\right)-g_k\Vert +M\Vert d_k+g_k\Vert ,\end{array}$

由(5)、(6)、(11)、(15)、(17)、(22)以及 ${\alpha }_k\to 0$ 可得：

$\begin{array}{c}\underset{k\to \infty }{\lim }\Vert d_k+g_k\Vert \le \underset{k\to \infty }{\lim }\frac{2\Vert g_k\Vert \Vert z_{k-1}\Vert }{\max \left\{s_{k-1}^T{z}_{k-1},\mu {\Vert g_{k-1}\Vert }^2\right\}}\Vert s_{k-1}\Vert \\ \le \underset{k\to \infty }{\lim }\frac{2M\left(L+t_{k-1}\right)\Vert s_{k-1}\Vert }{\mu {\Vert g_{k-1}\Vert }^2}\Vert s_{k-1}\Vert \\ \le \underset{k\to \infty }{\lim }\frac{2M\left(L+t_{k-1}\right){\Vert {\alpha }_{k-1}{d}_{k-1}\Vert }^2}{\mu {\epsilon }^2}\\ =0\end{array}$ (26)

因此，由 $g\left(x\right)$ 的连续性和 ${{\alpha }^{\prime }}_k\to 0$ 以及(26)可知： ${\Delta }_k\to 0$。

由(3)、(19)、(25)，引理2.4以及 ${{\alpha }^{\prime }}_k\to 0$，我们可以得到：

${\Vert r_k\Vert }^2={\Vert P_{\Omega }\left(x_k-g_k\right)-x_k\Vert }^2\le \frac{{\Vert P_{\Omega }\left(x_k-{{\alpha }^{\prime }}_k{g}_k\right)-x_k\Vert }^2}{{{\alpha }^{\prime }}_k^2}\le \left|{\Delta }_k\right|+\delta {{\alpha }^{\prime }}_k{\Vert d_k\Vert }^2\to 0$.

这与(21)矛盾，证毕。

4. 数值实验

在这一部分我们将通过数值实验来验证本文所提出算法的有效性。实验测试在PC机上完成，PC机配置：联想，Intel(R) Core(TM) i7-8700 CPU @ 3.20GHz 3.19GHz，8Gb内存，Windows10操作系统，所有代码用Matlab R2016b编写并运行。

测试对象：函数来自文献 [18]，表达式如下：

$f\left(x\right)=\frac{1}{2}{\displaystyle \underset{i=1}{\overset{n-1}{\sum }}{\left(x_i-x_{i-1}\right)}^2}+\frac{1}{12}{\displaystyle \underset{i=1}{\overset{n-1}{\sum }}{\gamma }_i{\left(x_i-x_{i-1}\right)}^4}+\frac{1}{2}{x}^{\text{T}}x$.

约束集 $\Omega =\left\{x|-10\le x_i\le 10,i=1,2,\cdots ,n\right\}$，其中 ${\gamma }_i\ge 0\left(i=1,2,\cdots ,n-1\right)$ 为任意常数。

令 $\gamma ={\left[{\gamma }_1,{\gamma }_2,\cdots ,{\gamma }_{n-1}\right]}^{\text{T}}$。

测试参数： $\delta =0.1$, $\rho =0.1$, $\mu =1$, ${\lambda }_{\max }={\lambda }_{\min }=1$, ${\eta }_k={0.5}^k$。

初始点： $x_0={\left(-1.2,1,-1.2,1\cdots ,-1.2,1\right)}^{\text{T}}$。

终止条件：迭代次数 $k\ge 500$ 或 ${\Vert r_k\Vert }_{\infty }\le {10}^{-5}$，其中 ${\Vert r_k\Vert }_{\infty }$ 表示迭代终止时 $r_k$ 的无穷范数。

采用本文提出的算法与Zhou在文献 [18] 中提出的投影PRP算法求解上述测试问题，分别记为算法1和算法2，测试结果见表1和表2。

Table 1. Test function with γ = ( 1 , 2 , ⋯ , n − 1 ) T

表1. 测试函数中 $\gamma ={\left(1,2,\cdots ,n-1\right)}^{\text{T}}$

Table 2. Test function with γ = 1 n ( 1 2 , 2 2 , ⋯ , ( n − 1 ) 2 ) T

表2. 测试函数中 $\gamma =\frac{1}{n}{\left(1^2,2^2,\cdots ,{\left(n-1\right)}^2\right)}^{\text{T}}$

由表1和表2的数据我们可以知道，在迭代次数和运行时间两个方面，本文提出的算法优于 [18] 提出的投影PRP方法。

5. 结束语

本文提出了一种求解凸约束优化问题的杂交三阶投影HS-PRP共轭梯度法，它是求解无约束优化问题的共轭梯度法的推广。利用投影的相关性质，我们证明了该算法在修改的Armijo线搜索下的全局收敛性。数值结果表明，本文所提出的算法较投影PRP算法更优。

参考文献