# Tikhonov regularized exterior penalty dynamics for constrained variational
inequalities

Mathias Staudigl and Siqi Qu1 *This work was supported by the CSC and
benefited from the support of the FMJH Program Gaspard Monge for optimization
and operations research and their interactions with data science.1 University
of Mannheim, Department of Mathematics, B6<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Solving equilibrium problems under constraints is an important problem in
optimization and optimal control. In this context an important practical
challenge is the efficient incorporation of constraints. We develop a
continuous-time method for solving constrained variational inequalities based
on a new penalty regulated dynamical system in a general potentially infinite-
dimensional Hilbert space. In order to obtain strong convergence of the issued
trajectory of our method, we incorporate an explicit Tikhonov regularization
parameter in our method, leading to a class of time-varying monotone inclusion
problems featuring multiscale aspects. Besides strong convergence, we
illustrate the practical efficiency of our developed method in solving
constrained min-max problems.

##  I INTRODUCTION

Let $\mathcal{H}$ be a real Hilbert space, $\mathsf{A}:\mathcal{H}\to
2^{\mathcal{H}}$ a general maximally monotone operator,
$\mathsf{D}:\mathcal{H}\to\mathcal{H}$ a Lipschitz continuous and monotone
operator, and $\mathsf{C}\subseteq\mathcal{H}$ a closed convex set. Denote by
$\operatorname{\mathsf{N}}_{\mathsf{C}}(x)$ the outward normal cone to
$\mathsf{C}$. In this paper we are concerned with the study of a class of
splitting methods for solving constrained variational equalities (VIs) of the
form

$0\in\Phi(x)=\mathsf{A}(x)+\mathsf{D}(x)+\operatorname{\mathsf{N}}_{\mathsf{C}}(x).$
(P)

Problems of this form are ubiquitous in control and engineering. Important
examples include inverse problems [1], generalized Nash equilibrium problems
[2, 3, 4], domain decomposition for PDEs [5, 6], and many more. Motivated by
these applications, we present an operator splitting method designed to
approach a specific solution of (P) in a Hilbertian framework using a new
dynamical system featuring multiscale aspects. Our construction relies on the
assumption that the set constraint $\mathsf{C}$ can be represented as the zero
of another monotone operator $\mathsf{B}:\mathcal{H}\to\mathcal{H}$, so that
$\mathsf{C}=\\{x\in\mathcal{H}|\mathsf{B}(x)=0\\}$. While this setup might
appear restrictive, it is in fact an almost universal constellation in
equilibrium problems and convex optimization [7, 8, 9]. Motivated by solving
variational inequalities arising in game theory, we construct a dynamical
system that exhibits strong convergence properties under mere monotonicity
assumptions on the Lipschitzian operator $\mathsf{D}$. This technical
achievement allows us to approach large classes of generalized Nash
equilibrium problems, without strong monotonicity assumption, as are commonly
used in the perceived literature (see e.g. [4, 10, 11]). In particular, our
method allows us to apply the developed scheme directly to convex-concave
saddle-point problems, which regained a lot of importance in the data science
and machine learning community due to its important applications in
reinforcement learning [12], and generative adversarial networks [13].
However, our approach applies to many more important instances of constrained
VIs, which are of particular relevance in Generalized Nash equilibrium
problems (GNEP).

######  Example 1 (Generalized Nash equilibrium Problems)

The GNEP is a very important class of multi-agent optimization problems in
which non-cooperatively agents aim to minimize their private cost functions,
given the other agents’ decisions and eventually also joint coupling
constraints restricting the feasible set for each player. It has attracted
enormous attention within the systems and control community as a general
mathematical template to design distributed control strategies in complex
networked systems [14, 15, 16, 17]. Consider $N$ agents where the local
optimization problem of agent $i$ reads as
$\min_{x_{i}}J_{i}(x_{i},x_{-i})=\ell_{i}(x_{i},x_{-i})+r_{i}(x_{i})\quad\text{s.t.:
}(x_{i},x_{-i})\in\mathsf{C}.$ The constraint $x=(x_{i},x_{-i})\in\mathsf{C}$
represents a coupling constraint and for simplicity we assume this set of to
be described by linear restrictions in the control variables of the agents:
Denote by $\mathcal{H}=\prod_{i}\mathcal{H}_{i}$, we assume that the jointly
feasible set of the game is described as
$\mathsf{C}=\\{x\in\mathcal{H}|\sum_{i=1}^{N}T_{i}x_{i}=b\\}$. Here
$T_{i}:\mathcal{H}_{i}\to\mathcal{G}$ are bounded linear operators between two
real Hilbert spaces $\mathcal{H}_{i}$ and $\mathcal{G}$, and $b\in\mathcal{G}$
is given. Assuming that the cost functions $\ell_{i}(\cdot,x_{-i})$ and
$r_{i}(\cdot)$ are convex in the own control variable, we arrive at jointly
convex GNEP for which we can use variational inequality methods to compute
Nash equilibrium points. In this paper we follow penalty techniques to enforce
the joint feasibility restrictions $x\in\mathsf{C}$ [18, 19]. Consider the
function $g(x)=\frac{1}{2}\norm{\sum_{i=1}^{N}T_{i}x_{i}-b}^{2}$ and
$\mathsf{B}(x)=\nabla g(x)$. Then, it is clear that
$\mathsf{C}=\operatorname{zer}(\mathsf{B})=\operatorname*{argmin}_{x\in\mathcal{H}}g(x)$.
Assuming additionally that the functions $\ell_{i}(\cdot,x_{-i})$ are
continuously differentiable for all $x_{-i}$, we can define the operator
$\mathsf{D}(x):=[\nabla_{x_{1}}\ell_{1}(x);\ldots;\nabla_{x_{N}}\ell_{N}(x)]$,
as well as the set-valued operator $\mathsf{A}(x)=\partial
r_{1}(x_{1})\times\cdots\times\partial r_{N}(x_{N})$. Finding a Nash
equilibrium of the game can in this setting by casted as the search for a
solution to the variational inequality (P) with the data just defined.
$\Diamond$

To deal with the constraints present in the general formulation (P), we study
the trajectories defined by the continuous-time dynamical system with
components $(p,x)$, defined as

$\left\\{\begin{split}p(t)&=\operatorname{\mathsf{J}}_{\lambda(t)A}(x(t)-\lambda(t)V(t,x(t)),\\\
\dot{x}(t)&=p(t)-x(t)+\lambda(t)[V(t,x(t))-V(t,p(t))]\end{split}\right.$ (1)

where $V(t,x):=\mathsf{D}(x)+\varepsilon(t)x+\beta(t)\mathsf{B}(x)$ and
$\lambda(t)>0$ acts as a step-size parameter. This dynamical system is a
continuous-time version of Tseng’s modified extragradient method [20, 16]. The
vector field defining this dynamics carries two parameters in its description.
The addendum $\varepsilon(t)x$ acts as a Tikhonov regularization on the
trajectories, which will allow us to prove strong convergence (i.e.
convergence in norm) to the least norm solution of the original problem (P).
The second addendum $\beta(t)\mathsf{B}(x)$ acts as an exterior penalty to the
method which forces the trajectory to move towards the set
$\operatorname{zer}(\mathsf{B})=\mathsf{C}$ over time. The main result
(Theorem 10) of this note establishes the strong convergence of the trajectory
$x(t)$ to the least norm solution of the underlying constrained VI (P)
whenever the Tikhonov parameter $\varepsilon(t)$ vanishes and the penalty
parameter $\beta(t)$ grows to infinity, subject to some verifiable conditions.

###  I-A Related Literature

Continuous time methods for variational inequalities have received a lot of
attention in the last decades due to their close link to iterative methods via
time-discretization methods, and the availability of Lyapunov analysis to
assess their asymptotic properties. The dynamical system (1) is an example of
a modified extragradient method, which received a lot of attention recently
within the machine learning community. For our developments, an important
feature of this dynamical system is the presence of multi-scale aspects,
embodied by the functions $\varepsilon(t)$ (Tikhonov) and $\beta(t)$
(Penalty). The impact of such dynamical features in a continuous-time system
are well-documented within optimization [21, 22, 23, 24]. At the same time,
Tikhonov regularization is a classical tool in variational analysis, that has
been studied in connection with variational inequalities in many papers (see
e.g. [25, 26]). The contribution we are making here is to explicitly study the
interplay of both effects simultaneously. We give verifiable conditions that
guarantee asymptotic convergence the least norm solution of the original
problem using our exterior penalty approach. While a seemingly natural
approach, we could not identify a similar analysis in the literature, and
therefore belief that this constitutes a new results. Besides theoretical
convergence statements, we report on the empirical performance of the method
in solving convex-concave saddle point problems.

##  II PRELIMINARIES

###  II-A Notation

Let $\mathcal{H}$ be a real Hilbert space with inner product
$\langle\cdot,\cdot\rangle$ and associated norm $\norm{\cdot}$. The norm ball
with center $x$ and radius $\varepsilon$ is denoted by
$\mathbb{B}(x,\varepsilon)$. The symbols $\rightharpoonup$ and $\to$ denote
weak and strong convergence, respectively. For a closed convex set
$\mathsf{C}\subset\mathcal{H}$ we define the normal cone as
$\operatorname{\mathsf{N}}_{\mathsf{C}}(x)=\\{u\in\mathcal{H}|\langle
y-x,u\rangle\leq 0\\}$ if $x\in\mathsf{C}$, and
$\operatorname{\mathsf{N}}_{\mathsf{C}}(x)=\varnothing$ else. For a set-valued
operator ${\mathsf{M}}:\mathcal{H}\to 2^{\mathcal{H}}$ we denote by
$\operatorname{graph}({\mathsf{M}})=\\{(x,u)\in\mathcal{H}\times\mathcal{H}|u\in{\mathsf{M}}(x)\\}$
its graph,
$\operatorname{dom}({\mathsf{M}})=\\{x\in\mathcal{H}|{\mathsf{M}}(x)\neq\varnothing\\}$
its domain, and by ${\mathsf{M}}^{-1}:\mathcal{H}\to 2^{\mathcal{H}}$ its
inverse, defined by
$(u,x)\in\operatorname{graph}({\mathsf{M}}^{-1})\Leftrightarrow(x,u)\in\operatorname{graph}({\mathsf{M}}).$
We let
$\operatorname{zer}({\mathsf{M}})=\\{x\in\mathcal{H}|0\in{\mathsf{M}}(x)\\}$
denote the set of zeros of ${\mathsf{M}}$. An operator ${\mathsf{M}}$ is
$c$-strongly monotone if $c\geq 0$ and $\langle x-y,u-v\rangle\geq
c\norm{x-y}^{2}$ for all $(x,u),(y,v)\in\operatorname{graph}({\mathsf{M}})$.
In case $c=0$ holds, the operator ${\mathsf{M}}$ is said to be monotone. A
monotone operator ${\mathsf{M}}$ is maximally monotone if there exists no
proper monotone extension of the graph of ${\mathsf{M}}$ on
$\mathcal{H}\times\mathcal{H}$.

###### Fact 1

[27, Proposition 23.39] If ${\mathsf{M}}$ is maximally monotone, then
$\operatorname{zer}({\mathsf{M}})$ is a convex and closed set.

###### Fact 2

If ${\mathsf{M}}$ is maximally monotone, then
$p\in\operatorname{zer}({\mathsf{M}})\Leftrightarrow\langle u-p,w\rangle\geq
0\quad\forall(u,w)\in\operatorname{graph}({\mathsf{M}}).$

The resolvent of ${\mathsf{M}}$,
$\operatorname{\mathsf{J}}_{{\mathsf{M}}}:\mathcal{H}\to 2^{\mathcal{H}}$ is
defined by
$\operatorname{\mathsf{J}}_{{\mathsf{M}}}=(\operatorname{Id}+{\mathsf{M}})^{-1}$.
If ${\mathsf{M}}$ is maximally monotone, then
$\operatorname{\mathsf{J}}_{{\mathsf{M}}}$ is single-valued and maximally
monotone.

###  II-B Properties of perturbed solutions

As already mentioned in the Introduction, our approach combines Tikhonov
regularization and penalization. Therefore, we first have to understand the
properties of sequences of solutions of the intermediate auxiliary problems.
Specifically, let $(\varepsilon,\beta)\in(0,\infty)\times(0,\infty)$ be a
given pair of parameters. The trajectory of the dynamical system (1) is going
to track solutions of the auxiliary problem

$0\in\Phi_{\varepsilon,\beta}(x)=(\mathsf{A}+\mathsf{D}+\varepsilon\operatorname{Id}+\beta\mathsf{B})(x)$
(2)

This VI involves the parametric family of mappings
$V_{\varepsilon,\beta}(x):=\mathsf{D}(x)+\varepsilon x+\beta\mathsf{B}(x)$ for
all $x\in\mathcal{H}$.

###### Assumption 1

$\mathsf{A}:\mathcal{H}\to 2^{\mathcal{H}}$ is maximally monotone.
$\mathsf{D}:\mathcal{H}\to\mathcal{H}$ is maximally monotone and
$\frac{1}{\eta}$-Lipschitz continuous. $\mathsf{B}:\mathcal{H}\to\mathcal{H}$
is maximally monotone, satisfies $\operatorname{zer}(\mathsf{B})=\mathsf{C}$
and is $\frac{1}{\mu}$-Lipschitz. $\Diamond$

Our first lemma collects basic regularity properties of this family of
mappings. We skip the easy proof because of space limitations.

###### Lemma 3

For all $\varepsilon,\beta>0$, we have

  * (i)

$V_{\varepsilon,\beta}$ is Lipschitz continuous with modulus
$L_{\varepsilon,\beta}\triangleq\frac{1}{\eta}+\varepsilon+\frac{\beta}{\mu}$;

  * (ii)

If either $\operatorname{dom}(\mathsf{D})=\mathcal{H}$ or
$\operatorname{dom}(\mathsf{D})\cap\operatorname{int}\operatorname{dom}(\mathsf{B})\neq\varnothing$,
then $V_{\varepsilon,\beta}$ is maximally monotone and even strongly monotone.

We see that the family of auxiliary problems (2) becomes a sequence of
strongly monotone inclusion problems. Therefore, for each parameter pair
$(\varepsilon,\beta)\in(0,\infty)\times[0,\infty)$, the set
$\operatorname{zer}(\Phi_{\varepsilon,\beta})$ reduces to a singleton
$\\{\bar{x}(\varepsilon,\beta)\\}$. The next proposition establishes some
consistency and regularity properties of this parametric family of solutions.

###### Proposition 4

Let $(\varepsilon_{n})_{n\in\mathbb{N}},(\beta_{n})_{n\in\mathbb{N}}$ be
sequences in $(0,\infty)$ such that $\varepsilon_{n}\to
0,\beta_{n}\to+\infty$. Then $\bar{x}(\varepsilon_{n},\beta_{n})\to
z\in\operatorname{zer}(\Phi)$ satisfying
$\norm{z}=\inf\\{\norm{x}:x\in\operatorname{zer}(\Phi)\\}$.

We next prove that $(\varepsilon,\beta)\mapsto\bar{x}(\varepsilon,\beta)$ is a
locally Lipschitz continuous function.

###### Proposition 5

The solution mapping $(\varepsilon,\beta)\mapsto\bar{x}(\varepsilon,\beta)$ is
locally Lipschitz continuous. In particular, for all
$t_{1}=(\varepsilon_{1},\beta_{1})$ and $t_{2}=(\varepsilon_{2},\beta_{2})$,
we have

$\norm{\bar{x}(t_{2})-\bar{x}(t_{1})}\leq\frac{\ell}{\varepsilon_{1}}\left(\absolutevalue{\beta_{2}-\beta_{1}}+\absolutevalue{\varepsilon_{2}-\varepsilon_{1}}\right),$
(3)

where
$\ell\triangleq\max\\{\sup_{x\in\mathbb{B}(0,\mathtt{a})}\norm{\mathsf{B}(x)},\mathtt{a}\\}$,
and $\mathtt{a}\triangleq\inf\\{\norm{x}:x\in\operatorname{zer}(\Phi)\\}$.

##  III Penalty regulated dynamical systems

As solutions of the proposed dynamical system (1) we consider absolutely
continuous functions [28]. Recall that a function $f:[0,b]\to\mathcal{H}$
(where $b>0$) is said to be absolutely continuous if there exists an
integrable function $g:[0,b]\to\mathcal{H}$ such that

$f(t)=f(0)+\int_{0}^{t}g(s)\operatorname{d\\!}s\quad\forall t\in[0,b].$

Given functions $\varepsilon,\beta,\lambda:(0,\infty)\to(0,\infty)$, we set
$V(t,x)\equiv V_{\varepsilon(t),\beta(t)}(x)$, and introduce the reflection
$R_{t}(x)\triangleq x-\lambda(t)V(t,x)$. Furthermore, define the vector field
$f(t,x):[0,\infty)\times\mathcal{H}\to\mathcal{H}$ by

$f(t,x)\triangleq\left(R_{t}\circ\operatorname{\mathsf{J}}_{\lambda(t)A}\circ
R_{t}\right)(x)-R_{t}x$ (4)

The first-order dynamical system (1) reads then compactly as

$\dot{x}(t)=f(t,x(t)),x(0)=x^{0}\in\mathcal{H}\text{ given. }$ (5)

We say that $x:[0,\infty)\to\mathcal{H}$ is a strong solution of (5) if
$t\mapsto x(t)$ is absolutely continuous on each interval $[0,b],0<b<\infty$
and $\frac{\operatorname{d\\!}}{\operatorname{d\\!}t}x(t)=f(t,x(t))$ for
almost every $t\in[0,+\infty)$.

###  III-A Existence of solutions

To prove existence and uniqueness of strong global solutions to (5), we use
the Cauchy-Lipschitz theorem for absolutely continuous trajectories [28].

###### Assumption 2

The functions $\lambda,\varepsilon,\beta:[0,\infty)\to(0,\infty)$ are
continuous on each interval $[0,b],0<b<\infty$. Additionally,
$\varepsilon(\cdot),\beta(\cdot)$ are continuously differentiable. The mapping
$t\mapsto\varepsilon(t)$ is monotonically decreasing and $t\mapsto\beta(t)$ is
monotonically increasing.

The following Lemma establishes Lipschitz continuity of the vector field
$f(t,x)$. The proof is similar to [26, Lemma 5.1], and thus omitted due to
space restrictions.

###### Lemma 6

Assume that $\lambda(t)\varepsilon(t)<\frac{1}{\eta}+\frac{\beta(t)}{\mu}$ for
all $t\geq 0$. For all $x,y\in\mathcal{H}$ and $t\geq 0$, we then have

$\norm{f(t,x)-f(t,y)}\leq\kappa(t)\norm{x-y}$

where
$\kappa(t)\equiv\sqrt{(1+2\lambda(t)L(t))\left(1+\lambda^{2}(t)L^{2}(t)-2\lambda(t)\varepsilon(t)\right)}$
and $L(t)\equiv
L_{\varepsilon(t),\beta(t)}=\frac{1}{\eta}+\varepsilon(t)+\frac{\beta(t)}{\mu}$.

Next, we establish a growth bound on the vector field. To that end, we define
parameterized maps $R_{\lambda,\varepsilon,\beta}(x)\triangleq x-\lambda
V_{\varepsilon,\beta}(x)$ and
$F_{\lambda,\varepsilon,\beta}(x)\triangleq\left(R_{\lambda,\varepsilon,\beta}\circ\operatorname{\mathsf{J}}_{\lambda
A}\circ
R_{\lambda,\varepsilon,\beta}\right)(x)-R_{\lambda,\varepsilon,\beta}x$.
Obviously, we have $f(t,x)\equiv F_{\lambda(t),\varepsilon(t),\beta(t)}(x)$
and $R_{t}(x)\equiv R_{\lambda(t),\varepsilon(t),\beta(t)}(x)$. Because of
space limitations we omit the fairly simple proof of the next result.

###### Lemma 7

For all $(\lambda,\varepsilon,\beta)\in\mathbb{R}^{3}_{+}$ satisfying
$\lambda<\frac{1}{1/\eta+\varepsilon+\beta/\mu}$, and $x\in\mathcal{H}$, there
exists a universal constant $C>0$ such that
$\norm{F_{\lambda,\varepsilon,\beta}(x)}\leq C(1+\norm{x}).$

Existence and uniqueness of solutions to the dynamical system (5) is now a
straightforward consequence of the Picard-Lindelöf Theorem.

###  III-B Convergence of trajectories

In order to show the convergence, we start with some technical lemmata. To
simplify the notation, we denote by
$\bar{x}(t)=\bar{x}(\varepsilon(t),\beta(t))$ the path of unique elements of
$\operatorname{zer}(\Phi_{t})$ where
$\Phi_{t}\equiv\Phi_{\varepsilon(t),\beta(t)}$.

###### Lemma 8

For almost all $t\in[0,+\infty)$, we have

$\displaystyle\norm{x(t)-p(t)}^{2}$
$\displaystyle-\norm{x(t)-\bar{x}(t)}^{2}\leq(1+2\lambda(t)\varepsilon(t))\|p(t)-\bar{x}(t)\|^{2}$
$\displaystyle+2\lambda(t)\langle V(t,p(t))-V(t,x(t)),p(t)-\bar{x}(t)\rangle$

###### Proof:

From (1), we have $(\operatorname{Id}+\lambda(t)A)p(t)\ni
x(t)-\lambda(t)V(t,x(t)).$ It follows,

$\displaystyle\Phi_{t}(p(t))$ $\displaystyle=A(p(t))+V(t,p(t))$
$\displaystyle\ni\frac{x(t)-p(t)}{\lambda(t)}-V(t,x(t))+V(t,p(t))=-\frac{\dot{x}(t)}{\lambda(t)}.$

By Assumption 1, the operators $\mathsf{D}$ and $\mathsf{B}$ are maximally
monotone, which implies that $\Phi_{t}$ is $\varepsilon(t)$-strongly monotone.
Consequently,

$\langle-\frac{\dot{x}(t)}{\lambda(t)}-0,p(t)-\bar{x}(t)\rangle\geq\varepsilon(t)\|p(t)-\bar{x}(t)\|^{2}.$
(6)

Using this property, we see

$\displaystyle 2\lambda(t)\varepsilon(t)\norm{p(t)-\bar{x}(t)}^{2}$
$\displaystyle\leq 2\langle x(t)-p(t),p(t)-\bar{x}(t)\rangle$
$\displaystyle~{}~{}~{}+2\lambda(t)\langle
V(t,p(t))-V(t,x(t)),p(t)-\bar{x}(t)\rangle$
$\displaystyle=-\|x(t)-p(t)\|^{2}+\|x(t)-\bar{x}(t)\|^{2}-\|p(t)-\bar{x}(t)\|^{2}$
$\displaystyle~{}~{}~{}+2\lambda(t)\langle
V(t,p(t))-V(t,x(t)),p(t)-\bar{x}(t)\rangle.$

∎

###### Lemma 9

Let $t\mapsto x(t)$ be the unique strong global solution of (1) for almost all
$t\in[0,+\infty)$. Then

$\displaystyle\langle x(t)-\bar{x}(t),\dot{x}(t)\rangle\leq$
$\displaystyle(\lambda(t)L(t)-1)\|x(t)-p(t)\|^{2}$
$\displaystyle-\lambda(t)\varepsilon(t)\|p(t)-\bar{x}(t)\|^{2}$

###### Proof:

For almost all $t\in[0,+\infty)$, we have

$\displaystyle 2\langle x(t)-\bar{x}(t),\dot{x}(t)\rangle$
$\displaystyle=2\langle x(t)-\bar{x}(t),p(t)-x(t)\rangle$
$\displaystyle~{}~{}~{}+2\langle
x(t)-\bar{x}(t),\lambda(t)[V(t,x(t))-V(t,p(t))]\rangle$
$\displaystyle=\|\bar{x}(t)-p(t)\|^{2}-\|\bar{x}(t)-x(t)\|^{2}-\|x(t)-p(t)\|^{2}$
$\displaystyle~{}~{}~{}+2\lambda(t)\langle
x(t)-\bar{x}(t),V(t,x(t))-V(t,p(t))\rangle$

combining with Lemma 8, we get
$\|\bar{x}(t)-p(t)\|^{2}-\|\bar{x}(t)-x(t)\|^{2}\leq-\|x(t)-p(t)\|^{2}-2\lambda(t)\varepsilon(t)\|p(t)-\bar{x}(t)\|^{2}+2\lambda(t)\langle
V(t,p(t))-V(t,x(t)),p(t)-\bar{x}(t)\rangle.$ Hence,

$\displaystyle 2\langle x(t)-\bar{x}(t),\dot{x}(t)\rangle$
$\displaystyle\leq-2\|x(t)-p(t)\|^{2}-2\lambda(t)\varepsilon(t)\|p(t)-\bar{x}(t)\|^{2}$
$\displaystyle~{}~{}~{}+2\lambda(t)\langle
V(t,p(t))-V(t,x(t)),p(t)-\bar{x}(t)\rangle$
$\displaystyle~{}~{}~{}+2\lambda(t)\langle
x(t)-\bar{x}(t),V(t,x(t))-V(t,p(t))\rangle$
$\displaystyle\leq-2(1-\lambda(t)L(t))\|x(t)-p(t)\|^{2}-2\lambda(t)\varepsilon(t)\|p(t)-\bar{x}(t)\|^{2}$

the proof is completed. ∎

###### Theorem 10

Let $t\mapsto x(t)$ be the strong global solution of (1), where $t\geq 0$, for
almost all $t\in[0,+\infty)$, assume that
$\limsup_{\to\infty}\lambda(t)\beta(t)<\mu$, as well as that Assumptions 1 and
2 hold. Assume further that

  * (a)

$\lim_{t\to\infty}\delta(t)=0$ and
$\lim\limits_{t\rightarrow+\infty}\int_{0}^{t}\delta(s)\operatorname{d\\!}s=\infty$,
where $\delta(t)=\frac{1-\lambda(t)L(t)}{a^{2}(t)}$, and
$a(t)=2+\frac{1}{\lambda(t)\varepsilon(t)}+\frac{1}{\eta\varepsilon(t)}+\frac{\beta(t)}{\mu\varepsilon(t)}.$

  * (b)

$\lim_{t\to\infty}\frac{\dot{\varepsilon}(t)}{\varepsilon(t)\delta(t)}=0$ and
$\frac{\dot{\beta}(t)}{\varepsilon(t)\delta(t)}=\mathcal{O}(1)$ as
$t\to\infty$.

Then $x(t)\rightarrow\Pi_{\operatorname{zer}(\Phi)}(0)$ as
$t\rightarrow+\infty$.

###### Proof:

Define $\theta(t)=\frac{1}{2}\|x(t)-\bar{x}(t)\|^{2}$ where $t\geq 0$. From
$\bar{x}(t)=\bar{x}(\varepsilon(t),\beta(t))$, we have
$\dot{\theta}(t)=\langle
x(t)-\bar{x}(t),\dot{x}(t)-\frac{\differential}{\differential
t}\bar{x}(t)\rangle,$ where $\frac{\differential}{\differential
t}\bar{x}(t)=\frac{\partial}{\partial\varepsilon}\bar{x}(\varepsilon(t),\beta(t))\dot{\varepsilon}(t)+\frac{\partial}{\partial\beta}\bar{x}(\varepsilon(t),\beta(t))\dot{\beta}(t).$
Before proving the statement, we need to establish some estimates on
$\frac{\differential}{\differential t}\bar{x}(t)$ first.

(i) Estimate on
$\frac{\partial}{\partial\varepsilon}\bar{x}(\varepsilon(t),\beta(t))$:

Set $\varepsilon_{1}=\varepsilon,\varepsilon_{2}=\varepsilon+h$, where
$h\rightarrow 0^{+}$, we obtain:

$\displaystyle\lim\limits_{h\rightarrow
0}\frac{\|\bar{x}(\varepsilon+h,\beta)-\bar{x}(\varepsilon,\beta)\|}{|h|}=\|\frac{\partial}{\partial\varepsilon}\bar{x}(\varepsilon,\beta)\|$
$\displaystyle\leq\lim\limits_{h\rightarrow
0}\frac{1}{\varepsilon+h}\|\bar{x}(\varepsilon,\beta)\|=\frac{\|\bar{x}(\varepsilon,\beta)\|}{\varepsilon}.$

(ii) Estimate on
$\frac{\partial}{\partial\beta}\bar{x}(\varepsilon(t),\beta(t))$: As in part
(i) we obtain

$\lim\limits_{h\rightarrow
0}\frac{\|\bar{x}(\varepsilon,\beta+h)-\bar{x}(\varepsilon,\beta)\|}{|h|}\leq\frac{\|\mathsf{B}(\bar{x}(\varepsilon,\beta))\|}{\varepsilon}.$
combining (i), (ii) with Lemma 9, we get

$\displaystyle\dot{\theta}$ $\displaystyle=\langle
x(t)-\bar{x}(t),\dot{x}(t)\rangle-\dot{\varepsilon}(t)\langle
x(t)-\bar{x}(t),\frac{\partial}{\partial\varepsilon}\bar{x}(\varepsilon(t),\beta(t))\rangle$
$\displaystyle~{}~{}~{}-\dot{\beta}(t)\langle
x(t)-\bar{x}(t),\frac{\partial}{\partial\beta}\bar{x}(\varepsilon(t),\beta(t))\rangle$
$\displaystyle\leq-(1-\lambda(t)L(t))\|x(t)-p(t)\|^{2}-\varepsilon(t)\lambda(t)\|p(t)-\bar{x}(t)\|^{2}$
$\displaystyle~{}~{}~{}-\dot{\varepsilon}(t)\langle
x(t)-\bar{x}(t),\frac{\partial}{\partial\varepsilon}\bar{x}(\varepsilon(t),\beta(t))\rangle$
$\displaystyle~{}~{}~{}-\dot{\beta}(t)\langle
x(t)-\bar{x}(t),\frac{\partial}{\partial\beta}\bar{x}(\varepsilon(t),\beta(t))\rangle$

As $\Phi_{t}=\mathsf{A}+V(t,\cdot)$ is $\varepsilon(t)$-strongly monotone, (6)
shows that

$\displaystyle\lambda(t)\varepsilon(t)\|p(t)-\bar{x}(t)\|^{2}$
$\displaystyle\leq\langle
x(t)-p(t)+\lambda(t)[V(t,p(t))-V(t,x(t))],p(t)-\bar{x}(t)\rangle,$

Using Cauchy-Schwarz, and the $L(t)$-Lipschitz continuity of $V_{t}$, we
obtain

$\norm{p(t)-\bar{x}(t)}\leq\big{(}\frac{1}{\lambda(t)\varepsilon(t)}+1+\frac{1}{\eta\varepsilon(t)}+\frac{\beta(t)}{\mu\varepsilon(t)}\big{)}\|x(t)-p(t)\|.$

it follows $\|x(t)-\bar{x}(t)\|\leq\|x(t)-p(t)\|+\|p(t)-\bar{x}(t)\|\leq
a(t)\|x(t)-p(t)\|.$ For almost all $t\geq 0$, we thus get
$-\|x(t)-p(t)\|^{2}\leq-\frac{1}{a^{2}(t)}\|x(t)-\bar{x}(t)\|^{2}$. Define
$\varphi\triangleq\sqrt{2\theta}$, combining with the last bound on
$\dot{\theta}$, we obtain

$\displaystyle\dot{\theta}(t)=\dot{\varphi}(t)\varphi(t)$
$\displaystyle\leq-\frac{1-\lambda(t)L(t)}{a^{2}(t)}\varphi(t)^{2}-\dot{\varepsilon}(t)\varphi(t)\frac{\|\bar{x}(t)\|}{\varepsilon(t)}$
$\displaystyle~{}~{}~{}+\frac{\dot{\beta}(t)}{\varepsilon(t)}\varphi(t)\|\mathsf{B}(\bar{x}(t))\|.$

Define $\delta(t)\triangleq\frac{1-\lambda(t)L(t)}{a^{2}(t)}$ and the
integrating factor $\Delta(t)\triangleq\int_{0}^{t}\delta(s)\differential s$,
as well as
$w(t):=\norm{\bar{x}(t)}-\frac{\dot{\beta}(t)}{\dot{\varepsilon}(t)}\norm{\mathsf{B}(\bar{x}(t))}$.
We can then continue from the previous display with
$\frac{\differential}{\differential
t}\big{(}\varphi(t)\exp(\Delta(t))\big{)}\leq-\frac{\dot{\varepsilon}(t)}{\varepsilon(t)}\exp(\Delta(t))w(t).$
Integrating both sides from 0 to $t$, it immediately follows

$\varphi(t)\leq\exp(-\Delta(t))\bigg{[}\varphi(0)-\int_{0}^{t}\bigg{(}\exp(\Delta(s))\frac{\dot{\varepsilon}(s)}{\varepsilon(s)}w(s)\bigg{)}\differential
s\bigg{]}.$

If
$t\mapsto\int_{0}^{t}\exp(\Delta(s))\frac{\dot{\varepsilon}(s)}{\varepsilon(s)}w(s)\differential
s$ is bounded, then we immediately obtain from hypothesis (i) that
$\varphi(t)\to 0$. Otherwise, we apply l’Hôpital’s rule to get

$\displaystyle\lim_{t\to\infty}$
$\displaystyle\exp(-\Delta(t))\int_{0}^{t}\exp(\Delta(s))\frac{\dot{\varepsilon}(s)}{\varepsilon(s)}w(s)\differential
s$
$\displaystyle=\lim_{t\to\infty}\frac{\exp(\Delta(t))\frac{\dot{\varepsilon}(t)}{\varepsilon(t)}w(t)}{\delta(t)\exp(\Delta(t))}=\lim_{t\to\infty}\frac{\frac{\dot{\varepsilon}(t)}{\varepsilon(t)}w(t)}{\delta(t)}.$

Since $\mathsf{C}=\operatorname{zer}(\mathsf{B})$, and $\mathsf{B}$ is
Lipschitz, we know that $t\mapsto\norm{\mathsf{B}(\bar{x}(t))}$ is bounded.
Additionally, we know from the proof of Proposition 4 that
$\norm{\bar{x}(t)}\leq\inf\\{\norm{x}:x\in\operatorname{zer}(\Phi)\\}$. Using
conditions (a) and (b), we deduce that $\varphi(t)\to 0$ and therefore
$\norm{x(t)-\bar{x}(t)}\to 0$. Using Proposition 4, we conclude
$\|x(t)-\Pi_{\operatorname{zer}(\Phi)}(0)\|\leq\|x(t)-\bar{x}(t)\|+\|\bar{x}(t)-\Pi_{\operatorname{zer}(\Phi)}(0)\|$.
Hence, $x(t)\rightarrow\Pi_{\operatorname{zer}(\Phi)}(0)$ as
$t\rightarrow+\infty$. ∎

In the remainder of this note, we give some concrete specifications for
functions $\varepsilon(t),\lambda(t)$ and $\beta(t)$ satisfying all conditions
for Theorem 10 to hold. By hypothesis, we have
$\liminf_{t\to\infty}(1-\lambda(t)L(t))=1-\limsup_{t\to\infty}\lambda(t)L(t)>0$.
Additionally,

$a(t)=2+\frac{1}{\varepsilon(t)}\left(\frac{1}{\lambda(t)}+\frac{1}{\eta}+\frac{\beta(t)}{\mu}\right)=\frac{\lambda(t)(\varepsilon(t)+L(t))+1}{\lambda(t)\varepsilon(t)},$

which implies
$a(t)=\frac{L(t)}{\varepsilon(t)}(1+\frac{\varepsilon(t)}{L(t)}+\frac{1}{L(t)\lambda(t)})=\mathcal{O}(\beta(t)/\varepsilon(t))$,
using that $L(t)=\mathcal{O}(\beta(t))$. This in turn implies
$\delta(t)=\frac{1-\lambda(t)L(t)}{a^{2}(t)}=\mathcal{O}(\varepsilon^{2}(t)/\beta^{2}(t))$.
Hence, $\lim_{t\to\infty}\delta(t)=0$, and for obtaining $\delta\notin
L^{1}(\mathbb{R}_{+})$ it suffices to guarantee that
$\int_{0}^{\infty}\frac{\varepsilon^{2}(t)}{\beta^{2}(t)}\differential
t=\infty$. Then,
$\frac{\dot{\varepsilon}(t)}{\varepsilon(t)\delta(t)}=\frac{\dot{\varepsilon}(t)L^{2}(t)}{\varepsilon^{3}(t)}\frac{(1+\frac{\varepsilon(t)}{L(t)}+\frac{1}{(L(t)\lambda(t)})^{2}}{1-\lambda(t)L(t)}\\\
=\frac{\dot{\varepsilon}(t)\beta^{2}(t)}{\varepsilon^{3}(t)}\mathcal{O}(1).$
It therefore suffices to have
$\lim_{t\to\infty}\frac{\dot{\varepsilon}(t)\beta^{2}(t)}{\varepsilon^{3}(t)}=0$.
By a similar argument, it is easy to see that
$\frac{\dot{\beta}(t)}{\varepsilon(t)\delta(t)}=\frac{\dot{\beta}(t)\beta(t)^{2}}{\varepsilon(t)^{3}}\mathcal{O}(1)$.
Therefore, it suffices to ensure that
$\frac{\dot{\beta}(t)\beta(t)^{2}}{\varepsilon(t)^{3}}$ is bounded. Finding
such functions is not too difficult, as the next remark shows.

###### Remark 1

Assume $\varepsilon(t)=(t+b)^{-(r+q)},\beta(t)=(t+b)^{q}$, where $q,r,b>0$ are
chosen such that $r+q>0$. Then
$\frac{\varepsilon^{2}(t)}{\beta^{2}(t)}=(t+b)^{-2(r+2q)}$, and consequently
we need to impose the restriction $2q+r<1/2$ to ensure that $\delta\notin
L^{1}(\mathbb{R}_{+})$. Additionally, we compute
$\frac{\dot{\varepsilon}(t)\beta(t)^{2}}{\varepsilon(t)^{3}}=-(r+q)(t+b)^{2r+3q-1}$.
This yields the restriction $2r+3q<1$. Finally,
$\frac{\dot{\beta}(t)\beta(t)^{2}}{\varepsilon^{3}(t)}=q(t+b)^{6q+3r-1}$, and
to make this a bounded sequence, we need to impose the condition
$2q+r\leq\frac{1}{3}$. These conditions together span a region of feasible
parameters $r,q$ which is nonempty. $\Diamond$

##  IV Numerical Examples

To illustrate the empirical performance of our method we consider the saddle
point problem

$\displaystyle\min_{x_{1}\in\mathcal{X}_{1}}\max_{x_{2}\in\mathcal{X}_{2}}\langle
Qx_{1},x_{2}\rangle+\langle b$ $\displaystyle,x_{1}\rangle-\langle
c,x_{2}\rangle+g\norm{x_{1}}^{2}-f\norm{x_{2}}^{2}$ s.t.: $\displaystyle
x:=(x_{1},x_{2})\in\mathsf{C}$

where the coupling constraint is a polyhedron
$\mathsf{C}=\operatorname*{argmin}\frac{1}{2}\norm{T_{1}x_{1}+T_{2}x_{2}-t}^{2}$.
This problem is adapted from [29]. The sets
$\mathcal{X}_{i}\subseteq\mathbb{R}^{n_{i}}$ are individual restrictions, and
$T_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}^{d}$ are linear mappings. Define
$\mathsf{T}=[T_{1};T_{2}]$ the stacked matrix of dimensions $d\times
n,n=n_{1}+n_{2}$. The vector $t\in\mathbb{R}^{d}$ is a given right-hand side.
To embed this problem into our formulation, we define
$g(x_{1},x_{2})=\frac{1}{2}\norm{T_{1}x_{1}+T_{2}x_{2}-t}^{2}$, so that
$\mathsf{B}(x_{1},x_{2})=\mathsf{T}^{\ast}(\mathsf{T}x-t)$ is just the
gradient of $g$. Clearly $\mathsf{C}=\operatorname{zer}(B)$.

In Figure 1 we can see the development of $\|x(t)-p(t)\|$ when we define
$q=0.2$ and various values of the Tikhonov term $(t+1)^{(r+q)}$. However,
$\|x(t)-p(t)\|$ is the fixed point residual of the operator
$\operatorname{\mathsf{J}}_{\lambda A}(I-\lambda V)$. According to the
convergence analysis, we get $\|x(t)-p(t)\|\to 0$ as $t\to+\infty$.

Figure 1: $\|x(t)-p(t)\|$

Figure 2: Feasibility Gap

## APPENDIX

###### Proof:

To simplify notation, we set
$\bar{x}_{n}\equiv\bar{x}(\varepsilon_{n},\beta_{n})$. for all $n\geq 1$. The
proof proceeds in three steps:

  * (i)

The sequence $(\bar{x}_{n})_{n\in\mathbb{N}}$ is bounded.
Let $z\in\operatorname{zer}(\Phi)$ arbitrary. Then, there exists
$\xi\in\operatorname{\mathsf{N}}_{\mathsf{C}}(z)$ such that
$-\mathsf{D}(z)-\xi\in\mathsf{A}(z)$. Since
$\bar{x}_{n}\in\operatorname{zer}(\Phi_{\varepsilon_{n},\beta_{n}})$, we have
$-\varepsilon_{n}\bar{x}_{n}-\beta_{n}\mathsf{B}(\bar{x}_{n})-\mathsf{D}(\bar{x}_{n})\in\mathsf{A}(\bar{x}_{n})$
for all $n\geq 1.$ Since $\mathsf{A}$ is maximally monotone, we have for all
$n\geq 1$:

$\langle-\mathsf{D}(z)-\xi+\varepsilon\bar{x}_{n}+\beta_{n}\mathsf{B}(\bar{x}_{n})+\mathsf{D}(\bar{x}_{n}),z-\bar{x}_{n}\rangle\geq
0$ (7)

Rearranging, and using the fact that $\mathsf{B}(z)=0$ (since
$z\in\mathsf{C})$ as well that $B$ is a monotone operator, it follows

$\varepsilon\langle\bar{x}_{n},z-\bar{x}_{n}\rangle\geq\beta\langle\mathsf{B}(z)-\mathsf{B}(\bar{x}_{n}),z-\bar{x}_{n}\rangle\geq
0$

By Cauchy-Schwarz, we therefore obtain $\norm{\bar{x}_{n}}\leq\norm{z}$ for
all $z\in\operatorname{zer}(\Phi)$. It follows $\sup_{n\geq
1}\norm{\bar{x}_{n}}\leq\inf\\{\norm{x}:x\in\operatorname{zer}(\Phi)\\}$.

  * (ii)

Weak accumulation points of $(\bar{x}_{n})$ are in $\mathsf{C}$.
Since $(\bar{x}_{n})_{n\geq 1}$ is bounded, we can extract a weakly converging
subsequence $\bar{x}_{n_{j}}\rightharpoonup\bar{x}$. Let
$\varepsilon_{n_{j}},\beta_{n_{j}}$ the corresponding subsequences of the
parameters sequences $(\varepsilon_{n},\beta_{n})$. Using (7) and the
monotonicity of $\mathsf{D}$, we see

$\beta_{n_{j}}\langle\mathsf{B}(\bar{x}_{n_{j}}),z-\bar{x}_{n_{j}}\rangle\geq-\varepsilon_{n_{j}}\langle\bar{x}_{n_{j}},z-\bar{x}_{n_{j}}\rangle+\langle\xi,z-\bar{x}_{n_{j}}\rangle.$
$\langle\mathsf{B}(\bar{x}_{n_{j})},\bar{x}_{n_{j}}-z\rangle\leq\frac{\varepsilon_{n_{j}}}{\beta_{n_{j}}}\langle\bar{x}_{n_{j}},z-\bar{x}_{n_{j}}\rangle+\frac{1}{\beta_{n_{j}}}\langle\xi,\bar{x}_{n_{j}}-z\rangle.$

$\mathsf{B}$ is cocoercive and $\mathsf{B}(z)=0$, which implies that there
exists a $\gamma>0$ such that

$\langle\mathsf{B}(\bar{x}_{n_{j}}),\bar{x}_{n_{j}}-z\rangle\geq\gamma\norm{\mathsf{B}(\bar{x}_{n_{j}})-\mathsf{B}(z)}^{2}=\gamma\norm{\mathsf{B}(\bar{x}_{n_{j}})}^{2}.$

Hence,

$\norm{\mathsf{B}(\bar{x}_{n_{j}})}^{2}\leq\frac{\varepsilon_{n_{j}}}{\gamma\beta_{n_{j}}}\langle\bar{x}_{n_{j}},z-\bar{x}_{n_{j}}\rangle+\frac{1}{\gamma\beta_{n_{j}}}\langle\xi,\bar{x}_{n_{j}}-z\rangle.$

and from $\beta_{n_{j}}\to\infty$, we conclude
$\lim_{j\to\infty}\norm{\mathsf{B}(\bar{x}_{n_{j}})}=0$. By continuity,
$\mathsf{B}\bar{x}_{n_{j}}\to\mathsf{B}(\bar{x})$, which implies
$\mathsf{B}(\bar{x})=0$. This is equivalent to $\bar{x}\in\mathsf{C}$.

  * (iii)

Any weak accumulation point of $(\bar{x}_{n})_{n\in\mathbb{N}}$ is in
$\operatorname{zer}(\Phi)$.
We use the characterization of the points in $\operatorname{zer}(\Phi)$
provided by Fact 2. Let $(u,w)\in\operatorname{graph}(\Phi)$ be arbitrary.
Then, there exists $\xi\in\operatorname{\mathsf{N}}_{\mathsf{C}}(u)$ such that
$w-\xi-\mathsf{D}(u)\in\mathsf{A}(u).$ Moreover, for all $n\geq 1$,

$-\varepsilon_{n}\bar{x}_{n}-\beta_{n}\mathsf{B}(\bar{x}_{n})-\mathsf{D}(\bar{x}_{n})\in\mathsf{A}(\bar{x}_{n}).$

Monotonicity of $\mathsf{A}$ gives

$\langle-\varepsilon_{n}\bar{x}_{n}-\beta_{n}\mathsf{B}(\bar{x}_{n})-\mathsf{D}(\bar{x}_{n})-w+\xi+\mathsf{D}(u),\bar{x}_{n}-u\rangle\geq
0$

Using the monotonicity of $\mathsf{D}$,

$\displaystyle\langle w,u-\bar{x}_{n}\rangle$
$\displaystyle\geq\varepsilon_{n}\langle\bar{x}_{n},\bar{x}_{n}-u\rangle+\langle\beta_{n}\mathsf{B}(\bar{x}_{n}),\bar{x}_{n}-u\rangle$
$\displaystyle~{}~{}~{}+\langle\xi,u-\bar{x}_{n}\rangle$

Since $\mathsf{B}$ is monotone and $\mathsf{B}(u)=0$, we also have
$\langle\mathsf{B}(\bar{x}_{n}),\bar{x}_{n}-u\rangle\geq 0$. Consequently,

$\langle
w,u-\bar{x}_{n}\rangle\geq\varepsilon_{n}\langle\bar{x}_{n},\bar{x}_{n}-u\rangle+\langle\xi,u-\bar{x}_{n}\rangle.$

Therefore, $\liminf_{n\to\infty}\langle
w,u-\bar{x}_{n}\rangle\geq\langle\xi,u-\bar{x}\rangle\geq 0$ using that
$\xi\in\operatorname{\mathsf{N}}_{C}(u)$. Using Fact 2, this means that
accumulation points of $\bar{x}_{n}$ are solutions of the original problem.

  * (iv)

$\bar{x}_{n}\to\bar{x}=\operatorname*{argmin}\\{\norm{x}:x\in\operatorname{zer}(\Phi)\\}$.
Let $\bar{x}$ be any weak limit of $(\bar{x}_{n})_{n}$. We know that
$\bar{x}\in\operatorname{zer}(\Phi)$. Step (i) of the proof shows
$\norm{\bar{x}}\leq\inf\\{\norm{x}:x\in\operatorname{zer}(\Phi)\\}$. The claim
follows.

∎

###### Proof:

Fix $\beta>0$ and pick $\varepsilon_{1},\varepsilon_{2}>0$. Let
$\mathsf{D}_{\varepsilon}:=\mathsf{D}+\varepsilon\operatorname{Id}$ and set
$z_{1}=\bar{x}(\varepsilon_{1},\beta)$ and
$z_{2}=\bar{x}(\varepsilon_{2},\beta)$. It follows
$-\mathsf{D}_{\varepsilon_{1}}(z_{1})-\beta\mathsf{B}(z_{1})\in\mathsf{A}(z_{1})$,
and
$-\mathsf{D}_{\varepsilon_{2}}(z_{2})-\beta\mathsf{B}(z_{2})\in\mathsf{A}(z_{2})$.
Since $\mathsf{A}$ is maximally monotone, we have

$\langle
z_{1}-z_{2},-\mathsf{D}_{\varepsilon_{1}}(z_{1})-\beta\mathsf{B}(z_{1})+\mathsf{D}_{\varepsilon_{2}}(z_{2})+\beta\mathsf{B}(z_{2})\rangle\geq
0.$

Since $\mathsf{D}$ and $\mathsf{B}$ are both maximally monotone, we conclude
$\langle\varepsilon_{1}z_{1}-\varepsilon_{2}z_{2},z_{1}-z_{2}\rangle\leq 0$.
Assume first that $\varepsilon_{2}>\varepsilon_{1}$. Then

$0\geq\langle\varepsilon_{1}z_{1}-\varepsilon_{2}z_{2},z_{1}-z_{2}\rangle=\varepsilon_{1}\norm{z_{1}-z_{2}}^{2}+(\varepsilon_{1}-\varepsilon_{2})\langle
z_{2},z_{1}-z_{2}\rangle,$

which means $(\varepsilon_{2}-\varepsilon_{1})\langle
z_{2},z_{1}-z_{2}\rangle\geq\varepsilon_{1}\norm{z_{1}-z_{2}}^{2}$. By Cauchy-
Schwarz,
$(\varepsilon_{2}-\varepsilon_{1})\norm{z_{2}}\cdot\norm{z_{1}-z_{2}}\geq\varepsilon_{1}\norm{z_{1}-z_{2}}^{2},$
so that
$\norm{z_{2}-z_{1}}\leq\frac{\varepsilon_{2}-\varepsilon_{1}}{\varepsilon_{1}}\norm{z_{2}}.$
Next, assuming $\varepsilon_{1}>\varepsilon_{2}$. Then, interchanging the
labels in the above inequality, we get
$\norm{z_{2}-z_{1}}\leq\frac{\varepsilon_{1}-\varepsilon_{2}}{\varepsilon_{2}}\norm{z_{1}}.$
Hence,
$\norm{\bar{x}(\varepsilon_{1},\beta)-\bar{x}(\varepsilon_{2},\beta)}\leq\frac{\absolutevalue{\varepsilon_{2}-\varepsilon_{1}}}{\max\\{\varepsilon_{1},\varepsilon_{2}\\}}\max\\{\norm{z_{1}},\norm{z_{2}}\\}$.
This shows that $\varepsilon\mapsto\bar{x}(\varepsilon,\beta)$ is locally
Lipschitz.

Now, fix $\varepsilon>0$ and let $\beta_{1},\beta_{2}>0$. Denote
$z_{1}=\bar{x}(\varepsilon,\beta_{1})$ and
$z_{2}=\bar{x}(\varepsilon,\beta_{2})$. By definition, we have

$-D_{\varepsilon}z_{1}-\beta_{1}Bz_{1}\in Az_{1},\text{ and
}-D_{\varepsilon}z_{2}-\beta_{2}Bz_{2}\in Az_{2}.$

It follows
$\beta_{2}\langle\mathsf{B}(z_{2}),z_{1}-z_{2}\rangle-\beta_{1}\langle\mathsf{B}(z_{1}),z_{1}-z_{2}\rangle\geq\varepsilon\norm{z_{1}-z_{2}}^{2}.$
Assume that $\beta_{2}>\beta_{1}$. Then
$(\beta_{2}-\beta_{1})\langle\mathsf{B}(z_{1}),z_{1}-z_{2}\rangle+\beta_{2}\langle\mathsf{B}(z_{2})-\mathsf{B}(z_{1}),z_{1}-z_{2}\rangle\geq\varepsilon\norm{z_{1}-z_{2}}^{2}$.
Using the monotonicity of $\mathsf{B}$, we conclude

$\norm{z_{1}-z_{2}}\leq\frac{\beta_{2}-\beta_{2}}{\varepsilon}\norm{\mathsf{B}(z_{1})}.$

If $\beta_{1}>\beta_{2}$, we repeat the above computation, and obtain
$\norm{z_{1}-z_{2}}\leq\frac{\beta_{1}-\beta_{2}}{\varepsilon}\norm{\mathsf{B}(z_{2})}.$
This yields
$\norm{z_{1}-z_{2}}\leq\frac{\absolutevalue{\beta_{1}-\beta_{2}}}{\varepsilon}\max\\{\norm{\mathsf{B}(z_{1})},\norm{\mathsf{B}(z_{2})}\\}$,
which shows that $\beta\mapsto\bar{x}(\varepsilon,\beta)$ is locally
Lipschitz, for all $\varepsilon>0$.

Next, we show the Lipschitz continuity of the bivariate map
$(\varepsilon,\beta)\mapsto\bar{x}(\varepsilon,\beta)$. Let
$t_{1}\triangleq(\varepsilon_{1},\beta_{1})$ and
$t_{2}\triangleq(\varepsilon_{2},\beta_{2})$ with corresponding solutions
$\bar{x}(t_{1})$ and $\bar{x}(t_{2})$. By definition of these points, we have
$-V_{(\varepsilon_{1},\beta_{1})}\bar{x}(t_{1})\in\mathsf{A}\bar{x}(t_{1}),\text{
and
}-V_{(\varepsilon_{2},\beta_{2})}(\bar{x}(t_{2}))\in\mathsf{A}\bar{x}(t_{2}).$
Hence,

$\langle\mathsf{D}_{\varepsilon_{2}}\bar{x}(t_{2})+\beta_{2}\mathsf{B}\bar{x}(t_{2})-\mathsf{D}_{\varepsilon_{1}}\bar{x}(t_{1})-\beta_{1}\mathsf{B}\bar{x}(t_{1}),\bar{x}(t_{1})-\bar{x}(t_{2})\rangle\geq
0.$

Rearranging, we obtain

$\displaystyle\langle\varepsilon_{2}\bar{x}(t_{2})-\varepsilon_{1}\bar{x}(t_{1}),\bar{x}(t_{1})-\bar{x}(t_{2})\rangle\geq$
$\displaystyle\beta_{1}\langle\mathsf{B}\bar{x}(t_{1}),\bar{x}(t_{1})-\bar{x}(t_{2})\rangle$
$\displaystyle+\beta_{2}\langle\mathsf{B}\bar{x}(t_{2}),\bar{x}(t_{2})-\bar{x}(t_{1})\rangle.$

Then,

$\displaystyle\varepsilon_{1}\norm{\bar{x}(t_{1})-\bar{x}(t_{2})}^{2}$
$\displaystyle\leq\absolutevalue{\beta_{2}-\beta_{1}}\norm{\mathsf{B}\bar{x}(t_{1})}\cdot\norm{\bar{x}(t_{2})-\bar{x}(t_{1})}$
$\displaystyle~{}~{}~{}+\absolutevalue{\varepsilon_{2}-\varepsilon_{1}}\norm{\bar{x}(t_{2})}\cdot\norm{\bar{x}(t_{2})-\bar{x}(t_{1})}.$

It follows

$\norm{\bar{x}(t_{2})-\bar{x}(t_{1})}\leq\frac{\absolutevalue{\beta_{2}-\beta_{1}}}{\varepsilon_{1}}\norm{\mathsf{B}\bar{x}(t_{1})}+\frac{\absolutevalue{\varepsilon_{2}-\varepsilon_{1}}}{\varepsilon_{1}}\norm{\bar{x}(t_{2})}.$

From the proof of Step (i) of the proof of Proposition 4, we deduce that
$\norm{\bar{x}(\varepsilon,\beta)}\leq\inf\\{\norm{x}:x\in\operatorname{zer}(\Phi)\\}\triangleq\mathtt{a}$.
Hence, defining
$\ell\triangleq\max\\{\sup_{x\in\mathbb{B}(0,\mathtt{a})}\norm{\mathsf{B}x},\mathtt{a}\\}$,
the claim follows. ∎

## References

  * [1] R. I. Boţ and C. Hendrich, “Convergence analysis for a primal-dual monotone + skew splitting algorithm with applications to total variation minimization,” _Journal of Mathematical Imaging and Vision_ , vol. 49, no. 3, pp. 551–568, 2014.
  * [2] E. Börgens and C. Kanzow, “A distributed regularized jacobi-type admm-method for generalized nash equilibrium problems in hilbert spaces,” _Numerical Functional Analysis and Optimization_ , vol. 39, no. 12, pp. 1316–1349, 09 2018.
  * [3] E. Börgens and C. Kanzow, “Admm-type methods for generalized nash equilibrium problems in hilbert spaces,” _SIAM Journal on Optimization_ , vol. 31, no. 1, pp. 377–403, 2021.
  * [4] P. Yi and L. Pavel, “An operator splitting approach for distributed generalized nash equilibria computation,” _Automatica_ , vol. 102, pp. 111–121, 2019.
  * [5] H. Attouch and M.-O. Czarnecki, “Asymptotic behavior of coupled dynamical systems with multiscale aspects,” _Journal of Differential Equations_ , vol. 248, no. 6, pp. 1315–1344, 2010.
  * [6] H. Attouch, J. Bolte, P. Redont, and A. Soubeyran, “Alternating proximal algorithms for weakly coupled convex minimization problems. applications to dynamical games and pde’s,” _Journal of Convex Analysis_ , vol. 15, no. 3, p. 485, 2008.
  * [7] M. Amini and F. Yousefian, “An iterative regularized incremental projected subgradient method for a class of bilevel optimization problems,” in _2019 American Control Conference (ACC)_ , 2019, pp. 4069–4074.
  * [8] Yousefian, Farzad. ”Bilevel distributed optimization in directed networks.” 2021 American Control Conference (ACC). IEEE, 2021.
  * [9] E. Benenati, W. Ananduta, and S. Grammatico, “Optimal selection and tracking of generalized nash equilibria in monotone games,” _IEEE Transactions on Automatic Control_ , 2023.
  * [10] C. Sun and G. Hu, “Continuous-time penalty methods for nash equilibrium seeking of a nonsmooth generalized noncooperative game,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 10, pp. 4895–4902, 2021.
  * [11] M. Bianchi, G. Belgioioso, and S. Grammatico, “Fast generalized nash equilibrium seeking under partial-decision information,” _Automatica_ , vol. 136, p. 110080, 2022.
  * [12] Omidshafiei, Shayegan, et al. ”Deep decentralized multi-task multi-agent reinforcement learning under partial observability.” International Conference on Machine Learning. PMLR, 2017.
  * [13] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial networks,” _Communications of the ACM_ , vol. 63, no. 11, pp. 139–144, 2020.
  * [14] F. Facchinei and C. Kanzow, “Generalized nash equilibrium problems,” _Annals of Operations Research_ , vol. 175, no. 1, pp. 177–211, 2010.
  * [15] S. Grammatico, “Dynamic control of agents playing aggregative games with coupling constraints,” _IEEE Transactions on Automatic Control_ , vol. 62, no. 9, pp. 4537–4548, 2017.
  * [16] _Distributed forward-backward (half) forward algorithms for generalized Nash equilibrium seeking_. IEEE, 2020.
  * [17] _A relaxed-inertial forward-backward-forward algorithm for stochastic generalized Nash equilibrium seeking_. IEEE, 2021.
  * [18] F. Facchinei and C. Kanzow, “Penalty methods for the solution of generalized nash equilibrium problems,” _SIAM Journal on Optimization_ , vol. 20, no. 5, pp. 2228–2253, 2010.
  * [19] C. Sun and G. Hu, “Continuous-time penalty methods for nash equilibrium seeking of a nonsmooth generalized noncooperative game,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 10, pp. 4895–4902, 2020.
  * [20] P. Tseng, “A modified forward-backward splitting method for maximal monotone mappings,” _SIAM Journal on Control and Optimization_ , vol. 38, no. 2, pp. 431–446, 2000.
  * [21] H. Attouch, M.-O. Czarnecki, and J. Peypouquet, “Coupling forward-backward with penalty schemes and parallel splitting for constrained variational inequalities,” _SIAM Journal on Optimization_ , vol. 21, no. 4, pp. 1251–1274, 2011.
  * [22] J. Peypouquet, “Coupling the gradient method with a general exterior penalization scheme for convex minimization,” _Journal of Optimization Theory and Applications_ , vol. 153, no. 1, pp. 123–138, 2012.
  * [23] R. I. Boţ and E. Csetnek, “Forward-backward and tseng’s type penalty schemes for monotone inclusion problems,” _Set-Valued and Variational Analysis_ , vol. 22, pp. 313–331, 2014.
  * [24] ——, “Approaching the solving of constrained variational inequalities via penalty term-based dynamical systems,” _Journal of Mathematical Analysis and Applications_ , vol. 435, no. 2, pp. 1688–1700, 2016.
  * [25] R. Cominetti, J. Peypouquet, and S. Sorin, “Strong asymptotic convergence of evolution equations governed by maximal monotone operators with tikhonov regularization,” _Journal of Differential Equations_ , vol. 245, no. 12, pp. 3753–3763, 2008.
  * [26] R. I. Bot, S.-M. Grad, D. Meier, and M. Staudigl, “Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure,” _Advances in Nonlinear Analysis_ , vol. 10, no. 1, pp. 450–476, 2020.
  * [27] H. H. Bauschke and P. L. Combettes, _Convex Analysis and Monotone Operator Theory in Hilbert Spaces_. Springer - CMS Books in Mathematics, 2016.
  * [28] E. D. Sontag, _Mathematical control theory: deterministic finite dimensional systems_. Springer Science & Business Media, 2013, vol. 6.
  * [29] Y. Ouyang and Y. Xu, “Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems,” _Mathematical Programming_ , vol. 185, no. 1, pp. 1–35, 2021.