Explicit Convergence Rate of The Proximal Point Algorithm under R-Continuity

In what follows, $\mathbb{X}$ and $\mathbb{Y}$ are real Banach spaces whose norms are designated by $\|\cdot\|$. We use the notation $\mathbb{B}(x,r)$ to denote the closed ball with center $x$ and radius $r>0$ and by $\mathbb{B}$ the closed unit ball which consists of the elements of norm less than or equal to $1$. By a set-valued mapping $\mathcal{A}:\mathbb{X}\rightrightarrows\mathbb{Y}$, we mean a mapping which assigns to each $x\in\mathbb{X}$ a subset $\mathcal{A}(x)$ (possibly empty) of $\mathbb{Y}$. The domain, the range and the graph of $\mathcal{A}$ are defined respectively by

$${\rm dom}\,\mathcal{A}=\{x\in\mathbb{X}:\mathcal{A}(x)\neq\emptyset\},\;\;{\rm rge}\,\mathcal{A}=\cup_{x\in\mathbb{X}}\mathcal{A}(x),$$

and

$${\rm Graph\,}{\mathcal{A}=\{(x,y)\in\mathbb{X}\times\mathbb{Y}\;\text{such that}\;y\in\mathcal{A}(x})\}.$$

As usual we denote by $\mathcal{A}^{-1}:\mathbb{Y}\rightrightarrows\mathbb{X}$ the inverse of $\mathcal{A}$ defined by

$$x\in\mathcal{A}^{-1}(y)\;\iff\;y\in\mathcal{A}(x).$$

The notion $\mathbf{d}(x,\mathbf{S})$ stands for the distance from a point $x\in\mathbb{X}$ to a subset $\mathbf{S}\subset\mathbb{X}$:

$$\mathbf{d}(x,\mathbf{S}):=\,\inf_{y\in\mathbf{S}}\|x-y\|.$$

Given a set-valued mapping $\mathcal{A}:\mathcal{H}\rightrightarrows\mathcal{H}$ defined in a Hilbert space $\mathcal{H}$, and inspired by Rockafellar’s paper [25], recently B. K. Le [17] introduced the notion of R-continuity for studying the convergence rate of the Tikhonov regularization of the inclusion

$$0\in\mathcal{A}(x).$$

(1)

In [17], it was proved that R-continuity is a useful tool to analyze the convergence of $\mathbf{D}\mathbf{C}\mathbf{A}$ (Difference of Convex Algorithm) and can explain why $\mathbf{D}\mathbf{C}\mathbf{A}$ is effective in approximating solutions for a broad class of functions. In recent decades, there has been a surge of interest to study variational inclusions such as (1) since they modelise a variety of important systems. This is the case especially in optimization when the condition for critical points is considered (the Fermat rule). Another connection with the inclusion (1) arises in PDEs and is well discussed in the books [6, 9]. The fact that the solution set $\mathbf{S}:={\mathcal{A}}^{-1}(0)$ of (1) involves the inverse operator of $\mathcal{A}$, conducts naturally to study the continuity of $\mathcal{{A}}^{-1}$ at zero. According to [17], the mapping $\mathcal{A}:\mathcal{H}\rightrightarrows\mathcal{H}$ is said to be R-continuous at zero if there exist a radius $\sigma>0$ and a non-decreasing modulus function $\rho:\mathbb{R}^{+}\to\mathbb{R}^{+}$ satisfying $\lim_{r\to 0^{+}}\rho(r)=\rho(0)=0$ such that

$$\mathcal{A}(x)\subset\mathcal{A}(0)+\rho(\|x\|)\mathbb{B},\;\text{ for every}\;x\in\sigma\mathbb{B}.$$

(2)

Denoting by $\mathbf{e}\mathbf{x}(C,D):=\sup_{x\in C}\mathbf{d}(x,D)$, the excess of the set $C$ over the set $D$, with the convention that $\mathbf{e}\mathbf{x}(\emptyset,D)=0$ when $D$ is nonempty and $\mathbf{e}\mathbf{x}(C,\emptyset)=+\infty$ for any $C$, (2) is equivalent to saying that

$$\mathbf{e}\mathbf{x}(\mathcal{A}(x),\mathcal{A}(0))\leq\rho(\|x\|)\;\text{whenever}\;\|x\|\leq\sigma.$$

(3)

When $\rho(r):=\,Lr$ for some $L>0$, (3) is changed into

$$\mathbf{e}\mathbf{x}(\mathcal{A}(x),\mathcal{A}(0))\leq L\|x\|\;\text{whenever}\;\|x\|\leq\sigma.$$

(4)

In this case, $\mathcal{A}$ is referred to as R-Lipschitz continuous at zero or equivalently upper Lipschitz at zero in the sense of Robinson [24] or outer Lipschitz continuous at zero [5]. In addition, if $\mathcal{A}(0)$ is a singleton, R-Lipschitz continuity at zero of $\mathcal{A}$ is exactly the Lipschitz continuity at zero introduced by R. T. Rockafellar in [25] who considered Lipschitz continuity at zero of set-valued mappings as an important tool in optimization. Rockafellar demonstrated the linear convergence rate of the proximal point algorithm after a finite number of iterations from any starting point $x_{0}$. However the requirement that the solution set is a singleton is often quite restrictive in practice. Thus, allowing the solution set $\mathbf{S}$ to be set-valued and and not requiring the continuity modulus function $\rho$ to be Lipschitz continuous makes R-continuity a competitive alternative. It provides a viable option alongside other fundamental concepts such as metric regularity, metric subregularity or calmness in the study of sensitivity analysis as well as in establishing the convergence rate of algorithms. Note that R-continuity can be also extended to Banach spaces. In order to compare these regularity concepts, let us recall the definitions of metric regularity, metric subregularity and calmness (see, e.g., [14, 15, 12, 30, 31, 10, 16, 26, 11, 21, 22, 28] and the references therein). Given $\mathcal{A}:\mathbb{X}\rightrightarrows\mathbb{Y}$ where $\mathbb{X},\mathbb{Y}$ are real Banach spaces and $(\bar{x},\bar{y})\in{\rm Graph\,}\mathcal{A}$, one says that $\mathcal{A}$ is metrically regular near $(\bar{x},\bar{y})$ if a linear error bound holds

$$\mathbf{d}(x,\mathcal{A}^{-1}(y))\leq\kappa\mathbf{d}(y,\mathcal{A}(x))$$

(5)

for some $\kappa>0$ and for all $(x,y)$ close to $(\bar{x},\bar{y})$. If (5) is satisfied for all $(x,y)\in\mathbb{X}\times\mathbb{Y}$, then $\mathcal{A}$ is termed globally metrically regular. When $(\bar{x},0)\in{\rm Graph\,}\,\mathcal{A}$, inequality (5) provides an estimate of how far is a point $x$ around $\bar{x}$ to the solution set $\mathcal{A}^{-1}(0)$. However, metric regularity can be too stringent as it requires the inequality (5) to hold in a neighborhood of $(\bar{x},\bar{y})$. One says that $\mathcal{A}:\mathbb{X}\rightrightarrows\mathbb{Y}$ is calm at $(\bar{x},\bar{y})\in{\rm Graph\,}\mathcal{A}$ if there exist $\kappa>0,\epsilon>0,\sigma>0$ such that

$$\mathcal{A}({x})\cap\mathbb{B}(\bar{y},\epsilon)\subset\mathcal{A}(\bar{x})+\kappa\|x-\bar{x}\|\mathbb{B},\;\;\;\text{for all}\;x\in\mathbb{B}(\bar{x},\sigma),$$

(6)

or equivalently

$$\mathbf{e}\mathbf{x}(\mathcal{A}(x)\cap\mathbb{B}(\bar{y},\epsilon),\mathcal{A}(\bar{x}))\leq\kappa\|x-\bar{x}\|,\;\;{\rm for\;all}\;x\in\mathbb{B}(\bar{x},\sigma).$$

(7)

Note that when the set $\mathcal{A}(x)\cap\mathbb{B}(\bar{y},\epsilon)$ is empty the inequality (7) is always satisfied. When $\bar{x}=0$, (7) becomes

$$\mathbf{e}\mathbf{x}(\mathcal{A}(x)\cap\mathbb{B}(\bar{y},\epsilon),\mathcal{A}(0))\leq\kappa\|x\|,\;\;{\rm whenever}\;\|x\|\leq\sigma.$$

(8)

Another well-known regularity concept is metric subregularity. The set-valued mapping $\mathcal{A}:\mathbb{X}\rightrightarrows\mathbb{Y}$ is called metrically subregular at $(\bar{x},0)\in{\rm Graph\,}\,\mathcal{A}$ if there exists a constant $\kappa>0$ such that

$$\mathbf{d}(x,\mathcal{A}^{-1}(0))\leq\kappa\mathbf{d}(0,\mathcal{A}(x)),\;\;\text{ for all }\;x\;\text{close to}\;\bar{x}.$$

(9)

It is known (see, e.g., [14, Proposition 2.62]) that metric subregularity of $\mathcal{A}$ at $(\bar{x},0)$ is equivalent to calmness of $\mathcal{A}^{-1}$ at $(0,\bar{x})$. From (3) and (8), let us observe that if $\mathcal{A}$ is R-Lipschitz continuous at 0 then it is calm at $(0,\bar{y})$ for any $\bar{y}\in\mathcal{A}(0)$. While metric regularity is too strong, calmness is relatively weak to deduce useful properties. For example when the set $\mathcal{A}(x)\cap\mathbb{B}(\bar{y},\epsilon)$ is empty for some $x\in\epsilon\mathbb{B}$, no information can be deduced. In addition, with complicated $\mathcal{A}$, we do not know a specific $\bar{y}$ and have to use computers to find an approximation of an element of $\mathcal{A}(0)$. The first advantage of R-continuity is that it is unnecessary to know a prior solution $\bar{y}$ in advance. Furthermore in (2), since $x$ is small, for each $y\in\mathcal{A}(x)$, there exists some $\tilde{y}\in\mathcal{A}(0)$ close to $y$. This fact is meaningful since it is difficult to ensure $y$ to be in the vicinity of $\bar{y}$, which is unknown. Secondly, R-continuity is straightforward and always guarantees the system consistency in Hoffman’s sense [13]. Indeed, Theorem 7 establishes that under the R-continuity of $\mathcal{A}^{-1}$ at zero, the inclusion (1) is consistent, i.e., if $y_{\sigma}$ has a small norm and satisfies $y_{\sigma}\in\mathcal{A}(x_{\sigma})$, then we can find a solution $\bar{x}\in\mathbf{S}$ such that $x_{\sigma}$ is close to $\bar{x}$. Note that to guarantee the consistency property, metric subregularity or metric regularity must be satisfied globally. Thirdly, R-continuity does not require the property (2) to hold around a point belonging to the graph of the operator; it is easily verified for a broad class of set-valued mappings. In order to achieve the metric regularity at some point $(\bar{x},\bar{y})\in{\rm Graph\,}\mathcal{A}$, the celebrated Robinson-Ursescu Theorem [23, 29] requires for the operator $\mathcal{A}:\mathbb{X}\rightrightarrows\mathbb{Y}$ to have a closed and convex graph and also that $\bar{y}\in{\rm int}(\mathcal{A}(\mathbb{X}))$ (the interior of $\mathcal{A}(\mathbb{X}))$. R-continuity only necessitates that the graph of the operators be closed. Indeed, if the operator has a closed graph at zero and is locally compact at zero then it is R-continuous at zero (Theorem 5). Conversely, if the operator is R-continuous at zero and its value at zero is closed, then it has a closed graph at zero (Theorem 6). The condition for having its graph closed at zero is relatively mild. If an operator’s graph is closed, then it has a closed graph at zero as well. Furthermore, an operator has a closed graph if and only if its inverse has a closed graph. Closed graph operators are usually found in optimization when dealing with continuous single-valued mappings, maximally monotone operators (see, e.g., [8]), the sum of two closed graph operators where one of them is single-valued, the sum of two closed graph set-valued operators where one of them is locally compact (Proposition 3). The Sign function in ${\mathbb{R}}^{n}$, which equals to the convex subdifferential of the norm function, is a well-known example of an operator with compact range and is widely used in image processing, mechanical and electrical engineering (see, e.g., [2, 20]).

Finally, we demonstrate that R-continuity can be used to analyse the explicit convergence rate of the proximal point algorithm ($\mathbf{P}\mathbf{P}\mathbf{A}$) when applied to a maximally monotone operator $\mathcal{A}:\mathcal{H}\rightrightarrows\mathcal{H}$, where $\mathcal{H}$ is a Hilbert space. The $\mathbf{P}\mathbf{P}\mathbf{A}$, introduced by B. Martinet and further developed by Rockafellar, Bauschke and Combettes and others (see, e.g., [7, 18, 25]), is an essential tool in convex optimization if $\mathcal{A}$ is set-valued and lacks special structure. We show that if $\mathcal{A}^{-1}$ is globally R-Lipschitz continuous at zero (i.e., $\sigma=+\infty$), the convergence of the proximal point algorithm is linear from the beginning (Theorem 11). When considering the case where $\mathcal{A}=\partial f$, i.e. when $\mathcal{A}$ is the convex subdifferential of a proper lower semicontinuous extended real-valued convex function, not necessarily smooth $f:\mathcal{H}\to{\mathbb{R}}\cup\{+\infty\}$, if $\mathcal{A}^{-1}$ is only R-continuous, we obtain an explicit convergence rate of $\mathbf{P}\mathbf{P}\mathbf{A}$ based on the modulus function. If $(\partial f)^{-1}$ is R-Lipschitz continuous at zero, one has the linear convergence of the generated sequence $(x_{n})$ after some iterations (Theorem 14).

The paper is organized as follows. First we review the necessary material about R-continuity of set-valued mappings and maximally monotone operators in Section 2. Some key properties of R-continuity are established in Section 3. The analysis of the convergence rate of $\mathbf{P}\mathbf{P}\mathbf{A}$ under the R-continuity is presented in Section 4. The paper ends in Section 5 with some conclusions and perspectives.

In what follows, we extend the notion of R-continuity introduced in [17] from Hilbert spaces to Banach spaces, defined for any point in the domain of the operators. Let $\mathcal{A}:\mathbb{X}\rightrightarrows\mathbb{Y}$ be a set-valued mapping where $\mathbb{X},\mathbb{Y}$ are Banach spaces and ${\bar{x}}\in{\rm dom}\,\mathcal{A}$.

The following simple example shows that the metric regularity is strictly stronger than R-Lipschitz continuity. This important fact means that we still obtain the convergence rate of optimization algorithms if only R-Lipschitz continuity or even R-continuity holds (see, e.g., [17]).

A set-valued mapping $\mathcal{A}:\mathbb{X}\rightrightarrows\mathbb{Y}$ is called $\gamma$-coercive with modulus $\gamma>0$ if for all $x,y\in{\rm dom}\,\mathcal{A}$ and for all $\bar{x}\in\mathcal{A}(x)$, $\bar{y}\in\mathcal{A}(y)$, we have

$$\|\bar{x}-\bar{y}\|\geq\gamma\|x-y\|.$$

(12)

In order to simplify the writing we will use the notation: for all $x,y\in{\rm dom}\,\mathcal{A}$, we have

$$\|\mathcal{A}(x)-\mathcal{A}(y)\|\geq\gamma\|x-y\|,$$

to describe this property. It is easy to see that a $\gamma$-strongly monotone operator is $\gamma$-coercive. Another example is given by matrices with full column rank (see, e.g., [17]). Next we extend to a pair of set-valued mappings the notion of monotonicity of a pair of single-valued operators introduced in Hilbert spaces by Adly-Cojocaru-Le [4].

Note that when $\mathbb{Y}=\mathcal{H}$ is a Hilbert space, the monotonicity of $(\mathcal{B},\mathcal{C})$ is equivalent to

$$\langle\mathcal{B}(x)-\mathcal{B}(y),\mathcal{C}(x)-\mathcal{C}(y)\rangle\geq 0,\;\;\forall\;x,y\in\mathcal{H}.$$

In addition, we say $(\mathcal{B},\mathcal{C})$ is $\gamma$-strongly monotone $(\gamma>0)$ if

$$\langle\mathcal{B}(x)-\mathcal{B}(y),\mathcal{C}(x)-\mathcal{C}(y)\rangle\geq\gamma\|x-y\|^{2},\;\;\forall\;x,y\in\mathcal{H}.$$

First we show that the sum (and also the difference) of two R-continuous mappings is also R-continuous.

Next we show that R-continuity is satisfied for a large class of operators and has a closed connection with the closed graph property at zero.

Although R-continuity is straightforward, it always guarantees the consistency of the system in Hoffman’s sense [13].

In optimization, when we consider the inclusion $0\in\mathcal{A}(x)$, we want to know whether $\mathcal{A}^{-1}$ is R-continuous or even R-Lipschitz continuous. Here we provide some cases where the global R-Lipschitz continuity is satisfied. It is known that the inverse of any square matrix is globally R-Lipschitz continuous [17, Proposition 2.10]. Now we prove that the inverse of any matrix is globally R-Lipschitz continuous. Note that this result cannot be deduced from the Robinson-Ursescu Theorem. Finally we give some nontrivial nonlinear examples (see also Proposition 1 and [5, Theorem 7]).

Let $\mathcal{A}:\mathcal{H}\rightrightarrows\mathcal{H}$ be a maximally monotone operator with nonempty $\mathbf{S}:=\mathcal{A}^{-1}(0)$ where $\mathcal{H}$ is a Hilbert space. Let us recall that $\mathbf{P}\mathbf{P}\mathbf{A}$ generates for any starting point $x_{0}$, a sequence $(x_{n})$ defined by the rule:

$$x_{n+1}=\textbf{J}_{\gamma\mathcal{A}}(x_{n}),\;x_{0}\in\mathcal{H},$$

(16)

for some $\gamma>0$ where $\textbf{J}_{\gamma\mathcal{A}}(x):\,=(\mathbf{I}\mathbf{d}+\gamma\mathcal{A})^{-1}(x)$. $\mathbf{P}\mathbf{P}\mathbf{A}$ plays an important role in convex optimization if $\mathcal{A}$ is set-valued and has no special structure. The following result shows that the convergence rate of $\mathbf{P}\mathbf{P}\mathbf{A}$ is indeed linear if $\mathcal{A}^{-1}$ is R-Lipschitz continuous at zero globally.