# Convergence of Two Simple Methods for Solving Monotone Inclusion Problems in
Reflexive Banach Spaces

Chinedu Izuchukwu1, Simeon Reich2, Yekini Shehu3

###### Abstract.

We propose two very simple methods, the first one with constant step sizes and
the second one with self-adaptive step sizes, for finding a zero of the sum of
two monotone operators in real reflexive Banach spaces. Our methods require
only one evaluation of the single-valued operator at each iteration. Weak
convergence results are obtained when the set-valued operator is maximal
monotone and the single-valued operator is Lipschitz continuous, and strong
convergence results are obtained when either one of these two operators is
required, in addition, to be strongly monotone. We also obtain the rate of
convergence of our proposed methods in real reflexive Banach spaces. Finally,
we apply our results to solving generalized Nash equilibrium problems for gas
markets.

Keywords: Forward-backward type method; monotone inclusion; weak convergence;
strong convergence; Banach spaces.

2020 MSC classification: 47H05, 47J20, 47J25, 65K15, 90C25.

###### Key words and phrases:

Bregman resolvent; forward-backward splitting method; gas market; generalized
Nash equilibrium problem; maximal monotone operator; monotone inclusion;
reflexive Banach space.
2010 Mathematics Subject Classification: 47H09; 47H10; 49J20; 49J40

1,2Department of Mathematics, The Technion – Israel Institute of Technology,
32000 Haifa, Israel.
3College of Mathematics and Computer Science, Zhejiang Normal University,
Jinhua 321004, People’s Republic of China.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
##  1\. Introduction

Let $\mathbb{X}^{*}$ be the dual of a real reflexive Banach space $\mathbb{X}$
and let $\mathcal{B}:\mathbb{X}\to 2^{\mathbb{X}^{*}}$ be a set-valued
operator. The Null Point Problem (NPP) is formulated as follows:

(1.1) $\displaystyle\mbox{Find}~{}v\in\mathbb{X}~{}\mbox{such
that}~{}0^{*}\in\mathcal{B}v.$

This problem is very important in optimization theory and related fields. Many
optimization problems such as minimization problems, equilibrium problems, and
saddle point problems, can be modelled as Problem (1.1). For instance, if
$\mathcal{B}$ is the subdifferential of a proper, convex and lower
semicontinuous function, then Problem (1.1) is equivalent to the problem of
minimizing this convex function. Also, Problem (1.1) describes the equilibrium
or stable state of an evolution system governed by the operator $\mathcal{B}$,
which is very important in ecology, physics and economics, as well as in other
fields (see [11]). One of the most popular methods for solving Problem (1.1)
is the Proximal Point Algorithm (PPA), which was introduced in Hilbert spaces
by Martinet [21] in 1970. The PPA was further developed by Rockafellar [32]
and Bruck and Reich [8] in 1976 and 1977, respectively. Since then, the PPA
has been modified by several authors in order to solve Problem (1.1) (see, for
example, [3, 23, 29, 30, 31]). We mention, in particular, the paper by Reich
and Sabach [30]. The authors of this paper introduced the following
modification of the PPA for solving Problem (1.1) in a reflexive Banach space:

(1.2) $\displaystyle\begin{cases}x_{1}\in\mathbb{X}\\\
y_{n}=\mbox{Res}^{g}_{\mu_{n}\mathcal{B}}(x_{n})\\\
C_{n}=\\{z\in\mathbb{X}:D_{g}(z,y_{n})\leq D_{g}(z,x_{n})\\}\\\
Q_{n}=\\{z\in\mathbb{X}:\langle\nabla g(x_{1})-\nabla
g(x_{n}),z-x_{n}\rangle\leq 0\\}\\\ x_{n+1}=\mbox{Proj}^{g}_{C_{n}\cap
Q_{n}}(x_{1}),~{}n\geq 1,\end{cases}$

where $\\{\mu_{n}\\}$ is a given sequence of positive real numbers,
$\mbox{Res}^{g}_{\mathcal{B}}$ is the resolvent of $\mathcal{B}$, $\nabla g$
is the gradient of $g$ and $\mbox{Proj}^{g}_{\mathcal{C}}$ is the Bregman
projection of $\mathbb{X}$ onto a nonempty, closed and convex subset
$\mathcal{C}$ of $\mathbb{X}$.
In the same paper, the authors studied two extensions of Algorithm (1.2) that
solve Problem (1.1) for finitely many maximal monotone operators in real
reflexive Banach spaces.

Continuing the work of Reich and Sabach [30], Ogbuisi and Izuchukwu [25]
studied the following inclusion problem in a reflexive Banach space
$\mathbb{X}$:

(1.3) $\displaystyle\mbox{Find}~{}v\in\mathbb{X}~{}\mbox{such
that}~{}0^{*}\in\left(\mathcal{A}+\mathcal{B}\right)v,$

where $\mathcal{A}:\mathbb{X}\rightarrow\mathbb{X}^{*}$ is a single-valued
operator and $\mathcal{B}$ is as defined in (1.1).
If the operators are monotone, then Problem (1.3) can be referred to as a
Monotone Inclusion Problem (MIP). It is worth mentioning that if
$\mathcal{B}=N_{\mathcal{C}}$ in Problem (1.3), where $N_{\mathcal{C}}$ is the
normal cone associated with a nonempty, closed and convex subset $\mathcal{C}$
of $\mathbb{X}$, then Problem (1.3) reduces to the classical variational
inequality problem. Also, when $\mathcal{A}=0$, we recover the NPP (1.1) as a
special case of Problem (1.3). Furthermore, several problems in signal
processing, image recovery and machine learning can be formulated as Problem
(1.3). Therefore, we see that Problem (1.3) is quite general; it naturally
includes many other important optimization problems such as minimization
problems, linear inverse problems, saddle-point problems, fixed point
problems, split feasibility problems, Nash equilibrium problems in
noncooperative games, and many more. Several authors have studied Problem
(1.3) using the well-known forward-backward splitting method and its
modifications in real Hilbert spaces (see, for instance, [1, 12, 17, 37, 28,
19]).
In order to solve Problem (1.3) in reflexive Banach spaces, Ogbuisi and
Izuchukwu [25] proposed the following iterative method:

(1.4) $\displaystyle\begin{cases}u,x_{1}\in C,~{}~{}C_{1}=C\\\ y_{n}=\nabla
g^{*}\left(\alpha_{n}\nabla g(u)+\beta_{n}\nabla g(x_{n})+\gamma_{n}\nabla
g(T(x_{n}))\right)\\\ u_{n}=(\mbox{Res}^{g}_{\mu\mathcal{B}}\circ
A^{g}_{\mu})y_{n}\\\ C_{n+1}=\\{z\in
C_{n}:D_{g}(z,u_{n})\leq\alpha_{n}D_{g}(z,u)+(1-\alpha_{n})D_{g}(z,x_{n})\\}\\\
x_{n+1}=\mbox{Proj}^{g}_{C_{n+1}}(x_{1}),~{}n\geq 1,\end{cases}$

where $\mu>0$, $\\{\alpha_{n}\\},~{}\\{\beta_{n}\\}$ and $\\{\gamma_{n}\\}$
are sequences in $(0,1)$, $A_{\mu}^{g}:=\nabla g^{*}\circ(\nabla
g-\mu\mathcal{A})$ and $T$ is a Bregman strongly nonexpansive mapping.
These authors proved that the sequence generated by Algorithm (1.4) converges
to a common solution of Problem (1.3) and the fixed point problem for the
mapping $T$, provided that the solution set of the problem is nonempty,
$\mathcal{A}$ is Bregman inverse strongly monotone, $\mathcal{B}$ is maximal
monotone,
$\lim_{n\to\infty}\alpha_{n}=0,~{}\alpha_{n}+\beta_{n}+\gamma_{n}=1$, and
$0<a<\beta_{n},\gamma_{n}<b<1$.
Recently, Chang et al. [10] proposed a method similar to (1.4) (see [10,
Algorithm (11)] for solving Problem (1.3) when $\mathcal{A}$ is Bregman
inverse strongly monotone and $\mathcal{B}$ is maximal monotone. Other recent
methods for solving the MIP (1.3), under the same assumptions on $\mathcal{A}$
and $\mathcal{B}$ in reflexive Banach spaces, can be found in [24, 26, 27, 36,
38].

Very recently, Sunthrayuth et al. [35] proposed the following modification of
Tseng’s splitting method [37] for solving Problem (1.3) in a reflexive Banach
space when $\mathcal{A}$ is monotone and Lipschitz continuous, and
$\mathcal{B}$ is maximal monotone:

(1.5) $\displaystyle\begin{cases}x_{1}\in\mathbb{X}\\\
y_{n}=\mbox{Res}^{g}_{\mu_{n}\mathcal{B}}\nabla g^{*}\left(\nabla
g(x_{n})-\mu_{n}\mathcal{A}x_{n}\right)\\\ z_{n}=\nabla g^{*}\left(\nabla
g(y_{n})-\mu_{n}(\mathcal{A}y_{n}-\mathcal{A}x_{n})\right)\\\ x_{n+1}=\nabla
g^{*}\left((1-\alpha_{n})\nabla g(z_{n})+\alpha_{n}\nabla
g(Tz_{n}))\right),~{}n\geq 1,\end{cases}$

where $\\{\alpha_{n}\\}$ is a sequence in $(0,1)$, $\mu_{n}=\gamma l^{m_{n}}$
and $m_{n}$ is the smallest nonnegative integer such that

(1.6)
$\displaystyle\mu_{n}||\mathcal{A}x_{n}-\mathcal{A}y_{n}||\leq\mu||x_{n}-y_{n}||,$

with $\gamma>0,l\in(0,1),\mu\in(0,\alpha)$ and $\alpha>0$.
Furthermore, they proposed a variant of (1.5)–(1.6) by replacing only (1.6)
with a self-adaptive step size procedure (see [35, Algorithm 2]) for solving
Problem (1.3) under the same assumptions on $\mathcal{A}$ and $\mathcal{B}$ in
a reflexive Banach space.
At this point we mention another modification of Tseng’s splitting method due
to Shehu [34] for solving the MIP (1.3) in the context of $2$-uniformly convex
and uniformly smooth Banach spaces, when $\mathcal{A}$ is monotone and
Lipschitz continuous, and $\mathcal{B}$ is maximal monotone.
Unfortunately, all these methods for solving the MIP (1.3), when $\mathcal{A}$
is monotone and Lipschitz continuous in reflexive Banach spaces, require at
each iteration at least two evaluations of $\mathcal{A}$ and this might affect
the efficiency of these methods especially in situations where evaluating the
operator $\mathcal{A}$ is expensive, for instance, in problems arising from
optimal control.

In this paper, inspired by the results in [10, 25, 19, 34, 35], we propose two
methods for solving the MIP (1.3) in real reflexive Banach spaces. Our methods
have simple and elegant structures, and they only require one evaluation of
$\mathcal{A}$ at each iteration. We obtain weak convergence results when
$\mathcal{B}$ is maximal monotone and $\mathcal{A}$ is Lipschitz continuous,
and we obtain strong convergence results when either $\mathcal{A}$ or
$\mathcal{B}$ is required, in addition, to be strongly monotone. We also
obtain the rate of convergence of our proposed methods in real reflexive
Banach spaces and apply our results to solving generalized Nash equilibrium
problems for gas markets.

The rest of our paper is organized as follows: Section 2 contains basic
definitions and results. In Section 3, we present and discuss the methods we
propose. In Section 4, we obtain some convergence results for our methods. As
special cases, we also obtain methods for solving the NPP (1.1) and the
variational inequality problem. In Section 5, we consider a generalized Nash
equilibrium approach for modelling gas markets and apply our results to
solving this problem. We then give some concluding remarks in Section 6.

##  2\. Preliminaries

Let $\mathbb{X}$ be a real reflexive Banach space and let $\mathbb{X}^{*}$ be
its dual. Let $g:\mathbb{X}\to(-\infty,+\infty]$ be a function. The domain of
$g$, denoted by ${dom}_{g}$, is defined by
${dom}_{g}:=\\{x\in\mathbb{X}:g(x)<+\infty\\}$. The function
$g:\mathbb{X}\to(-\infty,+\infty]$ is called proper if
${dom}_{g}\neq\emptyset$, and convex if $g(\lambda x+(1-\lambda)y)\leq\lambda
g(x)+(1-\lambda)g(y)\;~{}\forall x,y\in\mathbb{X},~{}\lambda\in(0,1)$. A
function $g:{dom}_{g}\subseteq\mathbb{X}\to(-\infty,\infty]$ is said to be
lower semicontinuous at a point $x\in{dom}_{g}$, if
$g(x)\leq\liminf_{n\to\infty}g(x_{n})$ for each sequence $\\{x_{n}\\}$ in
${dom}_{g}$ such that $\underset{n\to\infty}{\lim}x_{n}=x$. It is is said to
be lower semicontinuous on ${dom}_{g}$ if it is lower semicontinuous at each
point in ${dom}_{g}$.

The Fenchel conjugate of $g$ is the function
$g^{*}:\mathbb{X}^{*}\to(-\infty,\infty]$ defined by

$g^{*}(x^{*}):=\sup\\{\langle x^{*},x\rangle-g(x):x\in\mathbb{X}\\}.$

Let $x\in$ $int({dom}_{g})$, where $int({dom}_{g})$ stands for the interior of
the domain of $g$. Then for any $y\in\mathbb{X}$, we define the right-hand
derivative of $g$ at $x$ by

(2.1) $\displaystyle g^{\prime}(x,y):=\lim_{\lambda\to 0^{+}}\frac{g(x+\lambda
y)-g(x)}{\lambda}.$

The function $g$ is said to be Gâteaux differentiable at $x$ if the limit in
(2.1) exists as $\lambda\to 0$ for each $y\in\mathbb{X}$. In this case, the
gradient of $g$ at $x$ is the linear function $\nabla g(x)$, defined by
$\langle\nabla g(x),y\rangle:=g^{\prime}(x,y)~{}\forall y\in\mathbb{X}$. We
say that $g$ is Gâteaux differentiable if it is Gâteaux differentiable at each
$x\in$ $int({dom}_{g})$. If the limit in (2.1) is attained uniformly for
$y\in\mathbb{X}$ with $||y||=1$, we say that $g$ is Fréchet differentiable at
$x$. If the limit in (2.1) is attained uniformly for $x\in\mathcal{C}$ and for
$y\in\mathbb{X}$ with $||y||=1$, then we say that the function $g$ is
uniformly Fréchet differentiable on the subset $\mathcal{C}$ of $\mathbb{X}$.
The function $g$ is said to be Legendre if it satisfies the following two
conditions.

  1. (i)

$g$ is Gâteaux differentiable, $int({dom}_{g})\neq\emptyset$ and
${dom}_{\nabla g}=$ $int({dom}_{g})$;

  2. (ii)

$g^{*}$ is Gâteaux differentiable, $int({dom}_{g^{*}})\neq\emptyset$ and
${dom}_{\nabla g^{*}}=$ $int({dom}_{g^{*}})$.

It is well known that $\nabla g=(\nabla g^{*})^{-1}$ in reflexive Banach
spaces. Combining this fact with conditions (i) and (ii), we get that
${ran}_{\nabla g}={dom}_{\nabla g^{*}}=$ $int({dom}_{g^{*}})$ and
${ran}_{\nabla g^{*}}={dom}_{\nabla g}=int({dom}_{g})$, where ${ran}_{g}$
denotes the range of $g$.
We also know that conditions (i) and (ii) imply that the functions $g$ and
$g^{*}$ are Gâteaux differentiable and strictly convex in the interior of
their respective domains. Hence, $g$ is Legendre if and only if $g^{*}$ is
Legendre.

The bifunction $D_{g}:{dom}_{g}\times{int({dom}_{g})}\to[0,+\infty)$, defined
by

(2.2) $\displaystyle D_{g}(x,y):=g(x)-g(y)-\langle\nabla g(y),x-y\rangle,$

is called a Bregman distance. If $g$ is a Gâteaux differentiable function,
then the Bregman distance has the following important property, called the
three point identity: for any $x\in{dom}_{g}$ and $y,z\in{int({dom}_{g})}$,

(2.3) $\displaystyle D_{g}(x,y)+D_{g}(y,z)-D_{g}(x,z)=\langle\nabla
g(z)-\nabla g(y),x-y\rangle.$

A Gâteaux differentiable function $g$ is called strongly convex (see [5, 22]),
if there exists $\gamma>0$ such that $\langle\nabla g(x)-\nabla
g(y),x-y\rangle\geq\gamma||x-y||^{2}$ or equivalently, $g(y)\geq
g(x)+\langle\nabla g(x),y-x\rangle+\frac{\gamma}{2}||x-y||^{2}\;~{}\forall
x,y\in{dom}_{g}$.

######  Remark 2.1.

If $g$ is a strongly convex function with constant $\gamma>0$, then

(2.4) $\displaystyle D_{g}(x,y)\geq\frac{\gamma}{2}||x-y||^{2}~{}\forall
x\in{dom}_{g},~{}y\in{int({dom}_{g})}.$

The function $g:\mathbb{X}\to\mathbb{R}\cup\\{+\infty\\}$ is said to be
strongly coercive if

$\lim_{||x||\to\infty}\frac{g(x)}{||x||}=+\infty.$

######  Remark 2.2.

(see [9]). If $g:\mathbb{X}\to\mathbb{R}$ is strongly coercive, then

  1. (i)

$\nabla g:\mathbb{X}\to\mathbb{X}^{*}$ is one-to-one, onto and norm-to-weak*
continuous;

  2. (ii)

$\\{x\in\mathbb{X}:D_{g}(x,y)\leq r\\}$ is bounded for all $y\in\mathbb{X}$
and $r>0$;

  3. (iii)

${dom}_{g^{*}}=\mathbb{X}^{*}$, $g^{*}$ is Gâteaux differentiable and $\nabla
g^{*}=(\nabla g)^{-1}$.

The operator $\mathcal{A}:\mathbb{X}\rightarrow\mathbb{X}^{*}$ is said to be
$L$-Lipschitz continuous if there exists $L>0$ such that

$\displaystyle\|\mathcal{A}x-\mathcal{A}y\|\leq L\|x-y\|~{}\forall
x,y\in\mathbb{X}.$

$A$ is called $\tau$-strongly monotone if there exists $\tau>0$ such that

$\displaystyle\langle\mathcal{A}x-\mathcal{A}y,x-y\rangle\geq\tau\|x-y\|^{2}~{}\forall
x,y\in\mathbb{X},$

and monotone if

$\displaystyle\langle\mathcal{A}x-\mathcal{A}y,x-y\rangle\geq 0\;~{}\forall
x,y\in\mathbb{X}.$

If $\mathcal{B}$ is a set-valued operator, that is,
$\mathcal{B}:\mathbb{X}\rightarrow 2^{\mathbb{X}^{*}}$, then $\mathcal{B}$ is
called $\tau$-strongly monotone if there exists $\tau>0$ such that

$\displaystyle\langle u-v,x-y\rangle\geq\tau\|x-y\|^{2}~{}\forall
x,y\in\mathbb{X},~{}u\in\mathcal{B}x,~{}v\in\mathcal{B}y,$

and monotone if

$\langle u-v,x-y\rangle\geq 0\;~{}\forall
x,y\in\mathbb{X},~{}u\in\mathcal{B}x,~{}v\in\mathcal{B}y.$

The monotone operator $\mathcal{B}$ is said to be maximal if the graph
$G(\mathcal{B})$ of $\mathcal{B}$, defined by

$G(\mathcal{B}):=\\{(x,y)\in\mathbb{X}\times\mathbb{X^{*}}:y\in\mathcal{B}x\\},$

is not properly contained in the graph of any other monotone operator. In
other words, $\mathcal{B}$ is maximal monotone if and only if for
$(x,u)\in\mathbb{X}\times\mathbb{X}^{*}$, the assumption that $\langle
u-v,x-y\rangle\geq 0$ for all $(y,v)\in G(\mathcal{B})$ implies that
$u\in\mathcal{B}x$. It is known [4, Corollary 2.4] that if
$g:\mathbb{X}\to\mathbb{R}$ is Gâteaux differentiable, strictly convex and
cofinite, then $\mathcal{B}$ is maximal monotone if and only if
${ran}_{(\nabla g+\mu\mathcal{B})}=\mathbb{X}^{*}$.
Let $g:\mathbb{X}\to\mathbb{R}$ be a Gâteaux differentiable function on
$\mathbb{X}$. Then the resolvent operator $\mbox{Res}_{\mu\mathcal{B}}^{g}$
associated with a set-valued operator $\mathcal{B}$ and $\mu>0$, and relative
to $g$, is the mapping $\mbox{Res}_{\mu\mathcal{B}}^{g}:\mathbb{X}\rightarrow
2^{\mathbb{X}}$ defined by

(2.5) $\displaystyle\mbox{Res}_{\mu\mathcal{B}}^{g}:=(\nabla
g+\mu\mathcal{B})^{-1}\circ\nabla g.$

The resolvent operator is single-valued when $\mathcal{B}$ is monotone and $g$
is strictly convex on $int({dom}_{g})$.

Let $\mathcal{C}$ be a nonempty, closed and convex subset of a reflexive
Banach space $\mathbb{X}$. The mapping $\mathcal{A}:\mathbb{X}\to
2^{\mathbb{X}^{*}}$ is said to be Bregman inverse strongly monotone on the set
$\mathcal{C}$ if $\mathcal{C}\cap({dom}_{g})\cap int({dom}_{g})\neq\emptyset$
and for any $x,y\in\mathcal{C}\cap int({dom}_{g})$, $\xi\in\mathcal{A}x$ and
$\eta\in\mathcal{A}y$, we have $\langle\xi-\eta,\nabla g^{*}(\nabla
g(x)-\xi)-\nabla g^{*}(\nabla g(y)-\eta)\rangle\geq 0.$

Let $g:\mathbb{X}\to\mathbb{R}\cup\\{+\infty\\}$ be a convex and Gâteaux
differentiable function, and let $\mathcal{C}$ be a nonempty, closed and
convex subset of a real reflexive Banach space $\mathbb{X}$. The Bregman
projection of $x\in int({dom}_{g})$ onto $\mathcal{C}\subset int({dom}_{g})$
is the unique vector ${Proj}^{g}_{\mathcal{C}}(x)\in\mathcal{C}$ satisfying
(see [6])
$D_{g}\left({Proj}^{g}_{\mathcal{C}}(x),x\right)=\inf\\{D_{g}(y,x):y\in\mathcal{C}\\}.$
The normal cone of $\mathcal{C}$ at a point $z\in\mathbb{X}$ is defined by

(2.6) $\displaystyle N_{\mathcal{C}}z:=\\{d^{*}\in\mathbb{X}^{*}:\langle
d^{*},y-z\rangle\leq 0\;~{}~{}\forall
y\in\mathcal{C}\\}\;~{}\mbox{if}~{}z\in\mathcal{C}~{}~{}\mbox{and}~{}\emptyset,~{}\mbox{otherwise}.$

######  Lemma 2.3.

[20] Let $g:\mathbb{X}\to\mathbb{R}$ be a proper, convex, lower semicontinuous
and Gâteaux differentiable on $int({dom}_{g})$ such that $\nabla g^{*}$ is
bounded on bounded subsets of ${dom}_{g^{*}}$. Let $x^{*}\in\mathbb{X}$ and
$\\{x_{n}\\}\subset$ $\mathbb{X}$. If $\\{D_{g}(x,x_{n})\\}$ is bounded, so is
the sequence $\\{x_{n}\\}$.

######  Lemma 2.4.

[15] Let $\mathbb{X}$ be a Banach space, and let
$g:\mathbb{X}\to(-\infty,\infty]$ be a proper and strictly convex function
such that $g$ is Gâteaux differentiable. Suppose that there exists a point
$p\in\mathbb{X}$ such that the sequence $\\{x_{n}\\}$ in $\mathbb{X}$
converges weakly to $p$. Then

$\limsup_{n\to\infty}D_{g}(p,x_{n})<\limsup_{n\to\infty}D_{g}(q,x_{n})$

for all $q\in{int({dom}_{g})}$ with $p\neq q$.

######  Lemma 2.5.

[2, Corollary 2.1 and Theorem 1.7] Let
$\mathcal{A}:\mathbb{X}\rightarrow\mathbb{X}^{*}$ be a monotone and Lipschitz
continuous operator, and let $\mathcal{B}:\mathbb{X}\rightarrow
2^{\mathbb{X}^{*}}$ be a maximal monotone operator. Then
$\mathcal{A}+\mathcal{B}$ is maximal monotone.

##  3\. Proposed Methods

In this section we present our proposed methods for solving the MIP (1.3).
Throughout this section we assume that the solution set of (1.3) is nonempty,
that is, $(\mathcal{A}+\mathcal{B})^{-1}(0^{*})\neq\emptyset$. We also assume
for the rest of this paper that the function
$g:\mathbb{X}\to\mathbb{R}\cup\\{+\infty\\}$ is proper, convex, lower
semicontinuous, uniformly Fréchet differentiable, $\gamma$-strongly convex,
strongly coercive and Legendre. In addition, we make the following
assumptions.

######  Assumption 3.1.

Let $\mathbb{X}$ be a real reflexive Banach space $\mathbb{X}$, let
$\mathbb{X}^{*}$ denote its dual, and let
$\mathcal{A}:\mathbb{X}\to\mathbb{X}^{*}$ and $\mathcal{B}:\mathbb{X}\to
2^{\mathbb{X}^{*}}$ be two operators satisfying the following conditions:

  * (a)

$\mathcal{A}$ is monotone on $\mathbb{X}$ and $\mathcal{B}$ is maximal
monotone on $\mathbb{X}$,

  * (b)

$\mathcal{A}$ is Lipschitz continuous on $\mathbb{X}$ with constant $L>0$.

When $L$ is known, we present the following method for solving the inclusion
problem (1.3).

######  Algorithm 3.2.

For arbitrary $v_{0},v_{1}\in\mathbb{X}$ and $\mu>0$, define the sequence
$\\{v_{n}\\}$ by

$\displaystyle v_{n+1}={Res}^{g}_{\mu\mathcal{B}}\Big{(}\nabla g^{*}(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1}))\Big{)},~{}n\geq 1.$

When $L$ is unknown, we present the method below with self-adaptive step sizes
for solving the inclusion problem (1.3).

######  Algorithm 3.3.

Let $\alpha\in(0,1)$, $\mu_{0},\mu_{1}>0$ and choose a nonnegative real
sequence $\\{d_{n}\\}$ such that $\sum_{n=1}^{\infty}d_{n}<\infty.$ For
arbitrary $v_{0},v_{1}\in\mathbb{X}$, let the sequence $\\{v_{n}\\}$ be
generated by

$\displaystyle v_{n+1}={Res}^{g}_{\mu_{n}\mathcal{B}}\Big{(}\nabla
g^{*}(\nabla
g(v_{n})-\left((\mu_{n}+\mu_{n-1})\mathcal{A}v_{n}-\mu_{n-1}\mathcal{A}v_{n-1}\right))\Big{)},~{}n\geq
1,$

where

(3.1)
$\displaystyle\mu_{n+1}=\begin{cases}\min\left\\{\frac{\alpha\|v_{n}-v_{n+1}\|_{\mathbb{X}}}{\|\mathcal{A}v_{n}-\mathcal{A}v_{n+1}\|_{\mathbb{X}^{*}}},~{}\mu_{n}+d_{n}\right\\},&\mbox{if}~{}\mathcal{A}v_{n}\neq\mathcal{A}v_{n+1},\\\
\mu_{n}+d_{n},&\mbox{otherwise}.\end{cases}$

######  Remark 3.4.

  * •

Clearly, Algorithms 3.2 and 3.3 only require one evaluation of $\mathcal{A}$
per iteration, unlike the methods in [16, 33, 34, 35] which require two
evaluations of $\mathcal{A}$ per iteration.

  * •

Note that by (3.1), $\lim\limits_{n\to\infty}\mu_{n}=\mu$, where
$\mu\in[\min\\{\frac{\alpha}{L},\mu_{1}\\},~{}\mu_{1}+d]$ with
$d=\sum_{n=1}^{\infty}d_{n}$ (see [18]).

  * •

When $d_{n}=0$, then the step size $\mu_{n}$ in (3.1) is similar to the one in
[14, 16, 35]. We recall that the step size in [14, 16, 35] is monotonically
decreasing; so their methods may depend on the choice of the initial step size
$\mu_{1}$. However, the step size given in (3.1) is non-monotonic and so the
dependence on the initial step size $\mu_{1}$ is reduced.

##  4\. Convergence Results

###  4.1. Weak Convergence

In this subsection we consider the weak convergence of the sequences generated
by Algorithms 3.2 and 3.3. We begin with those generated by Algorithm 3.2.

######  Lemma 4.1.

Let $\\{v_{n}\\}$ be generated by Algorithm 3.2 when Assumption 3.1(a) holds.
Then

$\displaystyle D_{g}(z,v_{n+1})$ $\displaystyle\leq
D_{g}(z,v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle$
$\displaystyle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle-
D_{g}(v_{n+1},v_{n})\hskip 5.69046pt\forall
z\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$

###### Proof.

Let $z\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$ Then
$-\mathcal{A}z\in\mathcal{B}z.$

By the definitions of $v_{n+1}$ and ${Res}^{g}_{\mu\mathcal{B}}$ (see (2.5)),
we obtain

$v_{n+1}=(\nabla g+\mu\mathcal{B})^{-1}\left(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1})\right),$

which implies that

(4.1) $\displaystyle\frac{1}{\mu}\left(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1})-\nabla g(v_{n+1})\right)\in
Bv_{n+1}.$

Hence, using the monotonicity of $\mathcal{B}$, we get

$0\leq\left\langle\frac{1}{\mu}\left(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1})-\nabla
g(v_{n+1})\right)+\mathcal{A}z,v_{n+1}-z\right\rangle,$

which implies that

(4.2) $\displaystyle 0$ $\displaystyle\leq$ $\displaystyle\langle\nabla
g(v_{n+1})-\nabla
g(v_{n})+\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1})-\mu\mathcal{A}z,z-v_{n+1}\rangle$
$\displaystyle=$ $\displaystyle\langle\nabla g(v_{n+1})-\nabla
g(v_{n}),z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}z,z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n+1}\rangle.$

Next, using the monotonicity of $\mathcal{A}$, we see that

(4.3)
$\displaystyle\langle\mathcal{A}v_{n}-\mathcal{A}z,z-v_{n+1}\rangle\leq\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle.$

Now, using (4.3) in (4.2), and noting equation (2.3), we obtain

$\displaystyle 0$ $\displaystyle\leq\langle\nabla g(v_{n+1})-\nabla
g(v_{n}),z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle$
$\displaystyle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle$
$\displaystyle=D_{g}(z,v_{n})-D_{g}(z,v_{n+1})-D_{g}(v_{n+1},v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle$
(4.4)
$\displaystyle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle,$

which yields the required conclusion. ∎

######  Theorem 4.2.

Let Assumption 3.1 hold and let
$\mu\in\Big{[}\delta,~{}\frac{\gamma(1-2\delta)}{2L}\Big{]}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ Then the sequence $\\{v_{n}\\}$
generated by Algorithm 3.2 converges weakly to an element of
$(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$

###### Proof.

Using the Lipschitz continuity of $\mathcal{A}$ and (2.4), we obtain

$\displaystyle\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle$
$\displaystyle\leq\mu L\|v_{n}-v_{n-1}\|\|v_{n}-v_{n+1}\|$
$\displaystyle\leq\frac{\mu
L}{2}\Big{(}\|v_{n}-v_{n-1}\|^{2}+\|v_{n+1}-v_{n}\|^{2}\Big{)}$ (4.5)
$\displaystyle\leq\mu
L\gamma^{-1}\Big{(}D_{g}(v_{n},v_{n-1})+D_{g}(v_{n+1},v_{n})\Big{)}.$

Since $\mu\leq\frac{\gamma(1-2\delta)}{2L},$ we get that $\mu
L\gamma^{-1}\leq\frac{1}{2}-\frac{2\delta}{2}<\frac{1}{2},$ which further
gives that $\mu L\gamma^{-1}-1\leq-\left(\frac{1}{2}+\delta\right)$. Using
these inequalities and (4.1) in Lemma 4.1, we see that

$\displaystyle D_{g}(z,v_{n+1})$ $\displaystyle\leq
D_{g}(z,v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\mu
L\gamma^{-1}D_{g}(v_{n},v_{n-1})$
$\displaystyle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle+(\mu
L\gamma^{-1}-1)D_{g}(v_{n+1},v_{n})$ $\displaystyle\leq
D_{g}(z,v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\frac{1}{2}D_{g}(v_{n},v_{n-1})$
(4.6)
$\displaystyle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle-\Big{(}\frac{1}{2}+\delta\Big{)}D_{g}(v_{n+1},v_{n}).$

Now, for $n\geq 1$, let

$\displaystyle s_{n}$ $\displaystyle=$ $\displaystyle
D_{g}(z,v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\frac{1}{2}D_{g}(v_{n},v_{n-1}),$
$\displaystyle t_{n}$ $\displaystyle=$ $\displaystyle\delta
D_{g}(v_{n+1},v_{n}).$

Then (4.1) can be rewritten as

(4.7) $\displaystyle s_{n+1}\leq s_{n}-t_{n}~{}\forall n\geq 1.$

We have $s_{n}\geq 0\;~{}\forall n\geq 1$, because

(4.8) $\displaystyle s_{n}$ $\displaystyle=$ $\displaystyle
D_{g}(z,v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\frac{1}{2}D_{g}(v_{n},v_{n-1})$
$\displaystyle\geq$ $\displaystyle D_{g}(z,v_{n})-\mu
L\gamma^{-1}\left(D_{g}(v_{n},v_{n-1})+D_{g}(z,v_{n})\right)+\frac{1}{2}D_{g}(v_{n},v_{n-1})$
$\displaystyle\geq$ $\displaystyle
D_{g}(z,v_{n})-\frac{1}{2}\left(D_{g}(v_{n},v_{n-1})+D_{g}(z,v_{n})\right)+\frac{1}{2}D_{g}(v_{n},v_{n-1})$
$\displaystyle=$ $\displaystyle\frac{1}{2}D_{g}(z,v_{n})\geq 0.$

Hence, (4.7) implies that the sequence $\\{s_{n}\\}$ is bounded and that
$\lim\limits_{n\rightarrow\infty}t_{n}=0.$ Since $\\{s_{n}\\}$ is bounded, it
follows from (4.8) that $\\{D_{g}(z,v_{n})\\}$ is also bounded, and using
Lemma 2.3, we get that the sequence $\\{v_{n}\\}$ is bounded. Let $u$ be a
weak cluster point of $\\{v_{n}\\}.$ Then we can choose a subsequence of
$\\{v_{n}\\},$ denoted by $\\{v_{n_{j}}\\}$, such that
$v_{n_{j}}\rightharpoonup u.$ Once again, since
$\lim\limits_{n\rightarrow\infty}D_{g}(v_{n+1},v_{n})=\frac{1}{\delta}\lim\limits_{n\rightarrow\infty}t_{n}=0,$
we obtain that $\lim\limits_{n\rightarrow\infty}\|v_{n+1}-v_{n}\|=0$ (by
inequality (2.4)). Since $g$ is strongly coercive, we get that
$\lim\limits_{n\rightarrow\infty}\|\nabla g(v_{n+1})-\nabla g(v_{n})\|=0$
(because if $g$ is uniformly Fréchet differentiable, then $\nabla g^{*}$ is
uniformly continuous on bounded subsets of $\mathbb{X}^{*}$). Also, since
$\mathcal{A}$ is Lipschitz continuous (hence uniformly continuous), we obtain
that
$\lim\limits_{n\rightarrow\infty}\|\mathcal{A}v_{n}-\mathcal{A}v_{n-1}\|=0.$

Now, consider $(v,w)\in G(\mathcal{A}+\mathcal{B})$. Then
$w-\mathcal{A}v\in\mathcal{B}v$. Using this, (4.1) and the monotonicity of
$\mathcal{B}$, we get that

(4.9) $\displaystyle\langle w-\mathcal{A}v-\frac{1}{\mu}\left(\nabla
g(v_{n_{j}})-\mu(2\mathcal{A}v_{n_{j}}-\mathcal{A}v_{n_{j}-1})-\nabla
g(v_{n_{j}+1})\right),v-v_{n_{j}+1}\rangle\geq 0.$

Using (4.9) and the monotonicity of $\mathcal{A}$, we obtain that

(4.10) $\displaystyle\langle w,v-v_{n_{j}+1}\rangle$ $\displaystyle\geq$
$\displaystyle\langle\mathcal{A}v+\frac{1}{\mu}\left(\nabla
g(v_{n_{j}})-\mu(2\mathcal{A}v_{n_{j}}-\mathcal{A}v_{n_{j}-1})-\nabla
g(v_{n_{j}+1})\right),v-v_{n_{j}+1}\rangle$ $\displaystyle=$
$\displaystyle\langle\mathcal{A}v-\mathcal{A}v_{n_{j}+1},v-v_{n_{j}+1}\rangle+\langle\mathcal{A}v_{n_{j}+1}-\mathcal{A}v_{n_{j}},v-v_{n_{j}+1}\rangle$
$\displaystyle+\langle\mathcal{A}v_{n_{j}-1}-\mathcal{A}v_{n_{j}},v-v_{n_{j}+1}\rangle+\frac{1}{\mu}\langle\nabla
g(v_{n_{j}})-\nabla g(v_{n_{j}+1}),v-v_{n_{j}+1}\rangle$ $\displaystyle\geq$
$\displaystyle\langle\mathcal{A}v_{n_{j}+1}-\mathcal{A}v_{n_{j}},v-v_{n_{j}+1}\rangle+\langle\mathcal{A}v_{n_{j}-1}-\mathcal{A}v_{n_{j}},v-v_{n_{j}+1}\rangle$
$\displaystyle+\frac{1}{\mu}\langle\nabla g(v_{n_{j}})-\nabla
g(v_{n_{j}+1}),v-v_{n_{j}+1}\rangle.$

Passing to the limit as $j\to\infty$ in (4.10), we see that $\langle
w,v-u\rangle\geq 0.$ Thus, using the maximal monotonicity of
$\mathcal{A}+\mathcal{B}$ (see Lemma 2.5), we conclude that
$u\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$.

We now show that $\\{v_{n}\\}$ converges weakly to $u$. It follows from (4.7)
that the sequence $\\{s_{n}\\}$ is monotone for all
$z\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$, and since it is also bounded for
all $z\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$, we get that

(4.11)
$\displaystyle\lim_{n\to\infty}\left(D_{g}(u,v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},u-v_{n}\rangle+\frac{1}{2}D_{g}(v_{n},v_{n-1})\right)~{}~{}\mbox{exists}.$

Since $\\{v_{n}\\}$ is bounded, $D_{g}(v_{n},v_{n-1})\to 0$ as $n\to\infty$,
and $\mathcal{A}$ is Lipschitz continuous, it follows from (4.11) that
$\lim\limits_{n\to\infty}D_{g}(u,v_{n})$ exists.
Next, we show that $u$ is unique. Suppose to the contrary that this is not
true. Then there exists a subsequence $\\{v_{n_{i}}\\}\subset\\{v_{n}\\}$ such
that $v_{n_{i}}\rightharpoonup\bar{u}$ with $u\neq\bar{u}$. Note that we can
again show that $\bar{u}\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$. Using Lemma
2.4, we get

$\displaystyle\lim_{n\to\infty}D_{g}(u,v_{n})$ $\displaystyle=$
$\displaystyle\limsup_{j\to\infty}D_{g}(u,v_{n_{j}})<\limsup_{j\to\infty}D_{g}(\bar{u},v_{n_{j}})$
$\displaystyle=$
$\displaystyle\lim_{n\to\infty}D_{g}(\bar{u},v_{n})=\limsup_{i\to\infty}D_{g}(\bar{u},v_{n_{i}})$
$\displaystyle<$
$\displaystyle\limsup_{i\to\infty}D_{g}(u,v_{n_{i}})=\lim_{n\to\infty}D_{g}(u,v_{n}),$

which is a contradiction. The contradiction we have reached shows that
$u=\bar{u}$. Therefore $u$ is indeed unique, as claimed. Thus the whole
sequence $\\{v_{n}\\}$ converges weakly to an element of
$(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$, as asserted. ∎

We now turn to Algorithm 3.3 and establish a weak convergence theorem for it.

######  Theorem 4.3.

Let Assumption 3.1 hold and let
$\alpha\in\Big{(}\delta,~{}\frac{\gamma(1-2\delta)}{2}\Big{)}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ Then the sequence $\\{v_{n}\\}$
generated by Algorithm 3.3 converges weakly to an element of
$(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$

###### Proof.

Let $z\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$ Following a method of proof
which is similar to that of the proof of Lemma 4.1, we obtain that

$\displaystyle D_{g}(z,v_{n+1})$ $\displaystyle\leq
D_{g}(z,v_{n})+\mu_{n-1}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\mu_{n-1}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle$
(4.12)
$\displaystyle+\mu_{n}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle-
D_{g}(v_{n+1},v_{n}).$

From (3.1) and (2.4) it follows that

$\displaystyle\mu_{n-1}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle$
$\displaystyle\leq\mu_{n-1}\|\mathcal{A}v_{n}-\mathcal{A}v_{n-1}\|\|v_{n}-v_{n+1}\|$
$\displaystyle\leq\frac{\mu_{n-1}}{\mu_{n}}\alpha\|v_{n}-v_{n-1}\|\|v_{n}-v_{n+1}\|$
$\displaystyle\leq\frac{\mu_{n-1}}{\mu_{n}}\frac{\alpha}{2}\Big{(}\|v_{n}-v_{n-1}\|^{2}+\|v_{n+1}-v_{n}\|^{2}\Big{)}$
(4.13)
$\displaystyle\leq\frac{\mu_{n-1}}{\mu_{n}}\alpha\gamma^{-1}\Big{(}D_{g}(v_{n},v_{n-1})+D_{g}(v_{n+1},v_{n})\Big{)}.$

By Remark 3.4(ii) and the condition
$\alpha\in\Big{(}\delta,~{}\frac{\gamma(1-2\delta)}{2}\Big{)},$ we have that
$\lim\limits_{n\to\infty}\left(1-\frac{\mu_{n}}{\mu_{n+1}}\alpha\gamma^{-1}\right)=1-\alpha\gamma^{-1}>\frac{1}{2}+\delta$.
Hence, there exists $n_{0}\geq 1$ such that
$1-\frac{\mu_{n}}{\mu_{n+1}}\alpha\gamma^{-1}>\frac{1}{2}+\delta~{}\forall
n\geq n_{0}$; which further implies that
$\frac{\mu_{n}}{\mu_{n+1}}\alpha\gamma^{-1}<\frac{1}{2}-\delta~{}\forall n\geq
n_{0}$. Hence, (4.1) becomes

(4.14)
$\displaystyle\mu_{n-1}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle$
$\displaystyle\leq\left(\frac{1}{2}-\delta\right)\Big{(}D_{g}(v_{n},v_{n-1})+D_{g}(v_{n+1},v_{n})\Big{)}~{}\forall
n\geq n_{0}.$

Using (4.14) in (4.1), we obtain

$\displaystyle D_{g}(z,v_{n+1})$ $\displaystyle\leq
D_{g}(z,v_{n})+\mu_{n-1}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\Big{(}\frac{1}{2}-\delta\Big{)}D_{g}(v_{n},v_{n-1})$
$\displaystyle+\mu_{n}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle-\Big{(}\frac{1}{2}+\delta\Big{)}D_{g}(v_{n+1},v_{n})$
$\displaystyle\leq
D_{g}(z,v_{n})+\mu_{n-1}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\frac{1}{2}D_{g}(v_{n},v_{n-1})$
(4.15)
$\displaystyle+\mu_{n}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle-\Big{(}\frac{1}{2}+\delta\Big{)}D_{g}(v_{n+1},v_{n})~{}\forall
n\geq n_{0}.$

For $n\geq n_{0}$, let

$\displaystyle s_{n}$ $\displaystyle=$ $\displaystyle
D_{g}(z,v_{n})+\mu_{n-1}\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\frac{1}{2}D_{g}(v_{n},v_{n-1}),$
$\displaystyle t_{n}$ $\displaystyle=$ $\displaystyle\delta
D_{g}(v_{n+1},v_{n}).$

Then (4.1) can be rewritten as

(4.16) $\displaystyle s_{n+1}\leq s_{n}-t_{n}~{}\forall n\geq n_{0}.$

Using an argument similar to the one used regarding (4.8), we obtain that
$s_{n}\geq 0\;~{}\forall n\geq n_{0}$. Hence, again following the arguments
used concerning (4.8) and noting that the sequence $\\{\mu_{n}\\}$ is bounded,
we can show that $\\{v_{n}\\}$ indeed converges weakly to an element of
$(\mathcal{A}+\mathcal{B})^{-1}(0^{*}),$ as asserted. ∎

######  Remark 4.4.

Theorem 4.2 and Theorem 4.3 extend Theorem 2.5 and Theorem 3.4 of [19],
respectively, from Hilbert space to all reflexive Banach spaces.

If we set $\mathcal{A}=0$ in Algorithm 3.2, then we obtain the following
result concerning the solution of the NPP (1.1) as a corollary of Theorem 4.2.

######  Corollary 4.5.

Let Assumption 3.1 hold and let $\mu>0$. For arbitrary $v_{1}\in\mathbb{X}$,
let the sequence $\\{v_{n}\\}$ be generated by

$\displaystyle v_{n+1}={Res}^{g}_{\mu\mathcal{B}}(v_{n}),~{}n\geq 1.$

Then $\\{v_{n}\\}$ converges weakly to an element of
$\mathcal{B}^{-1}(0^{*}).$

######  Remark 4.6.

We can replace $\mu$ with $\\{\mu_{n}\\}$ in Corollary 4.5 to obtain a
corollary of Theorem 4.3.

If we set $\mathcal{B}=N_{\mathcal{C}}$ in Algorithms 3.2 and 3.3 (where
$N_{\mathcal{C}}$ is as defined in (2.6)), we get
$\mbox{Res}_{\mu\mathcal{B}}^{g}={Proj}^{g}_{\mathcal{C}}$. Hence, we obtain
the following new results as corollaries of Theorem 4.2 and Theorem 4.3,
respectively. These results concern the following variational inequality
problem: $\mbox{Find}~{}v\in\mathcal{C}~{}\mbox{such
that}~{}\langle\mathcal{A}v,u-v\rangle\geq 0~{}\forall u\in\mathcal{C},$ where
$\mathcal{A}:\mathcal{C}\to\mathbb{X}^{*}$.
We denote the solution set of this problem by $VI(\mathcal{C},\mathcal{A})$.

######  Corollary 4.7.

Let Assumption 3.1 hold and let
$\mu\in\Big{[}\delta,~{}\frac{\gamma(1-2\delta)}{2L}\Big{]}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ For arbitrary
$v_{0},v_{1}\in\mathbb{X}$ and $\mu>0$, let the sequence $\\{v_{n}\\}$ be
generated by

$\displaystyle v_{n+1}={Proj}^{g}_{\mathcal{C}}\Big{(}\nabla g^{*}(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1}))\Big{)}~{}\forall n\geq 1.$

Then $\\{v_{n}\\}$ converges weakly to an element of
$VI(\mathcal{C},\mathcal{A})$.

######  Corollary 4.8.

Let Assumption 3.1 hold and let
$\alpha\in\Big{(}\delta,~{}\frac{\gamma(1-2\delta)}{2}\Big{)}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ Let $\alpha\in(0,1)$,
$\mu_{0},\mu_{1}>0$ and choose a nonnegative real sequence $\\{d_{n}\\}$ such
that $\sum_{n=1}^{\infty}d_{n}<\infty.$ For arbitrary
$v_{0},v_{1}\in\mathbb{X}$, let the sequence $\\{v_{n}\\}$ be generated by

$\displaystyle v_{n+1}={Proj}^{g}_{\mathcal{C}}\Big{(}\nabla g^{*}(\nabla
g(v_{n})-\left((\mu_{n}+\mu_{n-1})\mathcal{A}v_{n}-\mu_{n-1}\mathcal{A}v_{n-1}\right))\Big{)}~{}\forall
n\geq 1,$

where

(4.17)
$\displaystyle\mu_{n+1}=\begin{cases}\min\left\\{\frac{\alpha\|v_{n}-v_{n+1}\|}{||\mathcal{A}v_{n}-\mathcal{A}v_{n+1}||},~{}\mu_{n}+d_{n}\right\\},&\mbox{if}~{}\mathcal{A}v_{n}\neq\mathcal{A}v_{n+1},\\\
\mu_{n}+d_{n},&\mbox{otherwise}.\end{cases}$

Then $\\{v_{n}\\}$ converges weakly to an element of
$VI(\mathcal{C},\mathcal{A}).$

###  4.2. Rate of Convergence

In this subsection we obtain rates of convergence for both Algorithm 3.2 and
Algorithm 3.3.

It follows from Algorithm 3.2 (or Algorithm 3.3) that $v_{n+1}=v_{n}=v_{n-1}$
if and only if $v_{n}\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$. That is,

$\displaystyle v_{n+1}=v_{n}=v_{n-1}$ $\displaystyle\Leftrightarrow$
$\displaystyle v_{n}={Res}^{g}_{\mu\mathcal{B}}\Big{(}\nabla g^{*}(\nabla
g(v_{n})-\mu\mathcal{A}v_{n})\Big{)}$ $\displaystyle\Leftrightarrow$
$\displaystyle v_{n}=\left(\nabla g+\mu\mathcal{B}\right)^{-1}\circ\nabla
g\Big{(}\nabla g^{*}(\nabla g(v_{n})-\mu\mathcal{A}v_{n})\Big{)}$
$\displaystyle\Leftrightarrow$ $\displaystyle\left(\nabla
g(v_{n})-\mu\mathcal{A}v_{n}\right)\in\left(\nabla
g(v_{n})+\mu\mathcal{B}v_{n}\right)$ $\displaystyle\Leftrightarrow$
$\displaystyle v_{n}\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$

In our theorems, we established that $||v_{n+1}-v_{n}||\to 0$ as $n\to\infty$
(which also means that $||v_{n}-v_{n-1}||\to 0$ as $n\to\infty$) whenever
$(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$ is nonempty. Hence, using
$||v_{n+1}-v_{n}||$ as a measure of the convergence rate, we obtain in the
next theorem a sublinear rate of convergence for Algorithm 3.2.

######  Theorem 4.9.

Let Assumption 3.1 hold and let
$\mu\in\Big{[}\delta,~{}\frac{\gamma(1-2\delta)}{2L}\Big{]}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ Then

$\min\limits_{1\leq j\leq n}\|v_{j+1}-v_{j}\|=\mathcal{O}(1/\sqrt{n}).$

###### Proof.

It follows from (4.1) that

$\displaystyle\delta D_{g}(v_{n+1},v_{n})$ $\displaystyle\leq
D_{g}(z,v_{n})-D_{g}(z,v_{n+1})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle$
$\displaystyle-\mu\langle\mathcal{A}v_{n+1}-\mathcal{A}v_{n},z-v_{n+1}\rangle+\frac{1}{2}D_{g}(v_{n},v_{n-1})-\frac{1}{2}D_{g}(v_{n+1},v_{n}).$

This implies that

$\displaystyle\delta\sum_{j=1}^{n}D_{g}(v_{j+1},v_{j})$ $\displaystyle\leq
D_{g}(z,v_{1})-D_{g}(z,v_{n+1})+\mu\langle\mathcal{A}v_{1}-\mathcal{A}v_{0},z-v_{1}\rangle$
$\displaystyle-\mu\langle\mathcal{A}v_{n+1}-\mathcal{A}v_{n},z-v_{n+1}\rangle+\frac{1}{2}D_{g}(v_{1},v_{0})-\frac{1}{2}D_{g}(v_{n+1},v_{n})$
(4.18)
$\displaystyle=D_{g}(z,v_{1})+\mu\langle\mathcal{A}v_{1}-\mathcal{A}v_{0},z-v_{1}\rangle+\frac{1}{2}D_{g}(v_{1},v_{0})-s_{n+1},$

where we have

$s_{n+1}=D_{g}(z,v_{n+1})+\mu\langle\mathcal{A}v_{n+1}-\mathcal{A}v_{n},z-v_{n+1}\rangle+\frac{1}{2}D_{g}(v_{n+1},v_{n}).$

By (4.8), we also have $s_{n+1}\geq 0~{}\forall n\geq 1.$ Hence, it follows
from (4.2) and (2.4) that

$\displaystyle\sum_{j=1}^{n}\|v_{j+1}-v_{j}\|^{2}$
$\displaystyle\leq\frac{2}{\delta\gamma}\left[D_{g}(z,v_{1})+\mu\langle\mathcal{A}v_{1}-\mathcal{A}v_{0},z-v_{1}\rangle+\frac{1}{2}D_{g}(v_{1},v_{0})\right].$

Therefore,

$\min\limits_{1\leq j\leq
n}\|v_{j+1}-v_{j}\|^{2}\leq\frac{2}{n\delta\gamma}\left[D_{g}(z,v_{1})+\mu\langle\mathcal{A}v_{1}-\mathcal{A}v_{0},z-v_{1}\rangle+\frac{1}{2}D_{g}(v_{1},v_{0})\right].$

This means that

$\min\limits_{1\leq j\leq n}\|v_{j+1}-v_{j}\|=\mathcal{O}(1/\sqrt{n}).$

∎

Similarly to Theorem 4.9, we also have the following sublinear rate of
convergence result for Algorithm 3.3.

######  Theorem 4.10.

Let Assumption 3.1 hold and let
$\alpha\in\Big{(}\delta,~{}\frac{\gamma(1-2\delta)}{2}\Big{)}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ Then

$\min\limits_{1\leq j\leq n}\|v_{j+1}-v_{j}\|=\mathcal{O}(1/\sqrt{n}).$

###  4.3. Strong Convergence

In order to obtain strong convergence of the sequences generated by our
methods, we replace Assumption 3.1 with the following conditions.

######  Assumption 4.11.

Let $\mathcal{A}:\mathbb{X}\to\mathbb{X}^{*}$ and $\mathcal{B}:\mathbb{X}\to
2^{\mathbb{X}^{*}}$ be operators which satisfy the following conditions:

  * (a)

$\mathcal{A}$ is monotone on $\mathbb{X}$ and $\mathcal{B}$ is maximal
monotone and $\tau$-strongly monotone on $\mathbb{X}$,

  * (a)*

$\mathcal{A}$ is $\tau$-strongly monotone on $\mathbb{X}$ and $\mathcal{B}$ is
maximal monotone on $\mathbb{X}$,

  * (b)

$\mathcal{A}$ is Lipschitz continuous on $\mathbb{X}$ with constant $L>0$.

######  Lemma 4.12.

Let a sequence $\\{v_{n}\\}$ be generated by Algorithm 3.2 when Assumption
4.11(a) or (a)* holds. Then

$\displaystyle\tau\mu\|v_{n+1}-z\|^{2}$ $\displaystyle\leq
D_{g}(z,v_{n})-D_{g}(z,v_{n+1})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle$
$\displaystyle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle-
D_{g}(v_{n+1},v_{n})\hskip 5.69046pt\forall
z\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$

###### Proof.

Let $z\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$. Then
$-\mathcal{A}z\in\mathcal{B}z.$ Using arguments similar to those used in
obtaining (4.1), we get

(4.19) $\displaystyle\frac{1}{\mu}\left(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1})-\nabla
g(v_{n+1})\right)\in\mathcal{B}v_{n+1}.$

If we use Assumption 4.11(a), in particular, the $\tau$-strong monotonicity of
$\mathcal{B}$, we get

$\tau\|v_{n+1}-z\|^{2}\leq\left\langle\frac{1}{\mu}\left(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1})-\nabla
g(v_{n+1})\right)+\mathcal{A}z,v_{n+1}-z\right\rangle,$

which implies that

$\displaystyle\mu\tau\|v_{n+1}-z\|^{2}$ $\displaystyle\leq$
$\displaystyle\langle\nabla g(v_{n+1})-\nabla
g(v_{n}),z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}z,z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n+1}\rangle.$

Using the monotonicity of $\mathcal{A}$ and equation (2.3), we obtain

$\displaystyle\mu\tau\|v_{n+1}-z\|^{2}$ $\displaystyle\leq
D_{g}(z,v_{n})-D_{g}(z,v_{n+1})-D_{g}(v_{n+1},v_{n})+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n}\rangle$
(4.20)
$\displaystyle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},v_{n}-v_{n+1}\rangle,$

which is the desired inequality.

On the other hand, if we use Assumption 4.11(a)*, then by the monotonicity of
$\mathcal{B}$, we obtain

$0\leq\left\langle\frac{1}{\mu}\left(\nabla
g(v_{n})-\mu(2\mathcal{A}v_{n}-\mathcal{A}v_{n-1})-\nabla
g(v_{n+1})\right)+\mathcal{A}z,v_{n+1}-z\right\rangle,$

which implies that

(4.21) $\displaystyle 0$ $\displaystyle\leq$ $\displaystyle\langle\nabla
g(v_{n+1})-\nabla
g(v_{n}),z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}z,z-v_{n+1}\rangle+\mu\langle\mathcal{A}v_{n}-\mathcal{A}v_{n-1},z-v_{n+1}\rangle.$

Since $\mathcal{A}$ is $\tau$-strongly monotone, it follows that

(4.22)
$\displaystyle\langle\mathcal{A}v_{n}-\mathcal{A}z,z-v_{n+1}\rangle\leq\langle\mathcal{A}v_{n}-\mathcal{A}v_{n+1},z-v_{n+1}\rangle-\tau\|v_{n+1}-z\|^{2}.$

Now, using (4.22) in (4.21) and noting equation (2.3), we arrive at the
desired conclusion. ∎

######  Theorem 4.13.

Let Assumption 4.11(a),(b) or (a)*,(b) hold and let
$\mu\in\Big{[}\delta,~{}\frac{\gamma(1-2\delta)}{2L}\Big{]}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ Then the sequence $\\{v_{n}\\}$
generated by Algorithm 3.2 converges strongly to
$u\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$

###### Proof.

Let $u\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*})$. Using similar arguments to
those used in the proof of Theorem 4.2, we obtain that $\\{v_{n}\\}$ is
bounded,
$\lim\limits_{n\to\infty}\|v_{n}-v_{n+1}\|=0,~{}\lim\limits_{n\to\infty}\|\mathcal{A}v_{n}-\mathcal{A}v_{n+1}\|=0$
and $\lim\limits_{n\to\infty}D_{g}(u,v_{n})$ exists. Using these facts in
Lemma 4.12 and replacing $z$ with $u$, we see that
$\lim\limits_{n\to\infty}\|v_{n+1}-u\|\leq 0$, which implies that
$\\{v_{n}\\}$ converges strongly to
$u\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}),$ as asserted. ∎

Similarly to Theorem 4.13, we have the following strong convergence theorem
for Algorithm 3.3.

######  Theorem 4.14.

Let Assumption 4.11(a),(b) or (a)*,(b) hold and let
$\alpha\in\Big{(}\delta,~{}\frac{\gamma(1-2\delta)}{2}\Big{)}$ for some
$\delta\in(0,\frac{1}{2})$ and $~{}\gamma>0.$ Then the sequence $\\{v_{n}\\}$
generated by Algorithm 3.3 converges strongly to
$u\in(\mathcal{A}+\mathcal{B})^{-1}(0^{*}).$

######  Remark 4.15.

Similarly to Corollaries 4.5-4.8, we can obtain strong convergence results as
corollaries of Theorems 4.13 and 4.14 for solving the NPP (1.1) and the
variational inequality problem in real reflexive Banach spaces.

##  5\. Application to generalized Nash Equilbirium Problems for gas markets

In this section we apply our results to solving a Generalized Nash Equilibrium
Problem (GNEP) for which the constraints are governed by a system of partial
differential equations (PDEs). This type of problem is particularly useful in
the trading and transporting of natural gas because the dynamics of gas
transport is often posed as a system of PDEs. In [13], using a generalized
Nash equilibrium approach with PDE-constraints, the authors studied a two-node
(production and consumption nodes) gas market.
Consider strategic firms that trade and transport natural gas through a
pipeline system. That is, strategic gas firms that decide on their production
of gas at an injection node (production node) and on their sales at a
withdrawal node (consumption node) of a pipeline system with the aim of making
maximum profit over a finite period of time $[0,T]$. Here we focus on a single
pipe only. The flow through the pipe which connects the injection node at
$x=0$ and withdrawal node at $x=L$ (where $L>0$ is the length of the pipe) is
governed by a system of PDEs with some boundary conditions. A detailed study
of this system of PDEs can be found in [13, Section 3].

As in [13], let $y:=(p,q)$, where $p$ and $q$ are the pressure and mass flow,
respectively, in the pipe. Note that $p$ and $q$ are the state variables in
the pipe. Also, denote the collection of a firm’s decisions by $u$. Then the
inclusion $y=S(u)\in K$ (where the mapping $S$ provides the solution of the
system of PDEs for any given $u$ and $K$ is a closed and convex set) describes
the shared constraints of the firms. At any time $t\in[0,T]$, let
$q^{\mbox{in}}(t)$ denote the quantity of gas injected into the pipe at the
production node at a cost of $c(t)q^{\mbox{in}}(t)$. We also denote by
$q^{\mbox{out}}(t)$ the quantity of gas withdrawn from the pipe at the
consumption node due to the gas demand at this node. Then the price of gas is
given by an inverse demand function $P(t,q^{\mbox{out}}(t)).$ We assume that
firm $i$ ($i\in\\{1,\dots,M\\})$ strategically chooses the quantity
$q_{i}^{\mbox{in}}(t)$ injected at the production node located at $x=0$ at a
pressure $p_{i}^{\mbox{in}}(t)$ and the quantity $q_{i}^{\mbox{out}}(t)$ sold
at the consumption node $x=L$ at a pressure $p_{i}^{\mbox{out}}(t)$ at any
time $t\in[0,T]$. These decision variables are grouped into
$u_{i}:=(p_{i}^{\mbox{in}},p_{i}^{\mbox{out}},q_{i}^{\mbox{in}},q_{i}^{\mbox{out}})$,
which belong to a closed and convex subset $U_{i}$ of $L^{2}(0,T)^{4}$.
Thus, the maximization problem for firm $i$ is as follows::

(5.1) $\displaystyle\max_{u_{i}\in
U_{i}}\int_{0}^{T}\left[P\left(t,\sum_{k=1}^{M}q_{k}^{\mbox{out}}(t)\right)q_{i}^{\mbox{out}}(t)-c_{i}(t)q_{i}^{\mbox{in}}(t)\right]dt-
R_{i}(u_{i})$ (5.2) $\displaystyle\mbox{such that}\hskip 8.5359pt0\leq
q_{i}^{\mbox{in}}(t)\leq\bar{q}_{i}^{\mbox{in}}\hskip 8.5359pt\mbox{for
a.e}~{}~{}t\in(0,T),$ (5.3)
$\displaystyle\int_{0}^{T}q_{i}^{\mbox{out}}(t)-q_{i}^{\mbox{in}}(t)\leq 0,$
(5.4) $\displaystyle S(u)\in K,$

where $\bar{q}_{i}^{\mbox{in}}$ is a product-specific capacity,
$u=(u_{i},u_{-i})$, $u_{i}$ collects the decisions of firm $i$, $u_{-i}$
collects the decisions of all the other firms, and $R_{i}$ is a convex
function. The feasible set of firm $i$ is the intersection of $U_{i}$ with the
constraints (5.2)–(5.3) (see [13] for more details).

We note that the above maximization problem for strategic gas firms gives rise
to the following GNEP for player $i$ ($i\in\\{1,\dots,M\\}$):

$\displaystyle\min_{u_{i}\in
U}\int_{0}^{T}\left(\alpha(t)\sum_{k=1}^{M}q_{k}^{\mbox{out}}(t)-\beta(t)\right)q_{i}^{\mbox{out}}(t)dt+g_{i}(u_{i})$
(5.5) $\displaystyle\mbox{such that}\hskip 8.5359ptu_{i}\in
P^{\mbox{ad}}\times Q_{i}^{\mbox{ad}}~{}~{};~{}~{}S(u_{i},u_{-i})\in K,$

where $g_{i}(u_{i})=g^{p}(p_{i})+g^{q}_{i}(q_{i})$, the functions $g^{p}$ and
$g_{i}^{q}$ are proper convex and lower semicontinuous,
$\beta(t)-\alpha(t)q^{\mbox{out}}(t)=P(t,q^{\mbox{out}}(t))$, $P$ is a
measurable function of $t$, the functions $\alpha$ and $\beta$ are real-valued
functions of $t$, $P^{\mbox{ad}}$ and $Q_{i}^{\mbox{ad}}$ are subsets of
$P:=H^{1}(0,T)^{2}$ (the space of pressures at the endpoints) and
$Q:=H^{1}(0,T)^{2}$ (the space of mass flow at the endpoints), respectively,
and $U:=P\times Q$ denotes the space of decision variables (controls)
$u_{i}=(p_{i},q_{i})$ of each player. If for each $i$, $g_{i}$ is coercive and
the subdifferential $\partial g_{i}$ of $g_{i}$ is defined everywhere, then
$P^{\mbox{ad}}$ and $Q_{i}^{\mbox{ad}}$ are closed and convex.
Clearly, the GNEP (5.1)–(5.4) that models the gas market fits into the
settings of the GNEP (5). That is, we can recover the GNEP (5.1)–(5.4) from
(5) by setting

$g_{i}(u_{i})=\int_{0}^{T}c_{i}(t)q_{i}^{\mbox{in}}(t)dt+R_{i}(u_{i})$

and $Q_{i}^{\mbox{ad}}$ to capture the constraints (5.2)–(5.3).
The existence of solutions to the GNEP (5) for which all the pressures $p_{i}$
are identical was established in [13, Theorem 4.1] under some conditions which
are also satisfied by the GNEP (5.1)–(5.4).

We now apply our algorithms in Section 3 to solving the GNEP (5), which in
turn solves the GNEP (5.1)–(5.4) that models the gas market. To this end, we
consider some change of variables as in [13].
Given $y_{0}=(p_{0},q_{0})$, let $\hat{p}^{0}(t):=(p_{0}(0),p_{0}(L))$ and
$\hat{q}^{0}(t):=(q_{0}(0)/M,q_{0}(L)/M)$ for any $t\in[0,T]$. Then
$\hat{u}_{i}^{y_{0}}:=(\hat{p}^{0},\hat{q}^{0})$, and the shifted decisions
for player $i$ are given by $\hat{u}_{i}=u_{i}-\hat{u}_{i}^{y_{0}}$. Let
$\hat{P}:=\\{\hat{p}\in P:p(0)=0\\}$ and $\hat{Q}:=\\{\hat{q}\in Q:q(0)=0\\}$.
Then $\hat{P}^{\mbox{ad}}:=\\{\hat{p}\in\hat{P}:\hat{p}+\hat{p}^{0}\in
P^{\mbox{ad}}\\}$,
$\hat{Q}_{i}^{\mbox{ad}}:=\\{\hat{q}\in\hat{Q}:\hat{q}+\hat{q}^{0}\in
Q_{i}^{\mbox{ad}}\\}$ and
$\hat{U}_{i}^{\mbox{ad}}=\hat{P}^{\mbox{ad}}\times\hat{Q}_{i}^{\mbox{ad}}$.
Let $w_{i}=(w_{i}^{p0},w_{i}^{pL},w_{i}^{q0},w_{i}^{qL})\in\hat{U}$, and
define the mappings $d_{1}:\hat{U}\times\hat{U}^{M-1}\to\hat{U}^{*}$,
$d_{2}:\hat{U}\to\hat{U}^{*}$ and $e\in\hat{U}^{*}$ (where $\hat{U}^{*}$ is
the dual space of $\hat{U}$) by

$\langle
d_{1}(\hat{u}_{i},\hat{u}_{-i}),w_{i}\rangle_{\hat{U}^{*},\hat{U}}=\left(\alpha\sum_{k=1}^{M}\hat{q}_{k}^{\mbox{out}},w_{i}^{qL}\right)_{L^{2}(0,T)},$
$\langle
d_{2}(\hat{u}_{i}),w_{i}\rangle_{\hat{U}^{*},\hat{U}}=\left(\alpha\hat{q}_{i}^{\mbox{out}},w_{i}^{qL}\right)_{L^{2}(0,T)},$
$\langle
e,w_{i}\rangle_{\hat{U}^{*},\hat{U}}=\left(\beta-\hat{\alpha}q0(L),w_{i}^{qL}\right)_{L^{2}(0,T)}.$

Similarly, let $z_{i}=(z_{i}^{\mbox{in}},z_{i}^{\mbox{out}})\in\hat{Q}$, and
define the mappings $\tilde{d}_{1}:\hat{Q}\times\hat{Q}^{M-1}\to\hat{Q}^{*}$,
$\tilde{d}_{2}:\hat{Q}\to\hat{Q}^{*}$ and $\tilde{e}\in\hat{Q}^{*}$ (where
$\hat{Q}^{*}$ is the dual space of $\hat{Q}$) by

$\langle\tilde{d}_{1}(\hat{q}_{i},\hat{q}_{-i}),z_{i}\rangle_{\hat{Q}^{*},\hat{Q}}=\left(\alpha\sum_{k=1}^{M}\hat{q}_{k}^{\mbox{out}},z_{i}^{\mbox{out}}\right)_{L^{2}(0,T)},$
$\langle\tilde{d}_{2}(\hat{q}_{i}),z_{i}\rangle_{\hat{Q}^{*},\hat{Q}}=\left(\alpha\hat{q}_{i}^{\mbox{out}},z_{i}^{\mbox{out}}\right)_{L^{2}(0,T)},$
$\langle\tilde{e},z_{i}\rangle_{\hat{Q}^{*},\hat{Q}}=\left(\beta-\hat{\alpha}q0(L),z_{i}^{\mbox{out}}\right)_{L^{2}(0,T)}.$

Then, by the proof of Theorem 4.1 in [13], we have that the inclusion

(5.6) $\displaystyle
0^{*}\in\tilde{d}_{1}(\hat{q}_{i},\hat{q}_{-i})+\tilde{d}_{2}(\hat{q}_{i})+\partial\hat{g}^{q}_{i}(\hat{q}_{i})+N_{\hat{Q}_{i}^{\mbox{ad}}}(\hat{q}_{i})+(\eta^{\hat{q}})$

(where $\eta^{\hat{q}}\in\hat{Q}^{*}$ and
$\hat{g}^{q}_{i}(\hat{q}_{i})=g_{i}^{q}(\hat{q}_{i}+\hat{q}^{0})$) holds for
all $\hat{u}_{i}$, which implies that the inclusion

(5.7) $\displaystyle 0^{*}\in
d_{1}(\hat{u}_{i},\hat{u}_{-i})+d_{2}(\hat{u}_{i})+\partial\hat{g}_{i}(\hat{u}_{i})+N_{\hat{U}_{i}^{\mbox{ad}}}(\hat{u}_{i})+\hat{S}_{i}^{*}\mu-e,~{}\forall
i\in\\{1,\dots,M\\}$

also holds for $\hat{u}\in\hat{\mathcal{U}}:=\hat{U}^{M}$, where $\mu\in
N_{K}(\hat{S}(\hat{u}))$ and
$\hat{g}_{i}(\hat{u}_{i})=g^{p}(\hat{p}_{i}+\hat{p}^{0})+\hat{g}_{i}^{q}(\hat{q}_{i})$.
Moreover, any solution $\hat{u}$ of the inclusion (5.7) is a solution of the
GNEP (5).
Now, let $\tilde{\mathcal{U}}:=\hat{P}\times\hat{Q}^{M}$ and
$\tilde{Z}:=\hat{P}^{*}\times\prod_{i}\hat{Q}^{*}$, define the operators
$\tilde{A}:\tilde{\mathcal{U}}\to\tilde{Z}$ and
$\tilde{B}:\tilde{\mathcal{U}}\to 2^{\tilde{Z}}$ by

$\tilde{A}(\tilde{p},\hat{q}):=\tilde{d}_{1}(\hat{q}_{i},\hat{q}_{-i})+\tilde{d}_{2}(\hat{q}_{i})~{}~{}\mbox{and}~{}~{}\tilde{B}(\tilde{p},\hat{q}):=\partial\hat{g}^{q}_{i}(\hat{q}_{i})+N_{\hat{Q}_{i}^{\mbox{ad}}}(\hat{q}_{i})+(\eta^{\hat{q}}).$

Then the inclusion (5.6) becomes

$0^{*}\in\tilde{A}(\tilde{p},\hat{q})+\tilde{B}(\tilde{p},\hat{q}).$

Also, $\tilde{A}$ is linear, monotone and demicontinuous with full domain, and
$\tilde{B}$ is maximal monotone with full domain (see [13]). Hence, by setting
$\mathcal{A}=\tilde{A}$ and $\mathcal{B}=\tilde{B}$ in Algorithm 3.2 or
Algorithm 3.3, we can apply our results to approximating the solutions of the
GNEP.

##  6\. Conclusions

In this paper we have proposed two iterative algorithms for solving the
monotone inclusion problem (1.3) in real reflexive Banach spaces. As we have
seen, the methods have simple and elegant structures, and they require only
one evaluation of the single-valued operator $\mathcal{A}$ at each iteration.
We have established weak convergence results when the set-valued operator
$\mathcal{B}$ is maximal monotone, and $\mathcal{A}$ is monotone and Lipschitz
continuous, and we obtained strong convergence results when either
$\mathcal{A}$ or $\mathcal{B}$ is, in addition, required to be strongly
monotone. We also obtained a rate of convergence result and applied our
results to solving generalized Nash equilibrium problems in real reflexive
Banach spaces.

Acknowledgments.

The second author was partially supported by the Israel Science Foundation
(Grant 820/17), by the Fund for the Promotion of Research at the Technion and
by the Technion General Research Fund.

Declarations

Conflict of interest. The authors declare that they have no conflict of
interest.

Availability of data and material. Not applicable.

Code availability. Not applicable.

Authors’ contributions. All the authors contributed to this paper.

## References

  * [1] H. Attouch and A. Cabot, Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions, Appl. Math. Optim., 80 (2019), 547-598.
  * [2] V. Barbu, Nonlinear Differential Equations of Monotone Types in Banach Spaces. Springer, New York (2010).
  * [3] H.H. Bauschke, E. Matoušková and S. Reich, Projection and proximal point methods: convergence results and counterexamples, Nonlinear Anal., 56 (2004), 715-738.
  * [4] H.H. Bauschke, X. Wang and L. Yao, General resolvents for monotone operators: characterization and extension, In Biomedical Mathematics: Promising Directions in Imagine, Therapy Planning and Inverse Problem (Huangguoshu 2008), Y. Censor, M. Jiang and G.Wang (eds.), Medical Physics Plublishing, Madison, WI, USA, 57-74 (2010).
  * [5] D.P. Bertsekas, A. Nedic and A.E. Ozdaglar, Convex Analysis and Optimization. Athena Scientific, Belmont (2003).
  * [6] L.M. Bregman, The relaxation method for finding common points of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys., 7 (1967), 200-217.
  * [7] L.M. Bregman, Y. Censor and S. Reich, Dykstra’s algorithm as the nonlinear extension of Bregman’s optimization method, J. Convex Anal., 6 (1999), 319-333.
  * [8] R.E. Bruck and S. Reich, Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houston J. Math. 3 (1977), 459-470.
  * [9] D. Butnariu and A.N. Iusem, Totally Convex Functions for Fixed Points Computation and Infinite Dimensional Optimization. Springer, Dordrecht (2000).
  * [10] S.s. Chang, J.C. Yao, C.F. Wen and L.J. Qin, Shrinking projection method for solving inclusion problem and fixed point problem in reflexive Banach spaces, Optimization, (2020), https://doi.org/10.1080/02331934.2020.1763988.
  * [11] C.E. Chidume, Geometric Properties of Banach Spaces and Nonlinear iterations, Springer Verlag Series, Lecture Notes in Mathematics, ISBN 978-1-84882-189-7, (2009).
  * [12] P.L. Combettes and V.R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model Simul., 4 (2005), 1168-1200.
  * [13] V. Grimm, M. Hintermüller, O. Huber, L. Schewe, M. Schmidt, G. Zöttl, A PDE-constraints generalized Nash equilibrium approach for modeling gas markets with transport, (2021), https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/458.
  * [14] D.V. Hieu and P. Cholamjiak, Modified extragradient method with Bregman distance for variational inequalities, Appl. Anal., (2020), https://doi.org/10.1080/00036811.2020.1757078.
  * [15] Y.Y. Huang, J.C. Jeng, T.Y. Kuo, et al., Fixed point and weak convergence theorems for point-dependent $\lambda$-hybrid mappings in Banach spaces, Fixed Point Theory Appl. 2011;2011:105.
  * [16] L.O. Jolaoso and Y. Shehu, Single Bregman projection method for solving variational inequalities in reflexive Banach spaces, Appl. Anal., (2021), https://doi.org/10.1080/00036811.2020.1869947.
  * [17] P.L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), 964-979.
  * [18] H. Liu and J. Yang, Weak convergence of iterative methods for solving quasimonotone variational inequalities, Comput. Optim. Appl., 77 (2) (2020), 491-508.
  * [19] Y. Malitsky and M.K. Tam, A forward-backward splitting method for monotone inclusions without cocoercivity, SIAM J. Optim., 30 (2020), 1451-1472.
  * [20] V. Martin-Marquez, S. Reich and S. Sabach, Bregman strongly nonexpansive operators in reflexive Banach spaces, J. Math. Anal. Appl., 400 (2013), 597-614.
  * [21] B. Martinet, Régularisation d’inéquations variationnelles par approximations successives, Rev. Franćaise D’Inform. et de Rech. Opérationnelle 3 (1970), 154-158.
  * [22] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic, Berlin (2004).
  * [23] O. Nevanlinna and S. Reich, Strong convergence of contraction semigroups and of iterative methods for accretive operators in Banach spaces, Israel J. Math., 32 (1979), 44-58.
  * [24] F.U. Ogbuisi, On common solution of a monotone variational inclusion for two mappings and a fixed point problem, U. Politeh. Buch. Ser. A, 81 (2019), 111-122.
  * [25] F.U. Ogbuisi and C. Izuchukwu, Approximating a zero of sum of two monotone operators which solves a fixed point problem in reflexive Banach spaces, Numer. Funct. Anal. Optim., 41 (2020), 322-343.
  * [26] C.C. Okeke and C. Izuchukwu, Strong convergence theorem for split feasibility problems and variational inclusion problems in real Banach spaces, Rend. Circ. Mat. Palermo, 70 (2021), 457-480.
  * [27] B. Orouji, E. Soori, D. O’Regan and R.P. Agarwal, A strong convergence theorem for a finite family of Bregman demimetric mappings in a Banach space under a new shrinking projection method, J. Funct. Spaces, Volume 2021, Article ID 9551162, 11 pages, https://doi.org/10.1155/2021/9551162
  * [28] G.B. Passty, Ergodic convergence to a zero of the sum of monotone operators in Hilbert space, J. Math. Anal. Appl., 72 (1979), 383-390.
  * [29] D. Reem and S. Reich, Solutions to inexact resolvent inclusion problems with applications to nonlinear analysis and optimization, Rend. Circ. Mat. Palermo, 67 (2018), 337-371.
  * [30] S. Reich and S. Sabach, Two strong convergence theorems for a proximal method in reflexive Banach spaces, Numer. Funct. Anal. Optim., 31 (2010), 24-44.
  * [31] S. Reich and S. Sabach, A strong convergence theorem for a proximal-type algorithm in reflexive Banach spaces, J. Nonlinear Convex Anal., 10 (2009), 471-485.
  * [32] R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.
  * [33] Y. Shehu, Single projection algorithm for variational inequalities in Banach spaces with application to contact problem, Acta. Math. Sci., 40 (2020), 1045-1063.
  * [34] Y. Shehu, Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces, Results Math., 74 (2019), Article Number 138.
  * [35] P. Sunthrayuth, N. Pholasa and P. Cholamjiak, Mann-type algorithms for solving themonotone inclusion problem and the fixed point problem in reflexive Banach spaces, Ricerche di Matematica, (2021), https://doi.org/10.1007/s11587-021-00596-y.
  * [36] Y. Tang, R. Promkam, P. Cholamjiak and P. Sunthrayuth, Convergence results of iterative algorithms for the sum of two monotone operators in reflexive Banach spaces, Appl. Math., (2021), https://doi.org/10.21136/AM.2021.0108-20
  * [37] P. Tseng, A modified forward-backward splitting method for maximal monotone mappings, SIAM J. Control Optim., 38 (2000), 431-446.
  * [38] T.M. Tuyen, R. Promkam and P. Sunthrayuth, Strong convergence of a generalized forward-backward splitting method in reflexive Banach spaces, Optimization (2020), https://doi.org/10.1080/02331934.2020.


# Almost bi-Lipschitz embeddings and proper subsets of a Banach space - An
extension of a Theorem by M.I. Ostrovskii

F. Netillard  Université de Franche-Comté, Laboratoire de Mathématiques UMR
6623, 16 route de Gray, 25030 Besançon Cedex, FRANCE.
<EMAIL_ADDRESS>
###### Abstract.

Let $X$ and $Y$ be two infinite-dimensional Banach spaces. If $X$ is finitely
crudely representable in every finite-codimensional subspace of $Y$, then any
proper subset of $X$ almost bi-Lipschitz embeds into $Y$.

##  1\. Introduction

The typical problem of non linear Banach space theory is to decide if the
metric structure of a Banach space determines its linear structure. Given some
class $\mathcal{C}$ of non linear maps, we have therefore to decide which
linear properties of Banach spaces are stable under all maps in $\mathcal{C}$.
The non linear maps we use in this work are embeddings. It should be noted
that embeddings of discrete metric spaces into Banach spaces recently became
an important tool in computer science and topology. A familiar class in non
linear Banach space theory is constituted by the bi-Lipschitz embeddings which
are metric isomorphisms between the domain space and the range.
In recent years, it has become prevalent to investigate the embeddability of
spaces that are "thicker" than locally finite metric spaces (that is, metric
spaces in which each ball of finite radius has finite cardinality) into Banach
spaces. The problem is that in this case a bi-Lipschitz embedding is usually
unavailable. We need substitutes in order to make the embeddability as close
to the bi-Lipschitz embeddability as possible.
Along these lines, the condition of almost bi-Lipschitz embeddability
(introduced in [3]) happens to be useful. Under a condition of crude finite
representability (defined in the second part) of a Banach space $X$ in each
finite-codimensional subspace of another Banach space $Y$, we will show the
almost bi-Lipschitz embeddability of the proper subsets of $X$ into $Y$ (see
Theorem 1.4 below).
Two theorems (from [3] and [8]) lie in the background of our main result.

First of all, we recall the theorem of M.I. Ostrovskii, in the article [8]
(see also [9]).

######  Theorem 1.1.

Let $A$ be a locally finite metric space whose finite subsets admit uniformly
bi-Lipschitz embeddings into a Banach space $X$. Then $A$ admits a bi-
Lipschitz embedding into $X$.

This theorem is an improvement of the following result [3], where the notion
of crude finite representability shows up.

######  Theorem 1.2.

Let $X$ and $Y$ be two Banach spaces such that $X$ is finitely crudely
representable in $Y$.
Let $A\subset X$ such that $A$ is locally finite.
Then $A$ admits a bi-Lipschitz embedding into $Y$.

Local finiteness is a quite restrictive assumption, and it is natural to
wonder whether a similar general result on embeddings exists for a larger
class of metric spaces. For this purpose, we need the definition below.

######  Definition 1.3.

A metric space is said to be proper if all its closed balls are compact.

It is plain that locally finite metric spaces are proper, and Theorem 1.2
yields to the conjecture that any proper subset of a Banach space $X$ almost
bi-Lipschitz embeds (see definition below) into another Banach space $Y$ as
soon as $X$ is finitely crudely representable in $Y$. This motivated our work
(see chapter $4$ from [7]).

In connection with our work, F. Baudier et G. Lancien proved in [3], among
other results, that, for $p\in[1,+\infty]$ and $Y$ a Banach space which
contains uniformly the $\ell_{p}^{n}$ spaces, every proper subset $M$ of
$L_{p}$ almost bi-Lipschitzly embeds into $Y$. Baudier-Lancien’s proof of this
theorem provides a pattern for the proof of Theorem 1.4 below, which is the
main result of this paper.

######  Theorem 1.4.

Let $X$ and $Y$ be two Banach spaces.
Assume that $X$ is finitely crudely representable in the finite-codimensional
subspaces of $Y$. Let $M$ be a proper subset of $X$. Then $M$ almost bi-
Lipschitz embeds into $Y$.

##  2\. Preliminaries

###  2.1. Crudely finite representability

The concept of finite representability is due to R.C. James ([5] and [6]).

######  Definition 2.1.

Let $X$ and $Y$ be two infinite-dimensional Banach spaces, and $C>1$.
We say that $X$ is $C$-finitely crudely representable in $Y$ (in short
$C$-f.c.r) if for any finite-dimensional subspace $E$ of $X$, there is a
linear isomorphism from $E$ to the space $T(E)\subset Y$ verifying
$\|T\|\cdot\|T^{-1}\|<C$.

When the value of $C$ does not matter, we will simply say that $X$ is f.c.r.
in $Y$.

######  Definition 2.2.

We say that $X$ is finitely representable in $Y$ if, for all $\varepsilon>0$,
$X$ is $(1+\varepsilon)$-f.c.r in $Y$ for all $\varepsilon>0$.

######  Definition 2.3.

Let $X$ and $Y$ be two infinite-dimensional Banach spaces. We say that $X$ is
f.c.r in the finite-codimensional subspaces of $Y$ if there exists a constant
$C>1$ such that, for all $Z\in\textnormal{cof}(Y)$, $X$ is $C$-f.c.r in $Z$.

######  Remark 2.4.

Note that in the above definition, the constant $C$ is uniform on all finite-
codimensional subspaces. By Proposition 4.1 of [4], f.c.r in $Y$ does not
imply f.c.r in the finite-codimensional subspaces of $Y$. Our partial analogue
of Theorem 1.2 requests a strengthening of the assumption $X$ f.c.r in $Y$.

###  2.2. Almost bi-Lipschitz embeddings

Almost bi-Lipschitz embedding are defined in [3] and in [2]. Let $(M,d)$ and
$(N,\delta)$ be two metric spaces, and $f$ a map from $M$ into $N$. Let

$\rho_{f}(t)=\textnormal{inf}\\{\delta(f(x),f(y)):d(x,y)\geq
t\\}~{}(\textnormal{compression modulus of }f),$

and

$\omega_{f}(t)=\textnormal{sup}\\{\delta(f(x),f(y)):d(x,y)\leq
t\\}~{}(\textnormal{expansion modulus of }f).$

Denote $\Phi=\\{\varphi:[0,\infty)\rightarrow[0,1)$ continuous such that
$\varphi(0)=0$ and $\varphi(t)>0$ $\forall t>0\\}$.

We say that $M$ almost bi-Lipschitzly embeds into $N$ if there exists a
scaling factor $r\in(0,\infty)$, a constant $D$, and a family
$(f_{\varphi})_{\varphi\in\Phi}$ of maps from $M$ into $N$ such that, for all
$t\in(0,\infty)$,

$\omega_{f_{\varphi}}(t)\leq Drt$

and

$\rho_{f_{\varphi}}(t)\geq rt\varphi(t).$

In other words, $M$ is almost bi-Lipschitz embeddable into $N$ if there exist
a scaling factor $r\in(0,\infty)$ and a constant $D\in[1,\infty)$ such that
for any continuous function $\varphi\in\Phi$, there exists a map
$f_{\varphi}:M\rightarrow N$ such that:

$\forall~{}x,y\in
M,~{}\varphi(d(x,y))rd(x,y)\leq\delta(f_{\varphi}(x),f_{\varphi}(y))\leq
Drd(x,y).$

###  2.3. Banach spaces containing the $\ell_{p}^{n}$’s uniformly

The definitions below are classical items from the local theory of Banach
spaces.

######  Definition 2.5.

Let $\lambda\in[1,\infty)$ and $p\in[1,\infty]$.
We say that a Banach space contains $\lambda$-uniformly the $\ell_{p}^{n}$’s
if there exists a sequence of subspaces $(E_{n})_{n=1}^{\infty}$ of $X$ such
that $E_{n}$ is linearly isomorphic to $\ell_{p}^{n}$ with

$d_{BM}(E_{n},\ell_{p}^{n})\leq\lambda$,

where $d_{BM}$ is the Banach-Mazur distance between Banach spaces.

######  Definition 2.6.

Let $p\in[1,\infty]$.
We say that $X$ contains the $\ell_{p}^{n}$ ’s uniformly if it contains
$\lambda$-uniformly the $\ell_{p}^{n}$’s for some value
$\lambda\in[1,\infty)$.

##  3\. Main results

The following lemma is shown in [3].

######  Lemma 3.1.

For any continuous function $\varphi:[0,+\infty)\rightarrow[0,1)$ such that
$\varphi(0)=0$ and $\varphi(t)>0$ for all $t>0$, there exists a continuous
non-decreasing surjective function $\mu:(0,+\infty)\rightarrow(-\infty,0)$, so
that $\varphi(t)\leq 2^{\mu(t)}$ for all $t>0$.

We will need the next lemma, inspired by Lemma 2.6 from [3], to establish
Theorem 1.4.

######  Lemma 3.2.

Let $X$ and $Y$ be two Banach spaces. We assume that $X$ is f.c.r in the
finite-codimensional subspaces of $Y$.
Let $\gamma>0$, $(F_{j})_{j=1}^{\infty}$ be a family of finite dimensional
subspaces of $X$.
Then there exists a family $(H_{j})_{j=1}^{\infty}$ of finite dimensional
subspaces of $Y$ such that, for all $j$, $d_{BM}(H_{j},F_{j})\leq C$ and
$(H_{j})_{j=1}^{\infty}$ is an FDD of
$Z=\overline{\textnormal{Span}}(\bigcup_{j=1}^{\infty}H_{j})\subseteq Y$ with
$\|P_{j}\|\leq 1+\gamma$ where $P_{j}$ is the projection of $Z$ onto
$H_{1}\oplus\cdots\oplus H_{j}$ whose kernel is
$\overline{\textnormal{Span}}(\bigcup_{i=j+1}^{\infty}H_{i})$.

###### Proof.

Pick a sequence $(\gamma_{j})_{j=1}^{\infty}$ with $\gamma_{j}>0$ and
$\prod\limits_{j=1}^{\infty}(1+\gamma_{j})\leq 1+\gamma$.
We proceed by induction on $j\in\mathbb{N}$.
Since $X$ is $C$-finitely crudely representable in $Y$, there exists a finite-
dimensional subspace $H_{1}$ of $Y$ so that $d_{BM}(H_{1},F_{1})\leq C$.
Using the standard Mazur technique, we can find a finite-codimensional
subspace $Z$ of $Y$ so that

$H_{1}+Z_{1}=H_{1}\oplus Z_{1}$,

and a projection $P_{1}:H_{1}\oplus Z_{1}\rightarrow H_{1}$ whose kernel is
$Z_{1}$ and which satisfies

$\|P_{1}\|\leq 1+\gamma_{1}$.

Assume now that, for some integer $j\in\mathbb{N}$, there exists
$H_{1},\cdots,H_{j}$ so that

$d_{BM}(H_{i},F_{i})\leq C$ for any $i\in\\{1,\cdots,j\\}$,

$H_{1}+\cdots+H_{j}=H_{1}\oplus\cdots\oplus H_{j}$,

and $(H_{1}+\cdots+H_{j})+Z_{j}=(H_{1}+\cdots+H_{j})\oplus Z_{j}$,
with $P_{j}:(H_{1}+\cdots+H_{j})\oplus Z_{j}\rightarrow H_{1}+\cdots+H_{j}$ a
projection whose kernel is $Z_{j}$ and which satisfies

$\|P_{j}\|\leq\prod\limits_{i=1}^{j}(1+\gamma_{i})$.

Then, using the standard Mazur technique, we can find a subspace $Z_{j+1}$ of
$Z_{j}$ which is a finite-codimensional subspace of $Y$, and

$\forall~{}y\in H_{1}+\cdots+H_{j}~{}~{}\forall~{}z\in
Z_{j+1},~{}\|y\|\leq(1+\gamma_{j+1})\|y+z\|$.

Since $X$ is $C$-finitely crudely representable in $Z_{j}$, there exists a
finite-codimensional subspace $H_{j+1}$ of $Z_{j+1}$ so that
$d_{BM}(H_{j+1},F_{j+1})\leq C$.
It is then immediate to conclude that the sequence $(H_{j})_{j=1}^{\infty}$
satisfies the desired property. ∎

We can now prove our main result, Theorem 1.4.

###### Proof.

We adapt the proof of the Theorem $2.7$ of [3].
Let $B_{k}=\\{x\in M,~{}\|x\|\leq 2^{k+1}\\}$ for $k\in\mathbb{Z}$.
Since $M$ is a proper subset of $X$, $B_{k}$ is a compact subset of $X$.
Let $G_{k,n}$ be a $\varepsilon_{k,n}$-net of $B_{k}$ containing $0$ (we will
specify $\varepsilon_{k,n}$ later) , where $n\in\mathbb{N}$.
Let $\varphi_{k,n}$ be a map from $B_{k}$ to $G_{k,n}$ such that

$\forall~{}x\in B_{k},~{}~{}\|x-\varphi_{k,n}(x)\|=d(x,G_{k,n}).$

Thereby:

$\forall~{}x,y\in
B_{k},~{}\|x-y\|-\varepsilon_{k,n}\leq\|\varphi_{k,n}(x)-\varphi_{k,n}(y)\|\leq\|x-y\|+\varepsilon_{k,n}.$

By the previous lemma, we can construct a family of finite dimensional
subspaces $(H_{j})_{j=1}^{\infty}$ of $Y$ and linear isomorphisms
$R_{k,j}:\textnormal{Vect}(G_{k,j})\rightarrow H_{j}$ such that
$\|R_{k,j}\|\leq 1$ and $\|R_{k,j}^{-1}\|\leq C$, with
$(H_{j})_{j=1}^{\infty}$ FDD of
$Z=\overline{\textnormal{Span}}(\bigcup_{j=1}^{\infty}H_{j})$.
Let $\gamma>0$. We will specify later the choice of $\gamma$.
We note $P_{n}$ the projection of $Z$ on $H_{1}\oplus\cdots\oplus H_{n}$.
Using the previous lemma, we can assume that $\|P_{n}\|\leq 1+\gamma$ for any
$n\in\mathbb{N}$.
We put, for $n\in\mathbb{N}$, $f_{k,n}=R_{k,n}\circ\varphi_{k,n}$.
So:

$\forall~{}x,y\in
B_{k},~{}\frac{1}{C}(\|x-y\|-2\varepsilon_{k,n})\leq\|f_{k,n}(x)-f_{k,n}(y)\|\leq\|x-y\|+2\varepsilon_{k,n}.$

We define:

$f_{k}:B_{k}\rightarrow\displaystyle\sum\limits_{n\geq 1}H_{n}$

$x\mapsto\displaystyle\sum\limits_{n=1}^{\infty}2^{-n}f_{k,n}(x)$
Let $\mu:(0,+\infty)\rightarrow(-\infty,0)$ be an increasing surjective
continuous function, and $\sigma:(-\infty,0)\rightarrow(0,+\infty)$ the
function defined by $\sigma(y)=\textnormal{inf}\\{x\in(0,+\infty):\mu(x)\geq
y\\}$, with the convention inf $\emptyset=\infty$.
We put
$\varepsilon_{k,n}=\textnormal{min}(2^{-k},2^{k})\times\textnormal{min}\left(\frac{\sigma(-n)}{\eta},1\right)$
where $\eta>2$ will be determined later. So:

$\displaystyle\left\|\displaystyle\sum\limits_{n=1}^{\infty}2^{-n}(f_{k,n}(x)-f_{k,n}(y))\right\|$
$\displaystyle\leq\left(\displaystyle\sum\limits_{n=1}^{\infty}2^{-n}\right)\|x-y\|+2.\textnormal{min}(2^{-k},2^{k})\displaystyle\sum\limits_{n=1}^{\infty}\left[2^{-n}\textnormal{min}\left(\frac{\sigma(-n)}{\eta},1\right)\right]$
$\displaystyle\leq\|x-y\|+2.\textnormal{min}(2^{-k},2^{k}).$

Thus: $\|f_{k}(x)-f_{k}(y)\|\leq\|x-y\|+2.\textnormal{min}(2^{-k},2^{k})$.

We define:

$f:M\rightarrow Y$

$x\mapsto\lambda_{x}f_{k}(x)+(1-\lambda_{x})f_{k+1}(x)$, if
$2^{k}\leq\|x\|\leq 2^{k+1}$ where $k\in\mathbb{Z}$,
with $\lambda_{x}=\frac{2^{k+1}-\|x\|}{2^{k}}$.
The rest of the proof will be divided into two parts.
In the first part, it is proven that $f$ is a Lipschitz map. The proof
requires the inequality obtained for $f_{k}$, the definition of $f$ in terms
of the dyadic slicing and the triangle inequality.
In the second part, an estimate of the compression function of $f$ is given.

Part 1. Upper bound
Let $x,y\in M$. Assume that $\|x\|\leq\|y\|$. Note that $f(0)=0$.

Case 1. If $\|x\|\leq\frac{1}{2}\|y\|$ and $2^{k}\leq\|y\|<2^{k+1}$, where
$k\in\mathbb{Z}$, then

$\displaystyle\|f(x)-f(y)\|$ $\displaystyle\leq\|f(x)-f(0)\|+\|f(y)-f(0)\|$
$\displaystyle\leq\|x\|+\|y\|+4.2^{k+1}$
$\displaystyle\leq\frac{3}{2}\|y\|+8\|y\|$ $\displaystyle\leq 19(\|y\|-\|x\|)$
$\displaystyle\leq 19\|x-y\|.$

Case 2. $\frac{1}{2}\|y\|<\|x\|\leq\|y\|$. We observe that
$\|y-x\|\geq\|y\|-\|x\|\geq\frac{1}{2}\|y\|$.
We consider two sub-cases.

Case 2.a. $2^{k}\leq\|x\|\leq\|y\|<2^{k+1}$, where $k\in\mathbb{Z}$.
For $\lambda_{x}=\frac{2^{k+1}-\|x\|}{2^{k}}$ and
$\lambda_{y}=\frac{2^{k+1}-\|y\|}{2^{k}}$, we have

$|\lambda_{x}-\lambda_{y}|=\frac{\|y\|-\|x\|}{2^{k}}\leq\frac{\|x-y\|}{2^{k}}.$

Therefore

$\displaystyle\|f(x)-f(y)\|$
$\displaystyle=\|\lambda_{x}f_{k}(x)-\lambda_{y}f_{k}(y)+(1-\lambda_{x})f_{k+1}(x)-(1-\lambda_{y})f_{k+1}(y)\|$
$\displaystyle\leq\lambda_{x}\|f_{k}(x)-f_{k}(y)\|+(1-\lambda_{x})\|f_{k+1}(x)-f_{k+1}(y)\|+2|\lambda_{x}-\lambda_{y}|(\|y\|+2^{k+2})$
$\displaystyle\leq\|x-y\|+2^{k+2}+(2^{k+2}+2^{k+3})\dfrac{\|x-y\|}{2^{k}}$
$\displaystyle\leq 13\|x-y\|+2^{k+2}$ $\displaystyle\leq 13\|x-y\|+4\|y\|$
$\displaystyle\leq 21\|x-y\|.$

Case 2.b. $2^{k}\leq\|x\|<2^{k+1}\leq\|y\|<2^{k+2}$, where $k\in\mathbb{Z}$.
Let $\lambda_{x}=\dfrac{2^{k+1}-\|x\|}{2^{k}}$ and
$\lambda_{y}=\dfrac{2^{k+2}-\|y\|}{2^{k+1}}$.
We have $\lambda_{x}\leq\dfrac{\|x-y\|}{2^{k}}$, and so $\lambda_{x}\|x\|\leq
2\|x-y\|$.
In the same way:
$1-\lambda_{y}=\frac{\|y\|-2^{k+1}}{2^{k+1}}\leq\frac{\|x-y\|}{2^{k+1}}$, and
$(1-\lambda_{y})\|y\|\leq 2\|x-y\|$.
It follows that:

$\displaystyle\|f(x)-f(y)\|$
$\displaystyle=\|\lambda_{x}f_{k}(x)+(1-\lambda_{x})f_{k+1}(x)-\lambda_{y}f_{k+1}(y)-(1-\lambda_{y})f_{k+2}(y)\|$
$\displaystyle\leq\lambda_{x}(\|f_{k}(x)\|+\|f_{k+1}(x)\|)+(1-\lambda_{y})(\|f_{k+1}(y)\|+\|f_{k+2}(y)\|)$
$\displaystyle{}\hskip 199.16928pt+\|f_{k+1}(x)-f_{k+1}(y)\|$
$\displaystyle\leq\lambda_{x}(2\|x\|+2^{k+3})+(1-\lambda_{y})(2\|y\|+2^{k+4})+\|x-y\|+2^{k+2}$
$\displaystyle\leq 10\lambda_{x}\|x\|+10(1-\lambda_{y})\|y\|+\|x-y\|+2\|y\|$
$\displaystyle\leq 20\|x-y\|+20\|x-y\|+\|x-y\|+4\|x-y\|=45\|x-y\|.$

Part 2. Lower bound
Let $x,y\in M$.
Assume that $\|x\|\leq\|y\|$.
We put, for $k\in\mathbb{Z}$ and $n\in\mathbb{N}$,
$Q_{k,n}=R_{k,n}^{-1}\circ\Pi_{n}$, where $\Pi_{1}=P_{1}$, and
$\Pi_{n}=P_{n}-P_{n-1}$ when $n$ is greater than or equal to $2$.
For the sequel, we also assume that $2^{k}\leq\|x\|<2^{k+1}$ and
$2^{l}\leq\|y\|<2^{l+1}$, where $(k,l)\in\mathbb{Z}^{2}$.
• Assume first that $\|x-y\|<\sigma(-1)$.
Let then $n\in\mathbb{N}$ such

$\sigma(-(n+1))\leq\|x-y\|<\sigma(-n),$

in other words

$-(n+1)\leq\mu(\|x-y\|)<-n.$

Then:

$\displaystyle Q_{k,n+1}(f(x))$
$\displaystyle=2^{-(n+1)}\lambda_{x}\varphi_{k,n+1}(x),$ $\displaystyle
Q_{k+1,n+1}(f(x))$
$\displaystyle=2^{-(n+1)}(1-\lambda_{x})\varphi_{k+1,n+1}(x),$ $\displaystyle
Q_{l,n+1}(f(y))$ $\displaystyle=2^{-(n+1)}\lambda_{y}\varphi_{l,n+1}(y),$
$\displaystyle Q_{l+1,n+1}(f(y))$
$\displaystyle=2^{-(n+1)}(1-\lambda_{y})\varphi_{l+1,n+1}(y),$
$\displaystyle\textnormal{and }Q_{r,n+1}(f(x))$
$\displaystyle=Q_{s,n+1}(f(y))=0\textnormal{ for
}r\notin\\{k,k+1\\},~{}s\notin\\{l,l+1\\}.$

Therefore:

$\displaystyle(Q_{r_{1},n+1}+\cdots+Q_{r_{s},n+1})(f(x)-f(y))=$ $\displaystyle
2^{-(n+1)}[\lambda_{x}\varphi_{k,n+1}(x)+(1-\lambda_{x})\varphi_{k+1,n+1}(x)$
$\displaystyle-\lambda_{y}\varphi_{l,n+1}(y)-(1-\lambda_{y})\varphi_{l+1,n+1}(y)]$

with $s\in\\{2,3,4\\}$ and $r_{1},\cdots,r_{s}\in\\{k,k+1,l,l+1\\}$.
We will now use the following inequality:

$\underset{r\in\\{k,k+1,l,l+1\\}}{\textnormal{max}}\|\varphi_{r,n+1}(x)-x\|\leq\frac{\sigma(-(n+1))}{\eta}.$

This allows us to get:

$\displaystyle\|(Q_{r_{1},n+1}+\cdots+Q_{r_{s},n+1})(f(x)-f(y))\|$
$\displaystyle\geq
2^{-(n+1)}\left(\|x-y\|-\frac{2\sigma(-(n+1))}{\eta}\right)$
$\displaystyle\geq 2^{-(n+1)}\frac{\eta-2}{\eta}\|x-y\|.$

As $\|Q_{r_{1},n+1}+\cdots+Q_{r_{s},n+1}\|\leq 8C(1+\gamma)$, we deduce

$\|f(x)-f(y)\|\geq\frac{2^{-(n+1)}(\eta-2)\|x-y\|}{8\eta
C(1+\gamma)}\geq\frac{2^{\mu(\|x-y\|)}(\eta-2)\|x-y\|}{16\eta C(1+\gamma)}.$

• Assume now that $\|x-y\|\geq\sigma(-1)$ or equivalently that
$-1\leq\mu(\|x-y\|)$.
So, using the maps $Q_{k,1},Q_{k+1,1},Q_{l,1}$ and $Q_{l+1,1}$ instead of
$Q_{k,n+1},Q_{k+1,n+1},Q_{l,n+1}$, and $Q_{l+1,n+1}$, we obtain that

$\|f(x)-f(y)\|\geq\frac{(\eta-2)\|x-y\|}{16\eta C(1+\gamma)}.$

Since $\mu\leq 0$, it follows that

$\|f(x)-f(y)\|\geq\frac{2^{\mu(\|x-y\|)}(\eta-2)\|x-y\|}{16\eta C(1+\gamma)}.$

Since $\gamma$ can be chosen as small and $\eta$ as large as desired, thanks
to Lemma 3.1, this concludes our proof. ∎

######  Corollary 3.3.

Let $X$ and $Y$ be two Banach spaces.
If $X$ is f.c.r in the finite-codimensional subspaces of $Y$, then for any
$Z\in\textnormal{cof}(Y)$, for any proper subset $M$ of $X$, $M$ almost bi-
Lipschitz embeds into $Z$.

######  Remark 3.4.

Corollary 2.8 from [3] is a special case of this last result. This corollary
says that, for $M$ a proper subset of $L_{p}$ ($p\in[1,\infty]$), and $X$ a
Banach space containing uniformly the $\ell_{p}^{n}$’s, $M$ almost bi-
Lipschitz embeds into $X$. Indeed, the following assertions are equivalent,
for an infinite-dimensional Banach space $X$ and $p\in[1,\infty]$:
$(i)$ $X$ contains the $\ell_{p}^{n}$’s uniformly.
$(ii)$ $L_{p}$ is finitely representable in $X$.
$(iii)$ $L_{p}$ is f.c.r in the finite-codimensional subspaces of $X$.
A proof is given in [7].

######  Definition 3.5.

A Banach space $X$ is said to be locally minimal if there exists a constant
$K>1$ such that $X$ is $K$-f.c.r in each of its infinite-dimensional
subspaces.

######  Examples 3.6.

$c_{0}$, $\ell_{p}$ for $1\leq p<\infty$, and the Tsirelson space $T^{*}$ are
such spaces.

With this last definition, the following corollary is an obvious consequence
of Theorem 1.4:

######  Corollary 3.7.

Let $X$ and $Y$ be two Banach spaces such that $Y$ is locally minimal, and $X$
is finitely representable in $Y$.
Let $M$ be a proper subset of $X$. Then $M$ almost bi-Lipschitz embeds into
$Y$.

## References

  * [1]
  * [2] F. Baudier, Barycentric gluing and geometry of stable metrics, Rev. R. Acad. Cienc. Exactas Fís. Nat. Ser. A Mat. RACSAM, no. 1, (2022), Paper No. 37, 48pp.
  * [3] F. Baudier and G. Lancien, Tight embeddability of proper and stable metric spaces, Anal. Geom. Metr. Spaces, 3, (2015), 140–156.
  * [4] V. Ferenczi and C. Rosendal, Banach spaces without minimal subspaces, J. Funct. Anal., 257 (1), (2009), 149–193.
  * [5] R.C. James, Superreflexive Banach spaces, Canadian J. Math., 24, (1972), 896–904.
  * [6] R.C. James, Superreflexive spaces with bases, Pacific J. Math., 41–42, (1972), 409–419.
  * [7] F. Netillard, Plongements grossièrement Lipschitz et presque Lipschitz dans les espaces de Banach. Analyse fonctionnelle [math.FA], Université de Bourgogne Franche-Comté, (2019). <NNT: 2019UBFCD020>. <tel-02378971>
  * [8] M.I. Ostrovskii, Embeddability of locally finite metric spaces into Banach spaces is finitely determined, Proc. Amer. Math. Soc., 140, (2012), 2721–2730.
  * [9] M.I. Ostrovskii, Metric embeddings: bilipschitz and coarse embeddings into Banach spaces, De Gruyter Studies in Mathematics, 49, Walter de Gruyter & Co., Berlin, (2013).