The forward-backward-forward algorithm with extrapolation from the past and penalty scheme for solving monotone inclusion problems and applications

In the last decade, penalty schemes have become a popular approach for studying constrained or hierarchical optimization problems in Hilbert spaces, particularly for solving complex problems (see [1‐7]). In this work, we intend to study the general monotone inclusion problem in the term of the sum of three operators as the following form:where \(A: \mathcal {H} \rightrightarrows \mathcal {H}\) is a maximally monotone operator, \(D:\mathcal {H}\rightarrow \mathcal {H}\) a (single-valued) monotone and \(\eta ^{-1}\)-Lipschitz continuous operator with \(\eta >0\), and \(N_C: \mathcal {H} \rightrightarrows \mathcal {H}\) is the normal cone of the closed convex set \(C\subseteq \mathcal {H}\) which is the nonempty set of zeros of another operator \(B : \mathcal {H} \rightarrow \mathcal {H}\), which is a (single-valued) \(\mu ^{-1}\)-Lipschitz continuous operator with \(\mu >0\). If the involved operators are subdifferentials, the situation can be framed as a specialized convex bilevel optimization problem. In this context, the feasible set of the upper-level problem corresponds to the set of solutions for the lower-level problem, and both sets are characterized by convexity (see (3) and (4) below).

If \(D=0\), the problem (1) is the generalized version of the monotone inclusion problemwhere \(C=\arg \min \Psi \ne \emptyset \), and \(\Psi : \mathcal {H} \rightarrow \mathbb {R}\) is a convex differentiable function with a Lipschitz gradient satisfying \(\min \Psi = 0\), which introduces a penalization function with respect to the constraint \(x\in C\). Implicit and explicit discretized methods to solve the problem in (2) were proposed in Attouch et al.’s work [1, 2]. Several subsequent penalty type numerical algorithms in the literature are inspired by the continuous nonautonomous differential inclusion investigated in Attouch and Czarnecki’s paper [8].

In the case where A and D are the convex subdifferentials of the proper, convex, and lower semicontinuous functions \(\Phi : \mathcal {H} \rightarrow \bar{\mathbb {R}}\) and \(\phi : \mathcal {H} \rightarrow \bar{\mathbb {R}}\), respectively, then any solution of (1) solves the convex minimization problemand a solution of (2) solves the problemrespectively. Consequently, a solution to these convex minimizations can be approximated by using the same iterative scheme as in [1, 2, 5]. Furthermore, there are other methods for solving such optimization problems which are studied by several authors in the literature (see, for instance, [3, 6, 7, 9]).

The iterative algorithms for solving both monotone inclusion problems (1) and (2) in the penalty scheme have been proposed by several researchers (see [1‐5]). They could provide the weak ergodic convergence of the iterates for their proposed algorithms. In particular, they must suppose the strong monotonicity of A to prove the strong convergence. However, the (ergodic) convergent results need to assume the following hypothesis:For solving the monotone inclusion problem (1), if we use the approach involved with the forward-backward algorithm, then some of the operators in the iterates are cocoercive. For instance, (see [5]) with the sequences of positive real number, \((\lambda _n)_{n\in \mathbb {N}}\) and \((\beta _n)_{n\in \mathbb {N}}\), and the operators D and B are cocoercive. We know from the definition of the cocoercivity (see Section 2) that every cocoercive operator is a monotone and Lipchitz operator, but the converse argument is not the case. One of the research directions is to develop an algorithm for inclusions involving monotone and Lipschitz operators, which has known as Tseng’s type algorithm (or forward-backward-forward algorithm), see further [10]. In the penalty scheme, Boț and Csetnek [5] relaxed the cocoercivity of B and D to monotonicity and Lipschitzian and the convergence properties of Boț and Csetnek’s algorithm are studied under \((H_{fitz})\) and the condition \(\lim \sup _{n \rightarrow + \infty } \left( \frac{\lambda _{n}\beta _n}{\mu } + \frac{\lambda _{n}}{\eta } \right) < 1\).

In recent years, Tseng’s forward-backward-forward algorithm has been modified by many researchers in various versions depending on the setting of the operators (see [11‐15], and references therein). One such modification is the Tseng’s forward-backward-forward algorithm with extrapolation from the past, which is developed by using Popov’s idea [16] for the extragradient method with the extrapolated technique. This algorithm can store and reuse the extrapolated term in the next step of the iterative scheme, illustrated as where \(\gamma \) satisfies some suitable condition for each method and \(J_A\) is the resolvent operator of A. Indeed, the classical Tseng’s method requires two forward evaluations in every iteration, whereas the modified algorithm with extrapolation from the past can reuse one of the calculations from the prior procedure. According to this scheme, it has the potential to reduce computational costs and energy consumption in practical applications.

Motivated by these considerations, we investigate Tseng’s forward-backward-forward algorithm with extrapolation from the past involving a penalty scheme under certain hypotheses for solving the generalized inclusion problem in terms of the sum of three operators (1). We propose the algorithm and prove its weak ergodic convergence. Moreover, strong convergence is also demonstrated when the operator A is a strongly monotone operator in Section 3. Furthermore, we can extend our results in Section 3 to solve minimax problems as elaborated in Section 4. In Section 5, our proposed algorithm can be extended to solving more intricate problems involving the finite sum of the composition of the linear continuous operator with maximally monotone operators by using the product space approach, and the convergence results for our modified iterative method are also provided.

To broaden the applicability of our scheme, we also provide the iterative scheme and its convergence result for the convex minimization problem expressed in Section 6. Finally, we demonstrate a numerical experiment in TV-based image inpainting to ensure theoretical convergence results in Section 7.

In this paper, we introduce some notations used throughout. We denote the set of positive integers by \(\mathbb {N}\) and a real Hilbert space with an inner product \(\langle \cdot , \cdot \rangle \) and the associated norm \(\Vert \cdot \Vert = \sqrt{\langle \cdot , \cdot \rangle }\) by \(\mathcal {H}\). A sequence \((x_n)_{n\in \mathbb {N}}\) is said to converge weakly to x, if for any \(y\in \mathcal {H}\), \(\langle x_n, y \rangle \rightarrow \langle x, y \rangle \), and we use the symbols \(\rightharpoonup \) and \(\rightarrow \) to represent weak and strong convergence, respectively. For a linear continuous operator \(L: \mathcal {H}\rightarrow \mathcal {G}\), where \(\mathcal {G}\) is another real Hilbert space, we define the norm of L as \(\Vert L \Vert = \sup \{ \Vert Lx\Vert : x\in \mathcal {H}, \Vert x\Vert \le 1 \}\). We also use \(L^* : \mathcal {G} \rightarrow \mathcal {H}\) to denote the adjoint operator of L, defined by \(\langle L^* y, x \rangle = \langle y, Lx \rangle \) for all \((x,y) \in \mathcal {H} \times \mathcal {G}\).

For a function \(f: \mathcal {H} \rightarrow \bar{\mathbb {R}}\) (where \( \bar{\mathbb {R}}:= \mathbb {R}\cup \{\pm \infty \}\) is the extended real line), we denote its effective domain by \({\text {dom}} f = \{ x \in \mathcal {H} : f(x) < + \infty \}\) and say that f is proper if \({\text {dom}} f\ne \emptyset \) and \(f(x) \ne - \infty \) for all \(x\in \mathcal {H}\). Let \(f^* : \mathcal {H} \rightarrow \bar{\mathbb {R}}\), where \(f^*(u) = \sup _{x\in \mathcal {H}} \{ \langle u, x \rangle - f(x) \}\) for all \(u\in \mathcal {H}\), be the conjugate function of f. We denote by \(\Gamma (\mathcal {H})\) the family of proper, convex, and lower semicontinuous extended real-valued functions defined on \(\mathcal {H}\). The subdifferential of f at \(x\in \mathcal {H}\), with \(f(x)\in \mathbb {R}\), is the set \(\partial f(x) := \{v \in \mathcal {H} : f(y) \ge f(x) + \langle v, y-x \rangle \; \forall y\in \mathcal {H} \}\). We take, by convention, \(\partial f(x) :=\emptyset \) if \(f(x) \in \{ \pm \infty \}\).

The indicator function of a nonempty set \(S\subseteq \mathcal {H}\), denoted by \(\delta _{S} : \mathcal {H}\rightarrow \bar{\mathbb {R}}\), is defined as follows: \(\delta _{S}(x)=0\) if \(x\in S\) and \(\delta _{S}(x)=+\infty \) otherwise. The subdifferential of the indicator function is called the normal cone of S, denoted by \(N_{S}(x)\). For \(x \in S\), \(N_{S}(x)=\{ u\in \mathcal {H} : \langle y-x, u \rangle \le 0 \; \forall y \in S \}\), and \(N_{S}(x) = \emptyset \) if \(x\notin S\). It is worth noting that for \(x\in S\), \(u \in N_{S} (x)\) if and only if \(\sigma _{S}(u) = \langle x, u \rangle \), where \(\sigma _{S}\) is the support function of S. The support function is defined as \(\sigma _{S} (u) = \sup _{y\in S} \langle y, u \rangle \). A cone is a set that is closed under positive scaling, i.e., \(\lambda x \in S\) for all \(x \in S\) and \(\lambda > 0\). The normal cone, which is a tool used in optimization, is always a cone itself.

Let A be a set-valued operator mapping from a Hilbert space \(\mathcal {H}\) to itself. We define the graph of A as \(GrA=\{(x,u)\in \mathcal {H}\times \mathcal {H}:u\in A(x) \}\), the domain of A as \({\text {dom}} A=\{x\in \mathcal {H}: A(x) \ne \emptyset \}\), and the range of A as \({\text {ran}} A=\{u\in \mathcal {H}:\exists x\in \mathcal {H} \;\text {s.t.} \; u\in A(x) \}\). The inverse operator of A, denoted by \(A^{-1}:\mathcal {H}\rightrightarrows \mathcal {H}\), is defined as \((u,x)\in Gr A^{-1}\) if and only if \((x,u)\in Gr A\). We also define the set of zeros of A as \(zerA=\{x\in \mathcal {H}:0\in A(x) \}\). The operator A is said to be monotone if \(\langle x-y, u-v \rangle \ge 0\) for all \((x,u),(y,v)\in Gr A\). Moreover, a monotone operator A is said to be maximally monotone if its graph on \(\mathcal {H}\times \mathcal {H}\) has no proper monotone extension. If A is maximally monotone, then zerA is a closed and convex set, and a point \(z\in \mathcal {H}\) belongs to zerA if and only if \(\langle u-z, w \rangle \ge 0\) for all \((u,w)\in Gr A\). Conditions ensuring that zerA is nonempty can be found in Section 23.4 of [17].

The set-valued operator A is said to be \(\gamma \)-strongly monotone with \(\gamma > 0\) if and only if \(\langle x-y, u-v \rangle \ge \gamma \Vert x-y\Vert ^2\) for all \((x,u),(y,v) \in Gr A\). If A is maximally monotone and strongly monotone, then the set of zeros zerA is a singleton and thus nonempty (refer to Corollary 23.37 in [17]). A single-valued operator \(A : \mathcal {H}\rightarrow \mathcal {H}\) is considered to be \(\gamma \)-cocoercive if \(\langle x-y, A(x)-A(y) \rangle \ge \gamma \Vert A(x)-A(y) \Vert ^2\), and \(\gamma \)-Lipschitz continuous (or \(\gamma \)-Lipschitzian) if \(\Vert A(x)-A(y) \Vert \le \gamma \Vert x-y\Vert \) for all \((x,y)\in \mathcal {H}\times \mathcal {H}\).

In optimization, the proximal operator is a common tool used to develope algorithms for solving problems that involve a sum of a smooth function and a nonsmooth function. The proximal operator of a function f at a point x is defined as the unique minimizer of the function \(y\mapsto f(y) + \frac{1}{2}\Vert y-x\Vert ^2\), denoted by \(\text {prox}_{ f}(x):\mathcal {H}\rightarrow \mathcal {H}\). The resolvent of A, denoted by \(J_A : \mathcal {H} \rightrightarrows \mathcal {H}\), is defined as \(J_{A}=(Id+A)^{-1}\) where \(Id: \mathcal {H} \rightarrow \mathcal {H}\), \(Id(x) = x\) for all \(x\in \mathcal {H}\), is the identity operator on \(\mathcal {H}\). Moreover, if A is maximally monotone, then \(J_A: \mathcal {H}\rightarrow \mathcal {H}\) is single-valued and maximally monotone (see Corollary 23.10 in [17]). Notice that \(J_{ \partial f} = (Id + \partial f)^{-1}=\text {prox}_{f}\) (see also Proposition 16.34 in [17]).

The notation we use in this paper was introduced by Fitzpatrick in [18] and has proved to be a useful tool for investigating the maximality of monotone operators using convex analysis techniques (see [17, 19]). For a monotone operator A, we define its associated Fitzpatrick function \(\varphi _{A}: \mathcal {H}\times \mathcal {H}\rightarrow \bar{\mathbb {R}}\) as follows:This function is convex and lower semicontinuous, and it will be an important tool for investigating convergence in this paper.

If A is a maximally monotone operator, then its Fitzpatrick function is proper and satisfies \(\varphi _{A}(x,u) \ge \langle x,u\rangle \) for all \((x,u) \in \mathcal {H}\times \mathcal {H}\), with equality if and only if \((x,u)\in Gr A\). In particular, the subdifferential \(\partial f\) of any convex function \(f\in \Gamma (\mathcal {H})\) is a maximally monotone operator (see [20]), and we have \((\partial f)^{-1} = \partial f^*\). Furthermore, we have the inequality (see [19])where \(f^*\) is the convex conjugate of f.

Before we enter on a detailed analysis of the convergence result, we introduce some definitions of sequences and useful lemmas that will be used several times in the paper. Let \((x_n)_{n\in \mathbb {N}\cup \{0\}}\) be a sequence in \(\mathcal {H}\) and \((\lambda _{k})_{k\in \mathbb {N}\cup \{0\}}\) be a sequence of positive numbers such that \(\sum _{k\in \mathbb {N}\cup \{0\}} \lambda _k = +\infty \). Let \((z_n)_{n\in \mathbb {N}\cup \{0\}}\) be the sequence of weighted averages defined as shown in [2, 4, 5]:The following lemma is the Opial-Passty Lemma, which serves as a key tool for achieving the convergence results in our analysis.

Another key lemma underlying our work is presented below, which establishes the existence of convergence and the summability of sequences satisfying the conditions of the lemma. This lemma has been sourced from [1].

In this section, we will begin by presenting a problem introduced in [4, 5], which can be formulated as follows:

Problem 1: Let \(\mathcal {H}\) be a real Hilbert space, \(A : \mathcal {H}\rightrightarrows \mathcal {H}\) be a maximally monotone operator, \(D : \mathcal {H}\rightarrow \mathcal {H}\) be a monotone and \(\eta ^{-1}\)-Lipschitz continuous operator with \(\eta >0\), \(B:\mathcal {H}\rightarrow \mathcal {H}\) be a monotone and \(\mu ^{-1}\)-Lipschitz continuous operator with \(\mu >0\), and suppose that \(C = zerB\ne \emptyset \). The monotone inclusion problem that we want to solve isSome methods to solve Problem 1 have been already studied in [4, 5] by using Tseng’s algorithm and penalty scheme. The iterative scheme presented below for solving Problem 1 draws inspiration from Tseng’s forward-backward-forward algorithm with extrapolation from the past (see [11, 12, 15]).

Of course, in order to demonstrate the (ergodic) convergence results we need to assume the hypotheses \((H_{fitz})\) for every \(n\in \mathbb {N}\cup \{ 0\}.\)

Prior to establishing the weak ergodic convergence result, we shall prove the following lemma, which serves as a valuable tool for our main outcome.

As observed in the forward-backward-forward penalty scheme discussed in [4, 5], strong monotonicity of the operator A guarantees the strong convergence of the sequence \((x_n)_{n\in \mathbb {N}\cup \{0\}}\). However, it remains to be seen whether this result extends to the forward-backward-forward with extrapolation from the past and the penalty scheme under consideration. The following result provides the necessary clarification.

The minimax optimization problem is a classical problem where the goal is to find a saddle point for a function in two variables. This problem arises in many applications, including game theory [21], control theory [22], and robust optimization [23, 24]. In recent years, there has been a growing interest in the study of minimax problems in modern machine learning, such as Generative Adversarial Networks(GANs) [11], data-driven optimization [25] and furthermore in [26].

In this section, we will consider a class of minimax problems with a convex-concave structure, which can be solved using Tseng’s forward-backward-forward method with extrapolation from the past and penalty scheme. We will present the problem formulation, discuss the properties of the objective function, and introduce some numerical methods for solving the problem.

Let \(f:\mathcal {H}\times \mathcal {G} \rightarrow \mathbb {R}\) be convex-concave and differentiable, where \(f(\cdot , y)\) is convex for all \(y\in \mathcal {G}\) and \(f(x, \cdot )\) is concave for all \(x\in \mathcal {H}\). The Min-Max problem (or minimax problem) is the problem in the form:A saddle point of (20) is a vector \((\bar{x}, \bar{y})\) fulfilling:Let \(F:\mathcal {H}\times \mathcal {G} \rightarrow \mathcal {H}\times \mathcal {G}\) defined by \( F \begin{pmatrix} x \\ y \end{pmatrix} \rightarrow \begin{pmatrix} \nabla _1 f(x,y) \\ -\nabla _2 f(x,y)\end{pmatrix}\), where \(\nabla _1 f \), \(\nabla _2 f\) are the derivative of f with respect to the first and second component, respectively. Then, writing the optimal conditions for the inequalities in (21), we getMoreover, F is monotone and also is Lipschitz continuous (if we impose Lipschitz continuous properties on \(\nabla _1 f, \nabla _2 f\) ), see Proposition 17.10 in [17] and Theorem 35.1 in [27]. In constrained case, the problem in (20) can be written aswhere \(\mathcal {X}\subset \mathcal {H}, \mathcal {Y}\subset \mathcal {G}\) are nonempty closed convex sets and a saddle point \((\bar{x}, \bar{y}) \in \mathcal {X} \times \mathcal {Y}\) satisfies:The characterization of saddle points of (23) follows from the considerations:equivalently,Further we consider more involved minimax problems with constrained sets described by linear equations:where \(\mathcal {Q}\), \(\mathcal {Q}'\) are other real Hilbert spaces, \(K_1: \mathcal {H}\rightarrow \mathcal {Q}, K_2:\mathcal {G}\rightarrow \mathcal {Q}'\) are linear continuous operators with closed ranges such that \(b\in \mathcal {Q}, b'\in \mathcal {Q}'\) and \(\{x\in \mathcal {X} : K_1 (x) = b\}\ne \emptyset \), \(\{y\in \mathcal {Y} : K_2 (y) = b'\}\ne \emptyset \) are nonempty sets. This kind of the minimax constrained problem was studied with plenty of applications, for instance in [25]. In this case, we have the following characteristic of saddle points of (26)Note that \(N_{C_1\cap C_2} = \partial (\delta _{C_1} + \delta _{C_2}) = N_{C_1} + N_{C_2}\), if a constraint qualification is satisfied, for example \( \emptyset \ne C_1 \cap {\text {int}} C_2 \) (see Corollary 16.38 in [17]). ThenWe find the solution ofby considering the functions \(\psi _1:\mathcal {H} \rightarrow \mathbb {R}, \psi _2 : \mathcal {G}\rightarrow \mathbb {R}\) asNamely, the solution of (29) can be obtained by solving the following optimization problem:For every \(x\in \mathcal {H}\) and \(y\in \mathcal {G}\), letTherefore, (28) can be written asDue to the above setting, the problem (28) turns into the monotone inclusion in (7). The iterative pattern in Algorithm 1 can be transformed into for each \(n\ge 0\) as where \(\nabla \psi _1 (x) = K_1^{*} ( K_1 (x) -b)\) and \(\nabla \psi _2 (y) = K_2^{*} ( K_2 (y) -b')\).

Notice that if G is a nonempty closed convex subset of \(\mathcal {H}\), then \(J_{N_{G}} = (Id+N_{G})^{-1} = prox_{\delta _{G}} = proj_G\) (see Example 23.4 in [17]), where \(proj_G\) is the projector (or projection operator) onto G, namely, for all \(x\in \mathcal {H}\), \(proj_G(x)\) is the unique element in G s.t. \(\Vert x - proj_G(x) \Vert := \min _{y\in G} \Vert x - y \Vert \). Therefore, we are able to construct a relevant algorithm for solving the monotone inclusion scheme in (32) (i.e., for solving problem (26)) demonstrated as:

Thus, we can use condition (ii) in (H) (in Section 1) to get the convergent results. We define \(\Psi : \mathcal {H} \times \mathcal {G} \rightarrow \mathbb {R}\),Then, we have (see Proposition 13.27 in [17])From the considerations above, we have:Furthermore, we also haveThus, if we impose for \(i=1,2\)then, it follows thatit is exactly the condition (ii) that we need for convergence in (H).

In this context, we assume the following condition:which is a constraint qualification of our considered problem (see Corollary 16.38 in [17] and (27)-(28)).

Hence, we can propose the ergodic convergence results which follow from Theorem 4 as below.

In this section, we propose forward-backward-forward algorithm with extrapolation from the past and penalty scheme utilized to address the inclusion problem involving the finite sum of the compositions of monotone operators with linear continuous operators. To this end, we begin with the following problem:

Problem 3: Let \(\mathcal {H}\) be a real Hilbert space, \(A : \mathcal {H}\rightrightarrows \mathcal {H}\) be a maximally monotone operator, \(D : \mathcal {H}\rightarrow \mathcal {H}\) be a monotone and \(\nu \)-Lipschitz continuous operator with \(\nu >0\). Let m be strictly positive integer and for any \(i\in \{ 1,\dots ,m \}\), let \(\mathcal {G}_i\) be a real Hilbert space, \(B_i : \mathcal {G}_i \rightrightarrows \mathcal {G}_i\) be a maximally monotone operator, and \(L_i : \mathcal {H}\rightarrow \mathcal {G}_i\) be a nonzero linear continuous operator. Assume that \(B:\mathcal {H}\rightarrow \mathcal {H}\) is a monotone and \(\mu ^{-1}\)-Lipschitz continuous operator with \(\mu >0\), and suppose \(C = zerB\ne \emptyset \). The monotone inclusion problem to solve isThe monotone inclusion problem, Problem 3, can be reformulated into the same form as Problem 1 using the product space approach with a pertinent setting. To address this problem, we work with the product space \(\mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m\), where the inner product and associated norm are defined for every element \((x,v_1,\dots ,v_m)\) by \(\langle (x,v_1,\dots ,v_m), (y,w_1,\dots ,w_m) \rangle = \langle x, y \rangle + \sum _{i=1}^{m} \langle v_i, w_i \rangle \) and \(\Vert (x,v_1,\dots ,v_m)\Vert = \sqrt{\Vert x \Vert ^2 + \sum _{i=1}^{m}\Vert v_i \Vert ^2}\). We proceed to define the operators on the product space \(\mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m\) as follows: for every \((x,v_1,\dots ,v_m), (y,w_1,\dots ,w_m)\) \( \in \mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m\), \(\tilde{A}: \mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m \rightrightarrows \mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m\)\(\tilde{D} : \mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m \rightarrow \mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m\),and \(\tilde{B} : \mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m \rightarrow \mathcal {H} \times \mathcal {G}_1 \times \dots \times \mathcal {G}_m\),Note that the maximal monotonicity of A and \(B_i\), \(i=1,\dots ,m\), implies that the operator \(\tilde{A}\) is also maximally monotone, as stated in Proposition 20.22 and 20.23 of [17]. Moreover, according to Theorem 3.1 in [28], it is possible to demonstrate that the operator \(\tilde{D}\) is monotone and \(\beta \)-Lipschitz continuous where \(\beta = \nu + \sqrt{\sum _{i=1}^{m} \Vert L_i\Vert ^2 }\) (in this context, the monotonicity and Lipschitzian of D is a special case of [4, 28]). Moreover, we also have that \(\tilde{B}\) is monotone and \(\mu ^{-1}\)-Lipschitz continuous withandOne can show (see [4]) that x is a solution to Problem 3 if and only if there exists \(v_1\in \mathcal {G}_1,\dots ,v_m\in \mathcal {G}_m\) such taht \((x,v_1,\dots ,v_m) \in zer(\tilde{A} + \tilde{D} + N_{\tilde{C}})\). On the other hand, when \((x,v_1,\dots ,v_m) \in zer(\tilde{A} + \tilde{D} + N_{\tilde{C}})\), then \(x\in zer(A + \sum _{i=1}^{m} L_i^{*} B_i L_i + D + N_C)\). This means that determining the zeros of \(\tilde{A} + \tilde{D} + N_{\tilde{C}}\) will automatically provide a solution to Problem 3.

By using the identity given in Proposition 23.16 of [17], which provides that for any \((x,v_1,\dots ,v_m)\in \mathcal {H} \times \mathcal {G}_1, \times \dots \times \mathcal {G}_m\) and \(\lambda > 0\), \(J_{\lambda \tilde{A}} (x,v_1,\dots ,v_m) = (J_{\lambda _n A}(x), J_{\lambda B_{1}^{-1}} (v_1),\dots ,J_{\lambda B_{m}^{-1}} (v_m))\), it can be observed that the iterations of Algorithm 1 are given for any \(n\in \mathbb {N}\cup \{0\}\) as follows: This leads to the algorithm below:

To consider the convergence of this iterative scheme, we need the following additional hypotheses, similar to the hypotheses in Section 2 of [4]: \((H_{fitz}^{sum}){\left\{ \begin{array}{ll} (i) &{}A +N_C \;\text {is maximally monotone and} \; zer(A+\sum _{i=1}^{m} L^*B_i L+D+N_C)\ne \emptyset ;\\ (ii) &{}\text {For every } p\in {\text {ran}} N_C, \sum _{n\in \mathbb {N}\cup \{0\}} \lambda _n\beta _n [\sup \limits _{u\in C} \varphi _{B} (u,\frac{p}{\beta _n})-\sigma _C(\frac{p}{\beta _n})] < +\infty ;\\ (iii) &{}(\lambda _n)_{ n\in \mathbb {N}\cup \{0\} } \in \ell ^2 \setminus \ell ^1. \end{array}\right. }\)

The Fitzpatrick function of \(\tilde{B}\) (i.e., \(\varphi _{\tilde{B}}\) ) and the support function of \(\tilde{C}\) (i.e., \(\sigma _{\tilde{C}}\)) can be computed in the same way as demonstrated in Section 2 of [4] for arbitrary elements \((x_1,v_{1},\dots ,v_{m}), (x_1',v_{1}',\dots ,v_{m}')\in \mathcal {H} \times \mathcal {G}_1, \times \dots \times \mathcal {G}_m\). Moreover, the satisfaction of condition (i) in \((H_{fitz}^{sum})\) guarantees that \(\tilde{A} + N_{\tilde{C}}\) is maximally monotone and \(zer(\tilde{A}+\tilde{D}+N_{\tilde{C}})\ne \emptyset \). As a result, we can apply Theorems 4 and 5 to the problem of finding the zeros of \(\tilde{A}+\tilde{D}+N_{\tilde{C}}\). Thus, we can establish the convergence results for the scheme of the sum of monotone operators and linear continuous operators, which are given below.

Problem 4 Let \(\mathcal {H}\) be a real Hilbert space, \(f\in \Gamma (\mathcal {H})\), and \(h:\mathcal {H} \rightarrow \mathbb {R}\) be a convex and differentiable function with \(\nu \)-Lipschitz continous gradient for \(\nu >0\). Let m be a strictly positive integer, and for any \(i = 1,\dots ,m\), let \(\mathcal {G}_i\) be a real Hilbert space, \(g_i\in \Gamma (\mathcal {G}_i)\),In order to solve this problem in our context, we can follow the Problem 3 in Section 5. We know that any element belonging to \(zer(\partial f + \sum _{i=1}^{m} L^*_i \partial g_i L_i + \nabla h + N_C)\) is an optimal solution for (39) if we substitute all of operators withwhere \(B{ isamonotoneand}\mu ^{-1}{} \)-Lipschitz continuous operator (see Proposition 17.10 and Theorem 18.15 in [17]). However, the converse is true only if a suitable qualification condition is satisfied. Necessary conditions, namely that (39) leads to Problem 3 with (37), have been previously given in [4] (for example, see Proposition 4.3 and Remark 4.4 in [28])Note that the strong quasi-relative interior for a convex set S in a real Hilbert space \(\mathcal {H}{} \) is denoted by sqri S and is defined as the set of points x \(\in \) S such that the union of all positive scalar multiples of \((S-x){ isaclosedlinearsubspaceof}\mathcal {H}{} \). Notice that sqri S always contains the interior of S, denoted by int S, but this inclusion can be strict. When \(\mathcal {H}{} \) is finite-dimensional, sqri S coincides with the relative interior of S, denoted by ri S, which is the interior of S with respect to its affine hull. Moreover, the condition in (41) is fulfilled ifAt this point, we are equipped to state the iterative method based on Tseng’s forward-backward-forward algorithm with extrapolation from the past and penalty scheme and its convergent result.

To analyze the convergence theorem, we need to assume the hypotheses similar to those in Section 3 of [4], which are as follows:For the hypothesis \((H^{opt})\), some observations have already been presented in [4], which are as follows:

With the same effort as in Section 5, we may continue and provide the convergence results for Algorithm 4 as shown below.

In this section, we demonstrate the application of Algorithm 4 for solving an image inpainting problem, which involves recovering lost information in an image. We compare the classical Tseng’s type (or the forward-backwards-forward (FBF) algorithm) penalty system, which Boț and Csetnek proposed in [4], with our modified Tseng’s type penalty scheme. Because our algorithm can reduce the redundant computed terms in the typical Tseng’s method (see introduction), then we expect to gain less time consumption in the next numerical experiment. The computations presented in this part were carried out with Python (version 3.7.9) on a Windows desktop computer powered by an Intel(R) Core(TM) i5-8250U processor that operated at speeds between 1.6 GHz and 1.8 GHz, and was equipped with 8.00 GB of RAM. We represent images of size \(M\times N{ asvectors}x\in \mathbb {R}^{\bar{n}},\,{ where}\bar{n} = M\cdot N,\,{ andeachpixeldenotedby}x_{i,j}, 1 \le i \le M, 1 \le j \le N,\,{ takesvaluesintheclosedintervalfrom}0 ({ pureblack}){ to}1 ({ purewhite}).{ Givenanimage}b\in \mathbb {R}^{\bar{n}}{} { withmissingpixels}({ whicharesettoblackinthiscase}),\,{ wedefine}P\in \mathbb {R}^{\bar{n}\times \bar{n}}{} { asthediagonalmatrixwith}P_{i,i}=0{ ifthe}i\)-th pixel in the noisy image \(b{ ismissing},\,{ and}P_{i,i} = 1{ otherwise},\,{ for}i = 1,\dots ,\bar{n} ({ notingthat}\Vert P\Vert =1\)). The original image is reconstructed by solving the following TV-regularized model:The function \(TV_{iso}:\mathbb {R}^{\bar{n}}\rightarrow \mathbb {R}{} \), which we use as our objective function, is defined as the isotropic total variation:It is possible to express the problem presented in (43) as an optimization problem of the form of Problem 4 in (39). This can be achieved by introducing the set \(\mathcal {Y}=\mathbb {R}^{\bar{n}}\times \mathbb {R}^{\bar{n}},\,{ anddefiningthelinearoperator}L:\mathbb {R}^{\bar{n}}\rightarrow \mathcal {Y}{} { as}L(x_{i,j}) = ( L^1 (x_{i,j}),L^2 (x_{i,j}) )\),whereThe operator \(L{ representsadiscretizationofthegradientinthehorizontalandverticaldirections}.{ Itisworthnotingthat}\Vert L\Vert ^2 < 8,\,{ anditsadjoint}L^*: \mathcal {Y}\rightarrow \mathbb {R}^{\bar{n}}{} { isaseasytoimplementas}L\) itself (see [15, 29]). Furthermore, the inner product on \(\mathcal {Y},\,{ givenby}\langle (y,z), (p,q) \rangle = \sum _{i=1}^{M} \sum _{j=1}^{N} (y_{i,j} p_{i,j} + z_{i,j} q_{i,j}),\,{ inducesanormdefinedas}\Vert (y,z)\Vert _{\times } = \sum _{i=1}^{M} \sum _{j=1}^{N} \sqrt{y_{i,j}^2 + z_{i,j}^2}{} { for}(y,z),(p,q) \in \mathcal {Y}.{ Itcanbeshownthat}TV_{iso}(x) = \Vert L(x) \Vert _{\times }{} { forevery}x\in \mathbb {R}^{\bar{n}}.{ Moreover},\,{ byconsideringthefunction}\Psi :\mathbb {R}^{\bar{n}}\rightarrow \mathbb {R}, \Psi (x) = \frac{1}{2} \Vert P(x) - b\Vert ^2\), problem in (43) can be reformulated aswhere \(f: \mathbb {R}^{\bar{n}}\rightarrow \bar{\mathbb {R}}, f = \delta _{[0,1]^{\bar{n}}},\,g_1: \mathcal {Y}\rightarrow \mathbb {R}, g_1(y_1,y_2) = \Vert (y_1,y_2) \Vert _{\times }{} \). The problem given in (44) can be written as Problem 4 (39) when we set \(m=1, L_1=L\), and \(h=0\). It is worth noting that \(\nabla \Psi (x) = P(P(x)-b) = P(x-b)\) for all \(x\in \mathbb {R}^{\bar{n}}\), which makes \(\nabla \Psi \) Lipschitz continuous with a Lipschitz constant of \(\mu =1\). Therefore, the iterative scheme in Algorithm 4 can be written as follows for every \(n\ge 0\) in this particular case:To implement this iterative method, we need the following formulas:andwhere \(S = \{ (p,q) \in \mathcal {Y} : \max _{\begin{array}{c} 1\le i \le M \\ 1 \le j \le N \end{array}} \sqrt{p_{i,j}^2 + q_{i,j}^2} \le 1 \}\). The projection operator \(proj_{S} : \mathcal {Y} \rightarrow S\) is defined viaThe quality of the reconstructed images was compared using the Improvement in Signal-to-Noise Ratio (ISNR), defined as follows:where x, b and \(x_n\) denote the original, the image with missing pixels and the recovered image at iteration n, respectively.

Bild vergrößern

Bild vergrößern

Bild vergrößern

We evaluated the performance of the algorithm on a \(256\times 256\) pixel image of the Pisa Tower, using the parameters \(\lambda _n = 0.9 \cdot n^{-0.75}\) (see [4]), \(\lambda _n = 0.9 \cdot 2^{-1}\cdot n^{-0.75}\) and \(\beta _n = n^{0.75}\) for all \(n \in \mathbb {N}\). The original image, as well as an image with \(80\%\) randomly blacked-out pixels, were used in the test. Figure 1 displays the original image, the noisy image, the non-averaged reconstructed image \(x_n\), and the averaged reconstructed image \(z_n\) after 2000 iterations using both the Forward-Backward-Forward (FBF) in the penalty scheme with \(\lambda _n = 0.9 \cdot n^{-0.75}\), FBF in penalty scheme with \(\lambda _n = 0.9 \cdot 2^{-1} \cdot n^{-0.75}\) and Forward-Backward-Forward with Extrapolation from the Past(FBF-EP) in penalty scheme with \(\lambda _n = 0.9 \cdot 2^{-1} \cdot n^{-0.75}\) . Note that \(\lambda _n = 0.9 \cdot n^{-0.75}\) can not be used for FBF-EP in penalty scheme because there is no theorem to support its convergence. In addition, since the parameters \(\lambda _n\) and \(\beta _n\) play a role in the methods as the stepsize of the algorithm, then we decided to choose these parameters, which have value close to the upper bound of their conditions (namely, either \(\limsup _{n\rightarrow +\infty } \left( \frac{\lambda _n \beta _n}{\mu } + \lambda _n \beta \right) < 1\) or \(\limsup _{n\rightarrow +\infty } \left( \frac{\lambda _n \beta _n}{\mu } + \lambda _n \beta \right) < \frac{1}{2}\)).

Figures 2 and 3 depict the evolution of the ISNR values for both the averaged and non-averaged reconstructed images using FBF and FBF-EP algorithms (in both two values of \(\lambda _n\) in FBF, respectively). The theoretical outcomes concerning the sequences involved in Theorem 8 are illustrated in the figure, indicating that the averaged sequence exhibits better convergence properties than the non-averaged sequence. We notice that the behavior of ISNR values in both algorithms carries out similarly when we use the same value of \(\lambda _n\) and the ISNR values of averaged FBF-EP have a bit outperform at 2000 iteration. Table 1 reveals that the FBF-EP approach produced the averaged reconstructed image with an ISNR value of 11.39179, while it was 11.36461 for the averaged case of the FBF with \(\lambda _n =0.9 \cdot 2^{-1} \cdot n^{-0.75}\) and 11.41243 for the averaged case of the FBF with \(\lambda _n =0.9 \cdot n^{-0.75}\). However, the non-averaged reconstructed image using the FBF-EP method had the lowest ISNR value of 8.77024. Furthermore, the FBF-EP method was faster than the FBF method by around 13 seconds (compared with both two various of \(\lambda _n\) in FBF), indicating that it can offer time-saving benefits in image reconstruction.