A modified inertial proximal gradient method for minimization problems and applications

1.   Introduction

In this paper, we investigate the following convex minimization problem

where $H$ is a real Hilbert space, $g:H\rightarrow (-\infty, +\infty]$ is proper, lower semicontinuous and covex and $f:H\rightarrow \mathbb{R}$ is convex and differentiable with the Lipschitz continuous gradient denoted by $\nabla f$. It is known that $x^*$ is a minimizer of $f+g$ if and only if

where $\partial g$ denotes the subdifferential of $g$.

The convex minimization problem is an important mathematical models which unify numerous issues in applied mathematics for example, signal processing, image reconstruction, machine learning and so on. See ^{[1,3,8,9,11,22,31]}.

The most popular algorithm for solving the convex minimization problem is the so-called forward-backward algorithm ${\bf(FB)}$, which generates by a starting point $x_1\in H$ and

where $prox_g$ is the proximal operator of $g$ and the stepsize $\lambda\in(0, 2/L)$, $L$ is the Lipschitz constant of $\nabla f$.

Polyak ^[21] first proposed the inertial idea to improve the convergence speed of the method. In recent years, many authors introduced various fast iterative methods via inertial technique, for example, ^{[7,8,10,15,16,18,23,25,26,32]}.

In 2009, Beck and Teboulle ^[4] introduced the fast iterative shrinkage-thresholding algorithm for linear inverse problem ${\bf(FISTA)}$. Let $t_0 = 1$ and $x_0 = x_1\in H$. Compute

This improves the convergence speed for $O(1/n^2)$. However, the stepsize is established under the condition of the Lipschitz constant which is not known in general.

In 2000, Tseng ^[29] proposed a modified forward-backward algorithm (MFB) via the stepsize with linesearch technique as follows. Given $\sigma > 0$, $\rho\in(0, 1)$, $\delta\in(0, 1)$ and $x_1\in H$. Compute

where $\lambda_n$ is the largest $\lambda\in\{\sigma, \sigma\rho, \sigma\rho^2, ...\}$ satisfying $\lambda\|\nabla f(y_n)-\nabla f(x_n)\|\leq\|y_n-x_n\|$.

In 2020, Padcharoen et al. ^[20] proposed the modified forward-backward splitting method based on inertial Tseng method ${\bf(IMFB)}$. Given $\{\lambda_n\}\subset(0, \frac{1}{L})$, $\{\alpha_n\}\subset[0, \alpha]\subset[0, 1)$. Let $x_0, x_1\in H$ and compute

They established weak convergence of the proposed method.

In 2015, Shehu et al. ^[24] introduced the modified split proximal method ${\bf(MSP)}$. Let $r:H\rightarrow H$ be a contraction mapping with constant $\alpha\in(0, 1)$. Set $\varphi(x) = \sqrt{\|\nabla h(x)\|^2+\|\nabla \ell(x)\|^2}$ with $h(x)$ = $\frac{1}{2}\|(I-prox_{\lambda g})Ax\|^2$, $\ell(x) = \frac{1}{2}\|(I-prox_{\lambda\mu_nf})x\|^2$. Given an initial point $x_1\in H$ and construct

where the stepsize $\mu_n = \psi_n\frac{h(x_n)+\ell(x_n)}{\varphi^2(x_n)}$ with $0 < \psi_n < 4$. They proved strong convergence theorem for proximal split feasibility problems.

In 2016, Cruz and Nghia ^[5] presented a fast multistep forward-backward method ${\bf(FMFB)}$ with a linesearch. Given $\sigma > 0$, $\mu\in(0, \frac{1}{2})$, $\rho\in(0, 1)$ and $t_0 = 1$. Choose $x_0, x_1\in H$ and compute

where $\lambda_n = \sigma\rho^{m_n}$ and $m_n$ is the smallest nonnegative integer such that

Very recently, Malitsky and Tam ^[17] introduced the forward-reflected-backward algorithm ${\bf(FRB)}$. Given $\lambda_{0} > 0$, $\delta\in(0, 1)$, $\gamma\in\{1, \beta^{-1}\}$ and $\beta\in(0, 1)$. Compute

where the stepsize $\lambda_n = \gamma\lambda_{n-1}\beta^i$ with $i$ being the smallest nonnegative integer satisfying $\lambda_n\|\nabla f(x_{n+1})-\nabla f(x_n)\|\leq\frac{\delta}{2}\|x_{n+1}-x_{n}\|$.

Very recently, Hieu et al. ^[13] proposed the modified forward-reflected-backward method ${\bf(MFRB)}$ with adaptive stepsize. Given $x_{0}, x_1\in H$, $\lambda_{0}, \lambda_1 > 0$, $\mu\in(0, \frac{1}{2})$:

This stepsize allows the proposed method without knowing the Lipschitz constant to solve the problem.

Inspired and motivated by previous works, we propose based on the adaptive stepsize, the inertial proximal gradient algorithm for convex minimization problems. This method requires more flexible conditions than the fixed stepsize does. We then establish weak convergence of our scheme under some assumptions. Moreover, we present some numerical experiments in image deblurring. It reveals that our algorithm outperforms other methods.

2.   Basic definitions and lemmas

In this section, we provide some definitions and lemmas for proving our theorem.

Weak and strong convergence of a sequence $\{x_n\}\subset\Omega$ to $z\in\Omega$ are denoted by $x_n\rightharpoonup z$ and $x_n\rightarrow z$, respectively.

Let $g : H\rightarrow (-\infty, +\infty]$ be a proper, lower semicontinuous and convex function. We denote the domain of $g$ by ${\rm dom} g = \{x \in H | g(x) < +\infty\}$. For any $x\in {\rm dom} g$, the subdifferential of $g$ at $x$ is defined by

Recall that the proximal operator ${\rm prox}_g:{\rm dom}(g)\rightarrow H$ is given by ${\rm prox}_g(x) = (I + \partial g)^{-1}(z), \ z\in H.$ It is known that the proximal operator is single-valued. Moreover, we have

Definition 2.1. Let $S$ be a nonempty subset of $H$. A sequence $\{x_n\}$ in $H$ is said to be quasi-Fejér convergent to $S$ if and only if for all $x\in S$ there exists a positive sequence $\{\varepsilon_n\}$ such that $\sum\limits_{n = 1}^{\infty}\varepsilon_n < +\infty$ and $\|x_{n+1}-x\|^2\leq\|x_n-x\|^2+\varepsilon_n$ for all $n\geq1$. If $\{\varepsilon_n\}$ is a null sequence, we say that $\{x_n\}$ is Fejér convergent to $S$.

Lemma 2.1. ^[6] The subdifferential operator $\partial g$ is maximal monotone. Moreover, the graph of $\partial g, \ {\rm Gph}(\partial g) = \{(x, v)\in H\times H: v\in\partial g(x)\}$ is demiclosed, i.e., if the sequence $\{(x_n, v_n)\}\subset {\rm Gph}(\partial g)$ satisfies that $\{x_n\}$ converges weakly to $x$ and $\{v_n\}$ converges strongly to $v$, then $(x, v)\in{\rm Gph}(\partial g)$.

Lemma 2.2. ^[19] Let $\{a_n\}$, $\{b_n\}$ and $\{c_n\}$ be real positive sequences such that

If $\Sigma_{n = 1}^{\infty}c_n < +\infty$ and $\Sigma_{n = 1}^{\infty}b_n < +\infty$, then $\lim\limits_{n\rightarrow +\infty} a_n$ exists.

Lemma 2.3. ^[12] Let $\{a_n\}$ and $\{\theta_n\}$ be real positive sequences such that

Then, $a_{n+1}\leq K\cdot\prod_{i = 1}^{n}(1+2\theta_i)$ where $K = \max\{a_1, a_2\}.$ Moreover, if $\sum_{n = 1}^{\infty}\theta_n < +\infty$, then $\{a_n\}$ is bounded.

Lemma 2.4. ^[2,14] If $\{x_n\}$ is quasi-Fejér convergent to $S$, then we have:

(i) $\{x_n\}$ is bounded.

(ii) If all weak accumulation points of $\{x_n\}$ is in $S$, then $\{x_n\}$ weakly converges to a point in $S$.

3.   Main result

In this section, we assume that the following conditions are satisfied for our convergence analysis:

(A1) The solution set of the convex minimization problem (1.1) is nonempty, $i.e.$, $\Omega = {\rm argmin} (f+g)\neq\emptyset$.

(A2) $f, g : H\rightarrow (-\infty, +\infty]$ are two proper, lower semicontinuous and convex functions.

(A3) $f$ is differentiable on $H$ and $\nabla f$ is Lipschitz continuous on $H$ with the Lipschitz constant $L > 0$.

We next introduce a new inertial forward-backward method for solving (1.1).

Algorithm 3.1. Inertial modified forward-backward method (IMFB)

Initialization: Let $x_0 = x_1\in H$, $\lambda_1 > 0$, $\theta_1 > 0$ and $\delta\in(0, 1)$.

Iterative step: For $n\geq1$, calculate $x_{n+1}$ as follows:

Step 1. Compute the inertial step:

Step 2. Compute the forward-backward step:

Step 3. Compute the $x_{n+1}$ step:

where

Set $n = n+1$ and return to Step 1.

Remark 3.1. It is easy to see that the sequence $\{\lambda_n\}$ is non-increasing. From the Lipschitz continuity of $\nabla f$, there exists $L > 0$ such that $\|\nabla f(w_n)-\nabla f(y_n)\|\leq L\|w_n-y_n\|$. Hence,

By the definition of $\{\lambda_n\}$, it implies that the sequence $\{\lambda_n\}$ is bounded from below by $\min\{\lambda_0, \frac{\delta}{L}\}$. So, we obtain $\lim_{n\rightarrow \infty}\lambda_n = \lambda > 0$.

Lemma 3.1. Let $\{x_n\}$ be generated by Algorithm 3.1. Then

Proof. Let $x^*\in\Omega$. Then

Note that

It follows that

Combining (3.7) and (3.9), we obtain

From (3.2), we see that $w_n-\lambda_n\nabla f(w_n)\in(I+\lambda_n\partial g)y_n$. Since $\partial g$ is maximal monotone, then there is $u_n\in\partial g(y_n)$ such that

This shows that

Since $0\in(\nabla f+\partial g)(x^*)$ and $\nabla f(y_n)+u_n\in(\nabla f +\partial g)y_n$, we get

Substituting (3.12) into (3.13), we have

This implies that $\langle w_n-\lambda_n\nabla f(w_n)-y_n+\lambda_n\nabla f(y_n), y_n-x^*\rangle\geq0$. Using (3.10), we derive

Lemma 3.2. Let $\{x_n\}$ be generated by Algorithm 3.1. If $\sum_{n = 1}^{\infty}\theta_n < \infty$, then $\lim_{n\rightarrow \infty}\|x_n-x^*\|$ exists for all $x^*\in\Omega$.

Proof. Let $x^*\in\Omega$. From Lemma 3.1, we see that

So, we have

Hence

By Lemma 2.3, we conclude that

where $K = \max\{\|x_1-x^*\|, \|x_2-x^*\|\}$. Since $\sum_{n = 1}^{\infty}\theta_n < +\infty$, by Lemma 2.3, we have $\{x_n-x^*\}$ is bounded. Hence $\sum_{n = 1}^{\infty}\theta_n\|x_n-x_{n-1}\| < +\infty$. By Lemma 2.2 and (3.17), we have $\lim\limits_{n\rightarrow \infty}\|x_n-x^*\|$ exists.

Lemma 3.3. Let $\{x_n\}$ be generated by Algorithm 3.1. If $\sum_{n = 1}^{\infty}\theta_n < \infty$, then

Proof. We see that

From (3.15) and (3.20), we have

Note that $\theta_n\|x_n-x_{n-1}\|\rightarrow0$ and $\lim\limits_{n\rightarrow \infty}\|x_n-x^*\|$ exists by Lemma 3.2. From (3.1) and (3.21), we have $\|w_n-x_n\|\rightarrow0$ and $\|w_n-y_n\|\rightarrow0$, respectively. It is easy to see that $\|x_n-y_n\|\rightarrow0$. Since $\nabla f$ is uniformly continuous, we obtain

From (3.3) and (3.22), we get

Thus, we have

Theorem 3.1. Let $\{x_n\}$ be generated by Algorithm 3.1. If $\sum_{n = 1}^{\infty}\theta_n < \infty$, then $\{x_n\}$ weakly converges to a point in $\Omega$.

Proof. Since $\{x_n\}$ is bounded, there exists a subsequence $\{x_{n_k}\}$ of $\{x_n\}$ such that $x_{n_k}\rightharpoonup \bar{x}\in H$. From Lemma 3.3, we obtain $x_{n_k+1}\rightharpoonup \bar{x}$. We note that

From (2.1), we obtain

Hence

Since $\|x_n-y_n\|\rightarrow0$, we also have $y_{n_k}\rightharpoonup\bar{x}$. Letting $k\rightarrow \infty$ in (3.27) and using (3.22), by Lemma 2.1 and Remark 3.1, we get

So $\bar{x}\in\Omega$. From (3.21) we see that $\{x_n\}$ is a quasi-Fejer sequence. Hence, by Lemma 2.4, we conclude that $\{x_n\}$ weakly converges to a point in $\Omega$. This completes the proof.

4.   Numerical experiment in image deblurring

The image deblurring can be modeled by the following linear equation system:

where $A\in\mathbb{R}^{N\times M}$ is the blurring matrix, $x\in\mathbb{R}^N$ the original image, $b\in\mathbb{R}^M$ the degraded image and $v\in\mathbb{R}^M$ is the noisy.

An approximation of the clean image can be found by the following LASSO problem ^[27]:

where $\tau$ is a positive parameter, $\|\cdot\|_1$ is the $\ell_1$-norm, and $\|\cdot\|_2$ is the Euclidean norm.

It is known that (4.1) can be written in the form (1.1) by defining $f(x) = \frac{1}{2}\|b-Ax\|_2^2$ and $g(x) = \tau\|x\|_1$. We compare our algorithm (IMFB) with FISTA, MFB, FRB, MFRB, IMFB, MSP and FMFB.

In method IMFB, we set $t_0 = 1$, $t_n = \frac{1+\sqrt{1+4t_{n-1}^2}}{2}$ and

The regularization parameters are chosen by $\tau = 10^{-5}$ and $x_0 = x_1 = (1, 1, 1, ..., 1)\in\mathbb{R}^N$. We set the following parameters in Table 1.

In this example, we set all parameters as in Table 1. For the experiments, we use the sizes $251\times189$ for RGB images which are blurred by the following blur types:

(ⅰ) Motion blur with motion length of 45 pixels and motion orientation $180^\circ$.

(ⅱ) Gaussian blur of filter size $5\times 5$ with standard deviation 5.

(ⅲ) Out of focus with radius 7.

We add Poisson noise and use a Fast Fourier Transform (FFT) for converting it to the frequency domain. Structural similarity index measure (SSIM) ^[30] is used for measuring the similarity between two images. Peak-signal-to-noise ratio (PSNR) in decibel (dB) ^[28] is defined by

where MSE$= \|x_n-x\|^2$ and $x$ is the original image. It is noted that, a higher PSNR generally indicates that the reconstruction is of higher quality. The resultant SSIM index is a decimal value between 0 and 1, and value 1 is indicates perfect structural similarity.

The numerical experiments have been carried out in Matlab environment (version R2020b) on MacBook Pro M1 with ram 8 GB. For the results recovering the degraded RGB images, we limit the iterations to 1,000. We report the numerical results in Table 2.

In Table 2, we see that IMFB has a higher PSNR than FISTA, MFB, FRB, MFRB, IMFB, MSP, FMFB for the same number of iterations. Moreover, SSIM of IMFB is closer to 1 than other methods. This shows that our algorithm has a better convergence than other methods for this example. However, we observe that IMFB has a less CPU time than other methods.

We next show the different types of blurred RGB images with the PSNR in Figure 1.

We next show the restored images of RGB images for Motion blur with the PSNR in Figure 2.

We next show the restored images of RGB images for Gaussian blur with the PSNR in Figure 3.

We next show the restored images of RGB images for out of focus with the PSNR in Figure 4.

The results of the numerical experiments are summarized in Table 2. Figure 1 shows the original and blurred images for this experiment. In Figures 2–5, we report all results that include the recovered images via each algorithms. It is shown that IMFB outperforms FISTA, MFB, FRB, MFRB, IMFB, MSP and FMFB in terms of PSNR and SSIM.

5.   Conclusions

In this paper, we established the convergence theorem of the iterates generated by a new modified inertial forward-backward algorithm with adaptive stepsize under some suitable conditions for convex minimization problems. We applied our main result to image recovery. It was shown that our proposed method outperforms other methods in terms of PSNR and SSIM. In future work, we will study the convergence rate of the iteration.

Acknowledgments

This project is funded by National Research Council of Thailand (NRCT) under grant No. N41A640094. The authors wish to thank University of Phayao and Thailand Science Research and Innovation grant No. FF65-UOE001.

Conflict of interest

The authors declare no conflict of interest.