Error Bounds and Metric Subregularity

Introduction

This paper is another attempt to demonstrate that (necessary and sufficient) criteria for metric subregularity (or equivalently calmness) of set-valued mappings between general metric or Banach spaces can be treated in the framework of the theory of error bounds of extended real-valued functions. Another objective is to classify the general error bound and subregularity criteria and clarify the relationships between them.

Due to the importance of the three properties mentioned above in both theory and applications, the amount of publications devoted to the properties and corresponding (mostly sufficient) criteria is huge. The interested reader is referred to the articles by Azé , Azé and Corvellec , Corvellec and Motreanu , Gfrerer , Ioffe , Ioffe and Outrata , Ngai and Théra , Jong-Shi Pang , Zheng and Ng and the references therein.

Both local and global settings of the properties have proved to be important and have been thoroughly investigated. In this paper, only local properties are considered.

Here $S(f)$ stands for the lower $0$-level set $\{x\in X\mid f(x)\leq 0\}$.

A set-valued mapping $F:X\rightrightarrows Y$ is a mapping which assigns to every $x\in X$ a subset (possibly empty) $F(x)$ of $Y$. We use the notation

for the graph of $F$ and $F^{-1}:Y\rightrightarrows X$ for the inverse of $F$. This inverse (which always exists) is defined by

A set-valued mapping $F:X\rightrightarrows Y$ between metric spaces is called (locally) metrically subregular (cf., e.g., ) at a point $(\bar{x},\bar{y})\in{\rm gph}\,F$ with constant $\tau>0$ if there exists neighbourhoods $U$ of $\bar{x}$ and $V$ of $\bar{y}$ such that

A set-valued mapping $F:X\rightrightarrows Y$ between metric spaces is called (locally) calm (cf., e.g., ) at a point $(\bar{x},\bar{y})\in{\rm gph}\,F$ with constant $\tau>0$ if there exist neighbourhoods $U$ of $\bar{x}$ and $V$ of $\bar{y}$ such that

The above two properties represent weaker versions of the more robust metric regularity and Aubin properties, respectively, which correspond to replacing $\bar{x}$ and $\bar{y}$ in the above inequalities by arbitrary (not fixed!) $x\in U$ and $y\in V$; cf. .

An immediate observation is that the calmness of $F$ at $(\bar{x},\bar{y})$ with constant $\tau$ is equivalent to the metric subregularity of $F^{-1}$ at $(\bar{y},\bar{x})$ with constant $\tau^{-1}$; cf. [16, Theorem 3H.3]. Hence, any metric subregularity criterion automatically translates into a calmness criterion.

Another observation is that neighbourhood $V$ in the original definition of metric subregularity is actually not needed and the definition is equivalent to the existence of a neighbourhood $U$ of $\bar{x}$ such that

A similar remark can be made regarding the definition of calmness; cf. [16, Exercise 3H.4].

Comparing inequalities (1) and (2), one can easily see that metric subregularity of $F$ at $(\bar{x},\bar{y})$ is equivalent to the local error bound property of the extended real-valued function $x\mapsto d(\bar{y},F(x))$ at $\bar{x}$ (with the same constant). So one might be tempted to apply the well developed theory of error bounds to characterizing metric subregularity and calmness. This approach was very successfully followed by Ioffe and Outrata in finite dimensions.

However, in general the case is not that simple. Most of the error bound criteria (cf. Section 2) are formulated for lower semicontinuous functions, but in infinite dimensions the function $x\mapsto d(\bar{y},F(x))$ can fail to be lower semicontinuous even when ${\rm gph}\,F$ is closed. As observed by Ngai and Théra , in some situations, one can make use of the lower semicontinuous envelope of this function: $x\mapsto\liminf_{u\to x}d(\bar{y},F(u))$, although this breaks the equivalence between error bounds and metric subregularity.

Comparing the criteria for the error bounds and metric subregularity (see Sections 2 and 5), one can notice that in most cases they look very similarly. Furthermore, the proofs of these criteria, though formally independent, are usually based on the same ideas. In fact, when proving regularity or calmness criteria for set-valued mappings, the authors often use error bound-like estimates for an extended real-valued function, but defined on the product space $X\times Y$. The following function (or a function derived from it):

is most commonly used for that purpose; cf. . Observe that this function is lower semicontinuous if ${\rm gph}\,F$ is closed.

In this paper, the theory of local error bounds in metric or Banach/Asplund spaces is, with little changes in the standard proofs, expanded to a class of extended real-valued functions of two variables including, in particular, functions of the type (3). Then, metric subregularity criteria for set-valued mappings are formulated as consequences of the corresponding ones for error bounds.

Following the standard trend initiated by Ioffe (cf. ), criteria for error bounds and metric (sub-)regularity of set-valued mappings in metric spaces are formulated in terms of (strong) slopes . To simplify the statements in metric and also Banach/Asplund spaces, several other kinds of primal and dual space slopes for real-valued functions and set-valued mappings are introduced in this paper and the relationships between them are established. These relationships lead to a simple hierarchy of the error bound and metric subregularity criteria.

Some statements in the paper look rather long because each of them contains an almost complete list of criteria applicable in the situation under consideration. The reader is not expected to read through the whole list. Instead, they can select a particular criterion or a group of criteria corresponding to the setting of interest to them (e.g., local or nonlocal, in metric or Banach/Asplund spaces, etc.)

Certain important groups of criteria are not considered in the current paper: in terms of linearized objects (directional derivatives and tangent cones of some sort) and limiting objects (subdifferentials, normal cones and coderivatives) as well as criteria for nonlinear, in particular Hölder, error bounds and metric subregularity. The convex case is only slightly touched on in several statements.

Only general settings are considered. For metric subregularity and calmness criteria for specific set-valued mappings arising from optimization and variational problems we refer the reader to and the references therein.

Our basic notation is standard, see . Depending on the context, $X$ and $Y$ are either metric or normed spaces. Metrics in all spaces are denoted by the same symbol $d(\cdot,\cdot)$, $d(x,A):=\inf_{a\in{A}}\|x-a\|$ is the point-to-set distance from $x$ to $A$. $B_{\delta}(x)$ denotes the closed ball with radius $\delta$ and centre $x$. When dealing with product spaces, if not specified otherwise, we assume that the product topology is given by the maximum type distance/norm.

We say that a subset $\Omega$ of a metric space is locally closed near $\bar{x}\in\Omega$ if $\Omega\cap{U}$ is closed for some closed neighbourhood $U$ of $\bar{x}$.

is the Fréchet subdifferential of $f$ at $x$. Similarly, if $x\in\Omega\subset X$, then

is the Fréchet normal cone to $\Omega$ at $x$. In the convex case, sets (4) and (5) reduce to the subdifferential and normal cone in the sense of convex analysis, respectively. If $f(x)=\infty$ or $x\notin\Omega$, we set, respectively, $\partial{f}(x)=\emptyset$ or $N_{\Omega}(x)=\emptyset$.

If $F:X\rightrightarrows Y$ is a set-valued mapping between normed linear spaces and $(x,y)\in{\rm gph}\,F$, then

is the Fréchet coderivative of $F$ at $(x,y)$.

The proofs of the main statements rely heavily on two fundamental results of variational analysis: the Ekeland variational principle (Ekeland ; cf., e.g., [53, Theorem 2.1], [14, Theorem 2.26]) and the fuzzy (approximate) sum rule (Fabian ; cf., e.g., [53, Rule 2.2], [14, Theorem 2.33]). Below we provide these results for completeness.

(c) $f(u)+(\varepsilon/\lambda)d(u,x)\geq f(x)$ for all $u\in X$.

Recall that the (normalized) duality mapping [55, Definition 3.2.6] $J$ between a normed space $Y$ and its dual $Y^{*}$ is defined as

The following simple fact of convex analysis is well known (cf., e.g., [56, Corollary 2.4.16]).

$\partial\|\cdot\|(y)=J(y)$ for any $y\neq 0$.

The structure of the paper is as follows. In the next section, we present a survey of error bound criteria for extended-real-valued functions on metric and Banach/Asplund spaces. The criteria are formulated in terms of several kinds of primal and subdifferential slopes. The relationships between the slopes are presented. In Section 3, the definitions of the error bound property and slopes are extended to a special family of extended real-valued functions on the product of metric or Banach/Asplund spaces. The next Section 4 is dedicated to the error bound criteria for functions from this family. Finally, in Section 5, we demonstrate how the definitions of slopes and error bound criteria from Sections 3 and 4 translate into the corresponding definitions and criteria for metric subregularity of set-valued mappings.

Error Bounds and Slopes

In this section, we recall several error bound criteria in terms of (several kinds of) slopes.

Function $f$ is said to have a local error bound at $\bar{x}$ with constant $\tau>0$ if there exists a neighbourhood $U$ of $\bar{x}$ such that

The error bound modulus (conditioning rate ):

coincides with the exact upper bound of all $\tau>0$ such that (7) holds true for some neighbourhood $U$ of $\bar{x}$ and provides a quantitative characterization of the error bound property.

Recall that the local slope of $f$ at $x$ ($f(x)<\infty$) is defined as

when $x$ is not a point of local minimum of $f$ and $|\nabla{f}|(x)=0$ otherwise. This (possibly infinite) quantity provides a convenient primal space characterization of the local behaviour of $f$ near $x$. If $f(x)=\infty$, we set $|\nabla{f}|(x)=\infty$.

In the original publication , constant (9) was called “strong slope” to distinguish it from another (“weak”) construction used in the same article. As this other construction is not widely used in the theory of error bounds, we do not provide its definition here and omit adjective “strong” in the name of constant (9). In , constant (9) is referred to as calmness rate or downward slope. Compare with the rate of steepest descent in .

Several modifications of (9) have been introduced in and further developed in . Below we recall some of them which will be used in the rest of the paper.

An important ingredient of definition (9) (and also definitions (2.3) in and (4) in ) is the nonlocal slope of $f$ at $x$ ($f(x)<\infty$):

where ${f}_{B_{\varepsilon}(x)}$ is the restriction of $f$ to $B_{\varepsilon}(x)$.

Note that definition (10) is not absolutely nonlocal. The supremum in the right-hand side of (10) can be restricted to a certain neighbourhood of $x$ since $f_{+}$ is bounded from below, and consequently $[f(x)-f_{+}(u)]_{+}/d(u,{x})\to 0$ as $d(u,{x})\to\infty$. This distinguishes (10) from the least slope [59, pp. 127–128] and global slope [30, p. 27], [58, formula (4)] where $f(u)$ was used instead of $f_{+}(u)$ in the corresponding definitions.

If $f$ takes only nonnegative values, then (10) takes a simpler form:

(and coincides with the corresponding definitions in .)

Using (9) and (10), we define respectively the strict outer and uniform strict outer slopes of $f$ at $\bar{x}$:

(with the usual convention that the infimum of the empty set equals $+\infty$).

The word “strict” reflects the fact that slopes at nearby points (local or nonlocal) contribute to definitions (12) and (13) making them analogues of the strict derivative. The word “outer” is used to emphasize that only points outside the set $S(f)$ are taken into account. The word “uniform” emphasizes the nonlocal (non-limiting) character of $|\nabla{f}|^{\diamond}(x)$ involved in definition (13).

Definitions (12) and (13) corresponding to the lower $0$-level set $S(f)$ can be easily extended to the case of the general lower level set $\{x\in X\mid f(x)\leq f(\bar{x})\}$ with an arbitrary finite $f(\bar{x})$. It is sufficient to replace $f(x)\downarrow 0$ in (12) and (13) with $f(x)\downarrow f(\bar{x})$, cf. .

One can also consider (smaller) versions of (12) and (13) corresponding to the one-sided limits $f(x)\downarrow 0$ (or more generally $f(x)\downarrow f(\bar{x})$) in the definitions being replaced by the full ones: $f(x)\to 0$ (or $f(x)\to f(\bar{x})$). Such an analogue of (12) is known as the strict slope (limiting slope ); compare with the relaxed slope and the strong relaxed slope .

In normed linear spaces, one can use for estimating slopes and hence error bounds some other tools based on either directional derivatives or subdifferentials of some sort. Below we describe certain tools from the second group. Some examples of application of directional derivatives for estimating slopes and error bounds can be found, e.g., in .

Suppose $X$ is a normed linear space. One can define dual counterparts of the local slopes (9) and (12): the subdifferential slope (cf. the least slope , the nonsmooth slope , see also )

of $f$ at $x$ ($f(x)<\infty$) and the strict outer subdifferential slope

Similar to the case of the primal space slopes, one can also define analogues of (15) as described in Remarks 1 and 2 above, cf. .

The next proposition summarizes the relationships between the slopes.

If $0<f(x)<\infty$, then $|\nabla{f}|(x)\leq|\nabla{f}|^{\diamond}(x)$;

$\overline{|\nabla{f}|}{}^{>}(\bar{x})\leq\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})$;

$\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})\geq\displaystyle\liminf_{x\to\bar{x},\;f(x)\downarrow 0}\frac{f(x)}{d(x,\bar{x})}$.

$|\nabla{f}|(x)\leq|\partial{f}|(x)$ for all $x\in X$ with $f(x)<\infty$;

$\overline{|\nabla{f}|}{}^{>}(\bar{x})\leq\overline{|\partial{f}|}{}^{>}(\bar{x})$;

if $X$ is Asplund and $f_{+}$ is lower semicontinuous near $\bar{x}$, then $\overline{|\nabla{f}|}{}^{>}(\bar{x})=\overline{|\partial{f}|}{}^{>}(\bar{x})$;

if $f$ is convex, then $|\nabla{f}|(x)=|\partial{f}|(x)$ for all $x\in X$ with $f(x)<\infty$ and $\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})=\overline{|\nabla{f}|}{}^{>}(\bar{x})=\overline{|\nabla{f}|}{}^{>+}(\bar{x})=\overline{|\partial{f}|}{}^{>}(\bar{x})=\overline{|\partial{f}|}{}^{+>}(\bar{x})$.

Parts (i), (ii), (iv), and (v) of Proposition 2.1 follow directly from the definitions, see also . Part (iii) is a consequence of (11). Part (vi) was proved in [12, Proposition 5(ii)] using the Ekeland variational principle (Lemma 1.1), cf. [41, Lemma 2.1], [60, Remark 3.2]. The first equality in (vii) can be found in numerous publications, cf. . For the other equalities in (vii), see [12, Theorem 5]. Note that in most publications cited above, $X$ is assumed a Banach space and $f$ lower semicontinuous, but these additional assumptions seem to be superfluous.

The uniform strict slope (13) provides the necessary and sufficient characterization of error bounds, cf. [26, Theorem 1].

$\displaystyle{\rm Er}\,{f}(\bar{x})\leq\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})$;

if $X$ is a Banach space and $f_{+}$ is lower semicontinuous near $\bar{x}$, then $\displaystyle{\rm Er}\,{f}(\bar{x})=\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})$.

Analyzing the proof of [26, Theorem 1] (or more general Theorem 4.1 in Section 4), one can see that Theorem 2.2 remains true if the nonlocal slope (10) is replaced in definition (13) of the uniform strict slope by a smaller “restricted” nonlocal slope

where $D(x)$ is any subset of $X$ containing $S(f)$. For instance, one can take $D(x)=\{u\in X\mid d(u,S(f))\leq d(x,S(f))\}$. In this case (and under the natural assumption that $f(x)>0$), (16) reduces to the subslope of $f$ at $x$ introduced in . Another obvious possibility is to take $D(x)=S(f)$ in which case (16) becomes

(with the convention $0/0=0$). Substituting this quantity into (13) instead of $|\nabla{f}|^{\diamond}(x)$ makes (13) trivially equal to ${\rm Er}\,{f}(\bar{x})$.

Thanks to Theorem 2.2 and Proposition 2.1, one can formulate several quantitative and qualitative criteria of the error bound property in terms of various slopes.

Let $\gamma>0$. Consider the following conditions:

$f$ has a local error bound at $\bar{x}$ with constant $\tau>0$;

$\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})>\gamma$, i.e., for some $\rho>0$ and any $x\in B_{\rho}(\bar{x})$ with $0<f(x)<\rho$, it holds $|\nabla{f}|^{\diamond}(x)>\gamma$, and consequently, there is a $u\in X$ such that

$\displaystyle\liminf_{x\to\bar{x},\;f(x)\downarrow 0}\frac{f(x)}{d(x,\bar{x})}>\gamma$;

$\overline{|\nabla{f}|}{}^{>}(\bar{x})>\gamma$, i.e., for some $\rho>0$ and any $x\in B_{\rho}(\bar{x})$ with $0<f(x)<\rho$, it holds $|\nabla{f}|(x)>\gamma$, and consequently, for any $\varepsilon>0$, there is a $u\in B_{\varepsilon}(x)$ such that

$\displaystyle\liminf_{x\to\bar{x},\;f(x)\downarrow 0}\max\left\{|\nabla{f}|(x),\frac{f(x)}{d(x,\bar{x})}\right\}>\gamma$, i.e., for some $\rho>0$ and any $x\in B_{\rho}(\bar{x})$ with $0<f(x)<\rho$ and $f(x)/d(x,\bar{x})\leq\gamma$, it holds $|\nabla{f}|(x)>\gamma$, and consequently, for any $\varepsilon>0$, there is a $u\in B_{\varepsilon}(x)$ such that (17) holds true;

$X$ is a normed space and $\overline{|\partial{f}|}{}^{>}(\bar{x})>\gamma$, i.e., for some $\rho>0$ and any $x\in B_{\rho}(\bar{x})$ with $0<f(x)<\rho$, it holds $|\partial{f}|(x)>\gamma$, and consequently $\|x^{*}\|>\gamma$ for all $x^{*}\in\partial f(x)$;

$\displaystyle\liminf_{x\to\bar{x},\;f(x)\downarrow 0}\max\left\{|\partial{f}|(x),\frac{f(x)}{\|x-\bar{x}\|}\right\}>\gamma$, i.e., for some $\rho>0$ and any $x\in B_{\rho}(\bar{x})$ with $0<f(x)<\rho$ and $f(x)/\|x-\bar{x}\|\leq\gamma$, it holds $|\partial{f}|(x)>\gamma$, and consequently $\|x^{*}\|>\gamma$ for all $x^{*}\in\partial f(x)$.

if $\gamma<\tau$, then (a) \Rightarrow\(b);

if $X$ is a normed space, then (d) \Rightarrow\(f) and (e) \Rightarrow\(g).

Suppose $X$ is complete and $f_{+}$ is lower semicontinuous near $\bar{x}$. Then,

if $\tau\leq\gamma$, then (b) \Rightarrow\(a).

Suppose, additionally, that $X$ is a Banach space. Then,

if $X$ is Asplund, then (d) \Leftrightarrow\(f) and (e) \Leftrightarrow\(g);

if $f$ is convex, then (b) \Leftrightarrow\(d) \Leftrightarrow\(f).

Criterion (b) in the above proposition is a version of [5, Basic Lemma]; see also, [67, Theorem 2(ii)], [68, Theorem 1], [69, Theorem 3.1], [8, Corollary 2.3], [70, Corollary 4.3], [51, Remark 6.2.2].

Criteria (d) and (f) can be found, e.g., in [6, Theorem 2.1]; see also [13, Theorem 1], [71, Theorem 3.1], [72, Theorem 3.1], [73, Theorem 2.4], [2, Theorem 5.2], [7, Corollary 3.1 and Theorem 3.2], [74, Corollary 2], [36, Theorem 4.12], [10, (1.8)], [41, Proposition 2.1], [75, (R1)], [32, Corollary 4.5], [37, Corollary 1], [76, Theorem 3.2], [77, Corollary 4.1]).

Criterion (e) is a combination of criteria (c) and (d), while criterion (g) is a combination of criteria (c) and (f).

The equivalence of (a) and (f) in the convex case can be found, e.g., in [78, Theorem 2.5], [75, (R1) and (R2)].

Suppose $X$ is complete and $f_{+}$ is lower semicontinuous near $\bar{x}$. Then, $f$ has a local error bound at $\bar{x}$ provided that one of the following conditions holds true:

$\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})>0$;

$\displaystyle\liminf_{x\to\bar{x},\;f(x)\downarrow 0}\frac{f(x)}{d(x,\bar{x})}>0$;

$\overline{|\nabla{f}|}{}^{>}(\bar{x})>0$;

$\displaystyle\liminf_{x\to\bar{x},\;\frac{f(x)}{d(x,\bar{x})}\downarrow 0}|\nabla{f}|(x)>0$;

$X$ is an Asplund space and $\overline{|\partial{f}|}{}^{>}(\bar{x})>0$;

$X$ is an Asplund space and $\displaystyle\liminf_{x\to\bar{x},\;\frac{f(x)}{\|x-\bar{x}\|}\downarrow 0}|\partial{f}|(x)>0$.

condition (a) is also necessary for the local error bound property of $f$ at $\bar{x}$;

if $X$ is Asplund, then (e) \Leftrightarrow\(c) and (f) \Leftrightarrow\(d).

One of the main tools in the proof of inequality

in Proposition 2.1(vi) which is crucial for the sufficient error bound criterion in Corollary 2.4(e) is the fuzzy sum rule (Lemma 1.2) for Fréchet subdifferentials in Asplund spaces. The inequality and the corresponding sufficient criterion can be extended to general Banach spaces. For that, one has to replace Fréchet subdifferentials with some other (possibly abstract) subdifferentials on the given space satisfying a certain set of natural properties including a kind of sum rule (trustworthy subdifferentials ), cf. [1, Proposition 1.13], [19, Proposition 2.3], [2, Proposition 4.1], [12, Proposition 6], e.g., Ioffe approximate or Clarke subdifferentials. Note that the opposite inequality guaranteed by Proposition 2.1(vi) is specific for Fréchet subdifferentials and cannot be extended beyond Asplund spaces unless $f$ is convex near $\bar{x}$, cf. Proposition 2.1(vii).

The seemingly more general case of nonlinear error bounds, i.e., when the linear estimate (7) is replaced by the inequality

Error Bounds and Slopes for Functions of Two Variables

We assume that $f(\bar{x},\bar{y})=0$, and $f$ depends on its second variable in a special way:

$\displaystyle\liminf_{f(x,y)\downarrow 0}\frac{f(x,y)}{d(y,\bar{y})}>0$.

In particular, $f(x,y)\downarrow 0\;\Rightarrow\;y\to\bar{y}$.

Conditions (P1) and (P2) are obviously satisfied.

We are interested in a special kind of error bounds of $f$ with respect to the first argument.

We say that $f$ has an error bound with respect to $x$ at $(\bar{x},\bar{y})$ with constant $\tau>0$ if there exists a neighbourhood $U$ of $\bar{x}$ such that

where $S(f):=\{x\in X|\ f(x,y)\leq 0\mbox{ for some }y\in Y\}$. In view of (P1),

which is the usual error bound property for the function $x\mapsto\inf_{y\in Y}f(x,y)$, but for the goals of the current paper, it is more appropriate to use the setting of (19).

The error bound property (19) can be equivalently characterized using the following modification of (8):

Note that definition (20) (as well as the error bound property defined by (19)) looks local only in $x$. In fact, thanks to (P2), it is local in both $x$ and $y$. Indeed, it admits the following equivalent representations.

$\displaystyle{\rm Er}\,f(\bar{x},\bar{y})=\liminf_{\begin{subarray}{c}x\to\bar{x},\,y\to\bar{y}\\ f(x,y)>0\end{subarray}}\frac{f(x,y)}{d(x,S(f))}=\liminf_{\begin{subarray}{c}x\to\bar{x},\,f(x,y)\downarrow 0\end{subarray}}\frac{f(x,y)}{d(x,S(f))}$.

follow from (P2) and the obvious implications:

If ${\rm Er}\,f(\bar{x},\bar{y})=\infty$, then the claimed equalities hold trivially. If ${\rm Er}\,f(\bar{x},\bar{y})<\gamma<\infty$, then there exists a sequence $(x_{k},y_{k})\in X\times Y$ with $f(x_{k},y_{k})>0$ such that $x_{k}\to\bar{x}$ as $k\to\infty$ and $f(x_{k},y_{k})/d(x_{k},S(f))<\gamma$, $k=1,2,\ldots$. Hence, $d(x_{k},S(f))\to 0$ and consequently $f(x_{k},y_{k})\downarrow 0$ as $k\to\infty$. It follows that

2 Nonlocal slopes

The roles of variables $x$ and $y$ in definitions (19) and (20) are different. To better reflect this, we are going to consider the following asymmetric maximum-type distance in $X\times Y$ depending on a positive parameter $\rho$:

This is a pretty common trick, e.g., when studying regularity properties of set-valued mappings, cf. . Alternatively, one can use the parametric sum-type metric (cf. ):

To formulate (nonlocal) primal space characterizations of the error bound property (19), we are going to use the following modifications of slopes (10) and (13):

which will be called, respectively, the nonlocal $\rho$-slope of $f$ at $(x,y)$ and the uniform strict slope. It is assumed in (23) that $f(x,y)<\infty$.

Definition (23) of the nonlocal $\rho$-slope is a realization of definition (10) for the case of a function on a product space with the product metric defined by (21). In definition (24), we have not only $x\to\bar{x}$ and $f(x,y)\downarrow 0$, but also the metric on $X\times Y$ used in the definition of the nonlocal $\rho$-slope $|\nabla{f}|{}^{\diamond}_{\rho}(x,y)$ changing with the contribution of the $y$ component diminishing as $\rho\downarrow 0$.

3 Local slopes

The local analogues of (23) and (24) are defined as follows:

and are called, respectively, the $\rho$-slope of $f$ at $(x,y)$ ($f(x,y)<\infty$) and the strict outer slope of $f$ at $(\bar{x},\bar{y})$.

Definition (25) of the $\rho$-slope is a realization of definition (9) for the case of a function on a product space with the product metric defined by (21), cf. .

$|\nabla{f}|_{\rho}(x,y)\leq|\nabla{f}|_{\rho}^{\diamond}(x,y)$ for all $\rho>0$ and all $(x,y)\in X\times Y$ with $0<f(x,y)<\infty$;

$\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})\leq\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})$;

$\overline{|\nabla{f}|}{}^{\diamond}(\bar{x})\geq\displaystyle\liminf_{x\to\bar{x},\;f(x,y)\downarrow 0}\frac{f(x,y)}{d(x,\bar{x})}$.

(i) and (ii) follow from comparing definitions (23), (24), (25), and (26).

(iii) Let $\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})<\gamma<\infty$ and $\rho>0$. By (P2), one can find a $\rho^{\prime}\in(0,\rho)$ such that

as long as $0<f(x,y)<\rho^{\prime}$. By (24), there exists a point $(x,y)\in X\times Y$ with $d(x,\bar{x})<\rho^{\prime}$ and $0<f(x,y)<\rho^{\prime}$ such that $|\nabla{f}|{}^{\diamond}_{\rho^{\prime}}(x,y)<\gamma$, i.e., by (23),

for all $(u,v)\neq(x,y)$. Observe that $(x,y)\neq(\bar{x},\bar{y})$ since $f(x,y)>0$. Hence,

Taking limits as $\rho\downarrow 0$ and $\gamma\downarrow\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})$, we arrive at the claimed inequality. ∎

4 Subdifferential slopes

If $X$ and $Y$ are normed linear spaces, one can define subdifferential counterparts of the local slopes (25) and (26). In the product space $X\times Y$, along with the usual $l_{\infty}$-type norm

we are going to consider the $\rho$-norm $\|\cdot\|_{\rho}$ being the realization of the $\rho$-metric (21):

The corresponding dual norm (we keep the same notation $\|\cdot\|_{\rho}$ for it) is of the form:

The subdifferential slopes are defined as follows:

and called, respectively, the subdifferential $\rho$-slope of $f$ at $(x,y)$ ($f(x,y)<\infty$) and the strict outer subdifferential slope of $f$ at $(\bar{x},\bar{y})$.

$|\nabla{f}|_{\rho}(x,y)\leq|\partial{f}|_{\rho^{2}}(x,y)+\rho$ for all $\rho>0$ and all $(x,y)\in X\times Y$ with $f(x,y)<\infty$;

$\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})\leq\overline{|\partial{f}|}{}^{>}(\bar{x},\bar{y})$;

if $X$ and $Y$ are Asplund and $f_{+}$ is lower semicontinuous near $(\bar{x},\bar{y})$, then $\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})=\overline{|\partial{f}|}{}^{>}(\bar{x},\bar{y})$.

(i) Let $f(x,y)<\infty$, $\rho>0$, $(x^{*},y^{*})\in\partial f(x,y)$, and $\|y^{*}\|<\rho^{2}$. By definition (4) of the Fréchet subdifferential and taking into account that the Fréchet subdifferential is invariant to renorming of a space, we have

Comparing the first expression with definition (25) and taking into account that the last expression is positive, we conclude that $|\nabla{f}|_{\rho}(x,y)\leq\|x^{*}\|+\rho$. The assertion follows after taking infimum in the right-hand side of the last inequality over all $(x^{*},y^{*})\in\partial f(x,y)$ with $\|y^{*}\|<\rho^{2}$.

(ii) follows from (i) due to representations (26), (30), and the simple observation:

(iii) Let $X$ and $Y$ be Asplund and $f_{+}$ be lower semicontinuous near $(\bar{x},\bar{y})$ (in the product topology). Thanks to (ii), we only need to prove that $\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})\geq\overline{|\partial{f}|}{}^{>}(\bar{x},\bar{y})$. If $\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})=\infty$, the assertion is trivial. Let $\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})<\gamma<\infty$. Choose a $\gamma^{\prime}\in(\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y}),\gamma)$ and an arbitrary $\rho>0$. Set $\rho^{\prime}=\min\{1,\gamma^{-1}\}\rho$. By definitions (26) and (25), one can find a point $(x,y)\in X\times Y$ such that $d(x,\bar{x})<\rho^{\prime}$, $0<f(x,y)<\rho^{\prime}$, $f$ is lower semicontinuous near $(x,y)$, and

In other words, $(x,y)$ is a point of local minimum of the function

sufficiently small such that $f$ is lower semicontinuous on $B_{\varepsilon}((x,y))$ and $B_{\varepsilon}(x)\cap S(f)=\emptyset$. Applying the fuzzy sum rule (see, e.g., [14, Theorem 2.33]), we find points $(z,w)\in X\times Y$ and $(x^{*},y^{*})\in\partial f(z,w)$ such that $d((z,w),(x,y))<\varepsilon$, $f(z,w)<f(x,y)+\varepsilon$, and $\|(x^{*},y^{*})\|_{\rho^{\prime}}<\gamma^{\prime}+\varepsilon$. It follows that $d(z,\bar{x})<\rho$, $0<f(z,w)<\rho$, $\|x^{*}\|<\gamma$, and $\|y^{*}\|<{\rho^{\prime}}\gamma\leq\rho$. Hence, $|\partial{f}|_{\rho}(z,w)<\gamma$ and consequently $\overline{|\partial{f}|}{}^{>}(\bar{x},\bar{y})\leq\gamma$. The claimed inequality follows after letting $\gamma\to\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})$. ∎

The subdifferential $\rho$-slope (29) of $f$ at $(x,y)$ can be replaced in definition (30) by the following modification:

where norm $\|\cdot\|_{\rho}$ is given by (28). In fact, one can notice that this constant was implicitly present in the proof of Theorem 3.3 where it was shown, in particular, that

It is easy to check the relationships between constants (29) and (31):

$|\partial{f}|_{\rho^{\prime}}^{\prime}(x,y)\leq|\partial{f}|_{\rho}(x,y)+\rho/\rho^{\prime}$ for all $\rho>0$ and $\rho^{\prime}>0$;

if $|\partial{f}|_{\rho}^{\prime}(x,y)<\gamma<\infty$, then $|\partial{f}|_{\gamma\rho}(x,y)<\gamma$.

An advantage of constant (29) is that it does not depend on the choice of an equivalent norm in the product space.

Error Bounds Criteria for Functions of Two Variables

The main result is given by the next theorem being an extension of Theorem 2.2.

${\rm Er}\,f(\bar{x},\bar{y})\leq\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})$;

if $X$ and $Y$ are complete and $f_{+}$ is lower semicontinuous (in the product topology) near $(\bar{x},\bar{y})$, then ${\rm Er}\,f(\bar{x},\bar{y})=\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})$.

(i) If ${\rm Er}\,f(\bar{x},\bar{y})=0$, the assertion is trivial. Let $0<\gamma<{\rm Er}\,f(\bar{x},\bar{y})$. We are going to show that $\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})\geq\gamma$. By (20), there is a $\delta>0$ such that

for any $x\in{B}_{\delta}(\bar{x})$ and $y\in Y$ with $f(x,y)>0$. At the same time, by (P2), taking a smaller $\delta$ if necessary, we can ensure that

for all $(x,y)\in X\times Y$ such that $0<f(x,y)<\delta$. If $\rho\in(0,\delta)$, $d(x,\bar{x})<\rho$, and $0<f(x,y)<\rho$, then, by (32), one can find a $u\in S(f)$ such that

and consequently $\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})\geq\gamma$. The claimed inequality follows after letting $\gamma\to{\rm Er}\,f(\bar{x},\bar{y})$.

(ii) Let $X$ and $Y$ be complete and $f_{+}$ be lower semicontinuous near $(\bar{x},\bar{y})$ (in the product topology). Thanks to (i), we only need to show that

If ${\rm Er}\,f(\bar{x},\bar{y})=\infty$, the inequality is trivial. Let ${\rm Er}\,f(\bar{x},\bar{y})<\gamma<\infty$. Choose a $\gamma^{\prime}\in({\rm Er}\,f(\bar{x},\bar{y}),\gamma)$, a $\delta>0$ such that $f_{+}$ is lower semicontinuous on $B_{\delta}(\bar{x},\bar{y})$, a $\beta>0$ such that

By (20), there is a $z\in B_{\eta}(\bar{x})$ and a $w\in Y$ such that

Denote $\varepsilon:=f(z,w)$ and $\mu:=d(z,S(f))$. Then, $\mu\leq d(z,\bar{x})\leq\eta$. Now we consider a complete metric space $(B_{\delta}(\bar{x},\bar{y}),d_{\rho})$, where metric $d_{\rho}$ is defined by (21). Applying to $f_{+}$ the Ekeland variational principle (Lemma 1.1) with $\varepsilon>0$ defined above and

we find a point $(x,y)\in B_{\delta}(\bar{x},\bar{y})$ such that

Thanks to (38), (37), (35), and (36), we have

It follows from (40) that $f(x,y)>0$, while (41) and (42) together with (34) guarantee that $d(x,\bar{x})<\rho$, $f(x,y)<\rho$, and

If $(u,v)\notin B_{\delta}(\bar{x},\bar{y})$, then, by (43),

Taking limits in the last inequality as $\rho\downarrow 0$ and $\gamma\to{\rm Er}\,f(\bar{x},\bar{y})$ completes the proof. ∎

It follows from Theorem 4.1 that inequality $\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})>0$ is crucial for determining the error bound property of $f$ at $(\bar{x},\bar{y})$.

The nonlocal $\rho$-slope (23) depends on the choice of $\rho$-metric on the product space. If instead of the maximum type metric $d_{\rho}$, defined by (21), one employs in (23) the sum type metric $d_{\rho}^{1}$, defined by (22), it will produce a different number. We say that a $\rho$-metric $d^{\prime}_{\rho}$ on $X\times Y$ is admissible if $d_{\rho}\leq d^{\prime}_{\rho}\leq d^{1}_{\rho}$. Fortunately, Theorem 4.1 is invariant on the choice of an admissible metric.

Theorem 4.1 remains valid if, in definition (23), metric (21) is replaced by some other admissible $\rho$-metric.

Denote by $\overline{|\nabla{f}|}{}^{\diamond}_{1}(\bar{x},\bar{y})$ the constant produced by (24) if metric (21) is replaced in (23) by metric (22). Since a larger metric leads to a smaller value of (23) and consequently of (24), it holds $\overline{|\nabla{f}|}{}^{\diamond}_{1}(\bar{x},\bar{y})\leq\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})$ with the constants corresponding to any other admissible $\rho$-metric lying in between. We only need to prove that ${\rm Er}\,f(\bar{x},\bar{y})\leq\overline{|\nabla{f}|}{}^{\diamond}_{1}(\bar{x},\bar{y})$.

If ${\rm Er}\,f(\bar{x},\bar{y})=0$ or $\overline{|\nabla{f}|}{}^{\diamond}_{1}(\bar{x},\bar{y})=\infty$, the inequality is trivial. Let $0<\gamma<{\rm Er}\,f(\bar{x},\bar{y})$ and $\overline{|\nabla{f}|}{}^{\diamond}_{1}(\bar{x},\bar{y})<\infty$. We are going to show that $\overline{|\nabla{f}|}{}^{\diamond}_{1}(\bar{x},\bar{y})\geq\gamma$. Choose a $\gamma^{\prime}\in(\gamma,{\rm Er}\,f(\bar{x},\bar{y}))$. By (20), there is a $\delta>0$ such that

for any $x\in{B}_{\delta}(\bar{x})$ and $y\in Y$ with $f(x,y)>0$. Thanks to (P2), taking a smaller $\delta$ if necessary, we can ensure that

for all $(x,y)\in X\times Y$ such that $0<f(x,y)<\delta$.

Choose any $\rho\in(0,\delta)$ and any $(x,y)\in X\times Y$ such that $d(x,\bar{x})<\rho$ and $0<f(x,y)<\rho$ (Such points exist since $\overline{|\nabla{f}|}{}^{\diamond}_{1}(\bar{x},\bar{y})<\infty$.) By (44), one can find a $u\in S(f)$ such that

The claimed inequality follows after taking limits as $\rho\downarrow 0$ and $\gamma\to{\rm Er}\,f(\bar{x},\bar{y})$. ∎

It follows from Theorem 4.1 and Proposition 4.2 that, when $X$ and $Y$ are complete and $f_{+}$ is lower semicontinuous near $(\bar{x},\bar{y})$, the uniform strict slope (24) of $f$ at $(\bar{x},\bar{y})$ is invariant on the choice of an admissible $\rho$-metric on $X\times Y$.

2 Error bound criteria

Using slopes (24), (26), and (30), one can formulate several quantitative criteria of error bounds. The next corollary is a consequence of Theorems 4.1 and 3.3 and Proposition 3.2.

Let $\gamma>0$. Consider the following conditions:

$f$ has an error bound at $(\bar{x},\bar{y})$ with some $\tau>0$;

$\overline{|\nabla{f}|}{}^{\diamond}(\bar{x},\bar{y})>\gamma$, i.e., for some $\rho>0$ and any $(x,y)\in X\times Y$ with $d(x,\bar{x})<\rho$, and $0<f(x,y)<\rho$, it holds $|\nabla{f}|_{\rho}^{\diamond}(x,y)>\gamma$, and consequently there is a $(u,v)\in X\times Y$ such that

$\displaystyle\liminf_{x\to\bar{x},\;f(x,y)\downarrow 0}\frac{f(x,y)}{d(x,\bar{x})}>\gamma$;

$\overline{|\nabla{f}|}{}^{>}(\bar{x},\bar{y})>\gamma$, i.e., for some $\rho>0$ and any $(x,y)\in X\times Y$ with $d(x,\bar{x})<\rho$ and $0<f(x,y)<\rho$, it holds $|\nabla{f}|_{\rho}(x,y)>\gamma$ and consequently, for any $\varepsilon>0$, there is a $(u,v)\in B_{\varepsilon}(x,y)$ such that

$\displaystyle\liminf_{x\to\bar{x},\;f(x,y)\downarrow 0}\max\left\{|\nabla{f}|(x,y),\frac{f(x,y)}{d(x,\bar{x})}\right\}>\gamma$, i.e., for some $\rho>0$ and any $(x,y)\in X\times Y$ with $d(x,\bar{x})<\rho$, $0<f(x,y)<\rho$, and $f(x,y)/d(x,\bar{x})\leq\gamma$, it holds $|\nabla{f}|_{\rho}(x,y)>\gamma$ and consequently, for any $\varepsilon>0$, there is a $(u,v)\in B_{\varepsilon}(x,y)$ such that (46) holds true;

$X$ and $Y$ are normed spaces and $\overline{|\partial{f}|}{}^{>}(\bar{x},\bar{y})>\gamma$, i.e., for some $\rho>0$ and any $(x,y)\in X\times Y$ with $\|x-\bar{x}\|<\rho$ and $0<f(x,y)<\rho$, it holds $|\partial{f}|_{\rho}(x,y)>\gamma$ and consequently $\|x^{*}\|>\gamma$ for all $(x^{*},y^{*})\in\partial f(x,y)$ with $\|y^{*}\|<\rho$.

$X$ and $Y$ are normed spaces and $\displaystyle\liminf_{x\to\bar{x},\;f(x,y)\downarrow 0}\max\left\{|\partial{f}|(x,y),\frac{f(x,y)}{\|x-\bar{x}\|}\right\}>\gamma$, i.e., for some $\rho>0$ and any $(x,y)\in X\times Y$ with $\|x-\bar{x}\|<\rho$, $0<f(x,y)<\rho$, and $f(x,y)/\|x-\bar{x}\|\leq\gamma$, it holds $|\partial{f}|_{\rho}(x,y)>\gamma$ and consequently $\|x^{*}\|>\gamma$ for all $(x^{*},y^{*})\in\partial f(x,y)$ with $\|y^{*}\|<\rho$.