Accelerated preconditioning Krasnosel'skiĭ-Mann method for efficiently solving monotone inclusion problems

1.   Introduction

Let $\mathcal{H}$ be a real Hilbert space equipped with an inner product denoted by $\langle\cdot, \cdot\rangle$, and let $\|\cdot\|$ denote the norm induced by this inner product.

The monotone inclusion problem (MIP) is to find a point $x^*\in\mathcal{H}$ such that

where $A:\mathcal{H}\to 2^{\mathcal{H}}$ is a set-value operator and $B:\mathcal{H}\to\mathcal{H}$ is an operator.

This problem arises in a wide range of applications, including optimization, convex minimization problems, equilibrium problems, variational inequality problems, signal and image processing, machine learning, mechanics and partial differential equations (see, for example, references ^{[1,2,3,4,5,6,7,8,9]}). To tackle the monotone inclusion problem, various techniques have been developed, including the method of alternating projections and the proximal point algorithm ^[10]. The forward-backward method is a well-known algorithm for solving the monotone inclusion problem involving two operators. The method, also known as the proximal gradient method or the iterative soft-thresholding algorithm, was introduced by Lions and Mercier in ^[11]. Recall some definitions of maximal monotone and cocoercive operators. The operator $A:\mathcal{H}\to2^{\mathcal{H}}$ is called maximally monotone when no proper monotone extension of the graph of $A$ exists. For $L > 0$, the operator $B: \mathcal{H}\to \mathcal{H}$ is said to be $L$-cocoercive if it satisfies $L\|Bx-By\|^2\le \langle x-y, Bx-By\rangle, \forall\ x, y\in \mathcal{H}.$ Their method is defined as follows:

where $A:\mathcal{H}\to 2^{\mathcal{H}}$ is maximal monotone operator, and $B:\mathcal{H}\to\mathcal{H}$ is a $1/L$-cocoercive. They presented weak convergence of their algorithm under the assumption that $\lambda_k\in (0, 2/L)$.

In 1964, Polyak ^[12] introduced several innovative ideas aimed at improving the convergence speed of iterative algorithms. These approaches entail modifications to traditional iterative procedures, such as incorporating variable relaxation parameters and implementing acceleration methods that incorporate an inertial extrapolation term, denoted as ${{\theta }_{n}}({{x}_{n}}-{{x}_{n-1}})$, where ${{\theta }_{n}}$ is a sequence satisfying specific assumptions. Subsequently, inertial extrapolation has gained substantial attention and has been thoroughly investigated by numerous researchers; for more details, please refer to ^{[13,14,15,16,17,18,19]}.

Afterward, Moudafi and Oliny ^[20] applied the concept of the inertial method and the forward-backward method to introduce a new algorithm for solving MIP. The method is as follows:

where $A:\mathcal{H}\to 2^{\mathcal{H}}$ is a maximal monotone operator, $(\theta_k)_{k\ge0 }\subseteq[0, 1)$ is an inertial parameter sequence and $B:\mathcal{H}\to\mathcal{H}$ is a $1/L$-cocoercive. It has been shown that the generated sequence $(x_k)_{k\ge0}$ converges weakly to a solution of MIP when $\sum_{k\ge 1}\theta_k\|x_k-x_{k-1}\|^2 < +\infty$ and $\lambda_k\in(2/L)$.

To accelerate the algorithm for solving MIP, preconditioners are frequently employed. One such approach is the preconditioning forward-backward algorithm for solving MIP, defined as follows:

where $A:\mathcal{H}\to 2^{\mathcal{H}}$ is a maximal monotone operator and $B:\mathcal{H}\to\mathcal{H}$ is a $M$-cocoercive, where the precoditioner $M$ is a bounded linear operator. This method was introduced by Lorenz and Pock ^[21]. Furthermore, under appropriate assumptions on the parameters, it converges weakly to a solution of MIP.

In 2022, Altiparmak and Karahan ^[22] presented a new preconditioning forward-backward algorithm for solving MIP, incorporating the concept of viscosity. The algorithm is defined as follows:

where $T: = (I+\lambda M^{-1}A)^{-1}(I-\lambda M^{-1}B)$, $\lambda\in (0, 1]$, $(\theta_k)_{k\ge0 }\subseteq[0, \theta]$ with $\theta\in[0, 1)$, $(\alpha_k)_{k\ge0}$ and $(\beta_k)_{k\ge0}$ are sequences in $(0, 1]$. They proved the strong convergence results of this method.

Alternatively, for a certain nonexpansive operator $T: \mathcal{H}\to \mathcal{H}$ with $\text{Fix } T\neq\emptyset$, where $\text{Fix } T: = \{x\in \mathcal{H}:Tx = x\}$, the celebrated Krasnosel'skiĭ-Mann method [23, Theorem 2.2] for finding a point in $\text{Fix } T$ has the following form:

where $x_1\in \mathcal{H}$ is arbitrarily chosen, $(\lambda_k)_{k\geq1}\subset(0, 1)$ is a real sequence. It is well known that the sequence generated by Krasnosel'skiĭ-Mann method converges weakly to a point in $\text{Fix } T$. In order to deal with strong convergence result of Krasnosel'skiĭ-Mann type method, Boţ, Csetnek and Meier ^[24] proposed a modified Krasnosel'skiĭ-Mann method [24, Scheme (2)] of the following form:

where $x_1\in \mathcal{H}$ and $(\alpha_k)_{k\ge1}$, $(\delta_k)_{k\ge1}$ are sequences in $(0, 1]$. They proved that the generated sequence converges strongly to a point $x^*\in\text{Fix } T$. It is worth noting that such a point $x^*$ has a special feature in the sense that it captures the minimal norm value compared to other fixed points of $T$. The modified Krasnosel'skiĭ-Mann method (1.6) has been studied and generalized extensively in some aspects, see for example ^{[14,25,26,27]}. Recently, many researchers have proposed iterative methods to solve fixed point problems; see, e.g., ^[28,29,30] and the references therein.

The main contribution of this work is the introduction of an iterative method designed to find the zero of two monotone operators, as presented in problem (1.1). This method is built upon the principles of preconditioning and a modified Krasnosel'skiĭ-Mann method (1.6). Under certain conditions on the control sequences, we establish the strong convergence of our proposed algorithm to address the problem (1.1). To illustrate the effectiveness of our approach, we present a series of numerical experiments focused on the convex minimization problem.

2.   Preliminaries

In this section, we present results from real Hilbert spaces that are pertinent to this study, particularly in the context of convergence analysis.

Consider $\mathcal{C}$ as a nonempty closed convex subset of $\mathcal{H}$. For any $z\in \mathcal{H}$, there exists a unique $x^*\in \mathcal{C}$ satisfying $\left\| z-{{x}^{*}} \right\| = \underset{x\in \mathcal{C}}{\mathop{\inf }}\, \left\| z-x \right\|$. Furthermore, if we define ${{\bf proj}_{\mathcal{C}}}:\mathcal{H}\to \mathcal{C}$ by ${{\bf proj}_{\mathcal{C}}}(z) = {{x}^{*}}$ for all $z\in H$, we refer to ${{\bf proj}_{\mathcal{C}}}$ as the metric projection (or nearest point projection) from $\mathcal{H}$ onto $\mathcal{C}$.

Let $A:\mathcal{H}\to2^{\mathcal{H}}$ be a set-value operator. We denote the graph of $A$ as ${\bf gra}(A): = \{(x, w)\in\mathcal{H}\times\mathcal{H}: w\in Ax \}$. The operator $A$ is said to be monotone if $\langle x-y, w-z\rangle\ge 0$ for all $(x, w), (y, z)\in {\bf gra}(A)$, and it is called maximally monotone when no proper monotone extension of the graph of $A$ exists.

For a function $h:\mathcal{H}\to (-\infty, +\infty]$, we say that $h$ is proper if there exists at least one $x\in \mathcal{H}$ such that $h(x) < +\infty$. The subdifferential of $h$ at $x\in \mathcal{H}$, where $h(x)\in\mathbb{R}$, is defined as follows:

We say that and $h$ is subdifferentiable at $x\in \mathcal{H}$ if $\partial h(x)\neq\emptyset$. The elements of $\partial h(x)$ are referred to as the subgradients of $h$ at $x$. It is a well-established fact that the subdifferential of a proper convex lower semicontinuous function constitutes a maximally monotone operator.

Let $M: \mathcal{H}\to \mathcal{H}$ be a bounded linear operator. $M$ is characterized as self-adjoint if $M^* = M$, where $M^*$ represents the adjoint of the operator $M$. A self-adjoint operator is considered positive definite if $\langle M(x), x\rangle > 0$ for every $0\neq x\in \mathcal{H}$ ^[31].

Using the self-adjoint, positive and bounded linear operator $M$, we define the $M$-inner product as follows:

Definition 2.1. ^[32] Let $\mathcal{C}$ be a nonempty subset of $\mathcal{H}$, and let $M: \mathcal{H}\to \mathcal{H}$ be a positive definite operator. Then an operator $T:\mathcal{C}\to \mathcal{H}$ is said to be:

(i) nonexpansive operator with respect to $M$-norm if it satisfies: $\|Tx-Ty\|_M\le \|x-y\|_M, \ \ \forall\ x, y\in \mathcal{H},$

(ii) $M$-cocoercive operator if it satisfies: $\|Tx-Ty\|_{M^{-1}}^2\le \langle x-y, Tx-Ty\rangle, \ \ \forall\ x, y\in \mathcal{H}.$

Lemma 2.1. ^[32] Let $A: \mathcal{H}\to2^{ \mathcal{H}}$ be a maximal monotone operator, and let $B: \mathcal{H}\to \mathcal{H}$ be a $M$-cocoercive operator, where $M: \mathcal{H}\to \mathcal{H}$ is a bounded linear self-adjoint operator. Assume that $M$ is a positive definite operator and $\lambda\in (0, 1]$. Then $(I+\lambda M^{-1}A)^{-1}(I-\lambda M^{-1}B)$ is nonexpansive with respect to $M$-norm.

Lemma 2.2. ^[32] Let $A: \mathcal{H}\to2^{ \mathcal{H}}$ be a maximal monotone operator, and let $B: \mathcal{H}\to \mathcal{H}$ be a $M$-cocoercive operator, where $M: \mathcal{H}\to \mathcal{H}$ is a bounded linear self-adjoint operator. Assume that $M$ is a positive definite operator and $\lambda\in (0, \infty)$. Then $x\in \mathcal{H}$ is a solution of monoton inclusion problem (1.1) if and only if $x$ is a fixed point of $(I+\lambda M^{-1}A)^{-1}(I-\lambda M^{-1}B)$.

The subsequent lemma constitutes an essential characterization of the metric projection.

Lemma 2.3. ^[33,34] Let $(s_k)_{k\ge1}$ and $(\mu_k)_{k\ge1}$ be sequences of nonnegative real numbers and satisfy the inequality

where $0\le \delta_k\le 1$ for all $k\ge 1$. Assume that $\sum_{k\ge 1}\varepsilon_k < +\infty.$ Then the following statement hold:

${\rm(i)}$ If $\mu_k\le c\delta_k$ (where $c\ge0$), then $(s_k)_{k\ge1}$ is bounded.

${\rm(ii)}$ If $\sum_{k\ge 1}\delta_k = \infty$ and $\limsup_{k\to+\infty}\frac{\mu_k}{\delta_k}\le 0$, then the sequence $(s_k)_{k\ge1}$ converges to $0$.

Lemma 2.4. ^[1] Let $T$ be a nonexpansive operator from $\mathcal{H}$ into itself. Let $(x_k)_{k\ge1}$ be a sequence in $\mathcal{H}$ and $x\in\mathcal{H}$ such that $x_k\rightharpoonup x$ as $k\to+\infty$ (i.e., $(x_k)_{k\ge1}$ converges weakly to $x$) and $x_k-Tx_k\to 0$ as $k\to +\infty$ (i.e., $(x_k-Tx_k)_{k\ge1}$ converges strongly to $0$). Then $x\in{\bf Fix}(T).$

3.   Main results

This section discuss the convergence analysis of the proposed algorithm.

To prove the convergence of Algorithm 1, we assume the following assumption throughout this work.

Assumption 3.1. Let $(\alpha_k)_{k\ge1}$ and $(\delta_k)_{k\ge1}$ be sequences in $(0, 1]$. Assume the conditions are verifiable, as follows:

$(1) \; \liminf\limits_{k\to+\infty}\alpha_k > 0$ and $\sum_{k\ge 1}|\alpha_k-\alpha_{k-1}| < +\infty$,

$(2) \; \lim\limits_{k\to+\infty}\delta_k = 1$, $\sum_{k\ge 0}(1-\delta_k) = +\infty$ and $\sum_{n\ge 1}|\delta_k-\delta_{k-1}| < +\infty$.

We have verified Assumption 3.1 as shown in the following remark.

Remark 3.1. Let $z\in\mathcal{H}$. We set $\delta_k = 1-\frac{1}{k+1}$ and $\alpha_k = \frac{1}{2}-\frac{1}{(k+1)^2}$. It's easy to see that the Assumption 3.1 is satisfied.

Theorem 3.1. Let $M$ be a bounded linear self-adjoint and positive definite operator on $\mathcal{H}$, $A:\mathcal{H}\to 2^{\mathcal{H}}$ be a maximally monotone and let $B:\mathcal{H}\to\mathcal{H}$ be $M$-cocoercive operator such that $(A+B)^{-1}(0)\neq\emptyset$. Let $(x_k)_{k\ge 1}$ be generated by Algorithm 1. Assume that $(\alpha_k)_{k\ge1}$ and $(\delta_k)_{k\ge1}$ satisfy Assumption 3.1. Then, the sequence $(x_k)_{k\ge1}$ strongly converges to ${\bf proj}_{ {\bf Fix}((A+B)^{-1}(0))}(0)$.

Proof. Let $x^*\in(A+B)^{-1}(0)$. We define $\Gamma_{\lambda, M}^{A, B}: = (I+\lambda M^{-1}A)^{-1}(I-\lambda M^{-1}B)$ for ease of reference and convenience. From Algorithm 1, we obtain that

Let us consider $\|\delta_kx_k-x^*\|_M$ in the inequality (3.1),

Combining (3.1) and (3.2), we have

for all $k\ge 0$, hence $(x_k)_{k\ge1}$ is bounded.

Next, we cliam that $\|x_{k+1}-x_k\|\to 0$ as $k\to +\infty$. Let us consider,

By the boundedness of a sequence $(x_k)_{k\ge1}$ and the definition of $\Gamma_{\lambda, M}^{A, B}$, we have there exists $C_1 > 0$ such that

It follows that

Next, we will consider the term $\|\delta_kx_k-\delta_{k-1}x_{k-1}\|_M$ in the inequality (3.5).

Let us consider,

By the boundedness of a sequence $(x_k)_{k\ge1}$, there exists $C_2 > 0$ such that

From inequality (3.6), we have

Combining (3.5) and (3.7), we get that

By applying Lemma 2.3 and Assumption 3.1, we obtain that $\|x_{k+1}-x_k\|_M\to 0$ as $k\to+\infty$.

Now, we prove that $\|\Gamma_{\lambda, M}^{A, B}(\delta_kx_k)-\delta_kx_k\|_M\to0$ as $k\to+\infty$. We observe that

It follows that

Since $\lim\limits_{k\to+\infty}\|x_{k+1}-x_k\|_M = 0$ and considering the properties of the sequences involved, we have

Next, we will show that $(x_k)_{k\ge1}$ strongly converges to ${\bf proj}_{ {\bf Fix}((A+B)^{-1}(0))}(0): = \overline{x}$. From inequality (3.1) and Lemma 2.3, we implies that

for all $k\ge 0.$

In order to show that the sequence $(x_k)_{k\ge1}$ strongly converges to $\overline{x}$, it is sufficient to prove that

On the other hand, assume that the inequality (3.12) does not hold. In this case, there exists a real number $l > 0$ and a subsequence $(x_{k_i})_{i\ge1}$ such that

For a sequence $(x_k)_{k\ge1}$ bounded in a Hilbert space $\mathcal{H}$, we can identify a subsequence $(x_{k_i})_{i\ge1}$ of $(x_k)_{k\ge1}$ that weakly converges to a point $z\in\mathcal{H}.$ Without loss of generality, we can assume that $x_{k_i}\rightharpoonup z$ as $i\to+\infty.$ Therefore,

Notice that $\lim\limits_{k\to+\infty}\delta_k = 1$, we get $\delta_{k_i}x_{k_i}\rightharpoonup z$ as $i\to+\infty.$ Applying Lemma 2.4, we obtain that $z\in{\bf Fix}(\Gamma_{\lambda, M}^{A, B}).$ Hence, we obtain that $\langle -\overline{x}, z-\overline{x}\rangle_M\le0,$ which is a contradiction. Therefore, the inequality (3.12) is verifyed. It follows that

Using Lemma 2.3 and (3.11), we can conclude that $\lim\limits_{k\to+\infty}x_k = \overline{x}.$ Then the proof is complete. □

Now, Let us consider the following convex minimization problem (CMP):

where $f: \mathcal{H}\to\mathbb{R}$ is a proper convex lower semi-continuous function and $g: \mathcal{H}\to\mathbb{R}$ is a differentiable function with the gradient of $g$ being a Lipschitz continuous operator with constant $L_g$. Moreover, since the function $g$ is differentiable, and by using the Baillon-Haddad Theorem (see ^[1]), $\nabla g$ is cocoercive with respect to $\frac{1}{L_g}$. Furthermore, if $f: \mathcal{H}\to\mathbb{R}$ is a proper convex lower semi-continuous function, then $\partial f$ is maximal monotone. It is well-known that a point $x^*$ is a solution of convex minimization problem (3.14) if and only if $0\in \partial f(x^*)+\nabla g(x^*)$. In Theorem 3.1, set $A = \partial f$, $B = \nabla g$, and $M(x) = L_g(x)$. As a result, we can deduce the following corollary.

Corollary 3.1. Let $f: \mathcal{H}\to\mathbb{R}$ be a proper convex lower semi-continuous function, and let $g: \mathcal{H}\to\mathbb{R}$ be a differentiable function with the gradient of $g$ being Lipschitz continuous operator with constant $L_g$. Assume that the solution set of convex minimization problem (3.14) is nonempty, and parameters $(\alpha_k)_{k\ge1}$ and $(\delta_k)_{k\ge1}$ satisfy Assumption 3.1. Let $(x_k)_{k\ge1}$ be a sequence generated by:

Then, the sequence $(x_k)_{k\ge1}$ strongly converges to a solution $x^*$ of the convex minimization problem.

4.   Numerical experiments

In this section, we present numerical results comparing the performance of Algorithm 1, AK22 ^[22], BCM19 ^[24] and LP15 ^[21] in solving the convex minimization problem.

We demonstrate the effectiveness of our proposed iterative method by presenting a numerical example in the context of convex minimization. We also compare the convergence performance of our algorithm with existing methods from the literature. All experiments were conducted using MATLAB 9.19 (R2022b) and performed all computations on a MacBook Pro 14-inch 2021 with an Apple M1 Pro processor and 16 GB memory.

Let $f:\mathbb{R}^s\to\mathbb{R}$ be defied by $f(x) = \|x\|_1$ for all $x\in\mathbb{R}^s$ and $g:\mathbb{R}^s\to\mathbb{R}$ be defined by $g(x) = \|Kx-b\|^2_2$, where $K:\mathbb{R}^{s}\to \mathbb{R}^{l}$ is a non-zero linear transformation, $b\in \mathbb{R}^l$ for all $x\in\mathbb{R}^s$, we consider the following minimization problem:

The problem (4.1) can be written in the form of the monotone inclusion problem (1.1) as:

where $A = \partial f(\cdot)$ and $B = \nabla g(\cdot)$.

We generate vectors $x_0 = x_1\in \mathbb{R}^s$ and $b\in\mathbb{R}^l$ by random generating between $(–1, 1)$, and the matrix $K\in\mathbb{R}^{l\times s}$ is also generated using the same method of random generation between $(–1, 1)$.

In this numerical experiment, we terminate the algorithms by the stopping criterion

All computational times are given in seconds (sec.). In Theorem 3.1, we set $M(x) = \|K\|^2(x)$ and $\lambda = 1$. For AK22, we set $M(x) = \|K\|^2(x)$, $\lambda = 1$, $f(x) = 0.99x$ for all $x\in\mathbf{R}^s$, and

For BCM19, we set $\lambda = \frac{1}{\|K\|^2}$. For LP15, we set $\lambda_k = 1$, $M(x) = \|K\|^2(x)$ and $\theta_k$ defined as in (4.3).

The optimal parameter combinations for each method are as follows: Combination of each method are as follows:

● ${\bf Algorithm \; 1}$: $\alpha_k = 0.1+\frac{1}{k+1}$ and $\delta_k = 1-\frac{0.0005}{k+1}$.

● ${\bf AK22}$: $\alpha_k = 0.2+\frac{1}{k+1}$ and $\beta_k = \frac{1}{8k}$.

● ${\bf BCM19}$: $\alpha_k = 0.1+\frac{1}{k+1}$ and $\delta_k = 1-\frac{0.0005}{k+1}$.

For detailed parameter combinations, please refer to Appendices 1, 2 and 3.

Next, we present the behavior of Algorithm 1, AK22, BCM19 and LP15 for the average computational running time. We performed all methods for different sizes of $(l, s)$. The results are plotted in Figures 1–3.

5.   Conclusions

The objective of this study was to address a monotone inclusion problem guided by a maximal monotone operator and a cocoercive operator. We employed a combination of the preconditioning and Krasnosel'skiĭ-Mann method and proved the strong convergence of the generated sequence of iterates towards a solution to the considered problem. Numerical experiments reveal that under certain suitable parameters, the proposed method exhibits superior convergence behavior compared to existing algorithms.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

N. Artsawang has received funding support from Naresuan University [grant number R2566C026].

Conflict of interest

The author declare no conflict of interest.

Appendix 1

Parameter combinations of Algorithm 1

We start with the investigation of several parameter combinations which are chosen as in Algorithm 1 for minimization problem (4.1) by running algorithm and terminate it by the stopping criterion $t = 10^{-7}.$ We present the average computational running time for various choices of the parameters $\alpha_k$ and $\delta_k$, when the dimension of $K$ is $(100,400)$ in Table 1.

Table 1 shows that using the combination of $\alpha_k = 0.1+\frac{1}{k+1}$ with the relaxation parameter $\delta_k = 1-\frac{0.0005}{k+1}$ resulted in the shortest computational running time (2.0055 seconds).

Appendix 2

Parameter combinations of AK22

In this section, we present some parameter combinations of AK22. All experimental settings are the same as mentioned above.

Table 2 presents the average computational running time for different parameter choices of $\lambda_k$ and $\delta_k$. The combination of $\alpha_k = 0.2+\frac{1}{k+1}$ and $\beta_k = \frac{1}{8k}$ resulted in the shortest computational running time of $2.0045$ seconds.

Appendix 3

Parameter combinations of BCM19

In this section, we present some parameter combinations of BCM19.

Table 3 shows that using the combination of $\alpha_k = 0.1+\frac{1}{k+1}$ with the relaxation parameter $\delta_k = 1-\frac{0.0005}{k+1}$ resulted in the shortest computational running time (2.1517 seconds).