remarkRemark hypothesisHypothesis claimClaim exampleExample An inertial
proximal method for bilevel equilibriaA.Balhag, Z. Mazgouri , M. Théra
ex_supplement

# Weak and strong convergence of an inertial proximal method for solving
bilevel monotone equilibrium problems††thanks: Submitted to the editors DATE.
Research of Aïcha Balhag was supported by the EIPHI Graduate School (contract
ANR-17-EURE-0002) and research of Michel Théra was supported by a public grant
as part of the Investissement d’avenir project, reference
ANR-11-LABX-0056-LMH, LabEx LMH.

A. Balhag Institut de Mathématiques de Bourgogne, UMR 5584 CNRS, Université
Bourgogne Franche-Comté, F-2100 Dijon, France<EMAIL_ADDRESS>Z.
Mazgouri ORCID 0000-0003-0131-4741, National School of Applied Sciences, Sidi
Mohamed Ben Abdellah University, Laboratory LAMA Mathematics, 30000 Fez,
Morocco<EMAIL_ADDRESS>Michel Théra ORCID 0000-0001-9022-6406,
Laboratoire XLIM UMR-CNRS 7252, Université de Limoges, 87032 Limoges, France
and Federation University Australia, Ballarat 3353, Australia ).
<EMAIL_ADDRESS>
###### Abstract

In this paper, we introduce an inertial proximal method for solving a bilevel
problem involving two monotone equilibrium bifunctions in Hilbert spaces.
Under suitable conditions and without any restrictive assumption on the
trajectories, the weak and strong convergence of the sequence generated by the
iterative method are established. Two particular cases illustrating the
proposed method are thereafter discussed with respect to hierarchical
minimization problems and equilibrium problems under saddle point constraint.
Furthermore, a numerical example is given to demonstrate the implementability
of our algorithm. The algorithm and its convergence results improve and
develop previous results in the field.

###### keywords:

Bilevel Equilibrium problems; Monotone bifunctions; Proximal algorithm; Weak
and strong convergence; Equilibrium Fitzpatrick transform.

90C33, 49J40, 46N10, 65K15, 65K10

Let $K$ be a nonempty closed and convex subset of a real Hilbert space $H$,
and let $f:K\times K\rightarrow\mathbb{R}$ be a real-valued bifunction. The
equilibrium problem [9] associated with the bifunction $f$ on $K$ is stated as
follows: find $\bar{x}\in K$ such that

($EP$) $f(\bar{x},y)\geq 0,\;\;\forall y\in K.$

This abstract variational formulation constitutes a convenient unified
mathematical model for many problems in applied mathematics such as
optimization problems, variational and hemivariational inequalities, fixed-
point and saddle point problems, network equilibrium problems, Nash
equilibrium and others, see for instance [9, 13, 15, 24] and the bibliography
therein.

One of the most popular algorithm for solving $(EP)$ is the proximal point
method $(PPM)$ extended from variational inequalities to equilibrium problems
by Moudafi [25]. In this regard, by introducing the resolvent of the
bifunction $f$ (see, [9]), defined, for $\lambda>0$, by

$J_{\lambda}^{f}(x):=\\{z\in K:f(z,y)+\frac{1}{\lambda}\langle
z-x,y-z\rangle\geq 0,\;\forall y\in K\\},$

the author in [25] suggested a basic version of $(PPM)$ for $(EP)$ in the
monotone framework. This method generates the next iterate $x_{n+1}$, for each
$n\geq 0$, by solving the following subproblem $x_{n+1}=J_{r_{n}}^{f}(x_{n})$,
i.e.,

(1) $f(x_{n+1},y)+\frac{1}{r_{n}}\langle x_{n+1}-x_{n},y-x_{n+1}\rangle\geq
0,\;\;\forall y\in K,$

where $\\{r_{n}\\}$ is a sequence of nonnegative numbers.
Under the monotonicity condition on $f,$ Moudafi proved the weak convergence
of the sequence $\\{x_{n}\\}$ generated by algorithm (1) to a solution of
$(EP)$. Thereby, a great interest has been brought to the study of $(EP)$ by
means of splitting proximal point (or backward) methods; one can consult [4,
14, 28] and the references therein.

Given its growing interest in applications to different applied domains, the
problem $(EP)$ is currently considered as one of the important research
directions in which the optimization community is interested. Indeed, the
study of the existence of a solution to this problem still falls within the
scope of very recent studies concerning new methods of resolution. Let us
quote in this sense the paper [20] in which the authors, by using the
celebrated Ekeland variational principle under a weaker notion of continuity
and without any convexity assumptions, studied the existence of equilibria and
quasi-equilibria in the setting of metric spaces. The bibliography of this
article refers to new equilibrium concepts in which quasi-monotonicity and
quasi-convexity are relaxed.
In this paper, we study the problem $(EP)$ in a general framework where we
focus our interest on the following bilevel equilibrium problem: find
$\bar{x}\in S_{f}$ such that

($BEP$) $g(\bar{x},y)\geq 0,\;\;\forall y\in S_{f},$

where $g:K\times K\rightarrow\mathbb{R}$ is another real-valued bifunction and
$S_{f}$ stands for the set of constraints defined by solutions to the second
level equilibrium problem $(EP)$ given by $S_{f}:=\\{u\in K:f(u,y)\geq
0\;\;\forall y\in K\\}.$ We denote by $S$ the set of solutions to $(BEP)$
which we assume to be nonempty.

The problem $(BEP)$ was implicitly introduced in the paper by Chadli, Chbani
and Riahi [15] in the setting of the so-called viscosity principle for
equilibrium problems. This principle aims at a good selection of the upper
equilibrium among solutions to the lower level equilibrium problem. This class
of hierarchical problems covers in both levels, all the cases cited previously
for an equilibrium problem. Besides their unification aspect, bilevel
equilibrium problems has proved over the past two decades, very good
applicability in different fields covering mechanics, engineering sciences and
economy, see [21] and references therein. Greater attention was then paid to
this class of problems regarding the existence of solutions via dynamical and
algorithmic approaches and also from the point of view of parametric
stability. The interested reader can consult the following recent
investigations [1, 8, 16, 19, 27, 34] and the references therein. In recent
years, algorithmic resolution procedures have been widely studied for solving
$(BEP)$. Moudafi [27] introduced, by using the penalty method [15], the
regularized proximal point method $(RPPM)$ for solving $(BEP)$. This algorithm
is described as follows: from a starting point $x_{0}\in K$, for each $n\geq
0$, the next iterate $x_{n+1}$ is defined by the proximal iteration
$x_{n+1}:=J_{\lambda_{n}}^{f+\beta_{n}g}(x_{n})$, i.e.,

(2) $f(x_{n+1},y)+\beta_{n}g(x_{n+1},y)+\dfrac{1}{\lambda_{n}}\langle
x_{n+1}-x_{n},y-x_{n+1}\rangle\geq 0,\;\;\forall y\in K,$

where $\\{\beta_{n}\\}$ and $\\{\lambda_{n}\\}$ are two sequences of
nonnegative reals. More precisely, under suitable assumptions on the
bifunctions $f$ and $g$, Moudafi proved that the sequence $\\{x_{n}\\}$
generated by algorithm (2) converges weakly to a solution of $(BEP)$ provided
that

$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}>0,\displaystyle\sum_{n=0}^{+\infty}\lambda_{n}\beta_{n}<+\infty\;\text{
and }\;\|x_{n+1}-x_{n}\|=o(\beta_{n}).$

The drawback of the last assumption is the difficulty to choose such a control
sequence $(\beta_{n})$ because we do not know the convergence rate of
$\|x_{n+1}-x_{n}\|$. The author in [27] conjectured that this restrictive
assumption can be removed via the introduction of a conditioning notion for
equilibrium bifunctions.

Later on, the authors in [19] considered an alternate proximal scheme, which
generates the next iterates $x_{n+1}$ by solving the regularized problem
$x_{n+1}:=J_{\lambda_{n}}^{\beta_{n}f+g}(x_{n})$, i.e.,

$\beta_{n}f(x_{n+1},y)+g(x_{n+1},y)+\dfrac{1}{\lambda_{n}}\langle
x_{n+1}-x_{n},y-x_{n+1}\rangle,\;\;\forall y\in K.$

Here, the difficulty of the method $(RPPM)$ mentioned in [27] has been solved.
Following [5] and under a similar geometric assumption formulated in terms of
the Fenchel conjugate function associated to the bifunction $f$, they analyzed
both the weak and strong convergence of their algorithm to a solution of
$(BEP)$. More recently, in [31], the authors proposed a forward-forward
algorithm and a forward-backward algorithm for solving $(BEP)$ under quite
mild conditions where the bifunction of the two level equilibrium problems are
supposed pseudomonotone.

As a continuity of the studies of equilibrium problems by means of proximal
iterative methods, we propose an inertial proximal method for solving $(BEP)$.
It is well known that the inertial proximal iteration, where the next iterate
is defined by making use of the previous two iterates, may be interpreted as
an implicit discretization of differential systems of second order in time.
The presence of inertial terms improves the convergence behavior of the
generated sequences. We emphasize that the origin of these methods dates back
to [3] as part of the approach to a solution of an abstract inclusion of the
form: find $\bar{x}\in H$ such that

(3) $0\in A(\bar{x}),$

where $A:H\rightrightarrows H$ is a maximally monotone operator and the
solution set $A^{-1}(\\{0\\})$ is assumed to be nonempty. In this regard,
giving two sequences of nonnegative numbers $\\{\alpha_{n}\\}$ and
$\\{\lambda_{n}\\}$, the authors in [3] considered the following iterative
scheme:

$x_{n+1}-x_{n}-\alpha_{n}(x_{n}-x_{n-1})+\lambda_{n}A(x_{n+1})\ni 0,$

and proved the weak convergence of the sequence $\\{x_{n}\\}$ generated by the
above algorithm towards a solution of (3) under appropriate conditions on the
parameters $\\{\alpha_{n}\\}$ and $\\{\lambda_{n}\\}$ whenever the restrictive
assumption
$\displaystyle\sum_{n=1}^{+\infty}\alpha_{n}\|x_{n}-x_{n-1}\|^{2}<+\infty$
holds.

Inspired by the results presented in [26] in the framework of solving $(EP)$
by an approximate second order differential proximal procedure, and also
illuminated by the results explored in [19, 27], we propose a new approximate
inertial proximal scheme to solve $(BEP)$:

Algorithm: $($Inertial proximal algorithm $(IPA))$.  Initialization: Choose
positive sequences $\\{\beta_{n}\\}$, $\\{\lambda_{n}\\}$, and a nonnegative
real number $\alpha\in[0,1]$. Take arbitrary $x_{0},x_{1}\in K$.  Iterative
step: For every $n\geq 1$ and given current iterates $x_{n-1},x_{n}\in K$ set
$y_{n}:=x_{n}+\alpha(x_{n}-x_{n-1})$ and define $x_{n+1}\in K$ by
$x_{n+1}:=J_{\lambda_{n}}^{\beta_{n}f+g}(y_{n}),$ i.e.,

(4) $\beta_{n}f(x_{n+1},y)+g(x_{n+1},y)+\frac{1}{\lambda_{n}}\langle
x_{n+1}-y_{n},y-x_{n+1}\rangle\geq 0,\;\;\forall y\in K.$

In the above algorithm, $\\{\lambda_{n}\\}$ denotes the sequence of step
sizes, $\\{\beta_{n}\\}$ the sequence of penalization parameters, and
$\alpha\in[0,1]$ the parameter that controls the inertial terms. The proposed
numerical scheme recovers, when $\alpha=0$, the algorithm investigated in
[19], and if in addition $f=0$, the one suggested in [25]. The Fitzpatrick
transform of the bifunction $f$ will be a key ingredient in our convergence
analysis. Indeed, we provide conditions under which the sequence generated by
the algorithm $(IPA)$ weakly or strongly converges to a solution of $(BEP)$.
More precisely, under a discrete counterparts (6) of the geometric condition
used in [16] and formulated in terms of the Fitzpatrick transform of the
bifunction $f$, we first prove that (see Theorem 1) the sequence generated by
$(IPA)$ weakly converges to a solution of $(BEP)$ provided that
$0\leq\alpha<\frac{1}{3}$,
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}>0$ and
$\displaystyle\lim_{n\rightarrow+\infty}\beta_{n}=0$. Afterwards, by
strengthening the monotonicity assumption on the upper level bifunction $g$,
and whenever $0\leq\alpha<\frac{1}{3}$ and
$\displaystyle\sum_{n=1}^{\infty}\lambda_{n}=+\infty$, we show (see Theorem 2)
the strong convergence of the trajectories generated by the proposed algorithm
to the unique solution of $(BEP)$. Then, we show (see Theorem 3) that, without
the need of the geometric assumption (6), the sequence converges strongly to
the unique solution of $(BEP)$ when the parameters $\lambda_{n}$ and
$\beta_{n}$ satisfy additionally conditions
$\displaystyle\lim_{n\rightarrow+\infty}\lambda_{n}=0$,
$\displaystyle\lim_{n\rightarrow+\infty}\beta_{n}=+\infty$ and
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}\beta_{n}>0$. The main
advantage of our approach is that it provides convergence without any
restrictive assumption on the trajectories. The results can be seen as an
extension to the second order counterparts of the ones given in [19, 27]. To
our knowledge, such inertial proximal schemes have been studied only for the
first level equilibrium problem $(EP)$, see for instance [18, 23] and the
references therein. As applications, we discuss the hierarchical convex
minimization case and equilibrium problems under a saddle point constraint.
Numerical experiment is thereafter given to illustrate our theoretical
results. We end the paper by concluding comments.

##  1 Background and technical lemmata

In this section, we give some preliminary results and definitions that will be
used in the sequel. Throughout this paper, unless stated otherwise, let $K$ be
a nonempty closed and convex subset of a real Hilbert space $H$. We first
recall some well known concepts on monotonicity and continuity of real
bifunctions.

######  Definition 1.

A bifunction $f:K\times K\rightarrow\mathbb{R}$ is called:

  * $(i)$

monotone if $f(x,y)+f(y,x)\leq 0$ for all $x,y\in K$;

  * $(ii)$

$\gamma$-strongly monotone, if there exists $\gamma>0$ such that

$f(x,y)+f(y,x)\leq-\gamma\|x-y\|^{2}\;\text{for all}\;x,y\in K;$

  * $(iii)$

upper hemicontinuous, if

$\lim_{t\searrow 0}f(tz+(1-t)x,y)\leq f(x,y)\;\text{ for all}\;x,y,z\in K;$

  * $(iv)$

lower semicontinuous at $y$ with respect to the second argument on $K$, if

$f(x,y)\leq\displaystyle\liminf_{w\rightarrow y}f(x,w)\;\text{ for all}\;x\in
K;$

  * $(v)$

an equilibrium bifunction, if for each $x\in K$, $f(x,x)=0$ and $f(x,\cdot)$
is convex and lower semicontinuous.

The dual equilibrium problem associated with the bifunction $f$ on $K$ is
stated as follows: find $\bar{x}\in K$ such that

($DEP$) $f(y,\bar{x})\leq 0,\;\;\forall y\in K.$

The set of solutions to $(DEP)$ is called the Minty solution set. The
following result gives the link between Minty equilibria and the standard
ones.

######  Lemma 1 (Minty’s Lemma, [9]).

  * (i)

Whenever $f$ is monotone, every solution of $(EP)$ is a solution of $(DEP)$.

  * (ii)

Conversely, if $f$ is upper hemicontinuous and equilibrium bifunction, then
each solution of $(DEP)$ is a solution of $(EP)$.

The next lemma introduces the notion of resolvent associated to bifunctions.
This concept is crucial in our approach for solving $(BEP)$.

######  Lemma 2.

[17] Suppose that $f:K\times K\rightarrow\mathbb{R}$ is a monotone equilibrium
bifunction. Then the following are equivalent:

  * (i)

$f$ is maximal: $(x,u)\in K\times H$ and $f(x,y)\leq\langle
u,x-y\rangle,\;\forall y\in K$ imply that $f(x,y)+\langle u,x-y\rangle\geq
0\;\forall y\in K$;

  * (ii)

for each $x\in H$ and $\lambda>0$, there exists a unique
$z_{\lambda}=J^{f}_{\lambda}(x)\in K$, called the resolvent of $f$ at $x$,
such that

(5) $\lambda f(z_{\lambda},y)+\langle y-z_{\lambda},z_{\lambda}-x\rangle\geq
0,\;\;\forall y\in K.$

Moreover, $\bar{x}\in S_{f}$ if, and only if,
$\bar{x}=J^{f}_{\lambda}(\bar{x})$ for every $\lambda>0$ if, and only if,
$\bar{x}=J^{f}_{\lambda}(\bar{x})$ for some $\lambda>0$.

For the first main result of Section $3$ concerning the weak convergence of
the sequence generated by algorithm (4), we will make use of the two following
useful lemmata.

######  Lemma 3 (discrete Opial Lemma, [29]).

Let $C$ be a nonempty subset of $H$ and $(x_{k})_{k\geq 0}$ be a sequence in
$H$ such that the following two conditions hold:

  * (i)

For every $x\in C$, $\displaystyle\lim_{k\rightarrow+\infty}\|x_{k}-x\|$
exists.

  * (ii)

Every weak sequential cluster point of $(x_{k})_{k\geq 0}$ is in $C$.

Then, $(x_{k})_{k\geq 0}$ converges weakly to an element in $C$.

######  Lemma 4.

Let $0\leq p\leq 1$, and let $\\{b_{k}\\}$ and $\\{w_{k}\\}$ be two sequences
of nonnegative numbers such that, for all $k\geq 0$,

$b_{k+1}\leq pb_{k}+w_{k}.$

If $\sum_{k=0}^{+\infty}w_{k}<+\infty$, then
$\sum_{k=0}^{+\infty}b_{k}<+\infty$.

###### Proof.

We have

$(1-p)b_{k}\leq b_{k}-b_{k+1}+w_{k}.$

Summing up from $k=0$ to $n$, we get

$\displaystyle(1-p)\sum_{k=0}^{n}b_{k}$
$\displaystyle\leq\sum_{k=0}^{n}(b_{k}-b_{k+1})+\sum_{k=0}^{n}w_{k}$
$\displaystyle=b_{0}-b_{n+1}+\sum_{k=0}^{n}w_{k}$ $\displaystyle\leq
b_{0}+\sum_{k=0}^{n}w_{k}.$

And since $1-p\geq 0$ and $\sum_{k=0}^{+\infty}w_{k}<+\infty$, we conclude
that $\sum_{k=0}^{+\infty}b_{k}<+\infty$.

We also need the following technical lemmata.

######  Lemma 5.

[7] For all $x,y\in H$ and $\beta\in\mathbb{R},$ the following equality holds,

$\|\beta
x+(1-\beta)y\|^{2}=\beta\|x\|^{2}+(1-\beta)\|y\|^{2}-\beta(1-\beta)\|x-y\|^{2}.$

######  Lemma 6.

[19] Let $\\{a_{n}\\}$ be a sequence of real numbers that does not decrease at
infinity, in the sense that there exists a subsequence $\\{a_{n_{k}}\\}_{k\geq
0}$ of $\\{a_{n}\\}$ which satisfies

$a_{n_{k}}<a_{n_{k}+1}\quad\mbox{for all}\quad k\geq 0.$

Then, the sequence of integers $\\{\sigma(n)\\}_{n\geq n_{0}}$ defined by
$\sigma(n):=\max\\{k\leq n\;:\;a_{k}<a_{k+1}\\}$ is a nondecreasing sequence
verifying $\displaystyle\lim_{n\rightarrow+\infty}\sigma(n)=\infty$ and, for
all $n\geq n_{0}$

$a_{\sigma(n)}<a_{\sigma(n)+1}\quad\mbox{and}\quad a_{n}\leq a_{\sigma(n)+1}.$

In the rest of this section we recall some background material from convex
analysis. For a function $\varphi:H\rightarrow\mathbb{R}\cup{\\{+\infty\\}}$
we denote by $\mathop{\rm dom\,}\varphi=\\{x\in H:\varphi(x)<+\infty\\}$ its
effective domain and say that $\varphi$ is proper, if $\mathop{\rm
dom\,}\varphi\neq\emptyset$. We also denote by
$\min\varphi:=\displaystyle\inf_{x\in H}\varphi(x)$ the optimal objective
value of the function $\varphi$ and by $\mathop{\rm argmin\,}\varphi:=\\{x\in
H:\varphi(x)=\min\varphi\\}$ its set of global minima.

For a proper lower semicontinuous convex function
$\varphi:H\rightarrow\mathbb{R}\cup{\\{+\infty\\}}$ and $x\in H$, let
$\varphi^{*}:H\rightarrow\mathbb{R}\cup{\\{+\infty\\}}$ be its Fenchel
conjugate defined by $\varphi^{*}(x):=\displaystyle\sup_{y\in H}\\{\langle
x,y\rangle-\varphi(y)\\}$. If $\varphi=\delta_{K}$ is the indicator function
of $K\subset H$, i.e., $\delta_{K}(x)=0$ if $x\in K$ and $+\infty$ otherwise,
its Fenchel conjugate at $x^{*}\in H$ is the support function of $K$ at
$x^{*}$, i.e.,
$\delta_{K}^{*}(x^{*})=\sigma_{K}(x^{*})=\displaystyle\sup_{y\in K}\langle
x^{*},y\rangle.$ The subdifferential of $\varphi$ at $x\in H$, with
$\varphi(x)\in\mathbb{R}$ is the set $\partial\varphi(x):=\\{v\in
H:\varphi(y)\geq\varphi(x)+\langle v,y-x\rangle,\;\forall y\in H\\}$. We take
by convention $\partial\varphi(x):=\emptyset$ if $\varphi(x)=+\infty$.

The normal cone to $K\subset H$ at $x\in H$ is

$N_{K}(x)=\left\\{\begin{array}[]{ll}\\{x^{*}\in H:\langle
x^{*},u-x\rangle\leq 0,\;\forall u\in K\\}&\text{ if }x\in K\\\
\emptyset&\text{otherwise}.\end{array}\right.$

We mention that $N_{K}=\partial\delta_{K}$, and that $x^{*}\in N_{K}(x)$ if,
and only if, $\sigma_{K}(x^{*})=\langle x^{*},x\rangle$. For every $u\in K$,
we denote by $f_{u}$ the function defined on $H$ by $f_{u}(x)=f(u,x)$ if $x\in
K$ and $f_{u}(x)=+\infty$ otherwise. For an equilibrium bifunction $f:K\times
K\rightarrow\mathbb{R}$, the associate operator $A^{f}$ is defined by

$A^{f}(x):=\partial f_{x}(x)=\left\\{\begin{array}[]{ll}\\{z\in
H:f(x,y)+\langle z,x-y\rangle\geq 0,\;\forall y\in K\\}&\text{ if }x\in K\\\
\emptyset&\text{otherwise}.\end{array}\right.$

The Fitzpatrick transform $\mathcal{F}_{f}:K\times
H\rightarrow\mathbb{R}\cup\\{+\infty\\}$ associated to a bifunction $f$ and
introduced in [2, 12], is defined by

$\mathcal{F}_{f}(x,u)=\displaystyle\sup_{y\in K}\\{\langle
u,y\rangle+f(y,x)\\}.$

Given its continuity and convexity properties, the function $\mathcal{F}_{f}$
has proven to be an important tool when studying the asymptotic properties of
dynamical equilibrium systems, see [16] for a detailed presentation of these
elements. This section concludes with the following auxiliary result needed
for establishing our results.

######  Proposition 1.

[16] If $f(x,y)=\varphi(y)-\varphi(x)$ where
$\varphi:H\rightarrow\mathbb{R}\cup\\{+\infty\\}$ is convex and lower
semicontinuous with $\mathop{\rm dom\,}\varphi\subset K$, then for every
$(x,u)\in K\times H$, $\mathcal{F}_{f}(x,u)=\varphi(x)+\varphi^{*}(u).$

##  2 The main results

In the remaining part of the paper, $f$ and $g$ are two monotone and upper
hemicontinuous bifunctions. We suppose that for each $y\in K,\partial
g_{y}(y)\neq\emptyset$ (i.e., $\mathop{\rm dom\,}(A^{g})=K$) and that $K\cap
S_{f}\neq\emptyset$ and $\mathbb{R}_{+}(K-S_{f})$ is a closed linear subspace
of $H$. In this case, the operator $g_{x}+\delta_{S_{f}}$ is maximally
monotone, see [6, 30], and the subdifferential sum formula
$\partial(g_{x}+\delta_{S_{f}})=\partial g_{x}+N_{S_{f}}$ holds. The following
geometric assumption will be also needed and considered as a key tool in our
treatment of the convergence analysis: $\forall u\in S_{f},\;\text{for
all}\;p\in N_{S_{f}}(u)$,

(6)
$\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right]<+\infty.$

Let us mention that hypothesis (6) is the discrete counterpart of the
condition introduced in [16] in the context of continuous-time dynamical
equilibrium systems. Note also that it is a natural extension of similar
assumptions known in the literature for the convergence analysis of
variational inequalities expressed as monotone inclusion problems and for
constrained convex optimization problems, see [5, 10, 11] and references
therein for further useful comments on these assumptions.

###  2.1 Weak convergence analysis

In this paragraph, under natural conditions, we obtain weak convergence result
for the trajectory generated by (4) to a solution of $(BEP)$. We first prove
the following preliminary estimation.

######  Lemma 7.

Let $\\{x_{n}\\}$ be a sequence generated by algorithm (4). Take $u\in S$ and
set $a_{n}:=\|x_{n}-u\|^{2}$. Then, there exists $p\in N_{S_{f}}(u)$ such that
for each $n\geq 1$ the following inequality holds:

(7)
$\begin{array}[]{l}a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})+\lambda_{n}\beta_{n}f(u,x_{n+1})\\\
\leq(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}+\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right].\end{array}$

###### Proof.

Since $\\{x_{n}\\}$ is generated by algorithm (4), we have for each $x\in K$

(8)
$\begin{array}[]{l}0\leq\lambda_{n}\beta_{n}f(x_{n+1},x)+\lambda_{n}g(x_{n+1},x)\\\
\qquad+\dfrac{1}{2}\left(\|y_{n}-x\|^{2}-\|x_{n+1}-x\|^{2}-\|x_{n+1}-y_{n}\|^{2}\right).\end{array}$

By Lemma 5, we have for all $n\geq 1$

$\displaystyle\|y_{n}-x\|^{2}$
$\displaystyle=\|x_{n}+\alpha(x_{n}-x_{n-1})-x\|^{2}$
$\displaystyle=\|(1+\alpha)(x_{n}-x)-\alpha(x_{n-1}-x)\|^{2}$ (9)
$\displaystyle=(1+\alpha)\|x_{n}-x\|^{2}-\alpha\|x_{n-1}-x\|^{2}+\alpha(1+\alpha)\|x_{n}-x_{n-1}\|^{2}.$

Also, we have

(10)
$\begin{array}[]{lll}\|x_{n+1}-y_{n}\|^{2}&=&\|x_{n+1}-x_{n}-\alpha(x_{n}-x_{n-1})\|^{2}\\\
&=&\|x_{n+1}-x_{n}\|^{2}+\alpha^{2}\|x_{n}-x_{n-1}\|^{2}-2\alpha\langle
x_{n+1}-x_{n},x_{n}-x_{n-1}\rangle\\\
&\geq&(1-\alpha)\|x_{n+1}-x_{n}\|^{2}+(\alpha^{2}-\alpha)\|x_{n}-x_{n-1}\|^{2}.\end{array}$

Combining (2.1) and (10) with (8), we get for every $x\in K$

(11)
$\begin{array}[]{l}\|x_{n+1}-x\|^{2}-(1+\alpha)\|x_{n}-x\|^{2}+\alpha\|x_{n-1}-x\|^{2}\\\
\leq(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}+2\lambda_{n}\beta_{n}f(x_{n+1},x)+2\lambda_{n}g(x_{n+1},x).\end{array}$

Since $u\in S$, according to the first-order optimality condition, we have

$0\in\partial(g_{u}+\delta_{S_{f}})(u)=A^{g}(u)+N_{S_{f}}(u).$

Let $p\in N_{S_{f}}(u)$ be such that $-p\in A^{g}(u)$, we have for every
$n\geq 1$

(12) $\lambda_{n}g(u,x_{n+1})+\lambda_{n}\langle-p,u-x_{n+1}\rangle\geq 0,$

and by taking $x=u$ and $a_{n}=\|x_{n}-u\|^{2}$ in (11), we also have

(13) $\begin{array}[]{rcl}a_{n+1}-(1+\alpha)a_{n}+\alpha
a_{n-1}&\leq&(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}\\\
&&+2\lambda_{n}\beta_{n}f(x_{n+1},u)+2\lambda_{n}g(x_{n+1},u).\end{array}$

By summing up the above inequalities and using the monotonicity of $g$, we get

$\displaystyle a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})$
$\displaystyle\leq(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}$
$\displaystyle\quad+2\lambda_{n}\beta_{n}f(x_{n+1},u)+2\lambda_{n}\langle-p,u-x_{n+1}\rangle.$

Using the monotonicity of $f$, we obtain

$\begin{array}[]{l}a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})+\lambda_{n}\beta_{n}f(u,x_{n+1})\\\
\leq(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}+\lambda_{n}\beta_{n}f(x_{n+1},u)+2\lambda_{n}\langle-p,u-x_{n+1}\rangle\\\
=(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}\\\
\quad\quad+\lambda_{n}\beta_{n}\left[\left\langle\frac{2p}{\beta_{n}},x_{n+1}\right\rangle+f(x_{n+1},u)-\left\langle\frac{2p}{\beta_{n}},u\right\rangle\right].\end{array}$

Finally, using the fact that $p\in N_{S_{f}}(u)$, i.e.,
$\delta_{S_{f}}(u)+\sigma_{S_{f}}(p)=\langle p,u\rangle$, we obtain

$\begin{array}[]{lll}a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})+\lambda_{n}\beta_{n}f(u,x_{n+1})&&\\\
\leq(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}&&\\\
\qquad+\lambda_{n}\beta_{n}\left[\sup_{x\in
H}\left\\{\left\langle\frac{2p}{\beta_{n}},x\right\rangle+f(x,u)\right\\}-\sigma_{S_{f}}\left(\frac{2p}{\beta_{n}}\right)\right]&&\\\
=(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}\\\
\qquad+\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right].\end{array}$

The proof is complete.

######  Remark 1.

We can continue our analysis assuming that
$\displaystyle\sum_{n=1}^{+\infty}\|x_{n}-x_{n-1}\|^{2}<+\infty$; however this
condition involves the trajectory $\\{x_{n}\\}$ which is unknown. In the next
corollary we prove that the above condition holds under a suitable control of
the parameter $\alpha$.

######  Corollary 1.

Under hypothesis (6) and by assuming that $0\leq\alpha<\frac{1}{3}$, we have

  * (i)

$\displaystyle\sum_{n=1}^{+\infty}\|x_{n}-x_{n-1}\|^{2}<+\infty$;

  * (ii)

$\displaystyle\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}f(u,x_{n+1})<+\infty$,
for each $u\in S$.

###### Proof.

(i) First we simplify the writing of the estimation (7) given in Lemma 7.
Since $u\in S_{f}$ and $\lambda_{n}\beta_{n}\geq 0$, we have
$\lambda_{n}\beta_{n}f(u,x_{n+1})\geq 0$. Setting
$\delta_{n}=\|x_{n}-x_{n-1}\|^{2}$, then inequality (7) gives

(14)
$a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})+(1-\alpha)\delta_{n+1}-2\alpha\delta_{n}\leq\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right].$

In order to simplify its summation we rewrite (14) as

(15)
$\begin{array}[]{l}a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})+(1-\alpha)(\delta_{n+1}-\delta_{n})+(1-3\alpha)\delta_{n}\\\
\leq\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right].\end{array}$

Now, summing up (15) from $j=1$ to $n$, we obtain

$\begin{array}[]{l}(a_{n+1}-a_{1})-\alpha(a_{n}-a_{0})+(1-\alpha)(\delta_{n+1}-\delta_{1})+(1-3\alpha)\sum_{j=1}^{n}\delta_{j}\\\
\leq\sum_{j=1}^{n}\lambda_{j}\beta_{j}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{j}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{j}}\right)\right].\end{array}$

Assumption (6), infers that

(16) $(a_{n+1}-\alpha
a_{n})+(1-\alpha)\delta_{n+1}+(1-3\alpha)\sum_{j=1}^{n}\delta_{j}\leq C,$

for some nonnegative constant $C$.
Since $\alpha<\frac{1}{3}$ yields $1-3\alpha>0$ and $1-\alpha>0$, then
inequality (16) implies for all $n\geq 1$

(17) $a_{n+1}\leq\alpha a_{n}+C.$

Recursively we obtain for all $n\geq n_{0}\geq 1$

$\displaystyle a_{n+1}$
$\displaystyle\leq\alpha^{n-n_{0}}a_{n_{0}}+C(1+\alpha+\alpha^{2}+...+\alpha^{n-n_{0}-1})$
$\displaystyle=\alpha^{n-n_{0}}a_{n_{0}}+C\frac{1-\alpha^{n-n_{0}}}{1-\alpha}.$

Therefore the sequence $\\{x_{n}\\}$ is bounded and since

(18) $\sup_{n}\|x_{n+1}-x_{n}\|\leq 2\sup_{n}\|x_{n}\|<+\infty,$

the sequence $\\{\delta_{n}\\}$ is also bounded. Combining (18) with (16) and
noticing that $1-3\alpha>0,$ yields

$\sum_{j=1}^{+\infty}\delta_{j}<+\infty,$

ensuring $(i).$
Returning to inequality (7), we have

$\displaystyle
a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})+\lambda_{n}\beta_{n}f(u,x_{n+1})$
$\displaystyle\leq\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right]$
$\displaystyle\qquad+\underbrace{(\alpha-1)}_{\leq
0}\delta_{n+1}+2\alpha\delta_{n}.$
$\displaystyle\leq\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right]$
$\displaystyle\qquad+2\alpha\delta_{n}.\ $

By summing up from $n=1$ to $+\infty$, we obtain

$\displaystyle\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}f(u,x_{n+1})$
$\displaystyle\leq a_{1}-\alpha
a_{0}+\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right]$
$\displaystyle\qquad+2\alpha\sum_{n=1}^{+\infty}\|x_{n}-x_{n-1}\|^{2}.$

Then, assumptions (6) and $(i)$ ensure $(ii)$.

In order to further proceed with the convergence analysis, we have to choose
the sequences $\\{\lambda_{n}\\}$ and $\\{\beta_{n}\\}$ such that
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}>0$ and
$\beta_{n}\rightarrow+\infty$. We are now able to state and prove the first
main result of this section.

######  Theorem 1.

Suppose given monotone and upper hemicontinuous bifunctions $f$ and $g$. Let
$\\{x_{n}\\}$ be a sequence generated by algorithm (4). Under hypothesis (6)
and by assuming that

$0\leq\alpha<\frac{1}{3}$,
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}>0$ and
$\displaystyle\lim_{n\rightarrow+\infty}\beta_{n}=+\infty$,

the sequence $\\{x_{n}\\}$ weakly converges to $\bar{x}\in S$.

###### Proof.

The proof relies on the discrete Opial Lemma. To this end we will prove that
the conditions (i) and (ii) in Lemma 3 for $C=S$ are satisfied.
Returning to inequality (7), since $u\in S_{f}$ and $\lambda_{n}\beta_{n}\geq
0$, we have $\lambda_{n}\beta_{n}f(u,x_{n+1})\geq 0$, and then

$a_{n+1}-a_{n}\leq\alpha(a_{n}-a_{n-1})+2\alpha\|x_{n}-x_{n-1}\|^{2}+\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right].$

Taking the positive part, we immediately deduce that

$[a_{n+1}-a_{n}]_{+}\leq\alpha[a_{n}-a_{n-1}]_{+}+2\alpha\|x_{n}-x_{n-1}\|^{2}+\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right].$

Using assumption (6) together with the fact that
$\displaystyle\sum_{n=1}^{+\infty}\|x_{n}-x_{n-1}\|^{2}<+\infty$ and applying
Lemma 4 with

$b_{n}=[a_{n}-a_{n-1}]_{+}\;\text{and}\;w_{n}=2\alpha\|x_{n}-x_{n-1}\|^{2}+\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right],$

we obtain

$\sum_{n=1}^{+\infty}[a_{n}-a_{n-1}]_{+}<+\infty.$

Since $a_{n}$ is nonnegative, this implies the existence of
$\displaystyle\lim_{n\rightarrow+\infty}a_{n}$ and the one of
$\displaystyle\lim_{n\rightarrow+\infty}\|x_{n}-u\|$.

It remains to show that every weak cluster point $\bar{x}$ of the sequence
$\\{x_{n}\\}$ lies in $S$. Let $n_{k}\rightarrow+\infty$ as
$k\rightarrow+\infty$ such that $x_{n_{k}}\rightharpoonup\bar{x}$. We want to
show that $\bar{x}\in S$. Thanks to the monotonicity of $f$ and $g$,
inequality (4) ensures that for all $y\in K$ and for all $k$ large enough

(19)
$f(y,x_{{n_{k}}+1})\leq-\frac{1}{\beta_{n_{k}}}g(y,x_{{n_{k}}+1})+\frac{1}{\lambda_{n_{k}}\beta_{n_{k}}}\langle
x_{{n_{k}}+1}-y_{n_{k}},y-x_{{n_{k}}+1}\rangle.$

Since $\partial g_{y}(y)\neq\emptyset$, one can find $x^{*}(y)\in H$ such that
for every $z\in K$

$g(y,z)\geq\langle x^{*}(y),z-y\rangle\geq-\|x^{*}(y)\|\cdot\|y-z\|.$

Thus there exists $\gamma(y):=\|x^{*}(y)\|>0$ such that for every $z\in K$

(20) $-g(y,z)\leq\gamma(y).\|y-z\|.$

Returning to (19), we can write

$f(y,x_{n_{k}+1})\leq\dfrac{\gamma(y)}{\beta_{n_{k}}}\|y-x_{n_{k}+1}\|+\dfrac{1}{\lambda_{n_{k}}\beta_{n_{k}}}\|x_{n_{k}+1}-y_{n_{k}}\|.\|y-x_{n_{k}+1}\|.$

Passing to the limit, and using the facts that $\\{x_{n_{k}}\\}$ is bounded,
$\\{\beta_{n_{k}}\\}\rightarrow+\infty$,
$\displaystyle\liminf_{k\rightarrow+\infty}\lambda_{n_{k}}>0$ and
$\|x_{n_{k}+1}-y_{n_{k}}\|\rightarrow 0$, we deduce that $f(y,\bar{x})\leq 0$
for all $y\in K$. Lemma 1 leads to $\bar{x}\in S_{f}$.

By using (4) and the monotonicity of $f$ and $g$, we have for every $u\in
S_{f}$,

$\lambda_{n}\beta_{n}f(u,x_{n+1})+\lambda_{n}g(u,x_{n+1})\leq\langle
y_{n}-x_{n+1},x_{n+1}-u\rangle.$

By exploiting that $\displaystyle\lim_{n\rightarrow+\infty}\|x_{n}-u\|$ exists
and thanks to $(i)$ of Corollary 1, we deduce that

$\displaystyle\langle
y_{n}-x_{n+1},x_{n+1}-u\rangle\rightarrow_{n\rightarrow+\infty}0.$

Using $(ii)$ of the same Corollary, we obtain that
$\displaystyle\limsup_{n\rightarrow+\infty}\lambda_{n}g(u,x_{n+1})\leq 0$.
Since $g(u,.)$ is lower semicontinuous, from the assumption
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}>0$ we derive that
$g(u,\bar{x})\leq 0$. Lemma 1 allows us to conclude that

$g(\bar{x},u)\geq 0,\;\forall u\in S_{f},$

establishing the proof.

###  2.2 Strong convergence analysis

In this paragraph, under additional assumption on the monotonicity of the
bifunction of the upper level $g$, we ensure the strong convergence of the
trajectory in (4).

####  2.2.1 Strong convergence under assumption (6)

######  Theorem 2.

Suppose that the bifunctions $f$ and $g$ are monotone and upper
hemicontinuous. Under hypothesis (6), if the bifunction $g$ is $\rho$-strongly
monotone, and if

$0\leq\alpha<\frac{1}{3}\;\text{ and
}\;\sum_{n=1}^{\infty}\lambda_{n}=+\infty,$

the sequence $\\{x_{n}\\}$ generated by algorithm (4) strongly converges to a
unique solution $u\in S$.

###### Proof.

Uniqueness of the solution for $(BEP)$ follows from strong monotonicity of
$g$. For the existence, see [15, Theorem 4.3].
Using inequalities (12) and (11), with $x=u$, by summing up and using the
$\rho$-strong monotonicity of $g$, we get for $a_{n}:=\|x_{n}-u\|^{2}$

$\displaystyle a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})$
$\displaystyle\leq-2\rho\lambda_{n}a_{n+1}+(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}$
$\displaystyle\quad+2\lambda_{n}\beta_{n}f(x_{n+1},u)+2\lambda_{n}\langle-p,u-x_{n+1}\rangle.$

We follow the arguments in the proof of Lemma 7 to obtain

$\displaystyle a_{n+1}-a_{n}-\alpha(a_{n}-a_{n-1})+2\rho\lambda_{n}a_{n+1}$
$\displaystyle\leq(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}$
$\displaystyle\quad+\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right].$

Then, by summing up from $n=1$ to $+\infty$, we obtain

$\displaystyle 2\rho\sum_{n=1}^{+\infty}\lambda_{n}\|x_{n+1}-u\|^{2}$
$\displaystyle\leq a_{1}-\alpha
a_{0}+\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}\left[\mathcal{F}_{f}\left(u,\dfrac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\dfrac{2p}{\beta_{n}}\right)\right]$
$\displaystyle\quad+2\alpha\sum_{n=1}^{+\infty}\|x_{n}-x_{n-1}\|^{2}.$

Using condition (6) and assumption $(i)$ of Corollary 1, we deduce that

$\sum_{n=1}^{+\infty}\lambda_{n}\|x_{n+1}-u\|^{2}<+\infty.$

Since $\displaystyle\lim_{n\rightarrow+\infty}\|x_{n}-u\|$ exists and
$\sum_{n=1}^{\infty}\lambda_{n}=+\infty$, we conclude that
$\displaystyle\lim_{n\rightarrow+\infty}\|x_{n}-u\|=0$, which guarantees the
strong convergence of the whole sequence $\\{x_{n}\\}$ to $u$.

####  2.2.2 Strong convergence without assumption (6)

We will show that in this case, the algorithm strongly converges without the
need of the geometric hypothesis (6).

######  Theorem 3.

Suppose that the bifunctions $f$ and $g$ are monotone and upper hemicontinuous
with $S_{f}\neq\emptyset$ and $g$ is $\rho$-strongly monotone. Suppose
moreover that

$0\leq\alpha<\frac{1}{3}$,
$\displaystyle\lim_{n\rightarrow+\infty}\lambda_{n}=0$,
$\displaystyle\sum_{n=0}^{+\infty}\lambda_{n}=+\infty$,
$\displaystyle\lim_{n\rightarrow+\infty}\beta_{n}=+\infty$ and
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}\beta_{n}>0.$

Then, the sequence $\\{x_{n}\\}$ generated by algorithm (4) converges strongly
to the unique solution $u$ of $(BEP)$.

###### Proof.

Under assumptions on the two bifunctions $f$ and $g,$ we get the unique
solution denoted by $\bar{x}$ of the bilevel equilibrium problem $(BEP)$.

Step 1: We show that $\\{x_{n}\\}$ is bounded.
Since $\\{x_{n}\\}$ is generated by algorithm (4), then by (11), we have for
each $x\in K$

(21)
$\begin{array}[]{l}\|x_{n+1}-x\|^{2}-(1+\alpha)\|x_{n}-x\|^{2}+\alpha\|x_{n-1}-x\|^{2}\\\
\leq(\alpha-1)\|x_{n+1}-x_{n}\|^{2}+2\alpha\|x_{n}-x_{n-1}\|^{2}+2\lambda_{n}\beta_{n}f(x_{n+1},x)+2\lambda_{n}g(x_{n+1},x).\end{array}$

Fix $x\in S_{f}$, and set $a_{n}(x)=\|x_{n}-x\|^{2}$ and
$\delta_{n}=\|x_{n}-x_{n-1}\|^{2}.$ Thanks to the monotonicity of $f$, then
for each $n\geq 0$,

(22) $\begin{array}[]{l}a_{n+1}(x)-\alpha a_{n}(x)+2\alpha\delta_{n+1}\\\
\leq\left(a_{n}(x)-\alpha
a_{n-1}(x)+2\alpha\delta_{n}\right)+(3\alpha-1)\delta_{n+1}+2\lambda_{n}g(x_{n+1},x).\end{array}$

By setting $b_{n}(x)=a_{n}(x)-\alpha a_{n-1}(x)+2\alpha\delta_{n},$ we obtain,
for $n\geq 1,$

(23) $b_{n+1}(x)\leq
b_{n}(x)+(3\alpha-1)\delta_{n+1}+2\lambda_{n}g(x_{n+1},x).$

  * •

If there is $n_{0}\in\mathbb{N}$ such that $\\{b_{n}(x)\\}$ is decreasing for
all $n\geq n_{0},$ then $b_{n}(x)\leq b_{n_{0}}(x),$ which infers that

$a_{n+1}(x)\leq\alpha a_{n}(x)+b_{n_{0}}\quad\mbox{for all}\;\;n\geq n_{0}.$

Recursively, we obtain for all $n\geq n_{0}\geq 1$

$a_{n+1}(x)\leq\alpha^{n-n_{0}}a_{n_{0}}(x)+b_{n_{0}}\frac{1-\alpha^{n-n_{0}}}{1-\alpha},$

and the boundedness of the sequence $\\{a_{n}(x)\\}$.

  * •

Otherwise there exists an increasing sequence $\\{k_{n}\\}$ such that for
every $n\geq 0,$ $b_{k_{n+1}}(x)>b_{k_{n}}(x).$ By Lemma 6, there exist a
nondecreasing sequence $\\{\sigma_{n}\\}$ and $n_{0}>0$ such that
$\displaystyle\lim_{n\rightarrow+\infty}\sigma_{n}=\infty,$ and for all $n\geq
n_{0},$ $b_{\sigma_{n}(x)}<b_{\sigma_{n}+1}(x)$ and $b_{n}(x)\leq
b_{\sigma_{n}+1}(x).$ For $n=\sigma_{n}$ in (23), we get

(24)
$0<b_{\sigma_{n}+1}(x)-b_{\sigma_{n}}(x)\leq(3\alpha-1)\delta_{\sigma_{n}+1}+2\lambda_{\sigma_{n}}g(x_{\sigma_{n}+1},x).$

Using the $\rho$-strong monotonicity of $g$ and relation (20), we deduce that
for $n\geq n_{0}$

(25) $-2\lambda_{\sigma_{n}}\gamma(x)\sqrt{a_{\sigma_{n}+1}(x)}\leq
2\lambda_{\sigma_{n}}g(x,x_{\sigma_{n}+1})\leq(3\alpha-1)\delta_{\sigma_{n}+1}-2\lambda_{\sigma_{n}}\rho
a_{\sigma_{n}+1}(x).$

Since $3\alpha-1<0,$ we conclude that for $n\geq n_{0}$

(26)
$a_{\sigma_{n}+1}(x)\leq\left(\dfrac{\gamma(x)}{\rho}\right)^{2}\quad\mbox{and
}\quad\delta_{\sigma_{n}+1}\leq\dfrac{2\gamma^{2}(x)\lambda_{\sigma_{n}}}{\rho(1-3\alpha)}.$

Hence, $\\{a_{\sigma_{n}+1}(x)\\}$ is bounded and since,
$\\{\lambda_{\sigma_{n}}\\}$ is bounded, then $\\{\delta_{\sigma_{n}+1}\\}$ is
bounded, which means that $\\{b_{\sigma_{n}}(x)\\}$ also is bounded. So, for
all $n\geq n_{0},$ we have

$\begin{array}[]{lll}a_{n}(x)&\leq&\alpha a_{n-1}+b_{n}(x)\\\ &\leq&\alpha
a_{n-1}+b_{\sigma_{n}}(x)\\\ &\leq&\alpha a_{n-1}+C\\\
&\leq&\alpha^{n-n_{0}}a_{n_{0}}(x)+C\frac{1-\alpha^{n-n_{0}}}{1-\alpha}.\end{array}$

Therefore the sequence $\\{a_{n}(x)\\}$ is bounded, ensuring the boundedness
of $\\{x_{n}\\}.$

Step 2: We show that the sequence $\\{x_{n}\\}$ strongly converges to
$\bar{x}$, the unique solution of $(BEP).$
Let us consider two cases:
Case 1: There exists $n_{0}$ such that
$\\{b_{n}(\bar{x})\\}:=a_{n}(\bar{x})-\alpha
a_{n-1}(\bar{x})+2\alpha\delta_{n}$ is decreasing for $n\geq n_{0}$.
Then, the limit of sequence $\\{b_{n}(\bar{x})\\}$ exists and
$\displaystyle\lim_{n\rightarrow+\infty}(b_{n}(\bar{x})-b_{n+1}(\bar{x}))=0.$
Since $\bar{x}\in S_{f},$ then by (23) we have

(27) $b_{n+1}(\bar{x})\leq
b_{n}(\bar{x})+(3\alpha-1)\delta_{n+1}+2\lambda_{n}g(x_{n+1},\bar{x}).$

Hence, since $3\alpha-1<0,$
$\displaystyle\lim_{n\rightarrow+\infty}\lambda_{n}=0$ and $g(\cdot,\bar{x})$
is lower semi-continuous, then
$\displaystyle\lim_{n\rightarrow+\infty}\delta_{n+1}=0.$
Summing up inequality (27) from $1$ to $+\infty,$ we deduce that

(28) $\sum_{n=1}^{+\infty}-\lambda_{n}g(x_{n+1},\bar{x})\leq b_{1}(\bar{x}),$

which in combination with
$\displaystyle\sum_{n=0}^{+\infty}\lambda_{n}=+\infty$ leads to
$\displaystyle\liminf_{n\rightarrow\infty}-g(x_{n+1},\bar{x})\leq 0$.
On the other hand, since $g$ is $\rho$-strongly monotone, then we have

(29)
$\begin{array}[]{lll}\displaystyle\lim_{n\rightarrow+\infty}a_{n+1}(\bar{x})&=&\displaystyle\liminf_{n\rightarrow+\infty}\|x_{n+1}-\bar{x}\|^{2}\\\
&\leq&\frac{1}{\rho}\underbrace{\liminf_{n\rightarrow+\infty}-g(x_{n+1},\bar{x})}_{\leq
0}+\frac{1}{\rho}\displaystyle\limsup_{n\rightarrow+\infty}-g(\bar{x},x_{n+1})\\\
&\leq&-\frac{1}{\rho}\displaystyle\liminf_{n\rightarrow+\infty}g(\bar{x},x_{n+1}).\end{array}$

Hence, to prove that the sequence $\\{{a_{n+1}(\bar{x})}\\}$ converges to
zero, it is enough to verify that
$\displaystyle\liminf_{n\rightarrow+\infty}g(\bar{x},x_{n+1})\geq 0.$ Since
$\\{x_{n}\\}$ is bounded, let $x$ be a weak cluster point of $\\{x_{n}\\},$
i.e. $x=\displaystyle w-\lim_{n\in I_{n}\subset\mathbb{N}}x_{n}.$ By using the
weak lower semicontinuity of $g(\bar{x},\cdot)$ we have

$g(\bar{x},x)\leq\liminf_{n\in I}g(\bar{x},x_{n+1}).$

Since $\bar{x}$ is the unique solution of $(BEP)$, we need just to check that
$x\in S_{f}.$ In doing so, by (20) and (11), we have for every $y\in K,$

(30)
$f(y,x_{n+1})\leq-\frac{1}{\lambda_{n}\beta_{n}}\left(b_{n+1}(y)-b_{n}(y)\right)+\frac{1}{2\beta_{n}}\gamma(y)\sqrt{a_{n}(x)}.$

We have

$\begin{array}[]{l}b_{n}(y)-b_{n+1}(y)\\\ =\left(a_{n}(y)-\alpha
a_{n-1}(y)+2\alpha\delta_{n}\right)-\left(a_{n+1}(y)-\alpha
a_{n}(y)+2\alpha\delta_{n+1}\right)\\\
=\left(a_{n}(y)-a_{n+1}(y)\right)+\alpha\left(a_{n}(y)-a_{n-1}(y)\right)+2\alpha\left(\delta_{n}-\delta_{n+1}\right)\\\
=\left(a_{n}(\bar{x})-a_{n+1}(\bar{x})+2\langle
x_{n}-x_{n+1},\bar{x}-y\rangle\right)\\\
\quad+\alpha\left(a_{n-1}(\bar{x})-a_{n}(\bar{x})+2\langle
x_{n}-x_{n-1},\bar{x}-y\rangle\right)+2\alpha\left(\delta_{n}-\delta_{n+1}\right)\\\
=b_{n}(\bar{x})-b_{n+1}(\bar{x})+2\langle
x_{n}-x_{n+1},\bar{x}-y\rangle+2\alpha\langle
x_{n}-x_{n-1},\bar{x}-y\rangle.\end{array}$

Since
$\displaystyle\lim_{n\rightarrow+\infty}(b_{n}(\bar{x})-b_{n+1}(\bar{x}))=0$
and $\displaystyle\lim_{n\rightarrow+\infty}\|x_{n+1}-x_{n}\|=0,$ then
$\displaystyle\lim_{n\rightarrow+\infty}(b_{n}(y)-b_{n+1}(y))=0.$
By using the weak lower semicontinuity of $f(y,\cdot)$ and the fact that
$\\{x_{n}\\}$ is bounded,
$\displaystyle\lim_{n\rightarrow+\infty}\lambda_{n}=0,$
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}\beta_{n}>0$ and
$\displaystyle\lim_{n\rightarrow+\infty}\beta_{n}=+\infty,$ we conclude from
(30) that for every $y\in K$

$f(y,x)\leq\liminf_{n\in I}f(y,x_{n+1})\leq 0.$

Hence, by using Minty’s lemma we deduce that $x\in S_{f}.$
Therefore,

$0\leq g(\bar{x},x)\leq\liminf_{n\in I}g(\bar{x},x_{n+1}),$

and so $\displaystyle\lim_{n\rightarrow+\infty}a_{n}(\bar{x})=0.$
Case 2: There exists a subsequence $\\{x_{n_{j}}\\}$ of $\\{x_{n}\\}$ such
that $b_{n_{j}}(\bar{x})\leq b_{n_{j}+1}(\bar{x})$ for all $j\in\mathbb{N}.$
By Lemma 6, the sequence $\sigma(n):=\max\\{k\leq n\;:\;b_{k}<b_{k+1}\\}$ is a
nondecreasing, $\displaystyle\lim_{n\rightarrow+\infty}\sigma(n)=\infty$ and,
for all $n\geq n_{0}$

$b_{\sigma(n)}<b_{\sigma(n)+1}\quad\mbox{and}\quad b_{n}\leq b_{\sigma(n)+1}.$

Let us take $n=\sigma(n)$ and $x=\bar{x}$ in (23). We have

(31) $0<b_{\sigma(n)+1}(\bar{x})-b_{\sigma(n)}(\bar{x})\leq
2\lambda_{\sigma(n)}g(x_{\sigma(n)+1},\bar{x}),$

which yields $g(x_{\sigma(n)+1},\bar{x})\geq 0,$ and thus
$\displaystyle\limsup_{n\rightarrow+\infty}g(x_{\sigma(n)+1},\bar{x})\leq 0.$
Using again the $\rho$-strong monotonicity of $g$ and passing to the limit we
have

(32)
$\begin{array}[]{lll}\displaystyle\limsup_{n\rightarrow+\infty}a_{\sigma(n)+1}(\bar{x})&\leq&\frac{1}{\rho}\underbrace{\limsup_{n\rightarrow+\infty}-g(x_{\sigma(n)+1},\bar{x})}_{\leq
0}+\frac{1}{\rho}\displaystyle\limsup_{n\rightarrow+\infty}-g(\bar{x},x_{\sigma(n)+1})\\\
&\leq&-\frac{1}{\rho}\displaystyle\liminf_{n\rightarrow+\infty}g(\bar{x},x_{\sigma(n)+1}).\end{array}$

Under the boundedness of $\\{x_{n}\\},$ and similarly to the case 1, one can
show that

$\displaystyle\liminf_{n\rightarrow+\infty}g(\bar{x},x_{\sigma(n)+1})\geq 0.$

Hence, by (29), we conclude that
$\displaystyle\lim_{n\rightarrow+\infty}a_{\sigma(n)+1}(\bar{x})=0.$

Since $b_{n}(\bar{x})\leq b_{\sigma(n)+1}(\bar{x})$ for each $n\geq n_{0},$ we
derive that

$\begin{array}[]{lll}\displaystyle\lim_{n\rightarrow+\infty}a_{n}(\bar{x})\leq\displaystyle\lim_{n\rightarrow+\infty}b_{n}(\bar{x})&\leq&\displaystyle\lim_{n\rightarrow+\infty}b_{\sigma(n)+1}(\bar{x})\\\
&\leq&\displaystyle\lim_{n\rightarrow+\infty}\left(a_{\sigma(n)}(\bar{x})+2\alpha\delta_{\sigma(n)}\right)\\\
&\leq&(1+4\alpha)\displaystyle\lim_{n\rightarrow+\infty}a_{\sigma(n)}(\bar{x})+4\alpha\displaystyle\lim_{n\rightarrow+\infty}a_{\sigma(n)-1}(\bar{x})\\\
&=&0,\end{array}$

thus guaranteeing the strong convergence of the whole sequence $\\{x_{n}\\}$
to $\bar{x}.$

##  3 Application to optimization and saddle point problems

In this section, we give two examples of particular bifunctions, for which our
main weak and strong convergence theorems apply.

###  3.1 Hierarchical minimization

Our contribution in this paragraph discusses the following hierarchical
minimization problem:

($HMP$) $\min_{x\in\underset{K}{\hbox{argmin}}\,\psi}\;\varphi(x),$

where $\psi:H\rightarrow\mathbb{R}\cup\\{+\infty\\}$ is a proper, convex and
lower semicontinuous extend real-valued function such that $K=\mathop{\rm
dom\,}\psi$ is closed and $\varphi:H\rightarrow\mathbb{R}\cup\\{+\infty\\}$ is
a differentiable and lower semicontinuous function such that $K=\mathop{\rm
dom\,}\varphi$ is closed. The above problem can be equivalently expressed as:
find $\bar{x}\in\underset{K}{\hbox{argmin}}\,\psi$ such that

(33) $\varphi(\bar{x})\leq\varphi(y),\;\;\forall
y\in\underset{K}{\hbox{argmin}}\,\psi.$

Clearly, (33) can be viewed as a bilevel equilibrium problem $(BEP)$ such that
the associated bifunctions are defined for all $x,y\in K$ by
$f(x,y)=\psi(y)-\psi(x)$ and $g(x,y)=\varphi(y)-\varphi(x)$. In this case the
bifunctions $f$ and $g$ are obviously monotone and upper hemicontinuous. Hence
theorems on weak (resp. strong) convergence apply, whenever (6) (resp. (6) and
strong monotonicity) is satisfied.

\- Weak convergence: Without any loss of generality we assume
$\min_{K}\psi=0$.
Set $M=\underset{K}{\hbox{argmin}}\,\psi$, and consider
$\overline{\psi}(x)=\psi(x)$ if $x\in K$, and $\overline{\psi}(x)=+\infty$ if
$x\notin K$; then $\overline{\psi}(x)-\delta_{M}(x)\leq 0$ for all $x\in H$.
Using the reverse inequality for their Fenchel conjugates, we deduce
$\overline{\psi}^{*}(p)-\sigma_{M}(p)\geq 0$ for all $p\in H$, and in view of
Proposition 1, condition (6) becomes: $\forall u\in M,\;\text{for
all}\;p\in{N}_{M}(u),$

(34)
$\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}\left[\overline{\psi}^{*}\left(\frac{2p}{\beta_{n}}\right)-\sigma_{M}\left(\frac{2p}{\beta_{n}}\right)\right]<+\infty.$

Applying Theorem 1, and supposing that $M$ is nonempty,
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}>0$,
$\displaystyle\lim_{n\rightarrow+\infty}\beta_{n}=+\infty$ and
$0\leq\alpha<\frac{1}{3}$, then the whole sequence $\\{x_{n}\\}$ generated by
algorithm (4) weakly converges to a point $\bar{x}$ solution of $(HMP)$.
Consider the particular case where $\psi(x)=\dfrac{1}{2}d(x,M)^{2}$ and
$M\subset K$ is a nonempty closed convex set satisfying
$d(x,M)=\displaystyle\inf_{y\in M}\|x-y\|$. Then,
$\overline{\psi}^{*}(p)-\sigma_{M}(p)=\dfrac{1}{2}\|p\|^{2}$ for all $p\in H$.
Here, $M$ is the minimum set of $\psi$, and then condition (6) is equivalent
to $\displaystyle\sum_{n=1}^{+\infty}\dfrac{\lambda_{n}}{\beta_{n}}<+\infty$.

######  Remark 2.

We note that the condition (34) is simply the assumption originates from [5]
in the framework of solving a variational inequality of the forme

$Ax+N_{C}(x)\ni 0,$

where $A:H\rightrightarrows H$ is a maximally monotone operator and $C\subset
H$ is a closed convex set. For this problem, the authors in [5] obtained
solutions by means of the convergence analysis of the trajectories of the
following prox-penalization algorithm

$x_{n}=(I+\lambda_{n}(A+\beta_{n}\partial\psi))^{-1}x_{n-1},$

where $\\{\beta_{n}\\}$ and $\\{\lambda_{n}\\}$ are two sequences of
nonnegative reals and $\psi:H\rightarrow\mathbb{R}\cup\\{+\infty\\}$ acts as
an external penalization function with respect to the constraint $x\in C$.
Indeed, several ergodic and non ergodic convergence results have been
justified for $\\{x_{n}\\}$ under the key assumption: $\;\text{for all}\;p\in
R(N_{C})$,

$\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}\left[\psi^{*}\left(\frac{p}{\beta_{n}}\right)-\sigma_{C}\left(\frac{p}{\beta_{n}}\right)\right]<+\infty,$

where $R(N_{C})$ denotes the range of $N_{C}$.

\- Strong convergence: To deduce the strong convergence of the algorithm
$(IPA)$ to a solution of $(HMP)$, we’ll have to add a strong monotonicity
condition on the function $g$. However, when we set
$g(x,y)=\varphi(y)-\varphi(x)$, the strong monotonicity of $g$ is not assured,
so that we take $g(x,y)=\langle\nabla\varphi(x),y-x\rangle$, where
$\nabla\varphi$ is the gradient of $\varphi$ (we identify $\varphi$ with
$\overline{\varphi}(x)=\varphi(x)$ if $x\in K$, and
$\overline{\varphi}(x)=+\infty$ if $x\notin K$). In this case our inertial
proximal scheme associated to the problem (33) is the following:
$y_{n}:=x_{n}+\alpha(x_{n}-x_{n-1})$ and $x_{n+1}\in K$ such that

(35)
$\beta_{n}(\psi(y)-\psi(x_{n+1}))+\langle\nabla\varphi(x_{n+1}),y-x_{n+1}\rangle+\dfrac{1}{\lambda_{n}}\langle
x_{n+1}-y_{n},y-x_{n+1}\rangle\geq 0,\;\;\forall y\in K.$

Moreover, if we suppose $\varphi$ to be strongly convex on $K$, i.e., for some
$\kappa>0$ and for all $x,y\in K$ and all $t\in[0,1]$

$\varphi(tx+(1-t)y)\leq t\varphi(x)+(1-t)\varphi(y)-\kappa t(1-t)\|x-y\|^{2},$

we deduce that $g$ is strongly monotone, and thus the conclusion of Theorem 2
is valid whenever $\displaystyle\sum_{n=1}^{\infty}\lambda_{n}=+\infty$ and
$0\leq\alpha<\frac{1}{3}$.

###  3.2 Equilibrium problem under a saddle point constraint

Let $H_{1},H_{2}$ be two real Hilbert spaces, $U\subset H_{1}$ and $V\subset
H_{2}$ be nonempty closed convex sets, and let $L:U\times
V\rightarrow\mathbb{R}$ be closed and convex-concave, i.e., for each $(u,v)\in
U\times V$ the real functions $L(.,v)$ and $-L(u,.)$ are convex and lower
semicontinuous.

We consider the saddle-point problem: find $\;(\bar{u},\bar{v})\in U\times
V\;$ such that

($SP$) $L(\bar{u},v)\leq L(\bar{u},\bar{v})\leq L(u,\bar{v})\;\text{for
every}\;(u,v)\in U\times V,$

which is equivalent, see [22], to

$\displaystyle\max_{v\in V}\inf_{u\in U}L(u,v)=\min_{u\in U}\sup_{v\in
V}L(u,v)=L(\bar{u},\bar{v}).$

Setting $H=H_{1}\times H_{2}$, $K=U\times V$, we define the bifunction
$f:K\times K\rightarrow\mathbb{R}$ as:

$f((u_{1},v_{1}),(u_{2},v_{2})):=L(u_{2},v_{1})-L(u_{1},v_{2}),\text{ for each
}(u_{1},v_{1}),(u_{2},v_{2})\in K.$

Let us observe that problems $(SP)$ and $(EP)$ are equivalent and we denote
the solution set of $(SP)$ by $S_{L}$.

Using the definition of the Fitzpatrick transform $\mathcal{F}_{f}$, we have
for all $(u_{1},v_{1}),(u_{2},v_{2})\in K$:

$\displaystyle\mathcal{F}_{f}((u_{1},v_{1}),(u_{2},v_{2}))$
$\displaystyle=\sup_{(x,y)\in K}\\{\langle u_{2},x\rangle+\langle
v_{2},y\rangle+f((x,y),(u_{1},v_{1}))\\}$ $\displaystyle=\sup_{(x,y)\in
K}\\{\langle v_{2},y\rangle+L(u_{1},y)-L(x,v_{1})+\langle u_{2},x\rangle\\}$
$\displaystyle=\sup_{y\in V}\\{\langle
v_{2},y\rangle-(-L((u_{1},y))\\}+\sup_{x\in U}\\{\langle
u_{2},x\rangle-L(x,v_{1})\\}$
$\displaystyle=(-L(u_{1},.))^{*}(v_{2})+(L(.,v_{1}))^{*}(u_{2}).$

Therefore the condition (6) is satisfied when for all pairs $(u,v)\in S_{f}$
and $(p,q)\in N_{S_{f}}(u,v)$,

(36)
$\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}\left[(-L(u,.))^{*}\left(\frac{2q}{\beta_{n}}\right)+(L(.,v))^{*}\left(\frac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\frac{2p}{\beta_{n}},\frac{2q}{\beta_{n}}\right)\right]<+\infty.$

We consider two single-valued monotone operators $A$ and $B$ such that
$K\subset\mathop{\rm dom\,}A\times\mathop{\rm dom\,}B$ and $A\times
B+N_{S_{L}}$ is a maximally monotone operator (see [32, 33]). Furthermore we
suppose that the solution set $S_{VL}$ of $0\in A\bar{x}\times
B\bar{y}+N_{S_{L}}(\bar{x},\bar{y})$ is nonempty. By $A\times B$, we mean the
operator defined for $(u,v)\in H=H_{1}\times H_{2}$ by $(A\times
B)(u,v)=Au\times Bv$. When the monotone operator $A\times B+N_{S_{L}}$ is
maximally monotone, then

$(\bar{x},\bar{y})\in S_{VL}\quad\iff\quad(\bar{x},\bar{y})\in S_{L}\hbox{ and
}\langle A\bar{x},u-\bar{x}\rangle+\langle B\bar{y},v-\bar{y}\rangle\geq
0,\;\forall(u,v)\in S_{L}.$

For each $(u_{1},v_{1}),(u_{2},v_{2})\in K$, let us set

$g((u_{1},v_{1}),(u_{2},v_{2})):=\langle Au_{1},u_{2}-u_{1}\rangle+\langle
Bv_{1},v_{2}-v_{1}\rangle.$

Then, our inertial proximal algorithm $(IPA)$ used for approaching a solution
to the problem $(BEP)$ associated with the above bifunctions $f$ and $g$,
i.e., for finding a solution in $S_{VL}$, takes the following form: for every
$n\geq 1$, given current iterates $(x_{n-1}^{i},x_{n}^{i})\in K$, $i=1,2$, set
$y_{n}^{i}=x_{n}^{i}+\alpha(x_{n}^{i}-x_{n-1}^{i})$ and define
$(x_{n+1}^{1},x_{n+1}^{2})\in K$ in this way:

(37) $\left\\{\begin{array}[]{l}\text{ for all }(u,v)\in U\times V,\\\
\frac{1}{\lambda_{n}}\langle(x_{n+1}^{1},x_{n+1}^{2})-(y_{n}^{1},y_{n}^{2}),(u,v)-(x_{n+1}^{1},x_{n+1}^{2})\rangle+\langle
Ax_{n+1}^{1},u-x_{n+1}^{1}\rangle\\\ \hfill+\langle
Bx_{n+1}^{2},v-x_{n+1}^{2}\rangle+\beta_{n}(L(u,x_{n+1}^{2})-L(x_{n+1}^{1},v))\geq
0.\end{array}\right.$

In this case, Theorems 1 and 2 can be summarized as follows:

######  Corollary 2.

Let $\\{x_{n}^{1},x_{n}^{2}\\}$ be the sequence generated by (37). Under
hypothesis (36) and whenever $0\leq\alpha<\frac{1}{3}$,
$\displaystyle\liminf_{n\rightarrow+\infty}\lambda_{n}>0$ and
$\\{\beta_{n}\\}\rightarrow+\infty$, the weak convergence of
$\\{x_{n}^{1},x_{n}^{2}\\}$ to a solution of $S_{VL}$ is ensured. Also, the
strong convergence of $\\{x_{n}^{1},x_{n}^{2}\\}$ to the unique element of
$S_{VL}$ is ensured when $0\leq\alpha<\frac{1}{3}$,
$\displaystyle\sum_{n=1}^{\infty}\lambda_{n}=+\infty$ and $A\times B$ is
strongly monotone on $K$.

Next, let us give an example where the condition (36) is verified.

######  Example 1.

Take $K=[0,1]\times[0,1]$ and $L$ the closed convex-concave function defined
on $K$ by $L(u,v)=u^{2}(1+v)$. Then, the set of saddle points of $L$, which is
also the solution set $S_{f}$, is $S_{f}=\\{0\\}\times[0,1]$.
We also have

$\displaystyle(p,q)\in N_{(\\{0\\}\times[0,1])}(0,v)$
$\displaystyle\Leftrightarrow(p,q)(s,t-v)\leq
0,\;\;\forall\;(s,t)\in\\{0\\}\times[0,1]$ $\displaystyle\Leftrightarrow
q(t-v)\leq 0,\;\;\forall t\in[0,1];$

and then

$N_{S_{f}}(0,0)=\mathbb{R}\times\mathbb{R}_{-}$,
$N_{S_{f}}(0,1)=\mathbb{R}\times\mathbb{R}_{+}$ and
$N_{S_{f}}(0,v)=\mathbb{R}\times\\{0\\}$ for every $v\in]0,1[$.

To ensure (36), we check

$\begin{array}[]{rl}\displaystyle\sigma_{S_{f}}\left(\frac{2p}{\beta_{n}},\frac{2q}{\beta_{n}}\right)&=\displaystyle\sup_{v\in[0,1]}\left\\{v\frac{2q}{\beta_{n}}\right\\}=\left\\{\begin{array}[]{cl}\displaystyle\frac{2q}{\beta_{n}}&\text{
if }q>0\\\ 0&\text{ if }q\leq 0,\end{array}\right.\end{array}$

$\begin{array}[]{rl}(-L(0,.))^{*}\left(\frac{2q}{\beta_{n}}\right)&=\displaystyle\sup_{0\leq
s\leq
1}\left\\{\frac{2q}{\beta(t)}s\right\\}=\left\\{\begin{array}[]{cl}\displaystyle\frac{2q}{\beta_{n}}&\text{
if }q>0\\\ 0&\text{ if }q\leq 0,\end{array}\right.\end{array}$

and

$\begin{array}[]{rl}(L(.,v))^{*}\left(\frac{2p}{\beta_{n}}\right)&=\displaystyle\sup_{0\leq
s\leq
1}\left\\{\frac{2p}{\beta_{n}}s-(1+v)s^{2}\right\\}=\frac{p^{2}}{(1+v)\beta_{n}^{2}}.\end{array}$

Thus

$\begin{array}[]{l}\displaystyle\sum_{n=1}^{+\infty}\lambda_{n}\beta_{n}\left[(-L(u,.))^{*}\left(\frac{2q}{\beta_{n}}\right)+(L(.,v))^{*}\left(\frac{2p}{\beta_{n}}\right)-\sigma_{S_{f}}\left(\frac{2p}{\beta_{n}},\frac{2q}{\beta_{n}}\right)\right]\\\
=\frac{p^{2}}{(1+v)}{\displaystyle\sum_{n=1}^{+\infty}}\dfrac{\lambda_{n}}{\beta_{n}},\end{array}$

and then (36) is satisfied, whenever
$\displaystyle\sum_{n=1}^{+\infty}\frac{\lambda_{n}}{\beta_{n}}<+\infty$.

##  4 Numerical experiment

In this section, we present a numerical experiment to illustrate the
convergence of the proposed algorithm. Let us consider the constrained
minimization problem $(HMP)$, with

$K=\mathbb{R}^{2},\quad\varphi(x)=\frac{1}{4}(x_{1}-x_{2}-2)^{2}\quad\text{
and }\quad\psi(x)=\frac{1}{4}\left(x_{1}+x_{2}-4\right)^{2}.$

Since $\psi$ is convex, the minimum set of $\psi$ is
$S_{\psi}=\nabla\psi^{-1}(0,0)=\\{x=(x_{1},x_{2})\in\mathbb{R}^{2}:x_{2}=4-x_{1}\\}$
and the solution set of the hierarchical problem
$\displaystyle\min_{S_{\psi}}\varphi$ is $S=\\{\bar{x}\\}=\\{(3,1)\\}$.

We evaluate $\frac{1}{2}d(x,S_{\psi})^{2}$ where
$d(x,S_{\psi})=\displaystyle\inf_{y\in S_{\psi}}\|y-x\|_{2}$ and
$\|(x_{1},x_{2})\|_{2}:=\sqrt{x_{1}^{2}+x_{2}^{2}}$. For
$x=(x_{1},x_{2})\in\mathbb{R}^{2}$, we have

$d(x,S_{\psi})^{2}=\displaystyle\inf_{y_{1}\in\mathbb{R}}\left((y_{1}-x_{1})^{2}+(y_{1}+x_{2}-4)^{2}\right)=\displaystyle\inf_{y_{1}\in\mathbb{R}}\alpha(y_{1}).$

Since $\alpha(t)=(t-x_{1})^{2}+(t+x_{2}-4)^{2}$ is strongly convex and

$\alpha^{\prime}(\bar{y}_{1})=2(2\bar{y}_{1}+x_{2}-4-x_{1})=0\Leftrightarrow\bar{y}_{1}=\frac{1}{2}(x_{1}-x_{2}+4)$,

we get

$d(x,S_{\psi})^{2}=\alpha(\bar{y}_{1})=(\bar{y}_{1}-x_{1})^{2}+(\bar{y}_{1}+x_{2}-4)^{2}=2\psi(x),$

which yields $\psi(x)=\frac{1}{2}d(x,S_{\psi})^{2}$. Thus condition (6) is
equivalent to
$\displaystyle\sum_{n=1}^{+\infty}\dfrac{\lambda_{n}}{\beta_{n}}<+\infty.$

Note that the associated bifunctions are defined for all $x,y\in K$ by
$f(x,y)=\psi(y)-\psi(x)$ and $g(x,y)=\varphi(y)-\varphi(x)$, that $f$ and $g$
are monotone and that weak and strong convergences coincide in finite
dimension.

By using the proximal operator of $\varphi+\beta_{n}\psi,$ the drawing in
Figure 1 displays the asymptotic behavior of the trajectories
$x_{n}=(y_{n},z_{n})$ from the initial values $(y_{0},z_{0})=(0,0.5)$ and
$(y_{1},z_{1})=(0,0.5)$ with $\alpha=0.1,\lambda_{n}=\frac{1}{n}$ and
different values of $\beta_{n}.$ We also use the iterate error
$\|x_{n}-\bar{x}\|_{2}$ as a measure to describe the computational performance
of our algorithm. The numerical results in Figure 2 illustrate the rate of
convergence of $\|x_{n}-\bar{x}\|_{2}$ for different choices of $\beta_{n}$
and $\alpha=0.1,$ while Figure 3 displays the convergence rate of
$\|x_{n}-\bar{x}\|_{2}$ for different choices of $\alpha$ and
$\beta_{n}=(1+n).$

Figure 1: The asymptotic behavior of the trajectories $x_{n}=(y_{n},z_{n})$.
Figure 2: The rate of convergence of $\|x_{n}-\bar{x}\|_{2}$ for $\alpha=0.1$.
Figure 3: The convergence rate of $\|x_{n}-\bar{x}\|_{2}$ for
$\beta_{n}=(1+n).$

We note in Figure 2, that when $\beta_{n}$ increases then the rate of
convergence of $\|x_{n}-\bar{x}\|_{2}$ rapidly increases to $0,$ while in
Figure 3, the constant coefficient $\alpha$ acts inversely on the speed of
convergence of $\|x_{n}-\bar{x}\|_{2},$ (the convergence gets worst as the
values of $\alpha$ exceed $\frac{1}{3}$), which confirms the importance of
taking $\alpha<\frac{1}{3}$ in our theoretical results.

We note that all codes in this digital test are written in SCILAB-6.1.

##  5 Concluding Remark

In this paper, we presented an inertial proximal
method for solving bilevel monotone equilibrium problems in Hilbert spaces.
Our analysis shows the weak and the strong convergence of the trajectory
generated by the algorithm under natural assumptions. Our results can be seen
as an extension and improvement of some known results in the literature. In
particular, the geometric assumption (6) shows that, as conjectured in [27],
the restrictive assumption $\|x_{n+1}-x_{n}\|=o(\epsilon_{n})$ may be removed
via the introduction of a notion of conditioning for equilibrium bifunctions.
We illustrate this assumption with two concrete particular cases and conclude
this work by a numerical experiment, which shows that, with a suitable choice
of the parameters, the convergence conditions are satisfied and the proposed
iterative method succeeds in approximating a solution to bilevel equilibrium
problems.

Finally, we note that, to the best of our knowledge, our approach seems to be
the first introduced inertial proximal scheme for solving $(BEP)$ and then
several extensions of our main results may be analyzed. In particular, an
interesting direction of future research will be to obtain the above weak
convergence result without condition (6) and also to develop new splitting
inertial proximal algorithms for solving bilevel equilibrium problems.

## References

  * [1] M. Ait Mansour, Z. Mazgouri, and H. Riahi, A dynamical approach for the quantitative stability of parametric bilevel equilibrium problems and applications, Optimization, 71 (2022), pp. 1389–1408, https://doi.org/10.1080/02331934.2021.1981892.
  * [2] M. H. Alizadeh and N. Hadjisavvas, On the Fitzpatrick transform of a monotone bifunction, Optimization, 62 (2013), pp. 693–701, https://doi.org/10.1080/02331934.2011.653975.
  * [3] F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Var. Anal., 9 (2001), pp. 3–11, https://doi.org/10.1023/A:1011253113155.
  * [4] A. S. Antipin, Convergence and estimates for the rate of convergence of proximal methods to fixed points of extremal mappings, Zh. Vychisl. Mat. i Mat. Fiz., 35 (1995), pp. 688–704.
  * [5] H. Attouch, M. Czarnecki, and J. Peypouquet, Prox-penalization and splitting methods for constrained variational problems, SIAM J. Optim., 21 (2011), pp. 149–173, https://doi.org/10.1137/100789464.
  * [6] H. Attouch, H. Riahi, and M. Théra, Somme ponctuelle d’opérateurs maximaux monotones, Serdica Math. J., 22 (1996), pp. 267–292.
  * [7] H. H. Bauschke and P. L. Combettes, Convex analysis and monotone operator theory in Hilbert spaces, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, Springer, New York, 2011, https://doi.org/10.1007/978-1-4419-9467-7.
  * [8] G. C. Bento, J. X. Cruz Neto, J. O. Lopes, P. A. Soares, Jr., and A. Soubeyran, Generalized proximal distances for bilevel equilibrium problems, SIAM J. Optim., 26 (2016), pp. 810–830, https://doi.org/10.1137/140975589.
  * [9] E. Blum and W. Oettli, From optimization and variational inequalities to equilibrium problems, Math. Student, 63 (1994), pp. 123–145.
  * [10] R. I. Boţ and E. R. Csetnek, Forward-backward and Tseng’s type penalty schemes for monotone inclusion problems, Set-Valued Var. Anal., 22 (2014), pp. 313–331, https://doi.org/10.1007/s11228-014-0274-7.
  * [11] R. I. Boţ, E. R. Csetnek, and N. Nimana, An inertial proximal-gradient penalization scheme for constrained convex optimization problems, Vietnam J. Math., 46 (2018), pp. 53–71, https://doi.org/10.1007/s10013-017-0256-9.
  * [12] R. I. Boţ and S. Grad, Approaching the maximal monotonicity of bifunctions via representative functions, J. Convex Anal., 19 (2012), pp. 713–724.
  * [13] H. Brézis, L. Nirenberg, and G. Stampacchia, A remark on Ky Fan’s minimax principle, Boll. Un. Mat. Ital. (4), 6 (1972), pp. 293–300.
  * [14] R. Burachik and G. Kassay, On a generalized proximal point method for solving equilibrium problems in Banach spaces, Nonlinear Anal., 75 (2012), pp. 6456–6464, https://doi.org/10.1016/j.na.2012.07.020.
  * [15] O. Chadli, Z. Chbani, and H. Riahi, Equilibrium problems with generalized monotone bifunctions and applications to variational inequalities, J. Optim. Theory Appl., 105 (2000), pp. 299–323, https://doi.org/10.1023/A:1004657817758.
  * [16] Z. Chbani, Z. Mazgouri, and H. Riahi, From convergence of dynamical equilibrium systems to bilevel hierarchical Ky Fan minimax inequalities and applications, Minimax Theory Appl., 4 (2019), pp. 231–270.
  * [17] Z. Chbani and H. Riahi, Variational principles for monotone and maximal bifunctions, Serdica Math. J., 29 (2003), pp. 159–166, https://doi.org/10.4099/math1924.29.159.
  * [18] Z. Chbani and H. Riahi, Weak and strong convergence of an inertial proximal method for solving Ky Fan minimax inequalities, Optim. Lett., 7 (2013), pp. 185–206, https://doi.org/10.1007/s11590-011-0407-y.
  * [19] Z. Chbani and H. Riahi, Weak and strong convergence of prox-penalization and splitting algorithms for bilevel equilibrium problems, Numer. Algebra Control Optim., 3 (2013), pp. 353–366, https://doi.org/10.3934/naco.2013.3.353.
  * [20] J. Cotrina, M. Théra, and J. Zúñiga, An existence result for quasi-equilibrium problems via Ekeland’s variational principle, J. Optim. Theory Appl., 187 (2020), pp. 336–355, https://doi.org/10.1007/s10957-020-01764-0.
  * [21] S. Dempe, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), pp. 333–359, https://doi.org/10.1080/0233193031000149894.
  * [22] I. Ekeland and R. Temam, Convex analysis and variational problems, Studies in Mathematics and its Applications, Vol. 1, North-Holland Publishing Co., Amsterdam-Oxford; American Elsevier Publishing Co., Inc., New York, 1976\.  Translated from the French.
  * [23] D. V. Hieu and A. Gibali, Strong convergence of inertial algorithms for solving equilibrium problems, Optim. Lett., 14 (2020), pp. 1817–1843, https://doi.org/10.1007/s11590-019-01479-w.
  * [24] U. Mosco, Implicit variational problems and quasi variational inequalities, in Nonlinear operators and the calculus of variations (Summer School, Univ. Libre Bruxelles, Brussels, 1975), Lecture Notes in Math., Vol. 543, Springer, Berlin, 1976, pp. 83–156.
  * [25] A. Moudafi, Proximal point algorithm extended to equilibrium problems, J. Nat. Geom., 15 (1999), pp. 91–100.
  * [26] A. Moudafi, Second-order differential proximal methods for equilibrium problems, JIPAM. J. Inequal. Pure Appl. Math., 4 (2003), pp. Article 18, 7.
  * [27] A. Moudafi, Proximal methods for a class of bilevel monotone equilibrium problems, J. Global Optim., 47 (2010), pp. 287–292, https://doi.org/10.1007/s10898-009-9476-1.
  * [28] A. Moudafi and M. Théra, Proximal and dynamical approaches to equilibrium problems, in Ill-posed variational problems and regularization techniques (Trier, 1998), vol. 477 of Lecture Notes in Econom. and Math. Systems, Springer, Berlin, 1999, pp. 187–201, https://doi.org/10.1007/978-3-642-45780-7_12.
  * [29] Z. Opial, Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc., 73 (1967), pp. 591–597, https://doi.org/10.1090/S0002-9904-1967-11761-0.
  * [30] H. Riahi, On the maximality of the sum of two maximal monotone operators, Publ. Mat., 34 (1990), pp. 269–271, https://doi.org/10.5565/PUBLMAT_34290_05.
  * [31] H. Riahi, Z. Chbani, and M.-T. Loumi, Weak and strong convergences of the generalized penalty Forward-Forward and Forward-Backward splitting algorithms for solving bilevel hierarchical pseudomonotone equilibrium problems, Optimization, 67 (2018), pp. 1745–1767, https://doi.org/10.1080/02331934.2018.1490957.
  * [32] R. T. Rockafellar, On the maximal monotonicity of subdifferential mappings, Pacific J. Math., 33 (1970), pp. 209–216, http://projecteuclid.org/euclid.pjm/1102977253.
  * [33] R. T. Rockafellar, On the maximality of sums of nonlinear monotone operators, Trans. Amer. Math. Soc., 149 (1970), pp. 75–88, https://doi.org/10.2307/1995660.
  * [34] L. Q. Thuy and T. N. Hai, A projected subgradient algorithm for bilevel equilibrium problems and applications, J. Optim. Theory Appl., 175 (2017), pp. 411–431, https://doi.org/10.1007/s10957-017-1176-2.