¹枣庄学院，数学与统计学院，山东 枣庄

²山东煤炭卫生学校，山东 枣庄

收稿日期：2022年6月30日；录用日期：2022年7月11日；发布日期：2022年7月21日

摘要

共轭梯度法是数值计算领域的一类重要方法。本文基于Schmidt正交化方法，提出了两种改进的Hestenes-Stiefel共轭梯度法。无需线搜索条件，它们自动满足共轭梯度法的两个重要性质，即充分下降性和共轭条件。在适当的条件下，本文证明了所设计算法的全局收敛性。最后，将这两种算法应用到脉冲噪声去噪中，初步的数值试验表明了算法的有效性。

关键词

共轭梯度，收敛性，脉冲噪声去噪

Impulse Noise Denoising Algorithm Based on Conjugate Gradient

Min Sun¹, Maoying Tian²

¹School of Mathematics and Statistics, Zaozhuang University, Zaozhuang Shandong

²Shandong Coal Medical School, Zaozhuang Shandong

Received: Jun. 30^th, 2022; accepted: Jul. 11^th, 2022; published: Jul. 21^st, 2022

ABSTRACT

Conjugate gradient method is an important method in numerical computation. Based on Schmidt orthogonalization, two improved Hestenes-Stiefel conjugate gradient methods are proposed in this paper. Without line search conditions, they automatically satisfy two important properties of the conjugate gradient method, namely, sufficient descent and conjugate conditions. Under appropriate conditions, the global convergence of the proposed algorithm is proved. Finally, the two algorithms are applied to impulse noise denoising, and preliminary numerical experiments show the effectiveness of the algorithm.

Keywords:Conjugate Gradient, Convergence, Impulse Noise Denoising

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

考虑无约束最优化问题(记为UCP)：

$\underset{x\in R^n}{\min }f\left(x\right)$ (1)

其中 $f:R^n\to R$ 是一个光滑函数，且有下界。UCP是最优化领域中最重要和最基本的问题之一，学者们对其进行了系统而深入的研究。有许多经典的迭代方法来求解UCP，包括最速下降法、共轭梯度法、信赖域法、牛顿法、拟牛顿法等 [1] [2]。尽管信赖域方法、牛顿方法和拟牛顿方法具有很好的收敛性，但它们不适合大规模的UCP，因为它们需要计算Hessian矩阵 ${\nabla }^{2}f\left(x_k\right)$ 或其近似值，从而导致大量的计算和存储。最速下降法和共轭梯度法在迭代方案中只包括梯度 $\nabla f\left(x_k\right)$，因此，它们适用于求解大规模的UCP。

共轭梯度法的基本思想可以追溯到Hestenes和Stiefel求解线性方程组的研究成果。后来，Fletcher和Reeves将其推广到解决非线性优化问题。共轭梯度法自出现以来，一直受到学者们的密切关注。从初始迭代 $x_0$ 开始，共轭梯度法的迭代格式为

$x_{k+1}=x_k+{\alpha }_k{d}_k,k=0,1,\cdots$ (2)

其中 ${\alpha }_k$ 是由某些线搜索计算的步长， $d_k$ 是生成的搜索方向，其定义下式

$d_k=\{\begin{array}{l}-g_k\text{if}k=0,\hfill \\ -g_k+{\beta }_k{d}_{k-1},\text{if}k\ge 1,\hfill \end{array}$ (3)

其中， $g_k=\nabla f\left(x_k\right)$ 和 ${\beta }_k$ 是共轭参数，这是不同共轭梯度方法之间的根本区别。比较著名的共轭参数包括：Hestenes-Stiefiel (HS)，Polak-Ribiere-Polyak (PRP)，Fletcher-Reeves (FR)，与Dai-Yuan (DY)。具体定义如下 [3]：

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

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

如果UCP中的 $f\left(x\right)$ 是一个强二次函数，并且(2)中的步长 ${\alpha }_k$ 是通过精确的线搜索生成的，则上述四个 ${\beta }_k$ 公式是等价的，否则可以得到四个著名的共轭梯度方法，即HS方法、PRP方法、FR方法和DY方法。这四个方法具有不同的收敛结果和数值性能。FR方法和DY方法分别在强Wolfe线搜索和Wolfe线搜索下具有全局收敛性。对于HS方法和PRP方法，它们通常被认为是实际应用中最有效的两种共轭梯度法，但即使步长 ${\alpha }_k$ 是精确步长，它们也可能发散。

大量数值试验表明，高效的共轭梯度法产生的搜索方向满足两个性质：充分下降条件和共轭条件，也就是

$g_k^{\top }{d}_k\le -c{\Vert g_k\Vert }^2,c>0$ (4)

与

$y_{k-1}^{\top }{d}_k=0$ (5)

其中 $y_{k-1}=g_k-g_{k-1}$。近几年学者们设计了多种满足(4)或(5)的共轭梯度法。比如，Hager与Zhang [4] 将(3)中的参数 ${\beta }_k$ 取为

${\beta }_k^{\text{HZ}}=\frac{1}{\langle d_{k-1},y_{k-1}\rangle }\langle y_{k-1}-2d_{k-1}\frac{{\Vert y_{k-1}\Vert }^2}{\langle d_{k-1},y_{k-1}\rangle },g_k\rangle .$

如果 $\langle d_{k-1},y_{k-1}\rangle \ne 0$，则有

$g_k^{\top }{d}_k\le -\frac{7}{8}{\Vert g_k\Vert }^2.$

文献 [5] [6] 提出了两种修正的PRP共轭梯度法，其方向取为

$d_k^{\text{ZTPRP}}=-g_k+{\beta }_k^{\text{PRP}}{d}_{k-1}-{\theta }_k{y}_{k-1},$

$d_k^{\text{CTPRP}}=-\left(1+{\beta }_k^{\text{PRP}}\frac{g_k^{\top }{d}_{k-1}}{{\Vert g_k\Vert }^2}\right)g_k+{\beta }_k^{\text{PRP}}{d}_{k-1},$

其中 ${\theta }_k=\frac{g_k^{\top }{d}_{k-1}}{{\Vert g_{k-1}\Vert }^2}$。容易验证上面两类方向都满足 $g_k^{\top }{d}_k=-{\Vert g_k\Vert }^2$，并且容易看出 $d_k^{\text{CTPRP}}$ 的设计动机来自于Schmidt正交化方法。基于这个设计思想， [7] 提出了一类满足夹角性质的记忆梯度法，其产生的方向同时满足(4)与夹角条件 $\cos \langle -g_k,d_k\rangle \ge 1/3$。

本文继续对这一方向进行研究，提出了两种同时满足充分下降性和共轭条件的改进HS共轭梯度法。本文的其余部分组织如下：第2节提出了HS方法的两种变体，并证明了生成序列的一些重要性质。第3节证明了它们的全局收敛性。在第4节中，我们给出了一些图像去噪的试验结果。第5节给出一些未来的研究方向。

2. 两类改进的HS方法

在这一节中，我们设计两种改进的HS方法的迭代格式。在无需线搜索的条件下，它们产生的方向满足充分下降条件和共轭条件。

正如在第1节中所分析，由下式产生的方向 $d_k$ 满足充分下降条件：

$d_k=-\left(1+{\beta }_k\frac{g_k^{\top }{d}_{k-1}}{{\Vert g_k\Vert }^2}\right)g_k+{\beta }_k{d}_{k-1}$ (6)

因此，为了确保 $d_k$ 满足共轭条件，我们只需将其代入(5)式，并求解得到的线性方程。也就是

$y_{k-1}^{\top }\left(\left(1+{\beta }_k\frac{g_k^{\top }{d}_{k-1}}{{\Vert g_k\Vert }^2}\right)g_k-{\beta }_k{d}_{k-1}\right)=0$

由此得

${\beta }_k^{\text{HS1}}=\frac{{\Vert g_k\Vert }^2{g}_k^{\top }{y}_{k-1}}{{\Vert g_k\Vert }^2{y}_{k-1}^{\top }{d}_{k-1}^{\text{HS1}}-\left(g_k^{\top }{d}_{k-1}^{\text{HS1}}\right)\left(g_k^{\top }{y}_{k-1}\right)}$ (7)

其中 $d_{k-1}$ 替换成了 $d_{k-1}^{\text{HS1}}$。然后，将(7)代入(6)，得到以下迭代方向：

$d_k^{\text{HS1}}=-\left(1+{\beta }_k^{\text{HS1}}\frac{g_k^{\top }{d}_{k-1}}{{\Vert g_k\Vert }^2}\right)g_k+{\beta }_k^{\text{HS1}}{d}_{k-1}^{\text{HS1}}.$ (8)

引理2.1由(8)定义的方向 $d_k^{\text{HS1}}$ 满足充分下降条件和共轭条件。此外，如果步长 ${\alpha }_{k-1}$ 是通过精确的线搜索计算的，并且 $d_{k-1}^{\text{HS1}}=d_{k-1}^{\text{HS}}$，那么 $d_k^{\text{HS1}}=d_k^{\text{HS}}$，其中 $d_k^{\text{HS}}$ 是HS方法的方向，即

$d_k^{\text{HS}}=-g_k+{\beta }_k^{\text{HS}}{d}_{k-1}^{\text{HS}}.$

证明 从 $d_k^{\text{HS1}}$ 的公式可得

$g_k^{\top }{d}_k^{\text{HS1}}=-{\Vert g_k\Vert }^2,y_{k-1}^{\top }{d}_k^{\text{HS1}}=0.$ (9)

因此，方向 $d_k^{\text{HS1}}$ 满足充分下降条件和共轭条件。

由于 ${\alpha }_{k-1}$ 是通过精确的行搜索计算的，因此我们有 $g_k^{\top }{d}_{k-1}^{\text{HS1}}=0$。这与(7)、(8)表明如果 $d_{k-1}^{\text{HS1}}=d_{k-1}^{\text{HS}}$，则 ${\beta }_k^{\text{HS1}}={\beta }_k^{\text{HS}}$ 及 $d_k^{\text{HS1}}=d_k^{\text{HS}}$。证毕。

参数 ${\beta }_k^{\text{HS1}}$ 由以下两个步骤生成：首先通过Schmidt正交化使 $d_k$ 满足充分下降条件，然后通过求解相应的线性方程调整得到的 $d_k$ 满足共轭条件。显然，上述两个步骤可以交换顺序。也就是说，可以先通过施密特正交化使 $d_k$ 满足共轭条件，然后调整得到的 $d_k$ 以满足充分下降条件。具体地，为了使(3)定义的 $d_k$ 满足共轭条件，通过Schmidt正交化得

$d_k=-g_k+{\beta }_k{d}_{k-1}-\frac{-g_k^{\top }{y}_{k-1}+{\beta }_k{d}_{k-1}^{\top }{y}_{k-1}}{{\Vert y_{k-1}\Vert }^2}{y}_{k-1}.$

然后将上述等式代入等式 $g_k^{\top }{d}_k=-{\Vert g_k\Vert }^2$，得

${\beta }_k^{\text{HS2}}=\frac{{\left(g_k^{\top }{y}_{k-1}\right)}^2}{\left(g_k^{\top }{y}_{k-1}\right)\left(y_{k-1}^{\top }{d}_{k-1}^{\text{HS2}}\right)-{\Vert y_{k-1}\Vert }^2{g}_k^{\top }{d}_{k-1}^{\text{HS2}}}$ (10)

其中 $d_{k-1}$ 替换成了 $d_{k-1}^{\text{HS2}}$。于是，得到了一个新的方向

$d_k^{\text{HS2}}=-g_k+{\beta }_k^{\text{HS2}}{d}_{k-1}^{\text{HS2}}-\frac{-g_k^{\top }{y}_{k-1}+{\beta }_k^{\text{HS2}}{\left(d_{k-1}^{\text{HS2}}\right)}^{\top }{y}_{k-1}}{{\Vert y_{k-1}\Vert }^2}{y}_{k-1}.$ (11)

引理2.2由(11)定义的方向 $d_k^{\text{HS2}}$ 满足充分下降条件和共轭条件。此外，如果步长 ${\alpha }_{k-1}$ 是通过精确的线搜索计算的，并且 $d_{k-1}^{\text{HS2}}=d_{k-1}^{\text{HS}}$，那么 $d_k^{\text{HS2}}=d_k^{\text{HS}}$。

证明 从 $d_k^{\text{HS2}}$ 的公式可得

$g_k^{\top }{d}_k^{\text{HS2}}=-{\Vert g_k\Vert }^2,y_{k-1}^{\top }{d}_k^{\text{HS2}}=0.$ (12)

因此，方向 $d_k^{\text{HS2}}$ 满足充分下降条件和共轭条件。

由于 ${\alpha }_{k-1}$ 是通过精确的行搜索计算的，因此我们有 $g_k^{\top }{d}_{k-1}^{\text{HS2}}=0$。这与(9)、(10)表明如果 $d_{k-1}^{\text{HS2}}=d_{k-1}^{\text{HS}}$，则 ${\beta }_k^{\text{HS2}}={\beta }_k^{\text{HS}}$ 及 $d_k^{\text{HS2}}=d_k^{\text{HS}}$。证毕。

在下文中，对问题(1)做出以下限制。假设：

(H1) 水平集 $\Omega =\left\{x\in R^n|f\left(x\right)\le f\left(x_0\right)\right\}$ 有界；

(H2) 在 $\Omega$ 的某个邻域中，梯度 $g\left(x\right)$ 是Lipschitz连续的，即存在一个常数 $L>0$，使得

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

(H3) 函数 $f\left(x\right)$ 在 $\Omega$ 上一致凸，即存在一个常数 $\mu >0$，使得

${\left(g\left(x\right)-g\left(y\right)\right)}^{\top }\left(x-y\right)\ge \mu {\Vert x-y\Vert }^2,\forall x,y\in \Omega .$ (13)

假设(H1)与(H2)表明存在正常数 $\gamma$ 与B使得

$\Vert g\left(x\right)\Vert \le \gamma ,\forall x\in \Omega ,$ (14)

$\Vert x-y\Vert \le B,\forall x,y\in \Omega .$ (15)

在共轭梯度法中，步长 ${\alpha }_k$ 通常由非精确线性搜索确定，比如 Armijo线搜索、Wolfe线搜索、Goldstein线搜索等。本文采用Armijo线搜搜，即步长 ${\alpha }_k$ 是集合 $\left\{1,\rho ,{\rho }^2,\cdots \right\}$ 中满足下面不等式的最大的 $\alpha$ ：

$f\left(x_k+\alpha d_k\right)\le f\left(x_k\right)-\sigma {\alpha }^2{\Vert d_k\Vert }^2,$ (16)

其中 $\rho \in \left(0,1\right)$，$\sigma >0$。

由(13)得

$d_{k-1}^{\top }{y}_{k-1}=d_{k-1}^{\top }\left(g_k-g_{k-1}\right)\ge {\alpha }_{k-1}{\Vert d_{k-1}\Vert }^2\ge 0.$ (17)

如果 $\Vert y_{k-1}\Vert =0$，则由充分下降性及(17)得 $\Vert g_{k-1}\Vert =0$，这说明 $x_{k-1}$ 是问题(1)的一个稳定点。

基于上面的分析，下面给出求解问题(1)的两项HS共轭梯度法。

TTMHSCG1方法(两项修正HS共轭方法1)

步0. 选取正常数 $\nu$，$\rho$，$\sigma$ 满足 $0<\rho <\sigma <1$。选取初始迭代点 $x_0\in R^n$，计算 $g_0$。令 $d_0^{\text{HS1}}=-g_0$，$k:=0$。

步1. 如果 $\Vert g_k\Vert =0$，停止否则转步2。

步2. 由Armijo线搜索(16)确定步长 ${\alpha }_k$。

步3. 令 $x_{k+1}=x_k+{\alpha }_k{d}_k$，计算 $g_{k+1}$。

步4. 如果 $g_{k+1}^{\top }{y}_k$ 与 $g_{k+1}^{\top }{d}_k^{\text{HS1}}$ 的符号相同且

$\left|{\Vert g_{k+1}\Vert }^2{y}_k^{\top }{d}_k^{\text{HS1}}-\left(g_{k+1}^{\top }{d}_k^{\text{HS1}}\right)\left(g_{k+1}^{\top }{y}_k\right)\right|<\nu \Vert d_k^{\text{HS1}}\Vert$

则令 $d_{k+1}^{\text{HS1}}=-g_{k+1}$ ；否则 $d_{k+1}^{\text{HS1}}$ 由(8)式确定。

步5. 令 $k=k+1$，返回步1。

类似地，基于 $d_k^{\text{HS2}}$ 可得另一类HS共轭梯度法。

TTMHSCG2方法(两项修正HS共轭方法2)

步0~步3. 与TTMHSCG1方法一样。

步4. 如果 $g_{k+1}^{\top }{y}_k$ 与 $g_{k+1}^{\top }{d}_k^{\text{HS2}}$ 的符号相同且

$\left|\left(g_{k+1}^{\top }{y}_k\right)\left(y_k^{\top }{d}_k^{\text{HS2}}\right)-{\Vert y_k\Vert }^2{g}_{k+1}^{\top }{d}_k^{\text{HS2}}\right|<\nu \Vert d_k^{\text{HS2}}\Vert$

则令 $d_{k+1}^{\text{HS2}}=-g_{k+1}$ ；否则 $d_{k+1}^{\text{HS2}}$ 由(11)式确定。

步5. 令 $k=k+1$，返回步1。

3. 全局收敛性

本文讨论TTMHSCG1与TTMHSCG2的全局收敛性。下面的引理给出了Armijo线搜索所生成的步长序列 $\left\{{\alpha }_k\right\}$ 存在一个正下界。

引理3.1 如果函数 $f(\cdot )$ 满足假设(H1)与(H2)，步长 ${\alpha }_k$ 由Armijo线搜索确定，则

${\alpha }_k\ge \min \left\{1,\frac{\rho {\Vert g_k\Vert }^2}{\left(L+\sigma \right){\Vert d_k\Vert }^2}\right\}.$ (18)

证明 如果 ${\alpha }_k\ne 1$，这说明 ${{\alpha }^{\prime }}_k={\alpha }_k/\rho$ 不满足(16)，即

$f\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)>f\left(x_k\right)-\sigma {\left({{\alpha }^{\prime }}_k\right)}^2{\Vert d_k\Vert }^2.$ (19)

由中值定理及(H2)得，存在常数 ${\theta }_k\in \left(0,1\right)$ 使得

$\begin{array}{l}f\left(x_k+{{\alpha }^{\prime }}_k{d}_k\right)-f\left(x_k\right)\\ ={{\alpha }^{\prime }}_{k}g{\left(x_k+{\theta }_k{{\alpha }^{\prime }}_k{d}_k\right)}^{\top }{d}_k\\ ={{\alpha }^{\prime }}_k{g}_k^{\top }{d}_k+{\left(g\left(x_k+{\theta }_k{{\alpha }^{\prime }}_k{d}_k\right)-g_k\right)}^{\top }{d}_k\\ \le -{{\alpha }^{\prime }}_k{\Vert g_k\Vert }^2+{\left({{\alpha }^{\prime }}_k\right)}^{2}L{\Vert d_k\Vert }^2,\end{array}$

由此式及(19)容易得到(18)成立。证毕。

定理3.1 假设(H1)~(H3)成立，令 $\left\{x_k\right\}$ 是算法TTMHSCG1与TTMHSCG2生成的点列，则

$\underset{k\to \infty }{\lim }\Vert g_k\Vert =0.$

证明 我们只证明了TTMHSCG1的全局收敛性。TTMHSCG2的证明与其类似。事实上，由(H2)可得 $\Vert y_{k-1}\Vert \le L\Vert x_k-x_{k-1}\Vert$ ；由(H3)可得 $y_{k-1}^{\top }{d}_{k-1}^{\text{HS1}}\ge \mu {\alpha }_{k-1}{\Vert d_{k-1}^{\text{HS1}}\Vert }^2>0$。

以下证据分为三种情况。第一种情况，当 $g_k^{\top }{y}_{k-1}$ 与 $g_k^{\top }{d}_{k-1}^{\text{HS1}}$ 有不同的符号时，有

$\begin{array}{c}\left|{\beta }_k^{\text{HS1}}\right|=\frac{{\Vert g_k\Vert }^2\left|g_k^{\top }{y}_{k-1}\right|}{{\Vert g_k\Vert }^2{y}_{k-1}^{\top }{d}_{k-1}^{\text{HS1}}+\left|\left(g_k^{\top }{d}_{k-1}^{\text{HS1}}\right)\left(g_k^{\top }{y}_{k-1}\right)\right|}\\ \le \frac{\left|g_k^{\top }{y}_{k-1}\right|}{y_{k-1}^{\top }{d}_{k-1}^{\text{HS1}}}\le \frac{L\Vert g_k\Vert \Vert x_k-x_{k-1}\Vert }{\mu {\alpha }_{k-1}{\Vert d_{k-1}^{\text{HS1}}\Vert }^2}=\frac{L\Vert g_k\Vert }{\mu \Vert d_{k-1}^{\text{HS1}}\Vert },\end{array}$

由此可得

$\Vert d_k^{\text{HS1}}\Vert \le \Vert g_k\Vert +2\left|{\beta }_k^{\text{HS1}}\right|\Vert d_{k-1}^{\text{HS1}}\Vert \le \left(1+\frac{2L}{\mu }\right)\Vert g_k\Vert .$ (20)

第二种情况，当 $\left|{\Vert g_k\Vert }^2{y}_{k-1}^{\top }{d}_{k-1}^{\text{HS1}}-\left(g_k^{\top }{d}_{k-1}^{\text{HS1}}\right)\left(g_k^{\top }{y}_{k-1}\right)\right|\ge \nu \Vert d_{k-1}\Vert$，并且 $g_k^{\top }{y}_{k-1}$ 与 $g_k^{\top }{d}_{k-1}^{\text{HS1}}$ 符号相同时，有

$\left|{\beta }_k^{\text{HS1}}\right|=\frac{{\Vert g_k\Vert }^2\left|g_k^{\top }{y}_{k-1}\right|}{\left|{\Vert g_k\Vert }^2{y}_{k-1}^{\top }{d}_{k-1}^{\text{HS1}}-\left(g_k^{\top }{d}_{k-1}^{\text{HS1}}\right)\left(g_k^{\top }{y}_{k-1}\right)\right|}\le \frac{{\Vert g_k\Vert }^2\left|g_k^{\top }{y}_{k-1}\right|}{\nu \Vert d_{k-1}^{\text{HS1}}\Vert }\le \frac{LD{\gamma }^2\Vert g_k\Vert }{\Vert d_{k-1}^{\text{HS1}}\Vert },$

其中不等式是根据(14)、(15)得到的。于是

$\Vert d_k^{\text{HS1}}\Vert \le \Vert g_k\Vert +2\left|{\beta }_k^{\text{HS1}}\right|\Vert d_{k-1}^{\text{HS1}}\Vert \le \left(1+2LD{\gamma }^2\right)\Vert g_k\Vert .$ (21)

第三种情况，当 $\left|{\Vert g_k\Vert }^2{y}_{k-1}^{\top }{d}_{k-1}^{\text{HS1}}-\left(g_k^{\top }{d}_{k-1}^{\text{HS1}}\right)\left(g_k^{\top }{y}_{k-1}\right)\right|<\nu \Vert d_{k-1}\Vert$，并且 $g_k^{\top }{y}_{k-1}$ 与 $g_k^{\top }{d}_{k-1}^{\text{HS1}}$ 符号相同时，由TTMHSCG1的第4步得

$\Vert d_k^{\text{HS1}}\Vert =\Vert g_k\Vert .$ (22)

因此，从(20)~(22)，可得

$\Vert d_k\Vert \le \tau \Vert g_k\Vert \le \tau \gamma ,$ (23)

其中 $\tau =1+2L\max \left\{1/\mu ,D{\gamma }^2\right\}$。

另一方面，从Armijo线搜索(17)，我们有

$\underset{k\to \infty }{\lim }{\alpha }_k\Vert d_k\Vert =0.$

由这个式子与充分下降条件可得

$\underset{k\to \infty }{\lim }{\alpha }_k\Vert g_k\Vert \le \underset{k\to \infty }{\lim }{\alpha }_k\Vert d_k\Vert =0.$ (24)

下面利用反证法证明结论。假设 $\underset{k\to \infty }{\lim }\Vert g_k\Vert =0$ 不成立，于是存在常数 $ϵ>0$ 与无穷点列K使得

$\Vert g_k\Vert \ge ϵ,\forall k\in K.$

由此式及(18) (23) (24)得

$\underset{k\to \infty ,k\in K}{\lim }{\alpha }_k=0,$

以及

${\alpha }_k\ge \min \left\{1,\frac{\rho {ϵ}_1^2}{\left(L+\sigma \right){\tau }^2{\gamma }^2}\right\},\forall k\in K.$

显然上面两个式子是矛盾的，因此假设不成立。证毕。

4. 数值实验

本节利用TTMHSCG1与TTMHSCG2求解 [8] 中提出的图像处理的两阶段法。令 $X={\left[x_{i,j}\right]}_{M\times N}$ 表示一个有 $M\times N$ 个像素的图像，对于每个 $\left(i,j\right)\in A:=\left\{1,2,\cdots ,M\right\}\times \left\{1,2,\cdots ,N\right\}$，令 $V_{i,j}$ 表示 $\left(i,j\right)$ 的相邻点，即

$V_{i,j}=\left\{\left(i,j-1\right),\left(i,j+1\right),\left(i-1,j\right),\left(i+1,j\right)\right\}.$

同时令 $y_{i,j}$ 表示点 $\left(i,j\right)$ 的观测像素。下面简要回顾一下两阶段法。在第一阶段，两阶段法利用自适应中值滤波器(AMF)探测出椒盐噪声的位置，并令 $N\subseteq A$ 表示椒盐噪声的坐标集合；第二阶段，两阶段法通过求解下面的最优化问题填补椒盐噪声点处的像素值。

$\underset{u}{\min }{\mathcal{G}}_{\alpha }\left(u\right)={\displaystyle \underset{\left(i,j\right)\in N}{\sum }\left\{{\sum }_{\left(m,n\right)\in V_{i,j}\backslash N}{\phi }_{\alpha }\left(u_{i,j}-y_{m,n}\right)+\frac{1}{2}{\displaystyle \underset{\left(m,n\right)\in V_{i,j}\cap N}{\sum }{\phi }_{\alpha }}\left(u_{i,j}-y_{m,n}\right)\right\}},$

其中 $\alpha$ 是正则化参数， ${\phi }_{\alpha }$ 是保边函数， $u={\left[u_{i,j}\right]}_{\left(i,j\right)\in N}$ 是一个列向量(按字典序排列)。

图1与图2给出利用TTMHSCG1与TTMHSCG2还原Lena (256 × 256)的结果，其中图1的PSNR由13.8402增加到29.0134，图2的PSNR由13.8571增加到28.4543。

图1. TTMHSCG1去噪效果(左：原始图，中：含噪图，右：去噪图)

图2. TTMHSCG2去噪效果(左：原始图，中：含噪图，右：去噪图)

由图1与图2的还原效果可以看出，TTMHSCG1与TTMHSCG2成功地将脉冲噪声去除，因此其在脉冲噪声去噪方面表现良好。

5. 结论

本文设计了两种修正的HS共轭梯度法，它们同时满足充分下降性与共轭条件，同时这两个性质是不依赖于线搜索的。同时本文证明了两种修正HS共轭梯度法的全局收敛性。最后初步的数值实验表明所设计方法在脉冲噪声去噪方面是有效的。

致谢

感谢审稿人对本文提出的宝贵意见。

基金项目

枣庄学院博士科研启动基金、枣庄学院教学改革重点项目(XJG20019)。

文章引用

孙 敏,田茂英. 基于共轭梯度的脉冲噪声去噪算法
Impulse Noise Denoising Algorithm Based on Conjugate Gradient[J]. 图像与信号处理, 2022, 11(03): 125-133. https://doi.org/10.12677/JISP.2022.113014

参考文献