A CHAIN RULE FOR STRICT TWICE EPI-DIFFERENTIABILITY AND ITS APPLICATIONS
NGUYEN T. V. HANG111 Institute of Mathematics, Vietnam Academy of Science and
Technology, Hanoi, Vietnam (ntvhang@math.ac.vn). and M. EBRAHIM
SARABI222Department of Mathematics, Miami University, Oxford, OH 45065, USA
(sarabim@miamioh.edu). Research of this author is partially supported by the
U.S. National Science Foundation under the grant DMS 2108546.

Abstract. The presence of second-order smoothness for objective functions of
optimization problems can provide valuable information about their stability
properties and help us design efficient numerical algorithms for solving these
problems. Such second-order information, however, cannot be expected in
various constrained and composite optimization problems since we often have to
express their objective functions in terms of extended-real-valued functions
for which the classical second derivative may not exist. One powerful
geometrical tool to use for dealing with such functions is the concept of
twice epi-differentiability. In this paper, we are going to study a stronger
version of this concept, called strict twice epi-differentiability. We
characterize this concept for certain composite functions and use it to
establish the equivalence of metric regularity and strong metric regularity
for a class of generalized equations at their nondegenerate solutions.
Finally, we present a characterization of continuous differentiability of the
proximal mapping of our composite functions.
Keywords. strict twice epi-differentiability, regularity of subdifferentials,
strict proto-differentiability, generalized equations, nondegenerate
solutions, proximal mappings, chain rule.
Mathematics Subject Classification (2000) 90C31, 65K99, 49J52, 49J53

##  1 Introduction

Twice epi-differentiability of extended-real-valued functions, introduced by
Rockafellar in [29], is a geometric concept that provides approximation of
epigraphs and so differs from the classical quadratic approximation, obtained
from the classical second derivative of functions. Such a geometrical
approximation opens the door to deal with important classes of extended-real-
valued functions, appearing in optimization problems. Despite the fact this
concept was introduced in the late 1980s, major progress has been achieved
recently in [15, 13] in understanding its various properties. It has also been
shown recently that it can be an important tool for conducting convergence
analysis of important numerical algorithms including the Newton method [19]
and the augmented Lagrangian method [7, 31]. This paper aims to study a
stronger version of this concept, called strict twice epi-differentiability,
for an extended-real-valued function $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm
I\\!R}}$, finite at $\bar{x}\in{\rm I\\!R}^{n}$, that enjoys the composite
representation

$\varphi(x)=(g\circ\Phi)(x)\quad\mbox{for all}\;\;x\in{O}$ (1.1)

around $\bar{x}$, where ${O}$ is a neighborhood of $\bar{x}$ and where
$\Phi:{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ is twice continuously differentiable
around $\bar{x}$ and $g:{\rm I\\!R}^{m}\to\overline{{\rm
I\\!R}}:=[-\infty,\infty]$ is a polyhedral function. Recall that a proper
function $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is called polyhedral if
its epigraph, namely the set ${\rm epi}\,g=\\{(z,\alpha)\in{\rm
I\\!R}^{m}\times{\rm I\\!R}|\;g(z)\leq\alpha\\}$, is a polyhedral convex set.
Traditionally, when a function, satisfying the composite representation (1.1),
enjoys a certain constraint qualification, it belongs to an important class of
functions, called fully amenable (cf. [26, Definition 10.23(a)]). We, however,
do not use this terminology since most of the results in this paper require a
different constraint qualification than the one in [26, Definition 10.23(a)].
Note also that the objective functions of a number of important classes of
constrained and composite optimization problems, including classical nonlinear
programming problems, constrained and unconstrained minimax problems, can be
expressed in the composite form (1.1); see Example 2.1 for more details. This
can pave the way to study various stability properties of these optimization
problems and their KKT systems by exploring various variational properties of
the composite form in (1.1).

Strict twice epi-differentiability was first introduced in [21] and was only
studied in [24] for nonlinear programming and minimax problems. Our primary
goal is to present a systematic approach for understanding this concept and
its consequences in stability properties of generalized equations. One may
wonder whether strict twice epi-differentiability leads us to stronger
properties in comparison to those stemming from its weaker version, namely
twice epi-differentiability. In Section 3, we reveal that this stronger
version of twice epi-differentiability render the graph of the subgradient
mapping of $\varphi$ in (1.1) to satisfy an interesting regularity property,
called strict proto-differentiability. Such a property, as demonstrated in
Section 4, has a number of important implications. First, it allows us to
characterize the regularity of the graph of the subgradient mapping of
$\varphi$ in (1.1), which is a highly nonconvex set. Second, we are able to
achieve the equivalence of metric regularity and strong metric regularity for
an important class of generalized equations at their nondegenerate solutions,
which leads us to an extension of a similar result by Dontchev and Rockafellar
in [5]. Using the latter equivalence, we obtain a simple but useful
characterization of continuous differentiability of the proximal mapping of
the composite function $\varphi$ in (1.1). Note that while $\varphi$ may not
be a convex function, it is well-known that its proximal mapping is locally
single-valued (cf. [26, Proposition 13.37]) and directionally differentiable.
Using the concept of strict proto-differentiability, we are going to show that
one should expect a stronger differentiability property of the proximal
mapping, namely continuous differentiability, when certain subgradients of
$\varphi$ are chosen.

In Section 2, first we recall important concepts, used in this paper, and then
establish some elementary properties related to a constraint qualification
that is going to be assumed in most of the results of this paper. Among these
properties are certain metric estimates that allow us to achieve a chain rule
for strict twice epi-differentiability. Section 3 begins with the concept of
the strict second subderivative for which we will establish a chain rule.
Using this result together with a chain rule for epi-convergence of functions,
we achieve a characterization of strict twice epi-differentiability of
$\varphi$ in (1.1) when an appropriate constraint qualification is assumed. In
Section 4, we show that metric regularity and strong metric regualrity are
equivalent for a class of generalized equations at their nondegenerate
solutions. This equivalence is utilized next to obtain a characterization of
continuous differentiability of the proximal mapping of the composite function
in (1.1) as well as twice continuous differentiability of its Moreau envelope.

##  2 Notation and Preliminary Results

In this paper, we denote by $\mathbb{B}$ the closed unit ball in the space in
question and by $\mathbb{B}_{r}(x):=x+r\mathbb{B}$ the closed ball centered at
$x$ with radius $r>0$. Given a nonempty set $C\subset{\rm I\\!R}^{n}$, the
symbols ${\rm ri}\,C$ and ${\rm span}\,C$ signify its relative interior and
the linear space generated by $C$, respectively. For any set $C$ in ${\rm
I\\!R}^{n}$, its indicator function $\delta_{C}$ is defined by
$\delta_{C}(x)=0$ for $x\in C$ and $\delta_{C}(x)=\infty$ otherwise. We denote
by $P_{C}$ the projection mapping onto $C$ and by ${\rm dist}(x,C)$ the
distance between $x\in{\rm I\\!R}^{n}$ and a set $C$. For a vector $w\in{\rm
I\\!R}^{n}$, the subspace $\\{tw|\,t\in{\rm I\\!R}\\}$ is denoted by $[w]$.
The domain and range of a set-valued mapping $F:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ are defined, respectively, by
${\rm dom}\,F:=\\{x\in{\rm I\\!R}^{n}\big{|}\;F(x)\neq\emptyset\\}$ and ${\rm
rge\,}F=\\{u\in{\rm I\\!R}^{m}|\;\exists\,w\in{\rm
I\\!R}^{n}\;\,\mbox{with}\;\;u\in F(x)\\}$.

In what follows, the convergence of a family of sets is always understood in
the sense of Painlevé-Kuratowski (cf. [26, Definition 4.1]). This means that
the inner limit set of a parameterized family of sets $\\{C^{t}\\}_{t>0}$ in
${\rm I\\!R}^{d}$, denoted $\liminf_{t\searrow 0}C^{t}$, is the set of points
$x$ such that for every sequence $t_{k}\searrow 0$, $x$ is the limit of a
sequence of points $x^{t_{k}}\in C^{t_{k}}$. The outer limit set of this
family of sets, denoted $\limsup_{t\searrow 0}C^{t}$, is the set of points $x$
such that there exist sequences $t_{k}\searrow 0$ and $x^{t_{k}}\in C^{t_{k}}$
such that $x^{t_{k}}\to x$ as $k\to\infty$. And, the limit set of
$\\{C^{t}\\}_{t>0}$ exists if the inner and outer limit sets coincide, namely
$\liminf_{t\searrow 0}C^{t}=\limsup_{t\searrow 0}C^{t}=:C$, written as
$C^{t}\to C$ when $t\searrow 0$. A sequence $\\{f^{k}{\\}_{k\in{\rm I\\!N}}}$
of functions $f^{k}:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is said to epi-
converge to a function $f:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ if we have
${\rm epi}\,f^{k}\to{\rm epi}\,f$ as $k\to\infty$; see [26, Definition 7.1]
for more details on the epi-convergence of a sequence of extended-real-valued
functions. We denote by $f^{k}\xrightarrow{e}f$ the epi-convergence of
$\\{f^{k}{\\}_{k\in{\rm I\\!N}}}$ to $f$.

Given a nonempty set $\Omega\subset{\rm I\\!R}^{n}$ with $\bar{x}\in\Omega$,
the tangent cone to $\Omega$ at $\bar{x}$, denoted $T_{\Omega}(\bar{x})$, is
defined by

$T_{\Omega}(\bar{x})=\limsup_{t\searrow 0}\frac{\Omega-\bar{x}}{t}.$

The regular/Fréchet normal cone ${\widehat{N}}_{\Omega}(\bar{x})$ to $\Omega$
at $\bar{x}$ is defined by
${\widehat{N}}_{\Omega}(\bar{z})=T_{\Omega}(\bar{z})^{*}$. The
(limiting/Mordukhovich) normal cone $N_{\Omega}(\bar{x})$ to $\Omega$ at
$\bar{x}$ is the set of all vectors $\bar{v}\in{\rm I\\!R}^{n}$ for which
there exist sequences $\\{x^{k}{\\}_{k\in{\rm I\\!N}}}$ and
$\\{v^{k}{\\}_{k\in{\rm I\\!N}}}$ with $v^{k}\in{\widehat{N}}_{\Omega}(x^{k})$
such that $(x^{k},v^{k})\to(\bar{x},\bar{v})$. When $\Omega$ is convex, both
normal cones boil down to that of convex analysis. Given a function $f:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and a point $\bar{x}\in{\rm I\\!R}^{n}$
with $f(\bar{x})$ finite, the subderivative function ${\rm
d}f(\bar{x})\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is defined by

${\rm d}f(\bar{x})(w)=\liminf_{\begin{subarray}{c}t\searrow 0\\\ w^{\prime}\to
w\end{subarray}}{\frac{f(\bar{x}+tw^{\prime})-f(\bar{x})}{t}}.$

A vector $v\in{\rm I\\!R}^{n}$ is called a subgradient of $f$ at $\bar{x}$ if
$(v,-1)\in N_{{\rm epi}\,f}(\bar{x},f(\bar{x}))$. The set of all subgradients
of $f$ at $\bar{x}$ is denoted by $\partial f(\bar{x})$. Replacing the
limiting normal cone with ${\widehat{N}}_{{\rm epi}\,f}(\bar{x},f(\bar{x}))$
in the definition of $\partial f(\bar{x})$ gives us
${\widehat{\partial}}f(\bar{x})$, which is called the regular subdifferential
of $f$ at $\bar{x}$. The critical cone of $f$ at $\bar{x}$ for $\bar{v}$ with
$\bar{v}\in\partial f(\bar{x})$ is defined by

${K_{f}}(\bar{x},\bar{v})=\big{\\{}w\in{\rm
I\\!R}^{n}\,\big{|}\,\langle\bar{v},w\rangle={\rm d}f(\bar{x})(w)\big{\\}}.$

When $f=\delta_{\Omega}$, where $\Omega$ is a nonempty subset of ${\rm
I\\!R}^{n}$, the critical cone of $\delta_{\Omega}$ at $\bar{x}$ for $\bar{v}$
is denoted by $K_{\Omega}(\bar{x},\bar{v})$. In this case, the above
definition of the critical cone of a function boils down to the well known
concept of the critical cone of a set (see [4, page 109]), namely
$K_{\Omega}(\bar{x},\bar{v})=T_{\Omega}(\bar{x})\cap[\bar{v}]^{\perp}$ because
of ${\rm d}\delta_{\Omega}(\bar{x})=\delta_{T_{\Omega}(\bar{x})}$. If the
function $f$ is convex and $\partial f(\bar{x})\neq\emptyset$, then ${\rm
d}f(\bar{x})$ is the support function of $\partial f(\bar{x})$ (cf. [26,
Theorem 8.30]) and the critical cone $K_{f}(\bar{x},\bar{v})$ can be
equivalently described by

$K_{f}(\bar{x},\bar{v})=N_{\partial f(\bar{x})}(\bar{v}).$ (2.1)

According to [26, Theorem 2.49], a polyhedral function $g:{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ enjoys the representation

$g(z)=\max_{j\in J}\big{\\{}\langle
a^{j},z\rangle-\alpha_{j}\big{\\}}+\delta_{{\rm dom}\,g}(z),\quad z\in{\rm
I\\!R}^{m},$ (2.2)

where $J:=\\{1,\ldots,l\\}$ for some $l\in{\rm I\\!N}$, $a^{j}\in{\rm
I\\!R}^{m}$ and $\alpha_{j}\in{\rm I\\!R}$ for all $j\in J$, and where ${\rm
dom}\,g=\\{z\in{\rm I\\!R}^{m}|\,g(z)<\infty\\}$ is a polyhedral convex set
with the representation

${\rm dom}\,g=\big{\\{}z\in{\rm I\\!R}^{m}\,\big{|}\,\langle
b^{i},z\rangle\leq\beta_{i},i\in I:=\\{1,\ldots,s\\}\big{\\}}$ (2.3)

for some $s\in{\rm I\\!N}$, $b^{i}\in{\rm I\\!R}^{m}$ and $\beta_{i}\in{\rm
I\\!R}$ for all $i\in I$. It is not hard to see that ${\rm dom}\,g$ can be
expressed as the finite union of the polyhedral convex sets $C_{j},j\in J$,
defined by

$C_{j}=\big{\\{}z\in{\rm dom}\,g\,\big{|}\,g(z)=\langle
a^{j},z\rangle-\alpha_{j}\big{\\}}=\big{\\{}z\in{\rm dom}\,g\,\big{|}\,\langle
a^{i}-a^{j},z\rangle\leq\alpha_{i}-\alpha_{j},i\in J\big{\\}}.$

Pick $\bar{z}\in{\rm dom}\,g$ and define the sets of active indices at
$\bar{z}$ corresponding to the representation (2.3) and to the partition of
${\rm dom}\,g$ via the sets $C_{j}$ by

$I(\bar{z})=\big{\\{}i\in I\,\big{|}\,\langle
b^{i},\bar{z}\rangle=\beta_{i}\big{\\}}\quad\textrm{ and }\quad
J(\bar{z})=\big{\\{}j\in J\,\big{|}\,\bar{z}\in C_{j}\big{\\}}.$ (2.4)

Given a set-valued mapping $F:{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$
and $(\bar{x},\bar{y})\in{\rm gph}\,F$, the graphical derivative of $F$ at
$\bar{x}$ for $\bar{y}$, denoted by $DF(\bar{x},\bar{y})$, is a set-valued
mapping, defined by

${\rm gph}\,DF(\bar{x},\bar{y})=T_{{\rm
gph}\,F}(\bar{x},\bar{y})=\limsup_{t\searrow 0}\frac{{\rm
gph}\,F-(\bar{x},\bar{y})}{t}.$ (2.5)

The coderivative of $F$ at $\bar{x}$ for $\bar{y}$, denoted by
$D^{*}F(\bar{x},\bar{y})$, is defined via the relationship

$w\in D^{*}F(\bar{x},\bar{y})(u)\iff(w,-u)\in N_{{\rm
gph}\,F}(\bar{x},\bar{y}).$

It is known (cf. [6, Theorem 3.6(a)] and [6, equation (3.25)], respectively)
that for a polyhedral function $g$ and $(\bar{z},{\bar{\lambda}})\in{\rm
gph}\,\partial g$, we always have

$D(\partial
g)(\bar{z},{\bar{\lambda}})=N_{{K_{g}(\bar{z},{\bar{\lambda}})}}\quad\mbox{and}\quad
D^{*}(\partial
g)(\bar{z},{\bar{\lambda}})(0)={K_{g}(\bar{z},{\bar{\lambda}})}^{*}-{K_{g}(\bar{z},{\bar{\lambda}})}^{*}.$
(2.6)

Also, it follows from [6, Theorem 3.6(a)] and [6, Theorem 3.7(b)],
respectively, that

${\rm dom}\,D(\partial
g)(\bar{z},{\bar{\lambda}})=K_{g}(\bar{z},{\bar{\lambda}})\quad\mbox{and}\quad{\rm
dom}\,D^{*}(\partial
g)(\bar{z},{\bar{\lambda}})=K_{g}(\bar{z},{\bar{\lambda}})-K_{g}(\bar{z},{\bar{\lambda}}).$
(2.7)

Take the function $\varphi$ from (1.1) and define the Lagrange multiplier
mapping ${\Lambda}:{\rm I\\!R}^{n}\times{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{m}$ by

$\Lambda(x,v)=\big{\\{}\lambda\in{\rm
I\\!R}^{m}\;\big{|}\;\nabla\Phi(x)^{*}\lambda=v,\;\lambda\in\partial
g(\Phi(x))\big{\\}},\quad(x,v)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{n}.$ (2.8)

In the presence of an appropriate constraint qualification, we can ensure that
$\Lambda(x,v)\neq\emptyset$ when $(x,v)\in{\rm gph}\,\partial\varphi$. We are
not concerned, however, in this paper about what the weakest constraint
qualification is to achieve this goal. To proceed, pick
$\bar{v}\in\partial\varphi(\bar{x})$ and suppose that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. In what follows, we say that
the second-order qualification condition (SOQC) is satisfied at
$(\bar{x},{\bar{\lambda}})$ for the composite form (1.1) if the condition

$D^{*}(\partial g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)\cap{\rm
ker}\,\nabla\Phi(\bar{x})^{*}=\\{0\\}$ (2.9)

holds. This condition has been often used in second-order variational analysis
to obtain second-order chain rules for important classes of functions
including fully amenable functions; see [17, 18]. While $D^{*}(\partial
g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)$ was already calculated in
(2.6), a more useful representation of it can be found in [18, Theorem
3.1(i)-(ii)]. These results tell us that the latter can be equivalently
calculated as

$\displaystyle D^{*}(\partial
g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)$ $\displaystyle=$
$\displaystyle{\rm par}\,\\{\partial g(\Phi(\bar{x}))\\}$ (2.10)
$\displaystyle=$ $\displaystyle{\rm span}\,\big{\\{}a^{i}-a^{j}\,|\,i,j\in
J(\Phi(\bar{x}))\big{\\}}+{\rm span}\,\big{\\{}b^{i}\,|\,i\in
I(\Phi(\bar{x}))\big{\\}},$

where ${\rm par}\,\\{\partial g(\Phi(\bar{x}))\\}$ stands for the linear
subspace of ${\rm I\\!R}^{m}$ parallel to the affine hull of $\partial
g(\Phi(\bar{x}))$. This shows that the SOQC (2.9) is equivalent to the
transversality condition in the sense of [1, Definition 3.4]. Moreover, using
(2.10), one can see that the SOQC is equivalent to the nondegeneracy condition
for the composite form (1.1), defined in [12, Definition 5.3.1]. To elaborate
more on the SOQC (2.9), we consider two special cases of the polyhedral
function $g$ and then show that the latter condition, indeed, boils down to
the well-known conditions in optimization.

######  Example 2.1.

Suppose that $g$ and $\Phi$ are taken from (1.1) and
$\Phi=(\varphi_{1},\ldots,\varphi_{m})$ with $\varphi_{i}:{\rm
I\\!R}^{n}\to{\rm I\\!R}$ for all $i=1,\ldots,m$. We are going to discuss the
SOQC (2.9) for the following instances of the polyhedral function $g$:

  * (a)

Suppose that $g(z)=\max\\{z_{1},\ldots,z_{m}\\}$ with
$z=(z_{1},\ldots,z_{m})\in{\rm I\\!R}^{m}$, $\bar{z}=\Phi(\bar{x})$. This
selection of $g$ enables us to cover a minimax problem. In this case, we are
going to demonstrate that the SOQC (2.9) amounts to saying that the set
$\\{\nabla\varphi_{i}(\bar{x})\,|\,i\in J(\bar{z})\\}$ is affinely
independent. Recall that a set of vectors $w_{0},w_{1},\ldots,w_{m}$ is
affinely independent if the set $\\{w_{1}-w_{0},\ldots,w_{m}-w_{0}\\}$ is
linearly independent. To justify our claim about the SOQC (2.9) in this
setting, assume without loss of generality that $J(\bar{z})=\\{1,\ldots,m\\}$.
Thus, we deduce from (2.10) that

$D^{*}(\partial g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)={\rm
span}\,\big{\\{}e^{i}-e^{j}\,|\,i,j\in J(\bar{z})\big{\\}}={\rm
span}\,\big{\\{}e^{i}-e^{1}\,|\,i\in J(\bar{z})\big{\\}},$

where the vectors $e^{i}$, $i=1,\ldots,m$, are unit vectors in ${\rm
I\\!R}^{m}$ that have 1 as the $i^{th}$ component and zeros elsewhere. This
clearly tells us that the SOQC (2.9) amounts to the set
$\\{\nabla\varphi_{2}(\bar{x})-\nabla\varphi_{1}(\bar{x}),\ldots,\nabla\varphi_{m}(\bar{x})-\nabla\varphi_{1}(\bar{x})\\}$
being linearly independent and thus confirms our claim.

  * (b)

Suppose that $g=\delta_{C}$, where $C=\\{0\\}^{s}\times{\rm I\\!R}^{m-s}_{-}$
with $0\leq s\leq m$. This selection of $g$ allows us to cover both equality
and inequality constraints appearing in classical nonlinear programming
problems. In this case, it is not hard to see that the SOQC (2.9) reduces to
the classical linear independence constraint qualification (LICQ); see the
discussion after [20, Definition 6.1] for a proof of this fact.

We proceed with some direct consequences of the SOQC (2.9) for the composite
form (1.1), which play an important role for our developments in the next
section.

######  Proposition 2.2.

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) is satisfied
at $(\bar{x},{\bar{\lambda}})$, then the following properties hold.

  * (a)

The basic constraint qualification

$N_{{\rm dom}\,g}(\Phi(x))\cap{\rm ker}\,\nabla\Phi(x)^{*}=\\{0\\}$ (2.11)

hold for any $x$ close to $\bar{x}$.

  * (b)

There exist a constant $\ell\geq 0$ and a neighborhood $U$ of
$(\bar{x},\bar{v})$ such that for any $(x,v)\in U\cap{\rm
gph}\,\partial\varphi$, the Lagrange multiplier set ${\Lambda}(x,v)$ is a
singleton and the estimate

$\|\lambda-{\bar{\lambda}}\|\leq\ell\big{(}\|x-\bar{x}\|+\|v-\bar{v}\|\big{)}$
(2.12)

holds, where $\lambda$ is the unique Lagrange multiplier in ${\Lambda}(x,v)$.

[Proof. ]By (2.6), one can obtain from (2.9) that

$D(\partial g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)\cap{\rm
ker}\,\nabla\Phi(\bar{x})^{*}=\\{0\\}.$ (2.13)

Appealing now to [32, Proposition 3.10] illustrates that this property is
equivalent to the condition
${\Lambda}(\bar{x},\bar{v})=\\{{\bar{\lambda}}\\}$. It follows from [26,
Proposition 10.21] that ${\rm dom}\,{\rm d}g(\Phi(\bar{x}))=T_{{\rm
dom}\,g}(\Phi(\bar{x}))$, which allows us to conclude the inclusion
$K_{g}(\Phi(\bar{x}),{\bar{\lambda}})\subset T_{{\rm dom}\,g}(\Phi(\bar{x}))$.
This gives us the inclusion $N_{{\rm
dom}\,g}(\Phi(\bar{x}))\subset\big{(}K_{g}(\Phi(\bar{x}),{\bar{\lambda}})\big{)}^{*}$.
Combining this, (2.13), and (2.6) leads us to

$N_{{\rm dom}\,g}(\Phi(\bar{x}))\cap{\rm
ker}\,\nabla\Phi(\bar{x})^{*}=\\{0\\}.$

It is not hard to see that this condition justifies (a). Turning now to (b),
we deduce from (a) that there exists a $\delta>0$ such that for all
$(x,v)\in\big{(}{\rm
gph}\,\partial\varphi\big{)}\cap\mathbb{B}_{\delta}(\bar{x},\bar{v})$, the
Lagrange multiplier set ${\Lambda}(x,v)$ is nonempty and uniformly bounded.
Next, we claim that there exists a $\delta^{\prime}>0$ such that
$\delta^{\prime}<\delta$ and for all $(x,v)\in\big{(}{\rm
gph}\,\partial\varphi\big{)}\cap\mathbb{B}_{\delta^{\prime}}(\bar{x},\bar{v})$
and all $\lambda\in{\Lambda}(x,v)$, the condition

$D^{*}(\partial g)(\Phi(x),\lambda)(0)\cap{\rm
ker}\,\nabla\Phi(x)^{*}=\\{0\\}$

holds. Suppose to the contrary that for any $k\in{\rm I\\!N}$, there are a
pair $(x^{k},v^{k})\in{\rm gph}\,\partial\varphi$, converging to
$(\bar{x},\bar{v})$, and $\lambda^{k}\in{\Lambda}(x^{k},v^{k})$ for which we
can find $\eta^{k}\in{\rm I\\!R}^{m}\setminus\\{0\\}$ such that

$\eta^{k}\in D^{*}(\partial g)(\Phi(x^{k}),\lambda^{k})(0)\cap{\rm
ker}\,\nabla\Phi(x^{k})^{*}.$ (2.14)

According to the discussion above, the Lagrange multiplier sets
${\Lambda}(x^{k},v^{k})$ are uniformly bounded for sufficiently large $k$.
Passing to a subsequence, if necessary, we can assume that the sequence
$\\{\lambda^{k}{\\}_{k\in{\rm I\\!N}}}$ converges to a vector in
${\Lambda}(\bar{x},\bar{v})$. Since
${\Lambda}(\bar{x},\bar{v})=\\{{\bar{\lambda}}\\}$, we arrive at
$\lambda^{k}\to{\bar{\lambda}}$. Passing to a subsequence again if necessary,
we can assume that $\eta^{k}/\|\eta^{k}\|\to\eta$ with $\eta\in{\rm
I\\!R}^{m}\setminus\\{0\\}$. Combining these and using (2.14) bring us to

$\eta\in D^{*}(\partial g)(\Phi(\bar{x}),{\bar{\lambda}})(0)\cap{\rm
ker}\,\nabla\Phi(\bar{x})^{*},$

which contradicts (2.9) since $\eta\neq 0$ and thus proves our claim. Similar
to the argument presented above for (2.13), we get for any
$(x,v)\in\big{(}{\rm
gph}\,\partial\varphi\big{)}\cap\mathbb{B}_{\delta^{\prime}}(\bar{x},\bar{v})$
and any $\lambda\in{\Lambda}(x,v)$ that the condition

$D(\partial g)(\Phi(x),\lambda)(0)\cap{\rm ker}\,\nabla\Phi(x)^{*}=\\{0\\}$
(2.15)

is satisfied. This condition, coupled with [32, Proposition 3.10], tells us
that ${\Lambda}(x,v)$ is a singleton for any such a pair $(x,v)$. To justify
the estimate (2.12), suppose by contradiction that it fails. Thus, for any
$k\in{\rm I\\!N}$, we find $(x^{k},v^{k})\in{\rm gph}\,\partial\varphi$,
converging to $(\bar{x},\bar{v})$, and $\lambda^{k}\in{\Lambda}(x^{k},v^{k})$
such that

$\|\lambda^{k}-{\bar{\lambda}}\|>k(\|x^{k}-\bar{x}\|+\|v^{k}-\bar{v}\|).$

Setting $t_{k}:=\|\lambda^{k}-{\bar{\lambda}}\|$, we get
$\|x^{k}-\bar{x}\|=o(t_{k})$ and $\|v^{k}-\bar{v}\|=o(t_{k})$. Similar to the
argument utilized above, we can assume by passing to a subsequence if
necessary that $\lambda^{k}\to{\bar{\lambda}}$. By the definitions of
$\lambda^{k}$ and ${\bar{\lambda}}$, we obtain

$\nabla\Phi(\bar{x})^{*}(\frac{\lambda^{k}-{\bar{\lambda}}}{t_{k}})=\frac{1}{t_{k}}\big{(}(\nabla\Phi(\bar{x})-\nabla\Phi(x^{k}))^{*}\lambda^{k}+v^{k}-\bar{v}\big{)}=\frac{o(t_{k})}{t_{k}}.$

Assume without loss of generality that
$\|\lambda^{k}-{\bar{\lambda}}\|/t_{k}\to q$ for some $q\in{\rm
I\\!R}^{m}\setminus\\{0\\}$. This immediately implies that $q\in{\rm
ker}\,\nabla\Phi(\bar{x})^{*}$. On the other hand, since $\partial
g(\Phi(\bar{x}))$ is a polyhedral convex set, it follows from [26, Exercise
6.47] and (2.1) that

$\lambda^{k}-{\bar{\lambda}}\in T_{\partial
g(\Phi(\bar{x}))}({\bar{\lambda}})=(N_{\partial
g(\Phi(\bar{x}))}({\bar{\lambda}}))^{*}=K_{g}(\Phi(\bar{x}),{\bar{\lambda}})^{*}$

for all $k$ sufficiently large. By (2.6), we have $D(\partial
g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)=K_{g}(\Phi(\bar{x}),{\bar{\lambda}})^{*}$.
Thus, we get $q\in D(\partial
g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)$, a contradiction with
(2.13). This proves (b) and completes the proof.

We continue with another consequence of the SOQC (2.9), important for the
calculus of strict second subderivative in the next section. To this end,
recall that a set-valued mapping $F:{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{m}$ is called metrically regular at $\bar{x}$ for $\bar{y}\in
F(\bar{x})$ if there exist $\kappa\geq 0$ and neighborhoods $U$ of $\bar{x}$
and $V$ of $\bar{y}$ such that the distance estimate

${\rm dist}\big{(}x,F^{-1}(y)\big{)}\leq\kappa\,{\rm
dist}\big{(}y,F(x)\big{)}$ (2.16)

holds for all $(x,y)\in U\times V$. When the estimate in (2.16) holds for any
$(x,y)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}$, we call $F$ globally
metrically regular. Recall that $F$ is called positively homogeneous if $0\in
F(0)$ and $F(tx)=tF(x)$ for any $t>0$ and $x\in{\rm I\\!R}^{n}$. It is known
(cf. [9, Theorem 5.9(a)]) that when $F$ is positively homogeneous and
metrically regular at $0\in{\rm I\\!R}^{n}$ for $0\in{\rm I\\!R}^{m}$, it is
globally metrically regular.

Given a closed set $C\subset{\rm I\\!R}^{m}$, a continuously differentiable
function $h:{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$, and $\bar{x}\in{\rm
I\\!R}^{n}$ with $h(\bar{x})\in C$, it follows from [26, Example 9.44] that
the mapping $x\mapsto h(x)-C$ is metrically regular at $\bar{x}$ for $0$ if
and only if the condition

$N_{C}(h(\bar{x}))\cap{\rm ker}\,\nabla h(\bar{x})^{*}=\\{0\\}$

is satisfied. In this case, the infimum of the constants $\kappa$ for which
metric regularity of the mapping $x\mapsto h(x)-C$ holds at $\bar{x}$ for $0$
can be calculated by

$\max\big{\\{}\frac{1}{\|\nabla h(\bar{x})^{*}y\|}\big{|}\;y\in
N_{C}(h(\bar{x})),\,\|y\|=1\big{\\}}.$ (2.17)

######  Proposition 2.3.

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$, then there is a neighborhood $U$ of
$(\bar{x},\bar{v})$ such that for any $(x,v)\in({\rm
gph}\,\partial\varphi)\cap U$, the mapping
$w\mapsto\nabla\Phi(x)w-K_{g}(\Phi(x),\lambda)$ is globally metrically regular
with constant $2\bar{\gamma}$, where $\lambda$ is the unique Lagrange
multiplier in ${\Lambda}(x,v)$ and where

$\bar{\gamma}=\max\big{\\{}\frac{1}{\|\nabla\Phi(\bar{x})^{*}y\|}|\,\|y\|=1,y\in
D^{*}(\partial g)(\Phi(\bar{x}),{\bar{\lambda}})(0)\big{\\}}.$ (2.18)

[Proof. ]Using a similar argument as the proof of Proposition 2.2, we find
$\delta>0$ such that for any $(x,v)\in({\rm
gph}\,\partial\varphi)\cap\mathbb{B}_{\delta}(\bar{x},\bar{v})$ the condition
(2.15) holds. Shrinking $\delta$ if necessary, we conclude from Proposition
2.2(b) that ${\Lambda}(x,v)$ is a singleton for any $(x,v)\in({\rm
gph}\,\partial\varphi)\cap\mathbb{B}_{\delta}(\bar{x},\bar{v})$. Take any such
a pair $(x,v)$, let $\lambda$ be the unique Lagrange multiplier in
${\Lambda}(x,v)$ and define the mapping $G_{x,\lambda}:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ by
$G_{x,\lambda}(w)=\nabla\Phi(x)w-K_{g}(\Phi(x),\lambda)$ for any $w\in{\rm
I\\!R}^{n}$. It is not hard to check that $G_{x,\lambda}$ is positively
homogeneous. Moreover, it follows from (2.6) that $D(\partial
g)(\Phi(x),\lambda)(0)=N_{K_{g}(\Phi(x),\lambda)}(0)$. Appealing now to
(2.15), we arrive at

$N_{K_{g}(\Phi(x),\lambda)}(0)\cap{\rm ker}\,\nabla\Phi(x)^{*}=\\{0\\}.$
(2.19)

By the discussion prior to this proposition, the latter condition amounts to
metric regularity of the mapping $G_{x,\lambda}$ at $0\in{\rm I\\!R}^{n}$ for
$0\in{\rm I\\!R}^{m}$. As pointed out above, it follows from [26, Example
9.44] that the infimum of the constant $\kappa_{x,\lambda}$ for which metric
regularity of $G_{x,\lambda}$ holds at $0$ for $0$ can be calculated by

$\gamma_{x,\lambda}:=\max\big{\\{}\frac{1}{\|\nabla\Phi(x)^{*}y\|}|\,\|y\|=1,y\in
N_{K_{g}(\Phi(x),\lambda)}(0)\big{\\}}.$

We claim that there exists $r\in(0,\delta)$ such that for any $(x,v)\in({\rm
gph}\,\partial\varphi)\cap\mathbb{B}_{r}(\bar{x},\bar{v})$, we have
$\gamma_{x,\lambda}\leq 3\bar{\gamma}/2$ with $\bar{\gamma}$ taken from
(2.18). To justify the claim, suppose by contradiction that for any $k\in{\rm
I\\!N}$, there exist $(x^{k},v^{k})\in{\rm gph}\,\partial\varphi$ with
$(x^{k},v^{k})\to(\bar{x},\bar{v})$, and $y^{k}\in
N_{K_{g}(\Phi(x^{k}),\lambda^{k})}(0)$ with $\|y^{k}\|=1$ and
$\lambda^{k}\in\Lambda(x^{k},v^{k})$ that

$\frac{1}{\|\nabla\Phi(x^{k})^{*}y^{k}\|}>\frac{3\bar{\gamma}}{2}.$

Passing to a subsequence if necessary, we can assume that $y^{k}\to y$ for
some vector $y\in{\rm I\\!R}^{m}$ with $\|y\|=1$. Moreover, we have

$\displaystyle y^{k}\in N_{K_{g}(\Phi(x^{k}),\lambda^{k})}(0)$
$\displaystyle=$ $\displaystyle K_{g}(\Phi(x^{k}),\lambda^{k})^{*}$
$\displaystyle\subset$ $\displaystyle
K_{g}(\Phi(x^{k}),\lambda^{k})^{*}-K_{g}(\Phi(x^{k}),\lambda^{k})^{*}=D^{*}(\partial
g)(\Phi(x^{k}),\lambda^{k})(0),$

where the last equality results from (2.6). By Proposition 2.2(b), we obtain
$\lambda^{k}\to{\bar{\lambda}}$. Passing to the limit then brings us to

$\frac{1}{\|\nabla\Phi(\bar{x})^{*}y\|}\geq\frac{3\bar{\gamma}}{2},\;\;y\in
D^{*}(\partial g)(\Phi(\bar{x}),{\bar{\lambda}})(0),\;\;\|y\|=1,$

which is a contradiction with the definition of $\bar{\gamma}$. This proves
our claim and thus indicates that there exists $r\in(0,\delta)$ such that for
any $(x,v)\in({\rm gph}\,\partial\varphi)\cap\mathbb{B}_{r}(\bar{x},\bar{v})$,
the infimum of the constants $\kappa_{x,\lambda}$ of metric regularity of
$G_{x,\lambda}$ at $0$ for $0$ is strictly less than $2\bar{\gamma}$. This
tells us that $2\bar{\gamma}$ can be chosen as a common constant of metric
regularity of $G_{x,\lambda}$ at $0$ for $0$ for any $(x,v)\in({\rm
gph}\,\partial\varphi)\cap\mathbb{B}_{r}(\bar{x},\bar{v})$. Since
$G_{x,\lambda}$ are positively homogenous, it results from [9, Theorem 5.9(a)]
that $G_{x,\lambda}$ are globally metrically regular with the same constant
$2\bar{\gamma}$, which completes the proof.

######  Proposition 2.4.

Assume that $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a polyhedral
function and $\bar{z}\in{\rm dom}\,g$ and that $s={\rm dim}\,({\rm
par}\,\\{\partial g(\bar{z})\\})$. Then there exist a neighborhood $U$ of
$\bar{z}$, an $s\times m$ matrix $B$, and a polyhedral function
$\vartheta:{\rm I\\!R}^{s}\to\overline{{\rm I\\!R}}$ for which we have
$g(z)=\vartheta(Bz)$ for any $z\in U$ and ${\rm ker}\,B=({\rm
par}\,\\{\partial g(\bar{z})\\})^{\perp}$. Consequently, $B$ has full rank.

[Proof. ]The first claim was established in [18, Lemma 3.1]. The second claim
was justified in the proof of [18, Theorem 3.2]. Finally, the last claim is a
direct consequence of the classical rank-nullity theorem from linear algebra.

The above result has an important implication for the compsite form (1.1) in
the presence of the SOQC (2.9), allowing us to equivalently express $\varphi$
in the form of (1.1) with the SOQC replaced by a stronger condition.

######  Corollary 2.5.

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$ and the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$. Then there exists a neighborhood $O$ of $\bar{x}$
on which $\varphi$ can be expressed as

$\varphi(x)=(\vartheta\circ\Psi)(x)\quad\mbox{for all}\;\;x\in O,$ (2.20)

where $\vartheta:{\rm I\\!R}^{s}\to\overline{{\rm I\\!R}}$ is a polyhedral
function with $s={\rm dim}\,({\rm par}\,\\{\partial g(\Phi(\bar{x}))\\})$ and
where $\Psi:{\rm I\\!R}^{n}\to{\rm I\\!R}^{s}$, defined by $\Psi=B\circ\Phi$
with $B$ and $\Phi$ taken from Proposition 2.4 and (1.1), respectively.
Moreover, $\nabla\Psi(\bar{x})$ has full rank.

[Proof. ]Shrinking the neighborhood $O$ in (1.1), together with Proposition
2.4, gives us the representation (2.20). The claim about $\nabla\Psi(\bar{x})$
was established in [18, Proposition 4.1].

A function $f\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is called prox-
regular at $\bar{x}$ for $\bar{v}$ if $f$ is finite at $\bar{x}$ and locally
lower semicontinuous (lsc) around $\bar{x}$ with $\bar{v}\in\partial
f(\bar{x})$, and there exist constants $\varepsilon>0$ and $\rho>0$ such that
for all $x\in\mathbb{B}_{\varepsilon}(\bar{x})$ with $f(x)\leq
f(\bar{x})+\varepsilon$ we have

$f(x)\geq f(u)+\langle\bar{v},x-u\rangle-\frac{\rho}{2}\|x-u\|^{2}\;\mbox{
whenever }\;(u,v)\in({\rm gph}\,\partial
f)\cap\mathbb{B}_{\varepsilon}(\bar{x},\bar{v}).$ (2.21)

The function $f$ is called subdifferentially continuous at $\bar{x}$ for
$\bar{v}$ if the convergence $(x^{k},v^{k})\to(\bar{x},\bar{v})$ with
$v^{k}\in\partial f(x^{k})$ yields $f(x^{k})\to f(\bar{x})$ as $k\to\infty$.

######  Proposition 2.6.

Assume that $\varphi$ has the representation (1.1) around $\bar{x}\in{\rm
I\\!R}^{n}$ and $\bar{v}\in\partial\varphi(\bar{x})$, and that the basic
constraint qualification (2.11) holds at $x=\bar{x}$. Then the following
properties hold.

  * (a)

$\varphi$ is prox-regular and subdifferentially continuous at $\bar{x}$ for
$\bar{v}$.

  * (b)

The critical cone $K_{\varphi}(\bar{x},\bar{v})$ can be represented by

$K_{\varphi}(\bar{x},\bar{v})=\big{\\{}w\in{\rm
I\\!R}^{n}|\;\nabla\Phi(\bar{x})w\in
K_{g}(\Phi(\bar{x}),{\bar{\lambda}})\big{\\}}=N_{\partial\varphi(\bar{x})}(\bar{v}),$
(2.22)

where ${\bar{\lambda}}$ can be any vector in ${\Lambda}(\bar{x},\bar{v})$.
Moreover, for any $w\in K_{\varphi}(\bar{x},\bar{v})$, we always have

$N_{K_{\varphi}(\bar{x},\bar{v})}(w)=\nabla\Phi(\bar{x})^{*}N_{K_{g}(\Phi(\bar{x}),{\bar{\lambda}})}(\nabla\Phi(\bar{x})w).$

  * (c)

We have $\partial\varphi(\bar{x})={\widehat{\partial}}\varphi(\bar{x})$.
Consequently, $N_{\partial\varphi(\bar{x})}(\bar{v})$ is a linear subspace if
and only if $\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$.

  * (d)

$\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$ if and only if
${\bar{\lambda}}\in{\rm ri}\,\partial g(\Phi(\bar{x}))$ for any
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$.

[Proof. ]Part (a) results from [26, Proposition 13.32]. The first equivalent
representation of $K_{\varphi}(\bar{x},\bar{v})$ in (b) follows from the chain
rule for the subderivative in [26, Theorem 13.14], which holds under the basic
constraint qualification (2.11). The second one was taken from [26, Theorem
13.14]. The claimed chain rule for normal cones in (b) is an immediate
consequence of the fact that both critical cones
$K_{\varphi}(\bar{x},\bar{v})$ and $K_{g}(\Phi(\bar{x}),{\bar{\lambda}})$ are
polyhedral. The first claim in (c) can be found in [26, Exercise 10.25(a)].
The second claim results from the fact that $\partial\varphi(\bar{x})$ is
convex. To justify (d), observe that (2.11) ensures that
${\Lambda}(\bar{x},\bar{v})\neq\emptyset$. Thus, for any
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$, we have
$\bar{v}=\nabla\Phi(\bar{x})^{*}{\bar{\lambda}}$. The claimed equivalence then
results from [26, Proposition 2.44(a)].

##  3 Chain Rule for Strict Twice Epi-Differentiability

This section is devoted to study an important second-order variational
property, called strict twice epi-differentiability, for the composite
function $\varphi$ in (1.1). To this end, consider a function $f:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and $\bar{x}\in{\rm I\\!R}^{n}$ with
$f(\bar{x})$ finite and define the parametric family of second-order
difference quotients of $f$ at $\bar{x}$ for $\bar{v}\in\partial f(\bar{x})$
by

$\Delta_{t}^{2}f(\bar{x},\bar{v})(w)=\frac{f(\bar{x}+tw)-f(\bar{x})-t\langle\bar{v},\,w\rangle}{\frac{1}{2}t^{2}}$

for any $w\in{\rm I\\!R}^{n}$ and $t>0$. The second subderivative of $f$ at
$\bar{x}$ for $\bar{v}$, denoted ${\rm d}^{2}f(\bar{x},\bar{v})$, is an
extended-real-valued function defined by

${\rm d}^{2}f(\bar{x},\bar{v})(w)=\liminf_{\begin{subarray}{c}t\searrow 0\\\
w^{\prime}\to
w\end{subarray}}\Delta_{t}^{2}f(\bar{x},\bar{v})(w^{\prime}),\;\;w\in{\rm
I\\!R}^{n}.$

Following [26, Definition 13.6], $f$ is said to be twice epi-differentiable at
$\bar{x}$ for $\bar{v}$ if the functions $\Delta_{t}^{2}f(\bar{x},\bar{v})$
epi-converge to ${\rm d}^{2}f(\bar{x},\bar{v})$ as $t\searrow 0$. Further, we
say that $f$ is strictly twice epi-differentiable at $\bar{x}$ for $\bar{v}$
if the functions $\Delta_{t}^{2}f(x,v)$ epi-converge to a function as
$t\searrow 0$, $(x,v)\to(\bar{x},\bar{v})$ with $f(x)\to f(\bar{x})$ and
$(x,v)\in{\rm gph}\,\partial f$. If this condition holds, the limit function
is then the second subderivative ${\rm d}^{2}f(\bar{x},\bar{v})$. The
following result, established recently in [6, Theorem 4.3], achieved a simple
characterization of strict twice epi-differentiability of polyhedral
functions.

######  Proposition 3.1 (strict twice epi-differentiability of polyhedral
functions).

Assume that $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a polyhedral
function and that $(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$. Then
the following properties are equivalent:

  * (a)

there is a neighborhood $U$ of $(\bar{z},{\bar{\lambda}})$ such that for any
$(z,\lambda)\in U\cap{\rm gph}\,\partial g$, $g$ is strictly twice epi-
differentiable at $z$ for $\lambda$;

  * (b)

${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$.

It is insightful to add that the main driving force of the characterization
above was the following result for polyhedral functions, observed in [6,
Theorem 3.3(b)], which holds under the relative interior condition
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$: There exists a neighborhood
$V$ of $(\bar{z},{\bar{\lambda}})$ for which we have

$K_{g}(z,\lambda)=K_{g}(\bar{z},{\bar{\lambda}})\quad\mbox{for
all}\;\;(z,\lambda)\in V\cap{\rm gph}\,\partial g.$ (3.1)

The above result motivates us to pursue the possibility of obtaining a similar
characterization of strict twice epi-differentiability for the composite form
(1.1). To this end, we define the strict second subderivative of $f$ at
$\bar{x}$ for $\bar{v}$ with $\bar{v}\in\partial f(\bar{x})$ at $w\in{\rm
I\\!R}^{n}$ by

${\rm d}_{s}^{2}f(\bar{x},\bar{v})(w)=\liminf_{\begin{subarray}{c}t\searrow
0,\,w^{\prime}\to w\\\ (x,v)\xrightarrow{{\rm gph}\,\partial
f}(\bar{x},\bar{v})\\\ f(x)\to
f(\bar{x})\end{subarray}}\Delta_{t}^{2}f(x,v)(w^{\prime}).$

When $f$ is subdifferentially continuous at $\bar{x}$ for $\bar{v}$, we can
drop the requirement $f(x)\to f(\bar{x})$ in the definition above. Two
immediate observations can be made about the strict second subderivative. The
first one is that it is positively homogeneous of degree $2$ (see [26,
Definition 13.4] for its definition). The second one is that it is always
lower semicontinuous (lsc). Both claims can be proven as of those for the
second subderivative established in [26, Proposition 13.5].

######  Lemma 3.2.

Assume that $f:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and
$(\bar{x},\bar{v})\in{\rm gph}\,\partial f$. Then we have

${\rm d}_{s}^{2}f(\bar{x},\bar{v})(w)\leq\liminf_{\begin{subarray}{c}t\searrow
0,\,w^{\prime}\to w\\\ (x,v)\xrightarrow{{\rm gph}\,\partial
f}(\bar{x},\bar{v})\\\ f(x)\to f(\bar{x})\end{subarray}}{\rm
d}^{2}f(x,v)(w^{\prime}).$

[Proof. ]Denote by $\alpha$ the value of the limit on the right-hand side of
the above inequality. Thus, we can find sequences
$(x^{k},v^{k})\to(\bar{x},\bar{v})$ with $(x^{k},v^{k})\in{\rm gph}\,\partial
f$, $f(x^{k})\to f(\bar{x})$, and $w^{k}\to w$ for which we have ${\rm
d}^{2}f(x^{k},v^{k})(w^{k})\to\alpha$. By the definition of the second
subderivative, for each $k$, we find sequences $w^{k}_{m}\to w^{k}$ and
$t^{m}_{k}\searrow 0$ as $m\to\infty$ such that
$\Delta^{2}_{t_{k}^{m}}f(x^{k},v^{k})(w^{k}_{m})\to{\rm
d}^{2}f(x^{k},v^{k})(w^{k})$ as $m\to\infty$. Using a standard diagonalization
technique, we can find sequences $m_{k}\to\infty$, $w^{k}_{m_{k}}\to w$ and
$t_{k}^{m_{k}}\searrow 0$ as $k\to\infty$ such that
$\Delta^{2}_{t_{k}^{m_{k}}}f(x^{k},v^{k})(w^{k}_{m_{k}})\to\alpha$ as
$k\to\infty$. It is evident from the definition of the strict second
subderivative that $\alpha\geq{\rm d}_{s}^{2}f(\bar{x},\bar{v})(w)$, which
proves our claimed inequality.  We show below that the strict second
subderivative can be utilized to obtain a characterization of the so-called
uniform quadratic growth condition; see [2, Definition 5.16]. The latter
condition is known to be equivalent to the variational strong convexity,
defined by Rockafellar in [30, Definition 2], for lsc functions; see Corollary
3.6 for the definition of this property.

######  Proposition 3.3.

Assume that $f:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is an lsc function
and $(\bar{x},\bar{v})\in{\rm gph}\,\partial f$. Then the following properties
are equivalent:

  * (a)

${\rm d}^{2}_{s}f(\bar{x},\bar{v})(w)>0$ for all $w\in{\rm
I\\!R}^{n}\setminus\\{0\\}$;

  * (b)

there exist convex neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{v}$ and
constants $\kappa>0$ and $\varepsilon>0$ such that

$f(x^{\prime})\geq f(x)+\langle
v,x^{\prime}-x\rangle+\frac{\kappa}{2}\|x-x^{\prime}\|^{2}\quad\mbox{for
all}\;\;(x,v)\in({\rm gph}\,\partial f)\cap(U_{\varepsilon}\times
V),\;x^{\prime}\in U,$

where $U_{\varepsilon}=\\{x\in U|\;f(x)<f(\bar{x})+\varepsilon\\}$.

[Proof. ]If (b) holds, it is easy to see that
$\Delta_{t}^{2}f(x,v)(w^{\prime})\geq{\kappa}\|w^{\prime}\|^{2}$ whenever
$(x,v)\in{\rm gph}\,\partial f$ satisfying $(x,v)\to(\bar{x},\bar{v})$ with
and $f(x)\to f(\bar{x})$ and $w^{\prime}\to w$ and $t\searrow 0$. Passing to
the limit proves (a). To prove the opposite implication, we can argue by
contradiction that if (b) fails, then for any $k\in{\rm I\\!N}$, we find
$(x^{k},v^{k})\in{\rm gph}\,\partial f$ such that
$(x^{k},v^{k})\to(\bar{x},\bar{v})$ and $f(x^{k})<f(\bar{x})+1/k$ and
$y^{k}\in{\rm I\\!R}^{n}$ such that $y^{k}\to\bar{x}$ for which we have

$f(y^{k})<f(x^{k})+\langle
v^{k},y^{k}-x^{k}\rangle+\frac{1}{2k}\|x^{k}-y^{k}\|^{2}.$

Since $f$ is lsc, we also get $f(x^{k})\to f(\bar{x})$. Setting
$t_{k}=\|x^{k}-y^{k}\|$ and $w^{k}=(y^{k}-x^{k})/t_{k}$, assume by passing to
a subsequence if necessary that $w^{k}\to w$ for some $w\in{\rm
I\\!R}^{n}\setminus\\{0\\}$. Combining these shows that
$\Delta_{t_{k}}^{2}f(x^{k},v^{k})(w^{k})<1/k$ for any $k$. Passing to the
limit and taking into account that $w\neq 0$ lead us to a contradiction with
(a) and hence complete the proof.

Note that $U_{\varepsilon}$ in Proposition 3.3(b) can be replaced with $U$
provided that $f$ is subdifferentially continuous at $\bar{x}$ for $\bar{v}$.
It is also important to mention that the property in Proposition 3.3(a) can be
expressed equivalently as the existence of a constant $\ell>0$ for which ${\rm
d}^{2}_{s}f(\bar{x},\bar{v})(w)\geq\ell\|w\|^{2}$ for any $w\in{\rm
I\\!R}^{n}$. Looking into the proof of Proposition 3.3, one can conclude that
if (b) holds with constant $\kappa>0$, then we have ${\rm
d}^{2}_{s}f(\bar{x},\bar{v})(w)\geq\kappa\|w\|^{2}$ for any $w\in{\rm
I\\!R}^{n}$. Conversely, if ${\rm
d}^{2}_{s}f(\bar{x},\bar{v})(w)\geq\ell\|w\|^{2}$ holds, we can see that (b)
is satisfied for any constant $\kappa\in(0,\ell)$.

Our first goal in this section is to establish a chain rule for the strict
second subderivative of the function $\varphi$ in (1.1). This will tell us
when strict twice epi-differentiability should be expected for such a
composite function. We begin with the following result in which a chain rule
for the second subderivative was obtained for the composite form in (1.1)
under the SOQC (2.9).

######  Proposition 3.4.

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$, then there exists a neighborhood $U$ of
$(\bar{x},\bar{v})$ such that for any $(x,v)\in U\cap{\rm
gph}\,\partial\varphi$, we have

${\rm d}^{2}\varphi(x,v)(w)=\langle\lambda,\nabla^{2}\Phi(x)(w,w)\rangle+{\rm
d}^{2}g(\Phi(x),\lambda)(\nabla\Phi(x)w),$

where $\lambda$ is the unique element of the Lagrange multiplier set
${\Lambda}(x,v)$ and where ${\rm
d}^{2}g(\Phi(x),\lambda)=\delta_{K_{g}(\Phi(x),\lambda)}$.

[Proof. ]By Proposition 2.2, we find a $\delta>0$ such that for all
$(x,v)\in\big{(}{\rm
gph}\,\partial\varphi\big{)}\cap\mathbb{B}_{\delta}(\bar{x},\bar{v})$ the
Lagrange multiplier set ${\Lambda}(x,v)$ is a singleton and that for all
$x\in\mathbb{B}_{\delta}(\bar{x})$ the basic constraint qualification in
(2.11) holds. Combining these and [26, Theorem 13.14] immediately gives us the
claimed formula for the second subderivative of $\varphi$ for any
$(x,v)\in\big{(}{\rm
gph}\,\partial\varphi\big{)}\cap\mathbb{B}_{\delta}(\bar{x},\bar{v})$. The
formula for the second subderivative of $g$ was taken from [26, Proposition
13.9].

######  Theorem 3.5 (chain rule for strict second subderivative).

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$, then we have

${\rm
d}_{s}^{2}\varphi(\bar{x},\bar{v})(w)=\langle{\bar{\lambda}},\nabla^{2}\Phi(\bar{x})(w,w)\rangle+{\rm
d}^{2}_{s}g(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w)$

with ${\rm
d}^{2}_{s}g(\Phi(\bar{x}),{\bar{\lambda}})(u)=\delta_{K_{g}(\Phi(\bar{x}),{\bar{\lambda}})-K_{g}(\Phi(\bar{x}),{\bar{\lambda}})}(u)$
for all $u\in{\rm I\\!R}^{m}$.

[Proof. ]The given formula for the strict second subderivative of the
polyhedral function $g$ was recently obtained in [6, Proposition 4.1]. To
justify the claimed formula for the strict second subderivative of $\varphi$,
take the neighborhood $O$ from Corollary 2.5 on which $\varphi$ can be
represented as $\varphi=\vartheta\circ\Psi$ with $\nabla\Psi(\bar{x})$ having
full rank. Similar to (2.8), define the set of Lagrange multipliers at
$(x,v)\in{\rm gph}\,\partial\varphi$ associated with the latter representation
of $\varphi$ by

$\Gamma(x,v)=\big{\\{}\mu\in{\rm
I\\!R}^{s}|\;\nabla\Psi(x)^{*}\mu=v,\;\mu\in\partial\vartheta(\Psi(x))\big{\\}},$

where $s$ is taken from Corollary 2.5. When $(x,v)\in{\rm
gph}\,\partial\varphi$ is sufficiently close to $(\bar{x},\bar{v})$, it
follows from Proposition 2.2(b) that $\Gamma(x,v)$ is a singleton and that
$\|\mu-\bar{\mu}\|=O(\|x-\bar{x}\|+\|v-\bar{v}\|)$ with $\mu\in\Gamma(x,v)$
and $\bar{\mu}\in\Gamma(\bar{x},\bar{v})$. Pick $w\in{\rm I\\!R}^{n}$ and then
take sequences $(x^{k},v^{k})\to(\bar{x},\bar{v})$ with $(x^{k},v^{k})\in{\rm
gph}\,\partial\varphi$ and $w^{k}\to w$ and let
$\mu^{k}\in\Gamma(x^{k},v^{k})$. Set

$u^{k}:=\nabla\Psi(x^{k})w^{k}+{t_{k}}\nabla^{2}\Psi(x^{k})(w^{k},w^{k})/2+{o(t_{k}^{2})}/{t_{k}}$

and observe that

$\displaystyle\Delta^{2}_{t_{k}}\varphi(x^{k},v^{k})(w^{k})$ $\displaystyle=$
$\displaystyle\dfrac{\vartheta\big{(}\Psi(x^{k}+t_{k}w^{k})\big{)}-\vartheta\big{(}\Psi(x^{k})\big{)}-t_{k}\langle\nabla\Psi(x^{k})^{*}\mu^{k},w^{k}\rangle}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle=$
$\displaystyle\dfrac{\vartheta\big{(}\Psi(x^{k})+t_{k}u^{k}\big{)}-\vartheta\big{(}\Psi(x^{k})\big{)}-t_{k}\langle\mu^{k},u^{k}\rangle}{\frac{1}{2}t_{k}^{2}}+\dfrac{t_{k}\langle\mu^{k},u^{k}\rangle-
t_{k}\langle\mu^{k},\nabla\Psi(x^{k})w^{k}\rangle}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle=$
$\displaystyle\Delta^{2}_{t_{k}}\vartheta(\Psi(x^{k}),\mu^{k})(u^{k})+\langle\mu^{k},\nabla^{2}\Psi(x^{k})(w^{k},w^{k})\rangle+\dfrac{o(t^{2}_{k})}{t_{k}^{2}}.$

Passing to the limit and taking into account that $\mu^{k}\to\mu$ due to the
discussion above bring us to

$\displaystyle{\rm d}_{s}^{2}\varphi(\bar{x},\bar{v})(w)$ $\displaystyle\geq$
$\displaystyle\langle\bar{\mu},\nabla^{2}\Psi(\bar{x})(w,w)\rangle+{\rm
d}_{s}^{2}\vartheta(\Psi(\bar{x}),\bar{\mu})(\nabla\Psi(\bar{x})w)$
$\displaystyle=$
$\displaystyle\langle\bar{\mu},\nabla^{2}\Psi(\bar{x})(w,w)\rangle+\delta_{K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})-K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})}(\nabla\Psi(\bar{x})w),$

where the last equality stems from the fact that $\vartheta$ is a polyhedral
function. Clearly, we get equality if $\nabla\Psi(\bar{x})w\notin
K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})-K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})$.
We proceed to justify that the opposite inequality in (3) for any $w\in{\rm
I\\!R}^{n}$ such that $\nabla\Psi(\bar{x})w\in
K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})-K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})$.
To this end, it follows from [6, Proposition 3.4] that there exists a sequence
$\\{(y^{k},\mu^{k}){\\}_{k\in{\rm I\\!N}}}\subset{\rm gph}\,\partial\vartheta$
such that $(y^{k},\mu^{k})\to(\Psi(\bar{x}),\bar{\mu})$ and that
$K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})-K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})=K_{\vartheta}(y^{k},\mu^{k})$
for any $k$. Since $\nabla\Psi(\bar{x})$ has full rank, we conclude from the
classical Lyusternik-Graves Theorem (cf. [16, Corollary 3.8]) that $\Psi$ is
metrically regular at $\bar{x}$ for $\Psi(\bar{x})$. This implies that there
exists a constant $\ell\geq 0$ such that the estimate

${\rm dist}(\bar{x},\Psi^{-1}(y^{k}))\leq\ell\,\|\Psi(\bar{x})-y^{k}\|$

holds for all $k$ sufficiently large. Thus, we find $x^{k}\in{\rm I\\!R}^{n}$
such that $\Psi(x^{k})=y^{k}$ and $x^{k}\to\bar{x}$. The former yields
$K_{\vartheta}(y^{k},\mu^{k})=K_{\vartheta}(\Psi(x^{k}),\mu^{k})$. We can also
use Proposition 2.3 to conclude that the mappings
$G_{k}(u):=\nabla\Psi(x^{k})u-K_{\vartheta}(\Psi(x^{k}),\mu^{k})$ are globally
metrically regular with a uniform constant $\kappa>0$. This brings us to the
estimate

$\displaystyle{\rm dist}(w,G^{-1}_{k}(0))$ $\displaystyle\leq$
$\displaystyle\kappa\,{\rm dist}(0,G_{k}(w))=\kappa\,{\rm
dist}\big{(}\nabla\Psi(x^{k})w,K_{\vartheta}(\Psi(x^{k}),\mu^{k})\big{)}$
$\displaystyle\leq$
$\displaystyle\kappa\,\|\nabla\Psi(x^{k})w-\nabla\Psi(\bar{x})w\|\leq\kappa\,\|\nabla\Psi(x^{k})-\nabla\Psi(\bar{x})\|\|w\|,$

where the penultimate step results from the fact that $\nabla\Psi(\bar{x})w\in
K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})-K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})=K_{\vartheta}(\Psi(x^{k}),\mu^{k})$.
This allows us to find $w^{k}\in G^{-1}_{k}(0)$ such that $w^{k}\to w$. So, we
have $\nabla\Psi(x^{k})w^{k}\in K_{\vartheta}(\Psi(x^{k}),\mu^{k})$ for all
$k$ sufficiently large. Using Lemma 3.2 and the given formula for the second
subderivative of $\varphi$ at $x^{k}$ for $v^{k}$ in Proposition 3.4, we
arrive at

$\displaystyle{\rm d}_{s}^{2}\varphi(\bar{x},\bar{v})(w)$ $\displaystyle\leq$
$\displaystyle\liminf_{k\to\infty}{\rm d}^{2}\varphi(x^{k},v^{k})(w^{k})$
$\displaystyle=$
$\displaystyle\liminf_{k\to\infty}\langle\mu^{k},\nabla^{2}\Psi(x^{k})(w^{k},w^{k})\rangle+{\rm
d}^{2}\vartheta(\Psi(x^{k}),\mu^{k})(\nabla\Psi(x^{k})w^{k})$ $\displaystyle=$
$\displaystyle\liminf_{k\to\infty}\langle\mu^{k},\nabla^{2}\Psi(x^{k})(w^{k},w^{k})\rangle+\delta_{K_{\vartheta}(\Psi(x^{k}),\mu^{k})}(\nabla\Psi(x^{k})w^{k})$
$\displaystyle=$
$\displaystyle\liminf_{k\to\infty}\langle\mu^{k},\nabla^{2}\Psi(x^{k})(w^{k},w^{k})\rangle=\langle\bar{\mu},\nabla^{2}\Psi(\bar{x})(w,w)\rangle$
$\displaystyle=$
$\displaystyle\langle\bar{\mu},\nabla^{2}\Psi(\bar{x})(w,w)\rangle+{\rm
d}_{s}^{2}\vartheta(\Psi(\bar{x}),\bar{\mu})(\nabla\Psi(\bar{x})w),$

where the last equality results from $\nabla\Psi(\bar{x})w\in
K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})-K_{\vartheta}(\Psi(\bar{x}),\bar{\mu})$.
Combining this estimate and (3) gives us

${\rm
d}_{s}^{2}\varphi(\bar{x},\bar{v})(w)=\langle\bar{\mu},\nabla^{2}\Psi(\bar{x})(w,w)\rangle+{\rm
d}_{s}^{2}\vartheta(\Psi(\bar{x}),\bar{\mu})(\nabla\Psi(\bar{x})w).$ (3.3)

To achieve the same result for the representation (1.1), we first observe from
$\nabla\Psi(\bar{x})=B\nabla\Phi(\bar{x})$ that
${\bar{\lambda}}:=B^{*}\bar{\mu}\in{\Lambda}(\bar{x},\bar{v})$. Also, we have
$\nabla^{2}\Psi(\bar{x})=B\nabla^{2}\Phi(\bar{x})$. By Proposition 2.4, we
know that $g$ can be represented locally around $\Phi(\bar{x})$ as
$g=\vartheta\circ B$ with $\vartheta$ being a polyhedral function and $B$
having full rank. Applying (3.3) to the latter representation of $g$ gives us

${\rm d}_{s}^{2}g(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w)={\rm
d}_{s}^{2}\vartheta(\Psi(\bar{x}),\bar{\mu})(\nabla\Psi(\bar{x})w).$

This, together with (3.3), implies that

$\displaystyle{\rm d}_{s}^{2}\varphi(\bar{x},\bar{v})(w)$ $\displaystyle=$
$\displaystyle\langle\bar{\mu},\nabla^{2}\Psi(\bar{x})(w,w)\rangle+{\rm
d}_{s}^{2}\vartheta(\Psi(\bar{x}),\bar{\mu})(\nabla\Psi(\bar{x})w)$
$\displaystyle=$
$\displaystyle\langle\bar{\mu},B\nabla^{2}\Phi(\bar{x})(w,w)\rangle+{\rm
d}_{s}^{2}g(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w)$
$\displaystyle=$
$\displaystyle\langle{\bar{\lambda}},\nabla^{2}\Phi(\bar{x})(w,w)\rangle+{\rm
d}_{s}^{2}g(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w),$

which proves the claimed formula for the strict second subderivative of
$\varphi$ and hence completes the proof.

As an immediate consequence of the established chain rule for the strict
second subderivative, we can achieve a useful characterization of a property
called the variational strong convexity.

######  Corollary 3.6.

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$, then the following properties are equivalent:

  * (a)

$\langle{\bar{\lambda}},\nabla^{2}\Phi(\bar{x})(w,w)\rangle>0$ for all
$w\in{\rm I\\!R}^{n}\setminus\\{0\\}$ with $\nabla\Phi(\bar{x})w\in
K_{g}(\Phi(\bar{x}),{\bar{\lambda}})-K_{g}(\Phi(\bar{x}),{\bar{\lambda}})$;

  * (b)

$\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$, meaning
that there exist convex neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{v}$
and an lsc convex function $h$ such that $({\rm
gph}\,\partial\varphi)\cap(U\times V)=({\rm gph}\,\partial h)\cap(U\times V)$
and that $h(x)\leq\varphi(x)$ for any $x\in U$ but $\varphi(x)=h(x)$ for any
$(x,v)\in({\rm gph}\,\partial\varphi)\cap(U\times V)$.

[Proof. ]According to [30, Theorem 2], if
$\bar{v}\in{\widehat{\partial}}\varphi(\bar{x})$, the variational strong
convexity of $\varphi$ at $\bar{x}$ for $\bar{v}$ is equivalent to the uniform
quadratic growth condition in Proposition 3.3(b) with $f=\varphi$. The latter
amounts to ${\rm d}_{s}^{2}\varphi(\bar{x},\bar{v})(w)>0$ for all $w\in{\rm
I\\!R}^{n}\setminus\\{0\\}$ due to Proposition 3.3. Using the established
chain rule in Theorem 3.5 and taking into account that
${\widehat{\partial}}\varphi(\bar{x})=\partial\varphi(\bar{x})$ because of the
SOQC confirm that (a) and (b) are equivalent.

######  Remark 3.7.

One can use Corollary 3.6 to find a characterization of tilt-stable local
minimizers of the composite optimization problem

$\operatorname*{minimize\;}\varphi(x)\quad\textrm{subject to}\;\;x\in{\rm
I\\!R}^{n}.$ (3.4)

To elaborate more, consider a function $\varphi$ with the representation (1.1)
around $\bar{x}$. Recall that $\bar{x}$ is called a tilt-stable local
minimizer of $\varphi$ if there exist neighborhoods $U$ of $\bar{x}$ and $V$
of $\bar{v}=0$ such that the mapping

$v\mapsto\operatorname*{argmin}_{x\in U}\\{\varphi(x)-\langle
v,x-\bar{x}\rangle\\}$

is single-valued and Lipschitz continuous on $V$ and its value at $\bar{v}$ is
$\\{\bar{x}\\}$. Combining [30, Theorem 2] and [22, Theorem 1.3] tells us that
$\bar{x}$ is a tilt-stable local minimizer of $\varphi$ if and only if
$\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$. If the
SOQC (2.9) holds at $(\bar{x},{\bar{\lambda}})$, where ${\bar{\lambda}}$ is
the unique element in ${\Lambda}(\bar{x},\bar{v})$, we conclude from Corollary
3.6 that $\bar{x}$ is a tilt-stable local minimizer of $\varphi$ if and only
if we have

$\langle{\bar{\lambda}},\nabla^{2}\Phi(\bar{x})(w,w)\rangle>0\quad\mbox{ for
all}\;\;w\in{\rm
I\\!R}^{n}\setminus\\{0\\}\;\;\mbox{with}\;\nabla\Phi(\bar{x})w\in
K_{g}(\Phi(\bar{x}),{\bar{\lambda}})-K_{g}(\Phi(\bar{x}),{\bar{\lambda}}),$

a condition which was traditionally called the strong second-order sufficient
condition. This characterization of tilt-stable local minimizers of (3.4) was
perviously observed in [18] using a different approach, relying mainly on the
concept of coderivative.

Next, we recall a characterization of strict twice epi-differentiability,
which was established in [23, Corollary 4.3].

######  Proposition 3.8 (characterization of strict twice epi-
differentiability).

Assume that $\varphi$ has the representation (1.1) around $\bar{x}\in{\rm
I\\!R}^{n}$ and $\bar{v}\in\partial\varphi(\bar{x})$ and that the basic
constraint qualification (2.11) holds at $x=\bar{x}$. Then there is a
neighborhood $U$ of $(\bar{x},\bar{v})$ such that for any $(x,v)\in
U\cap\,{\rm gph}\,\varphi$, the following properties are equivalent:

  * (a)

$\varphi$ is strictly twice epi-differentiable at $x$ for $v$;

  * (b)

${\rm d}^{2}\varphi(x,v)$ epi-converges (to something) as
$(x^{\prime},v^{\prime})\to(x,v)$ with
$v^{\prime}\in\partial\varphi(x^{\prime})$.

[Proof. ]By Proposition 2.6(a), $\varphi$ is prox-regular and
subdifferentially continuous at $\bar{x}$ for $\bar{v}$. Moreover, it follows
from [26, Theorem 13.14], $\varphi$ is twice epi-differentiable at $x$ for
$v\in\partial\varphi(x)$ whenever $(x,v)$ is sufficiently close to
$(\bar{x},\bar{v})$. The claimed equivalence is a special case of a more
general result in [23, Corollary 4.3], obtained for prox-regular functions.

We are now in a position to characterize strict twice epi-differentiability of
the composite form (1.1). Our main tools will be a chain and a sum rules for
epi-convergence of a sequence of extended-real-valued functions, established
in [26, Ecercise 7.47] and [26, Theorem 7.64], respectively. Recall from [26,
page 250] that a sequence of extended-real-valued functions
$\\{f^{k}{\\}_{k\in{\rm I\\!N}}}$ converges continuously to $f:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ if for every $x\in{\rm I\\!R}^{n}$ and
every sequence $x^{k}\to x$, we have $f^{k}(x^{k})\to f(x)$.

######  Theorem 3.9.

Assume that $\varphi$ has the representation (1.1) around $\bar{x}\in{\rm
I\\!R}^{n}$, $\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$, then the following properties are equivalent:

  * (a)

there exists a neighborhood $U$ of $(\bar{x},\bar{v})$ such that for any
$(x,v)\in U\cap{\rm gph}\,\partial\varphi$, $\varphi$ is strictly twice epi-
differentiable at $x$ for $v$;

  * (b)

$\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$.

[Proof. ]Suppose that (b) holds and take the neighborhood $U$ for which the
conclusions in Propositions 2.2(b) and 3.4 hold. By Proposition 2.6(d), we get
${\bar{\lambda}}\in{\rm ri}\,\partial g(\Phi(\bar{x}))$. Using (3.1) which
holds under the condition ${\bar{\lambda}}\in{\rm ri}\,\partial
g(\Phi(\bar{x}))$, we get
$K_{g}(\Phi(\bar{x}),{\bar{\lambda}})=K_{g}(z,\lambda)$ for all
$(z,\lambda)\in V\cap{\rm gph}\,\partial g$, where $V$ is taken from (3.1).
Shrinking the neighborhood $U$ if necessary and using (2.12), we can assume
that $(\Phi(x),\lambda)\in V\cap{\rm gph}\,\partial g$, where $(x,v)\in
U\cap{\rm gph}\,\partial\varphi$ and $\lambda$ is the unique Lagrange
multiplier in ${\Lambda}(x,v)$, which results from Proposition 2.2(b). Thus,
we arrive at

$K_{g}(\Phi(\bar{x}),{\bar{\lambda}})=K_{g}(\Phi(x),\lambda)\quad\mbox{for
all}\;\;(x,v)\in U\cap{\rm gph}\,\partial\varphi,\;\lambda\in{\Lambda}(x,v).$
(3.5)

We claim that for any sequence $\\{(x^{k},v^{k}){\\}_{k\in{\rm I\\!N}}}\subset
U\cap{\rm gph}\,\partial\varphi$ such that
$(x^{k},v^{k})\to(\bar{x},\bar{v})$, we have

${\rm d}^{2}\varphi(x^{k},v^{k})\xrightarrow{e}{\rm
d}^{2}\varphi(\bar{x},\bar{v}).$ (3.6)

To this end, pick $w\in{\rm I\\!R}^{n}$ and conclude from Proposition 3.4 that

${\rm
d}^{2}\varphi(x^{k},v^{k})(w)=f^{k}(w)+\delta_{K_{g}(\Phi(x^{k}),\lambda^{k})}(\nabla\Phi(x^{k})w)\quad\mbox{with}\;\;f^{k}(w):=\langle\lambda^{k},\nabla^{2}\Phi(x^{k})(w,w)\rangle.$

Since $(x^{k},v^{k})\to(\bar{x},\bar{v})$, we deduce from (2.12) that
$\lambda^{k}\to{\bar{\lambda}}$. This tells us that the sequence of functions
$\\{f^{k}{\\}_{k\in{\rm I\\!N}}}$ is continuously convergent to $f$, where
$f(w)=\langle{\bar{\lambda}},\nabla^{2}\Phi(\bar{x})(w,w)\rangle$ for any
$w\in{\rm I\\!R}^{n}$. Moreover, it follows from (3.5) that
$K_{g}(\Phi(\bar{x}),{\bar{\lambda}})=K_{g}(\Phi(x^{k}),\lambda^{k})$, which
immediately implies via [26, Proposition 7.4(f)] that
$\delta_{K_{g}(\Phi(x^{k}),\lambda^{k})}\xrightarrow{e}\delta_{K_{g}(\Phi(\bar{x}),{\bar{\lambda}})}$.
Appealing now to [26, Exercise 7.47(a)] tells us that

$\delta_{K_{g}(\Phi(x^{k}),\lambda^{k})}\circ\nabla\Phi(x^{k})\xrightarrow{e}\delta_{K_{g}(\Phi(\bar{x}),{\bar{\lambda}})}\circ\nabla\Phi(\bar{x})$
(3.7)

provided that the condition

$0\in{\rm int}\,\big{(}K_{g}(\Phi(\bar{x}),{\bar{\lambda}})-{\rm
rge\,}\nabla\Phi(\bar{x})\big{)}$ (3.8)

is satisfied. According to [2, Proposition 2.97], this condition amounts to

$K_{g}(\Phi(\bar{x}),{\bar{\lambda}})^{*}\cap{\rm
ker}\,\nabla\Phi(\bar{x})^{*}=\\{0\\}.$

By (2.6), we have $K_{g}(\Phi(\bar{x}),{\bar{\lambda}})^{*}\subset
D^{*}(\partial g)\big{(}\Phi(\bar{x}),{\bar{\lambda}}\big{)}(0)$, which
together with the SOQC (2.9) confirms that (3.8) is satisfied. This proves
(3.7). Appealing now to the sum rule for epi-convergence from [26, Theorem
7.46(b)] justifies (3.6). Thus, it results from Proposition 3.8 that $\varphi$
is strictly twice epi-differentiable at $\bar{x}$ for $\bar{v}$. To achieve
the same conclusion for any point $(x,v)\in{\rm gph}\,\partial\varphi$
sufficiently close to $(\bar{x},\bar{v})$, we claim that for any such a pair
$(x,v)$, we have $v\in{\rm ri}\,\partial\varphi(x)$. As pointed out above, the
condition $\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$ yields
${\bar{\lambda}}\in{\rm ri}\,\partial g(\Phi(\bar{x}))$. Since
$K_{g}(\Phi(\bar{x}),{\bar{\lambda}})=N_{\partial
g(\Phi(\bar{x}))}({\bar{\lambda}})$, we conclude from Proposition 2.6(c) that
the critical cone $K_{g}(\Phi(\bar{x}),{\bar{\lambda}})$ is a linear subspace.
This, combined with (3.5), ensures that $K_{g}(\Phi(x),\lambda)$ is a linear
subspace for any $(x,v)\in U\cap{\rm gph}\,\partial\varphi$ and the unique
Lagrange multiplier $\lambda$ in ${\Lambda}(x,v)$. Again, since
$K_{g}(\Phi(x),\lambda)=N_{\partial g(\Phi(x))}(\lambda)$, we arrive at
$\lambda\in{\rm ri}\,\partial g(\Phi(x))$. It follows from Proposition 2.6(d)
that $v\in{\rm ri}\,\partial\varphi(x)$, which proves our claim. Employing the
same argument as the one for $(\bar{x},\bar{v})$ indicates that $\varphi$ is
strictly twice epi-differentiable at $x$ for $v$ for any $(x,v)\in U\cap{\rm
gph}\,\partial\varphi$ and hence proves (a).

Assume now that (a) holds, which implies that $\varphi$ is strictly twice epi-
differentiable at $\bar{x}$ for $\bar{v}$. This implies that ${\rm
d}_{s}^{2}\varphi(\bar{x},\bar{v})={\rm d}^{2}\varphi(\bar{x},\bar{v})$.
According to [26, Theorem 13.14], we have ${\rm dom}\,{\rm
d}^{2}\varphi(\bar{x},\bar{v})=K_{\varphi}(\bar{x},\bar{v})=N_{\partial\varphi(\bar{x})}(\bar{v})$.
We claim that $K_{\varphi}(\bar{x},\bar{v})$ is a linear subspace. To justify
it, it suffices to show that if $w\in K_{\varphi}(\bar{x},\bar{v})$, we have
$-w\in K_{\varphi}(\bar{x},\bar{v})$. Take $w\in
K_{\varphi}(\bar{x},\bar{v})$. By Proposition 3.4, we get ${\rm
d}^{2}\varphi(\bar{x},\bar{v})(w)<\infty$ and hence ${\rm
d}_{s}^{2}\varphi(\bar{x},\bar{v})(w)<\infty$. Appealing now to Theorem 3.5
results in $\nabla\Phi(\bar{x})w\in
K_{g}(\Phi(\bar{x}),{\bar{\lambda}})-K_{g}(\Phi(\bar{x}),{\bar{\lambda}})$,
which is equivalent to $-\nabla\Phi(\bar{x})w\in
K_{g}(\Phi(\bar{x}),{\bar{\lambda}})-K_{g}(\Phi(\bar{x}),{\bar{\lambda}})$.
This, combined with Theorem 3.5, confirms that ${\rm
d}_{s}^{2}\varphi(\bar{x},\bar{v})(-w)<\infty$ and hence ${\rm
d}^{2}\varphi(\bar{x},\bar{v})(-w)<\infty$, which implies that $-w\in
K_{\varphi}(\bar{x},\bar{v})$. Thus, $N_{\partial\varphi(\bar{x})}(\bar{v})$
is a linear subspace and hence $\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$,
which completes the proof.

Note that when the polyhedral function $g$ in Theorem 3.9 is the pointwise
maximum $g(z)=\max\\{z_{1},\ldots,z_{m}\\}$ with $z=(z_{1},\ldots,z_{m})$ as
in Example 2.1(a), Theorem 3.9 covers [24, Proposition 3.8] with a different
proof. As pointed out in Example 2.1(a), in this case, the SOQC (2.9) is
equivalent to saying that the set $\\{\nabla\varphi_{i}(\bar{x})\,|\,i\in
J(\Phi(\bar{x}))\\}$ is affinely independent. When $g$ is given as the one in
Example 2.1(b), Theorem 3.9 reduces to [24, Proposition 4.13]. We should add
here both results in [24] only contain the implication (b)$\implies$(a) in
Theorem 3.9 and do not achieve the established equivalence of (a) and (b) as
in Theorem 3.9.

We continue by exploring an important geometric property of ${\rm
gph}\,\partial\varphi$, called strict proto-differentiability, which will be
of great importance in the next section. To this end, take a set-valued
mapping $F:{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ and recall from
[26, page 331] that $F$ is said to be proto-differentiable at $\bar{x}$ for
$\bar{y}\in F(\bar{x})$ if the outer graphical limit in (2.5) is actually a
full limit. When $F(\bar{x})$ is a singleton consisting of $\bar{y}$ only, the
notation $DF(\bar{x},\bar{y})$ is simplified to $DF(\bar{x})$. It is easy to
see that for a single-valued function $F$, which is differentiable at
$\bar{x}$, the graphical derivative $DF(\bar{x})$ boils down to the Jacobian
matrix of $F$ at $\bar{x}$, denoted by $\nabla F(\bar{x})$. Recall from [26,
Definition 9.53] that the strict graphical derivative of a set-valued mapping
$F$ at $\bar{x}$ for $\bar{y}$, is the set-valued mapping
$D_{*}F(\bar{x},\bar{y}):{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$,
defined by

${\rm gph}\,D_{*}F(\bar{x},\bar{y})=\limsup_{\begin{subarray}{c}t\searrow 0\\\
(x,y)\xrightarrow{{\rm gph}\,F}(\bar{x},\bar{y})\end{subarray}}\frac{{\rm
gph}\,F-(x,y)}{t}.$ (3.9)

The set-valued mapping $F$ is said to be strictly proto-differentiable at
$\bar{x}$ for $\bar{y}$ if the outer graphical limit in (3.9) is a full limit.
To shed more light on this definition, take a set $\Omega\subset{\rm
I\\!R}^{d}$ and $\bar{x}\in\Omega$. The regular (Clarke) tangent cone and the
paratingent cone to $\Omega$ at $\bar{x}$ are defined, respectively, by

${\widehat{T}}_{\Omega}(\bar{x})=\liminf_{x\xrightarrow{\Omega}\bar{x},t\searrow
0}\frac{\Omega-x}{t}\quad\mbox{and}\quad\widetilde{T}_{\Omega}(\bar{x})=\limsup_{x\xrightarrow{\Omega}\bar{x},t\searrow
0}\frac{\Omega-x}{t}.$

Since we always have ${\widehat{T}}_{\Omega}(\bar{x})\subset
T_{\Omega}(\bar{x})\subset\widetilde{T}_{\Omega}(\bar{x})$, strict proto-
differentiability of a set-valued mapping $F$ at $\bar{x}$ for $\bar{y}$
amounts to the condition ${\widehat{T}}_{{\rm
gph}\,F}(\bar{x},\bar{y})=\widetilde{T}_{{\rm gph}\,F}(\bar{x},\bar{y})$. Note
that if the latter equality holds, we must have
$D_{*}F(\bar{x},\bar{y})=DF(\bar{x},\bar{y})$. We recently showed in [6,
Theorem 4.3] that if $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a
polyhedral function and $(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$,
then $\partial g$ is strictly proto-differentiable at $\bar{z}$ for
${\bar{\lambda}}$ if and only if ${\bar{\lambda}}\in{\rm ri}\,\partial
g(\bar{z})$. Below, we are going to demonstrate that a similar result can be
expected for the composite form in (1.1) when the SOQC (2.9) is satisfied.

######  Theorem 3.10.

Assume that $\varphi$ has the representation (1.1) around $\bar{x}\in{\rm
I\\!R}^{n}$, $\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$, then the following properties are equivalent:

  * (a)

there exists a neighborhood $U$ of $(\bar{x},\bar{v})$ such that for any
$(x,v)\in U\cap{\rm gph}\,\partial\varphi$, $\partial\varphi$ is strictly
proto-differentiable at $x$ for $v$;

  * (b)

$\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$.

[Proof. ]As explained in the proof of Proposition 3.8, the composite function
$\varphi$ satisfies the assumptions of [23, Corollary 4.3]. The latter result
demonstrates that the property in (a) is equivalent to the property in Theorem
3.9(a). This, combined with Theorem 3.9, proves the equivalence of (a) and
(b).

We continue by characterizing the regularity of the graph of the subgradient
mappings of functions with the composite representation (1.1). Recall that a
set $C\subset{\rm I\\!R}^{d}$ is called regular at $\bar{x}\in C$ provided
that ${\widehat{N}}_{C}(\bar{x})=N_{C}(\bar{x})$. To achieve our goal, we
begin with an observation about the regular tangent cone.

######  Lemma 3.11.

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and the basic constraint qualification
(2.11) holds at $x=\bar{x}$. Then the regular tangent cone
${\widehat{T}}_{{\rm gph}\,\partial\varphi}(\bar{x},\bar{v})$ is a linear
subspace.

[Proof. ]By Proposition 2.6(a), the composite function $\varphi$, accompanied
with (2.11), is prox-regular and subdifferentially continuous at $\bar{x}$ for
$\bar{v}$. Thus, it results from [26, Proposition 13.46] that the subgradient
mapping $\partial\varphi:{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ is
graphically Lipschitzian of dimension $n$ around $(\bar{x},\bar{v})$, meaning
that ${\rm gph}\,\partial\varphi$ can be identified locally with the graph of
a Lipschitz continuous function from ${\rm I\\!R}^{n}$ into ${\rm I\\!R}^{n}$;
see [26, Definition 9.66] for more elaboration on this concept. Employing now
[27, Theorem 3.5(b)] tells us that ${\widehat{T}}_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$ is a linear subspace.

######  Theorem 3.12.

Assume that $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ has the
representation (1.1) around $\bar{x}\in{\rm I\\!R}^{n}$,
$\bar{v}\in\partial\varphi(\bar{x})$, and that
${\bar{\lambda}}\in{\Lambda}(\bar{x},\bar{v})$. If the SOQC (2.9) holds at
$(\bar{x},{\bar{\lambda}})$, then the following properties are equivalent:

  * (a)

$\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$;

  * (b)

${\rm gph}\,\partial\varphi$ is regular at $(\bar{x},\bar{v})$, that is
${\widehat{N}}_{{\rm gph}\,\partial\varphi}(\bar{x},\bar{v})=N_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$;

  * (c)

for any $w\in{\rm I\\!R}^{n}$, we have
$D(\partial\varphi)(\bar{x},\bar{v})(w)=D^{*}(\partial\varphi)(\bar{x},\bar{v})(w)$.

[Proof. ]Suppose that $\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$. It
follows from Theorem 3.10 that $\partial\varphi$ is strictly proto-
differentiable at $\bar{x}$ for $\bar{v}$. This is equivalent to saying that
${\widehat{T}}_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})=\widetilde{T}_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$, which implies that
${\widehat{T}}_{{\rm gph}\,\partial\varphi}(\bar{x},\bar{v})=T_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$. By [26, Corollary 6.29], the latter
is equivalent to saying that ${\widehat{N}}_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})=N_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$, which proves (b). Conversely, assume
that (b) holds. As pointed out above, this implies that ${\widehat{T}}_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})=T_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$. We claim that
$K_{\varphi}(\bar{x},\bar{v})$ is a linear subspace. By Proposition 2.6(b), we
have $K_{\varphi}(\bar{x},\bar{v})=N_{\partial\varphi(\bar{x})}(\bar{v})$.
Thus, to verify our claim, it suffice to show that if $w\in
K_{\varphi}(\bar{x},\bar{v})$, then $-w\in K_{\varphi}(\bar{x},\bar{v})$. Take
$w\in K_{\varphi}(\bar{x},\bar{v})$ and observe from [13, Theorem 7.2] that
${\rm dom}\,D(\partial\varphi)(\bar{x},\bar{v})=K_{\varphi}(\bar{x},\bar{v})$.
So, we find $u\in{\rm I\\!R}^{n}$ such that $u\in
D(\partial\varphi)(\bar{x},\bar{v})(w)$ or equivalently $(w,u)\in T_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$. By Lemma 3.11 and
${\widehat{T}}_{{\rm gph}\,\partial\varphi}(\bar{x},\bar{v})=T_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$, we conclude that $(-w,-u)\in T_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$. This can be translated as $-w\in{\rm
dom}\,D(\partial\varphi)(\bar{x},\bar{v})=K_{\varphi}(\bar{x},\bar{v})$, which
proves our claim. Since $N_{\partial\varphi(\bar{x})}(\bar{v})$ is a linear
subspace, we arrive at $\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$, and
hence obtain (a).

Now, assume (a) holds. This implies via Proposition 2.6(d) that
${\bar{\lambda}}\in{\rm ri}\,\partial g(\Phi(\bar{x}))$, where
${\bar{\lambda}}$ is the unique Lagrange multiplier in
${\Lambda}(\bar{x},\bar{v})$. Appealing to [6, Corollary 3.8] indicates that
the condition ${\bar{\lambda}}\in{\rm ri}\,\partial g(\Phi(\bar{x}))$ is
equivalent to

$D(\partial g)(\Phi(\bar{x}),{\bar{\lambda}})=D^{*}(\partial
g)(\Phi(\bar{x}),{\bar{\lambda}}).$ (3.10)

By the SOQC (2.9), we get ${\Lambda}(\bar{x},\bar{v})=\\{{\bar{\lambda}}\\}$.
Since the basic constraint qualification (2.11) holds, it follows from [13,
Theorem 7.2] that

$D(\partial\varphi)(\bar{x},\bar{v})(w)=\nabla^{2}\langle{\bar{\lambda}},\Phi\rangle(\bar{x})w+\nabla\Phi(\bar{x})^{*}D(\partial
g)(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w).$ (3.11)

Also, one can see from [17, Theorem 4.3] that

$D^{*}(\partial\varphi)(\bar{x},\bar{v})(w)=\nabla^{2}\langle{\bar{\lambda}},\Phi\rangle(\bar{x})w+\nabla\Phi(\bar{x})^{*}D^{*}(\partial
g)(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w).$ (3.12)

Combining these and (3.10) proves that
$D(\partial\varphi)(\bar{x},\bar{v})=D^{*}(\partial\varphi)(\bar{x},\bar{v})$.
Conversely, suppose that (c) holds. This, in particular, indicates that ${\rm
dom}\,D(\partial\varphi)(\bar{x},\bar{v})={\rm
dom}\,D^{*}(\partial\varphi)(\bar{x},\bar{v})$. By the second equation in
(2.7) and (3.12), we get

${\rm dom}\,D^{*}(\partial\varphi)(\bar{x},\bar{v})=\big{\\{}w\in{\rm
I\\!R}^{n}|\;\nabla\Phi(\bar{x})w\in
K_{g}(\Phi(\bar{x}),{\bar{\lambda}})-K_{g}(\Phi(\bar{x}),{\bar{\lambda}})\big{\\}},$

which clearly is a linear subspace. Thus, ${\rm
dom}\,D(\partial\varphi)(\bar{x},\bar{v})=K_{\varphi}(\bar{x},\bar{v})=N_{\partial\varphi(\bar{x})}(\bar{v})$
is a linear subspace. By Proposition 2.6(c), we get $\bar{v}\in{\rm
ri}\,\partial\varphi(\bar{x})$ and hence obtain (a).

We close this section by considering a special case of the polyhedral function
$g$ in the composite form (1.1). Assume that $\Theta$ is a subset of ${\rm
I\\!R}^{n}$ and $\bar{x}\in\Theta$ and that there exists a neighborhood $O$ of
$\bar{x}$ around which $\Theta$ has the representation

$\Theta\cap O=\big{\\{}x\in O|\,\Phi(x)\in C\big{\\}},$ (3.13)

where $C$ is a polyhedral convex set in ${\rm I\\!R}^{m}$ and that $\Phi$ is
taken from (1.1). This clearly fits into the composite form (1.1) by assuming
that $g=\delta_{C}$. An important example of the set $\Theta$ with the
representation (3.13) is when the polyhedral convex set $C=\\{0\\}$ with
$0\in{\rm I\\!R}^{m}$. In this case, it follows from Example 2.1(b) that the
SOQC (2.9) amounts to $\nabla\Phi(\bar{x})$ having full rank. Note that a set
$\Theta\subset{\rm I\\!R}^{n}$ is said to be a ${\cal C}^{2}$ smooth manifold
around a point $\bar{x}\in\Theta$ if there exists a neighborhood $O$ of
$\bar{x}$ on which $\Theta$ has the representation (3.13) with $C=\\{0\\}$
with $0\in{\rm I\\!R}^{m}$ and $\nabla\Phi(\bar{x})$ has full rank. For such a
set, it was shown recently in [10, Theorem 6.3] via a different approach that
both properties in Theorem 3.12(b)-(c) hold. It is important to mention that
our results, Theorems 3.10 and 3.12, go one step further and show that,
indeed, the regular tangent cone and the paratingent cone to ${\rm
gph}\,N_{\Theta}$ coincide when $\Theta$ is a ${\cal C}^{2}$ smooth manifold.

##  4 Stability Properties of Generalized Equations

This section concerns the stability properties of solution set to the
canonical perturbation of the generalized equation

$\bar{u}\in f(x)+\partial\varphi(x),$ (4.1)

where $f:{\rm I\\!R}^{n}\to{\rm I\\!R}^{n}$ is a ${\cal C}^{1}$ function and
$\varphi$ is taken from (1.1) and where $\bar{u}$ is a fixed vector in ${\rm
I\\!R}^{n}$. This generalized equation provides a rich and unified framework
to study stability properties of variational inequalities and KKT systems from
important classes of constrained and composite optimization problems. In
particular, when $\varphi=\delta_{C}$ with $C$ a polyhedral convex set in
${\rm I\\!R}^{n}$, it reduces to the generalized equation in [5] by Dontchev
and Rockafellar for which they demonstrated that strong metric regularity and
metric regularity of (4.1) are equivalent. Recall that a set-valued mapping
$F:{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ is called strongly
metrically regular at $\bar{x}$ for $\bar{y}\in F(\bar{x})$ if $F^{-1}$ admits
a Lipschitz continuous single-valued localization around $\bar{y}$ for
$\bar{x}$, which means that there exist neighborhoods $U$ of $\bar{x}$ and $V$
of $\bar{y}$ such that the mapping $y\mapsto F^{-1}(y)\cap U$ is single-valued
and Lipschitz continuous on $V$. According to [4, Proposition 3G.1], strong
metric regularity of $F$ at $\bar{x}$ for $\bar{y}$ amounts to $F$ being
metrically regular at $\bar{x}$ for $\bar{y}$ and its inverse $F^{-1}$
admitting a single-valued localization around $\bar{y}$ for $\bar{x}$.

Our first goal is to show that for the mapping $G:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$, defined by

$G(x)=f(x)+\partial\varphi(x),\;\;\;x\in{\rm I\\!R}^{n},$ (4.2)

metric regularity and strong metric regularity are equivalent. Our approach is
different from [5] and relies upon the characterization of strict proto-
differentiability of the subgradient mapping $\partial\varphi$, established in
Theorem 3.10. This forces us to confine our analysis to nondegenerate
solutions to (4.1). Recall that $\bar{x}$ is called a nondegenerate solution
to the generalized equation (4.1) if it satisfies the relative interior
condition

$\bar{u}-f(\bar{x})\in{\rm ri}\,\partial\varphi(\bar{x}).$ (4.3)

The following result presents an equivalent description of nondegenerate
solutions to (4.1).

######  Proposition 4.1.

Assume that $\bar{x}$ is a solution to the generalized equation (4.1) and that
the basic constraint qualification in (2.11) holds at $x=\bar{x}$. Then the
following properties are equivalent:

  * (a)

$\bar{x}$ is a nondegenerate solution to (4.1);

  * (b)

the critical cone $K_{\varphi}(\bar{x},-f(\bar{x}))$ is a linear subspace.

[Proof. ]According to (2.22), we have
$K_{\varphi}(\bar{x},\bar{u}-f(\bar{x}))=N_{\partial\varphi(\bar{x})}(\bar{u}-f(\bar{x}))$.
Since $\partial\varphi(\bar{x})$ is convex, we can conclude that
$K_{\varphi}(\bar{x},\bar{u}-f(\bar{x}))$ is a linear subspace if and only if
(4.3) is satisfied. This proves the equivalence of (a) and (b).

To proceed, define the solution mapping $S:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ to the canonical perturbation of
(4.1) by

$S(u):=G^{-1}(u)=\big{\\{}x\in{\rm I\\!R}^{n}\,\big{|}\,u\in
f(x)+\partial\varphi(x)\big{\\}},\quad u\in{\rm I\\!R}^{n}.$ (4.4)

We begin with the following result in which metric regularity of $G$ will be
characterized.

######  Theorem 4.2.

Assume that $\bar{x}$ is a nondegenerate solution to (4.1) and that the SOQC
in (2.9) holds at $(\bar{x},{\bar{\lambda}})$, where ${\bar{\lambda}}$ is the
unique vector in ${\Lambda}(\bar{x},\bar{u}-f(\bar{x}))$. Set
${\overline{K}}:=K_{\varphi}(\bar{x},\bar{u}-f(\bar{x}))$ and $A:=\nabla
f(\bar{x})+\nabla^{2}\langle{\bar{\lambda}},\Phi\rangle(\bar{x})$. Then the
following properties are equivalent:

  * (a)

the mapping $G$ in (4.2) is metrically regular at $\bar{x}$ for $\bar{u}$;

  * (b)

$\big{\\{}w\in{\rm
I\\!R}^{n}|\;A^{*}w\in{\overline{K}}^{\perp}\big{\\}}\cap{\overline{K}}=\\{0\\}$;

  * (c)

$A{\overline{K}}+{\overline{K}}^{\perp}={\rm I\\!R}^{n}$;

  * (d)

$DG(\bar{x},\bar{u})$ is surjective.

[Proof. ]By (4.3) and Theorem 3.12, we get
$D(\partial\varphi)(\bar{x},\bar{u}-f(\bar{x}))=D^{*}(\partial\varphi)(\bar{x},\bar{u}-f(\bar{x}))$.
This, along with (3.11), implies for any $w\in{\rm I\\!R}^{n}$ that

$\displaystyle D^{*}G(\bar{x},\bar{u})(w)$ $\displaystyle=$
$\displaystyle\nabla
f(\bar{x})^{*}w+D^{*}(\partial\varphi)(\bar{x},\bar{u}-f(\bar{x}))(w)$ (4.5)
$\displaystyle=$ $\displaystyle A^{*}w+\nabla\Phi(\bar{x})^{*}D(\partial
g)(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w)$ $\displaystyle=$
$\displaystyle
A^{*}w+\nabla\Phi(\bar{x})^{*}N_{K_{g}(\Phi(\bar{x}),{\bar{\lambda}})}(\nabla\Phi(\bar{x})w)$
$\displaystyle=$ $\displaystyle A^{*}w+N_{{\overline{K}}}(w),$

where the penultimate step results from (2.6) and the last equality comes from
Proposition 2.6(b). By Proposition 4.1, ${\overline{K}}$ is a linear subspace,
which brings us to

$u\in D^{*}G(\bar{x},\bar{u})(w)\iff
u-A^{*}w\in{\overline{K}}^{\perp},\;\;w\in{\overline{K}}.$

It is well-known (cf. [16, Theorem 3.3]) that metric regularity of $G$ at
$\bar{x}$ for $\bar{u}$ can be characterized by the implication

$0\in D^{*}G(\bar{x},\bar{u})(w)\implies w=0.$

Combining this with the calculation of $D^{*}G(\bar{x},\bar{u})(w)$, obtained
above, proves the equivalence of (a) and (b). By [26, Corollary 11.25(c)], we
have

$(A{\overline{K}})^{\perp}=\big{\\{}w\in{\rm
I\\!R}^{n}|\;A^{*}w\in{\overline{K}}^{\perp}\big{\\}},$

which implies (b) and (c) are equivalent. Arguing similar to (4.5), we get for
any $w\in{\rm I\\!R}^{n}$ that

$DG(\bar{x},\bar{u})(w)=Aw+N_{{\overline{K}}}(w),$ (4.6)

which brings us to

$(w,q)\in{\rm gph}\,DG(\bar{x},\bar{u})\iff
q-Aw\in{\overline{K}}^{\perp},\;\;w\in{\overline{K}}.$ (4.7)

This tells us that ${\rm
rge\,}DG(\bar{x},\bar{u})=A{\overline{K}}+{\overline{K}}^{\perp}$. Thus,
$DG(\bar{x},\bar{u})$ is surjective, meaning ${\rm
rge\,}DG(\bar{x},\bar{u})={\rm I\\!R}^{n}$, if and only if
$A{\overline{K}}+{\overline{K}}^{\perp}={\rm I\\!R}^{n}$, which demonstrates
that (c) and (d) are equivalent.

Next, we are going to show that metric regularity and strong metric regularity
of the mapping $G$ in (4.2) are equivalent for nondegenerate solutions to
(4.1). To achieve our goal, we are going to utilize the following
characterization of strong metric regularity from [4, Theorem 4D.1]: a set-
valued mapping $F:{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ is strongly
metrically regular at $\bar{x}$ for $\bar{y}\in F(\bar{x})$ provided that it
has a locally closed graph and the conditions

$0\in D_{*}F(\bar{x},\bar{y})(w)\;\Longrightarrow\;w=0$ (4.8)

and

$\bar{x}\in\liminf_{y\to\bar{y}}F^{-1}(y)$ (4.9)

hold.

######  Theorem 4.3 (equivalence of metric regularity and strong metric
regularity).

Assume that $\bar{x}$ is a nondegenerate solution to (4.1) and that the SOQC
in (2.9) holds at $(\bar{x},{\bar{\lambda}})$, where ${\bar{\lambda}}$ is the
unique vector in ${\Lambda}(\bar{x},\bar{u}-f(\bar{x}))$. Set
${\overline{K}}:=K_{\varphi}(\bar{x},\bar{u}-f(\bar{x}))$ and $A:=\nabla
f(\bar{x})+\nabla^{2}\langle{\bar{\lambda}},\Phi\rangle(\bar{x})$. Then the
following properties hold.

  * (a)

The mapping $G$ in (4.2) is metrically regular at $\bar{x}$ for $\bar{u}$ if
and only if it is strongly metrically regular at $\bar{x}$ for $\bar{u}$.

  * (b)

One of the equivalent properties (a)-(d) in Theorem 4.2 holds if and only if
the solution mapping $S$ in (4.4) has a Lipschitz continuous localization
$\sigma$ around $\bar{u}$ for $\bar{x}$, which is ${\cal C}^{1}$ in a
neighborhood of $\bar{u}$ and

$\nabla\sigma(\bar{u})=B\big{(}B^{*}AB\big{)}^{-1}B^{*},$

where $B\in{\rm I\\!R}^{n\times s}$ is a matrix whose columns form a basis for
the linear subspace ${\overline{K}}$ and $s={\rm dim}\,{\overline{K}}$.

[Proof. ]We begin with the proof of (a). If $G$ is strongly metrically regular
at $\bar{x}$ for $\bar{u}$, it clearly enjoys metric regularity at $\bar{x}$
for $\bar{u}$. Suppose now that $G$ is metrically regular at $\bar{x}$ for
$\bar{u}$. According to the discussion above, it suffices to verify the
validity of (4.8) and (4.9). The latter directly results from the estimate
(2.16) for $F=G$. To prove the former, take $w\in{\rm I\\!R}^{n}$ such that
$0\in D_{*}G(\bar{x},\bar{u})(w)$. We know from the SOQC and Theorem 3.12 that
$\partial\varphi$ is strictly proto-differentiable at $\bar{x}$ for
$\bar{u}-f(\bar{x})$ due to (4.3). This, coupled with [6, Proposition 5.3],
indicates that $G$ is strictly proto-differentiable at $\bar{x}$ for
$\bar{u}$. The discussion prior to Theorem 3.10 tells us that strict proto-
differentiability of $G$ at $\bar{x}$ for $\bar{u}$ yields
$D_{*}G(\bar{x},\bar{u})=DG(\bar{x},\bar{u})$. Thus, by (4.7), the condition
$0\in D_{*}G(\bar{x},\bar{u})(w)$ is equivalent to saying that
$-Aw\in{\overline{K}}^{\perp}$ and $w\in{\overline{K}}$. Since
${\overline{K}}$ is a linear subspace of dimension $s$, we find a matrix
$B\in{\rm I\\!R}^{n\times s}$ whose columns form a basis for ${\overline{K}}$.
This means that ${\overline{K}}={\rm rge\,}B$, which is equivalent to
${\overline{K}}^{\perp}={\rm ker}\,B^{*}$. This allows us to deduce from the
conditions $-Aw\in{\overline{K}}^{\perp}$ and $w\in{\overline{K}}$ that there
exists $q\in{\rm I\\!R}^{s}$ such that $w=Bq$ and $B^{*}ABq=0$. We are going
to show that the $s\times s$ matrix $B^{*}AB$ is nonsingular. To do so, pick
$p\in{\rm I\\!R}^{n}$. Since $G$ is metrically regular at $\bar{x}$ for
$\bar{u}$, it results from Theorem 4.2(c) that there are
$w^{\prime}\in{\overline{K}}$ and $p^{\prime}\in{\overline{K}}^{\perp}$ for
which we have $p=Aw^{\prime}+p^{\prime}$. By ${\overline{K}}={\rm rge\,}B$, we
find $d\in{\rm I\\!R}^{s}$ that $w^{\prime}=Bd$. Combining these and using
${\overline{K}}^{\perp}={\rm ker}\,B^{*}$, we arrive at

$B^{*}p=B^{*}(Aw^{\prime}+p^{\prime})=B^{*}Aw^{\prime}=B^{*}ABd.$

Because $p$ was chosen arbitrarily, we get ${\rm rge\,}B^{*}\subset{\rm
rge\,}(B^{*}AB)$. Since the opposite inclusion always holds, we obtain ${\rm
rge\,}B^{*}={\rm rge\,}(B^{*}AB)$. This, together with the fact that $B$ has
full column rank, implies that ${\rm rge\,}(B^{*}AB)={\rm I\\!R}^{s}$ and thus
confirms that $B^{*}AB$ is nonsingular. Consequently, the condition
$B^{*}ABq=0$ results in $q=0$ and so $w=Bq=0$. This proves (4.8) and completes
the proof of (a).

Turning to the proof (b), remember first that $S=G^{-1}$. So, the claimed
equivalence in (b) falls directly out of Theorem 4.2 and (a). Next, we are
going to show that if one of the equivalent properties (a)-(d) in Theorem 4.2
holds, the Lipschitz continuous localization of $S$ around $\bar{u}$ for
$\bar{x}$ is ${\cal C}^{1}$ around $\bar{u}$. To this end, we find
neighborhoods $U$ of $\bar{u}$ and $V$ of $\bar{x}$ such that the mapping
$u\mapsto S(u)\cap V$ is single-valued and Lipschitz continuous on $U$. Define
the function $\sigma:U\to V$ by $\sigma(u)=S(u)\cap V$. We claim that $\sigma$
is ${\cal C}^{1}$ in a neighborhood of $\bar{u}$. To justify it, remember from
the proof of (a) that $G$ is strictly proto-differentiable at $\bar{x}$ for
$\bar{u}$. Appealing to Theorem 3.10 allows us to ensure that $G$ enjoys the
same property at $x$ for $u$ whenever $(x,u)\in{\rm gph}\,G$ is sufficiently
close to $(\bar{x},\bar{u})$. Shrinking $U$ and $V$ if necessary, we can
assume without loss of generality that $G$ is strictly proto-differentiable at
$x$ for $u$ for any $(x,u)\in{\rm gph}\,G\cap(V\times U)$. Take any such a
pair $(x,u)$ and conclude from $S^{-1}=G$ that $S^{-1}$ is strictly proto-
differentiable at $u$ for $x$. Since strict proto-differentiability is a local
property of ${\rm gph}\,S$ and since ${\rm gph}\,\sigma={\rm
gph}\,S\cap(U\times V)$, $\sigma$ is strictly proto-differentiable at $u$ for
$x$. Employing [26, Proposition 3.1] tells us that $\sigma$ is strictly
differentiable on $U$, which is equivalent to saying that $\sigma$ is ${\cal
C}^{1}$ on $U$ due to [4, Exercise 1D.8].

To justify the claimed formula for the Jacobian matrix of $\sigma$ at
$\bar{u}$, take $p\in{\rm I\\!R}^{n}$ and set
$w=\nabla\sigma(\bar{u})p=D\sigma(\bar{u})(p)$. This implies that $p\in
DG(\bar{x},\bar{u})(w)$. By (4.7), the latter means that
$p-Aw\in{\overline{K}}^{\perp}$ and $w\in{\overline{K}}$. Recall that
${\overline{K}}={\rm rge\,}B$ and ${\overline{K}}^{\perp}={\rm ker}\,B^{*}$.
Thus, we find $q\in{\rm I\\!R}^{s}$ such that $w=Bq$, which leads us to

$0=B^{*}(p-Aw)=B^{*}p-B^{*}ABq.$

Since the matrix $B^{*}AB$ is nonsingular, we get

$\nabla\sigma(\bar{u})p=w=Bq=B(B^{*}AB)^{-1}B^{*}p,$

which completes the proof of theorem.

The equivalence of metric regularity and strong metric regularity for
generalized equations was first achieved in [5, Theorem 3] by Donchev and
Rockafellar without assuming the nondegeneracy for solutions. However, the
framework in [5] is associated with $\varphi=\delta_{C}$ in (4.1), $C$ being a
polyhedral convex set, and thus is narrower than the generalized equation in
(4.1). Moreover, the approach therein relies heavily on Robinson’s results in
[25] and did not utilize strict proto-differentiability. The new approach of
dealing with the latter equivalence was first presented in [6], where the main
attention was given to polyhedral functions.

######  Remark 4.4.

A closer look into the proof of Theorem 4.3 reveals that the underlying
property that allows to achieve the equivalence of metric regularity and
strong metric regularity for the generalized equation in (4.1) is strict
proto-differentiability of the mapping $G$ in (4.2) at $\bar{x}$ for
$\bar{u}$, which is indeed equivalent to the same property of the subgradient
mapping $\partial\varphi$ at $\bar{x}$ for $\bar{u}-f(\bar{x})$. As shown in
Theorem 3.10, the latter amounts to the nondegeneracy of the solution
$\bar{x}$ to (4.1). Since strict proto-differentiability is a local property
of ${\rm gph}\,\partial\varphi$, we could obtain the same equivalence if
$\partial\varphi$ in (4.1) is replaced with a graphical localization of
$\partial\varphi$ around $(\bar{x},\bar{u}-f(\bar{x}))$. To elaborate more,
suppose that $T:{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ is a set-
valued mapping such that ${\rm gph}\,T$ and ${\rm gph}\,\partial\varphi$
coincide locally around $(\bar{x},\bar{u}-f(\bar{x}))$. In this case, if all
the assumptions in Theorem 4.3 are satisfied, then both conclusions (a) and
(b) in the latter result hold for the generalized equation

$\bar{u}\in f(x)+T(x).$

This observation will be utilized later in this section while we are proving
continuous differentiability of the proximal mapping of $\varphi$.

An interesting case of the generalized equation (4.1) occurs when the
composite function $\varphi$ therein is the indicator function of a ${\cal
C}^{2}$ smooth manifold $\Theta$, defined by (3.13) with $C=\\{0\\}$. In this
case, the relative interior condition in (4.3) holds automatically because
$\partial\varphi(\bar{x})={\rm rge\,}\nabla\Phi(\bar{x})^{*}$, which is a
linear subspace of ${\rm I\\!R}^{n}$ and thus is relatively open. This tells
us that every solution to (4.1) with $\varphi=\delta_{\Theta}$ is
nondegenerate. The next result shows that metric regularity and strong metric
regularity in this case are always equivalent.

######  Corollary 4.5.

Assume that $\Theta$ is a ${\cal C}^{2}$ smooth manifold in ${\rm I\\!R}^{n}$
and that $\bar{x}$ is a solution to the generalized equation in (4.1), where
$\varphi=\delta_{\Theta}$. Then the mapping $G$ in (4.2) is metrically regular
at $\bar{x}$ for $\bar{u}$ if and only if it is strongly metrically regular at
$\bar{x}$ for $\bar{u}$.

[Proof. ]This results from our discussion prior to this corollary and Theorem
4.3(a).

Our final task is to study continuous differentiability of the proximal
mapping of the composite function $\varphi$ in (1.1). Recall that proximal
mapping of $\varphi$ for a parameter value $r>0$, denoted by
${\mbox{prox}\,}_{r\varphi}$, is defined by

${\mbox{prox}\,}_{r\varphi}(x)=\operatorname*{argmin}_{w\in{\rm
I\\!R}^{n}}\Big{\\{}\varphi(w)+\frac{1}{2r}\|w-x\|^{2}\Big{\\}}.$

To ensure that ${\mbox{prox}\,}_{r\varphi}$ is nonempty, we have to assume
that $\varphi$ is prox-bounded, meaning that for some $\alpha\in{\rm I\\!R}$,
the function $\varphi+\alpha\|\cdot\|^{2}$ is bounded from below on ${\rm
I\\!R}^{n}$; see [26, Exercise 1.24] for more equivalent descriptions. An
important instance of $\varphi$ for which this condition automatically holds
is when $\varphi=\delta_{\Theta}$ with $\Theta$ taken from (3.13). In this
case, the proximal mapping ${\mbox{prox}\,}_{r\varphi}$ boils down to the
projection mapping $P_{\Theta}$. Below, we collect some important properties
of the proximal mapping of $\varphi$, which will be utilized in our
characterization of continuous differentiability of
${\mbox{prox}\,}_{r\varphi}$ in the rest of this section.

######  Lemma 4.6.

Assume that $\varphi$ has the representation (1.1) around $\bar{x}\in{\rm
I\\!R}^{n}$ and $\bar{v}\in\partial\varphi(\bar{x})$, and that the basic
constraint qualification (2.11) holds at $x=\bar{x}$. Suppose further that
$\varphi$ is prox-bounded. Then there exist positive constants $\varepsilon$
and $\rho$ such that for any $r\in(0,1/\rho)$, there is a neighborhood $U_{r}$
of $\bar{x}+r\bar{v}$ on which ${\mbox{prox}\,}_{r\varphi}$ is nonempty,
single-valued, Lipschitz continuous and can be calculated by

${\mbox{prox}\,}_{r\varphi}=(I+rT_{\varepsilon})^{-1},$ (4.10)

where the set-valued mapping $T_{\varepsilon}:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ is defined by

$T_{\varepsilon}(x)=\begin{cases}\partial\varphi(x)\cap\mathbb{B}_{\varepsilon}(\bar{v})&\mbox{if}\;\;x\in\mathbb{B}_{\varepsilon}(\bar{x}),\\\
\emptyset&\mbox{otherwise},\end{cases}$ (4.11)

and where $I$ stands for the $n\times n$ identity matrix. Moreover, we have

$\nabla e_{r}\varphi(x)=\frac{1}{r}(x-{\mbox{prox}\,}_{r\varphi}(x)),\;\;x\in
U_{r},$ (4.12)

where the Moreau envelope function $e_{r}\varphi$ is defined by

$e_{r}\varphi(x)=\inf_{w\in\in{\rm
I\\!R}^{n}}\big{\\{}\varphi(w)+\frac{1}{2r}\|w-x\|^{2}\big{\\}},\;\;x\in{\rm
I\\!R}^{n}.$

[Proof. ]By Proposition 2.6(a), the composite function $\varphi$ is prox-
regular and subdifferentially continuous at $\bar{x}$ for $\bar{v}$. Both
results about ${\mbox{prox}\,}_{r\varphi}$ were established in [21, Theorem
4.4].

We proceed with a characterization of continuous differentiability of the
proximal mapping of the composite function $\varphi$ in (1.1).

######  Theorem 4.7.

Assume that $\varphi$ has the representation (1.1) around $\bar{x}\in{\rm
I\\!R}^{n}$ and $\bar{v}\in\partial\varphi(\bar{x})$, and that the SOQC in
(2.9) holds at $(\bar{x},{\bar{\lambda}})$, where ${\bar{\lambda}}$ is the
unique vector in ${\Lambda}(\bar{x},\bar{v})$. Suppose further that $\varphi$
is prox-bounded. Then the following properties are equivalent:

  * (a)

there exists a positive constant $\rho$ such that for any $r\in(0,1/\rho)$,
the proximal mapping ${\mbox{prox}\,}_{r\varphi}$ is ${\cal C}^{1}$ in a
neighborhood of $\bar{x}+r\bar{v}$;

  * (b)

there exists a positive constant $\rho$ such that for any $r\in(0,1/\rho)$,
the envelope function $e_{r}\varphi$ is ${\cal C}^{2}$ in a neighborhood of
$\bar{x}+r\bar{v}$;

  * (c)

$\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$.

[Proof. ]Assume first that (c) holds and take positive constants $\varepsilon$
and $\rho$ from Lemma 4.6. Fix $r\in(0,1/\rho)$ and consider the generalized
equation

$\bar{u}\in(I+rT_{\varepsilon})(x),\;\;x\in{\rm I\\!R}^{n},$ (4.13)

where $\bar{u}=\bar{x}+r\bar{v}$ and $T_{\varepsilon}$ is defined by (4.11).
We know from Lemma 4.6 that the solution set to (4.13), namely
$(I+rT_{\varepsilon})^{-1}(\bar{u})$, is single-valued and is precisely
${\mbox{prox}\,}_{r\varphi}(\bar{u})$. Moreover, we can find a neighborhood
$U_{r}$ of $\bar{u}$ such that for any $u\in U_{r}$ the solution mapping to
the canonical perturbation of (4.13), namely the generalized equation

$u\in(I+rT_{\varepsilon})(x),\;\;x\in{\rm I\\!R}^{n},$ (4.14)

is ${\mbox{prox}\,}_{r\varphi}(u)$. Also, ${\mbox{prox}\,}_{r\varphi}$ is
single-valued and Lipschitz continuous on $U_{r}$. Thus, it follows from
(4.10) and [4, Proposition 3G.1] that $I+rT_{\varepsilon}$ is metrically
regular at $\bar{x}$ for $\bar{u}$. We know from Theorem 3.10 that
$\partial\varphi$ is strictly proto-differentiable at $\bar{x}$ for $\bar{v}$.
This amounts to saying that ${\widehat{T}}_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})=\widetilde{T}_{{\rm
gph}\,\partial\varphi}(\bar{x},\bar{v})$. By the definition of
$T_{\varepsilon}$ in (4.11), we obtain ${\rm gph}\,T_{\varepsilon}={\rm
gph}\,\partial\varphi\cap(\mathbb{B}_{\varepsilon}(\bar{x})\times\mathbb{B}_{\varepsilon}(\bar{v}))$,
meaning that that the graphs of $T_{\varepsilon}$ and $\partial\varphi$
coincide locally around $(\bar{x},\bar{v})$. This implies that
${\widehat{T}}_{{\rm
gph}\,T_{\varepsilon}}(\bar{x},\bar{v})=\widetilde{T}_{{\rm
gph}\,T_{\varepsilon}}(\bar{x},\bar{v})$, which means that $T_{\varepsilon}$
is strictly proto-differentiable at $\bar{x}$ for $\bar{v}$. This clearly
shows that $rT_{\varepsilon}$ is strictly proto-differentiable at $\bar{x}$
for $r\bar{v}$ and so is $I+rT_{\varepsilon}$ at $\bar{x}$ for $\bar{u}$. As
discussed in Remark 4.4, this allows us to obtain both conclusions (a) and (b)
in Theorem 4.3 for the generalized equation in (4.13). Thus,
$I+rT_{\varepsilon}$ is metrically regular at $\bar{x}$ for $\bar{u}$ if and
only if the solution mapping to (4.14) has a Lipschitz continuous localization
around $\bar{u}$ for $\bar{x}$, which is ${\cal C}^{1}$ in a neighborhood of
$\bar{u}$. Since we already showed that $I+rT_{\varepsilon}$ is metrically
regular at $\bar{x}$ for $\bar{u}$, and since the solution mapping to (4.14)
is ${\mbox{prox}\,}_{r\varphi}$ on $U_{r}$, we can conclude by shrinking
$U_{r}$ if necessary that ${\mbox{prox}\,}_{r\varphi}$ is ${\cal C}^{1}$ in a
neighborhood of $\bar{u}$. This completes the proof of the implication
(c)$\implies$(a).

To justify the opposite implication, assume that (a) holds. Pick
$r\in(0,1/\rho)$ and set $h:={\mbox{prox}\,}_{r\varphi}$. Since $h$ is ${\cal
C}^{1}$ in a neighborhood of $\bar{x}+r\bar{v}$, we conclude from [27,
Proposition 3.1] that $T_{{\rm gph}\,h}(\bar{x}+r\bar{v},\bar{y})$ with
$\bar{y}:=h(\bar{x}+r\bar{v})$ is a linear subspace. It follows from (4.10)
that

$Dh(\bar{x}+r\bar{v})=\big{(}I+rD(\partial\varphi)(\bar{x},\bar{v})\big{)}^{-1};$
(4.15)

see the proof of [26, Exercise 12.64] for a similar result. This formula
implies that

$(w,q)\in T_{{\rm gph}\,\partial\varphi}(\bar{x},\bar{v})\iff(w+rq,w)\in
T_{{\rm gph}\,h}(\bar{x}+r\bar{v},\bar{y}).$

Thus $T_{{\rm gph}\,\partial\varphi}(\bar{x},\bar{v})$ is a linear subspace
since $T_{{\rm gph}\,h}(\bar{x}+r\bar{v},\bar{y})$ has this property. By
$T_{{\rm gph}\,\partial\varphi}(\bar{x},\bar{v})={\rm
gph}\,D(\partial\varphi)(\bar{x},\bar{v})$, we conclude that ${\rm
dom}\,D(\partial\varphi)(\bar{x},\bar{v})$ is a linear subspace. We know from
[13, Theorem 7.2] that ${\rm
dom}\,D(\partial\varphi)(\bar{x},\bar{v})=K_{\varphi}(\bar{x},\bar{v})$ and
from (2.22) that
$K_{\varphi}(\bar{x},\bar{v})=N_{\partial\varphi(\bar{x})}(\bar{v})$. This,
combined with $K_{\varphi}(\bar{x},\bar{v})$ being a linear subspace, tells us
that $\bar{v}\in{\rm ri}\,\partial\varphi(\bar{x})$ and hence proves (c). The
equivalence of (a) and (b) results from the identity in (4.12). This completes
the proof.

It is important to mention that a characterization of continuous
differentiability of the proximal mapping of prox-regular functions, which
encompass the composite function $\varphi$ in (1.1), was achieved in [23,
Theorem 4.4] under a rather restrictive assumption that $\bar{x}$, in the
notation of Theorem 4.7, must be a global minimum of $\varphi$. This forces us
to just deal with the case that $\bar{v}=0$. Our new approach, which stems
from the equivalence of metric regularity and strong metric regularity for
generalized equations at their nondegenerate solutions, allows us to drop the
latter restriction. Note also that the given characterization in [23] does not
go far enough to provide a characterization of continuous differentiability of
the proximal mapping via the relative interior condition in Theorem 4.7(b).

Continuous differentiability of the projection mapping to prox-regular sets in
Hilbert spaces was studied recently in [3] by extending the approach,
pioneered by Holmes in [8] for convex sets in Hilbert spaces. His main result,
[8, Theorem 2], states that if $\Omega\subset{\rm I\\!R}^{d}$ is a closed
convex set, $x\in{\rm I\\!R}^{d}$, the boundary of $\Omega$ is a ${\cal
C}^{2}$ smooth manifold around $y=P_{\Omega}(x)$, then the projection mapping
$P_{\Omega}$ is ${\cal C}^{1}$ in a neighborhood of the open normal ray
$\\{y+t(x-y)|\;t>0\\}$. It was shown in [3, Theorem 2.4] that under a similar
assumption with convexity replaced by prox-regularity, one can find $\rho>0$
such that a similar result holds for $P_{\Omega}$ in a neighborhood of the
open normal ray $\\{y+t(x-y)|\;t\in(0,1/\rho)\\}$. Holmes’s result in [8] and
its extension in [3] require that the boundary of the set under consideration
be a ${\cal C}^{2}$ smooth manifold, a condition which is not needed in our
approach. Moreover, we were able to provide a characterization of continuous
differentiability of the proximal mapping of functions, which goes beyond the
projection mapping onto sets. The price we paid is that our framework is
narrower than [3] and that we assume the space under consideration is finite
dimensional. As we show in our subsequent paper, the main driving force behind
finding a characterization of continuous differentiability of prox-regular
sets in a finite dimensional space is strict proto-differentiability, which is
equivalent to the relative interior condition in Theorem 4.7(b) when we are
dealing with a set with the representation (3.13).

Next, we are going to present a characterization of continuous
differentiability of the projection mapping to $\Theta$, where $\Theta$ is
defined by (3.13). In this case, it is not hard to see from (2.10) that the
SOQC in (2.9) boils down to

${\rm span}\,\big{\\{}N_{C}(\Phi(\bar{x}))\big{\\}}\cap{\rm
ker}\,\nabla\Phi(\bar{x})^{*}=\\{0\\}$ (4.16)

with the polyhedral convex set $C$ taken from (3.13).

######  Corollary 4.8.

Assume that $\Theta$ is a subset of ${\rm I\\!R}^{n}$ and $\bar{x}\in\Theta$
with the representation (3.13) around $\bar{x}$ and that $\bar{v}\in
N_{\Theta}(\bar{x})$ and the condition (4.16) holds at $\bar{x}$. Then the
following conditions are equivalent:

  * (a)

there exists a positive constant $\rho$ such that for any $r\in(0,1/\rho)$,
the projection mapping $P_{\Theta}$ is ${\cal C}^{1}$ in a neighborhood of
$\bar{x}+r\bar{v}$;

  * (b)

there exists a positive constant $\rho$ such that for any $r\in(0,1/\rho)$,
the function $x\mapsto{\rm dist}(x,\Theta)^{2}$ is ${\cal C}^{2}$ in a
neighborhood of $\bar{x}+r\bar{v}$;

  * (c)

$\bar{v}\in{\rm ri}\,N_{\Theta}(\bar{x})$.

[Proof. ]This results from Theorem 4.7 by setting $\varphi=\delta_{\Theta}$
therein. Note that $\delta_{\Theta}$ is clearly prox-bounded, which is
required in Theorem 4.7.

An important example of the set $\Theta$ with the representation (3.13) around
$\bar{x}$ that satisfies (4.16) is ${\cal C}^{2}$ smooth manifolds. This
happens when the polyhedral convex set $C$ in (3.13) is $\\{0\\}$ with
$0\in{\rm I\\!R}^{m}$. Observe from Example 2.1(b) that the condition (4.16)
amounts to $\nabla\Phi(\bar{x})$ having full rank when $\Theta$ is a ${\cal
C}^{2}$ smooth manifold. In this case, the relative interior condition
$\bar{v}\in{\rm ri}\,N_{\Theta}(\bar{x})$ automatically holds since we have
$N_{\Theta}(\bar{x})={\rm rge\,}\nabla\Phi(\bar{x})^{*}$. By Corollary 4.8, we
can find a positive constant $\rho$ such that for any $r\in(0,1/\rho)$, the
projection mapping $P_{\Theta}$ is always ${\cal C}^{1}$ in a neighborhood of
$\bar{x}+r\bar{v}$ whenever $\bar{v}\in N_{\Theta}(\bar{x})={\rm
rge\,}\nabla\Phi(\bar{x})^{*}$. In particular, when $\bar{v}=0$, we deduce
from (3.11) and Proposition 2.6(b) that

$DN_{\Theta}(\bar{x},\bar{v})=N_{K_{\Theta}(\bar{x},\bar{v})}=N_{T_{\Theta}(\bar{x})},$

where the last equality results from $\bar{v}=0$ and the definition of the
critical cone of $\Theta$. This, together with (4.15), tells us that

$\nabla
P_{\Theta}(\bar{x})=DP_{\Theta}(\bar{x})=(I+N_{T_{\Theta}(\bar{x})})^{-1}=P_{T_{\Theta}(\bar{x})}.$

This formula and continuous differentiability of $P_{\Theta}$ for a ${\cal
C}^{2}$ smooth manifold $\Theta$ at any point $\bar{x}\in\Theta$ were observed
before in [11, Lemma 2.1], which is a special case of Corollary 4.8 for a
${\cal C}^{2}$ smooth manifold $\Theta$ with $\bar{v}=0$.

## Acknowledgments

The first author would like to thank Vietnam Institute for Advanced Study in
Mathematics for hospitality during her post-doctoral fellowship of the
Institute in 2021–2022.

## References

  * [1] J.V. Burke and A. Engle, Strong metric (sub)regularity of KKT mappings for piecewise linear-quadratic convex composite optimization, Math. Oper. Res., 45 (2020), 797–1192.
  * [2] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000.
  * [3] R. Correa, D. Salas, and L. Thibault, Smoothness of the metric projection onto nonconvex bodies in Hilbert spaces, J. Math. Anal. Appl. 457 (2018), 1307–1332.
  * [4] A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings: A View from Variational Analysis, Springer, New York, 2014.
  * [5] A. L. Dontchev and R. T. Rockafellar, Characterizations of strong regularity for variational inequalities over polyhedral convex sets, SIAM J. Optim. 6 (1996), 1087–1105.
  * [6] N.T.V. Hang, W. Jung, and M.E. Sarabi, Role of Subgradients in Variational Analysis of Polyhedral Functions, arXiv.4402720 (2022).
  * [7] N.T.V. Hang and M.E. Sarabi, Local convergence analysis of augmented Lagrangian methods for piecewise linear-quadratic composite optimization problems. SIAM J. Optim. 31(4), 2665–2694 (2021).
  * [8] R.B. Holmes, Smoothness of certain metric projections on Hilbert space. Trans. Amer. Math. Soc. 183, 87–100 (1973).
  * [9] A.D. Ioffe, Variational Analysis of Regular Mappings: Theory and Applications. Springer, Cham, Switzerland, (2017).
  * [10] A.S. Lewis and C. Wylie, Active-set Newton methods and partial smoothness, Math. Oper. Res., to appear, doi.org/10.1287/moor.2020.1075.
  * [11] A.S. Lewis and J. Malick, Alternating projections on manifolds, Math. Oper. Res., 33 (2008) 216–234.
  * [12] A. Milzarek, Numerical Methods and Second Order Theory for Nonsmooth Problems, Ph.D. Dissertation, University of Munich, 2016.
  * [13] A. Mohammadi, B. Mordukhovich, and M. E. Sarabi, Variational analysis of composite models with applications to continuous optimization, Math. Oper. Res., to appear, doi.org/10.1287/moor.2020.1074.
  * [14] A. Mohammadi, B. Mordukhovich, and M. E. Sarabi, Parabolic regularity via geometric variational analysis. Trans. Amer. Soc. 374 (2021), 1711–1763.
  * [15] A. Mohammadi and M. E. Sarabi, Twice epi-differentiability of extended-real-valued functions with applications in composite optimization, SIAM J. Optim. 30 (2020), 2379–2409.
  * [16] B.S. Mordukhovich, Variational Analysis and Generalized Differentiation, I: Basic Theory; II: Applications. Springer Berlin, Heidelberg (2006).
  * [17] B. S. Mordukhovich and R. T. Rockafellar, Second-order subdifferential calculus with application to tilt stability in optimization, SIAM J. Optim. 22 (2012), 953–986.
  * [18] B. S. Mordukhovich and M. E. Sarabi, Second-order analysis of piecewise linear functions with applications to optimization and stability, J. Optim. Theory Appl. 171 (2016), 504–526.
  * [19] B. S. Mordukhovich and M. E. Sarabi, Generalized Newton algorithms for tilt-stable minimizers in nonsmooth optimization, SIAM J. Optim. 31 (2021), 1184–1214.
  * [20] B. S. Mordukhovich, M. E. Sarabi and R. T. Rockafellar, Characterizations of full stability in constrained optimization, SIAM J. Optim. 23 (2013), 1810–1849.
  * [21] R. A. Poliquin and R. T. Rockafellar, Prox-regular functions in variational analysis  Trans. Amer. Math. Soc. 348 (1996), 1805–1838.
  * [22] R. A. Poliquin and R. T. Rockafellar, Tilt stability of a Local Minimum, SIAM J. Optim., 8 (1998), 287–299.
  * [23] R. A. Poliquin and R. T. Rockafellar, Generalized Hessian properties of regularized nonsmooth functions, SIAM J. Optim. 6 (1996), 1121–1137.
  * [24] R. A. Poliquin and R. T. Rockafellar, Second-order nonsmooth analysis in nonlinear programming, in Recent Advances in Optimization (D. Du, L. Qi and R. Womersley, eds.), World Scientific Publishers, 1995, 322–350.
  * [25] S.M. Robinson, Normal maps induced by linear transformations. Math. Oper. Res. 17(3), 691–714 (1992).
  * [26] R. T. Rockafellar and R. J-B. Wets, Variational Analysis, Springer, Berlin, 1998.
  * [27] R. T. Rockafellar, Maximal monotone relations and the second derivatives of nonsmooth functions, Ann. Inst. H. Poincaré Analyse Non Linéaire 2 (1985), 167–184.
  * [28] R. T. Rockafellar, First- and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc. 307 (1988), 75–108.
  * [29] R. T. Rockafellar, Generalized second derivatives of convex functions and saddle functions, Trans. Amer. Math. Soc. 322 (1990), 51–77.
  * [30] R. T. Rockafellar, Variational Convexity and The Local Monotonicity of Subgradient Mappings, Vietnam Journal of Math. 47 (2019), 547–561.
  * [31] R. T. Rockafellar, Augmented Lagrangians and hidden convexity in sufficient conditions for local optimality. Math. Program. (2022). doi.org/10.1007/s10107-022-01768-w
  * [32] M. E. Sarabi, Primal superlinear convergence of SQP methods for piecewise linear-quadratic composite optimization problems, Set-Valued Var. Anal., 30 (2022), 1–37.