# On (local) analysis of multifunctions via subspaces contained in graphs of
generalized derivatives

Helmut Gfrerer Institute of Computational Mathematics, Johannes Kepler
University Linz, A-4040 Linz, Austria<EMAIL_ADDRESS>Jiří V. Outrata
Institute of Information Theory and Automation, Czech Academy of Sciences,
18208 Prague, Czech Republic, and Centre for Informatics and Applied
Optimization, Federation University of Australia, POB 663, Ballarat, Vic 3350,
Australia<EMAIL_ADDRESS>
Abstract. The paper deals with a comprehensive theory of mappings, whose local
behavior can be described by means of linear subspaces, contained in the
graphs of two (primal and dual) generalized derivatives. This class of
mappings includes the graphically Lipschitzian mappings and thus a number of
multifunctions, frequently arising in optimization and equilibrium problems.
The developed theory makes use of new generalized derivatives, provides us
with some calculus rules and reveals a number of interesting connections. In
particular, it enables us to construct a modification of the semismooth*
Newton method with improved convergence properties and to derive a
generalization of Clarke’s Inverse Function Theorem to multifunctions together
with new efficient characterizations of strong metric (sub)regularity and tilt
stability.

Key words. generalized derivatives, second-order theory, strong metric
(sub)regularity, semismoothness∗.

AMS Subject classification. 65K10, 65K15, 90C33.

##  1 Introduction

When implementing the semismooth∗ Newton method [14] for solving an inclusion
of the form

$0\in F(x)$

with some set-valued mapping
$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$, we observed that it is
advantageous to work with linear subspaces
$L\subseteq\mathbb{R}^{n}\times\mathbb{R}^{n}$ having dimension $n$ and
contained in the graph of the limiting coderivative, i.e.,

$L\subseteq\mathrm{gph}\,D^{*}F(x,y)$

at points $(x,y)\in\mathrm{gph}\,F$.

However, this paper goes far beyond the analysis of the above issue and
presents a comprehensive study of a class of mappings, whose local behavior
can be described by appropriately constructed linear subspaces. This class
turns out to be rather broad and the developed theory helps us both to suggest
an efficient modification of the semismooth∗ Newton method as well as to
derive a number of new results concerning strong metric subregularity, strong
metric regularity and tilt stability. More precisely, for the mentioned
mapping $F$, primal and dual generalized derivatives are introduced, whose
elements are subspaces of dimension $n$. In order to define these derivatives,
we consider points in the graph of the mapping where the tangent cone amounts
to a subspace and then perform an outer limiting operation in a certain
compact metric space.

Our construction is motivated by the definition of the B-subdifferential
(Bouligand-subdifferential) for single-valued mappings, whose elements are
given as limit of Jacobians at points where the mapping is Fréchet
differentiable. Note that the tangent cone to the graph of a map is a subspace
whenever the mapping is differentiable at the point under consideration.
Instead of computing limits of matrices, we consider the limit of subspaces
given by the graph of the linear mappings induced by the matrices. When the
mapping is Lipschitzian, then we obtain a one-to-one correspondence between
the new primal generalized derivative and the B-subdifferential. However, for
non-Lipschitzian single-valued mappings there will be a difference because we
are considering limits of subspaces in a compact metric space whereas the
underlying matrices can be unbounded.

There are some relations between our generalized derivatives and existing
ones. The dual derivative consists of subspaces contained in the limiting
coderivative and the elements of the primal derivative are subspaces contained
in the so-called outer limiting graphical derivative. To the best of our
knowledge, the latter has not yet been considered in the literature and is
contained in the so-called strict graphical derivative.

Our theory is not applicable to arbitrary mappings. However, as already
mentioned, the class of mappings which are suited for our approach, is rather
broad and important for applications. In particular, every mapping which is
graphically Lipschitzian, i.e., its graph coincides under some change of
coordinates with the graph of a locally Lipschitzian mapping, belongs to this
class. Graphically Lipschitzian mappings have been already considered by
Rockafellar [33]. E.g., locally maximally hypomonotone mappings like the
subdifferential mapping of prox-regular and subdifferentially continuous
functions possess this property [27]. Thus, our approach is particularly
suitable for second-order theory and we will establish a strong relationship
with the so-called quadratic bundle introduced in the recent paper [35]. Note
that in [33] also a limit of tangent spaces has been considered. However, in
[33] an inner limit with respect to the usual set-convergence has been used
yielding a different sort of results.

Within the framework of the new theory one can introduce a new regularity
notion leading to an adaptation of the semismooth∗ Newton method. This notion
is weaker than metric regularity and enables us to streamline the algorithm
and to relax the assumptions, ensuring its locally superlinear convergence.
Under the respective regularity condition it is also possible to show that a
semismooth∗ mapping is strongly metrically subregular, not only at the
reference point itself but also on a neighborhood of it. It seems that this
somewhat extended property of strong metric subregularity around the reference
point has not been considered yet. As a byproduct, we present a
characterization of this property by means of the outer limiting graphical
derivative.

Finally we turn our attention to the property of strong metric regularity.
Since strongly regular mappings are graphically Lipschitzian by the
definition, the preceding theory enables us to reveal some interesting new
connections. In particular, one obtains a generalization of Clarke’s Inverse
Function Theorem to set-valued mappings and, when applied to specific problem
classes, these results lead to new characterizations of strong metric
regularity for locally maximally monotone operators and to a new
characterization of tilt-stability. Compared with existing characterizations,
the new ones have the advantage, that not the whole strict graphical
derivative or limiting coderivative must be checked (as, e.g., in [20, 8, 28])
but only a condition on the subspaces contained in its graph. In this way the
arsenal of available criteria for strong metric regularity (cf. [31, 9, 20,
15, 8, 10]) and tilt stability (cf.[28, 11, 24]) is enriched.

The plan of the paper is as follows. After the Preliminaries, devoted to
relevant notions from variational analysis, in Section 3 we introduce and
analyze the crucial class of SCD (subspace containing derivative) mappings. In
their analysis we make use of the mentioned generalized derivatives, for which
some basic calculus rules are developed and exact formulas in case of
graphically Lipschitzian mappings are provided. In Section 4 we introduce the
notion of SCD-regularity, which plays a central role in the subsequent
sections. Section 5 deals with the adaptation of the semismooth∗ Newton method
to SCD mappings. The property of strong metric subregularity around a point is
characterized in Section 6. Finally, in Section 7 we present a generalization
of Clarke’s Inverse Function Theorem and new characterizations of strong
metric regularity and tilt stability for various classes of SCD mappings.

The following notation is employed. Given a linear subspace
$L\subseteq\mathbb{R}^{n}$, $L^{\perp}$ denotes its orthogonal complement and,
for a closed cone $K$ with vertex at the origin, $K^{\circ}$ signifies its
(negative) polar. Further, given a multifunction $F$,
$\mathrm{gph}\,F:=\\{(x,y)\mid\;y\in F(x)\\}$ stands for its graph. For an
element $u\in\mathbb{R}^{n}$, $\|u\|$ denotes its Euclidean norm and ${\cal
B}_{\delta}(u)$ denotes the closed ball around $u$ with radius $\delta$. In a
product space we use the norm $\|(u,v)\|:=\sqrt{\|u\|^{2}+\|v\|^{2}}$. Given
an $m\times n$ matrix $A$, we employ the operator norm $\|A\|$ with respect to
the Euclidean norm and we denote the range of A by ${\rm rge\;}A$. Given a set
$\Omega\subset\mathbb{R}^{s}$, we define the distance of a point $x$ to
$\Omega$ by
$d_{\Omega}(x):=\operatorname{dist}(x,\Omega):=\inf\\{\|y-x\|\mid\;y\in\Omega\\}$
and the indicator function is denoted by $\delta_{\Omega}$. When a mapping
$F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is differentiable at $x$, we denote by
$\nabla F(x)$ its Jacobian.

##  2 Preliminaries

Throughout the whole paper, we will frequently use the following basic notions
of modern variational analysis. All the sets under consideration are supposed
to be locally closed around the points in question without further mentioning.

######  Definition 2.1.

Let $A$ be a set in $\mathbb{R}^{s}$ and let $\bar{x}\in A$. Then

  1. (i)

The tangent (contingent, Bouligand) cone to $A$ at $\bar{x}$ is given by

$T_{A}(\bar{x}):=\mathop{{\rm Lim}\,{\rm sup}}\limits_{t\downarrow
0}\frac{A-\bar{x}}{t}$

and the paratingent cone to $A$ at $\bar{x}$ is given by

$T^{P}_{A}(\bar{x}):=\mathop{{\rm Lim}\,{\rm
sup}}\limits_{{\textstyle{x\mathop{\rightarrow}\limits^{A}\bar{x}\atop
t\downarrow 0}}}\frac{A-x}{t}$

  2. (ii)

The set

$\widehat{N}_{A}(\bar{x}):=(T_{A}(\bar{x}))^{\circ}$

is the regular (Fréchet) normal cone to $A$ at $\bar{x}$, and

$N_{A}(\bar{x}):=\mathop{{\rm Lim}\,{\rm sup}}\limits_{\stackrel{{\scriptstyle
A}}{{x\rightarrow\bar{x}}}}\widehat{N}_{A}(x)$

is the limiting (Mordukhovich) normal cone to $A$ at $\bar{x}$. Given a
direction $d\in\mathbb{R}^{s}$,

$N_{A}(\bar{x};d):=\mathop{{\rm Lim}\,{\rm
sup}}\limits_{\stackrel{{\scriptstyle t\downarrow 0}}{{d^{\prime}\rightarrow
d}}}\widehat{N}_{A}(\bar{x}+td^{\prime})$

is the directional limiting normal cone to $A$ at $\bar{x}$ in direction $d$.

In this definition ”$\mathop{{\rm Lim}\,{\rm sup}}$” stands for the Painlevé-
Kuratowski outer (upper) set limit, see, e.g.,[1]. If $A$ is convex, then
$\widehat{N}_{A}(\bar{x})=N_{A}(\bar{x})$ amounts to the classical normal cone
in the sense of convex analysis and we will write $N_{A}(\bar{x})$. By the
definition, the limiting normal cone coincides with the directional limiting
normal cone in direction $0$, i.e., $N_{A}(\bar{x})=N_{A}(\bar{x};0)$, and
$N_{A}(\bar{x};d)=\emptyset$ whenever $d\not\in T_{A}(\bar{x})$.

The above listed cones enable us to describe the local behavior of set-valued
maps via various generalized derivatives. All the set-valued mappings under
consideration are supposed to have locally closed graph around the points in
question.

######  Definition 2.2.

Consider a multifunction $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ and
let $(\bar{x},\bar{y})\in\mathrm{gph}\,F$.

  1. (i)

The multifunction
$DF(\bar{x},\bar{y}):\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ given by
$\mathrm{gph}\,DF(\bar{x},\bar{y})=T_{\mathrm{gph}\,F}(\bar{x},\bar{y})$ is
called the graphical derivative of $F$ at $(\bar{x},\bar{y})$.

  2. (ii)

The multifunction
$D_{*}F(\bar{x},\bar{y}):\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ given
by
$\mathrm{gph}\,D_{*}F(\bar{x},\bar{y})=T^{P}_{\mathrm{gph}\,F}(\bar{x},\bar{y})$
is called the strict (paratingent) derivative of $F$ at $(\bar{x},\bar{y})$.

  3. (iii)

The multifunction
$\widehat{D}^{\ast}F(\bar{x},\bar{y}):\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$
defined by

$\mathrm{gph}\,\widehat{D}^{\ast}F(\bar{x},\bar{y})=\\{(y^{*},x^{*})\mid\;(x^{*},-y^{*})\in\widehat{N}_{\mathrm{gph}\,F}(\bar{x},\bar{y})\\}$

is called the regular (Fréchet) coderivative of $F$ at $(\bar{x},\bar{y})$.

  4. (iv)

The multifunction
$D^{\ast}F(\bar{x},\bar{y}):\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$,
defined by

$\mathrm{gph}\,D^{\ast}F(\bar{x},\bar{y})=\\{(y^{*},x^{*})\mid\;(x^{*},-y^{*})\in
N_{\mathrm{gph}\,F}(\bar{x},\bar{y})\\}$

is called the limiting (Mordukhovich) coderivative of $F$ at
$(\bar{x},\bar{y})$.

  5. (v)

Given a pair of directions $(u,v)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$, the
multifunction
$D^{\ast}F((\bar{x},\bar{y});(u,v)):\mathbb{R}^{m}\rightrightarrows\mathbb{R}^{n}$,
defined by

$\mathrm{gph}\,D^{\ast}F((\bar{x},\bar{y});(u,v))=\\{(y^{*},x^{*})\mid\;(x^{*},-y^{*})\in
N_{\mathrm{gph}\,F}((\bar{x},\bar{y});(u,v))\\}$

is called the directional limiting coderivative of $F$ at $(\bar{x},\bar{y})$
in direction $(u,v)$.

The directional limiting normal cone and coderivative were introduced by the
first author in [12] and various properties of these objects can be found also
in [13] and in the references therein. Note that
$D^{\ast}F(\bar{x},\bar{y})=D^{\ast}F((\bar{x},\bar{y});(0,0))$ and that
$\mathrm{dom}\,D^{\ast}F((\bar{x},\bar{y});(u,v))=\emptyset$ whenever
$v\not\in DF(\bar{x},\bar{y})(u)$.

Note that by [34, Proposition 6.6] and the definition of the limiting
coderivative we have

$\mathrm{gph}\,D^{*}F(\bar{x},\bar{y})=\mathop{{\rm Lim}\,{\rm
sup}}_{(x,y)\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(\bar{x},\bar{y})}\mathrm{gph}\,D^{*}F(x,y).$
(1)

If $F$ is single-valued, we can omit the second argument and write $DF(x)$,
$\widehat{D}^{*}F(x),\ldots$ instead of $DF(x,F(x))$,
$\widehat{D}^{*}F(x,F(x)),\ldots$. However, be aware that when considering
limiting objects at $x$ where $F$ is not continuous, it is not enough to
consider only sequences $x_{k}\to x$ but we must work with sequences
$(x_{k},F(x_{k}))\to(x,F(x))$.

######  Definition 2.3.

Let $U\subset\mathbb{R}^{n}$ be open and let $F:U\to\mathbb{R}^{m}$ be a
mapping. The B-subdifferential of $F$ at $x\in U$ is defined as

$\overline{\nabla}F(x):=\\{A\mid\;\exists x_{k}\to x:\mbox{$F$ is Fr\'{e}chet
differentiable at $x_{k}$ and }A=\lim_{k\to\infty}\nabla F(x_{k})\\}$ (2)

Recall that the Clarke Generalized Jacobian is given by ${\rm
conv\,}\overline{\nabla}F(x)$, i.e., the convex hull of the B-subdifferential.

There exists the following relation between the B-subdifferential and the
coderivative of $F$, which states that every element from the
B-subdifferential defines a certain subspace contained in the graph of the
coderivative.

######  Proposition 2.4.

Let $U\subset\mathbb{R}^{n}$ be open and let $F:U\to\mathbb{R}^{m}$ be a
mapping. Let $F$ be continuous at $x\in U$ and let
$A\in\overline{\nabla}F(x)$. Then

$(y^{*},A^{T}y^{*})\in\mathrm{gph}\,D^{*}F(x)\ \forall
y^{*}\in\mathbb{R}^{m}.$

###### Proof.

Consider $A\in\overline{\nabla}F(x)$ together with some sequence $x_{k}\to x$
such that $\nabla F(x_{k})\to A$ as $k\to\infty$. By [34, Example 9.25(b)] we
have $T_{\mathrm{gph}\,F}(x_{k},F(x_{k}))=\\{(u,\nabla
F(x_{k})u)\mid\;u\in\mathbb{R}^{n}\\}$ and therefore $(y^{*},\nabla
F(x_{k})^{T}y^{*})\in\mathrm{gph}\,\widehat{D}^{*}F(x_{k})$, $\forall
y^{*}\in\mathbb{R}^{m}$. By passing to the limit, the assertion follows from
the definition of the limiting coderivative. ∎

If the mapping $F:U\to\mathbb{R}^{m}$ is Lipschitz continuous, by Rademacher’s
Theorem $F$ is differentiable almost everywhere in $U$ and $\|\nabla F(x)\|$
is bounded there by the Lipschitz constant of $F$. Thus
$\overline{\nabla}F(\bar{x})\not=\emptyset$ for Lipschitz continuous mappings
$F$.

Let $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ be an extended-real-valued function
with the domain and the epigraph

$\mathrm{dom}\,q:=\\{x\in\mathbb{R}^{n}\mid\;q(x)<\infty\\},\quad\mathrm{epi}\,q:=\\{(x,\alpha)\in\mathbb{R}^{n}\times\mathbb{R}\mid\;\alpha\geq
q(x)\\}.$

The (limiting/Mordukhovich) subdifferential of $q$ at
$\bar{x}\in\mathrm{dom}\,q$ is defined geometrically by

$\partial q(\bar{x}):=\\{x^{*}\in\mathbb{R}^{n}\mid\;(x^{*},-1)\in
N_{\mathrm{epi}\,q}(\bar{x},q(\bar{x}))\\}.$

This subdifferential is a general extension of the classical gradient for
smooth functions and of the classical subdifferential of convex ones.

If $q(\bar{x})$ is finite, define the parametric family of second-order
difference quotients for $q$ at $\bar{x}$ for
${\bar{x}^{\ast}}\in\mathbb{R}^{n}$ by

$\Delta_{t}^{2}q(\bar{x},{\bar{x}^{\ast}})(w):=\frac{q(\bar{x}+tw)-q(\bar{x})-t\langle{\bar{x}^{\ast}},w\rangle}{\frac{1}{2}t^{2}}\quad\mbox{
with $w\in\mathbb{R}^{n}$, $t>0$.}$

The second-order subderivative of $q$ at $\bar{x}$ for ${\bar{x}^{\ast}}$ is
given by

${\rm d^{2}}q(\bar{x},{\bar{x}^{\ast}})(w)=\liminf_{{\textstyle{t\downarrow
0\atop w^{\prime}\to
w}}}\Delta_{t}^{2}q(\bar{x},{\bar{x}^{\ast}})(w^{\prime}).$

$q$ is called twice epi-differentiable at $\bar{x}$ for ${\bar{x}^{\ast}}$, if
the functions $\Delta_{t}^{2}q(\bar{x},{\bar{x}^{\ast}})$ epi-converge to
${\rm d^{2}}q(\bar{x},{\bar{x}^{\ast}})$ as $t\downarrow 0$.

Let us now recall the following regularity notions.

######  Definition 2.5.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ be a mapping and let
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$.

  1. 1.

$F$ is said to be metrically subregular at $(\bar{x},\bar{y})$ if there exists
$\kappa\geq 0$ along with some neighborhood $X$ of $\bar{x}$ such that

$\operatorname{dist}(x,F^{-1}(\bar{y}))\leq\kappa\operatorname{dist}(\bar{y},F(x))\
\forall x\in X.$ (3)

The infimum over all $\kappa\geq 0$ such that (3) holds for some neighborhood
$X$ is denoted by ${\rm subreg\,}F(\bar{x},\bar{y})$.

  2. 2.

$F$ is said to be strongly metrically subregular at $(\bar{x},\bar{y})$ if it
is metrically subregular at $(\bar{x},\bar{y})$ and there exists a
neighborhood $X^{\prime}$ of $\bar{x}$ such that $F^{-1}(\bar{y})\cap
X^{\prime}=\\{\bar{x}\\}$.

  3. 3.

$F$ is said to be metrically regular around $(\bar{x},\bar{y})$ if there is
$\kappa\geq 0$ together with neighborhoods $X$ of $\bar{x}$ and $Y$ of
$\bar{y}$ such that

$\operatorname{dist}(x,F^{-1}(y))\leq\kappa\operatorname{dist}(y,F(x))\
\forall(x,y)\in X\times Y.$ (4)

The infimum over all $\kappa\geq 0$ such that (4) holds for some neighborhoods
$X,Y$ is denoted by ${\rm reg\,}F(\bar{x},\bar{y})$.

  4. 4.

$F$ is said to be strongly metrically regular around $(\bar{x},\bar{y})$ if it
is metrically regular around $(\bar{x},\bar{y})$ and $F^{-1}$ has a single-
valued localization around $(\bar{y},\bar{y})$, i.e., there are open
neighborhoods $Y^{\prime}$ of $\bar{y}$, $X^{\prime}$ of $\bar{x}$ and a
mapping $h:Y^{\prime}\to\mathbb{R}^{n}$ with $h(\bar{y})=\bar{x}$ such that
$\mathrm{gph}\,F\cap(X^{\prime}\times Y^{\prime})=\\{(h(y),y)\mid\;y\in
Y^{\prime}\\}$.

It is well-known, see, e.g., [10] that the property of (strong) metric
subregularity for $F$ at $(\bar{x},\bar{y})$ is equivalent with the property
of (isolated) calmness for $F^{-1}$ at $(\bar{y},\bar{x})$. Further, $F$ is
metrically regular around $(\bar{x},\bar{y})$ if and only if the inverse
mapping $F^{-1}$ has the so-called Aubin property around $(\bar{y},\bar{x})$.
In this paper we will frequently use the following characterization of strong
metric regularity.

######  Theorem 2.6 ( cf. [10, Proposition 3G.1]).

$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is strongly metrically
regular around $(\bar{x},\bar{y})$ if and only if $F^{-1}$ has a Lipschitz
continuous localization $h$ around $(\bar{y},\bar{x})$. In this case there
holds

${\rm
reg\,}F(\bar{x},\bar{y})=\limsup_{{\textstyle{y,y^{\prime}\to\bar{y}\atop
y\not=y^{\prime}}}}\frac{\|h(y)-h(y^{\prime})\|}{\|y-y^{\prime}\|}.$

In this paper we will also use the following point-based characterizations of
the above regularity properties.

######  Theorem 2.7.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ be a mapping and let
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$.

  1. (i)

(Levy-Rockafellar criterion) $F$ is strongly metrically subregular at
$(\bar{x},\bar{y})$ if and only if

$0\in DF(\bar{x},\bar{y})(u)\ \Rightarrow u=0.$ (5)

and in this case one has

${\rm
subreg\,}F(\bar{x},\bar{y})=\sup\\{\|u\|\mid\;(u,v)\in\mathrm{gph}\,DF(\bar{x},\bar{y}),\
\|v\|\leq 1\\}.$

  2. (ii)

(Mordukhovich criterion) $F$ is metrically regular around $(\bar{x},\bar{y})$
if and only if

$0\in D^{*}F(\bar{x},\bar{y})(y^{*})\ \Rightarrow\ y^{*}=0.$ (6)

Further, in this case one has

${\rm
reg\;}F(\bar{x},\bar{y})=\sup\\{\|y^{*}\|\mid\;(y^{*},x^{*})\in\mathrm{gph}\,D^{*}F(\bar{x},\bar{y}),\
\|x^{*}\|\leq 1\\}.$ (7)

  3. (iii)

$F$ is strongly metrically regular around $(\bar{x},\bar{y})$ if and only if

$0\in D_{*}F(\bar{x},\bar{y})(u)\ \Rightarrow\ u=0$ (8)

and (6) holds. In this case one also has

${\rm
reg\;}F(\bar{x},\bar{y})=\sup\\{\|u\|\mid\;(u,v)\in\mathrm{gph}\,D_{*}F(\bar{x},\bar{y}),\
\|v\|\leq 1\\}.$ (9)

###### Proof.

Statement (i) follows from [10, Theorem 4E.1]. Statement (ii) can be found in
[22, Theorem 3.3]. The criterion for strong metric regularity follows from
Dontchev and Frankowska [8, Theorem 16.2] by taking into account that the
condition $\bar{x}\in\liminf_{y\to\bar{y}}F^{-1}(y)$ appearing in [8, Theorem
16.2] can be ensured by the requirement that $F$ is metrically regular which
in turn can be characterized by the Mordukhovich criterion. ∎

For a sufficient condition for metric subregularity based on directional
limiting coderivatives we refer to [13].

The properties of (strong) metric regularity and strong metric subregularity
are stable under Lipschitzian and calm perturbations, respectively, cf. [10].
Further note that the property of (strong) metric regularity holds around all
points belonging to the graph of $F$ sufficiently close to the reference
point, whereas the property of (strong) metric subregularity is guaranteed to
hold only at the reference point. This leads to the following definition.

######  Definition 2.8.

We say that the mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is
(strongly) metrically subregular around $(\bar{x},\bar{y})\in\mathrm{gph}\,F$
if there is a neighborhood $W$ of $(\bar{x},\bar{y})$ such that $F$ is
(strongly) metrically subregular at every point $(x,y)\in\mathrm{gph}\,F\cap
W$ and we define

${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y}):=\limsup_{(x,y)\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(\bar{x},\bar{y})}{\rm
subreg\,}F(x,y)<\infty.$

In this case we will also speak about (strong) metric subregularity on a
neighborhood.

Note that every polyhedral multifunction, i.e., a mapping whose graph is the
union of finitely many convex polyhedral sets, is metrically subregular around
every point of its graph by Robinson’s result [32]. In Section 6,
characterizations of strong metric subregularity on a neighborhood will be
investigated.

Next we introduce the semismooth∗ sets and mappings.

######  Definition 2.9.

(cf. [14].)

  1. 1.

A set $A\subseteq\mathbb{R}^{s}$ is called semismooth∗ at a point $\bar{x}\in
A$ if for all $u\in\mathbb{R}^{s}$ it holds

$\langle x^{*},u\rangle=0\quad\forall x^{*}\in N_{A}(\bar{x};u).$ (10)

  2. 2.

A set-valued mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is
called semismooth∗ at a point $(\bar{x},\bar{y})\in\mathrm{gph}\,F$, if
$\mathrm{gph}\,F$ is semismooth∗ at $(\bar{x},\bar{y})$, i.e., for all
$(u,v)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ we have

$\langle u^{*},u\rangle=\langle
v^{*},v\rangle\quad\forall(v^{*},u^{*})\in\mathrm{gph}\,D^{*}F((\bar{x},\bar{y});(u,v)).$
(11)

The class of semismooth* mappings is rather broad. We list here two important
classes of multifunctions having this property.

######  Proposition 2.10.

  1. (i)

Every mapping whose graph is the union of finitely many closed convex sets is
semismooth∗ at every point of its graph.

  2. (ii)

Every mapping with closed subanalytic graph is semismooth∗ at every point of
its graph.

###### Proof.

The first assertion was already shown in [14, Proposition 3.4, 3.5]. As
mentioned in [14, Remark 3.10], the semismooth∗ property of sets amounts to
the notion of semismoothness introduced in [16]. It follows thus from [19,
Theorem 2], that all closed subanalytic sets are automatically semismooth∗ and
the second statement holds by the definition of semismooth∗ mappings. ∎

The statement of Proposition 2.10(ii) can be considered as the counterpart to
[4], where it is shown that locally Lipschitz tame mappings
$F:U\subseteq\mathbb{R}^{n}\to\mathbb{R}^{m}$ are semismooth in the sense of
Qi and Sun [30]. In case of single-valued Lipschitzian mappings the
semismooth∗ property is equivalent with the semismooth property introduced by
Gowda [15], which is weaker than the one in [30].

In the above definition the semismooth∗ sets and mappings have been defined
via directional limiting normal cones and coderivatives. For our purpose it is
convenient to make use of equivalent characterizations in terms of standard
(regular and limiting) normal cones and coderivatives, respectively.

######  Proposition 2.11 (cf.[14, Corollary 3.3]).

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ and
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$ be given. Then the following three
statements are equivalent

  1. (i)

$F$ is semismooth∗ at $(\bar{x},\bar{y})$.

  2. (ii)

For every $\epsilon>0$ there is some $\delta>0$ such that

$|\langle x^{*},x-\bar{x}\rangle-\langle
y^{*},y-\bar{y}\rangle|\leq\epsilon\|(x,y)-(\bar{x},\bar{y})\|\|(x^{*},y^{*})\|\
\forall(x,y)\in{\cal B}_{\delta}(\bar{x},\bar{y})\
\forall(y^{*},x^{*})\in\mathrm{gph}\,\widehat{D}^{*}F(x,y).$ (12)

  3. (iii)

For every $\epsilon>0$ there is some $\delta>0$ such that

$|\langle x^{*},x-\bar{x}\rangle-\langle
y^{*},y-\bar{y}\rangle|\leq\epsilon\|(x,y)-(\bar{x},\bar{y})\|\|(x^{*},y^{*})\|\
\forall(x,y)\in{\cal B}_{\delta}(\bar{x},\bar{y})\
\forall(y^{*},x^{*})\in\mathrm{gph}\,D^{*}F(x,y).$ (13)

##  3 SCD mappings

In what follows we denote by ${\cal Z}_{n}$ the metric space of all
$n$-dimensional subspaces of $\mathbb{R}^{2n}$ equipped with the metric

$d_{\cal Z}(L_{1},L_{2}):=\|P_{1}-P_{2}\|$

where $P_{i}$ is the symmetric $2n\times 2n$ matrix representing the
orthogonal projection on $L_{i}$, $i=1,2$.

Sometimes we will also work with bases for the subspaces $L\in{\cal Z}_{n}$.
Let ${\cal M}_{n}$ denote the collection of all $2n\times n$ matrices with
full rank $n$ and for $L\in{\cal Z}_{n}$ we define

${\cal M}(L):=\\{Z\in{\cal M}_{n}\mid\;{\rm rge\;}Z=L\\},$

i.e., the columns of $Z\in{\cal M}(L)$ are a basis for $L$. Further we denote
by ${\cal M}^{\rm orth}(L)$ the set of all matrices $Z\in{\cal M}(L)$ with
$Z^{T}Z=I$, i.e., the columns of $Z$ are an orthogonal basis for $L$. Recall
that, given any matrix $\bar{Z}\in{\cal M}(L)$ ( or $\bar{Z}\in{\cal M}^{\rm
orth}(L)$), there holds

${\cal M}(L)=\\{\bar{Z}B\mid\;B\mbox{ nonsingular $n\times n$
matrix}\\}\quad({\cal M}^{\rm orth}(L)=\\{\bar{Z}B\mid\;B\mbox{ orthogonal
$n\times n$ matrix}\\}).$

Further recall that the $2n\times 2n$ matrix $P$, representing the orthogonal
projection on some $L\in{\cal Z}_{n}$, admits the representations

$P=Z(Z^{T}Z)^{-1}Z^{T},\ Z\in{\cal M}(L)\quad\mbox{and}\quad P=ZZ^{T},\
Z\in{\cal M}^{\rm orth}(L).$ (14)

######  Lemma 3.1.

  1. (i)

Let $Z_{k}\in{\cal M}_{n}$ be a sequence converging to some $Z\in{\cal
M}_{n}$. Then ${\rm rge\;}Z_{k}$ converges in ${\cal Z}_{n}$ to ${\rm
rge\;}Z\in{\cal Z}_{n}$.

  2. (ii)

Let $L_{k}\in{\cal Z}_{n}$ be a sequence converging to $L\in{\cal Z}_{n}$.
Then there is a sequence $Z_{k}\in{\cal M}(L_{k})$ converging to some
$Z\in{\cal M}(L)$.

  3. (iii)

Let $A_{k}$ be a sequence of nonsingular $2n\times 2n$ matrices converging to
a nonsingular matrix $A$ and let $L_{k}\in{\cal Z}_{n}$ be a sequence
converging to $L\in{\cal Z}_{n}$. Then $\lim_{k\to\infty}d_{\cal
Z}(A_{k}L_{k},AL)=0$.

  4. (iv)

The metric space ${\cal Z}_{n}$ is compact.

  5. (v)

Let $L_{k}\in{\cal Z}_{n}$ be a sequence and let $L\in{\cal Z}_{n}$. Then
$L_{k}$ converges to $L$ in ${\cal Z}_{n}$, i.e., $\lim_{k\to\infty}d_{\cal
Z}(L_{k},L)=0$, if and only if $\lim_{k\to\infty}L_{k}=L$ in the sense of
Painlevé-Kuratowski convergence.

###### Proof.

The first statement follows immediately from
$Z(Z^{T}Z)^{-1}Z^{T}=\lim_{k\to\infty}Z_{k}(Z_{k}^{T}Z_{k})^{-1}Z_{k}^{T}$
together with (14). In order to prove (ii), choose $Z_{k}\in{\cal M}^{\rm
orth}(L_{k})$ and $Z\in{\cal M}^{\rm orth}(L)$. Then
$ZZ^{T}=\lim_{k\to\infty}Z_{k}Z_{k}^{T}$ due to
$L_{k}\mathop{\longrightarrow}\limits^{{\cal Z}_{n}}L$ and consequently
$Z=ZZ^{T}Z=\lim_{k\to\infty}\tilde{Z}_{k}$ with
$\tilde{Z}_{k}:=Z_{k}(Z_{k}^{T}Z)$. Hence, for sufficiently large $k$ we have
$\tilde{Z}_{k}\in{\cal M}_{n}$ and $\tilde{Z}_{k}\in{\cal M}(L_{k})$ follows.
This proves (ii) and (iii) follows from (ii) and (i). In order to prove the
compactness of ${\cal Z}_{n}$, consider a sequence $L_{k}\in{\cal Z}_{n}$
together with basis matrices $Z_{k}\in{\cal M}^{\rm orth}(L_{k})$. By possibly
passing to a subsequence we may assume that $Z_{k}$ converges to some $Z$.
Since $Z^{T}Z=\lim_{k\to\infty}Z_{k}^{T}Z_{k}=I$, we conclude $Z\in{\cal
M}_{n}$ and ${\rm rge\;}Z=\lim_{k\to\infty}L_{k}\in{\cal Z}_{n}$ by (i). Hence
the metric space ${\cal Z}_{n}$ is (sequentially) compact. Finally, by [34,
Example 5.35] there holds $L_{k}\to L$ in the sense of Painlevé-Kuratowski
convergence if and only if the projections $P_{L_{k}}$ on $L_{k}$ converge
graphically to the projection $P_{L}$ on $L$. Since the projections on
subspaces in ${\cal Z}_{n}$ are linear mappings with norm equal to $1$,
graphical convergence of $P_{L_{k}}$ to $P_{L}$ is equivalent to uniform
convergence $\lim_{k\to\infty}\|P_{L_{k}}-P_{L}\|=0$ by [34, Theorems 5.43,
5.44]. ∎

We treat every element of $\mathbb{R}^{2n}$ as a column vector. In order to
keep our notation simple we write $(u,v)$ instead of
$\left(\begin{array}[]{c}u\\\ v\end{array}\right)\in\mathbb{R}^{2n}$ when this
does not lead to confusion. In order to refer to the components of the vector
$z=\left(\begin{array}[]{c}u\\\ v\end{array}\right)$ we set $\pi_{1}(z):=u,\
\pi_{2}(z):=v$.

Let $L\in{\cal Z}_{n}$ and consider $Z\in{\cal M}(L)$, which can be written in
the form $Z=\left(\begin{array}[]{c}A\\\ B\end{array}\right)$. But we will
rather write it as $Z=(A,B)$; thus ${\rm
rge\;}(A,B):=\\{(Au,Bu)\mid\;u\in\mathbb{R}^{n}\\}\doteq\Big{\\{}\left(\begin{array}[]{c}Au\\\
Bu\end{array}\right)\mid\;u\in\mathbb{R}^{n}\Big{\\}}=L$. Similarly as before,
we will also use $\pi_{1}(Z):=A$, $\pi_{2}(Z):=B$ for referring to the two
$n\times n$ parts of $Z$.

Further, for every $L\in{\cal Z}_{n}$ we define

$\displaystyle L^{*}$ $\displaystyle:=\\{(-v^{*},u^{*})\mid\;(u^{*},v^{*})\in
L^{\perp}\\},$ (15)

where $L^{\perp}$ denotes as usual the orthogonal complement of $L$. Note that

$(L^{*})^{\perp}=\\{(v,u)\mid\;\langle v,-v^{*}\rangle+\langle
u,u^{*}\rangle=0\ \forall(u^{*},v^{*})\in
L^{\perp}\\}=\\{(v,u)\mid\;(u,-v)\in(L^{\perp})^{\perp}\\}$

and therefore

$\displaystyle(L^{*})^{*}=\\{(u,v)\mid\;(v,-u)\in(L^{*})^{\perp}\\}=\\{(u,v)\mid\;(-u,-v)\in
L\\}=L.$

We denote by $S_{n}$ the $2n\times 2n$ orthogonal matrix

$S_{n}:=\left(\begin{matrix}0&-I\\\ I&0\end{matrix}\right),$

so that $L^{*}=S_{n}L^{\perp}$. If $P$ represents the orthogonal projection on
$L$ then $I-P$ is the orthogonal projection on $L^{\perp}$ and
$S_{n}(I-P)S_{n}^{T}$ is the orthogonal projection on $L^{*}$. Given two
subspaces $L_{1},L_{2}\in{\cal Z}_{n}$ with orthogonal projections
$P_{1},P_{2}$, we obtain

$d_{\cal
Z}(L_{1}^{*},L_{2}^{*})=\|S_{n}(I-P_{1})S_{n}^{T}-S_{n}(I-P_{2})S_{n}^{T}\|=\|S_{n}(I-P_{1}-(I-P_{2}))S_{n}^{T}\|=\|P_{1}-P_{2}\|=d_{\cal
Z}(L_{1},L_{2}).$

Thus the mapping $L\mapsto L^{*}$ defines an isometry on ${\cal Z}_{n}$ and a
sequence $(L_{k})$ converges in ${\cal Z}_{n}$ to some $L$ if and only if the
sequence $(L_{k}^{*})$ converges to $L^{*}$.

Consider the following relation between the graphical derivative and
differentiability in case of single-valued mappings.

######  Lemma 3.2.

Consider $f:U\to\mathbb{R}^{n}$ with $U\subseteq\mathbb{R}^{n}$ open and a
point $x\in U$. Then one has:

  1. (i)

If $f$ is Fréchet differentiable at $x$, then $DF(x)$ is a single-valued
linear mapping, $DF(x)(u)=\nabla f(x)u$, $u\in\mathbb{R}^{n}$, and
consequently $T_{\mathrm{gph}\,f}(x,f(x))={\rm rge\;}(I,\nabla f(x))\in{\cal
Z}_{n}$.

  2. (ii)

Conversely, if $T_{\mathrm{gph}\,f}(x,f(x))\in{\cal Z}_{n}$ and $f$ is calm at
$x$, i.e., there is some $\kappa\geq 0$ such that the estimate
$\|f(x^{\prime})-f(x)\|\leq\kappa\|x^{\prime}-x\|$ holds for all $x^{\prime}$
sufficiently close to $x$, then $f$ is Fréchet differentiable at $x$.

###### Proof.

The statement (i) follows immediately from [34, Exercise 9.25]. In order to
show (ii), we first prove that there is an $n\times n$ matrix $A$ such that
$T_{\mathrm{gph}\,f}(x,f(x))={\rm rge\;}(I,A)$. Considering any $Z\in{\cal
M}(T_{\mathrm{gph}\,f}(x,f(x)))$, we will show that $B:=\pi_{1}(Z)$ is
nonsingular. Assuming on the contrary that $B$ is singular, there is some
$p\not=0$ with $Bp=0$. Then $v:=\pi_{2}(Z)p\not=0$ because otherwise $Zp=0$
which is not possible. Hence $(0,v)=Zp\in T_{\mathrm{gph}\,f}$ and there
exists sequences $t_{k}\downarrow 0$ and $(u_{k},v_{k})\to(u,v)$ such that
$f(x)+t_{k}v_{k}=f(x+t_{k}u_{k})$ $\forall k$ implying
$t_{k}\|v_{k}\|=\|f(x+t_{k}u_{k})-f(x)\|\leq\kappa t_{k}\|u_{k}\|$ and
$\|v\|=\lim_{k\to\infty}\|u_{k}\|=0$, a contradiction. Hence $B$ is
nonsingular and we obtain $T_{\mathrm{gph}\,f}(x,f(x))={\rm
rge\;}(B,\pi_{2}(Z))={\rm rge\;}(I,\pi_{2}(Z)B^{-1})$ proving our claim with
$A=\pi_{2}(Z)B^{-1}$. Hence $Df(x)u=Au$, $u\in\mathbb{R}^{n}$ and the
assertion follows once more from [34, Exercise 9.25]. ∎

Note that, when $f:U\to\mathbb{R}^{n}$, $U\subseteq\mathbb{R}^{n}$ open, is
Fréchet differentiable at $u\in U$, then we even have
$T_{\mathrm{gph}\,f}(u,f(u))={\rm Lim}_{t\downarrow
0}t^{-1}(\mathrm{gph}\,f-(u,f(u)))$.

We now introduce new generalized derivatives for set-valued mappings. We
confine ourselves to the particular case
$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and, as we will see in the
sequel, this restriction still permits a considerable number of applications.

######  Definition 3.3.

Consider a mapping $F:R^{n}\rightrightarrows\mathbb{R}^{n}$.

  1. 1.

We say that $F$ is graphically smooth of dimension $n$ at
$(x,y)\in\mathrm{gph}\,F$, if
$T_{\mathrm{gph}\,F}(x,y)=\mathrm{gph}\,DF(x,y)\in{\cal Z}_{n}$. Further we
denote by ${\cal O}_{F}$ the set of all points where $F$ is graphically smooth
of dimension $n$.

  2. 2.

Associate with $F$ the four mappings $\widehat{\cal S}F$, $\widehat{\cal
S}^{*}F$, ${\cal S}F$, ${\cal S}^{*}F$, all of which map
$\mathrm{gph}\,F\rightrightarrows{\cal Z}_{n}$ and are given by

$\displaystyle\widehat{\cal S}F(x,y)$
$\displaystyle:=\begin{cases}\\{\mathrm{gph}\,DF(x,y)\\}&\mbox{if
$(x,y)\in{\cal O}_{F}$,}\\\ \emptyset&\mbox{else,}\end{cases}$
$\displaystyle\widehat{\cal S}^{*}F(x,y)$
$\displaystyle:=\begin{cases}\\{\mathrm{gph}\,DF(x,y)^{*}\\}&\mbox{if
$(x,y)\in{\cal O}_{F}$,}\\\ \emptyset&\mbox{else,}\end{cases}$
$\displaystyle{\cal S}F(x,y)$ $\displaystyle:=\mathop{{\rm Lim}\,{\rm
sup}}_{(u,v)\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(x,y)}\widehat{\cal
S}F(u,v)$ $\displaystyle=\\{L\in{\cal
Z}_{n}\mid\;\exists(x_{k},y_{k})\mathop{\longrightarrow}\limits^{{{\cal
O}_{F}}}(x,y):\ \lim_{k\to\infty}d_{\cal
Z}(L,\mathrm{gph}\,DF(x_{k},y_{k}))=0\\},$ $\displaystyle{\cal S}^{*}F(x,y)$
$\displaystyle=\mathop{{\rm Lim}\,{\rm
sup}}_{(u,v)\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(x,y)}\widehat{\cal
S}^{*}F(u,v)$ $\displaystyle=\\{L\in{\cal
Z}_{n}\mid\;\exists(x_{k},y_{k})\mathop{\longrightarrow}\limits^{{{\cal
O}_{F}}}(x,y):\ \lim_{k\to\infty}d_{\cal
Z}(L,\mathrm{gph}\,DF(x_{k},y_{k})^{*})=0\\}.$

  3. 3.

    1. (a)

We say that $F$ has the SCD  (subspace containing derivative) property at
$(x,y)\in\mathrm{gph}\,F$, if ${\cal S}^{*}F(x,y)\not=\emptyset$.

    2. (b)

We say that $F$ has the SCD property around $(x,y)\in\mathrm{gph}\,F$, if
there is a neighborhood $W$ of $(x,y)$ such that $F$ has the SCD property at
every $(x^{\prime},y^{\prime})\in\mathrm{gph}\,F\cap W$.

    3. (c)

Finally, we call $F$ an SCD mapping if $F$ has the SCD property at every point
of its graph.

Apart from the collections ${\cal S}F(x,y)$ and ${\cal S}^{*}F(x,y)$ of
subspaces we will sometimes use the unions

$\bigcup{\cal S}F(x,y):=\bigcup_{L\in{\cal S}F(x,y)}L,\quad\bigcup{\cal
S}^{*}F(x,y):=\bigcup_{L\in{\cal S}^{*}F(x,y)}L.$ (16)

######  Remark 3.4.

By definition of the regular coderivative there holds

$\mathrm{gph}\,\widehat{D}^{*}F(x,y)=\mathrm{gph}\,DF(x,y)^{*},\ (x,y)\in{\cal
O}_{F}.$

######  Remark 3.5.

Since $L\mapsto L^{*}$ is an isometry on ${\cal Z}_{n}$ and $(L^{*})^{*}=L$,
we have

${\cal S}^{*}F(x,y)=\\{L^{*}\mid\;L\in{\cal S}F(x,y)\\},\quad{\cal
S}F(x,y)=\\{L^{*}\mid\;L\in{\cal S}^{*}F(x,y)\\}.$

Hence, $F$ has the SCD property at $(x,y)\in\mathrm{gph}\,F$ if and only if
${\cal S}F(x,y)\not=\emptyset$.

Since we consider convergence in the compact metric space ${\cal Z}_{n}$, we
obtain readily the following result.

######  Lemma 3.6.

A mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ has the SCD
property at $(x,y)\in\mathrm{gph}\,F$ if and only if $(x,y)\in{\rm cl\,}{\cal
O}_{F}$. Further, $F$ is an SCD mapping if and only if ${\rm cl\,}{\cal
O}_{F}={\rm cl\,}\mathrm{gph}\,F$, i.e., $F$ is graphically smooth of
dimension $n$ at the points of a dense subset of its graph.

The name ”SCD property” is motivated by the following statement.

######  Lemma 3.7.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and let
$(x,y)\in\mathrm{gph}\,F$. Then $\bigcup{\cal
S}^{*}F(x,y)\subseteq\mathrm{gph}\,D^{*}F(x,y)$.

###### Proof.

Let $L\in{\cal S}^{*}F(x,y)$ and consider a sequence
$(x_{k},y_{k},L_{k})\to(x,y,L)$ with $(x_{k},y_{k})\in{\cal O}_{F}$ and
$L_{k}:=(\mathrm{gph}\,DF(x_{k},y_{k}))^{*}\in\widehat{\cal
S}^{*}F(x_{k},y_{k})$. By Remark 3.4 we have
$L_{k}=\mathrm{gph}\,\widehat{D}^{*}F(x_{k},y_{k})$. Consider $Z_{k}\in{\cal
M}^{\rm orth}(L_{k})$. By possibly passing to a subsequence the matrices
$Z_{k}$ converge to some $Z$ and $L={\rm rge\;}Z$ by Lemma 3.2. Taking into
account $Z_{k}p\in L_{k}=\mathrm{gph}\,\widehat{D}^{*}F(x_{k},y_{k})$, we
obtain $Zp=\lim_{k\to\infty}Z_{k}p\in\mathrm{gph}\,D^{*}F(x,y)$ $\forall
p\in\mathbb{R}^{n}$ by the Definitions 2.1, 2.2 showing that
$L\subseteq\mathrm{gph}\,D^{*}F(x,y)$. Since this holds for every $L\in{\cal
S}^{*}F(x,y)$, the assertion follows. ∎

We will now show that the primal subspaces $L\in{\cal S}F(x,y)$ also belong to
the graph of some suitable generalized derivative mapping. Consider the
following definition.

######  Definition 3.8.

  1. 1.

Let $A\subset\mathbb{R}^{n}$ and let $\bar{x}\in A$. The outer limiting
tangent cone to $A$ at $\bar{x}$ is defined as

$T^{\sharp}_{A}(\bar{x}):=\mathop{{\rm Lim}\,{\rm
sup}}_{x\mathop{\rightarrow}\limits^{A}\bar{x}}T_{A}(x)=\mathop{{\rm
Lim}\,{\rm sup}}_{x\mathop{\rightarrow}\limits^{A}\bar{x}}\Big{(}\mathop{{\rm
Lim}\,{\rm sup}}_{t\downarrow 0}\frac{A-x}{t}\Big{)}$ (17)

  2. 2.

Consider a multifunction $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ and
let $(\bar{x},\bar{y})\in\mathrm{gph}\,F$. The outer limiting graphical
derivative of $F$ at $(\bar{x},\bar{y})$ is the multifunction
$D^{\sharp}F(\bar{x},\bar{y}):\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$
given by

$\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y})=T^{\sharp}_{\mathrm{gph}\,F}(\bar{x},\bar{y}).$

######  Remark 3.9.

Comparing (17) with the definition of the paratingent cone
$T^{P}_{A}(\bar{x})$ it follows that $T^{\sharp}_{A}(\bar{x})\subseteq
T^{P}_{A}(\bar{x})$ and therefore $D^{\sharp}F(\bar{x},\bar{y})(u)\subseteq
D_{*}F(\bar{x},\bar{y})(u)$, $u\in\mathbb{R}^{n}$.

Using similar arguments as in the proof of Lemma 3.7 one obtains the following
result.

######  Lemma 3.10.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and let
$(x,y)\in\mathrm{gph}\,F$. Then $\bigcup{\cal
S}F(x,y)\subseteq\mathrm{gph}\,D^{\sharp}F(x,y)$.

For single-valued mappings the constructions of Definition 3.3 are related to
the B-subdifferential.

######  Lemma 3.11.

Let $U\subset\mathbb{R}^{n}$ be open and let $f:U\to\mathbb{R}^{n}$ be
continuous. Then for every $x\in U$ there holds

$\displaystyle{\cal S}f(x):={\cal S}(x,f(x))\supseteq\\{{\rm
rge\;}(I,A)\mid\;A\in\overline{\nabla}f(x)\\},$ (18) $\displaystyle{\cal
S}^{*}f(x):={\cal S}^{*}(x,f(x))\supseteq\\{{\rm
rge\;}(I,A^{T})\mid\;A\in\overline{\nabla}f(x)\\}.$ (19)

If $f$ is Lipschitz continuous near $x$, these inclusions hold with equality
and $f$ has the SCD property around $x$.

###### Proof.

Consider $x\in U$ and $A\in\overline{\nabla}f(x)$ together with sequences
$x_{k}\to x$ and $\nabla f(x_{k})\to A$. Then for each $k$ we have
$T_{\mathrm{gph}\,f}(x_{k},f(x_{k}))={\rm rge\;}(I,\nabla
f(x_{k}))=:L_{k}\in{\cal Z}_{n}$ by Lemma 3.2 implying that
$(x_{k},f(x_{k}))\in{\cal O}_{f}$ and $\widehat{\cal S}f(x_{k})=\\{L_{k}\\}$.
Thus the subspaces $L_{k}$ converge in ${\cal Z}_{n}$ to ${\rm
rge\;}(I,A)\in{\cal S}f(x)$ by Lemma 3.1(i). This proves (18). By taking into
account the identity ${\rm rge\;}(I,A)^{\perp}={\rm rge\;}(-A^{T},I)$, it
follows that ${\rm rge\;}(I,A)^{*}={\rm rge\;}(I,A^{T})$ verifying (19). Now
assume that $f$ is Lipschitzian near $x$ and consider $L\in{\cal S}f(x)$
together with a sequence
$(x_{k},f(x_{k}))\mathop{\longrightarrow}\limits^{{{\cal O}_{f}}}(x,f(x))$
such that
$L_{k}:=T_{\mathrm{gph}\,f}(x_{k},f(x_{k}))\mathop{\longrightarrow}\limits^{{{\cal
Z}_{n}}}L$. By Lemma 3.2 we conclude that $f$ is differentiable at $x_{k}$ and
$L_{k}={\rm rge\;}(I,\nabla f(x_{k}))$. By Lipschitz continuity of $f$ the
derivatives $\nabla f(x_{k})$ are bounded. Hence, by possibly passing to a
subsequence, we can assume that $\nabla f(x_{k})$ converges to some
$A\in\overline{\nabla}f(x)$ and $L_{k}\mathop{\longrightarrow}\limits^{{{\cal
Z}_{n}}}{\rm rge\;}(I,A)$ follows. This proves equality in (18) and equality
in (19) easily follows from the identity ${\rm rge\;}(I,A)^{*}={\rm
rge\;}(I,A^{T})$. Since $\overline{\nabla}f(x)\not=\emptyset$ for Lipschitz
continuous mappings, the SCD property at $x$ is established. This also holds
for every point sufficiently close to $x$ and thus $f$ has the SCD property
even around $x$. ∎

######  Remark 3.12.

In particular, every Lipschitz continuous mapping $f:U\to\mathbb{R}^{n}$ with
$U\subseteq\mathbb{R}^{n}$ open is an SCD mapping. However, the converse is
not true: Consider the function $f(x)=\sqrt{|x|}$ which is an SCD mapping but
not Lipschitz continuous.

######  Lemma 3.13.

Consider a mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and let
$(x,y)\in\mathrm{gph}\,F$. Then

${\cal S}F(x,y)=\mathop{{\rm Lim}\,{\rm
sup}}_{(u,v)\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(x,y)}{\cal
S}F(u,v),\quad{\cal S}^{*}F(x,y)=\mathop{{\rm Lim}\,{\rm
sup}}_{(u,v)\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(x,y)}{\cal
S}^{*}F(u,v).$

###### Proof.

We prove only the first equation. The inclusion ${\cal
S}F(x,y)\subseteq\mathop{{\rm Lim}\,{\rm
sup}}_{(u,v)\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(x,y)}{\cal
S}F(u,v)=:S$ follows easily from the definition of ${\cal S}F(x,y)$ together
with $\widehat{\cal S}F(u,v)\subseteq{\cal S}F(u,v)$,
$(u,v)\in\mathrm{gph}\,F$. In order to show the reverse inclusion, consider
$L\in S$ together with sequences
$(u_{k},v_{k})\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(x,y)$ and
$L_{k}\in{\cal S}F(u_{k},v_{k})$ with
$L_{k}\mathop{\longrightarrow}\limits^{{{\cal Z}_{n}}}L$. By definition, for
every $k$ we can find $(u_{k}^{\prime},y_{k}^{\prime})\in{\cal O}_{F}$ and
$L_{k}^{\prime}\in\widehat{\cal S}F(u_{k},v_{k}))$ such that
$\|(u_{k},v_{k})-(u_{k}^{\prime},v_{k}^{\prime})\|\leq\frac{1}{k}$ and
$d_{\cal Z}(L_{k},L_{k}^{\prime})\leq\frac{1}{k}$. Thus
$(u_{k}^{\prime},v_{k}^{\prime})\mathop{\longrightarrow}\limits^{{{\cal
O}_{F}}}(x,y)$ and $L_{k}^{\prime}\mathop{\longrightarrow}\limits^{{{\cal
Z}_{n}}}L$ verifying $L\in{\cal S}F(x,y)$. ∎

We now provide some calculus rules.

######  Proposition 3.14.

Given a mapping $G:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and a
mapping $\Phi:\mathbb{R}^{2n}\to\mathbb{R}^{2n}$, consider the mapping
$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ given by

$\mathrm{gph}\,F=\\{(x,y)\mid\;\Phi(x,y)\in\mathrm{gph}\,G\\}.$

Then for every $(x,y)\in\mathrm{gph}\,F$ such that $\Phi$ is continuously
differentiable in some neighborhood of $(x,y)$ and $\nabla\Phi(x,y)$ is
nonsingular, there holds

$\displaystyle{\cal S}F(x,y)=\nabla\Phi(x,y)^{-1}{\cal
S}G(\Phi(x,y))(:=\\{\nabla\Phi(x,y)^{-1}L\mid\;L\in{\cal S}G(\Phi(x,y))\\}),$
(20) $\displaystyle{\cal S}^{*}F(x,y)=S_{n}\nabla\Phi(x,y)^{T}S_{n}^{T}{\cal
S}^{*}G(\Phi(x,y)).$ (21)

###### Proof.

By the classical Inverse Function Theorem, there is some open neighborhood $W$
of $(x,y)$ such that $\Phi$ is a one-to-one mapping from $W$ to the open
neighborhood $\tilde{W}:=\Phi(W)$ of $\Phi(x,y)$ and
$\nabla\Phi(x^{\prime},y^{\prime})$ is nonsingular for every
$(x^{\prime},y^{\prime})\in W$. By [34, Exercise 6.7] we have
$T_{\mathrm{gph}\,F}(x^{\prime},y^{\prime})=\nabla\Phi(x^{\prime},y^{\prime})^{-1}T_{\mathrm{gph}\,G}(\Phi(x^{\prime},y^{\prime}))$
for all $(x^{\prime},y^{\prime})\in\mathrm{gph}\,F\cap W$ and it follows that
${\cal O}_{G}\cap\tilde{W}=\Phi({\cal O}_{F}\cap W)$. Consider $L\in{\cal
S}F(x,y)$ together with sequences
$(x_{k},y_{k})\mathop{\longrightarrow}\limits^{{\cal O}_{F}}(x,y)$ and
$L_{k}\in\widehat{\cal S}F(x_{k},y_{k})$ converging to $L$. Then for all $k$
sufficiently large we have
$T_{\mathrm{gph}\,G}(\Phi(x_{k},y_{k}))=\nabla\Phi(x_{k},y_{k})T_{\mathrm{gph}\,F}(x_{k},y_{k})=\nabla\Phi(x_{k},y_{k})L_{k}\in\widehat{\cal
S}G(\Phi(x_{k},y_{k})$ showing
$\nabla\Phi(x,y)L=\lim_{k\to\infty}\nabla\Phi(x_{k},y_{k})L_{k}\in{\cal
S}G(\Phi(x,y))$ by Lemma 3.1(iii). This proves that ${\cal
S}F(x,y)\subseteq\nabla\Phi(x,y)^{-1}{\cal S}G(\Phi(x,y))$.

To show the reverse inclusion, consider $L\in{\cal S}G(\Phi(x,y))$ together
with sequences $z_{k}\mathop{\longrightarrow}\limits^{{\cal
O}_{G}\cap\tilde{W}}\Phi(x,y)$ and $L_{k}\in\widehat{\cal S}G(z_{k})$ with
$L_{k}\to L$. It follows that the sequence
$(x_{k},y_{k}):=\Phi^{-1}(z_{k})\cap W$ converges to $(x,y)$ and
$T_{\mathrm{gph}\,F}(x_{k},y_{k})=\nabla\Phi(x_{k},y_{k})^{-1}L_{k}\in\widehat{\cal
S}F(x_{k},y_{k})$ implying $\nabla\Phi(x,y)^{-1}L\in{\cal S}F(x,y)$ by Lemma
3.2(iii). Hence $\nabla\Phi(x,y)^{-1}{\cal S}G(\Phi(x,y))\subseteq{\cal
S}F(x,y)$ and equation (20) follows. To prove the equation (21), just use
Remark 3.5 together with the fact that for any $L\in{\cal Z}_{n}$ we have
$(\nabla\Phi(x,y)^{-1}L)^{\perp}=\nabla\Phi(x,y)^{T}L^{\perp}$ implying

$(\nabla\Phi(x,y)^{-1}L)^{*}=S_{n}\nabla\Phi(x,y)^{T}L^{\perp}=S_{n}\nabla\Phi(x,y)^{T}S_{n}^{T}L^{*}.$

∎

######  Proposition 3.15.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ have the SCD property at
$(x,y)\in\mathrm{gph}\,F$ and let $h:U\to\mathbb{R}^{n}$ be continuously
differentiable at $x\in U$ where $U\subseteq\mathbb{R}^{n}$ is open. Then
$F+h$ has the SCD property at $(x,y+h(x))$ and

$\displaystyle{\cal S}(F+h)(x,y+h(x))=\Big{\\{}\left(\begin{matrix}I&0\\\
\nabla h(x)&I\end{matrix}\right)L\mid\;L\in{\cal S}F(x,y)\Big{\\}}$ (22)
$\displaystyle{\cal S}^{*}(F+h)(x,y+h(x))=\Big{\\{}\left(\begin{matrix}I&0\\\
\nabla h(x)^{T}&I\end{matrix}\right)L\mid\;L\in{\cal S}^{*}F(x,y)\Big{\\}}$
(23)

###### Proof.

We have
$\mathrm{gph}\,(F+h)=\\{(u,v+h(u))\mid\;(u,v)\in\mathrm{gph}\,F\\}=\\{(x,y)\mid\;(x,y-h(x))\in\mathrm{gph}\,F\\}$
and the assertion follows from Proposition 3.14 with $\Phi(x,y)=(x,y-h(x))$. ∎

Next, let us proceed to the large class of graphically Lipschitzian mappings.

######  Definition 3.16 (cf.[34, Definition 9.66]).

A mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is graphically
Lipschitzian of dimension $d$ at $(\bar{x},\bar{y})\in\mathrm{gph}\,F$ if
there is an open neighborhood $W$ of $(\bar{x},\bar{y})$ and a one-to-one
mapping $\Phi$ from $W$ onto an open subset of $\mathbb{R}^{n+m}$ with $\Phi$
and $\Phi^{-1}$ continuously differentiable, such that
$\Phi(\mathrm{gph}\,F\cap W)$ is the graph of a Lipschitz continuous mapping
$f:U\to\mathbb{R}^{n+m-d}$, where $U$ is an open set in $\mathbb{R}^{d}$.

In what follows we will refer to the mapping $\Phi$ as transformation mapping.

######  Proposition 3.17.

Assume that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is graphically
Lipschitzian of dimension $n$ at $(\bar{x},\bar{y})\in\mathrm{gph}\,F$ with
transformation mapping $\Phi$. Then $F$ has the SCD property around
$(\bar{x},\bar{y})$ and for every $(x,y)\in\mathrm{gph}\,F$, sufficiently
close to $(\bar{x},\bar{y})$, one has

$\displaystyle{\cal S}F(x,y)=\nabla\Phi(x,y)^{-1}{\cal S}f(u)=\Big{\\{}{\rm
rge\;}\left[\nabla\Phi(x,y)^{-1}\left(\begin{array}[]{c}I\\\
B\end{array}\right)\right]\mid\;B\in\overline{\nabla}f(u)\Big{\\}},$ (24c)
$\displaystyle{\cal S}^{*}F(x,y)=S_{n}\nabla\Phi(x,y)^{T}S_{n}^{T}{\cal
S}^{*}f(u)=\Big{\\{}{\rm
rge\;}\left[S_{n}\nabla\Phi(x,y)^{T}S_{n}^{T}\left(\begin{array}[]{c}I\\\
B^{T}\end{array}\right)\right]\mid\;B\in\overline{\nabla}f(u)\Big{\\}},$ (24f)

where $f$ is as in Definition 3.16 and $u:=\pi_{1}(\Phi(x,y))$.

###### Proof.

Follows from Proposition 3.14 together with Lemma 3.11. ∎

######  Remark 3.18.

Note that for a graphically Lipschitizian mapping $F$ with transformation
mapping $\Phi$ we have $\Phi({\cal O}_{F}\cap W)={\cal O}_{f}$ by the proof of
Proposition 3.14, where $W$ and $f$ are as in Definition 3.16. At points
$(u,f(u))\in{\cal O}_{f}$ the mapping $f$ is Fréchet differentiable at $u$ by
Lemma 3.2(ii) and therefore $T_{\mathrm{gph}\,f}(u,f(u))={\rm
Lim}_{t\downarrow 0}t^{-1}(\mathrm{gph}\,f-(u,f(u)))$. Since the graphs of $F$
and $f$ coincide locally up to a change of coordinates, we may conclude that
$T_{\mathrm{gph}\,F}(x,y)={\rm Lim}_{t\downarrow
0}t^{-1}(\mathrm{gph}\,F-(x,y))$, $(x,y)\in{\cal O}_{F}\cap W$, i.e., $F$ is
proto-differentiable at these points, cf. [34, Section 8.H].

######  Corollary 3.19.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and let
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$ be given. Suppose that there is an open
neighborhood $V$ of $\bar{x}$ and a continuously differentiable mapping
$h:V\to\mathbb{R}^{n}$ such that $F+h$ is strongly metrically regular around
$(\bar{x},\bar{y}+h(\bar{x}))$. Then $F$ is graphically Lipschitzian of
dimension $n$ with transformation mapping $\Phi(x,y)=(y+h(x),x)$. Therefore
$F$ has the SCD property around $(\bar{x},\bar{y})$ and for every
$(x,y)\in\mathrm{gph}\,F$ sufficiently close to $(\bar{x},\bar{y})$ one has

$\displaystyle{\cal S}F(x,y)$ $\displaystyle=\\{{\rm rge\;}(B,I-\nabla
h(x)B)\mid\;B\in\overline{\nabla}(F+h)^{-1}(y+h(x))\\}$ (25a)
$\displaystyle=\left(\begin{matrix}0&I\\\ I&-\nabla
h(\bar{x})\end{matrix}\right){\cal S}(F+h)^{-1}(\bar{y}+h(\bar{x}),\bar{x}),$
$\displaystyle{\cal S}^{*}F(x,y)$ $\displaystyle=\\{{\rm rge\;}(B^{T},I-\nabla
h(x)^{T}B^{T})\mid\;B\in\overline{\nabla}(F+h)^{-1}(y+h(x))\\}$ (25b)
$\displaystyle=\left(\begin{matrix}0&I\\\ I&-\nabla
h(x)^{T}\end{matrix}\right){\cal S}^{*}(F+h)^{-1}(y+h(x),x).$

###### Proof.

By Theorem 2.6 there are open neighborhoods $U$ of $\bar{y}+h(\bar{x})$,
$W^{\prime}$ of $(\bar{y}+h(\bar{x}),\bar{x})$ and a Lipschitz continuous
mapping $f:U\to\mathbb{R}^{n}$ such that
$\mathrm{gph}\,f=\mathrm{gph}\,(F+h)^{-1}\cap W^{\prime}$. Since
$\mathrm{gph}\,(F+h)^{-1}=\\{(y+h(x),x)\mid\;(x,y)\in\mathrm{gph}\,F,\ x\in
V\\}$, $F$ is graphically Lipschitzian of dimension $n$ and (25) follows from
Proposition 3.17 by taking into account that

$\nabla\Phi(x,y)=\left(\begin{matrix}\nabla h(x)&I\\\ I&0\end{matrix}\right),\
\nabla\Phi(x,y)^{-1}=\left(\begin{matrix}0&I\\\ I&-\nabla
h(x)\end{matrix}\right),\ \
S_{n}\nabla\Phi(x,y)^{T}S_{n}^{T}=-\left(\begin{matrix}0&I\\\ I&-\nabla
h(x)^{T}\end{matrix}\right).$

∎

Some examples of graphically Lipschitzian mappings
$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ of dimension $n$ were
already given in [33, 27]. Next, we extend these examples and give an explicit
description of the subspaces contained in ${\cal S}F(x,y)$ and ${\cal
S}^{*}F(x,y)$, respectively. Recall that a mapping
$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is said to be monotone if

$\langle y_{1}-y_{2},x_{1}-x_{2}\rangle\geq 0\quad\mbox{ for all
$(x_{i},y_{i})\in\mathrm{gph}\,F,\ i=1,2$.}$

It is maximally monotone if, in addition, there holds
$\mathrm{gph}\,F=\mathrm{gph}\,T$ for every monotone mapping
$T:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ with
$\mathrm{gph}\,F\subset\mathrm{gph}\,T$. Next we define several types of local
monotonicity.

######  Definition 3.20.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and let
$(x,y)\in\mathrm{gph}\,F$. We say the following:

  1. 1.

$F$ is locally monotone at $(x,y)$ if there is an open neighborhood $X\times
Y$ of $(x,y)$ such that

$\langle y_{1}-y_{2},x_{1}-x_{2}\rangle\geq 0\quad\mbox{ for all
$(x_{i},y_{i})\in\mathrm{gph}\,F\cap(X\times Y),\ i=1,2$}.$ (26)

It is locally maximally monotone if, in addition, there holds
$\mathrm{gph}\,F\cap(X\times Y)=\mathrm{gph}\,T\cap(X\times Y)$ for every
monotone mapping $T:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ with
$\mathrm{gph}\,F\cap(X\times Y)\subseteq\mathrm{gph}\,T$.

  2. 2.

$F$ is locally (maximally) hypomonotone at $(x,y)$ if $\gamma I+F$ is locally
(maximally) monotone at $(x,\gamma x+y)$ for some $\gamma\geq 0$.

Related with maximally monotone operators are the so-called firmly
nonexpansive mappings.

######  Definition 3.21.

  1. 1.

A mapping $f:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is called firmly nonexpansive if
$\langle f(u_{1})-f(u_{2}),u_{1}-u_{2}\rangle\geq\|f(u_{1})-f(u_{2})\|^{2}$,
$u_{1},u_{2}\in\mathbb{R}^{n}$.

  2. 2.

An $n\times n$ matrix $B$ is called firmly nonexpansive, if the linear mapping
$u\to Bu$ is firmly nonexpansive, i.e., $\langle Bv,v\rangle\geq\|Bv\|^{2}$,
$v\in\mathbb{R}^{n}$.

Note that an $n\times n$ matrix $B$ is firmly nonexpansive if and only if
$\|2B-I\|\leq 1$, see, e.g., [3, Fact 1.1]. Further, a firmly nonexpansive
matrix $B$ is positive semidefinite and satisfies $\|B\|\leq 1$ and, when $B$
is symmetric, these conditions are also sufficient for $B$ being firmly
nonexpansive.

######  Proposition 3.22.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ be locally maximally
monotone at $(\bar{x},\bar{y})$. Then $F$ is graphically Lipschtzian of
dimension $n$ at $(\bar{x},\bar{y})$ with transformation mapping
$\Phi(x,y)=(x+y,x)$ and consequently $F$ has the SCD property around
$(\bar{x},\bar{y})$. Further, for every $(x,y)\in\mathrm{gph}\,F$ sufficiently
close to $(\bar{x},\bar{y})$ and for every subspace $L\in{\cal S}F(x,y)$ there
is a firmly nonexpansive $n\times n$ matrix $B$ such that $L={\rm
rge\;}(B,I-B)$ and $L^{*}={\rm rge\;}(B^{T},I-B^{T})$.

###### Proof.

Let $F_{\rm loc}:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ be given by
$\mathrm{gph}\,F_{\rm loc}=\mathrm{gph}\,F\cap(X\times Y)$, where $(X\times
Y)$ is as in Definition 3.20. Then $F_{\rm loc}$ is monotone, has a maximally
monotone extension $\tilde{F}$, cf. [34, Proposition 12.6] and
$\mathrm{gph}\,F\cap(X\times Y)=\mathrm{gph}\,\tilde{F}\cap(X\times Y)$. By
[2, Corollary 23.8], ${\rm rge\;}(I+\tilde{F})=\mathbb{R}^{n}$ and the
resolvent $f:=(I+\tilde{F})^{-1}$ is a single-valued, firmly nonexpansive
mapping on $\mathbb{R}^{n}$. Since $f(\bar{x}+\bar{y})=\bar{x}$, we can find
an open neighborhood $U$ of $\bar{x}+\bar{y}$ such that $f(u)\in X$ and
$u-f(u)\in Y$ for all $u\in U$. It follows that
$(I+F)^{-1}(u)=(I+\tilde{F})^{-1}(u)$ and therefore $I+F$ is strongly
metrically regular around $(\bar{x},\bar{x}+\bar{y})$. Thus $F$ is graphically
Lipschitzian at $(\bar{x},\bar{y})$ and has the SCD property around
$(\bar{x},\bar{y})$ by Corollary 3.19. Now consider a subspace $L\in{\cal
S}F(x,y)$, where $(x,y)$ is close to $(\bar{x},\bar{y})$. By (25a) there is a
matrix $B\in\overline{\nabla}f(x+y)$ such that $L={\rm rge\;}(B,I-B)$. Since
$f$ is firmly nonexpansive, for every $(u^{\prime},f(u^{\prime}))\in{\cal
O}_{f}$ we have $\langle\nabla f(u^{\prime})v,v\rangle\geq\|\nabla
f(u^{\prime})v\|^{2}$ and $\|Bv\|^{2}\leq\langle Bv,v\rangle$,
$v\in\mathbb{R}^{n}$ follows. This completes the proof. ∎

If $F$ is only locally maximally hypomonotone at $(\bar{x},\bar{y})$, it
follows that $(1+\gamma)I+F$ is strongly metrically regular around
$(\bar{x},(1+\gamma)\bar{x}+\bar{y})$ for some $\gamma\geq 0$. Hence we obtain
the following corollary.

######  Corollary 3.23.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ be locally maximally
hypomonotone at $(\bar{x},\bar{y})$. Then there is some $\gamma\geq 0$ such
that $F$ is graphically Lipschitzian at $(\bar{x},\bar{y})$ of dimension $n$
with transformation mapping $\Phi(x,y)=((1+\gamma)x+y,x)$ and therefore $F$
has the SCD property around $(\bar{x},\bar{y})$. For every
$(x,y)\in\mathrm{gph}\,F$ sufficiently close to $(\bar{x},\bar{y})$ and every
subspace $L\in{\cal S}F(x,y)$ there is a firmly nonexpansive $n\times n$
matrix $B$ such that $L={\rm rge\;}(B,I-(1+\gamma)B)$ and $L^{*}={\rm
rge\;}(B^{T},I-(1+\gamma)B^{T})$.

######  Corollary 3.24.

A mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ which is locally
maximally hypomonotone on a dense subset of its graph is an SCD mapping.

We now consider the subdifferential mapping $\partial q$ of some lsc function
$q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$.

######  Definition 3.25.

  1. 1.

A function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ is prox-regular at
$\bar{x}\in\mathrm{dom}\,q$ for ${\bar{x}^{\ast}}\in\partial q(\bar{x})$ if
$q$ is locally lsc around $\bar{x}$ and there exist $\epsilon>0$ and $\rho\geq
0$ such that for all $x^{\prime},x\in{\cal B}_{\epsilon}(\bar{x})$ with
$|q(x)-q(\bar{x})|\leq\epsilon$ one has

$q(x^{\prime})\geq q(x)+\langle
x^{*},x^{\prime}-x\rangle-\frac{\rho}{2}\|x^{\prime}-x\|^{2}\quad\mbox{whenever}\quad
x^{*}\in\partial q(x)\cap{\cal B}_{\epsilon}({\bar{x}^{\ast}}).$

When this holds for all ${\bar{x}^{\ast}}\in\partial q(\bar{x})$, $q$ is said
to be prox-regular at $\bar{x}$.

  2. 2.

A function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ is called subdifferentially
continuous at $\bar{x}\in\mathrm{dom}\,q$ for ${\bar{x}^{\ast}}\in\partial
q(\bar{x})$ if for any sequence
$(x_{k},x_{k}^{*})\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,\partial
q}}(\bar{x},{\bar{x}^{\ast}})$ we have $\lim_{k\to\infty}q(x_{k})=q(\bar{x})$.
When this holds for all ${\bar{x}^{\ast}}\in\partial q(\bar{x})$, $q$ is said
to be subdifferentially continuous at $\bar{x}$.

######  Proposition 3.26.

Suppose that $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ is prox-regular and
subdifferentially continuous at $\bar{x}$ for $\bar{x}^{*}\in\partial
q(\bar{x})$. Then $\partial q$ is locally maximally hypomonotone at
$(\bar{x},{\bar{x}^{\ast}})$ and there is some $\lambda>0$ such that $\partial
q$ is graphically Lipschitzian at $(\bar{x},\bar{y})$ with transformation
mapping $\Phi(x,x^{*})=(x+\lambda x^{*},x)$. Thus $\partial q$ has the SCD
property around $(\bar{x},{\bar{x}^{\ast}})$. Further, for every
$(x,x^{*})\in\mathrm{gph}\,\partial q$ sufficiently close to
$(\bar{x},{\bar{x}^{\ast}})$ one has ${\cal S}^{*}\partial q(x,x^{*})={\cal
S}\partial q(x,x^{*})$ and for every $L\in{\cal S}\partial q(x,x^{*})$ there
is a symmetric positive semidefinite $n\times n$ matrix $B$ such that
$L=L^{*}={\rm rge\;}(B,\frac{1}{\lambda}(I-B))$.

###### Proof.

Let $\tilde{q}(x):=q(x)-\langle{\bar{x}^{\ast}},x\rangle$. Then
$\partial\tilde{q}(\cdot)=\partial q(\cdot)-{\bar{x}^{\ast}}$ and $\tilde{q}$
is prox-regular at $\bar{x}$ for $0$. By the definition of prox-regularity we
have

$\tilde{q}(x^{\prime})\geq\tilde{q}(\bar{x})-\frac{\rho}{2}\|x^{\prime}-\bar{x}\|^{2}\
\forall x^{\prime}\in{\cal B}_{\epsilon}(\bar{x})$

for some $\epsilon>0$ and some $\rho\geq 0$. Hence the function
$\hat{q}:=\tilde{q}+\delta_{{\cal B}_{\epsilon}}$ fulfills the baseline
assumption of [27, Section 4]. By [27, Proposition 4.8] the subdifferential
mapping $\partial\hat{q}$ is locally maximally hypomonotone around
$(\bar{x},0)$ and, by the proof of [27, Theorem 4.7], for any
$\lambda\in(0,\frac{1}{\rho})$ the mapping $\partial\hat{q}$ is graphically
Lipschitzian with transformation mapping $\Phi(x,x^{*})=(x+\lambda x^{*},x)$.
Moreover, by [27, Theorem 4.4], $(I+\lambda\partial\hat{q})^{-1}$ is locally
monotone at $(\bar{x},\bar{x})$ and there holds

$\nabla
e_{\lambda}\hat{q}(u)=\frac{1}{\lambda}\big{(}I-(I+\lambda\partial\hat{q})^{-1}\big{)}(u)$
(27)

for all $u$ sufficiently close to $\bar{x}$, where

$e_{\lambda}\hat{q}(y):=\inf_{x}\\{\frac{1}{2\lambda}\|x-y\|^{2}+\hat{q}(x)\\}$

denotes the Moreau envelope of $\hat{q}$. Consider a pair $(x,\hat{x}^{*})$
close to $(\bar{x},0)$ and a subspace $L\in{\cal
S}\partial\hat{q}(x,\hat{x}^{*})$. According to Corollary 3.23, there is a
matrix
$B\in\overline{\nabla}(I+\lambda\partial\hat{q})^{-1}(x+\lambda\hat{x}^{*})$
with $L=\nabla\Phi(x,\hat{x}^{*})^{-1}{\rm rge\;}(I,B)={\rm
rge\;}(B,\frac{1}{\lambda}(I-B))$, where we have taken into account

$\nabla\Phi(x,\hat{x}^{*})=\left(\begin{matrix}I&\lambda I\\\
I&0\end{matrix}\right),\
\nabla\Phi(x,\hat{x}^{*})^{-1}=\left(\begin{matrix}0&I\\\
\frac{1}{\lambda}I&-\frac{1}{\lambda}I\end{matrix}\right).$

Since $(I+\lambda\partial\hat{q})^{-1}$ is locally monotone at
$(\bar{x},\bar{x})$, it follows that $B$ is positive semidefinite. Further, by
(27) we have $\frac{1}{\lambda}(I-B)\in\overline{\nabla}(\nabla
e_{\lambda}\hat{q})(x+\lambda\hat{x}^{*})$. By [34, Theorem 13.52],
$\overline{\nabla}(\nabla e_{\lambda}\hat{q})(x+\lambda\hat{x}^{*})$ consists
of symmetric matrices and consequently $B$ is symmetric. Since $L^{\perp}={\rm
rge\;}(\frac{1}{\lambda}(I-B),-B)$, we obtain $L^{*}=L$ and ${\cal
S}^{*}\partial\hat{q}(x,\hat{x}^{*})={\cal S}\partial\hat{q}(x,\hat{x}^{*})$
follows. Now, by taking into account that $\partial\tilde{q}$ and
$\partial\hat{q}$ coincide near $\bar{x}$ and $\partial q$ differs from
$\partial\tilde{q}$ only by the constant ${\bar{x}^{\ast}}$, it follows that
all the shown properties do not hold only for $\partial\hat{q}$ but also for
$\partial q$. ∎

######  Corollary 3.27.

For every lsc function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ which is prox-
regular and subdifferentially continuous at $x$ for $x^{*}$ on a dense subset
of $\mathrm{gph}\,\partial q$, its subdifferential mapping $\partial q$ is an
SCD mapping.

Clearly, every lsc convex function is prox-regular and subdifferentially
continuous at all points of its domain. Further, the proof of Proposition 3.26
holds true with $\lambda=1$ and $(I+\partial q)^{-1}$ is firmly nonexpansive
and therefore $\|B\|\leq 1$ $\forall
B\in\overline{\nabla}(I+\partial\hat{q})^{-1}(\bar{x})$. Thus we obtain the
following corollary.

######  Corollary 3.28.

For every lsc proper convex function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ the
subdifferential mapping $\partial q$ is graphically Lipschitzian of dimension
$n$ at every point $(x,x^{*})$ of its graph. Hence $\partial q$ is an SCD
mapping and for every $(x,x^{*})\in\mathrm{gph}\,\partial q$ and every
$L\in{\cal S}^{*}\partial q(x,x^{*})={\cal S}\partial q(x,x^{*})$ there is a
symmetric positive semidefinite $n\times n$ matrix $B$ with $\|B\|\leq 1$ such
that $L={\rm rge\;}(B,I-B)$.

######  Example 3.29.

Let $C\subset\mathbb{R}^{n}$ be a convex polyhedral set and consider
$q=\delta_{C}$ so that $\partial q=N_{C}$. By the well-known reduction Lemma,
see, e.g., [10, Lemma 2E.4], we have
$T_{\mathrm{gph}\,N_{C}}(x,x^{*})=\mathrm{gph}\,N_{{\cal K}_{C}(x,x^{*})}$,
where ${\cal K}_{C}(x,x^{*}):=T_{C}(x)\cap[x^{*}]^{\perp}$ denotes the
critical cone to $C$ at $x$ for $x^{*}$. Thus $N_{C}$ is graphically smooth of
dimension $n$ at $(x,x^{*})$ if and only if ${\cal K}_{C}(x,x^{*})$ is a
subspace and in this case we have $\widehat{\cal
S}N_{C}(x,x^{*})=K_{C}(x,x^{*})\times K_{C}(x,x^{*})^{\perp}=\widehat{\cal
S}^{*}N_{C}(x,x^{*})$. Given
$(\bar{x},{\bar{x}^{\ast}})\in\mathrm{gph}\,N_{C}$, by [10, Lemma 4H.2], for
every sufficiently small neighborhood $W$ of $(\bar{x},{\bar{x}^{\ast}})$, the
collection of all critical cones ${\cal K}_{C}(x,x^{*})$, $(x,x^{*})\in W$
coincides with the collection of all sets of the form ${\cal F}_{1}-{\cal
F}_{2}$, where ${\cal F}_{1},{\cal F}_{2}$ are faces of ${\cal
K}_{C}(\bar{x},{\bar{x}^{\ast}})$ with ${\cal F}_{2}\subseteq{\cal F}_{1}$.
Since ${\cal F}_{1}-{\cal F}_{2}$ is a subspace if and only if ${\cal
F}_{1}={\cal F}_{2}$ and ${\cal K}_{C}(\bar{x},{\bar{x}^{\ast}})$ has only
finitely many faces, we obtain

${\cal S}N_{C}(\bar{x},{\bar{x}^{\ast}})={\cal
S}^{*}N_{C}(\bar{x},{\bar{x}^{\ast}})=\\{({\cal F}-{\cal F})\times({\cal
F}-{\cal F})^{\perp}\mid\;\mbox{${\cal F}$ is face of ${\cal
K}_{C}(\bar{x},{\bar{x}^{\ast}})$}\\}.$ (28)

Of course, for every face ${\cal F}$ of ${\cal
K}_{C}(\bar{x},{\bar{x}^{\ast}})$ we have

$({\cal F}-{\cal F})\times({\cal F}-{\cal F})^{\perp}={\rm rge\;}(B,I-B),$

where $B$ represents the orthogonal projection on ${\cal F}-{\cal F}$.

Let us compare the representation (28) with the limiting coderivative
$D^{*}N_{C}(\bar{x},{\bar{x}^{\ast}})$. It was shown in [9, Proof of Theorem
2] that $N_{\mathrm{gph}\,N_{C}}(\bar{x},{\bar{x}^{\ast}})$ is the union of
all product sets $K^{\circ}\times K$ associated with cones $K$ of the form
${\cal F}_{1}-{\cal F}_{2}$, where ${\cal F}_{1}$ and ${\cal F}_{2}$ are
closed faces of the critical cone $K_{C}(\bar{x},{\bar{x}^{\ast}})$ satisfying
${\cal F}_{2}\subset{\cal F}_{1}$. Thus,
$\mathrm{gph}\,D^{*}N_{C}(\bar{x},{\bar{x}^{\ast}})$ is the union of all
respective sets of the form $({\cal F}_{2}-{\cal F}_{1})\times({\cal
F}_{1}-{\cal F}_{2})^{\circ}$ and we see that ${\cal
S}^{*}N_{C}(\bar{x},{\bar{x}^{\ast}})$ has a simpler structure than the
limiting coderivative $D^{*}N_{C}(\bar{x},{\bar{x}^{\ast}})$ whenever the
critical cone $K_{C}(\bar{x},{\bar{x}^{\ast}})$ is not a subspace.

Given a function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$, ${\cal S}^{*}\partial
q(x,x^{*})$ amounts to a generalized derivative of the subgradient mapping and
constitutes therefore some generalized second-order derivative of $q$. In the
framework of a study of sufficient conditions for local optimality,
Rockafellar [35] has introduced another type of generalized second-order
derivative as an epigraphical limit of certain second-order subderivatives.

######  Definition 3.30 ([35]).

  1. 1.

A function $\phi:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ is called a generalized
quadratic form, if $\phi(0)=0$ and the subgradient mapping $\partial\phi$ is
generalized linear, i.e., $\mathrm{gph}\,\partial\phi$ is a subspace of
$\mathbb{R}^{n}\times\mathbb{R}^{n}$.

  2. 2.

A function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ is called generalized twice
differentiable at $x$ for a subgradient $x^{*}\in\partial q(x)$, if it is
twice epi-differentiable at $x$ for $x^{*}$ with the second-order
subderivative ${\rm d}^{2}q(x,x^{*})$ being a generalized quadratic form.

  3. 3.

Given a function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ and a pair
$(x,x^{*})\in\mathrm{gph}\,\partial q$, the quadratic bundle of $q$ at $x$ for
$x^{*}$ is defined by

${\rm quad\,}q(x,x^{*}):=\left[\ \begin{minipage}{284.52756pt}the collection
of generalized quadratic forms $\phi$ for which
$\exists(x_{k},x_{k}^{*})\to(x,x^{*})$ with $q$ generalized twice
differentiable at $x_{k}$ for $x_{k}^{*}$ and such that the generalized
quadratic forms $\phi_{k}={\rm d}^{2}q(x_{k},x_{k}^{*})$ converge
epigraphically to $\phi$. \end{minipage}\right.$

We establish now a strong relationship between ${\cal S}\partial q$ and ${\rm
quad\,}q$ for prox-regular and subdifferentially continuous functions $q$. We
start with the following lemma.

######  Lemma 3.31.

Let $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ be prox-regular and
subdifferentially continuous at $x$ for $x^{*}\in\partial q(x)$. Then
$(x,x^{*})\in{\cal O}_{\partial q}$ if and only if $q$ is generalized twice
differentiable at $x$ for $x^{*}$, and in this case one has

$\widehat{\cal S}\partial
q(x,x^{*})=\\{\mathrm{gph}\,\partial\big{(}\frac{1}{2}{\rm
d^{2}}q(x,x^{*})\big{)}\\}.$ (29)

###### Proof.

By [34, Theorem 13.40], the subgradient mapping $\partial q$ is proto-
differentiable at $(x,x^{*})$ if and only if $q$ is twice epi-differentiable
at $x$ for $x^{*}$, and then

$D(\partial q)(x,x^{*})=\partial\big{(}\frac{1}{2}{\rm
d^{2}}q(x,x^{*})\big{)}.$

By Proposition 3.26, $\partial q$ is graphically Lipschitzian of order $n$ at
$(x,x^{*})$. Hence, if $(x,x^{*})\in{\cal O}_{\partial q}$ then $\partial q$
is proto-differentiable at $(x,x^{*})$ by Remark 3.18 and consequently $q$ is
twice epi-differentiable at $x$ for $x^{*}$ and
$\mathrm{gph}\,\partial\big{(}\frac{1}{2}{\rm
d^{2}}q(x,x^{*})\big{)}=\mathrm{gph}\,D(\partial
q)(x,x^{*})=T_{\mathrm{gph}\,\partial q}(x,x^{*})$ is a subspace. This
verifies that $q$ is generalized twice differentiable at $x$ for $x^{*}$.
Conversely, if $q$ is generalized twice differentiable at $x$ for $x^{*}$,
then $T_{\mathrm{gph}\,\partial
q}(x,x^{*})=\mathrm{gph}\,\partial\big{(}\frac{1}{2}{\rm
d^{2}}q(x,x^{*})\big{)}$ is a subspace. The dimension of this subspace must be
$n$ because $\partial q$ is graphically Lipschitzian of dimension $n$, and
$(x,x^{*})\in{\cal O}_{\partial q}$ follows. ∎

We will also make use of the following variant of Attouch’s theorem, see,
e.g., [34, Theorem 12.35], which states the connection between graphical
convergence of subdifferential mappings and epi-convergence of the functions
themselves, when the functions are convex.

######  Lemma 3.32.

Let $\phi_{k}:\mathbb{R}^{n}\to\bar{\mathbb{R}}$, $k\in\mathbb{N}$ and
$\phi:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ be proper lsc functions and assume
that there is some $\rho\geq 0$ such that the functions
$\hat{\phi}_{k}:=\phi_{k}+\rho\|\cdot\|^{2}$ are convex. Then the following
two statements are equivalent.

  1. (i)

The functions $\phi_{k}$ epi-converge to $\phi$.

  2. (ii)

The mappings $\partial\phi_{k}$ converge graphically to $\partial\phi$,
$\hat{\phi}:=\phi+\rho\|\cdot\|^{2}$ is convex and there is some sequence
$(x_{k},x_{k}^{*})$ converging to some
$(\bar{x},{\bar{x}^{\ast}})\in\mathrm{gph}\,\partial\phi$ such that
$(x_{k},x_{k}^{*})\in\mathrm{gph}\,\partial\phi_{k}$ $\forall k$ and
$\lim_{k\to\infty}\phi_{k}(x_{k})=\phi(\bar{x})$.

###### Proof.

Observe that assertion (i) is equivalent to epi-convergence of
$\hat{\phi}_{k}\to\hat{\phi}$ by [34, Exercise 7.8], and in this case the
epigraphical limit $\hat{\phi}$ is convex, cf. [34, Theorem 7.17]. Similarly,
$\partial\phi_{k}$ converges graphically to $\partial\phi$ if and only if
$\partial\hat{\phi}_{k}$ converges graphically to $\hat{\phi}$. Indeed, since
$\partial\hat{\phi}_{k}(x)=\partial\phi_{k}(x)+2\rho x$, we easily obtain

$\displaystyle\mathop{{\rm Lim}\,{\rm
sup}}_{k\to\infty}\mathrm{gph}\,\hat{\phi}_{k}=\\{(x,x^{*}+2\rho
x)\mid\;(x,x^{*})\in\mathop{{\rm Lim}\,{\rm
sup}}_{k\to\infty}\mathrm{gph}\,\phi_{k}\\},$ $\displaystyle\mathop{{\rm
Lim}\,{\rm inf}}_{k\to\infty}\mathrm{gph}\,\hat{\phi}_{k}=\\{(x,x^{*}+2\rho
x)\mid\;(x,x^{*})\in\mathop{{\rm Lim}\,{\rm
inf}}_{k\to\infty}\mathrm{gph}\,\phi_{k}\\}$

and the claim follows. Finally we have
$\phi(\bar{x})=\lim_{k\to\infty}\phi_{k}(x_{k})$ for some sequence
$(x_{k},x_{k}^{*})\to(\bar{x},{\bar{x}^{\ast}})\in\mathrm{gph}\,\partial\phi$
with $(x_{k},x_{k}^{*})\in\mathrm{gph}\,\partial\phi_{k}$, if and only if
$\hat{\phi}(\bar{x})=\lim_{k\to\infty}\hat{\phi}_{k}(x_{k})$ and
$\mathrm{gph}\,\partial\hat{\phi}_{k}\ni(x_{k},x_{k}^{*}+2\rho
x_{k})\to(\bar{x},{\bar{x}^{\ast}}+2\rho\bar{x})\in\mathrm{gph}\,\partial\hat{\phi}$.
Now the equivalence between (i) and (ii) follows from Attouch’s theorem [34,
Theorem 12.35] applied to the convex functions $\hat{\phi}_{k}$ and
$\hat{\phi}$. ∎

######  Proposition 3.33.

Suppose that $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ is prox-regular at
$\bar{x}$ for $\bar{x}^{*}\in\partial q(\bar{x})$. Further assume that for all
$(x,x^{*})\in\mathrm{gph}\,\partial q$ sufficiently close to
$(\bar{x},{\bar{x}^{\ast}})$ the function $q$ is subdifferentially continuous
at $x$ for $x^{*}$. Then

${\cal S}^{*}\partial q(\bar{x},{\bar{x}^{\ast}})={\cal S}\partial
q(\bar{x},{\bar{x}^{\ast}})=\\{\mathrm{gph}\,\partial(\frac{1}{2}\phi)\mid\;\phi\in{\rm
quad\,}q(\bar{x},{\bar{x}^{\ast}})\\}.$

###### Proof.

Let $\epsilon$ and $\rho\geq 0$ be as in Definition 3.25. Then we can find an
open neighborhood $W$ of $(\bar{x},{\bar{x}^{\ast}})$ such that $W\subset{\cal
B}_{\frac{\epsilon}{2}}(\bar{x})\times{\cal
B}_{\frac{\epsilon}{2}}({\bar{x}^{\ast}})$ and for all
$(x,x^{*})\in\mathrm{gph}\,\partial q\cap W$ the function $q$ is
subdifferentially continuous at $x$ for $x^{*}$ and
$|q(x)-q(\bar{x})|<\frac{\epsilon}{2}$. Consider
$(\hat{x},\hat{x}^{*})\in\mathrm{gph}\,\partial q\cap W$. Then for all
$x,x^{\prime}\in{\cal B}_{\frac{\epsilon}{2}}(\hat{x})$ with
$|q(x)-q(\hat{x})|\leq\frac{\epsilon}{2}$ and all $x^{*}\in\partial
q(x)\cap{\cal B}_{\frac{\epsilon}{2}}(\hat{x}^{*})$ we have
$x,x^{\prime}\in{\cal B}_{\epsilon}(\bar{x})$, $|q(x)-q(\bar{x})|\leq\epsilon$
and $x^{*}\in\partial q(x)\cap{\cal B}_{\epsilon}({\bar{x}^{\ast}})$ implying
$q(x^{\prime})\geq q(x)+\langle
x^{*},x^{\prime}-x\rangle-\frac{\rho}{2}\|x^{\prime}-x\|^{2}$. Thus $q$ is
prox-regular at $\hat{x}$ for $\hat{x}^{*}$ and therefore graphically
Lipschitzian of dimension $n$ at $(\hat{x},\hat{x}^{*})$. Further, by [34,
Proposition 13.49] and its proof, we may conclude that ${\rm
d^{2}}q(\hat{x},\hat{x}^{*})+\rho\|\cdot\|^{2}$ is a lsc convex function.
Now consider $\phi\in{\rm quad\,}q(\bar{x},{\bar{x}^{\ast}})$ together with
some sequence $(x_{k},x_{k}^{*})\to(\bar{x},{\bar{x}^{\ast}})$ such that $q$
is generalized twice differentiable at $x_{k}$ for $x_{k}^{*}$ and the
generalized quadratic forms $\phi_{k}:={\rm d}^{2}q(x_{k},x_{k}^{*})$ converge
epigraphically to $\phi$. We may assume that
$(x_{k},x_{k}^{*})\in\mathrm{gph}\,\partial q\cap W$ $\forall k$ and thus
$(x_{k},x_{k}^{*})\in{\cal O}_{\partial q}\cap W$ by Lemma 3.31. By Lemma
3.32, $\partial\phi_{k}$ converges graphically to $\partial\phi$, i.e.,
$\mathrm{gph}\,\partial\phi_{k}\to\mathrm{gph}\,\partial\phi$ in the sense of
Painlevé-Kuratowski convergence. Now it follows from Lemma 3.1(v) and (29)
that $\mathrm{gph}\,\partial(\frac{1}{2}\phi)\in{\cal S}\partial
q(\bar{x},{\bar{x}^{\ast}})$.
Conversely, consider a subspace $L\in{\cal S}\partial
q(\bar{x},{\bar{x}^{\ast}})$ together with sequences
$(x_{k},x_{k}^{*})\in{\cal O}_{\partial q}\cap W$ and $L_{k}\in\widehat{\cal
S}\partial q(x_{k},x_{k}^{*})$ with $\lim_{k\to\infty}d_{\cal Z}(L_{k},L)=0$.
According to Proposition 3.26 we can find symmetric positive semidefinte
matrices $B_{k}$, $B$ such that $L_{k}={\rm
rge\;}(B_{k},\frac{1}{\lambda}(I-B_{k}))$, $L={\rm
rge\;}(B,\frac{1}{\lambda}(I-B))$ with $\lambda=1/(\rho+1)$. Now let ${\cal
U}:={\rm rge\;}B$ and set $Q:=\frac{1}{\lambda}(B^{\dagger}-BB^{\dagger})$,
where $B^{\dagger}$ denotes the Moore-Penrose inverse of $B$. Since $B$ is
symmetric and positive semidefinite, so is $B^{\dagger}$ as well. Further,
$BB^{\dagger}B=B$ and $BB^{\dagger}=B^{\dagger}B$ is the orthogonal projection
onto ${\rm rge\;}B$, so that $I-B^{\dagger}B$ is the orthogonal projection
onto ${\cal U}^{\perp}=\ker B$. Now consider the generalized quadratic form
$\phi(x):=\langle Qx,x\rangle+\delta_{\cal U}(x)$. Since $Q$ is symmetric, we
obtain

$\partial(\frac{1}{2}\phi)(x)=\begin{cases}Qx+{\cal
U}^{\perp}=\frac{1}{\lambda}(B^{\dagger}-BB^{\dagger})x+{\cal
U}^{\perp}&\mbox{if $x\in{\cal U}$,}\\\ \emptyset&\mbox{else.}\end{cases}$

Thus

$\displaystyle\mathrm{gph}\,\partial(\frac{1}{2}\phi)$
$\displaystyle=\Big{\\{}\big{(}Bp,\frac{1}{\lambda}(B^{\dagger}-BB^{\dagger})Bp+(I-B^{\dagger}B)v\big{)}\mid\;p,v\in\mathbb{R}^{n}\Big{\\}}$
$\displaystyle=\Big{\\{}\Big{(}B\big{(}B^{\dagger}Bp+(I-B^{\dagger}B)v\big{)},\frac{1}{\lambda}(I-B)\big{(}B^{\dagger}Bp+(I-B^{\dagger}B)v\big{)}\Big{)}\mid\;p,v\in\mathbb{R}^{n}\Big{\\}}$
$\displaystyle={\rm rge\;}(B,\frac{1}{\lambda}(I-B))=L.$

The matrix
$Q+\frac{1}{\lambda}I=\frac{1}{\lambda}B^{\dagger}+\frac{1}{\lambda}(I-BB^{\dagger})$
is positive semidefinite as the sum of two positive semidefinite matrices and
therefore the function
$\hat{\phi}:=\phi+\frac{1}{\lambda}\|\cdot\|^{2}=\phi+(\rho+1)\|\cdot\|^{2}$
is convex. For each $k$, the function $\phi_{k}:={\rm
d}^{2}q(x_{k},x_{k}^{*})$ fulfills
$\mathrm{gph}\,\partial(\frac{1}{2}q)=L_{k}$ by Lemma 3.31 and
$\hat{\phi}_{k}:=\phi_{k}+(\rho+1)\|\cdot\|^{2}$ is convex. Since $(0,0)\in
L_{k}=\mathrm{gph}\,\partial(\frac{1}{2}\phi_{k})$, we have
$0\in\partial\phi_{k}(0)$. Further, $\phi_{k}(0)=\phi(0)=0$ and
$0\in\partial\phi(0)$. Since convergence of $L_{k}$ to $L$ implies that
$\partial\phi_{k}$ converges graphically to $\partial\phi$, it follows from
Lemma 3.32 that $\phi_{k}$ converges epigraphically to $\phi$ and we conclude
$\phi\in{\rm quad\,}q(\bar{x},{\bar{x}^{\ast}})$. Thus
$L\in\\{\mathrm{gph}\,\partial(\frac{1}{2}\phi)\mid\;\phi\in{\rm
quad\,}q(\bar{x},{\bar{x}^{\ast}})\\}$ verifying ${\cal S}\partial
q(\bar{x},{\bar{x}^{\ast}})=\\{\mathrm{gph}\,\partial(\frac{1}{2}\phi)\mid\;\phi\in{\rm
quad\,}q(\bar{x},{\bar{x}^{\ast}})\\}$. By Proposition 3.26 we have ${\cal
S}^{*}\partial q(\bar{x},{\bar{x}^{\ast}})={\cal S}\partial
q(\bar{x},{\bar{x}^{\ast}})$ and the proof is complete. ∎

######  Corollary 3.34.

For every lsc proper convex function $q:\mathbb{R}^{n}\to\bar{\mathbb{R}}$ and
for every pair $(x,x^{*})\in\mathrm{gph}\,\partial q$ we have

${\cal S}^{*}\partial q(x,x^{*})={\cal S}\partial
q(x,x^{*})=\\{\mathrm{gph}\,\partial(\frac{1}{2}\phi)\mid\;\phi\in{\rm
quad\,}q(x,x^{*})\\}.$

##  4 SCD regularity

In this section we present the definition and basic properties of a certain
property called SCD regularity, which has various applications as we will
demonstrate in the subsequent sections.

######  Definition 4.1.

  1. 1.

We denote by ${\cal Z}_{n}^{\rm reg}$ the collection of all subspaces
$L\in{\cal Z}_{n}$ such that

$(y^{*},0)\in L\ \Rightarrow\ y^{*}=0.$ (30)

  2. 2.

A mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is called SCD
regular around $(x,y)\in\mathrm{gph}\,F$, if $F$ has the SCD property around
$(x,y)$ and

$(y^{*},0)\in\bigcup{\cal S}^{*}F(x,y)\Rightarrow\ y^{*}=0,$ (31)

i.e., $L\in{\cal Z}_{n}^{\rm reg}$ for all $L\in{\cal S}^{*}F(x,y)$. Further,
we will denote by

${\rm scd\,reg\;}F(x,y):=\sup\\{\|y^{*}\|\mid\;(y^{*},x^{*})\in\bigcup{\cal
S}^{*}F(x,y),\|x^{*}\|\leq 1\\}$

the modulus of SCD regularity of $F$ around $(x,y)$.

In the following proposition we state some basic properties of subspaces
$L\in{\cal Z}_{n}^{\rm reg}$.

######  Proposition 4.2.

Given a $2n\times n$ matrix $Z$, there holds ${\rm rge\;}Z\in{\cal Z}_{n}^{\rm
reg}$ if and only if the $n\times n$ matrix $\pi_{2}(Z)$ is nonsingular. Thus,
for every $L\in{\cal Z}_{n}^{\rm reg}$ there is a unique $n\times n$ matrix
$C_{L}$ such that $L={\rm rge\;}(C_{L},I)$. Further, $L^{*}={\rm
rge\;}(C_{L}^{T},I)\in{\cal Z}_{n}^{\rm reg}$,

$\langle x^{*},C_{L}^{T}v\rangle=\langle y^{*},v\rangle\
\forall(y^{*},x^{*})\in L\ \forall v\in\mathbb{R}^{n}.$ (32)

and

$\|y^{*}\|\leq\|C_{L}\|\|x^{*}\|\ \forall(y^{*},x^{*})\in L.$ (33)

###### Proof.

Clearly, if $\pi_{2}(Z)$ is nonsingular then ${\rm rge\;}Z\in{\cal Z}_{n}$.
Further, given $(y^{*},0)\in{\rm rge\;}Z$, there is some $p$ with
$y^{*}=\pi_{1}(Z)p$, $0=\pi_{2}(Z)p$ implying $p=y^{*}=0$ and therefore ${\rm
rge\;}Z\in{\cal Z}_{n}^{\rm reg}$. Conversely, consider $L\in{\cal Z}_{n}^{\rm
reg}$ and $Z\in{\cal M}(L)$. Because $L\in{\cal Z}_{n}$, the matrix $Z$ has
full column rank $n$ and therefore there cannot exist $p\not=0$ with $Zp=0$.
Thus, if $A:=\pi_{2}(Z)$ were singular, there is some
$0\not=p\in\mathbb{R}^{n}$ with $Ap=0$ and $Bp\not=0$ with $B:=\pi_{1}(Z)$,
implying $(Bp,0)\in L$ and $Bp\not=0$ which is not possible because of
$L\in{\cal Z}_{n}^{\rm reg}$. This proves that $A$ is nonsingular and $L={\rm
rge\;}ZA^{-1}={\rm rge\;}(C_{L},I)$ with $C_{L}=BA^{-1}$ follows. Clearly,
$C_{L}$ is uniquely given by $L$ and does not depend on the particular choice
of $A$ and $B$. From $L={\rm rge\;}(C_{L},I)$ we deduce $L^{\perp}={\rm
rge\;}(I,-C_{L}^{T})$ and $L^{*}=S_{n}L^{\perp}={\rm rge\;}(C_{L}^{T},I)$.
Further, for every $p\in\mathbb{R}^{n}$ we have $(p,-C_{L}^{T}p)\in
L^{\perp}$, implying

$\langle p,y^{*}\rangle-\langle C_{L}^{T}p,x^{*}\rangle=\langle
p,y^{*}-C_{L}x^{*}\rangle=0\ \forall(y^{*},x^{*})\in L$

and (32) follows. Finally, for every $(y^{*},x^{*})\in L$ there is some
$p\in\mathbb{R}^{n}$ with $y^{*}=C_{L}p$, $x^{*}=p$ implying (33). ∎

######  Remark 4.3.

Note that for every $L\in{\cal Z}_{n}^{\rm reg}$ there holds
$C_{L}=\pi_{1}(Z)\pi_{2}(Z)^{-1}$ for every $Z\in{\cal M}(L)$.

In case of SCD regularity we obtain from Proposition 4.2 that

$\bigcup{\cal S}^{*}F(x,y)=\\{(C_{L}p,p)\mid\;L\in{\cal
S}^{*}F(x,y),p\in\mathbb{R}^{n}\\}$

and consequently

$\displaystyle{\rm scd\,reg\;}F(x,y)$
$\displaystyle=\sup\\{\|C_{L}p\|\mid\;L\in{\cal
S}^{*}F(x,y),p\in\mathbb{R}^{n},\|p\|\leq 1\\}$
$\displaystyle=\sup\\{\|C_{L}\|\mid\;L\in{\cal S}^{*}F(x,y)\\}.$ (34)

######  Remark 4.4.

In case of a single-valued, locally Lipschitzian mapping
$F:\mathbb{R}^{n}\to\mathbb{R}^{n}$, by virtue of Lemma 3.11, SCD regularity
of $F$ around $\bar{x}$ means that all matrices belonging to the
B-subdifferential are nonsingular. This is exactly the so-called BD-regularity
property from [29].

By isometry of the mapping $L\mapsto L^{*}$ and Proposition 4.2 we obtain
readily the following lemma.

######  Lemma 4.5.

The mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is SCD regular
around $(\bar{x},\bar{y})\in\mathrm{gph}\,F$ if and only if

$(u,0)\in\bigcup{\cal S}F(x,y)\ \Rightarrow\ u=0.$ (35)

Further,

${\rm scd\,reg\;}F(x,y)=\sup\\{\|u\|\mid\;(u,v)\in\bigcup{\cal S}F(x,y),\
\|v\|\leq 1\\}=\sup\\{\|C_{L}\|\mid\;L\in{\cal S}F(x,y)\\}.$

Note that SCD regularity is weaker than the metric regularity of $F$ around
$(x,y)$. Indeed, condition (6) for metric regularity of $F$ near $(x,y)$ can
be equivalently written as

$(y^{*},0)\in\mathrm{gph}\,D^{*}F(x,y)\ \Rightarrow\ y^{*}=0$

and $\bigcup{\cal S}^{*}F(x,y)$ is contained in $\mathrm{gph}\,D^{*}F(x,y)$ by
Lemma 3.7. The next example shows that SCD regularity is even strictly weaker
than metric regularity, see also Example 6.5 below.

######  Example 4.6.

Consider the SCD mapping

$F(x):=-x+N_{R_{-}}(x)=\partial q(x)\ \mbox{ with
}q(x)=-\frac{1}{2}x^{2}+\delta_{R_{-}}(x)$

at $(0,0)$. Then

$D^{*}F(0,0)(y^{*})=-y^{*}+\begin{cases}\\{0\\}&\mbox{if $y^{*}<0$}\\\
\mathbb{R}&\mbox{if $y^{*}=0$}\\\ \mathbb{R}_{+}&\mbox{if
$y^{*}>0$}\end{cases}$

and therefore the only subspaces contained in $\mathrm{gph}\,D^{*}F(0,0)$ are
$\\{(y^{*},-y^{*})\mid\;y^{*}\in\mathbb{R}\\}$ and $\\{0\\}\times\mathbb{R}$.
Hence $F$ is SCD regular at $(0,0)$, but $F$ is not metrically regular near
$(0,0)$ because of $0\in D^{*}F(0,0)(1)$.

######  Lemma 4.7.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ be SCD regular around
$(x,y)\in\mathrm{gph}\,F$. Then ${\rm scd\,reg\;}F(x,y)<\infty$.

###### Proof.

Assume on the contrary that there are sequences $L_{k}\in{\cal S}^{*}F(x,y)$
and $(y_{k}^{*},x_{k}^{*})\in L_{k}$ such that $\|y_{k}^{*}\|\geq k$ and
$\|x_{k}^{*}\|\leq 1$. By possibly passing to some subsequence we can assume
that $y_{k}^{*}/\|y_{k}^{*}\|$ converges to some $y^{*}$ with $\|y^{*}\|=1$
and $L_{k}$ converges in the compact metric space ${\cal Z}_{n}$ to some $L$.
Then $(y^{*},0)=\lim_{k\to\infty}(y_{k}^{*},x_{k}^{*})/\|y_{k}^{*}\|\in L$ and
$L\in{\cal S}^{*}F(x,y)$ by Lemma 3.13 contradicting the assumption of SCD
regularity. ∎

######  Proposition 4.8.

Assume that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is SCD regular
around $(\bar{x},\bar{y})\in\mathrm{gph}\,F$. Then $F$ is SCD regular around
every $(x,y)\in\mathrm{gph}\,F$ sufficiently close to $(\bar{x},\bar{y})$ and

$\limsup_{(x,y)\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})}{\rm
scd\,reg\;}F(x,y)\leq{\rm scd\,reg\;}F(\bar{x},\bar{y}).$

###### Proof.

By contraposition. If any of the assertions does not hold, we can find some
$\kappa>{\rm scd\,reg\;}F(\bar{x},\bar{y})$ and sequences
$(x_{k},y_{k})\mathop{\longrightarrow}\limits^{{\mathrm{gph}\,F}}(\bar{x},\bar{y})$,
$L_{k}\in{\cal S}^{*}F(x_{k},y_{k})$ and $(y_{k}^{*},x_{k}^{*})\in L_{k}$ with
$\|y_{k}^{*}\|\geq\kappa$ and $\|x_{k}^{*}\|\leq 1$. By possibly passing to
some subsequence we can assume that $(y_{k}^{*},x_{k}^{*})/\|y_{k}^{*}\|$
converges to some $(y^{*},x^{*})$ and $L_{k}$ converges to some $L$. Then
$\|y^{*}\|=1$, $\|x^{*}\|\leq\frac{1}{\kappa}$, $(y^{*},x^{*})\in L$ and
$L\in{\cal S}^{*}F(\bar{x},\bar{y})$ by Lemma 3.13. Since $L$ is a subspace,
we also have $(\kappa y^{*},\kappa x^{*})\in L\subseteq\bigcup{\cal
S}^{*}F(\bar{x},\bar{y})$ implying together with $\|\kappa x^{*}\|\leq 1$ the
contradiction ${\rm scd\,reg\;}F(\bar{x},\bar{y})\geq\|\kappa y^{*}\|=\kappa$.
∎

##  5 On semismooth* Newton methods for SCD mappings

Consider the inclusion

$0\in F(x),$ (36)

where $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$. Assume that $\bar{x}$
is a reference solution of (36). The idea behind the semismooth∗ Newton method
[14] for solving (36) is as follows. If $F$ is semismooth∗ at $(\bar{x},0)$
and we are given some point $(x,y)\in\mathrm{gph}\,F$ close to $(\bar{x},0)$,
then for every $(y^{*},x^{*})\in\mathrm{gph}\,D^{*}F(x,y)$ there holds

$\langle x^{*},x-\bar{x}\rangle=\langle
y^{*},y-0\rangle+o(\|(x,y)-(\bar{x},0)\|\|(x^{*},y^{*})\|)$

by the definition of the semismoothness* property. We choose now $n$ pairs
$(y_{i}^{*},x_{i}^{*})\in\mathrm{gph}\,D^{*}F(x,y)$, $i=1,\ldots,n$, compute a
solution $\Delta x$ of the system

$\langle x_{i}^{*},\Delta x\rangle=-\langle y_{i}^{*},y\rangle,\ i=1,\ldots,n$
(37)

and expect that $\|(x+\Delta x)-\bar{x}\|=o(\|(x,y)-(\bar{x},0)\|$. When
dealing with SCD mappings $F$ we can simplify this procedure by choosing the
pairs $(y_{i}^{*},x_{i}^{*})$ as a basis of some subspace $L\in{\cal
S}^{*}F(x,y)$, which allows us to weaken the notion of semismoothness* along
the lines of Proposition 2.11.

######  Definition 5.1.

We say that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is SCD
semismooth∗ at $(\bar{x},\bar{y})\in\mathrm{gph}\,F$ if $F$ has the SCD
property around $(\bar{x},\bar{y})$ and for every $\epsilon>0$ there is some
$\delta>0$ such that

$\displaystyle|\langle x^{*},x-\bar{x}\rangle-\langle y^{*},y-\bar{y}\rangle|$
$\displaystyle\leq\epsilon\|(x,y)-(\bar{x},\bar{y})\|\|(x^{*},y^{*})\|$ (38)

holds for all $(x,y)\in\mathrm{gph}\,F\cap{\cal B}_{\delta}(\bar{x},\bar{y})$
and all $(y^{*},x^{*})\in\bigcup{\cal S}^{*}F(x,y)$.
We say that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is SCD
semismooth∗ around $(\bar{x},\bar{y})\in\mathrm{gph}\,F$ if there is some
neighborhood $W$ of $(\bar{x},\bar{y})$ such that $F$ is SCD semismooth∗ at
every $(x,y)\in\mathrm{gph}\,F\cap W$.

The chosen subspace $L\in{\cal S}^{*}F(x,y)$ should have the property that the
resulting system (37) has a unique solution. Taking the pairs
$(y_{i}^{*},x_{i}^{*})$, $i=1,\ldots,n$, as columns of a $2n\times n$ matrix
$Z$, this yields the requirement that $\pi_{2}(Z)$ is nonsingular, which in
turn is equivalent to $L\in{\cal Z}_{n}^{\rm reg}$ by Proposition 4.2.
Comparing (32) with (37), we see that $\Delta x=-C_{L}^{T}y$ is a solution to
(37) in this case.

We are now in the position to describe the iteration step of the SCD variant
of the semismooth∗ Newton method introduced in [14]. Assume we are given some
iterate $x^{(k)}$. Since we cannot expect in general that
$F(x^{(k)})\not=\emptyset$ or that $0$ is close to $F(x^{(k)})$, even if
$x^{(k)}$ is close to a solution $\bar{x}$, we first perform some preparatory
step which yields $(\hat{x}^{(k)},\hat{y}^{(k)})\in\mathrm{gph}\,F$ as an
approximate projection of $(x^{(k)},0)$ onto $\mathrm{gph}\,F$. We require
that

$\|(\hat{x}^{(k)},\hat{y}^{(k)})-(\bar{x},0)\|\leq\eta\|x^{(k)}-\bar{x}\|$
(39)

for some constant $\eta>0$. E.g., if

$\|(\hat{x}^{(k)},\hat{y}^{(k)})-(x^{(k)},0)\|\leq\beta\operatorname{dist}((x^{(k)},0),\mathrm{gph}\,F)$

holds with some $\beta\geq 1$, then

$\displaystyle\|(\hat{x}^{(k)},\hat{y}^{(k)})-(\bar{x},0)\|$
$\displaystyle\leq\|(\hat{x}^{(k)},\hat{y}^{(k)})-(x^{(k)},0)\|+\|(x^{(k)},0)-(\bar{x},0)\|$
$\displaystyle\leq\beta\operatorname{dist}((x^{(k)},0),\mathrm{gph}\,F)+\|(x^{(k)},0)-(\bar{x},0)\|\leq(\beta+1)\|(x^{(k)},0)-(\bar{x},0)\|$

and (39) holds with $\eta=\beta+1$. Further we require that ${\cal
S}^{*}F(\hat{x}^{(k)},\hat{y}^{(k)})\cap{\cal Z}_{n}^{\rm reg}\not=\emptyset$
and compute the new iterate as
$x^{(k+1)}=\hat{x}^{(k)}-C_{L}^{T}\hat{y}^{(k)}$ for some $L\in{\cal
S}^{*}F(\hat{x}^{(k)},\hat{y}^{(k)})\cap{\cal Z}_{n}^{\rm reg}$. In fact, in a
numerical implementation we will not calculate the matrix $C_{L}$, but two
$n\times n$ matrices $A,B$ such that $L={\rm rge\;}(B^{T},A^{T})$, compute
$\Delta x^{(k)}$ as a solution of the system $A\Delta x=-B\hat{y}^{(k)}$ and
set $x^{(k+1)}=\hat{x}^{(k)}+\Delta x^{(k)}$.

This leads to the following conceptual algorithm.

######  Algorithm 1 (SCD semismooth∗ Newton-type method for inclusions).

1\. Choose a starting point $x^{(0)}$, set the iteration counter $k:=0$.
2\. If $0\in F(x^{(k)})$, stop the algorithm.
3\.  Approximation step:  Compute
$(\hat{x}^{(k)},\hat{y}^{(k)})\in\mathrm{gph}\,F$ satisfying (39) such that
${\cal S}^{*}F(\hat{x}^{(k)},\hat{y}^{(k)})\cap{\cal Z}_{n}^{\rm
reg}\not=\emptyset$.
4\.  Newton step: Select $n\times n$ matrices $A^{(k)},B^{(k)}$ with
$L^{(k)}:={\rm rge\;}\big{(}{B^{(k)}}^{T},{A^{(k)}}^{T})\in{\cal
S}^{*}F(\hat{x}^{(k)},\hat{y}^{(k)})\cap{\cal Z}_{n}^{\rm reg}$, calculate the
Newton direction $\Delta x^{(k)}$ as a solution of the linear system
$A^{(k)}\Delta x=-B^{(k)}\hat{y}^{(k)}$ and obtain the new iterate via
$x^{(k+1)}=\hat{x}^{(k)}+\Delta x^{(k)}.$
5\. Set $k:=k+1$ and go to 2.

We have $\Delta x^{(k)}=-C_{L^{(k)}}^{T}\hat{y}^{(k)}$ and therefore $(\Delta
x^{(k)},-\hat{y}^{(k)})\in-{L^{(k)}}^{*}={L^{(k)}}^{*}\in{\cal
S}F(\hat{x}^{(k)},\hat{y}^{(k)})$ by Proposition 4.2. Thus, alternatively we
can perform the Newton step also in the following way:
4\.  Newton step: Select $n\times n$ matrices $A^{(k)},B^{(k)}$ with ${\rm
rge\;}\big{(}{B^{(k)}},{A^{(k)}})\in{\cal
S}F(\hat{x}^{(k)},\hat{y}^{(k)})\cap{\cal Z}_{n}^{\rm reg}$, compute a
solution $p$ of the linear system ${A^{(k)}}p=-\hat{y}^{(k)}$ and compute the
new iterate $x^{(k+1)}=\hat{x}^{(k)}+\Delta x^{(k)}$ with Newton direction
$\Delta x^{(k)}=B^{(k)}p$.

######  Remark 5.2.

Note that $-\hat{y}^{(k)}\in D^{\sharp}F(\hat{x}^{(k)},\hat{y}^{(k)})(\Delta
x^{(k)})$ but we do not necessarily have $-\hat{y}^{(k)}\in
DF(\hat{x}^{(k)},\hat{y}^{(k)})(\Delta x^{(k)})$ as it is the case in Newton
methods based on the graphical derivative, cf. [7, 17, 25].

Which possibility for calculating the Newton direction is actually chosen,
depends on the availability of the respective derivative. Let us analyze the
two alternatives for the special case when $F$ is single-valued and
continuously differentiable at $x^{(k)}$. In Algorithm 1, the matrices
$A^{(k)},B^{(k)}$ with ${\rm rge\;}\big{(}{B^{(k)}}^{T},{A^{(k)}}^{T})\in{\cal
S}^{*}F(\hat{x}^{(k)},\hat{y}^{(k)})$ fulfill ${A^{(k)}}^{T}=\nabla
F(\hat{x}^{(k)})^{T}{B^{(k)}}^{T}$ and thus the Newton direction is computed
by solving the linear system $\big{(}B^{(k)}\nabla
F(\hat{x}^{(k)})\big{)}\Delta x=-B^{(k)}\hat{y}^{(k)}$. On the other hand,
given $A^{(k)},B^{(k)}$ with ${\rm rge\;}\big{(}{B^{(k)}},{A^{(k)}})\in{\cal
S}F(\hat{x}^{(k)},\hat{y}^{(k)})$, we have $A^{(k)}=\nabla
F(\hat{x}^{(k)})B^{(k)}$ and in this case the Newton direction is computed via
$\Delta x^{(k)}=B^{(k)}p=-B^{(k)}\big{(}\nabla
F(\hat{x}^{(k)})B^{(k)}\big{)}^{-1}\hat{y}^{(k)}$. The structure of the second
approach resembles the adjoint system method known from PDE-constrained
optimization and optimal control.

We now consider convergence of Algorithm 1.

######  Proposition 5.3.

Assume that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is SCD
semismooth∗ at $(\bar{x},\bar{y})\in\mathrm{gph}\,F$. Then for every
$\epsilon>0$ there is some $\delta>0$ such that the inequality

$\|x-C_{L}^{T}(y-\bar{y})-\bar{x}\|\leq\epsilon\sqrt{n(1+\|C_{L}\|^{2})}\|(x,y)-(\bar{x},\bar{y})\|$
(40)

holds for every $(x,y)\in\mathrm{gph}\,F\cap{\cal
B}_{\delta}(\bar{x},\bar{y})$ and every $L\in{\cal S}^{*}F(x,y)\cap{\cal
Z}_{n}^{\rm reg}$.

###### Proof.

Pick $\epsilon>0$ and choose $\delta>0$ such that (38) holds. Now consider any
$(x,y)\in\mathrm{gph}\,F\cap{\cal B}_{\delta}(\bar{x},\bar{y})$ and any
$L\in{\cal S}^{*}F(x,y)\cap{\cal Z}_{n}^{\rm reg}$. By Proposition 4.2 we have
$L={\rm rge\;}(C_{L},I)$ and therefore $(C_{L}e_{i},e_{i})\in L$,
$i=1,\ldots,n$, where $e_{i}$ denotes the $i$-th unit vector. From (38) we
obtain

$\displaystyle|\langle e_{i},\bar{x}-x\rangle-\langle
C_{L}e_{i},\bar{y}-y\rangle|$ $\displaystyle=|\langle
e_{i},x-C_{L}^{T}(y-\bar{y})-\bar{x}\rangle|\leq\epsilon\|(e_{i},C_{L}e_{i})\|\|(x,y)-(\bar{x},\bar{y})\|$
$\displaystyle\leq\epsilon\sqrt{1+\|C_{L}\|^{2}}\|(x,y)-(\bar{x},\bar{y})\|$

and

$\|x-C_{L}^{T}(y-\bar{y})-\bar{x}\|\leq\epsilon\sqrt{n(1+\|C_{L}\|^{2})}\|(x,y)-(\bar{x},\bar{y})\|$

follows. ∎

Given $\eta,\kappa>0$, we now define for $x\in\mathbb{R}^{n}$ the set

${\cal
G}^{\eta,\kappa}_{F,\bar{x}}(x):=\\{(\hat{x},\hat{y},L)\mid\;(\hat{x},\hat{y})\in\mathrm{gph}\,F,\
\|(\hat{x},\hat{y})-(\bar{x},0)\|\leq\eta\|x-\bar{x}\|,L\in{\cal
S}^{*}F(\hat{x},\hat{y})\cap{\cal Z}_{n}^{\rm reg},\|C_{L}\|\leq\kappa\\}.$

######  Theorem 5.4.

Assume that $F$ is SCD semismooth∗ at $(\bar{x},0)\in\mathrm{gph}\,F$ and
assume that there are $\eta,\kappa>0$ such that for every $x\not\in F^{-1}(0)$
sufficiently close to $\bar{x}$ we have ${\cal
G}_{F,\bar{x}}^{L,\kappa}(x)\not=\emptyset$. Then there exists some $\delta>0$
such that for every starting point $x^{(0)}\in{\cal B}_{\delta}(\bar{x})$
Algorithm 1 either stops after finitely many iterations at a solution or
produces a sequence $x^{(k)}$ which converges superlinearly to $\bar{x}$,
provided we choose in every iteration
$(\hat{x}^{(k)},\hat{y}^{(k)},L^{(k)})\in{\cal
G}_{F,\bar{x}}^{\eta,\kappa}(x^{(k)})$.

###### Proof.

Using Proposition 5.3 with $\bar{y}=0$, we can find some $\bar{\delta}>0$ such
that (40) holds with $\epsilon=\frac{1}{2\eta\sqrt{n(1+\kappa^{2})}}$ for all
$(x,y)\in\mathrm{gph}\,F\cap{\cal B}_{\bar{\delta}}(\bar{x},0)$ and all
$L\in{\cal S}^{*}F(x,y)\cap{\cal Z}_{n}^{\rm reg}$. Set
$\delta:=\bar{\delta}/\eta$ and consider an iterate $x^{(k)}\in{\cal
B}_{\delta}(\bar{x})\not\in F^{-1}(0)$. Then

$\|(\hat{x}^{(k)},\hat{y}^{(k)})-(\bar{x},0)\|\leq\eta\|x^{(k)}-\bar{x}\|\leq\bar{\delta}$

and consequently

$\|x^{(k+1)}-\bar{x}\|\leq\frac{1}{2\eta\sqrt{n(1+\kappa^{2})}}\sqrt{n(1+\kappa^{2})}\|(\hat{x}^{(k)},\hat{y}^{(k)})-(\bar{x},0)\|\leq\frac{1}{2}\|x^{(k)}-\bar{x}\|$

by Proposition 5.3. It follows that for every starting point $x^{(0)}\in{\cal
B}_{\delta}(\bar{x})$ Algorithm 1 either stops after finitely many iterations
with a solution or produces a sequence $x^{(k)}$ converging to $\bar{x}$. The
superlinear convergence of the sequence $x^{(k)}$ is now an easy consequence
of Proposition 5.3. ∎

So far Algorithm 1 is only a straightforward adaption of the semismooth∗
Newton method from [14] to SCD mappings. However, in [14] the semismooth∗
Newton method was only guaranteed to converge under the assumption of strong
metric regularity, whereas we will now prove that for its SCD variant a less
restrictive condition is sufficient.

######  Proposition 5.5.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ be SCD regular around
$(\bar{x},0)\in\mathrm{gph}\,F$. Then for every $\eta>0$ and every
$\kappa>{\rm scd\,reg\;}F(\bar{x},0)$ there is a neighborhood $U$ of $\bar{x}$
such that for every $x\in U$ the set ${\cal G}^{\eta,\kappa}_{F,\bar{x}}(x)$
is nonempty and amounts to

${\cal
G}^{\eta,\kappa}_{F,\bar{x}}(x)=\big{\\{}(\hat{x},\hat{y},L)\mid\;(\hat{x},\hat{y})\in\mathrm{gph}\,F,\
\|(\hat{x},\hat{y})-(\bar{x},0)\|\leq\eta\|x-\bar{x}\|,L\in{\cal
S}^{*}F(\hat{x},\hat{y})\big{\\}}.$ (41)

###### Proof.

By Proposition 4.8 we can find some positive radius $\rho$ such that $F$ is
SCD regular around $(x,y)$ with modulus ${\rm scd\,reg\;}F(x,y)\leq\kappa$ for
every $(x,y)\in\mathrm{gph}\,F\cap{\cal B}_{\rho}(\bar{x},0)$. By taking
$U:={\cal B}_{\rho/\eta}(\bar{x})$, for every $x\in U$ and every
$(\hat{x},\hat{y})\in\mathrm{gph}\,F$ with
$\|(\hat{x},\hat{y})-(\bar{x},0)\|\leq\eta\|x-\bar{x}\|$ we have
$(\hat{x},\hat{y})\in{\cal B}_{\rho}(\bar{x},0)$. By (34) we obtain that
$\|C_{L}\|\leq\kappa$ whenever $L\in{\cal S}^{*}F(\hat{x},\hat{y})$ and the
assertion follows. ∎

Since in (41) the right hand side does not depend on $\kappa$, we obtain the
following corollary of Theorem 5.4.

######  Corollary 5.6.

Assume that $F$ is SCD semismooth∗ at $(\bar{x},0)\in\mathrm{gph}\,F$ and SCD
regular around $(\bar{x},0)$. Then for every $\eta>0$ there is a neighborhood
$U$ of $\bar{x}$ such that for every starting point $x^{(0)}\in U$ Algorithm 1
is well-defined and either stops after finitely many iterations at a solution
of (36) or produces a sequence $x^{(k)}$ converging superlinearly to $\bar{x}$
for any choice of $(\hat{x}^{(k)},\hat{y}^{(k)})$ satisfying (39) and any
$L^{(k)}\in{\cal S}^{*}F(\hat{x}^{(k)},\hat{y}^{(k)})$.

######  Remark 5.7.

Note that Corollary 5.6 guarantees not only locally superlinear convergence,
but also that the method is locally well-defined, which is an advantage in
comparison with the Josephy-Newton method from [18]. In Theorem 6.2 below we
will show that, under the assumptions of Corollary 5.6, the mapping $F$ is
strongly metrically subregular at $(\bar{x},0)$. By [5, Theorem 6.1], in such
a case the convergence of the Josephy-Newton method is also locally
superlinear, provided the method is well-defined. This, however, need not be
the case as illustrated in [14, Example 5.13], where the assumptions of
Corollary 5.6 are fulfilled, the semismooth∗ Newton method works well, but the
Jospehy-Newton method collapses.

##  6 Strong metric subregularity on a neighborhood

We first present a characterization of strong metric subregularity on a
neighborhood, cf. Definition 2.8, by means of the outer limiting graphical
derivative defined in Definition 3.8.

######  Theorem 6.1.

Consider a mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and let
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$. Then $F$ is strongly metrically
subregular around $(\bar{x},\bar{y})$ if and only if the condition

$0\in D^{\sharp}F(\bar{x},\bar{y})(u)\ \Rightarrow u=0$ (42)

holds and in this case one has

${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y})=\sup\\{\|u\|\mid\;(u,v)\in\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y}),\
\|v\|\leq 1\\}.$ (43)

###### Proof.

We prove the ”if”-part by contraposition. Assume that (42) holds but $F$ is
not strongly metrically subregular around $(\bar{x},\bar{y})$. Then we can
find a sequence
$(x_{k},y_{k})\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})$
such that either $F$ is not strongly metrically subregular at $(x_{k},y_{k})$
for infinitely many $k$ or $\limsup_{k\to\infty}{\rm
subreg\,}F(x_{k},y_{k})=\infty$. After possibly passing to some subsequence
and taking into account Theorem 2.7, in both cases there is a sequence
$\kappa_{k}\to\infty$ and $(u_{k},v_{k})\in\mathrm{gph}\,DF(x_{k},y_{k})$ with
$\|v_{k}\|\leq 1$ such that $\|u_{k}\|>\kappa_{k}\|v_{k}\|$. Defining
$(\tilde{u}_{k},\tilde{v}_{k}):=(u_{k},v_{k})/\|u_{k}\|\in\mathrm{gph}\,DF(x_{k},y_{k})$,
we have $\|\tilde{v}_{k}\|\leq 1/\kappa_{k}$ implying
$\lim_{k\to\infty}\tilde{v}_{k}=0$. By possibly passing to a subsequence once
more, $\tilde{u}_{k}$ converges to some $u$ with $\|u\|=1$ and from the
definition of $D^{\sharp}F(\bar{x},\bar{y})$ we obtain
$(u,0)\in\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y})$ contradicting (42). This
proves the ”if”-part.

In order to show the ”only if”-part assume that (42) does not hold, so that
there is some $u\not=0$ with
$(u,0)\in\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y})$. By definition of
$D^{\sharp}F(\bar{x},\bar{y})$ there are sequences
$(x_{k},y_{k})\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})$
and $(u_{k},v_{k})\to(u,0)$ with
$(u_{k},v_{k})\in\mathrm{gph}\,DF(x_{k},y_{k})$. If $F$ is not strongly
metrically subregular at $(x_{k},y_{k})$ for infinitely many $k$, then it is
not strongly metrically subregular around $(\bar{x},\bar{y})$ by definition.
On the other hand, if $F$ is strongly metrically subregular at $(x_{k},y_{k})$
then $v_{k}\not=0$ and ${\rm subreg\,}F(x_{k},y_{k})\geq\|u_{k}\|/\|v_{k}\|$,
which follows from Theorem 2.7. Hence, $\limsup_{k\to\infty}{\rm
subreg\,}F(x_{k},y_{k})=\infty$ and $F$ is again not strongly metrically
subregular around $(\bar{x},\bar{y})$. This proves the ”only if”-part. There
remains to show (43). By definition we have

${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y})=\limsup_{(x,y)\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})}\sup\\{\|u\|\mid\;(u,v)\in\mathrm{gph}\,DF(x,y),\|v\|\leq
1\\}$

and therefore there are sequences
$(x_{k},y_{k})\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})$
and $(u_{k},v_{k})\in\mathrm{gph}\,DF(x_{k},y_{k})$ with $\|v_{k}\|\leq 1$ and
$\|u_{k}\|\to{\rm l\mbox{-}subreg\,}F(\bar{x},\bar{y})<\infty$. By possibly
passing to a subsequence, $(u_{k},v_{k})$ converges to some $(u,v)$ with
$\|v\|\leq 1$. By definition of $D^{\sharp}F$ we have
$(u,v)\in\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y})$ and ${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y})=\|u\|\leq\xi:=\sup\\{\|u\|\mid\;\exists
v:\ (u,v)\in\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y}),\ \|v\|\leq 1\\}$
follows. Next consider a sequence
$(u_{k},v_{k})\in\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y})$ with
$\|v_{k}\|\leq 1$ and $\|u_{k}\|\to\xi$. Then for every $k$ there are
$(x_{k},y_{k})\in\mathrm{gph}\,F$ and
$(u_{k}^{\prime},v_{k}^{\prime})\in\mathrm{gph}\,DF(x_{k},y_{k})$ such that
$\|(x_{k},y_{k})-(\bar{x},\bar{y})\|\leq\frac{1}{k}$ and
$(\|u_{k}^{\prime},v_{k}^{\prime})-(u_{k},v_{k})\|\leq\frac{1}{k}$ and

${\rm
subreg\,}F(x_{k},y_{k})\geq\xi_{k}:=\begin{cases}\frac{\|u_{k}^{\prime}\|}{\|v_{k}^{\prime}\|}&\mbox{if
$\|v_{k}^{\prime}\|>1$}\\\ \|u_{k}^{\prime}\|&\mbox{if $\|v_{k}^{\prime}\|\leq
1$}\end{cases}$

follows. In case when $\|v_{k}^{\prime}\|>1$ we have

$|\frac{\|u_{k}^{\prime}\|}{\|v_{k}^{\prime}\|}-\|u_{k}^{\prime}\||=\frac{\|v_{k}^{\prime}\|-1}{\|v_{k}^{\prime}\|}\|u_{k}^{\prime}\|\leq\frac{1}{k+1}\|u_{k}^{\prime}\|$

and $\lim_{k\to\infty}\xi_{k}=\xi$ follows. Hence ${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y})\geq\limsup_{k\to\infty}\xi_{k}=\xi$ and
relation (43) is established. ∎

From Lemma 3.10 together with Lemma 4.5, we may conclude that strong metric
subregularity around $(\bar{x},\bar{y})\in\mathrm{gph}\,F$ implies SCD
regularity around $(\bar{x},\bar{y})$ and that ${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y})\geq{\rm scd\,reg\;}F(\bar{x},\bar{y})$.
Next we show that, conversely, SCD regularity in conjunction with SCD
semismoothness* provides a sufficient condition for strong metric
subregularity.

######  Theorem 6.2.

Assume that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is SCD regular
around $(\bar{x},\bar{y})\in\mathrm{gph}\,F$. Then for every $\kappa>{\rm
scd\,reg\;}F(\bar{x},\bar{y})$ there is a neighborhood $W$ of
$(\bar{x},\bar{y})$ such that $F$ is strongly metrically subregular with
modulus ${\rm subreg\,}F(x,y)<\kappa$ at every point
$(x,y)\in\mathrm{gph}\,F\cap W$ where $F$ is SCD semismooth∗ .

###### Proof.

Fixing $\kappa>\tilde{\kappa}>{\rm scd\,reg\;}F(\bar{x},\bar{y})$, by
Proposition 4.8 there is an open neighborhood $W$ of $(\bar{x},\bar{y})$ such
that for every $(x,y)\in\mathrm{gph}\,F\cap W$ the mapping $F$ is SCD regular
around $(x,y)$ with modulus ${\rm scd\,reg\;}F(x,y)\leq\tilde{\kappa}$ .
Consider $(\tilde{x},\tilde{y})\in\mathrm{gph}\,F\cap W$ where $F$ is SCD
semismooth∗ . Assume now that $F$ is not metrically subregular at
$(\tilde{x},\tilde{y})$ or that ${\rm
subreg\,}F(\tilde{x},\tilde{y})>\tilde{\kappa}$. Then there is some
$\kappa^{\prime}>\tilde{\kappa}$ and a sequence $x_{k}$ converging to
$\tilde{x}$ such that
$\operatorname{dist}(x_{k},F^{-1}(\tilde{y}))>\kappa^{\prime}\operatorname{dist}(\tilde{y},F(x_{k}))$
$\forall k$. Consider $y_{k}\in F(x_{k})$ with
$\operatorname{dist}(\tilde{y},F(x_{k}))=\|y_{k}-\tilde{y}\|$. Then $y_{k}$
converges to $\tilde{y}$ and for all $k$ sufficiently large we have
$(x_{k},y_{k})\in\mathrm{gph}\,F\cap W$. Pick $L_{k}\in{\cal
S}^{*}F(x_{k},y_{k})$. Using Proposition 5.3 and (34) we have that
$\|C_{L_{k}}\|\leq\tilde{\kappa}$ and

$\|x_{k}-C_{L_{k}}^{T}(y_{k}-\tilde{y})-\tilde{x}\|\leq\frac{1}{k}\sqrt{n(1+\|C_{L_{k}}\|^{2})}\|(x_{k}-\tilde{x},y_{k}-\tilde{y})\|\leq\frac{1}{k}\sqrt{n(1+\tilde{\kappa}^{2})}(\|x_{k}-\tilde{x}\|+\|y_{k}-\tilde{y}\|)$

implying

$(1-\alpha_{k})\|x_{k}-\tilde{x}\|\leq\|C_{L_{k}}(y_{k}-\tilde{y})\|+\alpha_{k}\|y_{k}-\tilde{y}\|\leq(\tilde{\kappa}+\alpha_{k})\|y_{k}-\tilde{y}\|,$

where $\alpha_{k}:=\frac{1}{k}\sqrt{n(1+\tilde{\kappa}^{2})}$. Since
$\alpha_{k}\to 0$ as $k\to\infty$, we have
$(\tilde{\kappa}+\alpha_{k})/(1-\alpha_{k})<\kappa^{\prime}$ for all $k$
sufficiently large and therefore
$\|x_{k}-\tilde{x}\|<\kappa^{\prime}\|y_{k}-\tilde{y}\|$ in contrary to our
assumption. This shows that $F$ is metrically subregular at
$(\tilde{x},\tilde{y})$ and ${\rm
subreg\,}F(\tilde{x},\tilde{y})\leq\tilde{\kappa}<\kappa$. Further $\tilde{x}$
must be an isolated point in $F^{-1}(\tilde{y})$. Assume on the contrary that
there is a sequence $x_{k}\in F^{-1}(\tilde{y})$ converging to $\tilde{x}$.
Taking $L_{k}\in{\cal S}^{*}F(x_{k},\tilde{y})$ and applying Proposition 5.3
with $\epsilon=1/(2\sqrt{n(1+\tilde{\kappa}^{2})}$, we obtain for all $k$
sufficiently large

$\|x_{k}-\tilde{x}\|=\|x_{k}-C_{L_{k}}^{T}(\tilde{y}-\tilde{y})-\tilde{x}\|\leq\frac{1}{2}\|(x_{k}-\tilde{x},\tilde{y}-\tilde{y})\|=\frac{1}{2}\|x_{k}-\tilde{x}\|,$

a contradiction. This shows that $F$ is even strongly metrically subregular at
$(\tilde{x},\tilde{y})$. ∎

######  Remark 6.3.

In the special case of a single-valued locally Lipschitzian mapping
$F:\mathbb{R}^{n}\to\mathbb{R}^{n}$ the statement of Theorem 6.2 can be
derived also from [15, Proposition 1].

For semismooth∗ mappings we arrive thus at the following equivalence.

######  Corollary 6.4.

Assume that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is SCD
semismooth∗ around $(\bar{x},\bar{y})\in\mathrm{gph}\,F$. Then $F$ is strongly
metrically subregular around $(\bar{x},\bar{y})$ if and only if $F$ is SCD
regular around $(\bar{x},\bar{y})$ and in this case one has ${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y})={\rm scd\,reg\;}F(\bar{x},\bar{y})$.

######  Example 6.5.

Consider the mapping $F:=\mathbb{R}^{2}\rightrightarrows\mathbb{R}^{2}$ given
by

$F(x_{1},x_{2}):=\left(\begin{array}[]{c}x_{1}\\\
-x_{2}\end{array}\right)+h(x)+N_{C}(x_{1},x_{2}),$

where $C:=\\{(x_{1},x_{2})\mid\;-\frac{1}{2}x_{1}\leq
x_{2}\leq\frac{1}{2}x_{1}\\}$ is a convex polyhedral cone and
$h:\mathbb{R}^{2}\to\mathbb{R}^{2}$ is any continuously differentiable mapping
satisfying $h(0,0)=(0,0)$, $\nabla h(0,0)=0$. As the reference point we take
$(\bar{x},\bar{y})=\big{(}(0,0),(0,0)\big{)}$. The mapping $N_{C}$ is a
polyhedral mapping and therefore semismooth∗ at any point of its graph by
[14]. Further, $N_{C}(x)=\partial\delta_{C}(x)$ is an SCD mapping by Corollary
3.28. Thus, $F$ is both an SCD mapping around and semismooth∗ at any point of
its graph, because it differs from $N_{C}$ by a continuously differentiable
mapping. Now let us calculate ${\cal S}^{*}F(\bar{x},\bar{y})$. The critical
cone ${\cal K}_{C}(\bar{x},\bar{y})$ amounts to $C$ and has therefore the 4
faces $C$, $\\{(u,\frac{1}{2}u)\mid\;u\geq 0\\}$,
$\\{(u,-\frac{1}{2}u)\mid\;u\geq 0\\}$ and $\\{(0,0)\\}$. By using Example
3.29 we conclude that ${\cal S}^{*}N_{C}(0,0)$ consists of the 4 subspaces
$L_{1}:=\mathbb{R}^{2}\times\\{(0,0)\\}$,
$L_{2}:=\\{((u,\frac{1}{2}u),(-\frac{1}{2}v,v))\mid\;(u,v)\in\mathbb{R}^{2}\\}$,
$L_{3}:=\\{((u,-\frac{1}{2}u),(\frac{1}{2}v,v))\mid\;(u,v)\in\mathbb{R}^{2}\\}$
and $L_{4}:=\\{(0,0)\\}\times\mathbb{R}^{2}$ and Proposition 3.15 tells us
that ${\cal S}^{*}F(\bar{x},\bar{y})=\\{TL_{1},TL_{2},TL_{3},TL_{4}\\}$ where

$T=\left(\begin{matrix}1&0&0&0\\\ 0&1&0&0\\\ 1&0&1&0\\\
0&-1&0&1\end{matrix}\right).$

Straightforward calculations yield

$\displaystyle
TL_{1}=\\{((u,v),(u,-v))\mid\;(u,v)\in\mathbb{R}^{2}\\},TL_{2}=((u,\frac{1}{2}u),(u-\frac{1}{2}v,-\frac{1}{2}u+v))\mid\;(u,v)\in\mathbb{R}^{2}\\},$
$\displaystyle
TL_{3}=\\{((u,-\frac{1}{2}u),(u+\frac{1}{2}v,\frac{1}{2}u+v))\mid\;(u,v)\in\mathbb{R}^{2}\\},\
TL_{4}=\\{((0,0),(u,v))\mid\;(u,v)\in\mathbb{R}^{2}\\}.$

Now it easily follows that $F$ is SCD regular around $(\bar{x},\bar{y})$ with

$\displaystyle C_{TL_{1}}=\left(\begin{matrix}1&0\\\ 0&-1\end{matrix}\right),\
C_{TL_{2}}=\left(\begin{matrix}\frac{4}{3}&\frac{2}{3}\\\
\frac{2}{3}&\frac{1}{3}\end{matrix}\right),\
C_{TL_{3}}=\left(\begin{matrix}\frac{4}{3}&-\frac{2}{3}\\\
-\frac{2}{3}&\frac{1}{3}\end{matrix}\right),\
C_{TL_{4}}=\left(\begin{matrix}0&0\\\ 0&0\end{matrix}\right)$

and $\|C_{TL_{1}}\|=1$, $\|C_{TL_{2}}\|=\|C_{TL_{3}}\|=\frac{5}{3}$,
$\|C_{TL_{4}}\|=0$. Hence, by virtue of Theorem 6.2, $F$ is strongly
metrically subregular around $(\bar{x},\bar{y})$ with modulus ${\rm
l\mbox{-}subreg\,}F(\bar{x},\bar{y})=\frac{5}{3}$.

To illustrate this result, we explicitly compute $F^{-1}$ in case $h=0$. One
obtains that

$F^{-1}(y)=\begin{cases}\big{\\{}z_{1}(y)\big{\\}}&\mbox{if
$-\frac{1}{2}y_{1}+y_{2}>0,\;2y_{1}+y_{2}\geq 0$,}\\\
\big{\\{}z_{1}(y),z_{2}(y),z_{3}(y)\big{\\}}&\mbox{if
$-\frac{1}{2}y_{1}+y_{2}\leq 0,\;-\frac{1}{2}y_{1}-y_{2}\leq 0$,}\\\
\big{\\{}z_{3}(y)\big{\\}}&\mbox{if
$-\frac{1}{2}y_{1}-y_{2}>0,\;2y_{1}-y_{2}\geq 0$,}\\\
\big{\\{}z_{4}(y)\big{\\}}&\mbox{if $2y_{1}+y_{2}\leq 0,\;2y_{1}-y_{2}\leq
0\big{\\}}$,}\\\ \end{cases}$ (44)

with the mappings $z_{i}(y)$, $i=1,\ldots,4$, in (44) specified via

$\displaystyle z_{1}(y)$ $\displaystyle:=$
$\displaystyle\Big{(}\frac{4}{3}y_{1}+\frac{2}{3}y_{2},\frac{2}{3}y_{1}+\frac{1}{3}y_{2}\Big{)},\;z_{2}(y):=(y_{1},-y_{2}),$
$\displaystyle z_{3}(y)$ $\displaystyle:=$
$\displaystyle\Big{(}\frac{4}{3}y_{1}-\frac{2}{3}y_{2},-\frac{2}{3}y_{1}+\frac{1}{3}y_{2}\Big{)},\;z_{4}(y):=(0,0).$

We see that $F^{-1}$ has the isolated calmness property at every point of its
graph close to $(0,0)$, but it is not single-valued.

##  7 On strong metric regularity

Our results on strong metric regularity pertain again mappings
$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and are partly expressed in
terms of certain bases for the subspaces $L\in{\cal S}F(\bar{x},\bar{y})$.

Given a mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ which is
graphically Lipschitzian of dimension $n$ at
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$ with transformation mapping $\Phi$
according to Definition 3.16, we denote by
$\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ the collection of all $2n\times
n$ matrices $Z$ such that ${\rm rge\;}Z\in{\cal S}F(\bar{x},\bar{y})$ and
$\pi_{1}(\nabla\Phi(\bar{x},\bar{y})Z)=I$.

Note that by Proposition 3.17 for every $L\in{\cal S}F(\bar{x},\bar{y})$ there
exists a unique $Z\in\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})\cap{\cal
M}(L)$. Since for every Lipschitzian mapping $f:U\to\mathbb{R}^{n}$,
$U\subset\mathbb{R}^{n}$ open, the B-subdifferential $\overline{\nabla}f(u)$
is compact for every $u\in U$, we conclude from (24c) that
$\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ is compact as well.

The next statement provides us with an upper approximation of the graphs of
the strict derivative and the limiting coderivative, respectively.

######  Proposition 7.1.

Let $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ be graphically
Lipschitzian at $(\bar{x},\bar{y})\in\mathrm{gph}\,F$ with transformation
mapping $\Phi$. Then

$\displaystyle\mathrm{gph}\,D_{*}F(\bar{x},\bar{y})\subseteq\bigcup_{Z\in{\rm
conv\,}\overline{\nabla}^{\Phi}F(\bar{x},\bar{y})}{\rm rge\;}Z,$ (45)
$\displaystyle\mathrm{gph}\,D^{*}F(\bar{x},\bar{y})\subseteq\bigcup_{Z\in{\rm
conv\,}\overline{\nabla}^{\Phi}F(\bar{x},\bar{y})}({\rm rge\;}Z)^{*}$ (46)

###### Proof.

According to Definition 3.16 consider the open neighborhoods $W$ of
$(\bar{x},\bar{y})$, $U$ of $\bar{w}$ and the Lipschtitzian mapping
$f:U\to\mathbb{R}^{n}$ with $\Phi(\mathrm{gph}\,F\cap W)=\mathrm{gph}\,f$,
where $\bar{w}=\pi_{1}(\Phi(\bar{x},\bar{y}))$. Consider
$(u,v)\in\mathrm{gph}\,D_{*}F(\bar{x},\bar{y})$ together with sequences
$(x^{1}_{k},y^{1}_{k})\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})$,
$(x^{2}_{k},y^{2}_{k})\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})$
and $t_{k}\downarrow 0$ such that
$(u,v)=\lim_{k\to\infty}(x^{2}_{k}-x^{1}_{k},y^{2}_{k}-y^{1}_{k})/t_{k}$. For
each $k$ let $w^{i}_{k}$, $i=1,2$ be given by
$w^{i}_{k}=\pi_{1}(\Phi(x^{i}_{k},y^{i}_{k}))$. Then

$\displaystyle(w^{2}_{k}-w^{1}_{k},f(w^{2}_{k})-f(w^{1}_{k}))$
$\displaystyle=\Phi(x^{2}_{k},y^{2}_{k})-\Phi(x^{1}_{k},y^{1}_{k})=\nabla\Phi(\bar{x},\bar{y})(x^{2}_{k}-x^{1}_{k},y^{2}_{k}-y^{1}_{k})+o(\|(x^{2}_{k}-x^{1}_{k},y^{2}_{k}-y^{1}_{k})\|)$
$\displaystyle=\nabla\Phi(\bar{x},\bar{y})(x^{2}_{k}-x^{1}_{k},y^{2}_{k}-y^{1}_{k})+o(t_{k})$

implying that

$\lim_{k\to\infty}\frac{(w^{2}_{k}-w^{1}_{k},f(w^{2}_{k})-f(w^{1}_{k}))}{t_{k}}=\lim_{k\to\infty}\nabla\Phi(\bar{x},\bar{y})\frac{(x^{2}_{k}-x^{1}_{k},y^{2}_{k}-y^{1}_{k})}{t_{k}}=\nabla\Phi(\bar{x})(u,v)\in\mathrm{gph}\,D_{*}f(\bar{w}).$

Hence $\pi_{2}(\nabla\Phi(\bar{x})(u,v))\in
D_{*}f(\bar{w})(\pi_{1}(\nabla\Phi(\bar{x})(u,v)))$ and by [34, Theorem 9.62]
there is some $B\in{\rm conv\,}\overline{\nabla}f(\bar{w})$ satisfying
$\pi_{2}(\nabla\Phi(\bar{x})(u,v))=B\pi_{1}(\nabla\Phi(\bar{x})(u,v))$ which
is the same as $\nabla\Phi(\bar{x})(u,v)\in{\rm rge\;}(I,B)$. $B$ can be
expressed as a convex combination $\sum_{i=1}^{N}\alpha_{i}B_{i}$ with
$B_{i}\in\overline{\nabla}f(\bar{w})$, $\alpha_{i}\geq 0$,
$\sum_{i=1}^{N}\alpha_{i}=1$ and therefore

$(u,v)\in\nabla\Phi(\bar{x},\bar{y})^{-1}{\rm
rge\;}(I,B)=\Phi(\bar{x},\bar{y})^{-1}{\rm
rge\;}\Big{[}\sum_{i=1}^{N}\alpha_{i}\left(\begin{array}[]{c}I\\\
B_{i}\end{array}\right)\Big{]}={\rm
rge\;}\Big{[}\sum_{i=1}^{N}\alpha_{i}\Phi(\bar{x},\bar{y})^{-1}\left(\begin{array}[]{c}I\\\
B_{i}\end{array}\right)\Big{]}.$

Denoting $Z_{i}:=\Phi(\bar{x},\bar{y})^{-1}\left(\begin{array}[]{c}I\\\
B_{i}\end{array}\right)$ we have ${\rm rge\;}Z_{i}\in{\cal
S}F(\bar{x},\bar{y})$ by (24c) and $\pi_{1}(\Phi(\bar{x},\bar{y})Z_{i})=I$
yielding $Z_{i}\in\overline{\nabla}^{\Phi}F(\bar{x},\bar{y})$. Thus
$(u,v)\in{\rm rge\;}Z$ with $Z=\sum_{i=1}^{N}\alpha_{i}Z_{i}\in{\rm
conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ verifying (45).

Now consider $(y^{*},x^{*})\in\mathrm{gph}\,D^{*}F(\bar{x},\bar{y})$ which is
the same as

$S_{n}^{T}(y^{*},x^{*})\in
N_{\mathrm{gph}\,F}(\bar{x},\bar{y})=\nabla\Phi(\bar{x},\bar{y})^{T}N_{\mathrm{gph}\,f}(\bar{w},f(\bar{w}),$

where the second equality follows from [34, Exercise 6.7]. Hence
$z^{*}:=S_{n}\nabla\Phi(\bar{x},\bar{y})^{-T}S_{n}^{T}(y^{*},x^{*})\in
S_{n}N_{\mathrm{gph}\,f}(\bar{w},f(\bar{w})=\mathrm{gph}\,D^{*}f(\bar{w})$
implying $\pi_{2}(z^{*})\in D^{*}f(\bar{w})(\pi_{1}(z^{*}))$. By [34, Theorem
9.62] there is some $B\in{\rm conv\,}\overline{\nabla}f(\bar{w})$ such that
$\pi_{2}(z^{*})=B^{T}\pi_{1}(z^{*})$ which is the same as $z^{*}\in{\rm
rge\;}(I,B^{T})$ and

$(y^{*},x^{*})\in{\rm
rge\;}\Big{[}S_{n}\nabla\Phi(\bar{x},\bar{y})^{T}S_{n}^{T}\left(\begin{array}[]{c}I\\\
B^{T}\end{array}\right)\Big{]}$

follows. Taking into account that

${\rm
rge\;}\Big{[}S_{n}\nabla\Phi(\bar{x},\bar{y})^{T}S_{n}^{T}\left(\begin{array}[]{c}I\\\
B^{T}\end{array}\right)\Big{]}^{\perp}={\rm
rge\;}\Big{[}S_{n}\nabla\Phi(\bar{x},\bar{y})^{-1}S_{n}^{T}\left(\begin{array}[]{c}B\\\
-I\end{array}\right)\Big{]}={\rm
rge\;}\Big{[}-S_{n}\nabla\Phi(\bar{x},\bar{y})^{-1}\left(\begin{array}[]{c}I\\\
B\end{array}\right)\Big{]},$

we obtain

${\rm
rge\;}\Big{[}S_{n}\nabla\Phi(\bar{x},\bar{y})^{T}S_{n}^{T}\left(\begin{array}[]{c}I\\\
B^{T}\end{array}\right)\Big{]}^{*}=S_{n}{\rm
rge\;}\Big{[}-S_{n}\nabla\Phi(\bar{x},\bar{y})^{-1}\left(\begin{array}[]{c}I\\\
B\end{array}\right)\Big{]}={\rm
rge\;}\Big{[}\nabla\Phi(\bar{x},\bar{y})^{-1}\left(\begin{array}[]{c}I\\\
B\end{array}\right)\Big{]}.$

As we have shown above, the latter subspace equals to ${\rm rge\;}Z$ with
$Z\in{\rm conv\,}\overline{\nabla}^{\Phi}F(\bar{x},\bar{y})$ and
$(y^{*},x^{*})\in({\rm rge\;}Z)^{*}$ follows. ∎

On the basis of Proposition 7.1 we can now establish the following
characterization of strong metric regularity.

######  Theorem 7.2.

Consider a mapping $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and let
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$.

  1. (i)

If $F$ is strongly metrically regular around $(\bar{x},\bar{y})$ then it is
graphically Lipschitzian of dimension $n$ at $(\bar{x},\bar{y})$ with
transformation mapping $\Phi(x,y)=(y,x)$ and one has that $\\{{\rm
rge\;}Z\mid\;Z\in{\rm
conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})\\}\subseteq{\cal
Z}_{n}^{\rm reg}$. Further, $F$ is SCD regular around $(\bar{x},\bar{y})$ and
${\rm reg\,}F(\bar{x},\bar{y})={\rm scd\,reg\;}F(\bar{x},\bar{y})$.

  2. (ii)

Conversely, if $F$ is graphically Lipschitzian of dimension $n$ at
$(\bar{x},\bar{y})$ with some transformation mapping $\Phi$ such that $\\{{\rm
rge\;}Z\mid\;Z\in{\rm
conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})\\}\subseteq{\cal
Z}_{n}^{\rm reg}$ then $F$ is strongly metrically regular around
$(\bar{x},\bar{y})$.

###### Proof.

If $F$ is strongly metrically regular around $(\bar{x},\bar{y})$, then by
Theorem 2.6 it is clearly graphically Lipschitzian with the given
transformation mapping $\Phi$ and from Proposition 3.17 we obtain ${\cal
S}F(\bar{x},\bar{y})=\\{{\rm
rge\;}(B,I)\mid\;B\in\overline{\nabla}f(\bar{y})\\}$ where $f$ denotes the
Lipschitz continuous localization of $F^{-1}$ around $(\bar{y},\bar{x})$. Thus

$\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})=\Big{\\{}\left(\begin{array}[]{c}B\\\
I\end{array}\right)\mid\;B\in\overline{\nabla}f(\bar{y})\Big{\\}}$

and consequently every matrix $Z\in{\rm
conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ is of the form
$Z=\left(\begin{array}[]{c}B\\\ I\end{array}\right)$ with $B\in{\rm
conv\,}\overline{\nabla}f(\bar{y})$. From this we can easily deduce that
$L:={\rm rge\;}Z\in{\cal Z}_{n}^{\rm reg}$ and $B=C_{L}$ showing that $F$ is
SCD regular. In order to verify the formula for the modulus of strong metric
regularity we use (9). Let $\epsilon>0$ and consider
$(u,v)\in\mathrm{gph}\,D_{*}F(\bar{x},\bar{y})$ with $\|v\|\leq 1$ and
$\|u\|\geq{\rm reg\,}F(\bar{x},\bar{y})-\epsilon$. By Proposition 7.1 there is
some $Z\in{\rm conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ and some
$w\in\mathbb{R}^{n}$ with $(u,v)=Zw$. Thus there is $\bar{B}\in{\rm
conv\,}\overline{\nabla}f(\bar{y})$ such that $u=\bar{B}w$ and $v=w$ yielding

$\displaystyle{\rm reg\,}F(\bar{x},\bar{y})-\epsilon$
$\displaystyle\leq\|u\|\leq\|\bar{B}\|\|v\|\leq\|\bar{B}\|\leq\sup\\{\|B\|\mid\;B\in{\rm
conv\,}\overline{\nabla}f(\bar{y})\\}$
$\displaystyle=\sup\\{\|B\|\mid\;B\in\overline{\nabla}f(\bar{y})\\}=\sup\\{\|C_{L}\|\mid\;L\in{\cal
S}F(\bar{x},\bar{y})\\}={\rm scd\,reg\;}F(\bar{x},\bar{y})$

by Lemma 4.5. Since $\epsilon>0$ can be chosen arbitrarily small, there holds
${\rm reg\,}F(\bar{x},\bar{y})\leq{\rm scd\,reg\;}F(\bar{x},\bar{y})$. On the
other hand, we have $\bigcup{\cal
S}F(\bar{x},\bar{y})\subseteq\mathrm{gph}\,D^{\sharp}F(\bar{x},\bar{y})\subseteq\mathrm{gph}\,D_{*}F(\bar{x},\bar{y})$
implying ${\rm scd\,reg\;}F(\bar{x},\bar{y})\leq{\rm reg\,}F(\bar{x},\bar{y})$
by Lemma 4.5 and (9). This proves (i).

The statement (ii) follows from Theorem 2.7 together with Proposition 7.1. If
$0\in\mathrm{gph}\,D_{*}F(\bar{x},\bar{y})(u)$ then there is some $Z\in{\rm
conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ such that $(u,0)\in{\rm
rge\;}Z$ and $u=0$ follows from ${\rm rge\;}Z\in{\cal Z}_{n}^{\rm reg}$.
Similarly, if $0\in D^{*}F(\bar{x},\bar{y})(y^{*})$ then there is some
$Z\in{\rm conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ such that
$(y^{*},0)\in({\rm rge\;}Z)^{*}$. Since ${\rm rge\;}Z\in{\cal Z}_{n}^{\rm
reg}$, we have $({\rm rge\;}Z)^{*}\in{\cal Z}_{n}^{\rm reg}$ by Proposition
4.2 and $y^{*}=0$ follows. Hence, both (8) and (6) are fulfilled and strong
metric regularity of $F$ has been established. ∎

Consider the special case of a single-valued Lipschitzian mapping
$F:\mathbb{R}^{n}\to\mathbb{R}^{n}$ so that $\Phi(x,y)=(x,y)$. Then
$\overline{\nabla}{}^{\Phi}F(x,F(x))=\\{(I,B)\mid\;B\in\overline{\nabla}F(x)\\}$
by Lemma 3.11 and therefore

${\rm conv\,}\overline{\nabla}{}^{\Phi}F(x,F(x))=\\{(I,B)\mid\;B\in{\rm
conv\,}\overline{\nabla}F(x)\\}.$

Thus the requirement in Theorem 7.2(ii) that $\\{{\rm rge\;}Z\mid\;Z\in{\rm
conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})\\}\subseteq{\cal
Z}_{n}^{\rm reg}$ is equivalent to the condition that every matrix $B$
belonging to Clarke’s generalized Jacobian ${\rm conv\,}\overline{\nabla}F(x)$
is nonsingular. Therefore we may consider Theorem 7.2(ii) as a generalization
of Clarke’s Inverse Function Theorem, see, e.g., [6, Theorem 7.1.1], to set-
valued mappings.

Note that ${\rm reg\,}F(\bar{x},\bar{y})={\rm scd\,reg\;}F(\bar{x},\bar{y})$
whenever $F$ is strongly metrically regular around $(\bar{x},\bar{y})$. This
fact will not be repeated in the following results, where we present
sufficient conditions for strong metric regularity.

The sufficient condition for strong metric regularity in Theorem 7.2(ii)
depends on the particular basis representation
$\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ of ${\cal
S}F(\bar{x},\bar{y})$. The next results are stated in terms of the elements
$L\in{\cal S}F(\bar{x},\bar{y})$ which do not depend on a basis.

######  Corollary 7.3.

Given $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ and a point
$(\bar{x},\bar{y})\in\mathrm{gph}\,F$, assume that ${\cal
S}F(\bar{x},\bar{y})=\\{\bar{L}\\}$ is a singleton. Then $F$ is strongly
metrically regular around $(\bar{x},\bar{y})$ if and only if $F$ is
graphically Lipschitzian of dimension $n$ at $(\bar{x},\bar{y})$ and
$\bar{L}\in{\cal Z}_{n}^{\rm reg}$.

When ${\cal S}F(\bar{x},\bar{y})$ is a singleton and $F$ is not graphically
Lipschitzian at $(\bar{x},\bar{y})$ then $F$ cannot be strongly metrically
regular by Theorem 7.2(i). However, if $F$ is SCD semismooth∗ at (around)
$(\bar{x},\bar{y})$, then it is at least strongly metrically subregular at
(around) $(\bar{x},\bar{y})$. Consider the following example.

######  Example 7.4.

Let $q:\mathbb{R}\to\mathbb{R}$ be given by $q(x)=\frac{2}{3}{\rm
sign\,}(x)|x|^{\frac{3}{2}}$. Then $\partial q(x)=|x|^{\frac{1}{2}}$ is not
graphically Lipschitzian of dimension $1$ at $(0,0)$ but it is an SCD mapping
and SCD semismooth∗ . Further, ${\cal S}\partial
q(0,0)=\\{\\{0\\}\times\mathbb{R}\\}$ is a singleton and clearly
$\\{0\\}\times\mathbb{R}\in{\cal Z}_{n}^{\rm reg}$. Thus we deduce from
Corollary 6.4 that $\partial q$ is strongly metrically subregular around
$(0,0)$. However, $\partial q$ is not strongly metrically regular around
$(0,0)$ because $\partial q^{-1}(y)=\emptyset$ for every $y<0$.

We will now present a basis-independent characterization of strong metric
regularity for locally maximally hypomonotone mappings.

######  Theorem 7.5.

Assume that $F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is locally
maximally hypomonotone at $(\bar{x},\bar{y})\in\mathrm{gph}\,F$. Then the
following two statements are equivalent:

  1. (i)

$F$ is SCD regular around $(\bar{x},\bar{y})$ and for every $L\in{\cal
S}F(\bar{x},\bar{y})$ the matrix $C_{L}$ is positive semidefinite.

  2. (ii)

$F$ is strongly metrically regular around $(\bar{x},\bar{y})$ and

$\liminf_{(x^{1},y^{1}),(x^{2},y^{2})\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})}\frac{\langle
x^{1}-x^{2},y^{1}-y^{2}\rangle}{\|x^{1}-x^{2}\|\|y^{1}-y^{2}\|}\geq 0$ (47)

with the convention $0/0:=0$.

###### Proof.

We first prove (i)$\Rightarrow$(ii). By Corollary 3.23 there is some
$\lambda\geq 1$ such that $F$ is graphically Lipschitzian at
$(\bar{x},\bar{y})$ with transformation mapping $\Phi(x,y)=(\lambda x+y,x)$
and for every $Z\in\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ there is a
firmly nonexpansive $n\times n$ matrix $B$, such that
$Z=\left(\begin{array}[]{c}B\\\ I-\lambda B\end{array}\right)$. Since $F$ is
SCD regular around $(\bar{x},\bar{y})$, $\pi_{2}(Z)=I-\lambda B$ is
nonsingular and $C_{{\rm rge\;}Z}=B(I-\lambda B)^{-1}$. Consider
$u\in\mathbb{R}^{n}$ and set $v:=(I-\lambda B)u$. By the posed assumption,
$B(I-\lambda B)^{-1}$ is positive semidefinite and we obtain

$0\leq\lambda\langle v,B(I-\lambda B)^{-1}v\rangle=\lambda\langle
v,Bu\rangle=\lambda\langle(I-\lambda B)u,Bu\rangle$

implying $\langle u,\lambda Bu\rangle\geq\|\lambda Bu\|^{2}$. Thus $\lambda B$
is firmly nonexpansive and, consequently, $\|2\lambda B-I\|\leq 1$. Since
$I-\lambda B$ is nonsingular, we deduce from [3, Theorem 3.3] that $\|\lambda
B\|<1$. Now consider $\bar{Z}\in{\rm
conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$. It follows that
$\bar{Z}=\left(\begin{array}[]{c}\bar{B}\\\
I-\lambda\bar{B}\end{array}\right)$, where $\bar{B}$ is some convex
combination of matrices $B_{i}$ with $\|\lambda B_{i}\|<1$ and $\|2\lambda
B_{i}-I\|\leq 1$. It follows that $\|\lambda\bar{B}\|<1$ and
$\|2\lambda\bar{B}-I\|\leq 1$. Thus $\pi_{2}(\bar{Z})=I-\lambda\bar{B}$ is
nonsingular and from Proposition 4.2 we may deduce that ${\rm
rge\;}\bar{Z}\in{\cal Z}_{n}^{\rm reg}$. Now strong regularity of $F$ follows
from Theorem 7.2(ii). Next we prove (47) by contraposition. Assume on the
contrary that there are sequences
$(x^{i}_{k},y^{i}_{k})\mathop{\longrightarrow}\limits^{\mathrm{gph}\,F}(\bar{x},\bar{y})$,
$i=1,2$, and some $\eta>0$ such that $\langle
x^{1}_{k}-x^{2}_{k},y_{k}^{1}-y_{k}^{2}\rangle<-\eta\|x_{k}^{1}-x_{k}^{2}\|\|y_{k}^{1}-y_{k}^{2}\|$
for all $k$. By local hypomonotonicity, $\langle
x^{1}_{k}-x^{2}_{k},y^{1}_{k}-y^{2}_{k}\rangle\geq-(\lambda-1)\|x^{1}_{k}-x^{2}_{k}\|^{2}$
and therefore $\lambda>1$ and
$\|x^{1}_{k}-x^{2}_{k}\|\geq\frac{\eta}{\lambda-1}\|y_{k}^{1}-y_{k}^{2}\|$. On
the other hand, by strong metric regularity, choosing $c>{\rm
reg\,}F(\bar{x},\bar{y})$, we have $\|x^{1}_{k}-x^{2}_{k}\|\leq
c\|y_{k}^{1}-y_{k}^{2}\|$ for all $k$ sufficiently large. Let
$t_{k}:=\|y_{k}^{1}-y_{k}^{2}\|+\|x^{1}_{k}-x^{2}_{k}\|$. By possibly passing
to a subsequence, $(x^{1}_{k}-x^{2}_{k},y_{k}^{1}-y_{k}^{2})/t_{k}$ converges
to some $(u,v)\in D_{*}F(\bar{x},\bar{y})$ with $\|u\|+\|v\|=1$,
$\frac{\eta}{\lambda-1}\|v\|\leq\|u\|\leq c\|v\|$ and $\langle
u,v\rangle\leq-\eta\|u\|\|v\|$. We deduce that both $u$ and $v$ are nonzero
and thus $\langle u,v\rangle<0$. By Proposition 7.1 there is some
$\bar{Z}\in{\rm conv\,}\overline{\nabla}{}^{\Phi}F(\bar{x},\bar{y})$ and some
$p\in\mathbb{R}^{n}$ with $(u,v)=\bar{Z}p$. As shown above,
$\bar{Z}=\left(\begin{array}[]{c}\bar{B}\\\
I-\lambda\bar{B}\end{array}\right)$ for some $n\times n$ matrix $\bar{B}$ with
$\|2\lambda\bar{B}-I\|\leq 1$, i.e., $\lambda\bar{B}$ is firmly nonexpansive.
It follows that

$0\leq\langle