ROLE OF SUBGRADIENTS IN VARIATIONAL ANALYSIS OF POLYHEDRAL FUNCTIONS
NGUYEN T. V. HANG111Institute of Mathematics, Vietnam Academy of Science and
Technology, Hanoi, Vietnam (ntvhang@math.ac.vn). Research of this author is
partially supported by Vietnam Academy of Science and Technology under grant
CTTH00.01/22-23., WOOSUK JUNG222 Department of Mathematics, Miami University,
Oxford, OH 45065, USA (jungw2@miamioh.edu)., and M. EBRAHIM
SARABI333Corresponding author, Department 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. Understanding the role that subgradients play in various second-
order variational analysis constructions can help us uncover new properties of
important classes of functions in variational analysis. Focusing mainly on the
behavior of the second subderivative and subgradient proto-derivative of
polyhedral functions, functions with polyhedral epigraphs, we demonstrate that
choosing the underlying subgradient, utilized in the definitions of these
concepts, from the relative interior of the subdifferential of polyhedral
functions ensures stronger second-order variational properties such as strict
twice epi-differentiability and strict subgradient proto-differentiability.
This allows us to characterize continuous differentiability of the proximal
mapping and twice continuous differentiability of the Moreau envelope of
polyhedral functions. We close the paper with proving the equivalence of
metric regularity and strong metric regularity of a class of generalized
equations at their nondegenerate solutions.
Keywords Polyhedral functions, reduction lemma, nondegenerate solutions,
strict proto-differentiability, strict twice epi-differentiability, proximal
mappings, strong metric regularity.
Mathematics Subject Classification (2000) 90C31, 65K99, 49J52, 49J53

##  1 Introduction

Second-order variational constructions such as the second subderivative and
subgradient proto-derivative play an important role in parametric optimization
and convergence analysis of important numerical algorithms such as the
augmented Lagrangian method [5, 28]. Given an extended-real-valued function
$f:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}:=[-\infty,\infty]$, these second-
order variational constructions are defined at a point $(x,v)$ in the graph of
the subgradient mapping of $f$. One may wonder what impacts the selection of
the subgradient $v$ can have in these constructions. Our main goal in this
paper is to study the underlying role that the selection of a subgradient can
play for such constructions. To achieve this goal, we focus mainly on a
particular class of convex functions called polyhedral functions. Recall that
a proper function $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is called
polyhedral if its epigraph is a polyhedral convex set. Given $\bar{z}\in{\rm
I\\!R}^{m}$ with $g(\bar{z})$ finite, consider a subgradient
${\bar{\lambda}}\in\partial g(\bar{z})$. It is well-known (cf. [29,
Proposition 13.9]) that the polyhedral function $g$ is twice epi-
differentiable at $\bar{z}$ for ${\bar{\lambda}}$, that the subgradient
mapping $\partial g$ is proto-differentiable at $\bar{z}$ for
${\bar{\lambda}}$, and that its proximal mapping is directionally
differentiable at $\bar{z}+{\bar{\lambda}}$; see Sections 3 and 4 for the
definitions of these concepts.

Should we expect further properties if, in addition, we assume that
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$? This is the main question
that we are going to investigate for this class of convex functions. Note that
such a relative interior condition has been utilized in several studies
related to different numerical methods, including the partial smoothness [11]
and the ${\cal U}$-Lagrangian of convex functions [10]. Therefore
understanding the role that is played by this condition in second-order
variational analysis can lead to stronger stability properties for important
classes of functions in variational analysis as demonstrated in Sections 4 and
5.

Following this question, we uncover new second-order variational properties of
polyhedral functions, including strict twice epi-differentiability and strict
subgradient proto-differentiability, under this extra assumption. These
findings allow us to achieve a useful characterization of continuous
differentiability of the proximal mapping and twice continuous
differentiability of the Moreau envelope of polyhedral functions. As an
important application, we turn to study stability properties of the solution
mapping to the generalized equation

$0\in\psi(x)+\partial g(x),$ (1.1)

where $\psi:{\rm I\\!R}^{m}\to{\rm I\\!R}^{m}$ is a ${\cal C}^{1}$ mapping and
$g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a polyhedral function. Our
interest is mainly in examining the relationship between metric regularity and
strong metric regularity for (1.1). The seminal work of Donchev and
Rockafellar in [3] demonstrated that these properties are equivalent for (1.1)
when the polyhedral function $g$ is the indicator function of a polyhedral
convex set. Employing our new developments under the relative interior
condition, we are going to show that if $\bar{x}$ is a nondegenerate solution
to the generalized equation (1.1), meaning that it satisfies the condition

$-\psi(\bar{x})\in{\rm ri}\,\partial g(\bar{x}),$ (1.2)

then under some verifiable assumptions the solution mapping to the canonical
perturbation of (1.1) has a Lipschitz continuous single-valued localization,
which is continuously differentiable. The latter smoothness of a localization
of solution mappings of generalized equations resembles a similar conclusion
from the classical inverse mapping theorem.

The rest of the paper is organized as follows. Section 2 contains definitions
of important concepts, used in this paper. We also establish some properties
of polyhedral functions. Section 3 begins with a new proof of the reduction
lemma for polyhedral functions and then we present its important consequences
in various second-order variational constructions. In particular, we show that
under the relative interior condition, the subgradient mappings of polyhedral
functions are strictly proto-differentiable. Section 4 is devoted to study
strict twice epi-differentiablity of polyhedral functions. As an important
consequence, we characterize continuous differentiability of the proximal
mapping and twice continuous differentiability of the Moreau envelope of
polyhedral functions. The final section, Section 5, concerns the equivalence
of metric regularity and strong metric regularity for the generalized equation
(1.1). Using this equivalence and (1.2), we present sufficient conditions for
a smooth single-valued localization of the solution mapping to the canonical
perturbation of (1.1).

##  2 Notation and Preliminary Results

In what follows, 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$. In the product space ${\rm I\\!R}^{n}\times{\rm
I\\!R}^{m}$, we use the norm $\|(w,u)\|=\sqrt{\|w\|^{2}+\|u\|^{2}}$ for any
$(w,u)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}$. Given a nonempty set
$C\subset{\rm I\\!R}^{n}$, the symbols ${\rm int}\,C$, ${\rm ri}\,C$, ${\rm
cone}\,C$, and ${\rm co}\,C$ signify its interior, relative interior, conic
hull, and convex hull, respectively. For any set $C$ in ${\rm I\\!R}^{n}$, its
indicator function 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(w)\\}$.

In this paper, the convergence of a family of sets is always understood in the
sense of Painlevé-Kuratowski (cf. [29, 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$. 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$, where ${\rm
epi}\,f=\\{(x,\alpha)\in{\rm I\\!R}^{n}\times{\rm I\\!R}|\,f(x)\leq\alpha\\}$
is the epigraph of $f$; see [29, Definition 7.1] for more details on the epi-
convergence of a sequence of extended-real-valued functions.

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}.$ (2.1)

The regular/Fréchet normal cone ${\widehat{N}}_{\Omega}(\bar{x})$ to $\Omega$
at $\bar{x}$ is defined by
${\widehat{N}}_{\Omega}(\bar{x})=T_{\Omega}(\bar{x})^{*}$, the polar of the
tangent cone (2.1). 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}}.$

When $f$ is convex, its subdifferential at $\bar{x}$, denoted by $\partial
f(\bar{x})$, is understood in the sense of convex analysis (cf. [24, page
214]), namely $v\in\partial f(\bar{x})$ if $f(x)\geq f(\bar{x})+\langle
v,x-\bar{x}\rangle$ for any $x\in{\rm I\\!R}^{n}$.

As pointed earlier, a proper function $g:{\rm I\\!R}^{m}\to\overline{{\rm
I\\!R}}$ is called polyhedral if ${\rm epi}\,g$ is a polyhedral convex set.
According to [29, Theorem 2.49], this class of convex functions enjoys the
representation

$g(z)=\begin{cases}\max\limits_{j\in J}\big{\\{}\langle
a^{j},z\rangle-\alpha_{j}\big{\\}}\quad&\text{if }z\in{\rm dom}\,g,\\\
\infty&\text{otherwise,}\end{cases}$

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.2)

where $s\in{\rm I\\!N}$, and $b^{i}\in{\rm I\\!R}^{m}$ and $\beta_{i}\in{\rm
I\\!R}$ for all $i\in I$. Thus, we can equivalently express a polyhedral
function $g$ as

$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.3)

It was observed in [14, Proposition 3.2] 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.2) and to the expression of
${\rm dom}\,g$ via the finite union of $C_{j}$’s 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)

These sets allow us to conclude from [14, Proposition 3.3] that the
subdifferential of $g$ at $\bar{z}$ can be calculated as

$\partial g(\bar{z})={\rm co}\,\big{\\{}a^{j}\,\big{|}\,j\in
J(\bar{z})\big{\\}}+{\rm cone}\,\big{\\{}b^{i}\,\big{|}\,i\in
I(\bar{z})\big{\\}},$ (2.5)

which tells us that any ${\bar{\lambda}}\in\partial g(\bar{z})$ can be written
as

${\bar{\lambda}}=\sum_{j\in J(\bar{z})}{\bar{\sigma}}_{j}a^{j}+\sum_{i\in
I(\bar{z})}{\bar{\tau}}_{i}b^{i}\quad\textrm{ with
}\;\;{\bar{\sigma}}_{j},{\bar{\tau}}_{i}\geq 0\;\textrm{ and }\;\sum_{j\in
J(\bar{z})}{\bar{\sigma}}_{j}=1.$ (2.6)

For simplicity, we denote by ${\bar{\sigma}}\in{\rm I\\!R}^{l}$ and
${\bar{\tau}}\in{\rm I\\!R}^{s}$ the vectors with components
${\bar{\sigma}}_{j}$ and ${\bar{\tau}}_{i}$, respectively, where
${\bar{\sigma}}_{j}$ is taken from (2.6) if $j\in J(\bar{z})$ and
${\bar{\sigma}}_{j}=0$ if $j\not\in J(\bar{z})$ and likewise,
${\bar{\tau}}_{i}$ is taken from (2.6) if $i\in I(\bar{z})$ and
${\bar{\tau}}_{i}=0$ if $i\notin I(\bar{z})$. Pick the given representation of
${\bar{\lambda}}$ in (2.6) and define the sets of positive coefficients at
$\bar{z}$ for ${\bar{\sigma}}$ and ${\bar{\tau}}$, respectively, by

$J_{+}(\bar{z},{\bar{\sigma}})=\big{\\{}j\in
J(\bar{z})\,\big{|}\,{\bar{\sigma}}_{j}>0\big{\\}}\;\;\textrm{ and
}\;\;I_{+}(\bar{z},{\bar{\tau}})=\big{\\{}i\in
I(\bar{z})\,\big{|}\,{\bar{\tau}}_{i}>0\big{\\}}.$ (2.7)

Note that the representation of ${\bar{\lambda}}$ in (2.6) is not unique. We
demonstrate in the next result that all these representations of
${\bar{\lambda}}$ enjoy an interesting property, important for our proof of
the reduction lemma in the next section. A similar result was established in
[14, Theorem 3.4] but the neighborhood obtained therein depends on a chosen
decomposition of the subgradient ${\bar{\lambda}}$ in (2.6). Next, we show
that such a neighborhood can be chosen to be independent of a given
representation of ${\bar{\lambda}}$. We also simplify the proof presented in
[14] significantly.

######  Lemma 2.1.

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
there exists $r>0$ such that for any decomposition of ${\bar{\lambda}}$ as
(2.6) and any $(z,\lambda)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$, we have

$J_{+}(\bar{z},{\bar{\sigma}})\subset J(z)\;\;\textrm{ and
}\;\;I_{+}(\bar{z},{\bar{\tau}})\subset I(z).$ (2.8)

[Proof. ]Suppose by contradiction that for each $k\in{\rm I\\!N}$, there are a
decomposition of ${\bar{\lambda}}$ as

${\bar{\lambda}}=\sum_{j\in J(\bar{z})}{\bar{\sigma}}_{j}^{k}a^{j}+\sum_{i\in
I(\bar{z})}{\bar{\tau}}_{i}^{k}b^{i}\;\;\text{ with
}\;\;{\bar{\sigma}}_{j}^{k},{\bar{\tau}}_{i}^{k}\geq 0\;\text{ and
}\;\sum_{j\in J(\bar{z})}{\bar{\sigma}}_{j}^{k}=1,$ (2.9)

and $(z^{k},{\lambda^{k}})\in{\rm gph}\,\partial g$ such that
$(z^{k},{\lambda^{k}})\to(\bar{z},{\bar{\lambda}})$ as $k\to\infty$ with
$J_{+}^{k}\not\subset J(z^{k})$ or $I_{+}^{k}\not\subset I(z^{k})$, where
$J_{+}^{k}:=J_{+}(\bar{z},{\bar{\sigma}}^{k})$ and
$I_{+}^{k}:=I_{+}(\bar{z},{\bar{\tau}}^{k})$ are defined via (2.7). Since
$z^{k}\to\bar{z}$ as $k\to\infty$, the inclusions $J(z^{k})\subset J(\bar{z})$
and $I(z^{k})\subset I(\bar{z})$ hold for all $k$ sufficiently large. Passing
to a subsequence if necessary, we can assume that there exist subsets
$\bar{J}\subset J(\bar{z})$ and $\bar{I}\subset I(\bar{z})$ such that

$J(z^{k})=\bar{J}\quad\text{ and }\quad I(z^{k})=\bar{I}\quad\text{ for all
}k\in{\rm I\\!N},$

which, together with (2.5), lead us to

$\partial g(z^{k})={\rm co}\,\big{\\{}a^{j}|\,j\in\bar{J}\big{\\}}+{\rm
cone}\,\big{\\{}b^{i}|\,i\in\bar{I}\big{\\}}=:\Omega\quad\textrm{ for all
}k\in{\rm I\\!N}.$

Since ${\lambda^{k}}\in\partial g(z^{k})=\Omega$ and
${\lambda^{k}}\to{\bar{\lambda}}$ as $k\to\infty$, we arrive at
${\bar{\lambda}}\in\Omega=\partial g(z^{k})$ for all $k$ sufficiently large.
Fix such a $k\in{\rm I\\!N}$ and deduce from ${\bar{\lambda}}\in\partial
g(z^{k})$ that

$\langle{\bar{\lambda}},\bar{z}-z^{k}\rangle\leq g(\bar{z})-g(z^{k}).$ (2.10)

By the decomposition in (2.9), we obtain

$\displaystyle\langle{\bar{\lambda}},z^{k}-\bar{z}\rangle$
$\displaystyle=\sum_{j\in J(\bar{z})}{\bar{\sigma}}_{j}^{k}\langle
a^{j},z^{k}-\bar{z}\rangle+\sum_{i\in I(\bar{z})}{\bar{\tau}}_{i}^{k}\langle
b^{i},z^{k}-\bar{z}\rangle$ $\displaystyle=\sum_{j\in
J(\bar{z})}{\bar{\sigma}}_{j}^{k}\big{(}\langle
a^{j},z^{k}\rangle-\alpha_{j}-g(\bar{z})\big{)}+\sum_{i\in
I(\bar{z})}{\bar{\tau}}_{i}^{k}\big{(}\langle
b^{i},z^{k}\rangle-\beta_{i}\big{)},$ $\displaystyle\leq\sum_{j\in
J(\bar{z})}{\bar{\sigma}}_{j}^{k}\big{(}g(z^{k})-g(\bar{z})\big{)},$ (2.11)

where the second equality results from (2.4) and the last inequality comes
from the fact that $z^{k}\in{\rm dom}\,g$, combined with (2.2)–(2.3). If
$J_{+}^{k}\not\subset J(z^{k})$, there exists ${j_{0}}\in J_{+}^{k}$ such that
$z^{k}\notin C_{j_{0}}$, meaning that

${\bar{\sigma}}_{j_{0}}^{k}\big{(}\langle
a^{j_{0}},z^{k}\rangle-\alpha_{j_{0}}-g(\bar{z})\big{)}<{\bar{\sigma}}_{j_{0}}^{k}\big{(}g(z^{k})-g(\bar{z})\big{)}.$

If $I_{+}^{k}\not\subset I(z^{k})$, we find ${i_{0}}\in I_{+}^{k}$ such that
$\langle b^{i_{0}},z^{k}\rangle<\beta_{i_{0}}$, which implies that

${\bar{\tau}}_{i_{0}}^{k}\big{(}\langle
b^{i_{0}},z^{k}\rangle-\beta_{i_{0}}\big{)}<0,$

which tells us that in both cases the last inequality in (2) is strict. Thus,
our assumption that either $J_{+}^{k}\not\subset J(z^{k})$ or
$I_{+}^{k}\not\subset I(z^{k})$, together with the last condition in (2.9),
yields

$\langle{\bar{\lambda}},z^{k}-\bar{z}\rangle<\sum_{j\in
J(\bar{z})}{\bar{\sigma}}_{j}^{k}\big{(}g(z^{k})-g(\bar{z})\big{)}=g(z^{k})-g(\bar{z}),$

which contradicts (2.10) and therefore completes the proof.

We finish this section by recording some first-order variational properties of
polyhedral functions, important for our developments in this paper. Recall
from [29, Exercise 6.47] that for any polyhedral convex set $C\subset{\rm
I\\!R}^{n}$ and $\bar{x}\in C$, we can find a neighborhood ${\cal O}$ of
$0\in{\rm I\\!R}^{n}$ for which we have

$T_{C}(\bar{x})\cap{\cal O}=(C-\bar{x})\cap{\cal O}.$ (2.12)

######  Proposition 2.2 (first-order variational properties).

Assume that $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a polyhedral
function and $\bar{z}\in{\rm dom}\,g$. Then the following properties hold.

  * (a)

The domain of the subderivative function ${\rm d}g(\bar{z})$ can be calculated
by

${\rm dom}\,{\rm d}g(\bar{z})=T_{{\rm dom}\,g}(\bar{z})=\bigcup_{j\in
J(\bar{z})}T_{C_{j}}(\bar{z}).$

  * (b)

If $w\in T_{C_{j}}(\bar{z})$ for some $j\in J(\bar{z})$, then we have ${\rm
d}g(\bar{z})(w)=\langle a^{j},w\rangle$. Moreover, there exists $r>0$ such
that any $w\in T_{{\rm dom}\,g}(\bar{z})\cap\mathbb{B}_{r}(0)$, the
representation

$g(\bar{z}+w)=g(\bar{z})+{\rm d}g(\bar{z})(w)$ (2.13)

holds.

[Proof. ]The first equality in (a) was established in [29, Proposition 10.21].
The second equality results immediately from the fact that ${\rm
dom}\,g=\bigcup_{j\in J}C_{j}$. The first claim in (b) can be found again in
[29, Proposition 10.21]. To prove (2.13), recall that for any $j\in
J(\bar{z})$, $C_{j}$ is a polyhedral convex set. Employing (2.12) for these
sets, we can find $r>0$ such that

$T_{C_{j}}(\bar{z})\cap\mathbb{B}_{r}(0)=(C_{j}-\bar{z})\cap\mathbb{B}_{r}(0)\quad\textrm{
for all }\;j\in J(\bar{z}).$

Pick any $w\in T_{{\rm dom}\,g}(\bar{z})\cap\mathbb{B}_{r}(0)$, and conclude
from (a) that $w\in T_{C_{j_{0}}}(\bar{z})\cap\mathbb{B}_{r}(0)$ for some
${j_{0}}\in J(\bar{z})$ and from the first claim in (b) that ${\rm
d}g(\bar{z})(w)=\langle a^{j_{0}},w\rangle$. Thus, we get $\bar{z}+w\in
C_{j_{0}}$, which, together with the definition of $C_{j_{0}}$ and (2.4),
leads us to

$g(\bar{z}+w)=\langle
a^{j_{0}},\bar{z}+w\rangle-\alpha_{j_{0}}=g(\bar{z})+\langle
a^{j_{0}},w\rangle=g(\bar{z})+{\rm d}g(\bar{z})(w),$

and hence completes the proof.

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 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{\\}}.$

If, in addition, $f$ is convex and $\partial f(\bar{x})\neq\emptyset$, it
follows from [29, Theorem 8.30] that its subderivative function is the support
function of $\partial f(\bar{x})$, that is

${\rm d}f(\bar{x})(w)=\sup\big{\\{}\langle v,w\rangle\,\big{|}\,v\in\partial
f(\bar{x})\big{\\}},$

which in turn allows us to equivalently describe the critical cone
${K_{f}}(\bar{x},\bar{v})$ as

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

######  Proposition 2.3.

Assume that $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 the
following properties are equivalent:

  * (a)

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

  * (b)

the critical cone $K_{g}(\bar{z},{\bar{\lambda}})$ is a linear subspace.

[Proof. ]By (2.14), we have ${K_{g}(\bar{z},{\bar{\lambda}})}=N_{\partial
g(\bar{z})}({\bar{\lambda}})$. The equivalence of (a) and $N_{\partial
g(\bar{z})}({\bar{\lambda}})$ being a subspace is a well-known fact from
convex analysis.

The following equivalent description of the critical cone of a polyhedral
function was established in [16, Proposition 3.2].

######  Proposition 2.4 (critical cone of polyhedral functions).

Assume that $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a polyhedral
function and $(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$. If
${\bar{\lambda}}$ has the decomposition in (2.6), then
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}$ if and only if $w$ satisfies the
conditions

$\begin{cases}\langle a^{i}-a^{j},w\rangle=0,\quad&\textrm{for }\;i,j\in
J_{+}(\bar{z},{\bar{\sigma}}),\\\ \langle a^{i}-a^{j},w\rangle\leq
0,&\textrm{for }\;i\in J(\bar{z})\setminus
J_{+}(\bar{z},{\bar{\sigma}})\;\textrm{ and }\;j\in
J_{+}(\bar{z},{\bar{\sigma}}),\\\ \langle b^{i},w\rangle=0,&\textrm{for
}\;i\in I_{+}(\bar{z},{\bar{\tau}}),\\\ \langle b^{i},w\rangle\leq
0,&\textrm{for }\;i\in I(\bar{z})\setminus
I_{+}(\bar{z},{\bar{\tau}}).\end{cases}$

##  3 Reduction Lemma for Polyhedral Functions and its Applications

We begin this section by providing an extension of the reduction lemma for
polyhedral functions. The reduction lemma, established first by Robinson in
[22, Proposition 4.4] for polyhedral convex sets, shows that the graph of the
normal cone to a polyhedral convex set coincides locally with that of the
normal cone to its critical cone. Robinson’s proof of this result relies upon
his sticky face lemma, which was established in [21, Lemma 3.5] with a rather
involved proof. A simpler proof of this result was presented by Dontchev and
Rockafellar in [2, Lemma 2E.4]. Recently, the reduction lemma was extended for
an important class of convex functions, called piecewise linear-quadratic (cf.
[29, Definition 10.20]), by the third author in [30, Theorem 2.3]. This class
of convex functions clearly encompasses polyhedral functions and thus the
result below can be derived from the recent result in [30]. However, the
presented proof in [30] relies upon two major results: 1) Robinson’s reduction
lemma for polyhedral convex sets and 2) the fact that the graph of subgradient
mappings of convex piecewise linear-quadratic functions can be expressed as a
finite union of polyhedral convex sets (see the proof of [29, Theorem
11.14(b)]). Below, we present a direct proof of the reduction lemma for
polyhedral functions, which is solely based on Lemma 2.1.

######  Theorem 3.1 (reduction lemma).

Assume that $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 there
exists $r>0$ such that

$\big{(}({\rm gph}\,\partial
g)-(\bar{z},{\bar{\lambda}})\big{)}\cap\mathbb{B}_{r}(0,0)=\big{(}{\rm
gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}\big{)}\cap\mathbb{B}_{r}(0,0).$ (3.1)

[Proof. ]Suppose that the polyhedral function $g$ has the representation
(2.3). We first show that there is $r>0$ for which the inclusion ‘$\supset$’
in (3.1) holds. To do so, using (2.12) for the polyhedral convex set $\partial
g(\bar{z})$, we find $r_{0}>0$ such that

$T_{\partial
g(\bar{z})}({\bar{\lambda}})\cap\mathbb{B}_{r_{0}}(0)=\big{(}\partial
g(\bar{z})-{\bar{\lambda}}\big{)}\cap\mathbb{B}_{r_{0}}(0).$ (3.2)

Pick now a pair $(w,u)$ from the right-hand side of (3.1) with $r=r_{0}$
therein, which implies that the conditions
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}\cap\mathbb{B}_{r_{0}}(0)$,
$u\in{K_{g}(\bar{z},{\bar{\lambda}})}^{*}\cap\mathbb{B}_{r_{0}}(0)$, and
$\langle u,w\rangle=0$ are satisfied. Moreover, using (2.14) for the
polyhedral function $g$, we get
${K_{g}(\bar{z},{\bar{\lambda}})}^{*}=T_{\partial
g(\bar{z})}({\bar{\lambda}})$. Therefore $u$ belongs to the left-hand side of
(3.2), and thus ${\bar{\lambda}}+u\in\partial g(\bar{z})$. We now show that
$(\bar{z}+w,{\bar{\lambda}}+u)\in{\rm gph}\,\partial g$. To this end, take
$z\in{\rm I\\!R}^{m}$ and observe that

$\langle{\bar{\lambda}}+u,z-(\bar{z}+w)\rangle=\langle{\bar{\lambda}}+u,z-\bar{z}\rangle-\langle{\bar{\lambda}},w\rangle-\langle
u,w\rangle\leq g(z)-g(\bar{z})-{\rm d}g(\bar{z})(w),$ (3.3)

where the last inequality is deduced from the facts that
${\bar{\lambda}}+u\in\partial g(\bar{z})$,
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}$, and $\langle u,w\rangle=0$. Choosing a
smaller radius $r_{0}$ if necessary, we can assume that (2.13) is valid on
$T_{{\rm dom}\,g}(\bar{z})\cap\mathbb{B}_{r_{0}}(0)$. It follows from
Proposition 2.2(a) and
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}\cap\mathbb{B}_{r_{0}}(0)$ that $w\in
T_{{\rm dom}\,g}(\bar{z})\cap\mathbb{B}_{r_{0}}(0)$, which in turn allows us
to conclude via (2.13) that $g(\bar{z})+{\rm d}g(\bar{z})(w)=g(\bar{z}+w)$.
Combining this and (3.3) leads us to

$\langle{\bar{\lambda}}+u,z-(\bar{z}+w)\rangle\leq g(z)-g(\bar{z}+w)$

for any arbitrary $z\in{\rm I\\!R}^{m}$, and thus to
${\bar{\lambda}}+u\in\partial g(\bar{z}+w)$. This proves that $(w,u)$ belongs
to the left-hand side of (3.1) with $r=r_{0}$.

We now proceed with proving the inclusion ‘$\subset$’ in (3.1) for some $r>0$.
Decompose ${\bar{\lambda}}$ into
${\bar{\lambda}}={\bar{\lambda}}_{1}+{\bar{\lambda}}_{2}$ with
${\bar{\lambda}}_{1},{\bar{\lambda}}_{2}$ taken from (2.6). Pick $r_{0}$ from
(3.2) and choose $r\in(0,r_{0}]$ such that the inclusions in (2.8) hold for
all $(z,v)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$. Pick now a pair $(w,v)$
from the left-hand side of (3.1), and conclude that
$(w,u)\in\mathbb{B}_{r}(0,0)$ with ${\bar{\lambda}}+u\in\partial
g(\bar{z}+w)$. We are going to show that $u\in
N_{K_{g}(\bar{z},{\bar{\lambda}})}(w)$, which amounts via [2, Proposition
2A.3] to the conditions

$w\in{K_{g}(\bar{z},{\bar{\lambda}})},\quad
u\in{K_{g}(\bar{z},{\bar{\lambda}})}^{*},\quad\textrm{ and }\quad\langle
u,w\rangle=0.$ (3.4)

Taking a smaller radius $r$ if necessary, we can assume that $\partial
g(\bar{z}+w)\subset\partial g(\bar{z})$ (cf. [14, Proposition 3.3(a)]). Thus,
$u\in\big{(}\partial g(\bar{z})-{\bar{\lambda}}\big{)}\cap\mathbb{B}_{r}(0)$.
Since $r\leq r_{0}$, we deduce from (3.2) that $u\in T_{\partial
g(\bar{z})}({\bar{\lambda}})={K_{g}(\bar{z},{\bar{\lambda}})}^{*}$, which
justifies the second inclusion in (3.4). By shrinking $r$ again if necessary,
we can derive from $(\bar{z}+w,{\bar{\lambda}}+u)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$ and (2.8) that

$J_{+}(\bar{z},{\bar{\sigma}})\subset J(\bar{z}+w)\subset
J(\bar{z})\quad\textrm{ and }\quad I_{+}(\bar{z},{\bar{\tau}})\subset
I(\bar{z}+w)\subset I(\bar{z}).$

To prove that $w\in{K_{g}(\bar{z},{\bar{\lambda}})}$, we use Proposition 2.4
in which an equivalent description of ${K_{g}(\bar{z},{\bar{\lambda}})}$ was
given. We break this task into four cases as follows:

  * (i)

$i,j\in J_{+}(\bar{z},{\bar{\sigma}})$. In this case, we obtain from the
inclusions above that $i,j\in J(\bar{z}+w)\subset J(\bar{z})$. These
inclusions bring us via (2.4) to

$\langle a^{i},\bar{z}\rangle-\alpha_{i}=\langle
a^{j},\bar{z}\rangle-\alpha_{j}\quad\textrm{ and }\quad\langle
a^{i},\bar{z}+w\rangle-\alpha_{i}=\langle a^{j},\bar{z}+w\rangle-\alpha_{j}.$

Combining these confirms that $\langle a^{i}-a^{j},w\rangle=0$ for all $i,j\in
J_{+}(\bar{z},{\bar{\sigma}})$.

  * (ii)

$i\in J(\bar{z})\setminus J_{+}(\bar{z},{\bar{\sigma}})$ and $j\in
J_{+}(\bar{z},{\bar{\sigma}})$. In this case, we arrive at $i,j\in J(\bar{z})$
and $j\in J(\bar{z}+v)$, which imply via (2.4) that

$\langle a^{i},\bar{z}\rangle-\alpha_{i}=\langle
a^{j},\bar{z}\rangle-\alpha_{j}\quad\textrm{ and }\quad\langle
a^{i},\bar{z}+w\rangle-\alpha_{i}\leq\langle
a^{j},\bar{z}+w\rangle-\alpha_{j}.$

Combining these confirms that $\langle a^{i}-a^{j},w\rangle\leq 0$ for all
$i\in J(\bar{z})\setminus J_{+}(\bar{z},{\bar{\sigma}})$ and $j\in
J_{+}(\bar{z},{\bar{\sigma}})$.

  * (iii)

$i\in I_{+}(\bar{z},{\bar{\tau}})$. In this case, we have $i\in I(\bar{z})$
and $i\in I(\bar{z}+w)$, which result in $\langle b^{i},\bar{z}\rangle=\langle
b^{i},\bar{z}+w\rangle=\beta_{i}$. Combining these confirms that $\langle
b^{i},w\rangle=0$ for all $i\in I_{+}(\bar{z},{\bar{\tau}})$.

  * (iv)

$i\in I(\bar{z})\setminus I_{+}(\bar{z},{\bar{\tau}})$. In this case, we
deduce from $\bar{z}+w\in{\rm dom}\,g$ and $i\in I(\bar{z})$ that $\langle
b^{i},\bar{z}+w\rangle\leq\beta_{i}=\langle b^{i},\bar{z}\rangle$, which in
turn yields $\langle b^{i},w\rangle\leq 0$ for all $i\in I(\bar{z})\setminus
I_{+}(\bar{z},{\bar{\tau}})$.

In summary, we showed that $w$ satisfies the equivalent description of
${K_{g}(\bar{z},{\bar{\lambda}})}$ from Proposition 2.4, and so
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}$. It remains to demonstrate that
$\langle w,u\rangle=0$. Recall that ${\bar{\lambda}}+u\in\partial
g(\bar{z}+w)$. Using (2.5), we can express ${\bar{\lambda}}+u$ as

${\bar{\lambda}}+u=\sum_{j\in J(\bar{z}+w)}\sigma_{j}a^{j}+\sum_{i\in
I(\bar{z}+w)}\tau_{i}b^{i}\;\;\textrm{ with }\;\;\sigma_{j},\tau_{i}\geq
0\;\textrm{ and }\;\sum_{j\in J(\bar{z}+w)}\sigma_{j}=1.$

This and the decomposition
${\bar{\lambda}}={\bar{\lambda}}_{1}+{\bar{\lambda}}_{2}$ with
${\bar{\lambda}}_{1},{\bar{\lambda}}_{2}$ taken from (2.6) allow us to
conclude that

$\displaystyle\langle u,w\rangle$
$\displaystyle=\langle{\bar{\lambda}}+u,w\rangle-\langle{\bar{\lambda}},w\rangle$
$\displaystyle=\sum_{j\in J(\bar{z}+w)}(\sigma_{j}-{\bar{\sigma}}_{j})\langle
a^{j},w\rangle+\sum_{i\in I(\bar{z}+w)}(\tau_{i}-{\bar{\tau}}_{i})\langle
b^{i},w\rangle$ $\displaystyle=\sum_{j\in
J(\bar{z}+w)}(\sigma_{j}-{\bar{\sigma}}_{j})\big{[}\langle
a^{j},\bar{z}+w\rangle-\alpha_{j}-(\langle
a^{j},\bar{z}\rangle-\alpha_{j})\big{]}+\sum_{i\in
I(\bar{z}+w)}(\tau_{i}-{\bar{\tau}}_{i})\big{[}\langle
b^{i},\bar{z}+w\rangle-\langle b^{i},\bar{z}\rangle\big{]}$
$\displaystyle=\big{(}g(\bar{z}+w)-g(\bar{z})\big{)}\sum_{j\in
J(\bar{z}+w)}(\sigma_{j}-{\bar{\sigma}}_{j})+\sum_{i\in
I(\bar{z}+w)}(\tau_{i}-{\bar{\tau}}_{i})(\beta_{i}-\beta_{i})$
$\displaystyle=0,$

where the second equality results from the inclusions
$J_{+}(\bar{z},{\bar{\sigma}})\subset J(\bar{z}+w)$ and
$I_{+}(\bar{z},{\bar{\tau}})\subset I(\bar{z}+w)$, where the fourth equality
comes from the definitions of the active index sets $J(\bar{z}+w)$ and
$I(\bar{z}+w)$ as well as the inclusions $J(\bar{z}+w)\subset J(\bar{z})$ and
$I(\bar{z}+w)\subset I(\bar{z})$, and where the last equality follows from the
assumption on $\sigma_{j}$ and ${\bar{\sigma}}_{j}$. This proves the inclusion
‘$\subset$’ in (3.1) for some $r>0$ and thus completes the proof.

The rest of this section will be devoted to presenting several important
consequences of Theorem 3.1 for different second-order variational
constructions of polyhedral functions. We begin with a duality relation
between critical cones of a polyhedral function and its (Fenchel) conjugate in
the sense of convex analysis. Both results in the following corollary were
observed by Rockafellar in [28, equations (3.23) & (3.29)]. Since an explicit
proof was not presented for (3.5) in [28] and since this result plays an
important role in strict twice epi-differentiability of polyhedral functions
in the next section, we supply a short proof for readers’ convenience. Let us
recall an important result, used in the proof of next corollary, saying that
the conjugate function $g^{*}$ of a polyhedral function $g$ is again a
polyhedral function, cf. [29, Theorem 11.14(a)].

######  Corollary 3.2 (polar relation of critical cones).

Assume that $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
${K_{g}(\bar{z},{\bar{\lambda}})}$ enjoys the duality relationship

${K_{g}(\bar{z},{\bar{\lambda}})}=K_{g^{*}}({\bar{\lambda}},\bar{z})^{*}.$
(3.5)

Consequently, we have

${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})\;\textrm{ if and only if
}\;\bar{z}\in{\rm ri}\,\partial g^{*}({\bar{\lambda}}).$ (3.6)

[Proof. ]Let $r>0$ be such that (3.1) holds. Then, we conclude from (2.14)
that

$\displaystyle w\in{K_{g}(\bar{z},{\bar{\lambda}})}\;$
$\displaystyle\Longleftrightarrow\;(w,0)\in{\rm
gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}$
$\displaystyle\Longleftrightarrow\;\exists\,r^{\prime}>0:t(w,0)\in\big{(}{\rm
gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}\big{)}\cap\mathbb{B}_{r}(0,0)\;\;\textrm{
for all }\;t\in[0,r^{\prime})$
$\displaystyle\Longleftrightarrow\;\exists\,r^{\prime}>0:(\bar{z}+tw,{\bar{\lambda}})\in\big{(}{\rm
gph}\,\partial g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})\;\;\textrm{
for all }\;t\in[0,r^{\prime})$
$\displaystyle\Longleftrightarrow\;\exists\,r^{\prime}>0:{\bar{\lambda}}\in\partial
g(\bar{z}+tw)\;\;\textrm{ for all }\;t\in[0,r^{\prime})$
$\displaystyle\Longleftrightarrow\;\exists\,r^{\prime}>0:\bar{z}+tw\in\partial
g^{*}({\bar{\lambda}})\;\;\textrm{ for all }\;t\in[0,r^{\prime})$
$\displaystyle\Longleftrightarrow\;w\in T_{\partial
g^{*}({\bar{\lambda}})}(\bar{z})=\big{(}N_{\partial
g^{*}({\bar{\lambda}})}(\bar{z})\big{)}^{*}=K_{g^{*}}({\bar{\lambda}},\bar{z})^{*},$

where the third equivalence follows from (3.1) and the last equivalence relies
on the polyhedrality of $\partial g^{*}({\bar{\lambda}})$. To justify (3.6),
it follows from Proposition 2.3 that ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a
linear subspace if and only if ${\bar{\lambda}}\in{\rm ri}\,\partial
g(\bar{z})$. A similar observation can be made for
$K_{g^{*}}({\bar{\lambda}},\bar{z})$, which together with (3.5) completes the
proof of (3.6).

We proceed to characterize critical cones of polyhedral functions for points
nearby a given point in the graph of their subgradient mappings. Such a result
for polyhedral convex sets can be found in [2, Lemma 4H.2]. Recall that a
closed face $F$ of a polyhedral convex cone $C\subset{\rm I\\!R}^{d}$ is
defined by

$F=C\cap[v]^{\perp}\quad\mbox{for some}\;\;v\in C^{*}.$

######  Proposition 3.3.

Assume that $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 there
exists $r>0$ such that for all $(z,\lambda)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$ the corresponding
critical cone ${K_{g}(z,\lambda)}$ enjoys the following representation

${K_{g}(z,\lambda)}=F_{1}-F_{2},$

for some faces $F_{1},F_{2}$ of ${K_{g}(\bar{z},{\bar{\lambda}})}$ with
$F_{2}\subset F_{1}$. Conversely, for any pair of faces $F_{1},F_{2}$ of
${K_{g}(\bar{z},{\bar{\lambda}})}$ with $F_{2}\subset F_{1}$ and any
sufficiently small real number $r>0$, there exists $(z,\lambda)\in\big{(}{\rm
gph}\,\partial g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$ with
${K_{g}(z,\lambda)}=F_{1}-F_{2}$.

[Proof. ]Let $r>0$ be such that (3.1) holds. Choosing a smaller radius $r$ if
necessary, we can assume without loss of generality that the inclusions
$\partial g(z)\subset\partial g(\bar{z})$ and $N_{\partial
g(\bar{z})}(\lambda)\subset N_{\partial g(\bar{z})}({\bar{\lambda}})$ hold for
any $(z,\lambda)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$, which can be guaranteed
by $g$ being a polyhedral function. We first show that for any
$(z,\lambda)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$, we have

${K_{g}(z,\lambda)}={K_{g}(\bar{z},{\bar{\lambda}})}\cap[\lambda-{\bar{\lambda}}]^{\perp}+[z-\bar{z}].$
(3.7)

To this end, pick $(z,\lambda)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$ and observe that the
inclusion

$N_{\partial g(z)}(\lambda)\subset N_{\partial g(z)}({\bar{\lambda}})$ (3.8)

holds. To justify it, it is not hard to see $\partial g(z)=\partial
g(\bar{z})\cap D$ with $D:=\\{v\in{\rm I\\!R}^{m}|\,\langle
v,z-\bar{z}\rangle=g(z)-g(\bar{z})\\}$. It follows from $\lambda\in\partial
g(z)\subset D$ and $\lambda-{\bar{\lambda}}\in
N_{K_{g}(\bar{z},{\bar{\lambda}})}(z-\bar{z})$ that ${\bar{\lambda}}\in D$.
This, together with the definition of $D$, leads us to
$N_{D}(\lambda)=N_{D}({\bar{\lambda}})=[z-\bar{z}]$. Since both $\partial
g(\bar{z})$ and $D$ are polyhedral, we conclude from the intersection rule for
normal cones, holding without any constraint qualification for polyhedral
convex sets, that

$\displaystyle N_{\partial g(z)}(\lambda)$ $\displaystyle=$ $\displaystyle
N_{\partial g(\bar{z})\cap D}(\lambda)=N_{\partial
g(\bar{z})}(\lambda)+N_{D}(\lambda)$ $\displaystyle\subset$ $\displaystyle
N_{\partial g(\bar{z})}({\bar{\lambda}})+N_{D}({\bar{\lambda}})=N_{\partial
g(\bar{z})\cap D}({\bar{\lambda}})=N_{\partial g(z)}({\bar{\lambda}}),$

proving our claimed inclusion. Since $g^{*}$ is a polyhedral function as well,
using Lemma 2.1 for $g^{*}$ at $({\bar{\lambda}},\bar{z})\in{\rm
gph}\,\partial g^{*}$ and shrinking $r$, if necessary, ensure that
$\bar{z}\in\partial g^{*}(\lambda)$. Moreover, it results from (3.8) that
$N_{\partial g^{*}(\lambda)}(z)\subset N_{\partial g^{*}(\lambda)}(\bar{z})$,
which in combination with (2.14) leads us to

$K_{g^{*}}(\lambda,z)=N_{\partial g^{*}(\lambda)}(z)=N_{\partial
g^{*}(\lambda)}(\bar{z})\cap[z-\bar{z}]^{\perp}=K_{g^{*}}(\lambda,\bar{z})\cap[z-\bar{z}]^{\perp}.$

Using this and (3.5) brings us to

${K_{g}(z,\lambda)}=K_{g^{*}}(\lambda,z)^{*}=\big{(}K_{g^{*}}(\lambda,\bar{z})\cap[z-\bar{z}]^{\perp}\big{)}^{*}=K_{g}(\bar{z},\lambda)+[z-\bar{z}].$
(3.9)

Similarly, by (2.14) and the definition of the normal cone to the polyhedral
convex set $\partial g(\bar{z})$, we obtain

$K_{g}(\bar{z},\lambda)=N_{\partial g(\bar{z})}(\lambda)=N_{\partial
g(\bar{z})}({\bar{\lambda}})\cap[\lambda-{\bar{\lambda}}]^{\perp}={K_{g}(\bar{z},{\bar{\lambda}})}\cap[\lambda-{\bar{\lambda}}]^{\perp},$

which, together with (3.9), proves (3.7).

After these preparations, we are in a position to justify the claimed
descriptions of critical cones of $g$. Pick $(z,\lambda)\in\big{(}{\rm
gph}\,\partial g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$ and set
$F_{1}:={K_{g}(\bar{z},{\bar{\lambda}})}\cap[\lambda-{\bar{\lambda}}]^{\perp}$,
which is clearly a face of ${K_{g}(\bar{z},{\bar{\lambda}})}$. Because
$\lambda-{\bar{\lambda}}\in N_{K_{g}(\bar{z},{\bar{\lambda}})}(z-\bar{z})$,
resulting from (3.1), we conclude that $z-\bar{z}\in F_{1}$. Since the
relative interiors of nonempty faces of $F_{1}$ form a partition of this set
(cf. [24, Theorem 18.2]), we find a face of $F_{1}$, denoted by $F_{2}$, that
$z-\bar{z}\in{\rm ri}\,F_{2}$. This tells us that $F_{2}\subset F_{1}$.
Moreover, $F_{2}$ is a face of ${K_{g}(\bar{z},{\bar{\lambda}})}$ as well. By
(3.7), the inclusion ${K_{g}(z,\lambda)}\subset F_{1}-F_{2}$ clearly holds. To
get the opposite inclusion, pick $x_{i}\in F_{i}$ for $i=1,2$. It follows from
$z-\bar{z}\in{\rm ri}\,F_{2}$ and [24, Theorem 6.4] that there is $t>0$ such
that $(1+t)(z-\bar{z})-tx_{2}\in F_{2}\subset F_{1}$, which yields

$t(x_{1}-x_{2})=tx_{1}+(1+t)(z-\bar{z})-tx_{2}-(1+t)(z-\bar{z})\in
F_{1}+[z-\bar{z}],$ (3.10)

which confirms via (3.7) that the inclusion
$F_{1}-F_{2}\subset{K_{g}(z,\lambda)}$ holds. This shows that
${K_{g}(z,\lambda)}=F_{1}-F_{2}$.

Assume now that $F_{1}$ and $F_{2}$ are faces of
${K_{g}(\bar{z},{\bar{\lambda}})}$ with $F_{2}\subset F_{1}$. Pick $r>0$ from
Theorem 3.1 and choose $u\in{K_{g}(\bar{z},{\bar{\lambda}})}^{*}$ with
$\|u\|<r/2$ such that $F_{1}={K_{g}(\bar{z},{\bar{\lambda}})}\cap[u]^{\perp}$.
Since
$u\in{K_{g}(\bar{z},{\bar{\lambda}})}^{*}=N_{K_{g}(\bar{z},{\bar{\lambda}})}(0)$,
it follows from Theorem 3.1 that ${\bar{\lambda}}+u\in\partial g(\bar{z})$.
Pick now $w\in{\rm ri}\,F_{2}$ with $\|w\|<r/2$ and observe from $w\in F_{1}$
that $(w,u)\in{\rm gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}$. By Theorem 3.1,
we arrive at $(\bar{z}+w,{\bar{\lambda}}+u)\in{\rm gph}\,\partial g$. Since
$w\in{\rm ri}\,F_{2}$, as in (3.10), we can show that $F_{1}-F_{2}=F_{1}+[w]$.
Employing this and (3.7) leads us to

$F_{1}-F_{2}=F_{1}+[w]={K_{g}(\bar{z},{\bar{\lambda}})}\cap[u]^{\perp}+[w]=K_{g}(\bar{z}+w,{\bar{\lambda}}+u),$

which completes the proof.

######  Corollary 3.4.

For a polyhedral function $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ and
$(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$, the following properties
hold.

  * (a)

There exists $r>0$ such that for all $(z,\lambda)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$ the following inclusions
hold:

$\displaystyle{K_{g}(z,\lambda)}\subset{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})},$
(3.11a)
$\displaystyle{K_{g}(\bar{z},{\bar{\lambda}})}\cap-{K_{g}(\bar{z},{\bar{\lambda}})}\subset{K_{g}(z,\lambda)}.$
(3.11b)

  * (b)

If, in addition, ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$, then there
exists $r>0$ such that for all $(z,\lambda)\in\big{(}{\rm gph}\,\partial
g\big{)}\cap\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})$, we have $\lambda\in{\rm
ri}\,\partial g(z)$ and

${K_{g}(z,\lambda)}={K_{g}(\bar{z},{\bar{\lambda}})}.$ (3.12)

[Proof. ]The inclusion in (3.11a) for any $(z,\lambda)\in{\rm gph}\,\partial
g$ sufficiently close to $(\bar{z},{\bar{\lambda}})$ falls directly from
Proposition 3.3. Also, according to Proposition 3.3, for any such
$(z,\lambda)\in{\rm gph}\,\partial g$, one can find some faces $F_{1},F_{2}$
of ${K_{g}(\bar{z},{\bar{\lambda}})}$ with $F_{2}\subset F_{1}$ such that
$K_{g}(z,\lambda)=F_{1}-F_{2}$. Since
${K_{g}(\bar{z},{\bar{\lambda}})}\cap-{K_{g}(\bar{z},{\bar{\lambda}})}$ is the
smallest face of ${K_{g}(\bar{z},{\bar{\lambda}})}$, we get
${K_{g}(\bar{z},{\bar{\lambda}})}\cap-{K_{g}(\bar{z},{\bar{\lambda}})}\subset
F_{i}$ for $i=1,2$, which in turn justify the inclusion in (3.11b) for all
$(z,\lambda)\in{\rm gph}\,\partial g$ sufficiently close to
$(\bar{z},{\bar{\lambda}})$.

To justify (b), it follows from ${\bar{\lambda}}\in{\rm ri}\,\partial
g(\bar{z})$ and Proposition 2.3 that ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a
linear subspace. This and the inclusions (3.11a) and (3.11b) tell us that

${K_{g}(\bar{z},{\bar{\lambda}})}={K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}\supset{K_{g}(z,\lambda)}\supset{K_{g}(\bar{z},{\bar{\lambda}})}\cap-{K_{g}(\bar{z},{\bar{\lambda}})}={K_{g}(\bar{z},{\bar{\lambda}})}$

for all $(z,\lambda)\in{\rm gph}\,\partial g$ sufficiently close to
$(\bar{z},{\bar{\lambda}})$, which in turn confirms that ${K_{g}(z,\lambda)}$
is a linear subspace. Using Proposition 2.3 again, we have $\lambda\in{\rm
ri}\,\partial g(z)$ and hence complete the proof of (b).

Both inclusions in Corollary 3.4(a) were perviously established in [2,
Proposition 2E.10] for polyhedral convex sets without appealing to the
reduction lemma, an important tool used in our proof. Note that while the
observation in Corollary 3.4(b) is a simple and direct consequence of the
inclusions (3.11a)-(3.11b), it plays an indispensable role in the next two
sections in which we are going to study strict twice epi-differentiability of
polyhedral functions. In fact, this result reveals that when we are converging
in the graph of subgradient mappings of polyhedral functions to a given point
therein under the extra relative interior condition, all those points, used in
this convergence, enjoy this relative interior condition. This has a major
implication for second-order variational constructions such as limiting
coderivatives and strict subgradient graphical derivatives; see Theorem 3.5(c)
and Theorem 3.6(c).

We proceed with two other important applications of the established reduction
lemma for polyhedral functions in calculating the proto-derivative and
coderivative of subgradient mappings of this class of functions. To this end,
consider a set-valued mapping $F:{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{m}$. According to [29, Definition 8.33], the graphical derivative of
$F$ at $\bar{x}$ for $\bar{y}$ with $(\bar{x},\bar{y})\in{\rm gph}\,F$ is the
set-valued mapping $DF(\bar{x},\bar{y}):{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{m}$ defined via the tangent cone to ${\rm gph}\,F$ at
$(\bar{x},\bar{y})$ by

$u\in DF(\bar{x},\bar{y})(w)\;\Longleftrightarrow\;(w,u)\in T_{{\rm
gph}\,F}(\bar{x},\bar{y}),$

or, equivalently, ${\rm gph}\,DF(\bar{x},\bar{y})=T_{{\rm
gph}\,F}(\bar{x},\bar{y})$. Using the definition of the tangent cone, we can
present an alternative definition of $DF(\bar{x},\bar{y})$ in terms of
graphical limits as

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

The set-valued mapping $F$ is said to be proto-differentiable at $\bar{x}$ for
$\bar{y}$ if the outer graphical limit in (3.13) is actually a full limit. If
$F$ is proto-differentiable at $\bar{x}$ for $\bar{y}$, its graphical
derivative $DF(\bar{x},\bar{y})$ is called the proto-derivative of $F$ at
$\bar{x}$ for $\bar{y}$. 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 [29, Definition 9.53] that the strict graphical
derivative of a set-valued mapping $F$ at $\bar{x}$ for $\bar{y}$ with
$(\bar{x},\bar{y})\in{\rm gph}\,F$, 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.14)

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.14) is a full
limit. When $F$ is strictly proto-differentiable at $\bar{x}$ for $\bar{y}$,
its strict graphical derivative $D_{*}F(\bar{x},\bar{y})$ is called the strict
proto-derivative of $F$ at $\bar{x}$ for $\bar{y}$. To elaborate more, 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}.$ (3.15)

The strict proto-differentiability of $F$ at $\bar{x}$ for $\bar{y}$ amounts
to saying that $\widehat{T}_{{\rm
gph}\,F}(\bar{x},\bar{y})=\widetilde{T}_{{\rm gph}\,F}(\bar{x},\bar{y})$.
Observe also that since the inclusions $\widehat{T}_{{\rm
gph}\,F}(\bar{x},\bar{y})\subset T_{{\rm
gph}\,F}(\bar{x},\bar{y})\subset\widetilde{T}_{{\rm gph}\,F}(\bar{x},\bar{y})$
always hold, strict proto-differentiability of $F$ at $\bar{x}$ for $\bar{y}$
implies that its proto-derivative and strict proto-derivative coincide, namely
we have

$D_{*}F(\bar{x},\bar{y})=DF(\bar{x},\bar{y}).$ (3.16)

Strict proto-differentiability of a set-valued mapping has far-reaching
consequences. In fact, it allows us to evaluate the strict proto-derivative of
a set-valued mapping, which can be utilized to characterize its strong metric
regularity; see [2, Theorem 4D.1] and Section 5 for more details on this
application. The intriguing question is whether strict proto-differentiability
holds for any class of set-valued mappings, important for constrained and
composite optimization problems. In the next theorem, we are going to show
that subgradient mappings of polyhedral functions enjoy this property when a
relative interior condition is satisfied for subgradients under consideration.
Furthermore, we will prove that such a relative interior condition, indeed,
characterizes strict proto-differentiability of these set-valued mappings.
While it is not easy to study strict proto-differentiability of set-valued
mappings, its weaker version, namely proto-differentiability, has been well
understood for many important classes of functions that are important for
various applications; see [27, 12, 13, 29] for more details and examples. In
particular, it is well-known (cf. [29, Corollary 13.41] ) that subgradient
mappings of polyhedral functions are always proto-differentiable.

######  Theorem 3.5.

For a polyhedral function $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ and
$(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$, the following properties
hold.

  * (a)

The graphical derivative of $\partial g$ at $\bar{z}$ for ${\bar{\lambda}}$
can be obtained by

${\rm gph}\,D(\partial g)(\bar{z},{\bar{\lambda}})=T_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})={\rm gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}.$
(3.17)

  * (b)

The strict graphical derivative of $\partial g$ at $\bar{z}$ for
${\bar{\lambda}}$ can be obtained by***This formula was brought to our
attention by a reviewer.

${\rm gph}\,D_{*}(\partial g)(\bar{z},{\bar{\lambda}})={\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}-{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}.$ (3.18)

  * (c)

The condition ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$ amounts to the
existence of a neighborhood $O$ of $(\bar{z},{\bar{\lambda}})$ such that for
any $(z,\lambda)\in O\cap{\rm gph}\,\partial g$, $\partial g$ is strictly
proto-differentiable at $z$ for $\lambda$ and its proto-derivative and strict
proto-derivative coincide, namely

$D_{*}(\partial g)(z,\lambda)=D(\partial g)(z,\lambda).$ (3.19)

[Proof. ]Observe that the first equality in (3.17) is the definition of
graphical derivative. Using the equality (3.1) and the definition of the
tangent cone to ${\rm gph}\,\partial g$ at $(\bar{z},{\bar{\lambda}})$, we
immediately arrive at the second equality in (3.17).

To justify (b), we conclude from Theorem 3.1 and [2, Proposition 4H.10],
respectively, that

$\widetilde{T}_{{\rm gph}\,\partial g}(\bar{z},{\bar{\lambda}})={\rm
gph}\,D_{*}(\partial g)(\bar{z},{\bar{\lambda}})={\rm
gph}\,D_{*}N_{{K_{g}(\bar{z},{\bar{\lambda}})}}(0,0)={\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}-{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}.$ (3.20)

Finally, we proceed with the proof of (c). Suppose that
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$. By Corollary 3.4(b), we
find $r>0$ such that for any
$(z,\lambda)\in\mathbb{B}_{r}(\bar{z},{\bar{\lambda}})\cap{\rm gph}\,\partial
g$, the property $K_{g}(z,\lambda)={K_{g}(\bar{z},{\bar{\lambda}})}$ holds.
Take any such a pair $(z,\lambda)$ and conclude from part (a) that

$T_{{\rm gph}\,\partial g}(z,\lambda)={\rm gph}\,N_{K_{g}(z,\lambda)}={\rm
gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}.$

It follows then from [29, Theorem 6.26] that

$\widehat{T}_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})=\liminf_{(z,\lambda)\xrightarrow{{\rm
gph}\,\partial g}(\bar{z},{\bar{\lambda}})}T_{{\rm gph}\,\partial
g}(z,\lambda)={\rm gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}.$

Since ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$, we conclude that
${\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}={K_{g}(\bar{z},{\bar{\lambda}})}\times{K_{g}(\bar{z},{\bar{\lambda}})}^{\perp}$
is a linear subspace. These, coupled with (3.20), lead us to
$\widehat{T}_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})=\widetilde{T}_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})$, meaning that $\partial g$ is strictly proto-
differentiable at $\bar{z}$ for ${\bar{\lambda}}$. To achieve a similar
conclusion for any pair $(z,\lambda)\in{\rm gph}\,\partial g$ sufficiently
close to $(\bar{z},{\bar{\lambda}})$, observe from Corollary 3.4(b) that for
any such a pair, we have $\lambda\in{\rm ri}\,\partial g(z)$. A similar
argument as the one presented above for $(\bar{z},{\bar{\lambda}})$, shows
that $\partial g$ is strictly proto-differentiable at $z$ for $\lambda$
whenever $(z,\lambda)\in{\rm gph}\,\partial g$ is sufficiently close to
$(\bar{z},{\bar{\lambda}})$. Finally, (3.19) results from (3.16). Conversely,
if $\partial g$ is strictly proto-differentiable at $\bar{z}$ for
${\bar{\lambda}}$, our discussion prior to (3.16) implies that

${\rm gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}=T_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})=\widetilde{T}_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})={\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}-{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}},$

where the last equality results from (3.20). This clearly tells us that
${K_{g}(\bar{z},{\bar{\lambda}})}$ is a linear subspace and hence it follows
from Proposition 2.3 that ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$,
which completes the proof.

We continue with one more direct application of the reduction lemma for
polyhedral functions in finding the regular and limiting normal cones to ${\rm
gph}\,\partial g$.

######  Theorem 3.6 (regularity of subgradient mappings of polyhedral
functions).

For a polyhedral function $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ and
$(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$, the following properties
hold.

  * (a)

The regular normal cone to ${\rm gph}\,\partial g$ at
$(\bar{z},{\bar{\lambda}})$ can be calculated by

${\widehat{N}}_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})={K_{g}(\bar{z},{\bar{\lambda}})}^{*}\times{K_{g}(\bar{z},{\bar{\lambda}})}.$
(3.21)

  * (b)

The (limiting) normal cone to ${\rm gph}\,\partial g$ at
$(\bar{z},{\bar{\lambda}})$ can be calculated by

$N_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})=\bigcup_{\begin{subarray}{c}F_{1},F_{2}\subset\mathcal{F}_{K_{g}(\bar{z},{\bar{\lambda}})}\\\
F_{2}\subset F_{1}\end{subarray}}(F_{1}-F_{2})^{*}\times(F_{1}-F_{2}),$ (3.22)

where $\mathcal{F}_{K_{g}(\bar{z},{\bar{\lambda}})}$ is the collection of all
faces of ${K_{g}(\bar{z},{\bar{\lambda}})}$.

  * (c)

The condition ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$ is equivalent
to

$N_{{\rm gph}\,\partial g}(\bar{z},{\bar{\lambda}})={\widehat{N}}_{{\rm
gph}\,\partial g}(\bar{z},{\bar{\lambda}}).$ (3.23)

[Proof. ]We begin with the proof of (a). It follows from Theorem 3.1 that
${\rm gph}\,\partial g-(\bar{z},{\bar{\lambda}})$ and ${\rm
gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}$ coincide locally around $(0,0)$,
which leads us via the definition of the regular normal cone to

${\widehat{N}}_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})={\widehat{N}}_{{\rm gph}\,\partial
g-(\bar{z},{\bar{\lambda}})}(0,0)={\widehat{N}}_{{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}}(0,0).$

Since ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a polyhedral convex set, it
results from [2, page 264] that

${\widehat{N}}_{{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}}(0,0)=K_{{K_{g}(\bar{z},{\bar{\lambda}})}}(0,0)^{*}\times
K_{{K_{g}(\bar{z},{\bar{\lambda}})}}(0,0)={K_{g}(\bar{z},{\bar{\lambda}})}^{*}\times{K_{g}(\bar{z},{\bar{\lambda}})}.$

Combining these proves (a).

To justify (b), observe that $(u,w)\in N_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})$ if and only if there are sequences
$(z^{k},\lambda^{k})\to(\bar{z},{\bar{\lambda}})$ with
$(z^{k},\lambda^{k})\in{\rm gph}\,\partial g$ and $(u^{k},w^{k})\to(u,w)$ with
$(u^{k},w^{k})\in{\widehat{N}}_{{\rm gph}\,\partial g}(z^{k},\lambda^{k})$.
Using the definition of the regular normal cone and (3.1), we conclude for any
$k$ sufficiently large that

$\displaystyle(u^{k},w^{k})\in{\widehat{N}}_{{\rm gph}\,\partial
g}(z^{k},\lambda^{k})$ $\displaystyle\iff$
$\displaystyle(u^{k},w^{k})\in{\widehat{N}}_{{\rm gph}\,\partial
g-(\bar{z},{\bar{\lambda}})}(z^{k}-\bar{z},\lambda^{k}-{\bar{\lambda}})$
$\displaystyle\iff$ $\displaystyle(u^{k},w^{k})\in{\widehat{N}}_{{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}}(z^{k}-\bar{z},\lambda^{k}-{\bar{\lambda}}).$

By the definition of the limiting normal cone, we conclude from the last
inclusion that $(u,w)\in N_{{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}}(0,0)$ and thus get the inclusion
$N_{{\rm gph}\,\partial g}(\bar{z},{\bar{\lambda}})\subset N_{{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}}(0,0)$. A similar argument via
(3.1) can be used to justify the opposite inclusion and obtain

$N_{{\rm gph}\,\partial g}(\bar{z},{\bar{\lambda}})=N_{{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}}(0,0).$

Recall that ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a polyhedral convex cone.
Employing the representation of the limiting normal cone to the normal cone to
the graph of a polyhedral convex set, obtained in the proof of [3, Theorem 2],
we arrive at the representation on the right-hand side of (3.22) for $N_{{\rm
gph}\,N_{{K_{g}(\bar{z},{\bar{\lambda}})}}}(0,0)$, which completes the proof
of (b).

To prove (c), observe that it follows from ${\bar{\lambda}}\in{\rm
ri}\,\partial g(\bar{z})$ and Corollary 3.4(b) that there exists a
neighborhood $O$ of $(\bar{z},{\bar{\lambda}})$ such that for any
$(z,\lambda)\in O\cap{\rm gph}\,\partial g$, we have
$K_{g}(z,\lambda)={K_{g}(\bar{z},{\bar{\lambda}})}$. This and (3.21) bring us
to

${\widehat{N}}_{{\rm gph}\,\partial g}(z,\lambda)={\widehat{N}}_{{\rm
gph}\,\partial g}(\bar{z},{\bar{\lambda}})\quad\mbox{for
all}\;\;(z,\lambda)\in O\cap{\rm gph}\,\partial g,$ (3.24)

which, together with the definition of the limiting normal cone, justifies the
claimed equality in (3.23). Conversely, suppose that (3.23) holds. We are
going to show that ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a linear subspace. To
this end, it suffices to show that if $w\in{K_{g}(\bar{z},{\bar{\lambda}})}$,
then $-w\in{K_{g}(\bar{z},{\bar{\lambda}})}$. Pick
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}$ and conclude from (3.17) that there is
$u\in{\rm I\\!R}^{m}$ such that $(w,u)\in T_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})$. Appealing now to [29, Theorem 13.57] implies
that $(u,-w)\in N_{{\rm gph}\,\partial g}(\bar{z},{\bar{\lambda}})$. This,
together with (3.23) and (3.21), tells us that
$-w\in{K_{g}(\bar{z},{\bar{\lambda}})}$. Remember that
${K_{g}(\bar{z},{\bar{\lambda}})}=N_{\partial g(\bar{z})}({\bar{\lambda}})$.
Since ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a linear subspace, we arrive at
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$, which completes the proof
of (c).  The description (3.21) of the regular normal cone to ${\rm
gph}\,\partial g$ in terms of the critical cone of $g$ was established in [14,
Theorem 4.3(i)] using a different approach. Our current proof relies upon the
reduction lemma, which allows us to simplify the proof of this result. We
should mention that a similar result was established for polyhedral convex
sets using Robinson’s reduction lemma for polyhedral convex sets in the proof
of [3, Theorem 2]. A similar expression of the limiting normal cone to ${\rm
gph}\,\partial g$ was achieved in [14, Theorem 5.1] via a lengthy direct
argument. Our proof, which heavily uses Theorem 3.1, reduces the calculation
to the case of a polyhedral convex cone and then utilizes the available result
for this setting. Thus, Theorem 3.6 can be considered as a generalization of
Dontchev and Rockafellar’s result, obtained in [3, Theorem 2], for polyhedral
convex sets. Note that part (c) of Theorem 3.6 offers a new piece of
information about ${\rm gph}\,\partial g$, which has not been observed before
to the best of our knowledge. Indeed, it tells us that ${\rm gph}\,\partial g$
is regular at $(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$ in the sense
of [29, Definition 6.4] if and only if the subgradient ${\bar{\lambda}}$ is
taken from the relative interior of $\partial g(\bar{z})$.

Recall that for a polyhedral function $g$ with
$(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$, the coderivative mapping
of $\partial g$ at $\bar{z}$ for ${\bar{\lambda}}$, denoted $D^{*}(\partial
g)(\bar{z},{\bar{\lambda}})$, is defined by

$u\in D^{*}(\partial g)(\bar{z},{\bar{\lambda}})(w)\iff(u,-w)\in N_{{\rm
gph}\,\partial g}(\bar{z},{\bar{\lambda}}).$

It is well-known (cf. [29, Theorem 13.57]) that the inclusion $D(\partial
g)(\bar{z},{\bar{\lambda}})(w)\subset D^{*}(\partial
g)(\bar{z},{\bar{\lambda}})(w)$, for any $w\in{\rm I\\!R}^{m}$, always holds
for a polyhedral function $g$. Below, we show that this inclusion becomes
equality provided that the subgradient ${\bar{\lambda}}$ is taken from the
relative interior of $\partial g(\bar{z})$.

######  Corollary 3.7.

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
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$ if and only if

$D(\partial g)(\bar{z},{\bar{\lambda}})(w)=D^{*}(\partial
g)(\bar{z},{\bar{\lambda}})(w)\quad\mbox{ for all}\;\;w\in{\rm I\\!R}^{m}.$
(3.25)

[Proof. ]Suppose that ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$. Thus
the critical cone ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a linear subspace. By
Theorem 3.5(a), we have $T_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})={\rm
gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}={K_{g}(\bar{z},{\bar{\lambda}})}\times{K_{g}(\bar{z},{\bar{\lambda}})}^{\perp}$.
Moreover, we conclude from Theorem 3.6(c) that $N_{{\rm gph}\,\partial
g}(\bar{z},{\bar{\lambda}})={K_{g}(\bar{z},{\bar{\lambda}})}^{\perp}\times{K_{g}(\bar{z},{\bar{\lambda}})}$.
Combining these with the definitions of coderivative and proto-derivative
justifies (3.25).

Assume now that (3.25) holds. We are going to show that
${K_{g}(\bar{z},{\bar{\lambda}})}$ is a linear subspace. To this end, it
suffices to show that if $w\in{K_{g}(\bar{z},{\bar{\lambda}})}$, then
$-w\in{K_{g}(\bar{z},{\bar{\lambda}})}$. Pick
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}$ and conclude from (3.17) that there is
$u\in{\rm I\\!R}^{m}$ such that $u\in D(\partial
g)(\bar{z},{\bar{\lambda}})(w)=N_{K_{g}(\bar{z},{\bar{\lambda}})}(w)$, which
yields that
$(w,u)\in{K_{g}(\bar{z},{\bar{\lambda}})}\times{K_{g}(\bar{z},{\bar{\lambda}})}^{*}$.
This, combined with (3.22), tells us that
$(u,w)\in{K_{g}(\bar{z},{\bar{\lambda}})}^{*}\times{K_{g}(\bar{z},{\bar{\lambda}})}\subset
N_{{\rm gph}\,\partial g}(\bar{z},{\bar{\lambda}})$. Employing the definition
of coderivative and (3.25), we obtain $u\in D^{*}(\partial
g)(\bar{z},{\bar{\lambda}})(-w)=D(\partial
g)(\bar{z},{\bar{\lambda}})(-w)=N_{K_{g}(\bar{z},{\bar{\lambda}})}(-w)$, which
clearly confirms that $-w\in{K_{g}(\bar{z},{\bar{\lambda}})}$. Since
${K_{g}(\bar{z},{\bar{\lambda}})}=N_{\partial g(\bar{z})}({\bar{\lambda}})$
and ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a linear subspace, we obtain
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$, which completes the proof.

##  4 Strict Twice Epi-Differentiability of Polyhedral Functions

In this section, we study another important second-order variational property,
called strict twice epi-differentiability, for polyhedral functions and
continuous differentiability of proximal mappings for this class of functions.
Once again, our results rely heavily on our extension of the reduction lemma
for polyhedral functions. To achieve our goal, consider a function $f:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ with $\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 [29, 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})$. Twice epi-
differentiability of extended-real-valued functions, introduced by Rockafellar
in [25], has been investigated for important classes of functions appearing in
constrained and composite optimization problems in [26, 12, 13]. Its strict
version, introduced in [18], was only studied in [17] for nonlinear
programming and minimax problems and so it is tempting to ask when this
property holds and to explore its applications in parametric optimization. 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}$ in the
sense of [29, Definition 13.28], we can drop the requirement $f(x)\to
f(\bar{x})$ in the definition of the strict second subderivative. According to
[29, Example 13.30], convex functions are always subdifferentialy continuous.
Clearly, we always have ${\rm d}_{s}^{2}f(\bar{x},\bar{v})(w)\leq{\rm
d}^{2}f(\bar{x},\bar{v})(w)$ for any $w\in{\rm I\\!R}^{n}$. If $f$ is strictly
twice epi-differentiable at $\bar{x}$ for $\bar{v}$, the latter inequality
becomes equality. Being able to calculate the strict second subderivative of a
function and comparing with its second subderivative can tell us when strict
twice epi-differentiability should be expected for such a function. Note also
that the second subderivative was exploited to characterize the quadratic
growth condition for extended-real-valued functions in [29, Theorem 13.24(c)].
Similarly, we can use the strict second subderivative to achieve a
characterization of the uniform quadratic growth condition (cf. [1, Definition
5.16]), which plays an important role in parametric optimization. This is
beyond the scope of this paper and so we postpone it to our future research.
Below, we use the characterization of the faces of the critical cone of a
polyhedral function in Proposition 3.3 to find its strict second
subderivative.

######  Proposition 4.1.

For a polyhedral function $g:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ and
$(\bar{z},{\bar{\lambda}})\in{\rm gph}\,\partial g$, its strict second
subderivative can be calculated by

${\rm
d}_{s}^{2}g(\bar{z},{\bar{\lambda}})(w)=\delta_{{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}}(w)\quad\textrm{
for all }\;w\in{\rm I\\!R}^{m}.$ (4.1)

[Proof. ]We first prove that ${\rm d}_{s}^{2}g(\bar{z},{\bar{\lambda}})(w)=0$
for all
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}$.
First, observe that the convexity of $g$ yields ${\rm
d}_{s}^{2}g(\bar{z},{\bar{\lambda}})(w)\geq 0$ for all $w\in{\rm I\\!R}^{m}$.
To obtain the opposite inequality, pick
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}$. By
Proposition 3.3, we find a sequence
$(z^{k},{\lambda^{k}})\to(\bar{z},{\bar{\lambda}})$ such that
$(z^{k},\lambda^{k})\in{\rm gph}\,\partial g$ and
$K_{g}(z^{k},{\lambda^{k}})={K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}$.
This implies that $w\in K_{g}(z^{k},{\lambda^{k}})$, which is equivalent to
saying that ${\rm d}g(z^{k})(w)=\langle{\lambda^{k}},w\rangle$. Employing
Proposition 2.2(b), we find a sequence $t_{k}\searrow 0$ such that
$g(z^{k}+t_{k}w)-g(z^{k})={\rm d}g(z^{k})(t_{k}w)=t_{k}{\rm d}g(z^{k})(w)$. By
definition, we get $\Delta_{t_{k}}^{2}g(z^{k},{\lambda^{k}})(w)=0$, which
results in

${\rm
d}_{s}^{2}g(\bar{z},{\bar{\lambda}})(w)\leq\lim_{k\to\infty}\Delta_{t_{k}}^{2}g(z^{k},{\lambda^{k}})(w)=0.$

This confirms that ${\rm d}_{s}^{2}g(\bar{z},{\bar{\lambda}})(w)=0$ for any
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}$. To
obtain (4.1), it suffices to to justify that ${\rm dom}\,{\rm
d}_{s}^{2}g(\bar{z},{\bar{\lambda}})\subset{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}$.
Taking any $w\in{\rm I\\!R}^{m}$ with ${\rm
d}_{s}^{2}g(\bar{z},{\bar{\lambda}})(w)<\infty$, we can find sequences
$t_{k}\searrow 0$, $w^{k}\to w$, and
$(z^{k},{\lambda^{k}})\to(\bar{z},{\bar{\lambda}})$ with
$(z^{k},{\lambda^{k}})\in{\rm gph}\,\partial g$ such that

$\lim_{k\to\infty}\frac{g(z^{k}+t_{k}w^{k})-g(z^{k})-t_{k}\langle{\lambda^{k}},w^{k}\rangle}{\tfrac{1}{2}t_{k}^{2}}<\infty.$

This, together with the convexity of $g$, allows us to find a constant $M>0$
such that

$0\leq\frac{g(z^{k}+t_{k}w^{k})-g(z^{k})-t_{k}\langle{\lambda^{k}},w^{k}\rangle}{t_{k}}\leq
Mt_{k}$

for all $k$ sufficiently large and therefore to obtain

$\lim_{k\to\infty}\frac{g(z^{k}+t_{k}w^{k})-g(z^{k})-t_{k}\langle{\lambda^{k}},w^{k}\rangle}{t_{k}}=0.$
(4.2)

Take an arbitrary

$u\in\big{(}{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}\big{)}^{\perp}={K_{g}(\bar{z},{\bar{\lambda}})}^{*}\cap-{K_{g}(\bar{z},{\bar{\lambda}})}^{*}=T_{\partial
g(\bar{z})}({\bar{\lambda}})\cap-T_{\partial g(\bar{z})}({\bar{\lambda}}),$

where the last equality results from (2.14). We now show that $\langle
u,w\rangle=0$, which in turn yields
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}$. To
this end, by (2.12), we find $\alpha>0$ such that ${\bar{\lambda}}\pm\alpha
u\in\partial g(\bar{z})$. This clearly implies that

$\langle{\bar{\lambda}}\pm\alpha u,z^{k}+t_{k}w^{k}-\bar{z}\rangle\leq
g(z^{k}+t_{k}w^{k})-g(\bar{z}).$ (4.3)

Employing Theorem 3.1, we can conclude that
$(z^{k}-\bar{z},{\lambda^{k}}-{\bar{\lambda}})\in{\rm
gph}\,N_{K_{g}(\bar{z},{\bar{\lambda}})}$ for all $k$ sufficiently large. This
tells us that $z^{k}-\bar{z}\in{K_{g}(\bar{z},{\bar{\lambda}})}=N_{\partial
g(\bar{z})}({\bar{\lambda}})$ for all $k$ sufficiently large. Moerover, Lemma
2.1 confirms that ${\bar{\lambda}}\in\partial g(z^{k})$ for all $k$
sufficiently large. Combining these, we can conclude that

$\langle u,z^{k}-\bar{z}\rangle=0\quad\textrm{ and
}\quad\langle{\bar{\lambda}},z^{k}-\bar{z}\rangle=g(z^{k})-g(\bar{z}).$

These, together with (4.3), yield

$\langle{\bar{\lambda}}\pm\alpha u,t_{k}w^{k}\rangle\leq
g(z^{k}+t_{k}w^{k})-g(z^{k}),$

and therefore we get

$\langle{\bar{\lambda}}-{\lambda^{k}}\pm\alpha
u,w^{k}\rangle\leq\frac{g(z^{k}+t_{k}w^{k})-g(z^{k})-t_{k}\langle{\lambda^{k}},w^{k}\rangle}{t_{k}}.$

Passing to the limit as $k\to\infty$ and employing (4.2), we arrive at
$\pm\alpha\langle u,w\rangle\leq 0$, meaning $\langle u,w\rangle=0$. This
confirms that
$w\in{K_{g}(\bar{z},{\bar{\lambda}})}-{K_{g}(\bar{z},{\bar{\lambda}})}$ and
hence completes the proof.

The established formula for the strict second subderivative of a polyhedral
function in (4.1) suggests a path forward in the study of strict twice epi-
differentiability of this class of functions. As pointed out earlier, strict
twice epi-differentiability requires that the second subderivative and strict
second subderivative coincide. For polyhedral functions, Proposition 4.1
immediately suggests that the given subgradient ${\bar{\lambda}}$ must belong
to ${\rm ri}\,\partial g(\bar{z})$; see the proof of the implication
(a)$\implies$(b) in Theorem 4.3 for a detailed proof. One may wonder whether
the opposite holds as well, namely the relative interior condition
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$ implies strict twice epi-
differentiability of polyhedral functions. Our next goal is to indeed
demonstrate that this is true. In doing so, we rely heavily upon the reduction
lemma, obtained in Theorem 3.1, as well as a characterization of strict twice
epi-differentiablity of prox-regular functions from [19]. The next result is a
simplified version of [19, Corollary 4.3], and presents a useful
characterization of strict twice epi-differentiability of convex functions,
which comprise an important subclass of prox-regular functions according to
[29, Example 3.30].

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

Assume that $f:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$, $\bar{x}\in{\rm
I\\!R}^{n}$ with $f(\bar{x})$ finite, and $\bar{v}\in\partial f(\bar{x})$ and
that $f$ is a convex function. Then there is a neighborhood $O$ of
$(\bar{x},\bar{v})$ such that for any $(x,v)\in O\cap{\rm gph}\,f$, the
following properties are equivalent:

  * (a)

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

  * (b)

$\partial f$ is strictly proto-differentiable at $x$ for $v$.

The next result is an immediate consequence of Theorem 3.5(c) and reveals that
polyhedral functions are always strictly twice epi-differentiable under a
relative interior condition.

######  Theorem 4.3 (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 $O$ of $(\bar{z},{\bar{\lambda}})$ such that for any
$(z,\lambda)\in O\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})$.

[Proof. ]We begin with the implication (b)$\implies$(a). By Proposition 4.2,
(a) is equivalent to strict proto-differentiability of $\partial g$ at $z$ for
$\lambda$ for any $(z,\lambda)\in O\cap{\rm gph}\,\partial g$. It follows from
Theorem 3.5(c) that the latter condition holds since ${\bar{\lambda}}\in{\rm
ri}\,\partial g(\bar{z})$. This shows that (b) yields (a). To prove the
opposite implication, suppose that (a) holds. As pointed out earlier, when
strict twice epidifferentiablity holds for a function, its second
subderivative and strict second subderivative coincide. Strict twice epi-
differentiability of $g$ at $\bar{z}$ for ${\bar{\lambda}}$, together with
(4.1), tells us that

$\delta_{K_{g}(\bar{z},{\bar{\lambda}})-{K_{g}(\bar{z},{\bar{\lambda}})}}={\rm
d}_{s}^{2}g(\bar{z},{\bar{\lambda}})={\rm
d}^{2}g(\bar{z},{\bar{\lambda}})=\delta_{K_{g}(\bar{z},{\bar{\lambda}})},$

where the last equality comes from [29, Propsoition 13.9]. This implies that
$K_{g}(\bar{z},{\bar{\lambda}})-{K_{g}(\bar{z},{\bar{\lambda}})}={K_{g}(\bar{z},{\bar{\lambda}})}$,
meaning that ${K_{g}(\bar{z},{\bar{\lambda}})}$ is a linear subspace. By
Proposition 2.3, we get ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$,
which completes the proof.

Combining the obtained characterization of strict twice epi-differentiability
of polyhedral functions with (3.6) allows us to conclude that this property is
preserved under the Fenchel conjugate for polyhedral functions, as shown
below.

######  Corollary 4.4.

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 $O$ of $(\bar{z},{\bar{\lambda}})$ such that for any
$(z,\lambda)\in O\cap{\rm gph}\,\partial g$, $g$ is strictly twice epi-
differentiable at $z$ for $\lambda$;

  * (b)

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

  * (c)

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

  * (d)

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

[Proof. ]We know from [29, Theorem 11.14(a)] that $g^{*}$ is a polyhedral
function. We obtain the equivalence of (a) and (c) and of (b) and (d) from
Theorem 4.3. Corollary 3.2 also tells us that (c) and (d) are equivalent,
which completes the proof.

We close this section with another consequence of the reduction lemma for
polyhedral function about smoothness of the Moreau envelope and proximal
mapping for polyhedral functions. To this end, recall that for a function
$f\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and parameter value $r>0$,
the Moreau envelope function $e_{r}f$ and the proximal mapping ${\rm
prox}_{rf}$ are defined, respectively, by

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

and

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

When $f$ is convex, the subdifferential sum rule from convex analysis implies
that

${\rm{prox}}_{rf}(x)=\big{(}I+r\partial f\big{)}^{-1}(x),\;\;x\in{\rm
I\\!R}^{n},$ (4.4)

where $I$ stands for the $n\times n$ identity matrix. Furthermore, it is known
that the envelope function $e_{r}f$ is continuously differentiable (cf. [29,
Theorem 2.26]) for any convex function $f$. If, in addition, $f$ is a
polyhedral function, we deduce from [29, Proposition 13.9] and [29, Exercise
13.45] that the proximal mapping ${\rm prox}_{rf}$ is semidifferentiable.
According to [2, Proposition 2D.1], the latter is equivalent to directional
differentiability of ${\rm prox}_{rf}$. Below, we present a simple but useful
characterization of continuous differentiability of the proximal mapping of
polyhedral functions.

######  Theorem 4.5.

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)

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

  * (b)

for any $r>0$, the envelope function $e_{r}g$ is ${\cal C}^{2}$ in a
neighborhood of $\bar{z}+r{\bar{\lambda}}$;

  * (c)

for any $r>0$, the proximal mapping ${\rm prox}_{rg}$ is ${\cal C}^{1}$ in a
neighborhood of $\bar{z}+r{\bar{\lambda}}$.

Furthermore, if ${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$ and $r>0$,
then for any $x$ sufficiently close to $\bar{z}+r{\bar{\lambda}}$, the
Jacobian matrix $\nabla({\rm prox}_{rg})(x)$ and the Hessian matrix
$\nabla^{2}(e_{r}g)(x)$ can be calculated, respectively, by

$\nabla({\rm
prox}_{rg})(x)=P_{K_{g}(\bar{z},{\bar{\lambda}})}\quad\mbox{and}\quad\nabla^{2}(e_{r}g)(x)=\frac{1}{r}\big{(}I-P_{K_{g}(\bar{z},{\bar{\lambda}})}\big{)}=\frac{1}{r}P_{K_{g^{*}}({\bar{\lambda}},\bar{z})}.$

[Proof. ]Set $\varphi(z)=g(z)-\langle{\bar{\lambda}},z\rangle$ for any
$z\in{\rm I\\!R}^{m}$. Since ${\bar{\lambda}}\in\partial g(\bar{z})$, we get
$0\in\partial\varphi(\bar{z})$. This, together with the convexity of
$\varphi$, yields $\bar{z}\in\mbox{argmin}\,\varphi$, where
$\mbox{argmin}\,\varphi$ stands for the set of global minimizers of $\varphi$
over ${\rm I\\!R}^{m}$. Observe also that the condition
${\bar{\lambda}}\in{\rm ri}\,\partial g(\bar{z})$ is equivalent to $0\in{\rm
ri}\,\partial\varphi(\bar{z})$ and that

${\rm prox}_{r\varphi}(z)={\rm prox}_{rg}(z+r{\bar{\lambda}})\quad\mbox{for
all}\;\;z\in{\rm I\\!R}^{m}.$ (4.5)

Picking $r>0$ and employing [19, Theorem 4.4] imply that ${\rm
prox}_{r\varphi}$ is ${\cal C}^{1}$ in a neighborhood of $\bar{z}$ if and only
if $\varphi$ is strictly twice epi-differentiable at $z$ for $v$ for all
$(z,v)\in{\rm gph}\,\partial\varphi$ sufficiently close to $(\bar{z},0)$ (the
parameter $r$ in [19, Theorem 4.4] should be chosen sufficiently small since
the function under consideration in [19] is prox-regular. It is, however,
well-known that such a restriction on $r$ for convex functions is not
necessary). By Theorem 4.3, the latter property of $\varphi$ amounts to the
condition $0\in{\rm ri}\,\partial\varphi(\bar{z})$. It is not hard to see that
$\varphi$ is strictly twice epi-differentiable at $z$ for $v$ for any
$(z,v)\in{\rm gph}\,\partial\varphi$ sufficiently close to $(\bar{z},0)$ if
and only if $g$ enjoys the same property at $z$ for $\lambda$ for any
$(z,\lambda)\in\partial g$ sufficiently close to $(\bar{z},{\bar{\lambda}})$.
Combining these with (4.5) and Theorem 4.3, we conclude the equivalence of (a)
and (c). To obtain the equivalence of (a) and (b), one can see that

$e_{r}\varphi(z)=e_{r}g(z+r{\bar{\lambda}})-\langle{\bar{\lambda}},z\rangle-\frac{r}{2}\|{\bar{\lambda}}\|^{2}\quad\mbox{for
all}\;\;z\in{\rm I\\!R}^{m}.$

This, combined with a similar argument via [19, Theorem 4.4], confirms that
(a) and (b) are equivalent.

Finally, pick $r>0$ and suppose that ${\bar{\lambda}}\in{\rm ri}\,\partial
g(\bar{z})$. By (b) and (c), there exists a neighborhood $U$ of
$\bar{z}+r{\bar{\lambda}}$ such that ${\rm prox}_{rg}$ is ${\cal C}^{1}$ and
$e_{r}g$ is ${\cal C}^{2}$ on $U$. Take $x\in U$ and set $y={\rm
prox}_{rg}(x)$. By (4.4), we get $v:=r^{-1}(x-y)\in\partial g(y)$. It also
follows from (4.4) and the definition of graphical derivative that

$D({\rm prox}_{rg})(x)(w)=\big{(}I+rD(\partial
g)(y,v)\big{)}^{-1}(w)\quad\mbox{for all}\;\;w\in{\rm I\\!R}^{m},$

which, together with (3.17), brings us to

$D({\rm
prox}_{rg})(x)(w)=\big{(}I+rN_{K_{g}(y,v)}\big{)}^{-1}(w)=\big{(}I+N_{K_{g}(y,v)}\big{)}^{-1}(w)=P_{K_{g}(y,v)}(w)$

for any $w\in{\rm I\\!R}^{m}$. By (c), the proximal mapping ${\rm prox}_{rg}$
is differentiable at $x$ and thus we get $D({\rm prox}_{rg})(x)=\nabla({\rm
prox}_{rg})(x)$. Combining these confirms the claimed formula for the Jacobian
matrix $\nabla({\rm prox}_{rg})(x)$. Recall also from [29, Theorem 2.26] that
$\nabla(e_{r}g)(x)=r^{-1}(x-{\rm prox}_{rg}(x))$ for any $x\in{\rm
I\\!R}^{m}$. By (b), the envelope function $e_{r}g$ is twice differentiable at
$x$ and thus we have

$\nabla^{2}(e_{r}g)(x)=\frac{1}{r}(I-\nabla({\rm
prox}_{rg})(x)\big{)}=\frac{1}{r}\big{(}I-P_{K_{g}(y,v)}\big{)}=\frac{1}{r}P_{K_{g^{*}}(v,y)},$

where the last equality comes from the identity
$P_{K_{g}(y,v)}+P_{K_{g}(y,v)^{*}}=I$ together with (3.5). Now, we claim that
$K_{g}(y,v)={K_{g}(\bar{z},{\bar{\lambda}})}$ whenever $x\in U$. This can be
accomplished via Theorem 3.4(b) provided that we show $(y,v)\in{\rm
gph}\,\partial g$ is sufficiently close to $(\bar{z},{\bar{\lambda}})$. Since
the proximal mapping is nonexpansive and since ${\rm
prox}_{rg}(\bar{z}+r{\bar{\lambda}})=\bar{z}$, we get

$\|y-\bar{z}\|=\|{\rm prox}_{rg}(x)-{\rm
prox}_{rg}(\bar{z}+r{\bar{\lambda}})\|\leq\|x-\bar{z}-r{\bar{\lambda}}\|.$

Moreover, we have

$\|v-{\bar{\lambda}}\|=\|r^{-1}(x-y)-{\bar{\lambda}}\|\leq
r^{-1}\|x-\bar{z}-r{\bar{\lambda}}\|+r^{-1}\|y-\bar{z}\|\leq
2r^{-1}\|x-\bar{z}-r{\bar{\lambda}}\|.$

Using these estimates and shrinking $U$, if necessary, confirm our claim and
hence prove the claimed formulas for the Jacobian matrix $\nabla({\rm
prox}_{rg})(x)$ and the Hessian matrix $\nabla^{2}(e_{r}g)(x)$.

We should mention that smoothness of projection mapping onto a closed convex
set was first studied by Holmes in [6] in Hilbert spaces. His main result, [6,
Theorem 2], states that if $C\subset{\rm I\\!R}^{d}$ is a closed convex set,
$x\in{\rm I\\!R}^{d}$, the boundary of $C$ is a ${\cal C}^{2}$ smooth manifold
(cf. [29, Example 6.8]) around $y=P_{C}(x)$, then the projection mapping
$P_{C}$ is ${\cal C}^{1}$ in a neighborhood of the open normal ray
$\\{y+t(x-y)|\;t>0\\}$. As pointed out by Hiriart-Urruty in [7], when the
projection point $y$ is a corner point, Holmes’s result can not be utilized to
study smoothness of the projection mapping because the boundary of $C$ fails
to be a ${\cal C}^{2}$ smooth manifold around $y$. In contrast, Theorem 4.5
goes beyond the projection mapping and provides a characterization of
smoothness of the proximal mapping of a polyhedral function via a verifiable
condition. While our result is limited to polyhedral functions, our approach
via second-order variational analysis opens a new door to study smoothness of
projection mappings of convex sets. It is important to emphasize that our
approach to characterize smoothness of proximal mappings demonstrates that
instead of expecting smoothness of the boundary of the convex set under
consideration, we should look for a second-order regularity condition, which
seems to be the driving force for such a result.

######  Corollary 4.6.

Assume that $C\subset{\rm I\\!R}^{m}$ is a polyhedral convex set and $x\in{\rm
I\\!R}^{m}$. Then $P_{C}$ is ${\cal C}^{1}$ in a neighborhood of $x$ if and
only if $x-z\in{\rm ri}\,N_{C}(z)$, where $z=P_{C}(x)$.

[Proof. ]Applying Theorem 4.5 to the polyhedral function $g=\delta_{C}$ proves
the claimed equivalence.

Note that a characterization of differentiability at a point, but not
continuous differentiability around a point, of the projection mapping
$P_{C}$, $C$ being a polyhedral convex set, via the same relative interior
condition as in Corollary 4.6 can be found in [4, Corollary 4.1.2]. Not only
is our proof different from the one in [4], also Corollary 4.6 improves the
latter result by showing that differentiability of the projection mapping at a
given point can be strengthened to the ${\cal C}^{1}$ property of this mapping
in a neighborhood of that point.

##  5  Regularity Properties of Variational Systems

In this section, we aim to explore the relationship between important
regularity properties of the solution mapping to the generalized equation
(1.1). When $g=\delta_{C}$ with $C$ being a polyhedral convex set, the
generalized equation (1.1) will be an example of variational inequalities. In
this case, the seminal paper [3] revealed for the first time that strong
metric regularity and metric regularity of the solution mapping to the
canonical perturbation of (1.1) are equivalent; see below for the definitions
of both concepts. We aim to present a similar result for the generalized
equation (1.1), which is based upon the reduction lemma for polyhedral
functions. Furthermore, we show that for nondegenerate solutions to (1.1),
meaning solutions that satisfy the condition (1.2), one can find conditions
under which the solution mapping to the generalized equation (1.1) is
continuously differentiable.

To explore regularity properties of (1.1), define the set-valued mapping
$G:{\rm I\\!R}^{m}\rightrightarrows{\rm I\\!R}^{m}$ by

$G(x):=\psi(x)+\partial g(x),\quad x\in{\rm I\\!R}^{m},$ (5.1)

and then consider the solution mapping $S:{\rm I\\!R}^{m}\rightrightarrows{\rm
I\\!R}^{m}$ to the canonical perturbation of the generalized equation (1.1) by

$S(y):=G^{-1}(y)=\big{\\{}x\in{\rm I\\!R}^{m}\,\big{|}\,y\in\psi(x)+\partial
g(x)\big{\\}},\quad y\in{\rm I\\!R}^{m}.$ (5.2)

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{)}$ (5.3)

holds for all $(x,y)\in U\times V$. The mapping is called strongly metrically
regular at $\bar{x}$ for $\bar{y}$ 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 [2, 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}$.

######  Theorem 5.1 (equivalence between metric regularity and strong metric
regularity).

Assume that $\bar{x}$ is a solution to the generalized equation (1.1). Then
the mapping $G$, taken from (5.1), is metrically regular at $\bar{x}$ for $0$
if and only if it is strongly metrically regular at $\bar{x}$ for $0$.

[Proof. ]Note that one can argue via [2, Corollary 3F.5] that (strong) metric
regularity of the mapping $G$ from (5.1) at $\bar{x}$ for $0$ is equivalent to
that of the mapping
$x\mapsto\psi(\bar{x})+\nabla\psi(\bar{x})(x-\bar{x})+\partial g(x)$ at
$\bar{x}$ for $0$. Employing then Theorem 3.1 tells us that (strong) metric
regularity of the latter amounts to the same property of the mapping
$\Phi(w):=\nabla\psi(\bar{x})w+N_{{\overline{K}}}(w)$ with
${\overline{K}}=K_{g}(\bar{x},-\psi(\bar{x}))$ and $w\in{\rm I\\!R}^{m}$ at
$0$ for $0$. Since $\Phi$ fits into the framework of [3], one can conclude via
[3, Theorem 3] (or [8, Corollary 9.7]) that metric regularity and strong
metric regularity are equivalent for $\Phi$ at $0$ for $0$, which implies that
these properties are equivalent for $G$ at $\bar{x}$ for $0$ and hence
completes the proof.

We proceed with an application of Theorem 5.1 in studying regularity
properties of the solution mapping to the KKT system of the composite
minimization problem

$\operatorname*{minimize\;}\varphi(x)+\big{(}g\circ\Phi\big{)}(x),\quad\textrm{subject
to}\;\;x\in{\rm I\\!R}^{n},$ (5.4)

where $\varphi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ and $\Phi:{\rm I\\!R}^{n}\to{\rm
I\\!R}^{m}$ are ${\cal C}^{2}$ functions and $g:{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a polyhedral function. The KKT system
associated with the composite problem (5.4) is given by

$0=\nabla_{x}L(x,\lambda),\quad\lambda\in\partial g(\Phi(x)),$ (5.5)

where $L(x,\lambda):=\varphi(x)+\langle\lambda,\Phi(x)\rangle$ with
$(x,\lambda)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}$ is the Lagrangian of
(5.4). A pair $(\bar{x},{\bar{\lambda}})$ is called a KKT point of (5.4)
provided that it satisfies the KKT system (5.5). Define the mapping $\Psi:{\rm
I\\!R}^{n}\times{\rm I\\!R}^{m}\rightrightarrows{\rm I\\!R}^{n}\times{\rm
I\\!R}^{m}$ by

$\Psi(x,\lambda):=\begin{bmatrix}\nabla_{x}L(x,\lambda)\\\
-\Phi(x)\end{bmatrix}+\begin{bmatrix}0\\\ \partial
g^{*}(\lambda)\end{bmatrix}$ (5.6)

and observe that $(\bar{x},{\bar{\lambda}})$ is a KKT point if and only if
$(0,0)\in\Psi(\bar{x},{\bar{\lambda}})$. We aim at finding conditions under
which the solution mapping to the canonical perturbed of the KKT system (5.5),
defined by

$S_{KKT}(p,q):=\Psi^{-1}(p,q)=\big{\\{}(x,\lambda)\in{\rm I\\!R}^{n}\times{\rm
I\\!R}^{m}\,\big{|}\,(p,q)\in\Psi(x,\lambda)\big{\\}},$

has a Lipschitz continuous single-valued localization. As shown below, this
can be distilled from Theorem 5.1.

######  Theorem 5.2.

Let $(\bar{x},{\bar{\lambda}})$ be a KKT point of (5.4). Then the following
properties are equivalent:

  * (a)

the mapping $\Psi$ is metrically regular at $(\bar{x},{\bar{\lambda}})$ for
$(0,0)$;

  * (b)

the mapping $\Psi$ is strongly metrically regular at
$(\bar{x},{\bar{\lambda}})$ for $(0,0)$;

  * (c)

the solution mapping $S_{KKT}$ has a Lipschitz continuous single-valued
localization around $(0,0)$ for $(\bar{x},{\bar{\lambda}})$;

  * (d)

the implication

$\begin{cases}\nabla^{2}_{xx}L(\bar{x},{\bar{\lambda}})w+\nabla\Phi(\bar{x})^{*}w^{\prime}=0,\\\
w^{\prime}\in D^{*}(\partial
g)(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w)\end{cases}\implies(w,w^{\prime})=(0,0)$

holds.

[Proof. ]Set

$\psi(x,\lambda):=\begin{bmatrix}\nabla_{x}L(x,\lambda)\\\
-\Phi(x)\end{bmatrix}\quad\textrm{ and
}\quad\hat{g}(x,\lambda):=g^{*}(\lambda),\;\;(x,\lambda)\in{\rm
I\\!R}^{n}\times{\rm I\\!R}^{m},$

and observe that the KKT system (5.5) can be written as the generalized
equation

$(0,0)\in\Psi(x,\lambda)=\psi(x,\lambda)+\partial\hat{g}(x,\lambda).$ (5.7)

It follows from [29, Theorem 11.14(a)] that $g^{*}$ is a polyhedral function
and so is $\hat{g}$. Also, we deduce from [29, Proposition 10.5] that
$\partial\hat{g}(x,\lambda)=\\{0\\}\times\partial g^{*}(\lambda)$. The
equivalence of (a)-(c) comes directly from Theorem 5.1. Part (d) is a direct
consequence of the coderivative criterion from [29, Theorem 9.40] for metric
regularity of the mapping $\Psi$ at $(\bar{x},{\bar{\lambda}})$ for $(0,0)$,
which translates as the implication

$\begin{bmatrix}0\\\ 0\end{bmatrix}\in
D^{*}\Psi\big{(}(\bar{x},{\bar{\lambda}}),(0,0)\big{)}(w,w^{\prime})=\left[\begin{array}[]{c}\nabla_{xx}^{2}L(\bar{x},{\bar{\lambda}})w-\nabla\Phi(\bar{x})^{*}w^{\prime}\\\
\nabla\Phi(\bar{x})w+D^{*}(\partial
g^{*})({\bar{\lambda}},\Phi(\bar{x}))(w^{\prime})\\\
\end{array}\right]\implies(w,w^{\prime})=(0,0).$

The second inclusion in this implication amounts to $-w^{\prime}\in
D^{*}(\partial g)(\Phi(\bar{x}),{\bar{\lambda}})(\nabla\Phi(\bar{x})w)$.
Combining this with the above implication confirms that (d) and (a) are
equivalent and hence completes the proof.

For classical nonlinear programming problems (NLPs), it is well-known that
metric regularity and strong metric regularity of KKT systems are equivalent;
see [2, Theorem 4I.2] and [9, Section 7.5]. Theorem 5.2 extends this result
for the composite problem (5.4).

According to Theorem 5.1, if $\bar{x}$ is a solution to (1.1) and if the
mapping $G$ in (5.1) is metrically regular at $\bar{x}$ for $0$, then the
solution mapping $S$ in (5.2) has a Lipschitz continuous single-valued
localization around $0$ for $\bar{x}$. Our final goal in this section is to
show that if, in addition, $\bar{x}$ is a nondegenerate solution to (1.1)
which means it satisfies (1.2), then the aforementioned localization of $S$ is
continuously differentiable around $0$. To this end, we begin with showing
that strict proto-differentiability is preserved for the sum of two functions.

######  Proposition 5.3 (sum rule for strict proto-derivative).

Let $f:{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ be ${\cal C}^{1}$ around $\bar{x}$
and let $F:{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ with $\bar{y}\in
F(\bar{x})$. Then we have

$D_{*}(f+F)(\bar{x},f(\bar{x})+\bar{y})(w)=\nabla
f(\bar{x})w+D_{*}F(\bar{x},\bar{y})(w)\quad\mbox{for all}\;\;w\in{\rm
I\\!R}^{n}.$

Moreover, $F$ is strictly proto-differentiable at $\bar{x}$ for $\bar{y}$ if
and only if $f+F$ is strictly proto-differentiable at $\bar{x}$ for
$f(\bar{x})+\bar{y}$.

[Proof. ]The given formula for $D_{*}(f+F)(\bar{x},f(\bar{x})+\bar{y})$ was
already established in [29, Exercise 10.43(b)]. To justify the second claim,
suppose that $F$ is strictly proto-differentiable at $\bar{x}$ for $\bar{y}$.
Let $(w,u)\in{\rm gph}\,D_{*}(f+F)(\bar{x},\bar{y}+f(\bar{x}))$ and take
arbitrary sequences $t_{k}\searrow 0$, and
$(x^{k},z^{k})\to(\bar{x},\bar{y}+f(\bar{x}))$ with
$\\{(x^{k},z^{k}){\\}_{k\in{\rm I\\!N}}}\subset{\rm gph}\,(f+F)$. The latter
tells us that $(x^{k},y^{k})\to(\bar{x},\bar{y})$ with
$y^{k}:=z^{k}-f(x^{k})$. By the sum rule for the strict graphical derivative,
we get $(w,u-\nabla f(\bar{x})w)\in{\rm gph}\,D_{*}F(\bar{x},\bar{y})$. Since
$F$ is strictly proto-differentiable at $\bar{x}$ for $\bar{y}$, we find a
sequence $(w^{k},v^{k})\to(w,u-\nabla f(\bar{x})w)$ such that
$y^{k}+t_{k}v^{k}\in F(x^{k}+t_{k}w^{k})$ for all $k\in{\rm I\\!N}$, which in
turn implies for any $k\in{\rm I\\!N}$ that

$z^{k}+t_{k}u^{k}\in(f+F)(x^{k}+t_{k}w^{k})\quad\mbox{with}\;\;u^{k}:=\frac{f(x^{k}+t_{k}w^{k})-f(x^{k})}{t_{k}}+v^{k}.$

Since $\\{(w^{k},u^{k}){\\}_{k\in{\rm I\\!N}}}$ converges to $(w,u)$, we
conclude that $f+F$ is strictly proto-differentiable at $\bar{x}$ for
$f(\bar{x})+\bar{y}$.

Assume now that $f+F$ is strictly proto-differentiable at $\bar{x}$ for
$f(\bar{x})+\bar{y}$. By the argument above, we can conclude that $F=f+F+(-f)$
is strictly proto-differentiable at $\bar{x}$ for $\bar{y}$, which completes
the proof.

Recall from [25, page 173] that a set $C\subset{\rm I\\!R}^{d}$ is called
smooth at $\bar{x}\in C$ if the tangent cone $T_{C}(\bar{x})$ is a linear
subspace of ${\rm I\\!R}^{d}$ and the “$\limsup$” in (2.1) is the “$\lim$.” It
is called strictly smooth at $\bar{x}$ if
$\widehat{T}_{C}(\bar{x})=\widetilde{T}_{C}(\bar{x}),$ where both tangent
cones were defined in (3.15). It follows from [25, Proposition 3.1] that if
$f:{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ is Lipschitz continuous around
$\bar{x}\in{\rm I\\!R}^{n}$, then ${\rm gph}\,f$ is (strictly) smooth at
$(\bar{x},f(\bar{x}))$ if and only if $f$ is (strictly) differentiable at
$\bar{x}$.

######  Theorem 5.4.

Assume that $\bar{x}$ is a nondegenerate solution to the generalized equation
(1.1). Then the solution mapping $S$ to (1.1) has a Lipschitz continuous
single-valued localization $\sigma$ around $0\in{\rm I\\!R}^{m}$ for $\bar{x}$
if and only if one of the equivalent conditions

  * (a)

$\big{(}\nabla\psi(\bar{x}){\overline{K}}\big{)}+{\overline{K}}^{\perp}={\rm
I\\!R}^{m}$;

  * (b)

$\\{w\in{\rm
I\\!R}^{m}|\;\nabla\psi(\bar{x})^{*}w\in{\overline{K}}^{\perp}\big{\\}}\cap{\overline{K}}=\\{0\\}$,

holds, where ${\overline{K}}=K_{g}(\bar{x},-\psi(\bar{x}))$. In this case, the
function $\sigma$ is ${\cal C}^{1}$ in a neighborhood of $0$ and

$\nabla\sigma(y)=B\big{(}B^{*}\nabla\psi(\sigma(y))B\big{)}^{-1}B^{*}$

for all $y$ sufficiently close to $0$, where $B\in{\rm I\\!R}^{m\times s}$ is
a matrix whose columns form a basis for the linear subspace ${\overline{K}}$
with $s={\rm dim}\,{\overline{K}}$.

[Proof. ]The equivalence of the conditions (a) and (b) falls directly from
[29, Corollary 11.25(c)]. Part (b) is also a translation of the coderivative
criterion from [29, Theorem 9.40] for metric regularity of the mapping $G$ in
(5.1) at $\bar{x}$ for $0$. Indeed, we have for any $w\in{\rm I\\!R}^{m}$ that

$D^{*}G(\bar{x},0)(w)=\nabla\psi(\bar{x})^{*}w+D^{*}(\partial
g)(\bar{x},-\psi(\bar{x}))(w)=\nabla\psi(\bar{x})^{*}w+N_{{\overline{K}}}(w),$

where the last equality results from Theorems 3.7 and 3.5(a). This reads as
$u\in D^{*}G(\bar{x},0)(w)$ if and only if
$u\in\nabla\psi(\bar{x})^{*}w+{{\overline{K}}^{\bot}}$ and
$w\in{\overline{K}}$. Using this, one can see that (b) amounts to saying that
$G$ is metrically regular at $\bar{x}$ for $0$. By Theorem 5.1, the latter is
equivalent to strong metric regularity of $G$ at $\bar{x}$ for $0$, a property
that amounts to saying that the solution mapping $S$ in (5.2) has a Lipschitz
continuous single-valued localization around $0$ for $\bar{x}$. So we find
neighborhoods $U$ of $\bar{x}$ and $V$ of $0$ such that the mapping $y\mapsto
S(y)\cap U$ is single-valued and Lipschitz continuous on $V$. Define the
function $\sigma:V\to U$ by $\sigma(y)=S(y)\cap U$ for any $y\in V$. We are
going to demonstrate that $\sigma$ is ${\cal C}^{1}$ in a neighborhood of $0$.
To this end, it follows from the nondegeneracy condition (1.2) and Theorem
3.5(c) that $\partial g$ is strictly proto-differentiable at $x$ for $z$
whenever $(x,z)\in{\rm gph}\,\partial g$ is sufficiently close to
$(\bar{x},-\psi(\bar{x}))$, which, together with Proposition 5.3, tells us
that $G$ is strictly proto-differentiable at $x$ for $y$ whenever
$(x,y)\in{\rm gph}\,G$ is sufficiently close to $(\bar{x},0)$. Suppose without
loss of generality that $G$ is strictly proto-differentiable at $x$ for $y$
whenever $(x,y)\in(U\times V)\cap{\rm gph}\,G$. Choose a pair
$(x,y)\in(U\times V)\cap{\rm gph}\,G$ and observe that $\sigma$ is strictly
proto-differentiable at $y$ for $x$. This implies that ${\rm gph}\,\sigma$ is
strictly smooth at $(y,x)$. Since $\sigma$ is Lipschitz continuous on $V$, it
follows from [25, Proposition 3.1] that $\sigma$ is strictly differentiable at
$y$. This means that $\sigma$ is strictly differentiable on $V$, a property
equivalent to saying that $\sigma$ is ${\cal C}^{1}$ on $V$ (cf. [2, Exercise
1D.8]).

Finally, to justify the claimed formula for the Jacobian matrix of $\sigma$,
take $y\in V$. Thus, for any $u\in{\rm I\\!R}^{n}$ we have
$w=\nabla\sigma(y)u=D\sigma(y)(u)$, which is equivalent to $u\in DG(x,y)(w)$,
where $x=\sigma(y)$. By the definition of $G$ from (5.1), the sum rule for the
graphical derivative from [29, Exercise 10.43(b)], and Theorem 3.5(a), we
obtain for any $(x,y)\in{\rm gph}\,G$ and $w\in{\rm I\\!R}^{m}$ that

$\displaystyle DG(x,y)(w)=\nabla\psi(x)w+D(\partial
g)(x,y-\psi(x))(w)=\nabla\psi(x)w+N_{K_{g}(x,y-\psi(x))}(w).$

Recall that $\bar{x}$ is a nondegenerate solution to (1.1). Shrinking the
neighborhoods $U$ and $V$, if necessary, we deduce from Corollary 3.4(b) that
for any $(x,y)\in(U\times V)\cap{\rm gph}\,G$, we have
$K_{g}(x,y-\psi(x))=K_{g}(\bar{x},-\psi(\bar{x}))={\overline{K}}$. Combining
these with ${\overline{K}}$ being a linear subspace brings us to

$u\in DG(x,y)(w)\iff
u\in\nabla\psi(x)w+{\overline{K}}^{\perp},\;\;w\in{\overline{K}}.$ (5.8)

By the definition of $B$, we have ${\overline{K}}={\rm rge\,}B$ , or
equivalently, ${\overline{K}}^{\perp}={\rm ker}\,B^{*}$. Thus, we find
$q\in{\rm I\\!R}^{s}$ such that $w=Bq$ and that $u-\nabla\psi(x)Bq\in{\rm
ker}\,B^{*}$, or equivalently, $B^{*}u=B^{*}\nabla\psi(x)Bq$. We claim that
the matrix $B^{*}\nabla\psi(x)B$ is nonsingular, which leads us to

$\nabla\sigma(y)u=w=Bq=B\big{(}B^{*}\nabla\psi(x)B\big{)}^{-1}B^{*}u,$

and hence confirms the claimed formula for $\nabla\sigma(y)$. To justify our
claim, pick $u\in{\rm I\\!R}^{m}$. We conclude from metric regularity of $G$
at $\bar{x}$ for $0$ and and its equivalent description by condition (a) that
there exist $w\in{\overline{K}}$ and $w^{\prime}\in{\overline{K}}^{\perp}$
such that $u=\nabla\psi(\bar{x})w+w^{\prime}$. Since ${\overline{K}}={\rm
rge\,}B$, we find $q\in{\rm I\\!R}^{s}$ such that $w=Bq$ and hence
$B^{*}u=B^{*}(\nabla\psi(\bar{x})Bq+w^{\prime})=B^{*}\nabla\psi(\bar{x})Bq$.
Since $u\in{\rm I\\!R}^{m}$ was taken arbitrary, the latter equality leads us

${\rm rge\,}\big{(}B^{*}\nabla\psi(\bar{x})B\big{)}=B^{*}{\rm I\\!R}^{m}={\rm
rge\,}B^{*}={\rm I\\!R}^{s},$

where the last equality comes from $B$ having full column rank. This confirms
that $B^{*}\nabla\psi(\bar{x})B$ is an $s\times s$ nonsingular matrix and
completes the proof.

Theorem 5.4 can be viewed as an extension of the classical inverse mapping
theorem for generalized equations. This well-known result ensures under the
nonsingularity of the Jacobian matrix that the inverse of a ${\cal C}^{1}$
function has a Lipschitz continuous single-valued localization, which is
continuously differentiable. Robinson, in his landmark paper [20], showed that
for generalized equations, one can expect under appropriate conditions that
their solution mappings have a Lipschitz continuous single-valued
localization. Theorem 5.4 demonstrates that for nondegenerate solutions to
some particular class of generalized equations such a localization can be
continuously differentiable as well.

## 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] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer New York, New York (2000)
  * [2] Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings: A View from Variational Analysis. Springer New York, New York (2014)
  * [3] Dontchev, A.L., Rockafellar, R.T.: Characterizations of strong regularity for variational inequalities over polyhedral convex sets. SIAM J. Optim. 6(4), 1087–1105 (1996)
  * [4] Facchinei, F., Pang, J.-S.: Finite-Dimesional Variational Inequalities and Complementarity Problems. Springer New York, New York (2003)
  * [5] Hang, N.T.V., Sarabi, M.E.: Local convergence analysis of augmented Lagrangian methods for piecewise linear-quadratic composite optimization problems. SIAM J. Optim. 31(4), 2665–2694 (2021)
  * [6] Holmes, R.B.: Smoothness of certain metric projections on Hilbert space. Trans. Amer. Math. Soc. 183, 87–100 (1973)
  * [7] Hiriart-Urruty, J.-B.: At what points is the projection mapping differentiable? Amer. Math. Monthly 89(7), 456–458 (1982)
  * [8] Ioffe, A.D.: Variational Analysis of Regular Mappings: Theory and Applications. Springer, Cham, Switzerland, (2017)
  * [9] Klatte, D., Kummer, B.: Nonsmooth equations in optimization: Regularity, calculus, methods and applications. Kluwer, Dordrecht, (2002)
  * [10] Lemaréchal, C., Oustry, F., Sagastizábal, C.: The $\mathcal{U}$-Lagrangian of a convex function. Trans. Amer. Math. Soc. 352 (2), 711–729 (2000)
  * [11] Lewis, A.S.: Active sets, nonsmoothness and sensitivity. SIAM J. Optim. 13(3), 702–725 (2002)
  * [12] Mohammadi, A., Mordukhovich, B.S., Sarabi, M.E.: Parabolic regularity via geometric variational analysis. Trans. Amer. Soc. 374(3), 1711–1763 (2021)
  * [13] Mohammadi, A., Sarabi, M.E.: Twice epi-differentiability of extended-real-valued functions with applications in composite optimization. SIAM J. Optim. 30(3), 2379–2409 (2020)
  * [14] Mordukhovich, B.S., Sarabi, M.E.: Generalized differentiation of piecewise linear functions in second-order variational analysis. Nonlinear Anal. 132, 240–273 (2016)
  * [15] Mordukhovich, B.S., Sarabi, M.E.: Second-order analysis of piecewise linear functions with applications to optimization and stability. J. Optim. Theory Appl. 171, 504–526 (2016)
  * [16] Mordukhovich, B.S., Sarabi, M.E.: Critical multipliers in variational systems via second-order generalized differentiation. Math. Program. 169, 605–648 (2018)
  * [17] Poliquin, R.A., Rockafellar, R.T.: Second-order nonsmooth analysis in nonlinear programming. In: Du, D., Qi, L., Womersley, R. (eds.) Recent Advances in Optimization, World Scientific Publishers, 322–350 (1995)
  * [18] Poliquin, R.A., Rockafellar, R.T.: Prox-regular functions in variational analysis . Trans. Amer. Math. Soc. 348(5), 1805–1838 (1996)
  * [19] Poliquin, R.A., Rockafellar, R.T.: Generalized Hessian properties of regularized nonsmooth functions. SIAM J. Optim. 6(4), 1121–1137 (1996)
  * [20] Robinson, S.M.: Strongly regular generalized equations. Math. Oper. Res. 5(1), 43–62 (1980)
  * [21] Robinson, S.M.: Local structure of feasible sets in nonlinear programming. Part II: Nondegeneracy. Math. Program. Study 22, 217–230 (1984)
  * [22] Robinson, S.M.: An implicit-function theorem for a class of nonsmooth functions. Math. Oper. Res. 16(2), 292–309 (1991)
  * [23] Robinson, S.M.: Normal maps induced by linear transformations. Math. Oper. Res. 17(3), 691–714 (1992)
  * [24] Rockafellar, R.T.: Convex Ananlysis. Priceton University Press, Princeton, New Jersey (1970)
  * [25] Rockafellar, R.T.: Maximal monotone relations and the second derivatives of nonsmooth functions. Ann. Inst. H. Poincaré Analyse Non Linéaire 2(3), 167–184 (1985)
  * [26] Rockafellar, R.T.: First- and second-order epi-differentiability in nonlinear programming. Trans. Amer. Math. Soc. 307(1), 75–108 (1988)
  * [27] Rockafellar, R.T.: Generalized second derivatives of convex functions and saddle functions. Trans. Amer. Math. Soc. 322(1), 51–77 (1990)
  * [28] Rockafellar, R.T.: Augmented Lagrangians and hidden convexity in sufficient conditions for local optimality. Math. Program. (2022). doi.org/10.1007/s10107-022-01768-w
  * [29] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer Berlin, Heidelberg (1998)
  * [30] Sarabi, M.E.: Primal superlinear convergence of SQP methods for piecewise linear-quadratic composite optimization problems. Set-Valued Var. Anal. 30, 1–37 (2022)