Abstract
We study the existence and uniqueness of (locally) absolutely continuous trajectories of a dynamical system governed by a nonexpansive operator. The weak convergence of the orbits to a fixed point of the operator is investigated by relying on Lyapunov analysis. We show also an order of convergence of \(o\left( \frac{1}{\sqrt{t}}\right) \) for the fixed point residual of the trajectory of the dynamical system. We apply the results to dynamical systems associated with the problem of finding the zeros of the sum of a maximally monotone operator and a cocoercive one. Several dynamical systems from the literature turn out to be particular instances of this general approach.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction and Preliminaries
Having their origins in the nowadays standard works of Brézis, Baillon and Bruck (see [6, 12, 14]), differential inclusions and continuous dynamical systems governed by maximal monotone operators still play an important role in optimization and differential equations. While usually the existence and uniqueness of such trajectories is guaranteed in the framework of the Cauchy–Lipschitz theorem, their (ergodic) convergence to the set of zeros of the involved maximally monotone operators (which in case of the convex subdifferential of a convex function coincides with the set of its minima) relies on Lyapunov analysis.
In this paper we turn our attention to dynamical systems formulated via resolvents of maximal monotone operators, being motivated by several papers on this subject, like [1–3, 5, 8]. In [8], Bolte studied the convergence of the trajectories of the following dynamical system
where \(\phi :\mathcal{{H}}\rightarrow \mathbb {R}\) is a convex \(C^1\) function defined on a real Hilbert space \(\mathcal{{H}}\), \(C\) is a nonempty, closed and convex subset of \(\mathcal{{H}}\), \(x_0\in \mathcal{{H}}\), \(\mu >0\) and \(P_C\) denotes the projection operator on the set \(C\). In this context it is shown that the trajectory of (1) converges weakly to a minimizer of the optimization problem
provided the latter is solvable. We refer also to [3] for further statements and results concerning (1).
The following generalization of the dynamical system (1) has been recently considered by Abbas and Attouch in [1, Section 4.2]:
where \(\Phi :\mathcal{{H}}\rightarrow \mathbb {R}\cup \{+\infty \}\) is a proper, convex and lower semicontinuous function defined on a real Hilbert space \(\mathcal{{H}}\), \(B:\mathcal{{H}}\rightarrow \mathcal{{H}}\) is a cocoercive operator, \(x_0\in \mathcal{{H}}\), \(\mu >0\) and \({{\mathrm{\mathrm{prox}}}}_{\mu \Phi }:\mathcal{{H}}\rightarrow \mathcal{{H}}\),
denotes the proximal point operator of \(\Phi \).
According to [1], in case \({{\mathrm{\mathrm{zer}}}}(\partial \Phi +B)\ne \emptyset \), the weak convergence of the orbit \(x\) of (3) is ensured by choosing the step-size \(\mu \) in a suitable domain bounded by the parameter of cocoercivity of the operator \(B\) (notice that \(\partial \Phi \) denotes the convex subdifferential of \(\Phi \)).
Let us mention that the time discretization of the dynamical system (3) leads to the classical forward–backward algorithm, a scheme which iteratively generates a sequence that weakly converges to a zero of \(\partial \Phi +B\), see [1] and [7]. For more on the relations between the continuous and discrete dynamics we refer the reader to [19]. We also refer to [10, 11, 25] for more insights into the outstanding role played by the discrete forward–backward algorithm in connection to the solving of complexly structured monotone inclusion problems.
The dynamical systems (1) and (3) are the starting points of our research. It is known, see [7], that the discrete version of the forward–backward algorithm and some of its convergence properties follow from a more general iterative scheme, namely the Krasnosel’skiĭ–Mann algorithm, which generates a sequence which approaches the set of fixed points of a nonexpansive operator. Let us mention here that the classical Douglas–Rachford algorithm, designed for determining the set of zeros of the sum of two set-valued maximally monotone operators (see [7]) can be embedded in the framework of the Krasnosel’skiĭ–Mann-type algorithm.
In this paper we study a time-continuous dynamical system which involves a nonexpansive operator, see (5). Firstly, we address the existence and uniqueness of (locally) absolutely continuous trajectories of the considered system, which follows by reformulating in the framework of Cauchy–Lipschitz problems and by applying a classical result, see [17, 24]. In the next section we study the convergence of the trajectories to a fixed point of the operator, the investigation relying on Lyapunov analysis combined with the continuous version of the celebrated Opial Lemma. We study also the convergence rates of the fixed point residual of the orbits of the dynamical system, for which we obtain a speed of convergence of order \(o(1/\sqrt{t})\). Further, we propose a generalization of the forward–backward continuous version of the dynamical system (3) by considering instead of the convex subdifferential a maximally monotone operator and a relaxed backward step. A discussion on possible time-discretizations of the investigated dynamical systems is also made. In the last section we present a second approach which reduces the study of the dynamical system (5) via time rescaling arguments to the one of autonomous systems governed by cocoercive operators and which allows the formulation of convergence statements under weaker assumptions than in the direct approach.
Let us fix a few notations used throughout the paper. Let \(\mathbb {N}= \{0,1,2,\ldots \}\) be the set of nonnegative integers. Let \(\mathcal{{H}}\) be a real Hilbert space with inner product \(\langle \cdot ,\cdot \rangle \) and associated norm \(\Vert \cdot \Vert =\sqrt{\langle \cdot ,\cdot \rangle }\).
2 A Dynamical System: Existence and Uniqueness of Global Solutions
Let \(T:\mathcal{{H}}\rightarrow \mathcal{{H}}\) be a nonexpansive mapping (that is \(\Vert Tx-Ty\Vert \le \Vert x-y\Vert \) for all \(x,y\in \mathcal{{H}}\)), \(\lambda :[0,+\infty )\rightarrow [0,1]\) be a Lebesgue measurable function and \(x_0\in \mathcal{{H}}\). In this paper we are concerned with the following dynamical system:
The first issue we investigate is the existence of strong solutions for (5). As in [2, 5], we consider the following definition of an absolutely continuous function.
Definition 1
(see, for instance, [2, 5]) A function \(f:[0,b]\rightarrow \mathcal{{H}}\) (where \(b>0\)) is said to be absolutely continuous if one of the following equivalent properties holds:
-
(i)
there exists an integrable function \(g:[0,b]\rightarrow \mathcal{{H}}\) such that
$$\begin{aligned} f(t)=f(0)+\int _0^t g(s)ds \quad \forall t\in [0,b]; \end{aligned}$$ -
(ii)
\(f\) is continuous and its distributional derivative is Lebesgue integrable on \([0,b]\);
-
(iii)
for every \(\varepsilon > 0\), there exists \(\eta >0\) such that for any finite family of intervals \(I_k=(a_k,b_k)\) we have the implication:
$$\begin{aligned} \left( I_k\cap I_j=\emptyset \text{ and } \sum _k|b_k-a_k| < \eta \right) \Longrightarrow \sum _k\Vert f(b_k)-f(a_k)\Vert < \varepsilon . \end{aligned}$$
Remark 1
-
(a)
It follows from the definition that an absolutely continuous function is differentiable almost everywhere, its derivative coincides with its distributional derivative almost everywhere and one can recover the function from its derivative \(f'=g\) by the integration formula (i).
-
(b)
If \(f:[0,b]\rightarrow \mathcal{{H}}\) (where \(b>0\)) is absolutely continuous and \(B:\mathcal{{H}}\rightarrow \mathcal{{H}}\) is \(L\)-Lipschitz continuous (where \(L\ge 0\)), then the function \(h=B\circ f\) is absolutely continuous. This can be easily verified by considering the characterization in Definition 1(iii). Moreover, \(h\) is almost everywhere differentiable and the inequality \(\Vert h'(\cdot )\Vert \le L\Vert f'(\cdot )\Vert \) holds almost everywhere.
Definition 2
We say that \(x:[0,+\infty )\rightarrow \mathcal{{H}}\) is a strong global solution of (5) if the following properties are satisfied:
-
(i)
\(x:[0,+\infty )\rightarrow \mathcal{{H}}\) is absolutely continuous on each interval \([0,b]\), \(0<b<+\infty \);
-
(ii)
\(\dot{x}(t)=\lambda (t)\big (T(x(t))-x(t)\big )\) for almost every \(t\in [0,+\infty )\);
-
(iii)
\(x(0)=x_0\).
In what follows we verify the existence and uniqueness of strong global solutions of (5). To this end we use the Cauchy–Lipschitz theorem for absolutely continues trajectories (see for example [17, Proposition 6.2.1], [24, Theorem 54]).
It is immediate that the system (5) can be written as
where \(f:[0,+\infty )\times \mathcal{{H}}\rightarrow \mathcal{{H}}\) is defined by \(f(t,x)=\lambda (t)(Tx-x)\).
-
(a)
Take arbitrary \(x,y\in \mathcal{{H}}\). Relying on the nonexpansiveness of \(T\), for all \(t\ge 0\) we have
$$\begin{aligned} \Vert f(t,x)-f(t,y)\Vert \le 2\lambda (t)\Vert x-y\Vert . \end{aligned}$$Since \(\lambda \) is bounded above, one has \(2\lambda (\cdot )\in L^1([0,b])\) for any \(0<b<+\infty \);
-
(b)
Take arbitrary \(x\in \mathcal{{H}}\) and \(b>0\). One has
$$\begin{aligned} \int _0^b\Vert f(t,x)\Vert dt= \Vert Tx-x\Vert \int _0^b\lambda (t)dt\le b\Vert Tx-x\Vert , \end{aligned}$$hence
$$\begin{aligned} \forall x\in \mathcal{{H}}, \quad \forall b>0, \quad f(\cdot ,x)\in L^1([0,b],\mathcal{{H}}). \end{aligned}$$
By considering the statements proven in (a) and (b), the existence and uniqueness of a strong global solution of the dynamic system (5) follows.
Remark 2
From the considerations above one can easily notice that the existence and uniqueness of strong global solutions of (5) can be guaranteed in the more general setting when \(T\) is Lipschitz continuous and \(\lambda :[0,+\infty )\rightarrow \mathbb {R}\) is a Lebesgue measurable function such that \(\lambda (\cdot )\in L^1_{{{\mathrm{\mathrm{loc}}}}}([0,+\infty ))\).
3 Convergence of the Trajectories
In this section we investigate the convergence properties of the trajectories of the dynamical system (5). We show that under mild conditions imposed on the function \(\lambda \), the orbits converge weakly to a fixed point of the nonexpansive operator, provided the set of such points is nonempty.
In order to achieve this, we need the following preparatory result.
Lemma 3
([2, Lemma 5.2]) If \(1 \le p < \infty \), \(1 \le r \le \infty \), \(F:[0,+\infty )\rightarrow [0,+\infty )\) is locally absolutely continuous, \(F\in L^p([0,+\infty ))\), \(G:[0,+\infty )\rightarrow \mathbb {R}\), \(G\in L^r([0,+\infty ))\) and for almost all \(t\)
then \(\lim _{t\rightarrow +\infty } F(t)=0\).
The next result which we recall here is the continuous version of the Opial Lemma (see for example [2, Lemma 5.3], [1, Lemma 1.10]).
Lemma 4
Let \(S \subseteq \mathcal{{H}}\) be a nonempty set and \(x:[0,+\infty )\rightarrow \mathcal{{H}}\) a given map. Assume that
-
(i)
for every \(z\in S\), \(\lim _{t\rightarrow +\infty }\Vert x(t)-z\Vert \) exists;
-
(ii)
every weak sequential cluster point of the map \(x\) belongs to \(S\).
Then there exists \(x_{\infty }\in S\) such that \(w-\lim _{t\rightarrow +\infty }x(t)=x_{\infty }\).
The following result, which is a consequence of the demiclosedness principle (see [7, Theorem 4.17]), will be used in the proof of Theorem 6. which is the main theorem of this paper.
Lemma 5
([7, Corollary 4.18]) Let \(T:\mathcal{{H}}\rightarrow \mathcal{{H}}\) be nonexpansive and let \((x_n)_{n\in \mathbb {N}}\) be a sequence in \(\mathcal{{H}}\) and \(x\in \mathcal{{H}}\) such that \(w-\lim _{n\rightarrow +\infty } x_n=x\) and \((Tx_n-x_n)_{n\in \mathbb {N}}\) converges strongly to \(0\) (as \(n\rightarrow +\infty \)). Then \(x\in {{\mathrm{\mathrm{Fix}}}}T\).
The following identity will be used several times in the paper (see for example [7, Corollary 2.14]):
Theorem 6
Let \(T:\mathcal{{H}}\rightarrow \mathcal{{H}}\) be a nonexpansive mapping such that \({{\mathrm{\mathrm{Fix}}}}T\ne \emptyset \), \(\lambda :[0,+\infty )\rightarrow [0,1]\) a Lebesgue measurable function and \(x_0\in \mathcal{{H}}\). Suppose that one of the following conditions is fulfilled:
Let \(x:[0,+\infty )\rightarrow \mathcal{{H}}\) be the unique strong global solution of (5). Then the following statements are true:
-
(i)
the trajectory \(x\) is bounded and \(\int _0^{+\infty }\Vert \dot{x}(t)\Vert ^2dt<+\infty \);
-
(ii)
\(\lim _{t\rightarrow +\infty }(T(x(t))-x(t))=0\);
-
(iii)
\(\lim _{t\rightarrow +\infty }\dot{x}(t)=0\);
-
(iv)
\(x(t)\) converges weakly to a point in \({{\mathrm{\mathrm{Fix}}}}T\), as \(t\rightarrow +\infty \).
Proof
We rely on Lyapunov analysis combined with the Opial Lemma. We take an arbitrary \(y\in {{\mathrm{\mathrm{Fix}}}}T\) and give an estimation for \(\frac{d}{dt}\Vert x(t)-y\Vert ^2\). Take an arbitrary \(t\ge 0\). By (7), the fact that \(y\in {{\mathrm{\mathrm{Fix}}}}T\) and the nonexpansiveness of \(T\) we obtain:
Hence for all \(t\ge 0\) we have that
Since \(\lambda (t)\in [0,1]\) for all \(t\ge 0\), from (8) it follows that \(t\mapsto \Vert x(t)-y\Vert \) is decreasing, hence \(\lim _{t\rightarrow +\infty }\Vert x(t)-y\Vert \) exists. From here we obtain the boundedness of the trajectory and by integrating (8) we deduce also that \(\int _0^{+\infty }\Vert \dot{x}(t)\Vert ^2dt<+\infty \) and
thus (i) holds. Since \(y\in {{\mathrm{\mathrm{Fix}}}}T\) has been chosen arbitrary, the first assumption in the continuous version of Opial Lemma is fulfilled.
We show in the following that \(\lim _{t\rightarrow +\infty }(T(x(t))-x(t))\) exists and it is a real number. This is immediate if we show that the function \(t\mapsto \frac{1}{2}\Vert T(x(t))-x(t)\Vert ^2\) is decreasing. According to Remark 1(b), the function \(t\mapsto T(x(t))\) is almost everywhere differentiable and \(\Vert \frac{d}{dt}T(x(t))\Vert \le \Vert \dot{x}(t)\Vert \) holds for almost all \(t\ge 0\). Moreover, by the first equation of (5) we have
hence \(\lim _{t\rightarrow + \infty }(T(x(t))-x(t))\) exists and is a real number.
-
(a)
Firstly, let us assume that \(\int _0^{+\infty }\lambda (t)(1-\lambda (t))dt=+\infty \). This immediately implies by (9) that \(\lim _{t\rightarrow +\infty }(T(x(t))-x(t))=0\), thus (ii) holds. Taking into account that \(\lambda \) is bounded, from (5) and (ii) we deduce (iii). For the last property of the theorem we need to verify the second assumption of the Opial Lemma. Let \(\overline{x}\in \mathcal{{H}}\) be a weak sequential cluster point of \(x\), that is, there exists a sequence \(t_n\rightarrow +\infty \) (as \(n\rightarrow +\infty \)) such that \((x(t_n))_{n\in \mathbb {N}}\) converges weakly to \(\overline{x}\). Applying Lemma 5 and (ii) we obtain \(\overline{x}\in {{\mathrm{\mathrm{Fix}}}}T\) and the conclusion follows.
-
(b)
We suppose now that \(\inf _{t\ge 0}\lambda (t)>0\). From the first relation of (5) and (i) we easily deduce that \(Tx-x\in L^2([0,+\infty ),\mathcal{{H}})\), hence the function \(t\mapsto \frac{1}{2}\Vert T(x(t))-x(t)\Vert ^2\) belongs to \(L^1([0,+\infty ))\). Since \(\frac{d}{dt}\left( \frac{1}{2}\Vert T(x(t))-x(t)\Vert ^2\right) \le 0\) for almost all \(t\ge 0\), we obtain by applying Lemma 3 that \(\lim _{t\rightarrow +\infty }\Vert T(x(t))-x(t)\Vert ^2=0\), thus (ii) holds. The rest of the proof can be done in the lines of case (a) considered above. \(\square \)
Remark 7
Notice that the function \(\lambda _1(t)=\frac{1}{t+1}\), for all \(t\ge 0\), verifies the condition \(\int _0^{+\infty }\lambda _1(t)(1-\lambda _1(t))dt=+\infty \), while \(\inf _{t\ge 0}\lambda _1(t)>0\) is not fulfilled. On the other hand, the function \(\lambda _2(t)=1\), for all \(t\ge 0\), verifies the condition \(\inf _{t\ge 0}\lambda _2(t)>0\), while \(\int _0^{+\infty }\lambda _2(t)(1-\lambda _2(t))dt=+\infty \) fails. This shows that the two assumptions on \(\lambda \) under which the conclusions of Theorem (6) are valid are independent.
Remark 8
The explicit discretization of (5) with respect to the time variable \(t\), with step size \(h_n>0\), yields for an initial point \(x_0\) the following iterative scheme:
By taking \(h_n=1\) this becomes
which is the classical Krasnosel’skiĭ–Mann algorithm for finding the set of fixed points of the nonexpansive operator \(T\) (see [7, Theorem 5.14]). Let us mention that the convergence of (10) is guaranteed under the condition \(\sum _{n \in \mathbb {N}} \lambda _n(1-\lambda _n)=+\infty \). Notice that in case \(\lambda _n=1\) for all \(n \in \mathbb {N}\) and for an initial point \(x_0\) different from \(0\), the convergence of (10) can fail, as it happens for instance for the operator \(T=-{{\mathrm{\mathrm{Id}}}}\). In contrast to this, as pointed out in Theorem 6, the dynamical system (5) has a strong global solution and the convergence of the trajectory is guaranteed also in case \(\lambda (t)=1\) for all \(t\ge 0\).
An immediate consequence of Theorem 6 is the following corollary, where we consider dynamical systems involving averaged operators. Let \(\alpha \in (0,1)\) be fixed. We say that \(R:\mathcal{{H}}\rightarrow \mathcal{{H}}\) is \(\alpha -averaged\) if there exists a nonexpansive operator \(T:\mathcal{{H}}\rightarrow \mathcal{{H}}\) such that \(R=(1-\alpha ){{\mathrm{\mathrm{Id}}}}+\alpha T\). For \(\alpha =\frac{1}{2}\) we obtain as an important representative of this class the firmly nonexpansive operators. For properties and other insides concerning these families of operators we refer to [7].
Corollary 9
Let \(\alpha \in (0,1)\), \(R:\mathcal{{H}}\rightarrow \mathcal{{H}}\) be \(\alpha \)-averaged such that \({{\mathrm{\mathrm{Fix}}}}R\ne \emptyset \), \(\lambda :[0,+\infty )\rightarrow [0,1/\alpha ]\) a Lebesgue measurable function and \(x_0\in \mathcal{{H}}\). Suppose that one of the following conditions is fulfilled:
Let \(x:[0,+\infty )\rightarrow \mathcal{{H}}\) be the unique strong global solution of the dynamical system
Then the following statements are true:
-
(i)
the trajectory \(x\) is bounded and \(\int _0^{+\infty }\Vert \dot{x}(t)\Vert ^2dt<+\infty \);
-
(ii)
\(\lim _{t\rightarrow +\infty }(R(x(t))-x(t))=0\);
-
(iii)
\(\lim _{t\rightarrow +\infty }\dot{x}(t)=0\);
-
(iv)
\(x(t)\) converges weakly to a point in \({{\mathrm{\mathrm{Fix}}}}R\), as \(t\rightarrow +\infty \).
Proof
Since \(R\) is \(\alpha \)-averaged, there exists a nonexpansive operator \(T:\mathcal{{H}}\rightarrow \mathcal{{H}}\) such that \(R=(1-\alpha ){{\mathrm{\mathrm{Id}}}}+\alpha T\). The conclusion follows by taking into account that (11) is equivalent to
and \({{\mathrm{\mathrm{Fix}}}}R={{\mathrm{\mathrm{Fix}}}}T\). \(\square \)
In the following we investigate the convergence rate of the trajectories of the dynamical system (5). This will be done in terms of the fixed point residual function \(t\mapsto \Vert Tx(t)-x(t)\Vert \) and of \(t\mapsto \Vert \dot{x}(t)\Vert \). Notice that convergence rates for the discrete iteratively generated algorithm (10) have been investigated in [15, 16, 18].
Theorem 10
Let \(T:\mathcal{{H}}\rightarrow \mathcal{{H}}\) be a nonexpansive mapping such that \({{\mathrm{\mathrm{Fix}}}}T\ne \emptyset \), \(\lambda :[0,+\infty )\rightarrow [0,1]\) a Lebesgue measurable function and \(x_0\in \mathcal{{H}}\). Suppose that
Let \(x:[0,+\infty )\rightarrow \mathcal{{H}}\) be the unique strong global solution of (5). Then for all \(t> 0\) we have
where \(\underline{\tau }=\inf _{t\ge 0}\lambda (t)(1-\lambda (t))>0\).
Proof
Take an arbitrary \(y\in {{\mathrm{\mathrm{Fix}}}}T\) and \(t>0\). From (8) we have for all \(s\ge 0\):
By integrating we obtain
We have seen in the proof of Theorem 6 that \(t\mapsto \frac{1}{2}\Vert T(x(t))-x(t)\Vert ^2\) is decreasing, thus the last inequality yields
Since this inequality holds for an arbitrary \(y\in {{\mathrm{\mathrm{Fix}}}}T\), we get for all \(t\ge 0:\)
By taking also into account (5), the conclusion follows. \(\square \)
Next we show that the convergence rates of fixed point residual function \(t\mapsto \Vert Tx(t)-x(t)\Vert \) and of \(t\mapsto \Vert \dot{x}(t)\Vert \) can be improved to \(o\left( \frac{1}{\sqrt{t}}\right) \).
Theorem 11
Let \(T:\mathcal{{H}}\rightarrow \mathcal{{H}}\) be a nonexpansive mapping such that \({{\mathrm{\mathrm{Fix}}}}T\ne \emptyset \), \(\lambda :[0,+\infty )\rightarrow [0,1]\) a Lebesgue measurable function and \(x_0\in \mathcal{{H}}\). Suppose that
Let \(x:[0,+\infty )\rightarrow \mathcal{{H}}\) be the unique strong global solution of (5). Then for all \(t\ge 0\) we have
where \(\underline{\tau }=\inf _{t\ge 0}\lambda (t)(1-\lambda (t))>0\) and \(\lim _{t\rightarrow +\infty }\int _{t/2}^t\lambda (s)(1-\lambda (s))\Vert T(x(s))-x(s)\Vert ^2 ds=0\).
Proof
Define the function \(f:[0,+\infty )\rightarrow [0,+\infty )\),
According to (9) we have that \(\lim _{t\rightarrow +\infty }f(t)\in \mathbb {R}\).
Since \(t\mapsto \frac{1}{2}\Vert T(x(t))-x(t)\Vert ^2\) is decreasing (see the proof of Theorem 6), we have for all \(t\ge 0:\)
Taking into account the definition of \(\underline{\tau }\), we easily derive
and the conclusion follows by using again (5). \(\square \)
The rest of the section is dedicated to the formulation and investigation of a continuous version of the forward–backward algorithm. For readers convenience let us recall some standard notions and results in monotone operator theory which will be used in the following (see also [7, 9, 21–23]). For an arbitrary set-valued operator \(A:\mathcal{{H}}\rightrightarrows \mathcal{{H}}\) we denote by \({{\mathrm{\mathrm{Gr}}}}A=\{(x,u)\in \mathcal{{H}}\times \mathcal{{H}}:u\in Ax\}\) its graph. We use also the notation \({{\mathrm{\mathrm{zer}}}}A=\{x\in \mathcal{{H}}:0\in Ax\}\) for the set of zeros of \(A\). We say that \(A\) is monotone, if \(\langle x-y,u-v\rangle \ge 0\) for all \((x,u),(y,v)\in {{\mathrm{\mathrm{Gr}}}}A\). A monotone operator \(A\) is said to be maximally monotone, if there exists no proper monotone extension of the graph of \(A\) on \(\mathcal{{H}}\times \mathcal{{H}}\). The resolvent of \(A\), \(J_A:\mathcal{{H}} \rightrightarrows \mathcal{{H}}\), is defined by \(J_A=({{\mathrm{\mathrm{Id}}}}_{\mathcal{{H}}}+A)^{-1}\), where \({{\mathrm{\mathrm{Id}}}}_{\mathcal{{H}}} :\mathcal{{H}} \rightarrow \mathcal{{H}}, {{\mathrm{\mathrm{Id}}}}_\mathcal{{H}}(x) = x\) for all \(x \in \mathcal{{H}}\), is the identity operator on \(\mathcal{{H}}\). Moreover, if \(A\) is maximally monotone, then \(J_A:\mathcal{{H}} \rightarrow \mathcal{{H}}\) is single-valued and maximally monotone (see [7, Proposition 23.7 and Corollary 23.10]). For an arbitrary \(\gamma >0\) we have (see [7, Proposition 23.2])
The operator \(A\) is said to be uniformly monotone if there exists an increasing function \(\phi _A : [0,+\infty ) \rightarrow [0,+\infty ]\) that vanishes only at \(0\), and \(\langle x-y,u-v \rangle \ge \phi _A \left( \Vert x-y \Vert \right) \) for every \((x,u)\in {{\mathrm{\mathrm{Gr}}}}A\) and \((y,v) \in {{\mathrm{\mathrm{Gr}}}}A\). A well-known class of operators fulfilling this property is the one of the strongly monotone operators. Let \(\gamma >0\) be arbitrary. We say that \(A\) is \(\gamma \)-strongly monotone, if \(\langle x-y,u-v\rangle \ge \gamma \Vert x-y\Vert ^2\) for all \((x,u),(y,v)\in {{\mathrm{\mathrm{Gr}}}}A\). We consider also the class of cocoercive operators: \(B:\mathcal{{H}}\rightarrow \mathcal{{H}}\) is \(\gamma \)-cocoercive, if \(\langle x-y,Bx-By\rangle \ge \gamma \Vert Bx-By\Vert ^2\) for all \(x,y\in \mathcal{{H}}\).
Theorem 12
Let \(A:\mathcal{{H}}\rightrightarrows \mathcal{{H}}\) be a maximally monotone operator, \(\beta >0\) and \(B:\mathcal{{H}}\rightarrow \mathcal{{H}}\) be \(\beta \)-cocoercive such that \({{\mathrm{\mathrm{zer}}}}(A+B)\ne \emptyset \). Let \(\gamma \in (0,2\beta )\) and set \(\delta =\min \{1,\beta /\gamma \}+1/2\). Let \(\lambda :[0,+\infty )\rightarrow [0,\delta ]\) be a Lebesgue measurable function and \(x_0\in \mathcal{{H}}\). Suppose that one if the following conditions is fulfilled:
Let \(x:[0,+\infty )\rightarrow \mathcal{{H}}\) be the unique strong global solution of
Then the following statements are true:
-
(i)
the trajectory \(x\) is bounded and \(\int _0^{+\infty }\Vert \dot{x}(t)\Vert ^2dt<+\infty \);
-
(ii)
\(\lim _{t\rightarrow +\infty }\left[ J_{\gamma A}\Big (x(t)-\gamma B(x(t))\Big )-x(t)\right] =0\);
-
(iii)
\(\lim _{t\rightarrow +\infty }\dot{x}(t)=0\);
-
(iv)
\(x(t)\) converges weakly to a point in \({{\mathrm{\mathrm{zer}}}}(A+B)\), as \(t\rightarrow +\infty \).
Suppose that \(\inf _{t\ge 0}\lambda (t)>0\). Then the following hold:
-
(v)
if \(y\in {{\mathrm{\mathrm{zer}}}}(A+B)\), then \(\lim _{t\rightarrow \infty }B(x(t))=By\) and \(B\) is constant on \({{\mathrm{\mathrm{zer}}}}(A+B)\);
-
(vi)
if \(A\) or \(B\) is uniformly monotone, then \(x(t)\) converges strongly to the unique point in \({{\mathrm{\mathrm{zer}}}}(A+B)\), as \(t\rightarrow \infty \).
Proof
It is immediate that the dynamical system (14) can be written in the form
where \(T=J_{\gamma A}\circ ({{\mathrm{\mathrm{Id}}}}-\gamma B).\) According to [7, Corollary 23.8 and Remark 4.24(iii)], \(J_{\gamma A}\) is \(1/2\)-cocoercive. Moreover, by [7, Proposition 4.33], \({{\mathrm{\mathrm{Id}}}}-\gamma B\) is \(\gamma /(2\beta )\)-averaged. Combining this with [7, Proposition 4.32], we derive that \(T\) is \(1/\delta \)-averaged. The statements (i)-(iv) follow now from Corollary 9 by noticing that \({{\mathrm{\mathrm{Fix}}}}T={{\mathrm{\mathrm{zer}}}}(A+B)\), see [7, Proposition 25.1(iv)].
We suppose in the following that \(\inf _{t\ge 0}\lambda (t)>0\).
(v) The fact that \(B\) is constant on \({{\mathrm{\mathrm{zer}}}}(A+B)\) follows from the cocoercivity of \(B\) and the monotonicity of \(A\). A proof of this statement when \(A\) is the subdifferential of a proper, convex and lower semicontinuous function is given in [1, Lema 1.7].
We use the following inequality:
which follows from the nonexpansiveness property of the resolvent and the cocoercivity of \(B\):
Take an arbitrary \(y\in {{\mathrm{\mathrm{zer}}}}(A+B)={{\mathrm{\mathrm{Fix}}}}T\). From the first part of the proof of Theorem 6 and (16) we get for all \(t\ge 0\)
Taking into account that \(\inf _{t\ge 0}\lambda (t)>0\) and \(0<\gamma <2\beta \), by integrating the above inequality we obtain
Since \(B\) is \(1/\beta \)-Lipschitz (this follows from the \(\beta \)-cocoercivity of \(B\) by applying the Cauchy-Schwarz inequality) and \(t\mapsto \Vert \dot{x}(t)\Vert \in L^2([0,+\infty ))\), from Remark 1(b) we derive that \(t\mapsto \frac{d}{dt} B(x(t))\in L^2([0,+\infty ),\mathcal{{H}})\). From the Cauchy-Schwarz inequality we obtain for all \(t\ge 0\)
Combining these considerations with Lemma 3, we conclude that \(B(x(t))\) converges strongly to \(By\), as \(t\rightarrow +\infty \).
(vi) Suppose that \(A\) is uniformly monotone and let \(y\) be the unique point in \({{\mathrm{\mathrm{zer}}}}(A+B)\). According to (14) and the definition of the resolvent, we have
From \(-By\in Ay\) we get for all \(t \ge 0\) the inequality
where \(\phi _A:[0,+\infty )\rightarrow [0,+\infty ]\) is increasing and vanishes only at \(0\).
The monotonicity of \(B\) implies
The last inequality implies, by taking into consideration (iii), (iv) and (v), that
The properties of the function \(\phi _A\) allow to conclude that \(\frac{1}{\lambda (t)}\dot{x}(t)+x(t)-y\) converges strongly to \(0\), as \(t\rightarrow + \infty \), hence from (iii) we obtain the conclusion.
Finally, suppose that \(B\) is uniformly monotone, with corresponding function \(\phi _B:[0,+\infty ) \rightarrow [0,+\infty ]\), which is increasing and vanishes only at \(0\). The conclusion follows by taking in the inequality
the limit as \(t\rightarrow + \infty \) and by using (i) and (v). \(\square \)
Remark 13
Let us mention that in case \(A=\partial \Phi \), where \(\Phi :\mathcal{{H}}\rightarrow \mathbb {R}\cup \{+\infty \}\) is a proper, convex and lower semicontinuous function defined on a real Hilbert space \(\mathcal{{H}}\), and for \(\lambda (t)=1\) for all \(t\ge 0\), the dynamical system (14) becomes (3), which has been studied in [1]. Notice that the weak convergence of (3) is obtained in [1, Theorem 4.2] for a constant step-size \(\gamma \in (0,4\beta )\).
Remark 14
The explicit discretization of (14) with respect to the time variable \(t\), with step size \(h_n>0\) and initial point \(x_0\), yields the following iterative scheme:
For \(h_n=1\) this becomes
which is the classical forward–backward algorithm for finding the set of zeros of \(A+B\) (see [7, Theorem 25.8]). Let us mention that the convergence of (17) is guaranteed under the condition \(\sum _{n \in \mathbb {N}} \lambda _n(\delta -\lambda _n)=+\infty \).
Remark 15
As mentioned in the introduction, the Douglas–Rachford algorithm for finding the set of zeros of the sum of two maximally monotone operators follows from the discrete version of the Krasnosel’skiĭ–Mann numerical scheme, see [7]. Following the approach presented above, one can formulate a dynamical system of Douglas–Rachford-type, the existence and weak convergence of the trajectories being a consequence of the main results presented here. The same can be done for other iterative schemes which have their origins in the discrete Krasnosel’skiĭ–Mann algorithm, like are the generalized forward–backward splitting algorithm in [20] and the forward-Douglas–Rachford splitting algorithm in [13].
4 An Alternative Approach Relying on Time Rescaling Arguments
The content of this section has as starting point a comment made by H. Attouch on a preliminary version of this manuscript. We will show, by using time rescaling arguments, that the convergence behavior of the dynamical system (5) can be derived from the one of an autonomous dynamical system governed by a cocoercive operator. Let us recall first the following classical result, which can be deduced for example from [1, Theorem 3.1] by taking \(\Phi =0\) as well as from Theorem 12 by choosing \(Ax=0\) for all \(x\in \mathcal {H}\) and \(\lambda (t)=1\) for all \(t\ge 0\).
Theorem 16
Let \(B:\mathcal {H}\rightarrow \mathcal {H}\) be a cocoercive operator such that \({{\mathrm{\mathrm{zer}}}}B\ne \emptyset \) and \(w_0\in \mathcal{{H}}\). Let \(w:[0,+\infty )\rightarrow \mathcal{{H}}\) be the unique strong global solution of the dynamical system
Then the following statements are true:
-
(a)
the trajectory \(w\) is bounded and \(\int _0^{+\infty }\Vert \dot{w}(t)\Vert ^2dt<+\infty \);
-
(b)
\(w(t)\) converges weakly to a point in \({{\mathrm{\mathrm{zer}}}}B\), as \(t\rightarrow +\infty \);
-
(c)
\(B(w(t))\) converges strongly to \(0\), as \(t\rightarrow +\infty \).
Let us consider again the dynamical system (5), written as
We recall that \(T\) is nonexpansive such that \({{\mathrm{\mathrm{Fix}}}}T\ne \emptyset \) and \(\lambda :[0,\infty )\rightarrow [0,1]\) is Lebesgue measurable. By using a time rescaling argument as in [4, Lemma 4.1], we can prove a connection between the dynamical system (5) and the system
In the following we suppose that
Notice that the considerations which we make in the following remain valid also when one requires for the function \(\lambda \) an arbitrary positive upper bound. However, we choose as upper bound \(1\) in order to remain in the setting presented in the previous section.
Suppose that we have a solution \(w\) of (19). By defining the function \(T_1:[0,+\infty )\rightarrow [0,+\infty )\), \(T_1(t)=\int _0^t\lambda (s)ds\), one can easily see that \(w\circ T_1\) is a solution of (5).
Conversely, if \(x\) is a solution of (5), then \(x\circ T_2\) is a solution of (19), where \(T_2:[0,+\infty )\rightarrow [0,+\infty )\) is defined for every \(t \ge 0\) implicitly as \(\int _0^{T_2(t)}\lambda (s)ds=t\) (this is possible due to the properties of the the function \(\lambda \)).
In the arguments above we used that
and
Further, since \(B:={{\mathrm{\mathrm{Id}}}}-T\) is \(1/2\)-cocoercive (this follows from the nonexpansiveness of \(T\)), for the dynamical system (19) one can apply the convergence results presented in Theorem 16. We would also like to notice that the existence of a strong global solution of (5) follows from the corresponding result for (19), while for the uniqueness property we have to make use of the considerations at the end of Sect. 2.
In the following we deduce the convergence statements of Theorem 6 from the ones of Theorem 16 by using the time rescaling arguments presented above.
Let \(x\) be the unique strong global solution of (5). Due to the uniqueness of the solutions of (5) and (19), we have \(x=w\circ T_1\), where \(w\) is the unique strong global solution of (19).
-
(i)
From Theorem 16(a) we know that \(w\) is bounded, hence \(x\) is bounded, too. We have
$$\begin{aligned} \int _0^{+\infty }\Vert \dot{x}(s)\Vert ^2ds= & {} \lim _{t\rightarrow +\infty }\int _0^t \Vert w'(T_1(s))\Vert ^2(\lambda (s))^2ds\le \lim _{t\rightarrow +\infty }\int _0^t \Vert w'(T_1(s))\Vert ^2\lambda (s)ds\\= & {} \lim _{t\rightarrow +\infty }\int _0^{T_1(t)} \Vert w'(u)\Vert ^2du<+\infty , \end{aligned}$$where we used Theorem 16(a) and the change of variables \(T_1(s)=u\).
-
(ii)
This statement follows from Theorem 16(c).
-
(iii)
Is a direct consequence of the boundedness of \(\lambda \), (ii) and of the way the dynamic is defined.
-
(iv)
From Theorem 16(b) it follows that \(x(t)=w(T_1(t))\) converges weakly to a point in \({{\mathrm{\mathrm{zer}}}}B={{\mathrm{\mathrm{Fix}}}}T\) as \(t \rightarrow +\infty \).
Remark 17
In the light of the above considerations it follows that the conclusion of Theorem 6 remains valid also when assuming that \(\int _0^{+\infty }\lambda (t)dt=+\infty \), which is a weaker condition than asking that \(\int _0^{+\infty }\lambda (t)(1-\lambda (t))dt=+\infty \) or \(\inf _{t \ge 0} \lambda (t) >0\). A similar statement applies to Theorem 12, too. Notice also that the assumption that \(\lambda \) takes values in \([0,1]\), being strictly bounded away from the endpoints of this interval, was essential, in combination to the considerations made in the proof of Theorem 6, for deriving convergence rates for the trajectories of (5). Finally, let us mention that, as pointed out in Remark 8, the assumption \(\int _0^{+\infty }\lambda (t)(1-\lambda (t))dt=+\infty \) has a natural counterpart in the discrete case which guarantees convergence for the sequence of generated iterates, while this is not the case for the other two conditions on \(\lambda \) considered in this paper.
References
Abbas, B., Attouch, H.: Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator. Optimization (2014). doi:10.1080/02331934.2014.971412
Abbas, B., Attouch, H., Svaiter, B.F.: Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces. J. Optim. Theory Appl. 161(2), 331–360 (2014)
Antipin, A.S.: Minimization of convex functions on convex sets by means of differential equations. (Russian) Differentsial’nye Uravneniya 30(9), 1475–1486, 1994; translation in Differential Equations 30(9), 1365–1375 (1994)
Attouch, H., Czarnecki, M.-O.: Asymptotic behavior of coupled dynamical systems with multiscale aspects. J. Differ. Equ. 248(6), 1315–1344 (2010)
Attouch, H., Svaiter, B.F.: A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control Optim. 49(2), 574–598 (2011)
Baillon, J.B., Brézis, H.: Une remarque sur le comportement asymptotique des semigroupes non linéaires. Houst. J. Math. 2(1), 5–7 (1976)
Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, CMS Books in Mathematics. Springer, New York (2011)
Bolte, J.: Continuous gradient projection method in Hilbert spaces. J. Optim. Theory Appl. 119(2), 235–259 (2003)
Borwein, J.M., Vanderwerff, J.D.: Convex Functions: Constructions, Characterizations and Counterexamples. Cambridge University Press, Cambridge (2010)
Boţ, R.I., Csetnek, E.R., Heinrich, A.: A primal-dual splitting algorithm for finding zeros of sums of maximally monotone operators. SIAM J. Optim. 23(4), 2011–2036 (2013)
Boţ, R.I., Csetnek, E.R., Heinrich, A., Hendrich, C.: On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems. Mathematical Programming. doi:10.1007/s10107-014-0766-0
Brézis, H.: Opérateurs Maximaux Monotones et Semi-Groupes de Contractions Dans les Espaces de Hilbert. North-Holland Mathematics Studies No. 5, Notas de Matemática, vol. 50. North-Holland/Elsevier, New York (1973)
Briceño-Arias, L.M.: Forward-Douglas–Rachford splitting and forward-partial inverse method for solving monotone inclusions. Optimization (2013). doi:10.1080/02331934.2013.855210
Bruck Jr, R.E.: Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. J. Funct. Anal. 18, 15–26 (1975)
Corman, E., Yuan, X.: A Generalized proximal point algorithm and its convergence rate. SIAM J. Optim. 24(4), 1614–1638 (2014)
Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes, arXiv:1406.4834 (2014)
Haraux, A.: Systèmes Dynamiques Dissipatifs et Applications, Recherches en Mathé- matiques Appliquées 17. Masson, Paris (1991)
Liang, J., Fadili, J., Peyré, G.: Convergence rates with inexact nonexpansive operators, arXiv:1404.4837 (2014)
Peypouquet, J., Sorin, S.: Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time. J. Convex Anal. 17(3–4), 1113–1163 (2010)
Raguet, H., Fadili, J., Peyré, G.: A generalized forward-backward splitting. SIAM J. Imaging Sci. 6(3), 1199–1226 (2013)
Rockafellar, R.T.: On the maximal monotonicity of subdifferential mappings. Pac. J. Math. 33(1), 209–216 (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877–898 (1976)
Simons, S.: From Hahn-Banach to Monotonicity. Springer, Berlin (2008)
Sontag, E.D.: Mathematical Control Theory. Deterministic Finite-Dimensional Systems. Texts in Applied Mathematics 6, 2nd edn. Springer, New York (1998)
Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)
Acknowledgments
We are thankful to H. Attouch for bringing into our attention the time rescaling arguments which led to the results presented in the last section. Radu Ioan Boţ and Ernö Robert Csetnek: research partially supported by DFG (German Research Foundation), Project BO 2516/4-1.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Boţ, R.I., Csetnek, E.R. A Dynamical System Associated with the Fixed Points Set of a Nonexpansive Operator. J Dyn Diff Equat 29, 155–168 (2017). https://doi.org/10.1007/s10884-015-9438-x
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10884-015-9438-x
Keywords
- Dynamical systems
- Lyapunov analysis
- Krasnosel’skiĭ–Mann algorithm
- Monotone inclusions
- Forward–backward algorithm