Forward–Partial Inverse–Forward Splitting for Solving Monotone Inclusions

Abstract

In this paper, we provide a splitting method for finding a zero of the sum of a maximally monotone operator, a Lipschitzian monotone operator, and a normal cone to a closed vector subspace of a real Hilbert space. The problem is characterised by a simpler monotone inclusion involving only two operators: the partial inverse of the maximally monotone operator with respect to the vector subspace and a suitable Lipschitzian monotone operator. By applying the Tseng’s method in this context, we obtain a fully split algorithm that exploits the whole structure of the original problem and generalises partial inverse and Tseng’s methods. Connections with other methods available in the literature are provided, and the flexibility of our setting is illustrated via applications to some inclusions involving $m$ maximally monotone operators, to primal-dual composite monotone inclusions, and to zero-sum games.

1 Introduction

This paper is concerned with the numerical resolution of the problem of finding a zero of the sum of a set-valued, maximally monotone operator, a Lipschitzian monotone operator, and a normal cone to a closed vector subspace of a real Hilbert space. This problem arises in a wide range of areas such as optimisation [1, 2], variational inequalities [3–5], monotone operator theory [6–9], partial differential equations [3, 10, 11], economics [12, 13], signal and image processing [14–16], evolution inclusions [17, 18], traffic theory [19, 20], and game theory [21], among others.

When the single-valued operator is zero, the problem is solved in [9] via the method of partial inverses. On the other hand, when the vector subspace is the whole Hilbert space, the normal cone is zero and our problem is reduced to finding a zero of the sum of two monotone operators. In this case, the problem is solved in [22] via the forward–backward–forward splitting or Tseng’s method (see also [23] and the references therein). In addition, in the case when the single-valued operator is cocoercive, the problem is solved in [24].

In the general case, several algorithms are available in the literature for solving our problem, but any of them exploits its intrinsic structure. The Tseng’s method [22] can be applied to the general case, but it needs to compute the resolvent of the sum of the set-valued operator and the normal cone, which is not always easy to implement. It is preferable to activate both operators separately. Some ergodic approaches for solving this problem can be found in [25]. A disadvantage of these methods is the presence of vanishing parameters, which usually leads to numerical instabilities. The algorithms proposed in [9, 23, 26] permit us to find a zero of the sum of finitely many maximally monotone operators by activating them independently, without considering vanishing parameters. However, these methods need the computation of the resolvent of the single-valued operator, which is not easy to compute in general. An algorithm proposed in [27] overcomes this difficulty by explicitly activating the single-valued operator. However, this method does not take advantage of the vector subspace involved. Indeed, by using product space techniques, the method in [27] needs to store additional auxiliary variables at each iteration, which can be difficult in high-dimensional problems.

In this paper, we propose a fully split method for finding a zero of the sum of the three monotone operators detailed before, by exploiting each of their intrinsic properties. The algorithm computes, at each iteration, explicit steps on the single-valued operator and the resolvent of the partial inverse of the set-valued operator with respect to the closed vector subspace [9]. This resolvent has an explicit expression in several cases, and it reduces to a Douglas–Rachford step [7, 28] in a particular instance. In this case, our method can be perceived as a forward–Douglas–Rachford–forward splitting, which generalises partial inverse and Tseng’s methods when the single-valued operator is zero and the vector subspace is the whole Hilbert space, respectively. We also provide connections with other methods in the literature, and we illustrate the flexibility of our framework via some applications to inclusions involving $m$ maximally monotone operators, to primal-dual composite monotone inclusions, and to zero-sum games. In the application to primal-dual inclusions, we introduce a new operation between set-valued operators, called partial sum with respect to a closed vector subspace, which preserves monotonicity and takes a central role in the problem and algorithm. On the other hand, in continuous zero-sum games, we provide an interesting splitting algorithm for calculating a Nash equilibrium that avoids the computation of the projection onto mixed strategy spaces in infinite dimensions by performing simpler projections alternately. These applications enlighten the flexibility and usefulness of the vector space setting, which appears naturally in a different form in each instance.

The paper is organised as follows. In Sect. 2, we provide the notation and some preliminaries. We also obtain a relaxed version of Tseng’s method [22], which is interesting in its own right. In Sect. 3, a characterisation of our problem in terms of two appropriate monotone operators is given and a method for solving this problem is derived from the relaxed version of Tseng’s algorithm. Moreover, we provide connections with other methods in the literature. Finally, in Sect. 4, we apply our method to the problem of finding a zero of a sum of $m$ maximally monotone operators and a Lipschitzian monotone operator, to a primal-dual composite monotone inclusion, and to continuous zero-sum games. The methods derived in each instance generalise and improve available algorithms in the literature.

2 Notation and Preliminaries

Throughout this paper, $\mathcal {H}$ is a real Hilbert space with scalar product denoted by $\left\langle {\cdot }\mid {\cdot } \right\rangle$ and associated norm $\Vert \cdot \Vert$. The symbols $\rightharpoonup$ and $\rightarrow$ denote, respectively, weak and strong convergence, and $\mathrm{Id }$ denotes the identity operator. The indicator function of a subset $C$ of $\mathcal {H}$ is $\iota _C$, which takes the value $0$ in $C$ and $+\infty$ in $\mathcal {H}\setminus C$. If $C$ is non-empty, closed, and convex, then the projection of $x$ onto $C$, denoted by $P_Cx$, is the unique point in $\mathrm{Argmin }_{y\in C}\Vert x-y\Vert$, and the normal cone to $C$ is the maximally monotone operator

$$\begin{aligned} N_C:\mathcal {H}\rightrightarrows \mathcal {H}: x\mapsto {\left\{ \begin{array}{ll} \big \{{u\in \mathcal {H}} : {(\forall y\in C)\,\,\left\langle {y-x}\mid {u} \right\rangle \le 0}\big \},\quad &{}\mathrm{if\, }x\in C;\\ {\varnothing },&{}\mathrm{otherwise}. \end{array}\right. } \end{aligned}$$

(1)

An operator $T:\mathcal {H}\rightarrow \mathcal {H}$ is $\beta$–cocoercive for some $\beta \in \,\big ]0,+\infty \big [$ iff, for every $x\in \mathcal {H}$ and $y\in \mathcal {H}$, $\left\langle {x-y}\mid {Tx-Ty} \right\rangle \ge \beta \Vert Tx-Ty\Vert ^2$, it is $\chi$-Lipschitzian iff, for every $x,y\in \mathcal {H}$, $\Vert Tx-Ty\Vert \le \chi \Vert x-y\Vert$, it is non-expansive iff it is $1$-Lipschitzian, and the set of fixed points of $T$ is given by $\mathrm{Fix }T$.

We denote by $\mathrm{gra }A=\big \{{(x,u)\in \mathcal {H}\times \mathcal {H}} : {u\in Ax}\big \}$ the graph of $A:\mathcal {H}\rightrightarrows {\mathcal {H}}$, by $J_A=(\mathrm{Id }+A)^{-1}$ its resolvent, by $\mathrm{dom }A=\big \{{x\in \mathcal {H}} : {Ax\ne {\varnothing }}\big \}$ its domain, and by $\mathrm{zer }A=\big \{{x\in \mathcal {H}} : {0\in Ax}\big \}$ its set of zeros. If $A$ is monotone, i.e., for every $(x,u)$ and $(y,v)$ in $\mathrm{gra }A$, $\left\langle {x-y}\mid {u-v} \right\rangle \ge 0$, then $J_A$ is a single-valued, non-expansive operator. In addition, $A$ is maximally monotone iff $\mathrm{dom }J_A=\mathcal {H}$. Let $A:\mathcal {H}\rightrightarrows {\mathcal {H}}$ be maximally monotone. The reflection operator of $A$ is $R_A=2J_A-\mathrm{Id }$, which is non-expansive. The partial inverse of $A$ with respect to a vector subspace $V$ of $\mathcal {H}$, denoted by $A_V$, is defined by

$$\begin{aligned} (\forall (x,y)\in \mathcal {H}^2)\quad y\in A_Vx\quad \Leftrightarrow \quad (P_Vy+P_{V^{\perp }}x)\in A(P_Vx+P_{V^{\perp }}y). \end{aligned}$$

(2)

Note that $A_{\mathcal {H}}=A$ and $A_{\{0\}}=A^{-1}$. The following properties of the partial inverse will be useful throughout this paper.

Proposition 2.1

Let $A:\mathcal {H}\rightrightarrows {\mathcal {H}}$ be a set-valued operator and let $V$ be a closed vector subspace of $\mathcal {H}$. Then, $(A_V)^{-1}=(A^{-1})_V=A_{V^{\perp }}$ and $P_V(A+N_V)^{-1}P_V=P_V(A_{V^{\perp }}+N_V)P_V$.

Proof

Let $(x,u)\in \mathcal {H}^2$. We have from (2) that

$$\begin{aligned} u\in (A_V)^{-1}x\quad&\Leftrightarrow \quad x\in A_Vu\nonumber \\&\Leftrightarrow \quad P_Vx+P_{V^{\perp }}u\in A(P_Vu+P_{V^{\perp }}x)\end{aligned}$$

(3)

$$\begin{aligned}&\Leftrightarrow \quad P_Vu+P_{V^{\perp }}x\in A^{-1}(P_Vx+P_{V^{\perp }}u)\nonumber \\&\Leftrightarrow \quad u\in (A^{-1})_Vx. \end{aligned}$$

(4)

On the other hand, it follows from (3) and (2) that $u\in (A_V)^{-1}x$ is equivalent to $u\in A_{V^{\perp }}x$. For the second identity, we deduce from (2) that

$$\begin{aligned} u\in P_V(A+N_V)^{-1}(P_Vx) \quad&\Leftrightarrow \quad (u\in V)\quad u\in (A+N_V)^{-1}(P_Vx)\\&\Leftrightarrow \quad (u\in V)\quad P_Vx\in Au+N_Vu\\&\Leftrightarrow \quad (u\in V)(\exists \,y\in V^{\perp })\quad P_Vx-y\in Au\\&\Leftrightarrow \quad (u\in V)(\exists \,y\in V^{\perp })\quad u-y\in A_{V^{\perp }}(P_Vx)\\&\Leftrightarrow \quad (u\in V)\quad u\in (A_{V^{\perp }}+N_V)(P_Vx)\\&\Leftrightarrow \quad u\in P_V(A_{V^{\perp }}+N_V)(P_Vx), \end{aligned}$$

which yields the result. $\square$

The following result is a relaxed version of the methods proposed in [22, 23, 29].

Proposition 2.2

Let $\eta \in \,\big ]0,+\infty \big [$, let ${\mathcal {A}}:\mathcal {H}\rightrightarrows {\mathcal {H}}$ be maximally monotone, and let ${\mathcal {B}}:\mathcal {H}\rightarrow \mathcal {H}$ be monotone and $\eta$–Lipschitzian such that $\mathrm{zer }({\mathcal {A}}+{\mathcal {B}})\ne \varnothing$. Moreover, let $z_0\in \mathcal {H}$, let $\varepsilon \in \big ]0,\max \{1,1/2\eta \}\big [$, let $(\delta _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,(1/\eta )-\varepsilon \right]$, let $(\lambda _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,1\right]$, and iterate

$$\begin{aligned} (\forall n\in \mathbb {N})\quad&\left\lfloor \begin{array}{l} r_n:=z_n-\delta _n{\mathcal {B}}z_n\\ s_n:=J_{\delta _n{\mathcal {A}}}r_n\\ t_n:=s_n-\delta _n{\mathcal {B}}s_n\\ z_{n+1}:=z_n+\lambda _n(t_n-r_n). \end{array} \right. \end{aligned}$$

(5)

Then, $z_n\rightharpoonup \bar{z}$ for some $\bar{z}\in \mathrm{zer }({\mathcal {A}}+{\mathcal {B}})$ and $z_{n+1}-z_n\rightarrow 0$.

Proof

First note that (5) yields

$$\begin{aligned} (\forall n\in \mathbb {N})\quad \delta _n^{-1}(r_n-s_n)\in {\mathcal {A}}s_n. \end{aligned}$$

(6)

Let $z\in \mathrm{zer }({\mathcal {A}}+{\mathcal {B}})$ and fix $n\in \mathbb {N}$. We have

$$\begin{aligned} \Vert z_{n+1}-z\Vert ^2\!&=\!\Vert (1-\lambda _n)(z_n-z)+\lambda _n(z_n-z+t_n- r_n)\Vert ^2\nonumber \\&=\!(1\!-\!\lambda _n)\Vert z_n\!-\!z\Vert ^2+\lambda _n\Vert z_n-z+t_n- r_n\Vert ^2-\lambda _n(1-\lambda _n)\Vert t_n-r_n\Vert ^2\nonumber \\&=\!(1-\lambda _n)\Vert z_n-z\Vert ^2+\lambda _n\Vert s_n-\delta _n({\mathcal {B}}s_n- {\mathcal {B}}z_n)-z\Vert ^2\nonumber \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad -\lambda _n(1-\lambda _n)\Vert t_n-r_n\Vert ^2\nonumber \\&\le \!(1\!-\!\lambda _n)\Vert z_n\!-\!z\Vert ^2\!\!+\!\lambda _n \big (\Vert z_n\!-\!z\Vert ^2\!\!+\! \delta _n^2\Vert {\mathcal {B}}s_n\!-\!{\mathcal {B}}z_n\Vert ^2\!\!-\!\Vert s_n\!-\!z_n\Vert ^2\big )\nonumber \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad -\lambda _n(1\!-\!\lambda _n)\Vert t_n\!-\!r_n\Vert ^2\nonumber \\&\le \Vert z_n-z\Vert ^2-\varepsilon \big (1\!-\!(\delta _n\eta )^2\big )\Vert s_n\!-\!z_n\Vert ^2 -\lambda _n(1-\lambda _n)\Vert t_n\!-\!r_n\Vert ^2,\quad \end{aligned}$$

(7)

where the first and third equality follow from (5), the second equality is a consequence of [30, Corollary 2.14], the inequality in the fourth line is obtained from [22, Lemma 3.1], and the last inequality follows from the Lipschitz property on ${\mathcal {B}}$, $\sup _{n\in \mathbb {N}}\delta _n<1/\eta$, and $\inf _{n\in \mathbb {N}}\lambda _n\ge \varepsilon$. Hence, since $\delta _n<1/\eta$ and $0<\lambda _n\le 1$, we obtain $\Vert z_{n+1}-z\Vert ^2\le \Vert z_n-z\Vert ^2$, which yields the boundedness of the sequence $(z_k)_{k\in \mathbb {N}}$. Moreover, we deduce from (7) and [23, Lemma 2.1] that $(\Vert s_k-z_k\Vert ^2)_{k\in \mathbb {N}}$ and $(\Vert t_k-r_k\Vert ^2)_{k\in \mathbb {N}}$ are summable and, in particular,

$$\begin{aligned} s_k-z_k\rightarrow 0\quad \mathrm{and}\quad t_k-r_k\rightarrow 0, \end{aligned}$$

(8)

which yields $z_{k+1}-z_k=\lambda _k(t_k-r_k)\rightarrow 0$. By setting, for every $k\in \mathbb {N}$, $u_k:=\delta _k^{-1}(r_k-t_k)$, it follows from (5), (6), and (8) that $u_k=\delta _k^{-1}(r_k-s_k)+{\mathcal {B}}s_k\in ({\mathcal {A}}+{\mathcal {B}})s_k$ and $u_k\rightarrow 0$. Hence, for any weak cluster point of $(z_k)_{k\in \mathbb {N}}$, say $z_{k_\ell }\rightharpoonup w$, (8) yields $s_{k_\ell }\rightharpoonup w$, $u_{k_\ell }\rightarrow 0$, and $(s_{k_\ell },u_{k_\ell })\in \mathrm{gra }({\mathcal {A}}+{\mathcal {B}})$. Since ${\mathcal {B}}$ is monotone and continuous, it is maximally monotone [30, Corollary 20.25]. Moreover, since $\mathrm{dom }{\mathcal {B}}=\mathcal {H}$, we deduce from [30, Corollary 24.4(i)] that ${\mathcal {A}}+{\mathcal {B}}$ is maximally monotone and, hence, its graph is sequentially closed in $\mathcal {H}^\mathrm{weak}\times \mathcal {H}^\mathrm{strong}$ [30, Proposition 20.33(ii)], which yields $w\in \mathrm{zer }({\mathcal {A}}+{\mathcal {B}})$. Finally, from [23, Lemma 2.2], we deduce that there exists $\bar{z}\in \mathrm{zer }({\mathcal {A}}+{\mathcal {B}})$ such that $z_n\rightharpoonup \bar{z}$. $\square$

Remark 2.1

As in [23, Theorem 2.5], absolutely summable errors can be incorporated in each step of the algorithm in (5). However, for ease of presentation, we only provide the error-free version.

3 Forward–Partial Inverse–Forward Splitting

We aim at solving the following problem.

Problem 3.1

Let $\mathcal {H}$ be a real Hilbert space, and let $V$ be a closed vector subspace of $\mathcal {H}$. Let $A:\mathcal {H}\rightrightarrows {\mathcal {H}}$ be a maximally monotone operator, and let $B: \mathcal {H}\rightarrow \mathcal {H}$ be monotone and $\chi$–Lipschitzian for some $\chi \in \,\big ]0,+\infty \big [$. The problem is to

$$\begin{aligned} \mathrm{find}\;\;x\in \mathcal {H}\quad \mathrm{such}\, \mathrm{that}\quad 0\in Ax+Bx+N_Vx, \end{aligned}$$

(9)

under the assumption $Z:=\mathrm{zer }(A+B+N_V)\ne \varnothing$.

In Problem 3.1, the operator $N_V$ is separated from $A$ in order to exploit the intrinsic structure of each operator. Indeed, the proposed method and its variants activate separately each constituent of the inclusion, as we will see in Sect. 3.2. In Sect. 4, we justify the importance of the vector subspace framework via some applications, in which this setting appears naturally. In this section, we study a characterisation of the solutions to Problem 3.1, we provide our algorithm, and we prove its convergence to a solution to Problem 3.1.

3.1 Characterisation

The following result provides a characterisation of the solutions to Problem 3.1, in terms of two suitable monotone operators.

Proposition 3.1

In the context of Problem 3.1, let $\gamma \in \,\big ]0,+\infty \big [$ and define

$$\begin{aligned} {\mathcal {A}}_{\gamma }:=(\gamma A)_V:\mathcal {H}\rightrightarrows {\mathcal {H}}\quad \mathrm{and}\quad {\mathcal {B}}_{\gamma }:=\gamma P_V\circ B\circ P_V:\mathcal {H}\rightarrow V. \end{aligned}$$

(10)

Then, the following hold:

• (i) ${\mathcal {A}}_{\gamma }$ is maximally monotone and, for every $\delta \in \,\big ]0,+\infty \big [$ and $x\in \mathcal {H}$, there exist $p$ and $q$ in $\mathcal {H}$ such that $x=p+\gamma q$, $J_{\delta {\mathcal {A}}_{\gamma }}x=P_Vp+\gamma P_{V^{\perp }}q$, and

  $$\begin{aligned} \frac{P_Vq}{\delta }+P_{V^{\perp }}q\in A\left( P_Vp+\frac{P_{V^{\perp }}p}{\delta }\right) . \end{aligned}$$

  (11)

  In particular, $J_{{\mathcal {A}}_{\gamma }}=2P_VJ_{\gamma A}-J_{\gamma A}+\mathrm{Id }-P_V=(\mathrm{Id }+R_{N_V}R_{\gamma A})/2$.

• (ii) ${\mathcal {B}}_{\gamma }$ is monotone and $\gamma \chi$–Lipschitzian.

• (iii) Let $x\in \mathcal {H}$. Then, $x$ is a solution to Problem 3.1 if and only if $x\in V$ and

  $$\begin{aligned} \big (\exists \,y\!\in \! V^{\perp }\cap (Ax\!+\!Bx)\big )\,\,\mathrm{such}\,\mathrm{that}\,\,\, x\!+\!\gamma (y\!-\!P_{V^{\perp }}Bx)\in \mathrm{zer }({\mathcal {A}}_{\gamma }\!+\!{\mathcal {B}}_{\gamma }).\quad \end{aligned}$$

  (12)

• (iv) $Z=P_V\big (\mathrm{zer }({\mathcal {A}}_{\gamma }+{\mathcal {B}}_{\gamma })\big )$.

Proof

• (i): Since $\gamma A$ is maximally monotone, ${\mathcal {A}}_{\gamma }$ inherits this property [9, Proposition 2.1]. In addition, for every $(r,x)\in \mathcal {H}^2$ and $\delta \in \,\big ]0,+\infty \big [$, it follows from (2) that

  $$\begin{aligned} r=J_{\delta {\mathcal {A}}_{\gamma }}x&\Leftrightarrow \,\, \frac{x-r}{\delta }\in {\mathcal {A}}_{\gamma }r\nonumber \\&\Leftrightarrow \,\, \frac{P_V(x-r)}{\delta }+P_{V^{\perp }}r\in \gamma A\left( P_Vr+\frac{P_{V^{\perp }}(x-r)}{\delta } \right) \nonumber \\&\Leftrightarrow \,\, \frac{P_V(x-r)}{\gamma \delta }+\frac{P_{V^{\perp }}r}{\gamma }\in A\left( P_Vr+\frac{P_{V^{\perp }}(x-r)}{\delta } \right) . \end{aligned}$$

  (13)

  Hence, by taking $p:=P_{V^{\perp }}(x-r)+P_Vr$ and $q:=(P_V(x-r)+P_{V^{\perp }}r)/\gamma$, we have $p+\gamma q=(x-r)+r=x$, $P_Vp+\gamma P_{V^{\perp }}q=r=J_{\delta {\mathcal {A}}_{\gamma }}x$, and (11). Now, in the particular case when $\delta =1$, (11) reduces to $p=J_{\gamma A}(p+\gamma q)=J_{\gamma A}x$ and, hence,

  $$\begin{aligned} J_{{\mathcal {A}}_{\gamma }}x&=P_V(J_{\gamma A}x)+P_{V^{\perp }} (x-J_{\gamma A}x)\nonumber \\&=2P_VJ_{\gamma A}x-J_{\gamma A}x+x-P_Vx\nonumber \\&=\frac{1}{2}\left( x+2P_V(2J_{\gamma A}x-x)-2J_{\gamma A}x+x\right) \nonumber \\&=\frac{1}{2}\left( x+R_{N_V}R_{\gamma A}x\right) . \end{aligned}$$

  (14)

• (ii): Let $(x,y)\in \mathcal {H}^2$. We have from (10) the monotonicity of $B$, the linearity of $P_V$, and $P_V^*=P_V$ that $\left\langle {x-y}\mid {{\mathcal {B}}_{\gamma }x-{\mathcal {B}}_{\gamma }y} \right\rangle \!=\!\gamma \left\langle { P_Vx-P_V y}\mid {B(P_Vx)-B(P_Vy)} \right\rangle \ge 0$, and from the Lipschitzian property on $B$ and (10), we obtain $\Vert {\mathcal {B}}_{\gamma }x-{\mathcal {B}}_{\gamma } y\Vert \le \gamma \Vert B(P_Vx)-B(P_Vy)\Vert \le \gamma \chi \Vert P_Vx-P_Vy\Vert \le \gamma \chi \Vert x- y\Vert$. (iii): Let $x\in \mathcal {H}$ be a solution to Problem 3.1. We have $x\in V$, and there exists $y\in V^{\perp }=N_Vx$ such that $y\in Ax+Bx$. Since $B$ is single valued and $P_V$ is linear, it follows from (2) that

  $$\begin{aligned} y\in Ax+Bx\quad&\Leftrightarrow \quad \gamma y-\gamma Bx\in \gamma Ax\nonumber \\&\Leftrightarrow \quad -\gamma P_V(Bx) \in (\gamma A)_V\big (x+\gamma (y-P_{V^{\perp }}Bx)\big )\nonumber \\&\Leftrightarrow \quad 0\in (\gamma A)_V(x+\gamma (y-P_{V^{\perp }}Bx))\nonumber \\&\quad +\gamma P_V\big (B\big (P_V(x+\gamma (y-P_{V^{\perp }}Bx))\big )\big )\nonumber \\&\Leftrightarrow \quad x+\gamma (y-P_{V^{\perp }}Bx)\in \mathrm{zer }({\mathcal {A}}_{\gamma }+{\mathcal {B}}_{\gamma }), \end{aligned}$$

  (15)

  which yields the result. (iv): Direct from (iii).$\square$

3.2 Algorithm and Convergence

In the following result, we propose our algorithm and we prove its convergence to a solution to Problem 3.1. Since Proposition 3.1 asserts that Problem 3.1 can be written as a monotone inclusion involving a maximally monotone operator and a single-valued Lipschitzian monotone operator, our method is a consequence of Proposition 2.2 applied to this context.

Algorithm 3.1

In the context of Problem 3.1, let $\gamma \in \,\big ]0,+\infty \big [$, let $\varepsilon \in \big ]0,\max \{1,1/(2\gamma \chi )\}\big [$, let $(\delta _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,1/(\gamma \chi )-\varepsilon \right]$, let $(\lambda _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,1\right]$, let $x_0\in V$, let $y_0\in V^{\perp }$, and for every $n\in \mathbb {N}$,

$$\begin{aligned} \mathrm{Step}\,1.\,&\text { find } (p_n,q_n)\in \mathcal {H}^2\,\text { such that } x_n-\delta _n\gamma P_VBx_n+\gamma y_n=p_n+\gamma q_n\nonumber \\&\text {and } \frac{P_Vq_n}{\delta _n}+P_{V^{\perp }}q_n\in A\Big (P_Vp_n+\frac{P_{V^{\perp }}p_n}{\delta _n}\Big ).\nonumber \\ \mathrm{Step}\,2.\,&\text {set } x_{n+1}:=x_n+\lambda _n(P_Vp_n+\delta _n\gamma P_V(Bx_n-BP_Vp_n)-x_n)\,\,\nonumber \\&\text {and } y_{n+1}:=y_n+\lambda _n(P_{V^{\perp }}q_n-y_n).\, \text {Go to Step }1. \end{aligned}$$

(16)

Theorem 3.1

Let $(x_n)_{n\in \mathbb {N}}$ and $(y_n)_{n\in \mathbb {N}}$ be the sequences generated by Algorithm 3.1. Then $(x_n)_{n\in \mathbb {N}}$ and $(y_n)_{n\in \mathbb {N}}$ are in $V$ and $V^{\perp }$, respectively, $x_n\rightharpoonup \overline{x}$ and $y_n\rightharpoonup \overline{y}$ for some solution $\overline{x}\in \mathrm{zer }(A+B+N_V)$ and $\overline{y}\in V^{\perp }\cap (A\overline{x}+P_VB\overline{x})$, $x_{n+1}-x_n\rightarrow 0\,$, and $\,y_{n+1}-y_n\rightarrow 0$.

Proof

Since $x_0\in V$ and $y_0\in V^{\perp }$, (16) yields $(x_n)_{n\in \mathbb {N}}\subset V$ and $(y_n)_{n\in \mathbb {N}}\subset V^{\perp }$. Thus, for every $n\in \mathbb {N}$, it follows from (16) and Proposition 3.1(i) that

$$\begin{aligned} P_Vp_n+\gamma P_{V^{\perp }}q_n=J_{ \delta _n(\gamma A)_V}(x_n+\gamma y_n-\delta _n\gamma P_VBx_n). \end{aligned}$$

(17)

For every $n\in \mathbb {N}$, denote $z_n:=x_n+\gamma y_n$ and

$$\begin{aligned} s_n:&= J_{\delta _n(\gamma A)_V}(x_n+\gamma y_n-\delta _n\gamma P_VBx_n)=J_{\delta _n{\mathcal {A}}_{\gamma }}(z_n-\delta _n\gamma P_VBP_Vz_n)\nonumber \\&= J_{\delta _n{\mathcal {A}}_{\gamma }}(z_n-\delta _n{\mathcal {B}}_{ \gamma }z_n). \end{aligned}$$

(18)

Hence, it follows from (17) that $P_Vp_n=P_Vs_n$, $\gamma P_{V^{\perp }}q_n=P_{V^{\perp }}s_n$, and, from (16), we obtain

$$\begin{aligned} x_{n+1}&= x_n+\lambda _n (P_Vs_n+\delta _n\gamma P_V(Bx_n-BP_Vs_n)-x_n)\quad \mathrm{and}\quad \nonumber \\ \gamma y_{n+1}&= \gamma y_n+\lambda _n ( P_{V^{\perp }}s_n-\gamma y_n). \end{aligned}$$

(19)

By adding the latter equations, we deduce that the algorithm described in (16) can be written as

$$\begin{aligned} (\forall n\in \mathbb {N})\quad&\left\lfloor \begin{array}{l} r_n:=z_n-\delta _n{\mathcal {B}}_{\gamma }z_n\\ s_n=J_{\delta _n{\mathcal {A}}_{\gamma }}r_n\\ t_n:=s_n-\delta _n{\mathcal {B}}_{\gamma }s_n\\ z_{n+1}=z_n+ \lambda _n (t_n-r_n), \end{array} \right. \end{aligned}$$

(20)

which is a particular instance of (5) when ${\mathcal {B}}={\mathcal {B}}_{\gamma }$ and ${\mathcal {A}}={\mathcal {A}}_{\gamma }$. Therefore, it follows from Proposition 3.1 (i) & (ii) and Proposition 2.2 that $z_n\rightharpoonup \overline{z}\in \mathrm{zer }({\mathcal {A}}_{\gamma }+{\mathcal {B}}_{\gamma })$ and $z_{n+1}-z_n\rightarrow 0$. By defining $\overline{x}:=P_V\overline{z}$ and $\overline{y}:=P_{V^{\perp }}\overline{z}/\gamma$, the results follow from Proposition 3.1 and Proposition 2.2. $\square$

Remark 3.1

• (i) The Tseng’s method allows for errors in the computations of the operators involved [23, 29]. In our algorithm, these inexactitudes have not been considered for simplicity.

• (ii) In the particular case when $\lambda _n\equiv 1$ and $B\equiv 0$ ($\chi =0$), Algorithm 3.1 reduces to the classical partial inverse method [9] for finding $x\in V$ such that there exists $y\in V^{\perp }$ satisfying $y\in Ax$.

• (iii) Under further assumptions on the operators ${\mathcal {A}}_{\gamma }$ and/or ${\mathcal {B}}_{\gamma }$, e.g., as demi-regularity (see [31, Definition 2.3&Proposition 2.4]), strong convergence can be achieved. In particular, under the assumptions of Proposition 4.2 below, the strong monotonicity of ${\mathcal {A}}_{\gamma }$ can be guaranteed, and by following the proof in [23, Theorem 2.5 (iii)], we obtain strong convergence of the iterates.

The sequence $(\delta _n)_{n\in \mathbb {N}}$ in Algorithm 3.1 can be manipulated in order to accelerate the convergence. However, as in [9], Step 1 in Algorithm 3.1 is not always easy to compute. The following results show us a particular case of our method, in which Step 1 can be obtained explicitly when the resolvent of $A$ is computable. The method can be seen as a forward–Douglas–Rachford–forward splitting.

Corollary 3.1

In the setting of Problem 3.1, let $\gamma \in \big ]0,1/\chi \big [$, let $\varepsilon \in \big ]0,1\big [$, let $(\lambda _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,1\right]$, let $z_0\in \mathcal {H}$, and iterate, for every $n\in \mathbb {N}$,

$$\begin{aligned}&\left\lfloor \begin{array}{l} r_n:=z_n-\gamma P_V BP_Vz_n\\ p_n:=J_{\gamma A}r_n\\ s_n:=2P_Vp_n-p_n+r_n-P_Vr_n\\ t_n:=s_n-\gamma P_V BP_Vs_n\\ z_{n+1}:=z_n+\lambda _n (t_n-r_n). \end{array} \right. \end{aligned}$$

(21)

Then, by setting, for every $n\in \mathbb {N}$, $x_n:=P_Vz_n$ and $y_n:=P_{V^{\perp }}z_n/\gamma$, we have $x_n\rightharpoonup \bar{x}$ and $y_n\rightharpoonup \bar{y}$ for some $\overline{x}\!\in \!\mathrm{zer }(A+B+N_V)$ and $\overline{y}\in V^{\perp }\cap (A\overline{x}+P_VB\overline{x})$, $x_{n+1}-x_n\rightarrow 0$, and $y_{n+1}-y_n\rightarrow 0$.

Proof

Indeed, it follows from the proof of Theorem 3.1 that Algorithm 3.1 is equivalent to (20), where, for every $n\in \mathbb {N}$, $z_n=x_n+\gamma y_n$. In the particular case when $\delta _n\equiv 1\in \big ]0,1/(\gamma \chi )\big [$, it follows from Proposition 3.1 (i) that (20) reduces to (21). Hence, the results follow from Theorem 3.1. $\square$

Remark 3.2

• (i) Note that, when $V=\mathcal {H}$ and $\lambda _n\equiv 1$, we have $V^{\perp }=\{0\}$, $P_V=\mathrm{Id }$, $(\mathrm{Id }+R_{N_V}R_{\gamma A})/2=J_{\gamma A}$, and, therefore, (21) reduces to

  $$\begin{aligned} (\forall n\in \mathbb {N})\quad \left\lfloor \begin{array}{l} r_n=x_n-\gamma Bx_n\\ s_n=J_{\gamma A}r_n\\ t_n=s_n-\gamma Bs_n\\ x_{n+1}=x_n+t_n-r_n, \end{array} \right. \end{aligned}$$

  (22)

  which is a version with constant step size of the Tseng’s method [22] for finding a zero of $A+B$.

• (ii) On the other hand, when $B\equiv 0$, (21) reduces to

  $$\begin{aligned} (\forall n\in \mathbb {N})\quad \left\lfloor \begin{array}{l} s_n=(z_n+R_{N_V}R_{\gamma A}z_n)/2\\ z_{n+1}=z_n+\lambda _n(s_n-z_n), \end{array} \right. \end{aligned}$$

  (23)

  which is the Douglas–Rachford splitting method [7, 28] for finding $x\in \mathcal {H}$ such that $0\in N_Vx+Ax$. It coincides with Spingarn’s partial inverse method with constant step size [6]. On the other hand, in the particular case when $A$ is a normal cone to a closed and convex set, a detailed study of this method and some extensions and modifications may be found in [32].

• (iii) Let $\mathsf{H}$ and $\mathsf{G}$ be real Hilbert spaces, let $\mathsf{L}:\mathsf{H}\rightarrow \mathsf{G}$ be linear and bounded, let $\mathsf{A}$ and $\mathsf{B}$ be maximally monotone operators, and define $T:(\mathsf{x},\mathsf{y})\in \mathcal {H}\mapsto \mathsf{y}-\mathsf{L}\mathsf{x}$. When $\mathcal {H}=\mathsf{H}\times \mathsf{G}$, $V=\ker T$, $B=0$, and $A:(\mathsf{x},\mathsf{y})\mapsto \mathsf{A}\mathsf{x}\times \mathsf{B}\mathsf{y}$, Problem 3.1 reduces to the primal-dual inclusions (see [33])

  $$\begin{aligned}&\text {find }\mathsf{x}\in \mathsf{H}\quad \mathrm{such}\,\mathrm{that}\quad 0\in \mathsf{A}\mathsf{x}+\mathsf{L}^*\mathsf{B}(\mathsf{L}\mathsf{x})\nonumber \\&\text {find }\mathsf{u}\in \mathsf{G}\quad \mathrm{such}\, \mathrm{that}\quad 0\in -\mathsf{L}\mathsf{A}^{-1}(-\mathsf{L}^*\mathsf{u})+\mathsf{B}^{-1}\mathsf{u}. \end{aligned}$$

  (24)

  In this context, the algorithm proposed in Corollary 3.1 is the method proposed recently in [33] in the absence of errors. This algorithm needs the computation of $P_V$, which involves the inverse of a suitable linear operator. Since our framework allows for a non-zero Lipschitzian monotone operator, it can address more complicated structures than (24).

4 Applications

In this section, we study three applications of our method. In each instance, a different closed vector subspace arises naturally, which illustrates the flexibility of our setting. Connections with other algorithms in each framework are provided.

4.1 Inclusion Involving the Sum of $m$ Monotone Operators

Problem 4.1

Let $(\mathsf{H},|\cdot |)$ be a real Hilbert space, for every $i\in \{1,\ldots ,m\}$, let $\mathsf{A}_i:\mathsf{H}\rightrightarrows {\mathsf{H}}$ be maximally monotone, and let $\mathsf{B}:\mathsf{H}\rightarrow \mathsf{H}$ be monotone and $\chi$–Lipschitzian. The problem is to

$$\begin{aligned} \text {find}\quad \mathsf{x}\in \mathsf{H}\quad \text {such that} \quad \mathsf{0}\in \sum _{i=1}^m\mathsf{A}_i\mathsf{x} +\mathsf{B}\mathsf{x}, \end{aligned}$$

(25)

under the assumption that solutions exist.

Problem 4.1 has several applications in image processing, principally in the variational setting (see, e.g., [1, 34] and the references therein), variational inequalities [4, 5], partial differential equations [10, 11], and economics [12, 13], among others. In [34, 35], Problem 4.1 is solved by a fully split algorithm in the particular case when $\mathsf{B}$ is cocoercive. Nevertheless, this approach does not seem to work in the general case. In [27], a method for solving a more general problem than Problem 4.1 is proposed. However, this approach stores and updates at each iteration $m$ dual variables, which may be unfavourable in large-scale systems. Our method exploits the whole structure of the problem, and it is obtained from Theorem 3.1, when the underlying closed vector subspace is the diagonal space in $\mathsf{H}^m$.

Let us first provide a connection between Problem 4.1 and Problem 3.1 via product space techniques. Let $(\omega _i)_{1\le i\le m}$ be real numbers in $\big ]0,1\big [$ such that $\sum _{i=1}^m\omega _i=1$, let $\mathcal {H}$ be the real Hilbert space obtained by endowing the Cartesian product $\mathsf{H}^m$ with the scalar product and associated norm defined by $\left\langle {x}\mid {y} \right\rangle :=\sum _{i=1}^m\omega _i\varvec{\langle }{\mathsf{x}_i}\mid {\mathsf{y}_i}\varvec{\rangle }$ and $\Vert x\Vert :=\sqrt{\sum _{i=1}^m\omega _i\mathsf{|}\mathsf{x}_i\mathsf{|}^2}$, respectively, where $x=(\mathsf{x}_i)_{1\le i\le m}$ and $y=(\mathsf{y}_i)_{1\le i\le m}$ are generic elements of $\mathcal {H}$.

Proposition 4.1

In the context of Problem 4.1, define

$$\begin{aligned}&V:=\big \{{x=(\mathsf{x}_i)_{1\le i\le m}\in \mathcal {H}} : {\mathsf{x}_1=\cdots =\mathsf{x}_m}\big \},\quad \nonumber \\&j:\mathsf{H}\rightarrow V\subset \mathcal {H}:\mathsf{x}\mapsto (\mathsf{x},\ldots ,\mathsf{x}), \nonumber \\&A:\mathcal {H}\rightrightarrows {\mathcal {H}}: x\mapsto \frac{1}{\omega _1}\mathsf{A}_1\mathsf{x}_1\times \cdots \times \frac{1}{\omega _m}\mathsf{A}_m\mathsf{x}_m,\quad \nonumber \\&B:\mathcal {H}\rightarrow \mathcal {H}: x\mapsto (\mathsf{B}\mathsf{x}_1,\ldots ,\mathsf{B}\mathsf{x}_m). \end{aligned}$$

(26)

Then, the following hold:

• (i) $V$ is a closed vector subspace of $\mathcal {H}$, for every $x=(\mathsf{x}_i)_{1\le i\le m}\in \mathcal {H}$, $P_Vx=j(\sum _{i=1}^m\omega _i\mathsf{x}_i)$, and, if $x\in V$, then $N_Vx=V^{\perp }=\big \{{x=(\mathsf{x}_i)_{1\le i\le m}\in \mathcal {H}} : {\sum _{i=1}^m\omega _i\mathsf{x}_i=\mathsf{0}}\big \}$; otherwise, $N_Vx=\varnothing$.

• (ii) $j:\mathsf{H}\rightarrow V$ is a bijective isometry and $j^{-1}:(\mathsf{x},\ldots ,\mathsf{x}) \mapsto \mathsf{x}$.

• (iii) $A$ is a maximally monotone operator and, for every $\gamma \in \,\big ]0,+\infty \big [$, $J_{\gamma A}: (\mathsf{x}_i)_{1\le i\le m}\mapsto (J_{\gamma \mathsf{A}_i/\omega _i}\mathsf{x}_i)$.

• (iv) $B$ is monotone and $\chi$–Lipschitzian, $B(j(\mathsf{x}))=j(\mathsf{B}\mathsf{x})$, and $B(V)\subset V$.

• (v) For every $\mathsf{x}\in \mathsf{H}$, $\mathsf{x}$ is a solution to Problem 4.1 if and only if $j(\mathsf{x})\in \mathrm{zer }(A+B+N_V)$.

Proof

(i) & (ii): They follow from (1) and easy computations. (iii): [30, Proposition 23.16]. (iv): They follow from simple computations by using (26) and the properties on $\mathsf{B}$. (v): Let $\mathsf{x}\in \mathsf{H}$. We have

(27)

which yields the result. $\square$

The following algorithm for solving Problem 4.1 is a direct consequence of Corollary 3.1 applied to the monotone inclusion in Proposition 4.1(v).

Algorithm 4.1

In the context of Problem 4.1, let $\gamma \in \big ]0,1/\chi \big [$, let $\varepsilon \in \big ]0,1\big [$, let $(\lambda _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,1\right]$, let $(\mathsf{z}_{i,0})_{1\le i\le m}\in \mathsf{H}^m$, and iterate, for every $n\in \mathbb {N}$,

$$\begin{aligned}&\left\lfloor \begin{array}{l} \mathsf{x}_{n}:=\sum _{j=1}^m\omega _j\mathsf{z}_{j,n}\\ \text { For }i=1,\ldots ,m\\ \left\lfloor \begin{array}{l} \mathsf{r}_{i,n}:=\mathsf{z}_{i,n}-\gamma \mathsf{B}\mathsf{x}_n\\ \mathsf{p}_{i,n}:=J_{\gamma \mathsf{A}_i/\omega _i}\mathsf{r}_{i,n}\\ \end{array} \right. \\ \mathsf{q}_{n}:=\sum _{j=1}^m\omega _j\mathsf{p}_{j,n}\\ \text { For }i=1,\ldots ,m\\ \left\lfloor \begin{array}{l} \mathsf{s}_{i,n}:=2\mathsf{q}_{n}-\mathsf{p}_{ i,n}+\mathsf{z}_{i,n}-\mathsf{x}_{n}\\ \mathsf{t}_{i,n}:=\mathsf{s}_{i,n}-\gamma \mathsf{B}\mathsf{q}_n\\ \mathsf{z}_{i,n+1}:=\mathsf{z}_{i,n}+\lambda _n(\mathsf{t}_{i,n}-\mathsf{r}_{i,n}).\\ \end{array} \right. \\ \end{array} \right. \end{aligned}$$

(28)

Theorem 4.1

Let $(\mathsf{x}_n)_{n\in \mathbb {N}}$ be the sequence generated by Algorithm 4.1. Then, $\mathsf{x}_n\rightharpoonup \overline{\mathsf{x}}$ for some solution $\overline{\mathsf{x}}$ to Problem 4.1 and $\mathsf{x}_{n+1}-\mathsf{x}_n\rightarrow 0$.

Proof

Set, for every $n\in \mathbb {N}$, $x_n:=j(\mathsf{x}_n)$, $q_n:=j(\mathsf{q}_n)$, $s_n:=(\mathsf{s}_{i,n})_{1\le i\le m}$, $z_n:=(\mathsf{z}_{i,n})_{1\le i\le m}$, and $p_n:=(\mathsf{p}_{i,n})_{1\le i\le m}$. It follows from Proposition 4.1 (i) and (28) that, for every $n\in \mathbb {N}$, $x_n=P_Vz_n$ and $q_n=P_Vp_n=P_Vs_n$. Hence, it follows from (26) and Proposition 4.1 that (28) can be written equivalently as (21). Altogether, Corollary 3.1 and Proposition 4.1(v) yield the results. $\square$

Remark 4.1

In the particular case when $m=2$, $B=0$, and $\omega _1=\omega _2=1/2$, Algorithm 4.1 reduces to the method in [24, Remark 6.2 (ii)] for finding a zero of $\mathsf{A}_1+\mathsf{A}_2$, which computes the resolvents of $\mathsf{A}_1$ and $\mathsf{A}_2$ in parallel. When these resolvents are hard to calculate, this method provides an alternative to the Douglas–Rachford splitting [7].

4.2 Primal-Dual Monotone Inclusions

This section is devoted to the numerical resolution of a very general composite primal-dual monotone inclusion involving vector subspaces. The proposed algorithm addresses monotone operators composed with linear transformations and solves simultaneously primal and dual inclusions.

Let us introduce a partial sum operation with respect to a closed vector subspace. This notion is a generalisation of the parallel sum (see, e.g., [36] and the references therein).

Definition 4.1

Let $\mathcal {H}$ be a real Hilbert space, let $U\subset \mathcal {H}$ be a closed vector subspace, and let $A:\mathcal {H}\rightrightarrows {\mathcal {H}}$ and $B:\mathcal {H}\rightrightarrows {\mathcal {H}}$ be nonlinear operators. The partial sum of $A$ and $B$ with respect to $U$ is defined by

(29)

In particular, we have and .

The operation $A\mapsto A_U$ preserves monotonicity [9]. Hence, is monotone if $A$ and $B$ are monotone. In this section, we are interested in the following problem.

Problem 4.2

Let $\mathsf{H},(\mathsf{G}_i)_{1\le i\le m}$ be real Hilbert spaces, for every $i\in \{1,\ldots ,m\}$, let $\mathsf{U}\subset \mathsf{H}$ and $\mathsf{V}_i\subset \mathsf{G}_i$ be closed vector spaces, let $\mathsf{A}:\mathsf{H}\rightrightarrows {\mathsf{H}}$ and $\mathsf{B}_i:\mathsf{G}_i\rightrightarrows {\mathsf{G}_i}$ be maximally monotone, let $\mathsf{L}_i:\mathsf{H}\rightarrow \mathsf{G}_i$ be linear and bounded, let $\mathsf{D}_i:\mathsf{G}_i\rightrightarrows {\mathsf{G}_i}$ be monotone such that $(\mathsf{D}_i)_{\mathsf{V}_i^{\perp }}$ is $\nu _i$-Lipschitzian for some $\nu _i\in \,\big ]0,+\infty \big [$, let $\mathsf{C}:\mathsf{H}\rightarrow \mathsf{H}$ be monotone and $\mu$-Lipschitzian for some $\mu \in \,\big ]0,+\infty \big [$, let $\mathsf{z}\in \mathsf{H}$, and let $\mathsf{b}_i\in \mathsf{G}_i$. The problem is to solve the primal inclusion

(30)

together with the dual inclusion: find $\mathsf{u}_1\in \mathsf{G}_1,\ldots , \mathsf{u}_m\in \mathsf{G}_m$ such that

(31)

The set of solutions to (30) and (31) are denoted by ${\mathcal P}\ne \varnothing$ and ${\mathcal D}\ne \varnothing$, respectively.

In the particular case when $\mathsf{U}=\mathsf{H}$, for every $i\in \{1,\ldots ,m\}$, $\mathsf{V}_i=\mathsf{G}_i$, $\mathsf{D}_i0=\mathsf{G}_i$, for every $\mathsf{y}\ne 0$, $\mathsf{D}_i\mathsf{y}=\varnothing$, and $\mathsf{C}=0$, Problem 4.2 is solved in [23, 33] via fully split primal-dual algorithms. In particular, in [33], a proximal point algorithm applied to the partial inverse of a maximally monotone operator with respect to the kernel of a linear operator is proposed for solving Problem 4.2. On the other hand, when $\mathsf{U}=\mathsf{H}$ and, for every $i\in \{1,\ldots ,m\}$, $\mathsf{V}_i=\mathsf{G}_i$, Problem 4.2 is solved by a splitting method proposed in [27]. To the best of our knowledge, the general case has not been tackled in the literature via splitting methods.

Problem 4.2 requires a Lipschitzian condition on $({\mathsf{D}_i}_{\mathsf{V}_i^{\perp }})_{1\le i\le m}$. When, for every $i\in \{1,\ldots ,m\}$, $\mathsf{V}_i=\mathsf{G}_i$, this condition reduces to the Lipschitzian property on ${\mathsf{D}_i}^{-1}$, which is trivially satisfied, e.g., when $\mathsf{D}_i0=\mathsf{G}_i$ and, for every $\mathsf{y}\ne 0$, $\mathsf{D}_i\mathsf{y}=\varnothing$. The next proposition furnishes other non-trivial instances, in which the partial inverse of a monotone operator is Lipschitzian.

Proposition 4.2

Let $\mathsf{V}\subset \mathsf{H}$ be a closed vector space and suppose that one of the following holds:

• (i) $\mathsf{D}:\mathsf{H}\rightarrow \mathsf{H}$ is $\beta$-strongly monotone and $\nu$-cocoercive.

• (ii) $\mathsf{D}=\nabla \mathsf{f}$, where $\mathsf{f}:\mathsf{H}\rightarrow \,\big ]-\infty ,+\infty \big ]$ is differentiable, $\beta$-strongly convex, and $\nabla \mathsf{f}$ is $\nu ^{-1}$-Lipschitzian.

• (iii) $\mathsf{D}$ is a linear bounded operator satisfying, for every $\mathsf{x}\in \mathsf{H}$, $\left\langle {\mathsf{x}}\mid {\mathsf{D}\mathsf{x}} \right\rangle \ge \beta \Vert \mathsf{x}\Vert ^2$, and $\nu =\beta /\Vert \mathsf{D}\Vert ^2$.

Then, $\mathsf{D}_{\mathsf{V}}$ is $\alpha$-cocoercive and $\alpha$-strongly monotone with $\alpha =\min \{\beta ,\nu \}/2$. In particular, $\mathsf{D}_{\mathsf{V}}$ is $\alpha ^{-1}$-Lipschitzian.

Proof

(i): Let $(\mathsf{x},\mathsf{u})$ and $(\mathsf{y},\mathsf{v})$ in $\mathrm{gra }(\mathsf{D}_{\mathsf{V}})$. It follows from (2) that $(P_\mathsf{V}\mathsf{x}+P_{\mathsf{V}^{\perp }}\mathsf{u},P_{\mathsf{V}} \mathsf{u}+P_{\mathsf{V}^{\perp }}\mathsf{x})$ and $(P_{\mathsf{V}}\mathsf{y}+P_{\mathsf{V}^{\perp }}\mathsf{v},P_{\mathsf{V}} \mathsf{v}+P_{\mathsf{V}^{\perp }}\mathsf{y})$ are in $\mathrm{gra }(\mathsf{D})$, and from the strong monotonicity assumption on $\mathsf{D}$, we have

$$\begin{aligned} \left\langle {\mathsf{x}-\mathsf{y}}\mid {\mathsf{u}-\mathsf{v}} \right\rangle&= \big \langle {P_{\mathsf{V}}(\mathsf{x}-\mathsf{y})}{P_{\mathsf{V}}(\mathsf{u}- \mathsf{v})}\big \rangle +\left\langle {P_{\mathsf{V}^{\perp }}(\mathsf{u}-\mathsf{v})}\mid {P_{\mathsf{V}^{\perp }}(\mathsf{x}-\mathsf{y})} \right\rangle \nonumber \\&=\left\langle {P_{\mathsf{V}}\mathsf{x}+P_{\mathsf{V}^{\perp }}\mathsf{u}- (P_{\mathsf{V}}\mathsf{y}+P_{\mathsf{V}^{\perp }}\mathsf{v})}\mid {P_{\mathsf{V}}\mathsf{u}+P_{\mathsf{V}^{\perp }}\mathsf{x}- (P_{\mathsf{V}}\mathsf{v}+P_{\mathsf{V}^{\perp }}\mathsf{y})} \right\rangle \nonumber \\&\ge \beta \Vert P_\mathsf{V}\mathsf{x}+P_{\mathsf{V}^{\perp }}\mathsf{u}- (P_\mathsf{V}\mathsf{y}+P_{\mathsf{V}^{\perp }}\mathsf{v})\Vert ^2\nonumber \\&=\beta (\Vert P_\mathsf{V}(\mathsf{x}-\mathsf{y})\Vert ^2+ \Vert P_{\mathsf{V}^{\perp }}(\mathsf{u}-\mathsf{v})\Vert ^2). \end{aligned}$$

(32)

Analogously, the cocoercivity assumption on $\mathsf{D}$ yields $\left\langle {\mathsf{x}-\mathsf{y}}\mid {\mathsf{u}-\mathsf{v}} \right\rangle \ge \nu (\Vert P_\mathsf{V}(\mathsf{u}-\mathsf{v})\Vert ^2 +\Vert P_{\mathsf{V}^{\perp }}(\mathsf{x}-\mathsf{y})\Vert ^2)$. Hence, it follows from (32) that

$$\begin{aligned} \left\langle {\mathsf{x}\!-\!\mathsf{y}}\mid {\mathsf{u}\!-\!\mathsf{v}} \right\rangle&\ge \frac{\beta }{2}(\Vert P_\mathsf{V}(\mathsf{x}\!-\!\mathsf{y})\Vert ^2 \!+\!\Vert P_{\mathsf{V}^{\perp }}(\mathsf{u}\!-\!\mathsf{v})\Vert ^2)\nonumber \\&\quad +\frac{\nu }{2}(\Vert P_\mathsf{V}(\mathsf{u}\!-\!\mathsf{v})\Vert ^2 \!+\!\Vert P_{\mathsf{V}^{\perp }}(\mathsf{x}\!-\!\mathsf{y})\Vert ^2), \end{aligned}$$

(33)

which yields $\left\langle {\mathsf{x}-\mathsf{y}}\mid {\mathsf{u}-\mathsf{v}} \right\rangle \ge \alpha \big (\Vert \mathsf{x}-\mathsf{y}\Vert ^2+\Vert \mathsf{u}-\mathsf{v}\Vert ^2\big )$, and the result follows. (ii): From the strong convexity of $\mathsf{f}$, we have that $\mathsf{D}=\nabla \mathsf{f}$ is $\beta$-strongly monotone and, from [37], it is $\nu$-cocoercive. Hence, the result follows from (i). (iii): Since $\mathsf{D}$ is linear and bounded, we have $\Vert \mathsf{x}\Vert ^2\ge \Vert \mathsf{D}\mathsf{x}\Vert ^2/\Vert \mathsf{D}\Vert ^2$. Then, $\mathsf{D}$ is $\beta$-strongly monotone and $\nu$-cocoercive, and the result follows from (i). $\square$

The following proposition gives a connection between Problem 4.2 and Problem 3.1.

Proposition 4.3

Set $\mathcal {H}:=\mathsf{H}\oplus \mathsf{G}_1\oplus \cdots \oplus \mathsf{G}_m$, set

$$\begin{aligned} \chi :=\max \{\mu ,\nu _1,\ldots ,\nu _m\}+ \sqrt{\sum _{i=1}^m\Vert \mathsf{L}_i\Vert ^2}, \end{aligned}$$

and set

$$\begin{aligned}&A:\mathcal {H}\rightrightarrows {\mathcal {H}}:(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto (-\mathsf{z}+\mathsf{A}\mathsf{x})\times (P_{\mathsf{V}_1}\mathsf{b}_1+ (\mathsf{B}_1)_{\mathsf{V}_1^{\perp }}\mathsf{u}_1)\times \cdots \nonumber \\&\quad \times (P_{\mathsf{V}_m}\mathsf{b}_m+(\mathsf{B}_m)_{\mathsf{V}_m^{\perp }}\mathsf{u}_m)\nonumber \\&L:\mathcal {H}\rightarrow \mathcal {H}:(\mathsf{x},\mathsf{u}_1,\ldots , \mathsf{u}_m)\mapsto \left( \sum _{i=1}^m\mathsf{L}_i^*P_{\mathsf{V}_i}\mathsf{u}_i, -P_{\mathsf{V}_1}\mathsf{L}_1\mathsf{x},\ldots , -P_{\mathsf{V}_m}\mathsf{L}_m\mathsf{x}\right) \nonumber \\&C:\mathcal {H}\rightarrow \mathcal {H}:(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto \big (\mathsf{C}\mathsf{x}, (\mathsf{D}_1)_{\mathsf{V}_1^{\perp }}\mathsf{u}_1,\ldots , (\mathsf{D}_m)_{\mathsf{V}_m^{\perp }}\mathsf{u}_m\big )\nonumber \\&B:\mathcal {H}\rightarrow \mathcal {H}:(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto (C+L)(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\nonumber \\&W:=\mathsf{U}\times \mathsf{V}_1\times \cdots \times \mathsf{V}_m. \end{aligned}$$

(34)

Then, the following hold:

• (i) $A$ is maximally monotone and, for every $\gamma \in \,\big ]0,+\infty \big [$,

  $$\begin{aligned} J_{\gamma A}:(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto \Big (J_{\gamma \mathsf{A}}(\mathsf{x}\!+\!\mathsf{z}),J_{\gamma (\mathsf{B}_1)_{\mathsf{V}_1^{\perp }}}(\mathsf{u}_1\!-\!P_{\mathsf{V}_1}\mathsf{b}_1),\ldots , J_{\gamma (\mathsf{B}_m)_{\mathsf{V}_m^{\perp }} }(\mathsf{u}_m\!-\!P_{\mathsf{V}_m}\mathsf{b}_m)\Big ).\nonumber \\ \end{aligned}$$

  (35)

• (ii) $L$ is linear, bounded, $L^*=-L$, and $\Vert L\Vert \le \sqrt{\sum _{i=1}^m\Vert \mathsf{L}_i\Vert ^2}$.

• (iii) $B$ is monotone and $\chi$-Lipschitzian.

• (iv) $W$ is a closed vector subspace of $\mathcal {H}$, $N_{W}:(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto N_\mathsf{U}\mathsf{x}\times N_{\mathsf{V}_1}\mathsf{u}_1\times \cdots \times N_{\mathsf{V}_m}\mathsf{u}_m$, and $P_{W}:(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto (P_\mathsf{U}\mathsf{x},P_{\mathsf{V}_1}\mathsf{u}_1, \ldots ,P_{\mathsf{V}_m}\mathsf{u}_m).$

• (v) $\mathrm{zer }(A+B+N_{ W})\subset \mathcal {P}\times \mathcal {D}$.

• (vi) $\mathcal {P}\ne {\varnothing }\,\,\Leftrightarrow \,\, \mathrm{zer }(A+B+N_{W})\ne {\varnothing }\,\,\Leftrightarrow \,\,\mathcal {D}\ne {\varnothing }.$

Proof

(i): Since, for every $i\in \{1,\ldots ,m\}$, $(\mathsf{B}_i)_{\mathsf{V}_i^{\perp }}$ is maximally monotone, the result follows from [30, Proposition 23.15 and Proposition 23.16]. (ii): Let us define $\mathsf{M}:(\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto \sum _{i=1}^m\mathsf{L}_i^*P_{\mathsf{V}_i}\mathsf{u}_i$. Since $(\mathsf{L}_i)_{1\le i\le m}$ and $(P_{\mathsf{V}_i})_{1\le i\le m}$ are linear bounded operators, $\mathsf{M}$ is linear and bounded and, for every $\mathsf{x}\in \mathsf{H}$, $\mathsf{M}^*\mathsf{x}=(P_{\mathsf{V}_1}\mathsf{L}_1\mathsf{x}, \ldots ,P_{\mathsf{V}_m}\mathsf{L}_m\mathsf{x})$. Since $L$ can be written as $L:(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\mapsto (\mathsf{M}(\mathsf{u}_1,\ldots ,\mathsf{u}_m), -\mathsf{M}^*\mathsf{x})$, we deduce from [23, Proposition 2.7(ii)] that $L$ is linear and bounded, that $L^*=-L$, and that $\Vert L\Vert =\Vert M\Vert$. Now, for every $(\mathsf{u}_1,\ldots ,\mathsf{u}_m)\in \mathsf{G}_1\oplus \cdots \oplus \mathsf{G}_m$, we have from triangle and Hölder inequalities that $\Vert M(\mathsf{u}_1,\ldots ,\mathsf{u}_m)\Vert \le \sum _{i=1}^m\Vert \mathsf{L}_i\Vert \Vert P_{\mathsf{V}_i}\Vert \Vert \mathsf{u}_i\Vert \le \sum _{i=1}^m\Vert \mathsf{L}_i\Vert \Vert \mathsf{u}_i\Vert \le \sqrt{\sum _{i=1}^m\Vert \mathsf{L}_i\Vert ^2}\sqrt{\sum _{i=1}^m\Vert \mathsf{u}_i\Vert ^2}$. (iii): Since (ii) implies that $L$ is linear, bounded, and skew, it is monotone and $\Vert L\Vert$-Lipschitzian. Moreover, because $\mathsf{C}$ and $(\mathsf{D}_i)_{\mathsf{V}_i^{\perp }}$ are monotone and Lipschitzian, $C$ is monotone and Lipschitzian with constant $\max \{\mu ,\nu _1,\ldots ,\nu _m\}$. Altogether, $B=C+L$ is monotone and $\chi$-Lipschitzian. (iv): Clear. (v): Let $(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\in \mathsf{H}\times \mathsf{G}_1\times \cdots \mathsf{G}_m$. From (34) and Proposition 2.1, we obtain

(36)

(37)

which yields $\mathsf{x}\in \mathcal {P}$. Moreover, (36) yields $(\mathsf{u}_1,\ldots ,\mathsf{u}_m)\in \mathcal {D}$. (vi): If $\mathsf{x}\in \mathcal {P}$, then there exist $(\mathsf{u}_1,\ldots ,\mathsf{u}_m)$ such that (36) holds and, hence, $(\mathsf{u}_1,\ldots ,\mathsf{u}_m)\in \mathcal {D}$. Now, if $(\mathsf{u}_1,\ldots ,\mathsf{u}_m)\in \mathcal {D}$, then there exists $\mathsf{x}\in \mathsf{H}$ such that (36) holds and, hence, $(\mathsf{x},\mathsf{u}_1,\ldots ,\mathsf{u}_m)\in \mathrm{zer }(A+B+N_W)$. The last implication follows from (v). $\square$

Algorithm 4.2

In the setting of Problem 4.2, let $\gamma \in \big ]0,1/\chi \big [$, where $\chi$ is defined in Proposition 4.3, let $(\lambda _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,1\right]$, let $\mathsf{x}_0\in \mathsf{H}$, let $(\mathsf{u}_{i,0})_{1\le i\le m}\in \mathsf{G}_1\times \cdots \times \mathsf{G}_m$, and iterate, for every $n\in \mathbb {N}$,

$$\begin{aligned}&\left\lfloor \begin{array}{l} \mathsf{r}_{1,n}:=\mathsf{x}_{n}-\gamma P_{\mathsf{U}}\big (\mathsf{C}P_{\mathsf{U}}\mathsf{x}_{n}+\sum _{i=1}^{m}\mathsf{L}_i^*P_{\mathsf{V}_{i}}\mathsf{u}_{i,n}\big )\\ \mathsf{p}_{1,n}:=J_{\gamma \mathsf{A}}(\mathsf{r}_{1,n}+\gamma \mathsf{z})\\ \mathsf{s}_{1,n}:=2P_{\mathsf{U}}\mathsf{p}_{1,n}-\mathsf{p}_{1,n}+\mathsf{r}_{1,n}-P_{\mathsf{U}}\mathsf{r}_{1,n}\\ \text { For }i=1,\ldots ,m\\ \left\lfloor \begin{array}{l} \mathsf{r}_{2,i,n}:=\mathsf{u}_{i,n}-\gamma P_{\mathsf{V}_{i}}({\mathsf{D}_i}_{\mathsf{V}_i^{\perp }}P_{\mathsf{V}_{i}}\mathsf{u}_{i,n}-\mathsf{L}_iP_{\mathsf{U}}\mathsf{x}_{n})\\ \mathsf{p}_{2,i,n}:=J_{\gamma {\mathsf{B}_i}_{\mathsf{V}_i^{\perp }}}(\mathsf{r}_{2,i,n}-\gamma P_{\mathsf{V}_{i}}\mathsf{b}_i)\\ \mathsf{s}_{2,i,n}:=2P_{\mathsf{V}_i}\mathsf{p}_{2,i,n}-\mathsf{p}_{2,i,n}+\mathsf{r}_{2,i,n}-P_{\mathsf{V}_i}\mathsf{r}_{2,i,n}\\ \mathsf{t}_{2,i,n}:=\mathsf{s}_{2,i,n}-\gamma P_{\mathsf{V}_{i}}({\mathsf{D}_i}_{\mathsf{V}_i^{\perp }}P_{\mathsf{V}_{i}}\mathsf{s}_{2,i,n}-\mathsf{L}_iP_{\mathsf{U}}\mathsf{s}_{1,n})\\ \mathsf{u}_{i,n+1}:=\mathsf{u}_{i,n}+\lambda _n(\mathsf{t}_{2,i,n}-\mathsf{r}_{2,i,n}) \end{array} \right. \\ \mathsf{t}_{1,n}:=\mathsf{s}_{1,n}-\gamma P_{\mathsf{U}}\big (\mathsf{C}P_{\mathsf{U}}\mathsf{s}_{1,n}+\sum _{i=1}^{m}\mathsf{L}_i^*P_{\mathsf{V}_{i}}\mathsf{s}_{2,i,n}\big )\\ \mathsf{x}_{n+1}:=\mathsf{x}_{n}+\lambda _n(\mathsf{t}_{1,n}-\mathsf{r}_{1,n}). \end{array} \right. \end{aligned}$$

(38)

Theorem 4.2

Let $(\mathsf{x}_n)_{n\in \mathbb {N}}$ and $(\mathsf{u}_{1,n})_{n\in \mathbb {N}},\ldots ,(\mathsf{u}_{m,n})_{n\in \mathbb {N}}$ be the sequences generated by Algorithm 4.2. Then, $\mathsf{x}_n\rightharpoonup \overline{\mathsf{x}}\in \mathsf{H}$, $\mathsf{x}_{n+1}-\mathsf{x}_n\rightarrow 0$, for every $i\in \{1,\ldots ,m\}$, $\mathsf{u}_{i,n}\rightharpoonup \overline{\mathsf{u}}_i\in \mathsf{G}_i$, $\mathsf{u}_{i,n+1}-\mathsf{u}_{i,n}\rightarrow 0$, and $(P_{\mathsf{U}}\overline{\mathsf{x}},P_{\mathsf{V}_1}\overline{\mathsf{u}}_1,\ldots ,P_{\mathsf{V}_m}\overline{\mathsf{u}}_m)$ is a solution to Problem 4.2.

Proof

By defining, for every $n\in \mathbb {N}$, $z_n:=(\mathsf{x}_n,\mathsf{u}_{1,n},\ldots ,\mathsf{u}_{m,n})$, $r_n:=(\mathsf{r}_{1,n},\mathsf{r}_{2,1,n},\ldots ,\mathsf{r}_{2,m,n})$, $p_n\!\!:=\!\!(\mathsf{p}_{1,n},\mathsf{p}_{2,1,n},\ldots ,\mathsf{p}_{2,m,n})$, $s_n\!\!:=\!\!(\mathsf{s}_{1,n},\mathsf{s}_{2,1,n},\ldots ,\mathsf{s}_{2,m,n})$, and $t_n=(\mathsf{t}_{1,n},\mathsf{t}_{2,1,n},\ldots ,\mathsf{t}_{2,m,n})$, it follows from Proposition 4.3 that (38) is a particular instance of (21). Hence, the results follow from Corollary 3.1 and Proposition 4.3(v). $\square$

Remark 4.2

• (i) Even if Problem 4.1 can be seen as a particular case of Problem 4.2, the methods in (38) and (28) have different structures. Indeed, in (38), dual variables are updated at each iteration, which may be numerically costly in large-scale problems. Only primal variables are updated in Algorithm 4.1.

• (ii) Algorithm 4.2 activates each operator involved in Problem 4.2 independently. The algorithm is explicit in each step if the resolvents of $\mathsf{A}$ and $({\mathsf{B}_i}_{\mathsf{V}_i^{\perp }})_{1\le i\le m}$ can be computed. Observe that the resolvent of the partial inverse of a monotone operator can be explicitly found via Proposition 3.1(i).

• (iii) Note that, when $\lambda _n\equiv 1$, $\mathsf{U}=\mathsf{H}$, and, for every $i\in \{1,\ldots ,m\}$, $\mathsf{V}_i=\mathsf{G}_i$, Algorithm 4.2 reduces to the method in [27, Theorem 3.1] with constant step size.

• (iv) In the simplest case when $m=2$, $\mathsf{z}=\mathsf{A}=\mathsf{C}=\mathsf{b}_1=\mathsf{b}_2=0$, $\mathsf{L}_1=\mathsf{L_2}=\mathrm{Id }$, $\mathsf{U}=\mathsf{H}$, $\mathsf{V}_1\equiv \mathsf{G}_1$, $\mathsf{V}_2\equiv \mathsf{G}_2$, $\mathsf{D}_10=\mathsf{G}_1$, $\mathsf{D}_20=\mathsf{G}_2$, and for every $\mathsf{y}\ne 0$, $\mathsf{D}_1\mathsf{y}=\mathsf{D}_2\mathsf{y}=\varnothing$, we have, for every $i\in \{1,2\}$, ${\mathsf{D}_i}_{V_i^{\perp }}={\mathsf{D}_i}_{\{0\}}=\mathsf{D}_i^{-1}: \mathsf{y}\mapsto 0$, Problem 4.2 reduces to find a zero of $\mathsf{B}_1+\mathsf{B}_2$, and (38) becomes

  $$\begin{aligned} (\forall n\in \mathbb {N})\quad&\left\lfloor \begin{array}{l} \mathsf{p}_{1,n}=J_{\gamma \mathsf{B}_1^{-1}}(\mathsf{u}_{1,n}+\gamma \mathsf{x}_n)\\ \mathsf{p}_{2,n}=J_{\gamma \mathsf{B}_2^{-1}}(\mathsf{u}_{2,n}+\gamma \mathsf{x}_n)\\ \mathsf{x}_{n+1}=\mathsf{x}_n-\gamma \lambda _n(\mathsf{p}_{1,n}+\mathsf{p}_{2,n})\\ \mathsf{u}_{1,n+1}=(1-\lambda _n)\mathsf{u}_{1,n}+\lambda _n\big (\mathsf{p}_{1,n}-\gamma ^2(\mathsf{u}_{1,n}+\mathsf{u}_{2,n})\big )\\ \mathsf{u}_{2,n+1}=(1-\lambda _n)\mathsf{u}_{2,n}+\lambda _n\big (\mathsf{p}_{2,n}-\gamma ^2(\mathsf{u}_{1,n}+\mathsf{u}_{2,n})\big ). \end{array} \right. \end{aligned}$$

  (39)

  This method solves this problem and its dual, simultaneously, and differs from the algorithm derived in Remark 4.1.

4.3 Zero-Sum Games

Our last application is devoted to the problem of finding a Nash equilibrium in continuous zero-sum games. Some comments on finite zero-sum games are also provided. This problem can be formulated in the form of Problem 3.1, and it can be solved via an algorithm derived from Algorithm 3.1.

Problem 4.3

For every $i\in \{1,2\}$, let $\mathsf{H}_i$ and $\mathsf{G}_i$ be real Hilbert spaces, let $\mathsf{C}_i\subset \mathsf{H}_i$ be closed and convex, let $\mathsf{L}_i:\mathsf{H}_i\rightarrow \mathsf{G}_i$ be a linear bounded operator with closed range, let $\mathsf{e}_i\in \mathsf{H}_i$, set $\mathsf{b}_i:=\mathsf{L}_i\mathsf{e}_i$, set $\mathsf{S}_i:=\big \{{\mathsf{x}\in \mathsf{C}_i} : {\mathsf{L}_i\mathsf{x}=\mathsf{b}_i}\big \}$, let $\chi \in \,\big ]0,+\infty \big [$, and let $\mathsf{f}:\mathsf{H}_1\times \mathsf{H}_2\rightarrow {\mathbb {R}}$ be a differentiable function with a $\chi$–Lipschitzian gradient such that, for every $\mathsf{z}_1\in \mathsf{H}_1$, $\mathsf {f}(\mathsf{z}_1,\cdot )$ is concave and, for every $\mathsf{z}_2\in \mathsf{H}_2$, $\mathsf{f}(\cdot ,\mathsf{z}_2)$ is convex. Moreover, suppose that $\mathrm{int }(\mathsf{C}_1-\mathsf{e}_1)\cap \ker \mathsf{L}_1\ne {\varnothing }$ and $\mathrm{int }(\mathsf{C}_2-\mathsf{e}_2)\cap \ker \mathsf{L}_2\ne {\varnothing }$. The problem is to

$$\begin{aligned} \text {find}\quad \mathsf{x}_1\in \mathsf{S}_1\quad \text {and}\quad \mathsf{x}_2\in \mathsf{S}_2\quad \text {such that}\quad {\left\{ \begin{array}{ll} \mathsf{x}_1\in \underset{\begin{array}{c} {\mathsf{z}_1\in \mathsf{S}_1} \end{array}}{\mathrm{Argmin}}\;\;\mathsf{f}(\mathsf{z}_1,\mathsf{x}_2) \\ \mathsf{x}_2\in \underset{\begin{array}{c} {\mathsf{z}_2\in \mathsf{S}_2} \end{array}}{\mathrm{Argmax}}\;\;\mathsf{f}(\mathsf{x}_1,\mathsf{z}_2) , \end{array}\right. } \end{aligned}$$

(40)

under the assumption that solutions exist.

Problem 4.3 is a generic zero-sum game, in which the sets ${\mathsf{S}}_1$ and ${\mathsf{S}}_2$ are usually convex bounded sets representing mixed strategy spaces. For example, if, for every $i\in \{1,2\}$, $\mathsf{H}_i={\mathbb {R}}^{N_i}$, $\mathsf{C}_i$ is the positive orthant, $\mathsf{G}_i\equiv {\mathbb {R}}$, $\mathsf{b}_i\equiv 1$, and $\mathsf{L}_i$ is the sum of the components in ${\mathbb {R}}^{N_i}$, then $\mathsf{S}_i$ is the simplex in ${\mathbb {R}}^{N_i}$. In that case, for a bilinear function $\mathsf{f}$, Problem 4.3 reduces to a finite zero-sum game. Beyond this particular case, Problem 4.3 covers continuous zero-sum games, in which mixed strategies are distributions and $\mathsf{L}_1$ and $\mathsf{L}_2$ are integral operators.

As far as we know, some alternating methods are proposed in [38, 39] for solving Problem 4.3, when the function $\mathsf{f}$ has a special separable structure involving specific coupling schemes. On the other hand, a method proposed in [40] can solve Problem 4.3 when the projections onto $\mathsf{S}_1$ and $\mathsf{S}_2$ are computable. However, in infinite dimension, these projections are not always easy to compute, as we will discuss in Example 4.1. The following result provides a convergent algorithm for solving Problem 4.3, which replaces the projections onto $\mathsf{S}_1$ and $\mathsf{S}_2$ by simpler projections onto $\mathsf{C}_1$, $\mathsf{C}_2$, $\ker (\mathsf{L}_1)$, and $\ker (\mathsf{L}_2)$. It is a consequence of Corollary 3.1 when the underlying subspace is $V=\ker (\mathsf{L}_1)\times \ker (\mathsf{L}_2)$. Let us first introduce the generalised Moore-Penrose inverse of a bounded linear operator $\mathsf{L}:\mathsf{H}\rightarrow \mathsf{G}$ with closed range, defined by $\mathsf{L}^{\dagger }:\mathsf{G}\rightarrow \mathsf{H}:\mathsf{y}\mapsto P_{C_{\mathsf{y}}}0$, where, for every $\mathsf{y}\in \mathsf{G}$, $C_{\mathsf{y}}:=\big \{{\mathsf{x}\in \mathsf{H}} : {\mathsf{L}^*\mathsf{L}\mathsf{x}=\mathsf{L}^*\mathsf{y}}\big \}$. The operator $\mathsf{L}^{\dagger }$ is also linear and bounded, and, in the particular case when $\mathsf{L}^*\mathsf{L}$ is invertible, we have $\mathsf{L}^{\dagger }=(\mathsf{L}^*\mathsf{L})^{-1}\mathsf{L}^*$. For further details and properties, see [30, section 3].

Algorithm 4.3

In the context of Problem 4.3, let $\varepsilon \!\in \!\big ]0,1\big [$, let $\gamma \!\in \!\big ]0,1/\chi \big [$, let $(\lambda _n)_{n\in \mathbb {N}}$ be a sequence in $\left[ \varepsilon ,1\right]$, let $(\mathsf{z}_{1,0},\mathsf{z}_{2,0}) \!\in \! \mathsf{H}_1\oplus \mathsf{H}_2$, and iterate, for every $n\in \mathbb {N}$,

$$\begin{aligned}&\left\lfloor \begin{array}{l} \mathsf{u}_{1,n}:=(\mathrm{Id }-\mathsf{L}_1^*\mathsf{L}_1^{*\dagger }) \mathsf{z}_{1,n}+\mathsf{e}_1\\ \mathsf{u}_{2,n}:=(\mathrm{Id }-\mathsf{L}_2^*\mathsf{L}_2^{*\dagger }) \mathsf{z}_{2,n}+\mathsf{e}_2\\ \mathsf{g}_{1,n}:=(\mathrm{Id }-\mathsf{L}_1^*\mathsf{L}_1^{*\dagger })\nabla \big (\mathsf{f}(\cdot ,\mathsf{u}_{2,n})\big ) (\mathsf{u}_{1,n})\\ \mathsf{g}_{2,n}:=-(\mathrm{Id }-\mathsf{L}_2^*\mathsf{L}_2^{*\dagger })\nabla \big (\mathsf{f}(\mathsf{u}_{1,n},\cdot )\big )(\mathsf{u}_{2,n})\\ \mathsf{r}_{1,n}:=\mathsf{z}_{1,n}-\gamma \mathsf{g}_{1,n}\\ \mathsf{r}_{2,n}:=\mathsf{z}_{2,n}-\gamma \mathsf{g}_{2,n}\\ \mathsf{p}_{1,n}:=P_{\mathsf{C}_1}(\mathsf{r}_{1,n}+\mathsf{e}_1)-\mathsf{e}_1\\ \mathsf{p}_{2,n}:=P_{\mathsf{C}_2}(\mathsf{r}_{2,n}+\mathsf{e}_2)-\mathsf{e}_2\\ \mathsf{v}_{1,n}:=(\mathrm{Id }-\mathsf{L}_1^*\mathsf{L}_1^{*\dagger })\mathsf{p}_{1,n}\\ \mathsf{v}_{2,n}:=(\mathrm{Id }-\mathsf{L}_2^*\mathsf{L}_2^{*\dagger })\mathsf{p}_{2,n}\\ \mathsf{s}_{1,n}:=2\mathsf{v}_{1,n}-\mathsf{p}_{1,n}+\mathsf{L}_1^*\mathsf{L}_1^{*\dagger }\mathsf{r}_{1,n}\\ \mathsf{s}_{2,n}:=2\mathsf{v}_{2,n}-\mathsf{p}_{2,n}+\mathsf{L}_2^*\mathsf{L}_2^{*\dagger }\mathsf{r}_{2,n}\\ \mathsf{h}_{1,n}:=(\mathrm{Id }-\mathsf{L}_1^*\mathsf{L}_1^{*\dagger })\nabla \big (\mathsf{f}(\cdot ,\mathsf{e}_2+\mathsf{v}_{2,n})\big )(\mathsf{e}_1+\mathsf{v}_{1,n})\\ \mathsf{h}_{2,n}:=-(\mathrm{Id }-\mathsf{L}_2^*\mathsf{L}_2^{*\dagger })\nabla \big (\mathsf{f}(\mathsf{e}_1+\mathsf{v}_{1,n},\cdot )\big )(\mathsf{e}_2+\mathsf{v}_{2,n})\\ \mathsf{t}_{1,n}:=\mathsf{s}_{1,n}-\gamma \mathsf{h}_{1,n} \\ \mathsf{t}_{2,n}:=\mathsf{s}_{2,n}-\gamma \mathsf{h}_{2,n} \\ \mathsf{z}_{1,n+1}:=\mathsf{z}_{1,n}+\lambda _n(\mathsf{t}_{1,n}-\mathsf{r}_{1,n})\\ \mathsf{z}_{2,n+1}:=\mathsf{z}_{2,n}+\lambda _n(\mathsf{t}_{2,n}-\mathsf{r}_{2,n}). \end{array} \right. \end{aligned}$$

(41)

Theorem 4.3

Let $(\mathsf{u}_{1,n},\mathsf{u}_{2,n})_{n\in \mathbb {N}}$ be the sequence generated by Algorithm 4.3. Then, $\mathsf{u}_{1,n}\rightharpoonup \overline{\mathsf{x}}_1$ and $\mathsf{u}_{2,n}\rightharpoonup \overline{\mathsf{x}}_2$, where $(\overline{\mathsf{x}}_1,\overline{\mathsf{x}}_2)$ is a solution to Problem 4.3.

Proof

It follows from [30, Theorem 16.2] that Problem 4.3 can be written equivalently as the problem of finding $\mathsf{x}_1$ and $\mathsf{x}_2$ such that $0\in \partial (\iota _{\mathsf{S}_1}+\mathsf{f}(\cdot ,\mathsf{x}_2))(\mathsf{x}_1)$ and $0\in \partial (\iota _{\mathsf{S}_2}-\mathsf{f}(\mathsf{x}_1,\cdot ))(\mathsf{x}_2)$, or, equivalently, such that $0\in N_{\mathsf{S}_1}(\mathsf{x}_1)+\nabla \big (\mathsf{f}(\cdot , \mathsf{x}_2)\big )(\mathsf{x}_1)$ and $0\in N_{\mathsf{S}_2}(\mathsf{x}_2)- \nabla \big (\mathsf{f}(\mathsf{x}_1,\cdot )\big )(\mathsf{x}_2)$ [30, Corollary 16.38]. Now since, for every $i\in \{1,2\}$, $\mathsf{S}_i=\mathsf{C}_i\cap \mathsf{L}_i^{-1}(\mathsf{b}_i)=\mathsf{C}_i\cap (\mathsf{e}_i+\ker \mathsf{L}_i)$, it follows from qualification conditions that Problem 4.3 is equivalent to

$$\begin{aligned}&0\in N_{\mathsf{C}_1}(\mathsf{e}_1+\mathsf{z}_1)+ N_{\ker \mathsf{L}_1}(\mathsf{z}_1)+\nabla \big (\mathsf{f}(\cdot , \mathsf{e}_2+\mathsf{z}_2)\big )(\mathsf{e}_1+\mathsf{z}_1)\nonumber \\&0\in N_{\mathsf{C}_2}(\mathsf{e}_2+\mathsf{z}_2)+ N_{\ker \mathsf{L}_2}(\mathsf{z}_2)-\nabla \big ( \mathsf{f}(\mathsf{e}_1+\mathsf{z}_1,\cdot )\big )(\mathsf{e}_2+\mathsf{z}_2), \end{aligned}$$

(42)

where $\mathsf{z}_1:=\mathsf{x}_1-\mathsf{e}_1$ and $\mathsf{z}_2:=\mathsf{x}_2-\mathsf{e}_2$. Hence, by defining $V:=\ker (\mathsf{L}_1)\times \ker (\mathsf{L}_2)$ and, for every $(\mathsf{z}_1,\mathsf{z}_2)\in \mathsf{H}_1\times \mathsf{H}_2$,

$$\begin{aligned} A(\mathsf{z}_1,\mathsf{z}_2)&:= N_{\mathsf{C}_1\times \mathsf{C}_2} (\mathsf{e}_1+\mathsf{z}_1,\mathsf{e}_2+\mathsf{z}_2)\nonumber \\ B(\mathsf{z}_1,\mathsf{z}_2)&:= \begin{pmatrix} \nabla \big (\mathsf{f}(\cdot ,\mathsf{e}_2+\mathsf{z}_2)\big )(\mathsf{e}_1+\mathsf{z}_1)\\ -\nabla \big (\mathsf{f}(\mathsf{e}_1+\mathsf{z}_1,\cdot )\big )(\mathsf{e}_2+\mathsf{z}_2) \end{pmatrix}, \end{aligned}$$

(43)

Problem 4.3 is equivalent to find $\mathsf{z}_1\in \mathsf{H}_1$ and $\mathsf{z}_2\in \mathsf{H}_2$ such that $0\in A(\mathsf{z}_1,\mathsf{z}_2)+B(\mathsf{z}_1,\mathsf{z}_2)+ N_V(\mathsf{z}_1,\mathsf{z}_2)$. Note that $V$ is a closed vector subspace of $\mathsf{H}_1\times \mathsf{H}_2$, $A$ is maximally monotone [30, Proposition 20.22], and $B$ is monotone ([30, Proposition 20.22] and [41]). Moreover, since $\nabla \mathsf{f}$ is $\chi$-Lipschitzian, $B$ is also $\chi$-Lipschitzian. On the other hand, it follows from [30, Proposition 3.28 (iii)] and [30, Proposition 23.15 (iii)] that, for every $(\mathsf{z}_1,\mathsf{z}_2)\in \mathsf{H}_1\times \mathsf{H}_2$, $P_V(\mathsf{z}_1,\mathsf{z}_2)=\big (\mathsf{z}_1- \mathsf{L}_1^*\mathsf{L}_1^{*\dagger }\mathsf{z}_1,\mathsf{z}_2- \mathsf{L}_2^*\mathsf{L}_2^{*\dagger }\mathsf{z}_2\big )$, $J_{\gamma A}(\mathsf{z}_1,\mathsf{z}_2) =\big (P_{\mathsf{C}_1}(\mathsf{z}_1 +\mathsf{e}_1)-\mathsf{e}_1,P_{\mathsf{C}_2}(\mathsf{z}_2 +\mathsf{e}_2)-\mathsf{e}_2\big )$, and we deduce that (41) is a particular case of (21) when $A$, $B$, and $V$ are defined as before. Altogether, the result follows from Corollary 3.1. $\square$

Remark 4.3

The proposed method does not need to compute the projection onto $\mathsf{S}_1$ and $\mathsf{S}_2$ at each iteration, but it converges to solution strategies belonging to these sets. This new feature is very useful when the projection onto $\mathsf{S}_1$ and $\mathsf{S}_2$ are not easy to compute.

Example 4.1

We consider a $2$-player, zero-sum game, where $X_1\subset {\mathbb {R}}^{N_1}$ is a bounded set of pure strategies for player $1$ and $S_1:=\big \{{f\in L^2(X_1)} : {f\ge 0\,\text {a.e.},\int _{X_1}f(x)\mathrm{d}x=1}\big \}$ is her set of mixed strategies ($X_2$, $N_2$, and $S_2$ are defined likewise). We recall that $L^2(X)$ stands for the set of square-integrable functions $f: X\subset {\mathbb {R}}^n\rightarrow \,\big ]-\infty ,+\infty \big ]$. Moreover, let $F\in L^2(X_1\times X_2)$ be a function representing the payoff for player 1, and let $-F$ be the payoff of player 2. The problem is to

$$\begin{aligned}&\text {find}\,\, f_1\in S_1\,\,\,\text {and}\,\,\,f_2\in S_2 \,\,\text {such that}\,\,\nonumber \\&\quad {\left\{ \begin{array}{ll} f_1\in \underset{\begin{array}{c} {g_1\in S_1} \end{array}}{\mathrm{Argmin}}\;\;\displaystyle {\int _{X_1}\int _{X_2}F(x_1,x_2)g_1(x_1)f_2(x_2)\mathrm{d}x_2\mathrm{d}x_1} \\ f_2\in \underset{\begin{array}{c} {g_2\in S_2} \end{array}}{\mathrm{Argmax}}\;\;\displaystyle {\int _{X_1}\int _{X_2}F(x_1,x_2)f_1(x_1)g_2(x_2)\mathrm{d}x_2\mathrm{d}x_1} . \end{array}\right. } \end{aligned}$$

(44)

Note that $S_1$ and $S_2$ are closed and convex sets in $L^2(X_1)$ and $L^2(X_2)$, respectively. Hence, the projection of any square-integrable function onto $S_1$ or $S_2$ is well defined. However, these projections are not easy to compute. A possible way for avoiding the explicit computation of these projections is to split $S_1$ and $S_2$ in $S_1=\mathsf{C}_1\cap (\mathsf{e}_1+\ker \mathsf{L}_1)$ and $S_2=\mathsf{C}_2\cap (\mathsf{e}_2+\ker \mathsf{L}_2)$, as in the proof of Theorem 4.3, where, for every $i\in \{1,2\}$, $\mathsf{H}_i:=L^2(X_i)$, $\mathsf{C}_i:=\big \{{f\in \mathsf{H}_i} : {f\ge 0\quad \text {a.e.}}\big \}$, $\mathsf{e}_i:=(m_i(X_i))^{-1}$, $\mathsf{L}_i: f\mapsto \int _{X_i}f(x)\mathrm{d}x$, and $m_i(X_i)$ is the Lebesgue measure of the set $X_i$. Moreover, define the bilinear differentiable function $\mathsf{f}:(f_1,f_2)\mapsto \int _{X_1}\int _{X_2}F(x_1,x_2)f_1(x_1)f_2(x_2)\mathrm{d}x_2\mathrm{d}x_1$. It follows from $F\in L^2(X_1\times X_2)$ that

$$\begin{aligned} \!\!\nabla \mathsf{f}:(f_1,f_2)\!\mapsto \! \Big (\int _{X_2}F(\cdot ,x_2)f_2(x_2)\mathrm{d}x_2, \int _{X_1}F(x_1,\cdot )f_1(x_1)\mathrm{d}x_1\Big )\!\in \!\mathsf{H}_1\times \mathsf{H}_2,\qquad \end{aligned}$$

(45)

and that $\nabla \mathsf{f}$ is $\chi$-Lipschitzian with $\chi :=\Vert F\Vert _{L^2(X_1\times X_2)}$. Thus, (44) is a particular instance of Problem 4.3. Note that, for every $i\in \{1,2\}$, $\mathsf{L}_i^*:{\mathbb {R}}\rightarrow L^2(X_i):\xi \mapsto \delta _{\xi }$, where, for every $\xi \in {\mathbb {R}}$, $\delta _{\xi }: x\mapsto \xi$ is the constant function. Moreover, $\mathsf{L}_i\circ \mathsf{L}_i^*:\xi \rightarrow m_i(X_i)\xi$ is invertible and $(\mathsf{L}_i\circ \mathsf{L}_i^*)^{-1}:\xi \mapsto \xi /m_i(X_i)$, which yields $\mathrm{Id }-\mathsf{L}_i^*\mathsf{L}_i^{*\dagger }=\mathrm{Id }-\mathsf{L}_i^*(\mathsf{L}_i\circ \mathsf{L}_i^*)^{-1}\mathsf{L}_i: f\mapsto f-\delta _{\bar{f}}$, where $\bar{f}=\int _{X_i}f(x)\mathrm{d}x/m_i(X_i)$ is the mean value of $f$. In addition, for every $i\in \{1,2\}$, $P_{\mathsf{C}_i}: f\mapsto f_+: t\mapsto \max \{0,f(t)\}$. Altogether, Algorithm 4.3 applied to this instance is a fully split method for solving (44). In the particular case when $X_1$ and $X_2$ are finite sets of actions (or pure strategies), $S_1$ and $S_2$ are finite dimensional simplexes, $F: (x_1,x_2)\mapsto x_1^{\top }\mathsf{F}x_2$, and $\mathsf{F}$ is a payoff matrix, Algorithm 4.3 provides a first order method for finding Nash equilibria in the finite zero-sum game (for complements and background on finite games, see [42])

$$\begin{aligned} \text {find}\quad x_1\in S_1\,\,\,\text {and}\,\,\,x_2\in S_2 \quad \text {such that}\quad {\left\{ \begin{array}{ll} x_1\in \underset{\begin{array}{c} {y_1\in S_1} \end{array}}{\mathrm{Argmin}}\;\;x_1^{\top }\mathsf{F}x_2 \\ x_2\in \underset{\begin{array}{c} {y_2\in S_2} \end{array}}{\mathrm{Argmax}}\;\;x_1^{\top }\mathsf{F}x_2 . \end{array}\right. } \end{aligned}$$

(46)

When a large number of pure actions are involved (e.g., Texas Hold’em poker), classical linear programming methods for solving (44) are enormous and unsolvable via standard algorithms as simplex. Other attempts use acceleration schemes for obtaining good convergence rates [21]. However, the proposed method does not guarantee the convergence of the iterates. Algorithm 4.3 is an explicit convergent method that solves (46) overcoming previous difficulties. Numerical simulations and comparisons with other methods are part of further research.

5 Conclusions

We provide a fully split algorithm for finding a zero of $A+B+N_V$. The proposed method exploits the intrinsic properties of each of the operators involved, by explicitly activating the single-valued operator $B$ and by computing the resolvent of $A$ and projections onto $V$. Weak convergence to a zero of $A+B+N_V$ is guaranteed, and the flexibility of our framework is illustrated via applications to monotone inclusions involving $m$ maximally monotone operators, to primal-dual composite inclusions involving partial sums of monotone operators, and to continuous zero-sum games. It is worth mentioning that the three applications studied in this paper use different closed vector subspaces: the diagonal vector subspace in a product Hilbert space, the product of vector subspaces, and the kernel of a linear bounded operator. In addition, it follows from Remark 3.2 (iii) that it is possible to tackle very complex monotone inclusions, including compositions with linear operators, by using the kernel of appropriate bounded linear operators as closed vector subspaces. The influence of the linear operators of the original inclusion can be split from the other operators involved via these closed vector subspaces. The resulting algorithm shall need to compute inverses of suitable linear operators, which can be obtained easily without perturbing the efficiency of the method in several cases [33]. Altogether, the flexibility of the vector subspace setting gives a promising future to splitting methods involving this feature. It is part of further research to study the performance of the methods under specific assumptions of each problem. On the other hand, the partial sum of two set-valued operators with respect to a closed vector subspace is introduced. This operation preserves monotonicity, and further study will be done in this direction in future work. Finally, in zero-sum games, a splitting method is provided for computing Nash equilibria. The algorithm replaces the projections onto mixed strategy spaces by simpler projections.