TWICE EPI-DIFFERENTIABILITY OF EXTENDED-REAL-VALUED FUNCTIONS WITH
APPLICATIONS IN COMPOSITE OPTIMIZATION
ASHKAN MOHAMMADI111Department of Mathematics, Wayne State University, Detroit,
MI 48202, USA (ashkan.mohammadi@wayne.edu). and M. EBRAHIM SARABI222Department
of Mathematics, Miami University, Oxford, OH 45065, USA (sarabim@miamioh.edu).

Abstract. The paper is devoted to the study of the twice epi-differentiablity
of extended-real-valued functions, with an emphasis on functions satisfying a
certain composite representation. This will be conducted under parabolic
regularity, a second-order regularity condition that was recently utilized in
[14] for second-order variational analysis of constraint systems. Besides
justifying the twice epi-differentiablity of composite functions, we obtain
precise formulas for their second subderivatives under the metric
subregularity constraint qualification. The latter allows us to derive second-
order optimality conditions for a large class of composite optimization
problems.
Key words. Variational analysis, twice epi-differentiability, parabolic
regularity, composite optimization, second-order optimality conditions
Mathematics Subject Classification (2000) 49J53, 49J52, 90C31

##  1 Introduction

This paper aims to provide a systematic study of the twice epi-
differentiability of extend-real-valued functions in finite dimensional
spaces. In particular, we pay special attention to the composite optimization
problem

$\mbox{minimize}\;\;\varphi(x)+g(F(x))\quad\mbox{over
all}\;\;x\in{\mathbb{X}},$ (1.1)

where $\varphi:{\mathbb{X}}\to{\rm I\\!R}$ and $F:{\mathbb{X}}\to{\mathbb{Y}}$
are twice differentiable and $g:{\mathbb{Y}}\to\overline{{\rm
I\\!R}}:=(-\infty,+\infty]$ is a lower semicontinuous (l.s.c.) convex function
and where ${\mathbb{X}}$ and ${\mathbb{Y}}$ are two finite dimensional spaces,
and verify the twice epi-differentiability of the objective function in (1.1)
under verifiable assumptions. The composite optimization problem (1.1)
encompasses major classes of constrained and composite optimization problems
including classical nonlinear programming problems, second-order cone and
semidefinite programming problems, eigenvalue optimizations problems [24], and
fully amenable composite optimization problems [19], see Example 4.7 for more
detail. Consequently, the composite problem (1.1) provides a unified framework
to study second-order variational properties, including the twice epi-
differentiability and second-order optimality conditions, of the
aforementioned optimization problems. As argued below, the twice epi-
differentiability carries vital second-order information for extend-real-
valued functions and therefore plays an important role in modern second-order
variational analysis.

A lack of an appropriate second-order generalized derivative for nonconvex
extended-real-valued functions was the main driving force for Rockafellar to
introduce in [17] the concept of the twice epi-differentiability for such
functions. Later, in his landmark paper [19], Rockafellar justified this
property for an important class of functions, called fully amenable, that
includes nonlinear programming problems but does not go far enough to cover
other major classes of constrained and composite optimization problems.
Rockafellar’s results were extended in [7, 10] for composite functions
appearing in (1.1). However, these extensions were achieved under a
restrictive assumption on the second subderivative, which does not hold for
constrained optimization problems. Nor does this condition hold for other
major composite functions related to eigenvalue optimization problems; see
[24, Theorem 1.2] for more detail. Levy in [11] obtained upper and lower
estimates for the second subderivative of the composite function from (1.1),
but fell short of establishing the twice epi-differentiability for this
framework.

The authors and Mordukhovich observed recently in [14] that a second-order
regularity, called parabolic regularity (see Definition 3.1), can play a major
role toward the establishment of the twice epi-differentiability for
constraint systems, namely when the outer function $g$ in (1.1) is the
indicator function of a closed convex set. This vastly alleviated the
difficulty that was often appeared in the justification of the twice epi-
differentiability for the latter framework and opened the door for crucial
applications of this concept in theoretical and numerical aspects of
optimization. Among these applications, we can list the following:

  * •

the calculation of proto-derivatives of subgradient mappings via the
connection between the second subderivative of a function and the proto-
derivative of its subgradient mapping (see equation (3.21));

  * •

the calculation of the second subderivative of the augmented Lagrangian
function associated with the composite problem (1.1), which allows us to
characterize the second-order growth condition for the augmented Lagrangian
problem (cf. [14, Theorems 8.3 & 8.4]);

  * •

the validity of the derivative-coderivative inclusion (cf. [21, Theorem
13.57]), which has important consequences in parametric optimization; see [15,
Theorem 5.6] for a recent application in the convergence analysis of the
sequential quadratic programming (SQP) method for constrained optimization
problems.

In this paper, we continue the path, initiated in [14] for constraint systems,
and show that the twice epi-differentiability of the objective function in
(1.1) can be guaranteed under parabolic regularity. To achieve this goal, we
demand that the outer function $g$ from (1.1) be locally Lipschitz continuous
relative to its domain; see the next section for the precise definition of
this concept. Shapiro in [22] used a similar condition but in addition assumed
that this function is finite-valued. The latter does bring certain
restrictions for (1.1) by excluding constrained problems as well as piecewise
linear-quadratic composite problems. As shown in Example 4.7, major classes of
constrained and composite optimization problems satisfy this Lipschitzian
condition. However, some composite problems such as the spectral abcissa
minimization (cf. [4]), namely the problem of minimizing the largest real
parts of eigenvalues, can not be covered by (1.1).

The rest of the paper is organized as follows. Section 2 recalls important
notions of variational analysis that are used throughout this paper. Section 3
begins with the definition of parabolic regularity of extended-real-valued
functions. Then we justify that parabolic regularity amounts to a certain
duality relationship between the second subderivative and parabolic
subderivative. Employing this, we show that the twice epi-differentiability of
extended-real-valued functions can be guaranteed if they are parabolically
regular and parabolic epi-differentiable. Section 4 is devoted to important
second-order variational properties of parabolic subderivatives. In
particular, we establish a chain rule for parabolic subderivatives of
composite functions in (1.1) under the metric subregularity constraint
qualification. In Section 5, we establish chain rules for the parabolic
regularity and for the second subderivative of composite functions, and
consequently establish their twice epi-differentiability. Section 6 deals with
important applications of our results in second-order optimality conditions
for the composite optimization problem (1.1). We close the paper by achieving
a characterization of the strong metric subregularity of the subgradient
mapping of the objective function in (1.1) via the second-order sufficient
condition for this problem.

In what follows, ${\mathbb{X}}$ and ${\mathbb{Y}}$ are finite-dimensional
Hilbert spaces equipped with a scalar product $\langle\cdot,\cdot\rangle$ and
its induced norm $\|\cdot\|$. By $\mathbb{B}$ we denote 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$. For any set $C$ in ${\mathbb{X}}$, its
indicator function is defined by $\delta_{C}(x)=0$ for $x\in C$ and
$\delta_{C}(x)=\infty$ otherwise. We denote by $d(x,C)$ the distance between
$x\in{\mathbb{X}}$ and a set $C$. For $v\in{\mathbb{X}}$, the subspace
$\\{w\in{\mathbb{X}}|\,\langle w,v\rangle=0\\}$ is denoted by
$\\{v\\}^{\bot}$. We write $x(t)=o(t)$ with $x(t)\in{\mathbb{X}}$ and $t>0$ to
mean that ${\|x(t)\|}/{t}$ goes to $0$ as $t\downarrow 0$. Finally, we denote
by ${\rm I\\!R}_{+}$ (respectively, ${\rm I\\!R}_{-}$) the set of non-negative
(respectively, non-positive) real numbers.

##  2  Preliminary Definitions in Variational Analysis

In this section we first briefly review basic constructions of variational
analysis and generalized differentiation employed in the paper; see [12, 21]
for more detail. A family of sets $C_{t}$ in ${\mathbb{X}}$ for $t>0$
converges to a set $C\subset{\mathbb{X}}$ if $C$ is closed and

$\lim_{t\downarrow 0}d(w,C_{t})=d(w,C)\quad\mbox{for
all}\;\;w\in{\mathbb{X}}.$

Given a nonempty set $C\subset{\mathbb{X}}$ with $\bar{x}\in C$, the tangent
cone $T_{C}(\bar{x})$ to $C$ at $\bar{x}$ is defined by

$T_{C}(\bar{x})=\big{\\{}w\in{\mathbb{X}}|\;\exists\,t_{k}{\downarrow}0,\;\;w_{k}\to
w\;\;\mbox{ as }\;k\to\infty\;\;\mbox{with}\;\;\bar{x}+t_{k}w_{k}\in
C\big{\\}}.$

We say a tangent vector $w\in T_{C}(\bar{x})$ is derivable if there exist a
constant $\varepsilon>0$ and an arc $\xi:[0,\varepsilon]\to C$ such that
$\xi(0)=\bar{x}$ and $\xi^{\prime}_{+}(0)=w$, where $\xi^{\prime}_{+}$
signifies the right derivative of $\xi$ at $0$, defined by

$\xi^{\prime}_{+}(0):=\lim_{t\downarrow 0}\frac{\xi(t)-\xi(0)}{t}.$

The set $C$ is called geometrically derivable at $\bar{x}$ if every tangent
vector $w$ to $C$ at $\bar{x}$ is derivable. The geometric derivability of $C$
at $\bar{x}$ can be equivalently described by the sets $[C-\bar{x}]/{t}$
converging to $T_{C}(\bar{x})$ as $t\downarrow 0$. Convex sets are important
examples of geometrically derivable sets. The second-order tangent set to $C$
at $\bar{x}$ for a tangent vector $w\in T_{C}(\bar{x})$ is given by

$T_{C}^{2}(\bar{x},w)=\big{\\{}u\in{\mathbb{X}}|\;\exists\,t_{k}{\downarrow}0,\;\;u_{k}\to
u\;\;\mbox{ as
}\;k\to\infty\;\;\mbox{with}\;\;\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}u_{k}\in
C\big{\\}}.$

A set $C$ is said to be parabolically derivable at $\bar{x}$ for $w$ if
$T_{C}^{2}(\bar{x},w)$ is nonempty and for each $u\in T_{C}^{2}(\bar{x},w)$
there are $\varepsilon>0$ and an are $\xi:[0,\varepsilon]\to C$ with
$\xi(0)=\bar{x}$, $\xi^{\prime}_{+}(0)=w$, and $\xi^{\prime\prime}_{+}(0)=u$,
where

$\xi^{\prime\prime}_{+}(0):=\lim_{t\downarrow
0}\frac{\xi(t)-\xi(0)-t\xi^{\prime}_{+}(0)}{\frac{1}{2}t^{2}}.$

It is well known that if $C\subset{\mathbb{X}}$ is convex and parabolically
derivable at $\bar{x}$ for $w$, then the second-order tangent set
$T_{C}^{2}(\bar{x},w)$ is a nonempty convex set in ${\mathbb{X}}$ (cf. [2,
page 163]). Given the function $f:{\mathbb{X}}\to\overline{{\rm
I\\!R}}:=(-\infty,\infty]$, its domain and epigraph are defined, respectively,
by

$\mbox{\rm
dom}\,f=\big{\\{}x\in{\mathbb{X}}|\;f(x)<\infty\big{\\}}\quad\mbox{and}\quad\mbox{\rm
epi}\,f=\big{\\{}(x,\alpha)\in{\mathbb{X}}\times{\rm
I\\!R}|\,f(x)\leq\alpha\big{\\}}.$

The regular subdifferential of $f$ at $\bar{x}\in\mbox{\rm dom}\,f$ is defined
by

$\widehat{\partial}f(\bar{x})=\big{\\{}v\in{\mathbb{X}}\;|\;\liminf_{x\to\bar{x}}\frac{f(x)-f(\bar{x})-\langle
v,x-\bar{x}\rangle}{\|x-\bar{x}\|}\geq 0\big{\\}}.$

The subdifferential of $f$ at $\bar{x}$ is given by

$\displaystyle\partial
f(\bar{x})=\big{\\{}v\in{\mathbb{X}}\;|\;\exists\,x_{k}\stackrel{{\scriptstyle
f}}{{\to}}\bar{x},\;\;v_{k}\to
v\;\;\mbox{with}\;\;v_{k}\in\widehat{\partial}f(x_{k})\big{\\}},$

where $x_{k}\stackrel{{\scriptstyle f}}{{\to}}\bar{x}$ stands for
$x_{k}\to\bar{x}$ and $f(x_{k})\to f(\bar{x})$. We say that $v\in{\mathbb{X}}$
is a proximal subgradient of $f$ at $\bar{x}$ if there exists $r\in{\rm
I\\!R}_{+}$ and a neighborhood $U$ of $\bar{x}$ such that for all $x\in U$ we
have

$f(x)\geq f(\bar{x})+\langle v,x-\bar{x}\rangle-\frac{r}{2}\|x-\bar{x}\|^{2}.$
(2.1)

The set of all such $v$ is called the proximal subdifferential of $f$ at
$\bar{x}$ and is denoted by $\partial^{p}f(\bar{x})$. By definitions, it is
not hard to obtain the inclusions
$\partial^{p}f(\bar{x})\subset\widehat{\partial}f(\bar{x})\subset\partial
f(\bar{x})$. Given a nonempty set $C\subset{\mathbb{X}}$, the proximal and
regular normal cones to $C$ at $\bar{x}\in C$ are defined, respectively, by

$N^{p}_{C}(\bar{x}):=\partial^{p}\delta_{C}(\bar{x})\quad\mbox{and}\quad\widehat{N}_{C}(\bar{x}):=\widehat{\partial}\delta_{C}(\bar{x}).$

Similarly, we define the (limiting/Mordukhovich) normal cone of $C$ at
$\bar{x}$ by $N_{C}(\bar{x}):=\partial\delta_{C}(\bar{x})$. Consider a set-
valued mapping $S:{\mathbb{X}}\rightrightarrows{\mathbb{Y}}$ with its domain
and graph defined, respectively, by

$\mbox{\rm
dom}\,S=\big{\\{}x\in{\mathbb{X}}|\;S(x)\neq\emptyset\big{\\}}\quad\mbox{and}\quad\mbox{\rm
gph}\,S=\big{\\{}(x,y)\in{\mathbb{X}}\times{\mathbb{Y}}|\;y\in S(x)\big{\\}}.$

The graphical derivative of $S$ at $(\bar{x},\bar{y})\in\mbox{\rm gph}\,S$ is
defined by

$DS(\bar{x},\bar{y})(w)=\big{\\{}v\in{\mathbb{Y}}|\;(w,v)\in
T_{\scriptsize{\mbox{\rm gph}\,S}}(\bar{x},\bar{y})\big{\\}},\quad
w\in{\mathbb{X}}.$

Recall that a set-valued mapping
$S\colon{\mathbb{X}}\rightrightarrows{\mathbb{Y}}$ is metrically regular
around $(\bar{x},\bar{y})\in\mbox{\rm gph}\,S$ if there are constants
$\kappa\in{\rm I\\!R}_{+}$ and $\varepsilon>0$ such that the distance estimate

$d\big{(}x,S^{-1}(y)\big{)}\leq\kappa\,d\big{(}y,S(x)\big{)}\;\;\mbox{for
all}\quad(x,y)\in\mathbb{B}_{\varepsilon}(\bar{x},\bar{y})$

holds. When $y=\bar{y}$ in the above estimate, the mapping $S$ is called
metrically subregular at $(\bar{x},\bar{y})$. The set-valued mapping $S$ is
called strongly metrically subregular at $(\bar{x},\bar{y})$ if there are a
constant $\kappa\in{\rm I\\!R}_{+}$ and a neighborhood $U$ of $\bar{x}$ such
that the estimate

$\|x-\bar{x}\|\leq\kappa\,d(\bar{y},S(x))\;\;\mbox{for all}\;\;x\in U$

holds. It is known (cf. [8, Theorem 4E.1]) that the set-valued mapping $S$ is
strongly metrically subregular at $(\bar{x},\bar{y})$ if and only if we have

$0\in DS(\bar{x},\bar{y})(w)\implies w=0.$ (2.2)

Given a function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ and a point
$\bar{x}$ with $f(\bar{x})$ finite, the subderivative function ${\rm
d}f(\bar{x})\colon{\rm I\\!R}^{n}\to[-\infty,\infty]$ is defined by

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

Define the parametric family of second-order difference quotients for $f$ at
$\bar{x}$ for $\bar{v}\in{\mathbb{X}}$ by

$\Delta_{t}^{2}f(\bar{x},\bar{v})(w)=\dfrac{f(\bar{x}+tw)-f(\bar{x})-t\langle\bar{v},\,w\rangle}{\frac{1}{2}t^{2}}\quad\quad\mbox{with}\;\;w\in{\mathbb{X}},\;\;t>0.$

If $f(\bar{x})$ is finite, then the second subderivative of $f$ at $\bar{x}$
for $\bar{v}$ is given by

${\rm d}^{2}f(\bar{x},\bar{v})(w)=\liminf_{\begin{subarray}{c}t\downarrow 0\\\
w^{\prime}\to
w\end{subarray}}\Delta_{t}^{2}f(\bar{x},\bar{v})(w^{\prime}),\;\;w\in{\mathbb{X}}.$

Below, we collect some important properties of the second subderivative that
are used throughout this paper. Parts (i) and (ii) were taken from [21,
Proposition 13.5] and part (iii) was recently observed in [13, Theorem
4.1(i)].

######  Proposition 2.1 (properties of second subderivative).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ and
$(\bar{x},\bar{v})\in{\mathbb{X}}\times{\mathbb{X}}$ with $f(\bar{x})$ finite.
Then the following conditions hold:

  * (i)

the second subderivative ${\rm d}^{2}f(\bar{x},\bar{v})$ is a lower
semicontinuous (l.s.c.) function;

  * (ii)

if ${\rm d}^{2}f(\bar{x},\bar{v})$ is a proper function, meaning that ${\rm
d}^{2}f(\bar{x},\bar{v})(w)>-\infty$ for all $w\in{\mathbb{X}}$ and its
effective domain, defined by

$\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x},\bar{v})=\big{\\{}w\in{\mathbb{X}}|\,{\rm
d}^{2}f(\bar{x},\bar{v})(w)<\infty\big{\\}},$

is nonempty, then we always have the inclusion

$\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x},\bar{v})\subset\big{\\{}w\in{\mathbb{X}}|\,{{\rm
d}}f(\bar{x})(w)=\langle\bar{v},w\rangle\big{\\}};$

  * (iii)

if $\bar{v}\in\partial^{p}f(\bar{x})$, then for any $w\in{\mathbb{X}}$ we have
${\rm d}^{2}f(\bar{x},\bar{v})(w)\geq-r\|w\|^{2}$, where $r\in{\rm I\\!R}_{+}$
is taken from (2.1). In particular, ${\rm d}^{2}f(\bar{x},\bar{v})$ is a
proper function.

Following [21, Definition 13.6], a function $f:{\mathbb{X}}\to\overline{{\rm
I\\!R}}$ is said to be twice epi-differentiable at $\bar{x}$ for
$\bar{v}\in{\mathbb{X}}$, with $f(\bar{x})$ finite, if the sets $\mbox{\rm
epi}\,\Delta_{t}^{2}f(\bar{x},\bar{v})$ converge to $\mbox{\rm epi}\,{\rm
d}^{2}f(\bar{x},\bar{v})$ as $t\downarrow 0$. The latter means by [21,
Proposition 7.2] that for every sequence $t_{k}\downarrow 0$ and every
$w\in{\mathbb{X}}$, there exists a sequence $w_{k}\to w$ such that

${\rm
d}^{2}f(\bar{x},\bar{v})(w)=\lim_{k\to\infty}\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k}).$
(2.3)

We say that a function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ is Lipschitz
continuous around $\bar{x}$ relative to $C\subset\mbox{\rm dom}\,f$ with
constant $\ell\in{\rm I\\!R}_{+}$ if $\bar{x}\in C$ and there exists a
neighborhood $U$ of $\bar{x}$ such that

$|f(x)-f(y)|\leq\ell\,\|x-y\|\quad\mbox{for all }\;x,y\in U\cap C.$

Such a function is called locally Lipschitz continuous relative to $C$ if for
every $\bar{x}\in C$, it is Lipschitz continuous around $\bar{x}$ relative to
$C$. Piecewise linear-quadratic functions (not necessarily convex) and an
indicator function of a nonempty set are important examples of functions that
are locally Lipschitz continuous relative to their domains.

######  Proposition 2.2 (domain of subderivatives).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ be Lipschitz continuous around
$\bar{x}$ relative to its domain with constant $\ell\in{\rm I\\!R}_{+}$. Then
we have $\mbox{\rm dom}\,{\rm d}f(\bar{x})=T_{\scriptsize\mbox{\rm
dom}\,f}(\bar{x})$. In particular, for every $w\in T_{\scriptsize\mbox{\rm
dom}\,f}(\bar{x})$, the subderivative ${\rm d}f(\bar{x})(w)$ is finite.

[Proof. ]The inclusion $\mbox{\rm dom}\,{\rm d}f(\bar{x})\subset
T_{\scriptsize\mbox{\rm dom}\,f}(\bar{x})$ results directly from the
definition. To prove the opposite inclusion, pick $w\in
T_{\scriptsize\mbox{\rm dom}\,f}(\bar{x})$. This gives us some sequences
$t_{k}\downarrow 0$ and $w_{k}\to w$ such that $\bar{x}+t_{k}w_{k}\in\mbox{\rm
dom}\,f$ for all $k\in{\rm I\\!N}$. Using this and the Lipschitz continuity of
$f$ around $\bar{x}$ relative to its domain implies that for all $k$
sufficiently large we have

$|\frac{f(\bar{x}+t_{k}w_{k})-f(\bar{x})}{t_{k}}|\leq\ell\|w_{k}\|.$ (2.4)

This clearly yields $|{\rm d}f(\bar{x})(w)|\leq\ell\|w\|$. Thus ${\rm
d}f(\bar{x})(w)$ is finite and so $w\in\mbox{\rm dom}\,{\rm d}f(\bar{x})$.
This gives us the inclusion $T_{\scriptsize\mbox{\rm
dom}\,f}(\bar{x})\subset\mbox{\rm dom}\,{\rm d}f(\bar{x})$ and hence completes
the proof.

##  3  Twice Epi-Differetiability of Parabolically Regular Functions

This section aims to delineate conditions under which the twice epi-
differenibility of extend-real-valued functions can be established. To this
end, we appeal to an important second-order regularity condition, called
parabolic regularity, which was recently exploited in [14] to study a similar
property for constraint systems. We begin with the definition of this
regularity condition.

######  Definition 3.1 (parabolic regularity).

A function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ is parabolically regular
at $\bar{x}$ for $\bar{v}\in{\mathbb{X}}$ if $f(\bar{x})$ is finite and if for
any $w$ such that ${\rm d}^{2}f(\bar{x},\bar{v})(w)<\infty$, there exist,
among the sequences $t_{k}\downarrow 0$ and $w_{k}\to w$ with
$\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})\to{\rm
d}^{2}f(\bar{x},\bar{v})(w)$, those with the additional property that

$\limsup_{k\to\infty}\frac{\|w_{k}-w\|}{t_{k}}<\infty.$ (3.5)

A nonempty set $C\subset{\mathbb{X}}$ is said to be parabolically regular at
$\bar{x}$ for $\bar{v}$ if the indicator function $\delta_{C}$ is
parabolically regular at $\bar{x}$ for $\bar{v}$.

Although the notion of parabolic regularity was introduced first in [21,
Definition 13.65], its origin goes back to [5, Theorem 4.4], where Chaney
observed a duality relationship between his second-order generalized
derivative and the parabolic subderivative, defined in [1] by Ben-Tal and
Zowe. This duality relationship was derived later by Rockafellar [18,
Proposition 3.5] for convex piecewise linear-quadratic functions. As shown in
Proposition 3.6 below, the latter duality relationship is equivalent to the
concept of parabolic regularity from Definition 3.1 provided that $\bar{v}$,
appearing in Definition 3.1, is a proximal subgradient. A different second-
order regularity was introduced by Bonnans, Comminetti, and Shapiro [3,
Definition 3] for sets, which was later extended in [2, Definition 3.93] for
functions. It is not difficult to see that parabolic regularity is implied by
the second-order regularity in the sense of [3]; see [2, Proposition 3.103]
for a proof of this result. Moreover, the example from [2, page 215] shows
that the converse implication may not hold in general.

We showed in [14] that important sets appearing in constrained optimization
problems, including polyhedral convex sets, the second-order cone, and the
cone of positive semidefinite symmetric matrices, are parabolically regular.
Below, we add two important classes of functions for which this property
automatically fulfill. We begin first by convex piecewise-linear quadratic
functions and then consider eigenvalues functions. While the former was
justified in [21, Theorem 13.67], we provide below a different and simpler
proof.

######  Example 3.2 (piecewise linear-quadratic functions).

Assume that the function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ with
${\mathbb{X}}={\rm I\\!R}^{n}$ is convex piecewise linear-quadratic. Recall
that $f$ is called piecewise linear-quadratic if $\mbox{\rm
dom}\,f=\cup_{i=1}^{s}C_{i}$ with $s\in{\rm I\\!N}$ and $C_{i}$ being
polyhedral convex sets for $i=1,\ldots,s$, and if $f$ has a representation of
the form

$f(x)=\hbox{${1\over 2}$}\langle A_{i}x,x\rangle+\langle
a_{i},x\rangle+\alpha_{i}\quad\mbox{for all}\quad x\in C_{i},$

where $A_{i}$ is an $n\times n$ symmetric matrix, $a_{i}\in{\rm I\\!R}^{n}$,
and $\alpha_{i}\in{\rm I\\!R}$ for $i=1,\cdots,s$. It was proven in [21,
Propsoition 13.9] that the second subderivative of $f$ at $\bar{x}$ for
$\bar{v}\in\partial f(\bar{x})$ can be calculated by

${\rm d}^{2}f(\bar{x},\bar{v})(w)=\begin{cases}\langle
A_{i}w,w\rangle&\mbox{if}\;\;w\in
T_{C_{i}}(\bar{x})\cap\\{\bar{v}_{i}\\}^{\bot},\\\
\infty&\mbox{otherwise},\end{cases}$ (3.6)

where $\bar{v}_{i}:=\bar{v}-A_{i}\bar{x}-a_{i}$. To prove the parabolic
regularity of $f$ at $\bar{x}$ for $\bar{v}$, pick a vector $w\in{\rm
I\\!R}^{n}$ with ${\rm d}^{2}f(\bar{x},\bar{v})(w)<\infty$. This implies that
there is an $i$ with $1\leq i\leq s$ such that $w\in
T_{C_{i}}(\bar{x})\cap\\{\bar{v}_{i}\\}^{\bot}$. Since $C_{i}$ is a polyhedral
convex set, we conclude from [21, Exercise 6.47] that there exists an
$\varepsilon>0$ such that $\bar{x}+tw\in C_{i}$ for all $t\in[0,\varepsilon]$.
Pick a sequence $t_{k}\downarrow 0$ such that $t_{k}\in[0,\varepsilon]$ and
let $w_{k}:=w$ for all $k\in{\rm I\\!N}$. Thus a simple calculation tells us
that

$\begin{array}[]{lll}\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})=\dfrac{f(\bar{x}+t_{k}w_{k})-f(\bar{x})-t_{k}\langle\bar{v},\,w_{k}\rangle}{\frac{1}{2}t_{k}^{2}}\\\
~{}~{}~{}~{}=\dfrac{\frac{1}{2}\langle
A_{i}(\bar{x}+t_{k}w_{k}),\bar{x}+t_{k}w_{k}\rangle+\langle
a_{i},\bar{x}+t_{k}w_{k}\rangle+\alpha_{i}-\frac{1}{2}\langle
A_{i}\bar{x},\bar{x}\rangle-\langle
a_{i},\bar{x}\rangle-\alpha_{i}-t_{k}\langle\bar{v},\,w_{k}\rangle}{\frac{1}{2}t_{k}^{2}}\\\
~{}~{}~{}~{}=\langle A_{i}w,w\rangle+\dfrac{t_{k}\langle
w_{k},\bar{v}-A_{i}\bar{x}-a_{i}\rangle}{\frac{1}{2}t_{k}^{2}}=\langle
A_{i}w,w\rangle,\end{array}$

which in turn implies by (3.6) that
$\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})\to{\rm
d}^{2}f(\bar{x},\bar{v})(w)$ as $k\to\infty$. Since (3.5) is clearly holds,
$f$ is parabolic regular at $\bar{x}$ for $\bar{v}$.

######  Example 3.3 (eigenvalue functions).

Let ${\mathbb{X}}={{\mathbb{S}}}^{n}$ be the space of $n\times n$ symmetric
real matrices, which is conveniently treated via the inner product

$\langle A,B\rangle:=\mbox{\rm tr}\,AB$

with $\mbox{\rm tr}\,AB$ standing for the sum of the diagonal entries of $AB$.
For a matrix $A\in{{\mathbb{S}}}^{n}$, we denote by $A^{\dagger}$ the Moore-
Penrose pseudo-inverse of $A$ and by
$\mbox{eig}\,A=(\lambda_{1}(A),\ldots,\lambda_{n}(A))$ the vector of
eigenvalues of $A$ in decreasing order with eigenvalues repeated according to
their multiplicity. Given $i\in\\{1,\ldots,n\\}$, denote by $\ell_{i}(A)$ the
number of eigenvalues that are equal to $\lambda_{i}(A)$ but are ranked before
$i$ including $\lambda_{i}(A)$. This integer allows us to locate
$\lambda_{i}(A)$ in the group of the eigenvalues of $A$ as follows:

$\lambda_{1}(A)\geq\cdots\geq\lambda_{i-\ell_{i}(A)}>\lambda_{i-\ell_{i}(A)+1}(A)=\cdots=\lambda_{i}(A)\geq\cdots\geq\lambda_{n}(A).$

The eigenvalue $\lambda_{i-\ell_{i}(A)+1}(A)$, ranking first in the group of
eigenvalues equal to $\lambda_{i}(A)$, is called the leading eigenvalue. For
any $i\in\\{1,\ldots,n\\}$, define now the function
$\alpha_{i}:{{\mathbb{S}}}^{n}\to{\rm I\\!R}$ by

$\alpha_{i}(A)=\lambda_{i-\ell_{i}(A)+1}(A)+\cdots+\lambda_{i}(A),\quad
A\in{\mathbb{S}}^{n}.$ (3.7)

It was proven in [24, Theorem 2.1] that
$\widehat{\partial}\alpha_{i}(A)=\partial\alpha_{i}(A)$ and that the second
subderivative of $\alpha_{i}$ at $A$ for any $V\in\partial\alpha_{i}(A)$ is
calculated for every $W\in{{\mathbb{S}}}^{n}$ by

${\rm d}^{2}\alpha_{i}(A,V)(W)=\begin{cases}2\langle
V,W(\lambda_{i}(A)I_{n}-A)^{\dagger}W\rangle&\mbox{if}\;\;{\rm
d}\alpha_{i}(A)(W)=\langle X,W\rangle,\\\ \infty&\mbox{otherwise},\end{cases}$
(3.8)

where $I_{n}$ stands for the $n\times n$ identity matrix. Moreover, for any
$W\in{{\mathbb{S}}}^{n}$ with ${\rm d}^{2}\alpha_{i}(A,H)(W)<\infty$ and any
sequence $t_{k}\downarrow 0$, the proof of [24, Theorem 2.1] confirms that

$\Delta^{2}_{t_{k}}\alpha_{i}(A,V)(W_{k})\to{\rm
d}^{2}\alpha_{i}(A,V)(W)\quad\mbox{with}\;\;W_{k}:=W-t_{k}W(\lambda_{i}(A)I_{n}-A)^{\dagger}W.$

This readily verifies (3.5) and thus the functions $\alpha_{i}$,
$i\in\\{1,\ldots,n\\}$, are parabolically regular at $A$ for any
$V\in\partial\alpha_{i}(A)$. In particular, for $i=1$, the function
$\alpha_{i}$ from (3.7) boils down to the maximum eigenvalue function of a
matrix, namely

$\lambda_{\scriptsize\max}(A):=\alpha_{1}(A)=\lambda_{1}(A),\quad
A\in{\mathbb{S}}^{n}.$ (3.9)

So the maximum eigenvalue function $\lambda_{\max}$ is parabolically regular
at $A$ for any $V\in\partial\lambda_{\max}(A)$. This can be said for any
leading eigenvalue $\lambda_{i-\ell_{i}(A)+1}(A)$ since we have
$\alpha_{i}(B)=\lambda_{i-\ell_{i}(A)+1}(B)$ for every matrix
$B\in{\mathbb{S}}^{n}$ sufficiently close to $A$. Another important function
related to the eigenvalues of a matrix $A\in{\mathbb{S}}^{n}$ is the sum of
the first $i$ components of $\mbox{\rm eig}\,A$ with $i\in\\{1,\ldots,n\\}$,
namely

$\sigma_{i}(A)=\lambda_{1}(A)+\cdots+\lambda_{i}(A).$ (3.10)

It is well-known that the functions $\sigma_{i}$ are convex (cf. [21, Exercise
2.54]). Moreover, we have
$\sigma_{i}(A)=\alpha_{i}(A)+\sigma_{i-\ell_{i}(A)}(A)$. It follows from [24,
Proposition 1.3] that $\sigma_{i-\ell_{i}(A)}$ is twice continuously
differentiable (${\cal C}^{2}$-smooth) on ${{\mathbb{S}}}^{n}$. This together
with the parabolic regularity of $\alpha_{i}$ ensures that $\sigma_{i}$ are
parabolically regular at $A$ for any $V\in\partial\sigma_{i}(A)$.

To proceed further in this section, we require the concept of the parabolic
subderivative, introduced by Ben-Tal and Zowe in [1]. Let
$f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ and let $\bar{x}\in\mbox{\rm
dom}\,f$ and $w\in{\mathbb{X}}$ with ${\rm d}f(\bar{x})(w)$ finite. The
parabolic subderivative of $f$ at $\bar{x}$ for $w$ with respect to $z$ is
defined by

${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z):=\liminf_{\begin{subarray}{c}t\downarrow
0\\\ z^{\prime}\to
z\end{subarray}}\dfrac{f(\bar{x}+tw+\frac{1}{2}t^{2}z^{\prime})-f(\bar{x})-t{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t^{2}}.$

Recall from [21, Definition 13.59] that $f$ is called parabolically epi-
differentiable at $\bar{x}$ for $w$ if

$\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)=\big{\\{}z\in{\mathbb{X}}|\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)<\infty\big{\\}}\neq\emptyset,$

and for every $z\in{\mathbb{X}}$ and every sequence $t_{k}\downarrow 0$ there
exists a sequences $z_{k}\to z$ such that

${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)=\lim_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}.$ (3.11)

The main interest in parabolic subderivatives in this paper lies in its
nontrivial connection with second subderivatives. Indeed, it was shown in [21,
Proposition 13.64] that if the function $f:{\mathbb{X}}\to\overline{{\rm
I\\!R}}$ is finite at $\bar{x}$, then for any pair
$(\bar{v},w)\in{\mathbb{X}}\times{\mathbb{X}}$ with ${\rm
d}f(\bar{x})(w)=\langle w,\bar{v}\rangle$ we always have

${\rm d}^{2}f(\bar{x},\bar{v})(w)\leq\inf_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle\big{\\}}.$ (3.12)

As observed below, equality in this estimate amounts to the parabolic
regularity of $f$ at $\bar{x}$ for $\bar{v}$. To proceed, let
$f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ and pick
$(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial f$. The critical cone of $f$ at
$(\bar{x},\bar{v})$ is defined by

$K_{f}(\bar{x},\bar{v}):=\big{\\{}w\in{\mathbb{X}}\>|\>{\rm
d}f(\bar{x})(w)=\langle\bar{v},w\rangle\big{\\}}.$ (3.13)

When $f$ is the indicator function of a set, this definition boils down to the
classical definition of the critical cone for sets; see [8, page 109]. It is
not difficult to see that the set $K_{f}(\bar{x},\bar{v})$ is a cone in
${\mathbb{X}}$. Taking into account Proposition 2.1(ii), we conclude that the
domain of the second subderivative ${\rm d}^{2}f(\bar{x},\bar{v})$ is always
included in the critical cone $K_{f}(\bar{x},\bar{v})$ provided that ${\rm
d}^{2}f(\bar{x},\bar{v})$ is a proper function. The following result provides
conditions under which the domain of the second subderivative is the entire
critical cone.

######  Proposition 3.4 (domain of second subderivatives).

Assume that $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ is finite at $\bar{x}$
with $\bar{v}\in\partial^{p}f(\bar{x})$ and that for every $w\in
K_{f}(\bar{x},\bar{v})$ we have $\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)\neq\emptyset$.
Then for all $w\in K_{f}(\bar{x},\bar{v})$ we have

$-r\|w\|^{2}\leq{\rm
d}^{2}f(\bar{x},\bar{v})(w)\leq\inf_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle\big{\\}}<\infty,$ (3.14)

where $r\in{\rm I\\!R}_{+}$ is a constant satisfying (2.1). In particular, we
have $\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})=K_{f}(\bar{x},\bar{v})$.

[Proof. ]The lower estimate of ${\rm d}^{2}f(\bar{x},\bar{v})$ in (3.14)
results from Proposition 2.1(iii), which readily implies that ${\rm
d}^{2}f(\bar{x},\bar{v})(0)=0$. This tells us that the second subderivative
${\rm d}^{2}f(\bar{x},\bar{v})$ is proper. Employing now Proposition 2.1(ii)
gives us the inclusion $\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})\subset
K_{f}(\bar{x},\bar{v})$. The upper estimate of ${\rm
d}^{2}f(\bar{x},\bar{v})(w)$ in (3.14) directly comes from (3.12). By
assumptions, for any $w\in K_{f}(\bar{x},\bar{v})$, there exists a $z_{w}$ so
that ${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{w})<\infty$.
This guarantees that the infimum term in (3.14) is finite. Pick $w\in
K_{f}(\bar{x},\bar{v})$ and observe from (3.14) that ${\rm
d}^{2}f(\bar{x},\bar{v})(w)$ is finite. This yields the inclusion
$K_{f}(\bar{x},\bar{v})\subset\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})$,
which completes the proof.

The following example, taken from [21, page 636], shows the domain of the
second subderivative can be the entire set $K_{f}(\bar{x},\bar{v})$ even if
the assumption on the domain of the parabolic subderivative in Proposition 3.4
fails. As shown in the next section, however, this condition is automatically
satisfied for composite functions appearing in (1.1).

######  Example 3.5 (domain of second subderivative).

Define the function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ with
${\mathbb{X}}={\rm I\\!R}^{2}$ by
$f(x_{1},x_{2})=|x_{2}-x_{1}^{{4/3}}|-x_{1}^{2}$. As argued in [21, page 636],
the subderivative and subdifferential of $f$ at $\bar{x}=(0,0)$, respectively,
are

${\rm d}f(\bar{x})(w)=|w_{2}|\quad\mbox{and}\quad\partial
f(\bar{x})=\big{\\{}v=(v_{1},v_{2})\in{\rm I\\!R}^{2}|\,v_{1}=0,\,|v_{2}|\leq
1\big{\\}},$

where $w=(w_{1},w_{2})\in{\rm I\\!R}^{2}$. It is not hard to see that
$\bar{v}=(0,0)\in\partial^{p}f(\bar{x})$. Moreover, the second subderivative
of $f$ at $\bar{x}$ for $\bar{v}$ has a representation of the form

${\rm
d}^{2}f(\bar{x},\bar{v})(w)=\begin{cases}-2w_{1}^{2}&\mbox{if}\;\;w_{2}=0,\\\
\infty&\mbox{if}\;\;w_{2}\neq 0.\end{cases}$

Using the above calculation tells us that
$K_{f}(\bar{x},\bar{v})=\\{w=(w_{1},w_{2})|\,w_{2}=0\\}$. Thus we have
$\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})=K_{f}(\bar{x},\bar{v})$.
However, for any $w=(w_{1},w_{2})\in K_{f}(\bar{x},\bar{v})$ with $w_{1}\neq
0$ we have

${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)=\infty\quad\mbox{for
all}\;\;z\in{\rm I\\!R}^{2},$

which confirms that the assumption related to the domain of the parabolic
subderivative in Proposition 3.4 fails.

We proceed next by providing an important characterization of the parabolic
regularity that plays a key role in our developments in this paper.

######  Proposition 3.6 (characterization of parabolic regularity).

Assume that $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ is finite at $\bar{x}$
with $\bar{v}\in\partial^{p}f(\bar{x})$. Then the function $f$ is
parabolically regular at $\bar{x}$ for $\bar{v}$ if and only if we have

${\rm d}^{2}f(\bar{x},\bar{v})(w)=\inf_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle\big{\\}}$ (3.15)

for all $w\in K_{f}(\bar{x},\bar{v})$. Furthermore, for any $w\in\mbox{\rm
dom}\,{\rm d}^{2}f(\bar{x},\bar{v})$, there exists a $\bar{z}\in\mbox{\rm
dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$ such that

${\rm d}^{2}f(\bar{x},\bar{v})(w)={\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\bar{z})-\langle\bar{z},\bar{v}\rangle.$
(3.16)

[Proof. ]It follows from $\bar{v}\in\partial^{p}f(\bar{x})$ and Proposition
2.1(ii)-(iii) that the second subderivative ${\rm d}^{2}f(\bar{x},\bar{v})$ is
a proper function and

$\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})\subset K_{f}(\bar{x},\bar{v}).$
(3.17)

Assume now that $f$ is parabolically regular at $\bar{x}$ for $\bar{v}$. If
there exists a $w\in K_{f}(\bar{x},\bar{v})\setminus\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x},\bar{v})$, then (3.15) clearly holds due to (3.12). Suppose
now that $w\in\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})$. By Definition
3.1, there are sequences $t_{k}\downarrow 0$ and $w_{k}\to w$ for which we
have

$\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})\to{\rm
d}^{2}f(\bar{x},\bar{v})(w)\quad\mbox{and}\quad\limsup_{k\to\infty}\frac{\|w_{k}-w\|}{t_{k}}<\infty.$

Since the sequence $z_{k}:=2[w_{k}-w]/t_{k}$ is bounded, we can assume by
passing to a subsequence if necessary that $z_{k}\to\bar{z}$ as $k\to\infty$
for some $\bar{z}\in{\mathbb{X}}$. Thus we have
$w_{k}=w+\frac{1}{2}t_{k}z_{k}$ and

$\displaystyle{\rm d}^{2}f(\bar{x},\bar{v})(w)$ $\displaystyle=$
$\displaystyle\lim_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w_{k})-f(\bar{x})-t_{k}\langle\bar{v},w_{k}\rangle}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle=$
$\displaystyle\lim_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}\langle\bar{v},w\rangle}{\frac{1}{2}t_{k}^{2}}-\langle\bar{v},z_{k}\rangle$
$\displaystyle\geq$
$\displaystyle\liminf_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}-\langle\bar{v},\bar{z}\rangle$
$\displaystyle\geq$ $\displaystyle{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\bar{z})-\langle\bar{v},\bar{z}\rangle.$

Combining this and (3.12) implies that (3.15) and (3.16) hold for all
$w\in\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})$. To obtain the opposite
implication, assume that (3.15) holds for all $w\in K_{f}(\bar{x},\bar{v})$.
To prove the parabolic regularity of $f$ at $\bar{x}$ for $\bar{v}$, let ${\rm
d}^{2}f(\bar{x},\bar{v})(w)<\infty$, which by (3.17) yields $w\in
K_{f}(\bar{x},\bar{v})$. Employing now [21, Proposition 13.64] results in

${\rm d}^{2}f(\bar{x},\bar{v})(w)=\inf_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle\big{\\}}=\liminf_{\begin{subarray}{c}t\downarrow
0,\,w^{\prime}\to w\\\
[w^{\prime}-w]/t\,\,{\scriptsize\mbox{bounded}}\end{subarray}}\Delta_{t}^{2}f(\bar{x},\bar{v})(w^{\prime}).$

The last equality clearly justifies (3.5), and thus $f$ is parabolically
regular at $\bar{x}$ for $\bar{v}$. This completes the proof.

We next show that the indicator function of the cone of $n\times n$ positive
semidefinite symmetric matrices, denoted by ${{\mathbb{S}}}^{n}_{+}$, is
parabolic regular. This can be achieved via [14, Theorem 6.2] using the theory
of ${\cal C}^{2}$-cone reducible sets but below we give an independent proof
via Proposition 3.6.

######  Example 3.7 (parabolic regularity of ${{\mathbb{S}}}^{n}_{+}$).

Let ${{\mathbb{S}}}^{n}_{-}$ stand for the cone of $n\times n$ negative
semidefinite symmetric matrices. For any $A\in{\mathbb{S}}^{n}_{-}$, we are
going to show that $f:=\delta_{{\mathbb{S}}^{n}_{-}}$ is parabolic regular at
$A$ for any $V\in N_{{\mathbb{S}}^{n}_{-}}(A)$. Since we have
${\mathbb{S}}^{n}_{+}=-{\mathbb{S}}^{n}_{-}$, this clearly yields the same
property for ${\mathbb{S}}_{+}^{n}$. Using the notation in Example 3.3, we can
equivalently write

${\mathbb{S}}^{n}_{-}=\big{\\{}A\in{\mathbb{S}}^{n}|\,\lambda_{1}(A)\leq
0\big{\\}},$ (3.18)

which in turn implies that $\delta_{{\mathbb{S}}^{n}_{-}}(A)=\delta_{{\rm
I\\!R}_{-}}(\lambda_{1}(A))$ for any $A\in{\mathbb{S}}^{n}$. If $A$ is
negative definite, i.e., $\lambda_{1}(A)<0$, then our claim immediately
follows from $N_{{\mathbb{S}}^{n}_{-}}(A)=\\{0\\}$ for this case. Otherwise,
we have $\lambda_{1}(A)=0$. Pick $V\in N_{{\mathbb{S}}^{n}_{-}}(A)$ and
conclude from (3.18) and the chain rule from convex analysis that
$N_{{\mathbb{S}}^{n}_{-}}(A)={\rm I\\!R}_{+}\partial\lambda_{1}(A)$, which
implies that $V=rB$ for some $r\in{\rm I\\!R}_{+}$ and
$B\in\partial\lambda_{1}(A)$. If $r=0$, we get $V=0$ and parabolic regularity
of $\delta_{{\mathbb{S}}^{n}_{-}}$ at $A$ for $V$ follows directly from the
definition. Assume now $r>0$ and pick $W\in K_{f}(A,V)$. The latter amounts to

$\langle V,W\rangle={\rm d}\delta_{{\mathbb{S}}^{n}_{-}}(A)(W)=0\quad\mbox{and
}\;\;W\in T_{{\mathbb{S}}^{n}_{-}}(A).$

Employing now [2, Proposition 2.61] tells us that ${\rm
d}\lambda_{1}(A)(W)\leq 0$. Since $B\in\partial\lambda_{1}(A)$ and $\langle
B,W\rangle=0$, we arrive at ${\rm d}\lambda_{1}(A)(W)=0$. We know from [21,
Example 10.28] that

${\rm d}\lambda_{1}(A)(W)=\lim_{\begin{subarray}{c}t\downarrow 0\\\
W^{\prime}\to
W\end{subarray}}\Delta_{t}\lambda_{1}(A)(W^{\prime})\quad\mbox{with}\;\;\Delta_{t}\lambda_{1}(A)(W^{\prime}):=\frac{\lambda_{1}(A+tW^{\prime})-\lambda_{1}(A)}{t}.$

Using direct calculations, we conclude for any $t>0$ and
$W^{\prime}\in{\mathbb{S}}^{n}$ that

$\displaystyle\Delta_{t}^{2}\delta_{{\mathbb{S}}^{n}_{-}}(A,V)(W^{\prime})=\Delta_{t}^{2}\delta_{{\rm
I\\!R}_{-}}(\lambda_{1}(A),r)(\Delta_{t}\lambda_{1}(A)(W^{\prime}))+r\Delta_{t}^{2}\lambda_{1}(A,B)(W^{\prime}),$

which in turn results in

${\rm d}^{2}\delta_{{\mathbb{S}}^{n}_{-}}(A,V)(W)\geq{\rm d}^{2}\delta_{{\rm
I\\!R}_{-}}(\lambda_{1}(A),r)({\rm d}\lambda_{1}(A)(W))+r{\rm
d}^{2}\lambda_{1}(A,B)(W).$

Since $r>0$, $\lambda_{1}(A)=0$, and ${\rm d}\lambda_{1}(A)(W)=0$, we conclude
from [14, Example 3.4] that

${\rm d}^{2}\delta_{{\rm I\\!R}_{-}}(\lambda_{1}(A),r)({\rm
d}\lambda_{1}(A)(W))=\delta_{K_{{\rm
I\\!R}_{-}}(\lambda_{1}(A),r)}(0)=\delta_{\\{0\\}}(0)=0.$

Using this together with (3.8) brings us to

${\rm d}^{2}\delta_{{\mathbb{S}}^{n}_{-}}(A,V)(W)\geq-2r\langle
B,WA^{\dagger}W\rangle=-2\langle V,WA^{\dagger}W\rangle.$

On the other hand, we conclude from (3.14) that

${\rm
d}^{2}\delta_{{\mathbb{S}}^{n}_{-}}(A,V)(W)\leq-\sigma_{T^{2}_{{\mathbb{S}}^{n}_{-}}(A,W)}(V)=-2\langle
V,WA^{\dagger}W\rangle,$

where the last equality comes from [2, page 487] with
$\sigma_{T^{2}_{{\mathbb{S}}^{n}_{-}}(A,W)}$ standing for the support function
of $T^{2}_{{\mathbb{S}}^{n}_{-}}(A,W)$. Combining these confirms that

${\rm
d}^{2}\delta_{{\mathbb{S}}^{n}_{-}}(A,V)(W)=-\sigma_{T^{2}_{{\mathbb{S}}^{n}_{-}}(A,W)}(V)=-2\langle
V,WA^{\dagger}W\rangle\quad\mbox{for all}\;\;W\in K_{f}(A,V).$

This together with Proposition 3.6 tells us that ${{\mathbb{S}}^{n}_{-}}$ is
parabolic regular at $A$ for $V$.

We are now in a position to establish the main result of this section, which
states that parabolically regular functions are always twice epi-
differentiable.

######  Theorem 3.8 (twice epi-differenitability of parabolically regular
functions).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ be finite at $\bar{x}$ and
$\bar{v}\in\partial^{p}f(\bar{x})$ and let $f$ be parabolically epi-
differentiable at $\bar{x}$ for every $w\in K_{f}(\bar{x},\bar{v})$. If $f$ is
parabolically regular at $\bar{x}$ for $\bar{v}$, then it is properly twice
epi-differentiable at $\bar{x}$ for $\bar{v}$ with

${\rm
d}^{2}f(\bar{x},\bar{v})(w)=\left\\{\begin{array}[]{ll}\min_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle\big{\\}}&\mbox{if }\;\;w\in K_{f}(\bar{x},\bar{v}),\\\
+\infty&\mbox{otherwise}.\end{array}\right.$ (3.19)

[Proof. ]It follows from the parabolic epi-differentiability of $f$ at
$\bar{x}$ for every $w\in K_{f}(\bar{x},\bar{v})$ and Proposition 3.4 that
$\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})=K_{f}(\bar{x},\bar{v})$. This
together with (3.15) and (3.16) justifies the second subderivative formula
(3.19). To establish the twice epi-differentiability of $f$ at $\bar{x}$ for
$\bar{v}$, we are going to show that (2.3) holds for all $w\in{\mathbb{X}}$.
Pick $w\in K_{f}(\bar{x},\bar{v})$ and an arbitrary sequence $t_{k}\downarrow
0$. Since $f$ is parabolically regular at $\bar{x}$ for $\bar{v}$, by
Proposition 3.6, we find a $\bar{z}\in{\mathbb{X}}$ such that

${\rm d}^{2}f(\bar{x},\bar{v})(w)={\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\bar{z})-\langle\bar{z},\bar{v}\rangle.$
(3.20)

By the parabolic epi-differentiability of $f$ at $\bar{x}$ for $w$, we find a
sequence $z_{k}\to\bar{z}$ for which we have

${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\bar{z})=\lim_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}.$

Define $w_{k}:=w+\frac{1}{2}t_{k}z_{k}$ for all $k\in{\rm I\\!N}$. Using this
and $w\in K_{f}(\bar{x},\bar{v})$, we obtain

$\displaystyle\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})$ $\displaystyle=$
$\displaystyle\dfrac{f(\bar{x}+t_{k}w_{k})-f(\bar{x})-t_{k}\langle\bar{v},w_{k}\rangle}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle=$
$\displaystyle\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}-\langle\bar{v},z_{k}\rangle.$

This together with (3.20) results in

$\lim_{k\to\infty}\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})={\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\bar{z})-\langle\bar{v},\bar{z}\rangle={\rm
d}^{2}f(\bar{x},\bar{v})(w),$

which justifies (2.3) for every $w\in K_{f}(\bar{x},\bar{v})$. Finally, we are
going to show the validity of (2.3) for every $w\notin
K_{f}(\bar{x},\bar{v})$. For any such a $w$, we conclude from (3.19) that
${\rm d}^{2}f(\bar{x},\bar{v})(w)=\infty$. Pick an arbitrary sequence
$t_{k}\downarrow 0$ and set $w_{k}:=w$ for all $k\in{\rm I\\!N}$. Thus we have

$\infty={\rm
d}^{2}f(\bar{x},\bar{v})(w)\leq\liminf_{k\to\infty}\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})\leq\limsup_{t\downarrow
0}\Delta_{t_{k}}^{2}f(\bar{x},\bar{v})(w_{k})\leq\infty={\rm
d}^{2}f(\bar{x},\bar{v})(w),$

which again proves (2.3) for all $w\notin K_{f}(\bar{x},\bar{v})$. This
completes the proof of the Theorem.

The above theorem provides a very important generalization of a similar result
obtained recently by the authors and Mordukhovich in [14, Theorem 3.6] in
which the twice epi-differentiability of set indicator functions was
established. It is not hard to see that the assumptions of Theorem 3.8 boils
down to those in [14, Theorem 3.6]. To the best of our knowledge, the only
results related to the twice epi-differentiability of functions, beyond set
indicator functions, are [21, Theorem 13.14] and [24, Theorem 3.1] in which
this property was proven for the fully amenable and eigenvalue functions,
respectively. We will derive these results in Section 5 as an immediate
consequence of our chain rule for the second subderivative.

We proceed with an important consequence of Theorem 3.8 in which the proto-
differentiability of subgradient mappings is established under parabolic
regularity. Recall that a set-valued mapping
$S:{\mathbb{X}}\rightrightarrows{\mathbb{Y}}$ is said to be proto-
differentiable at $\bar{x}$ for $\bar{y}$ with $(\bar{x},\bar{y})\in\mbox{\rm
gph}\,S$ if the set $\mbox{\rm gph}\,S$ is geometrically derivable at
$(\bar{x},\bar{y})$. When this condition holds for the set-valued mapping $S$
at $\bar{x}$ for $\bar{y}$, we refer to $DS(\bar{x},\bar{y})$ as the proto-
derivative of $S$ at $\bar{x}$ for $\bar{y}$. The connection between the twice
epi-differentiablity of a function and the proto-differentiability of its
subgradient mapping was observed first by Rockafellar in [20] for convex
functions and was extended later in [16] for prox-regular functions. Recall
that a function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ is called prox-
regular at $\bar{x}$ for $\bar{v}$ if $f$ is finite at $\bar{x}$ and is
locally l.s.c. around $\bar{x}$ with $\bar{v}\in\partial f(\bar{x})$ and there
are constant $\varepsilon>0$ and $r\geq 0$ such that for all
$x\in\mathbb{B}_{\varepsilon}(\bar{x})$ with $f(x)\leq f(\bar{x})+\varepsilon$
we have

$\displaystyle f(x)\geq f(u)+\langle v,x-u\rangle-\hbox{${r\over
2}$}\|x-u\|^{2}\quad\quad\mbox{for all}\quad(u,v)\in(\mbox{\rm gph}\,\partial
f)\cap\mathbb{B}_{\varepsilon}(\bar{x},\bar{v}).$

Moreover, we say that $f$ is subdifferentially continuous at $\bar{x}$ for
$\bar{v}$ if $(x_{k},v_{k})\to(\bar{x},\bar{v})$ with $v_{k}\in\partial
f(x_{k})$, one has $f(x_{k})\to f(\bar{x})$.

######  Corollary 3.9 (proto-differentiability under parabolic regularity).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ be prox-regular and
subdifferentially continuous at $\bar{x}$ for $\bar{v}$ and let $f$ be
parabolically epi-differentiable at $\bar{x}$ for every $w\in
K_{f}(\bar{x},\bar{v})$. If $f$ is parabolically regular at $\bar{x}$ for
$\bar{v}$, then the following equivalent conditions hold:

  * (i)

the function $f$ is twice epi-differentiable at $\bar{x}$ for $\bar{v}$;

  * (ii)

the subgradient mapping $\partial f$ is proto-differentiable at $\bar{x}$ for
$\bar{v}$.

Furthermore, the proto-derivative of the subgradient mapping $\partial f$ at
$\bar{x}$ for $\bar{v}$ can be calculated by

$D(\partial f)(\bar{x},\bar{v})(w)=\partial\big{(}\hbox{${1\over 2}$}{\rm
d}^{2}f(\bar{x},\bar{v})\big{)}(w)\quad\mbox{for all}\;\;w\in{\mathbb{X}}.$
(3.21)

[Proof. ]Note that $\bar{v}\in\partial^{p}f(\bar{x})$ since $f$ is prox-
regular at $\bar{x}$ for $\bar{v}$. Employing now Theorem 3.8 gives us (i).
The equivalence between (i) and (ii) and the validity of (3.21) come from [21,
Theorem 13.40].

##  4 Variational Properties of Parabolic Subderivatives

This section is devoted to second-order analysis of parabolic subderivatives
of extended-real-valued functions that are locally Lipschitz continuous
relative to their domains. We pay special attention to functions that are
expressed as a composition of a convex function and a twice differentiable
function. We begin with the following result that gives us sufficient
conditions for finding the domain of the parabolic subderivative.

######  Proposition 4.1 (properties of parabolic subderivatives).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ be finite at $\bar{x}$ and let
$f$ be Lipschitz continuous around $\bar{x}$ relative to its domain with
constant $\ell\in{\rm I\\!R}_{+}$. Assume that $w\in T_{\scriptsize\mbox{\rm
dom}\,f}(\bar{x})$ and that $f$ is parabolic epi-differentiable at $\bar{x}$
for $w$. Then the following conditions hold:

  * (i)

$\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)=T_{\scriptsize\mbox{\rm
dom}\,f}^{2}(\bar{x},w)$;

  * (ii)

$\mbox{\rm dom}\,f$ is parabolically derivable at $\bar{x}$ for $w$.

[Proof. ]Since $w\in T_{\scriptsize\mbox{\rm dom}\,f}(\bar{x})$, we conclude
from Proposition 2.2 that ${\rm d}f(\bar{x})(w)$ is finite. To prove (i),
observe first that by definition, we always have the inclusion

$\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)\subset
T_{\scriptsize\mbox{\rm dom}\,f}^{2}(\bar{x},w).$ (4.1)

To obtain the opposite inclusion, take $z\in T_{\scriptsize\mbox{\rm
dom}\,f}^{2}(\bar{x},w)$. This tells us that there exist sequences
$t_{k}\downarrow 0$ and $z_{k}\to z$ so that
$\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k}\in\mbox{\rm dom}\,f$. Since $f$ is
parabolically epi-differentiable at $\bar{x}$ for $w$, we have $\mbox{\rm
dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)\neq\emptyset$.
Thus there exists a $z_{w}\in{\mathbb{X}}$ such that ${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{w})<\infty$.
Moreover, corresponding to the sequence $t_{k}$, we find another sequence
$z^{\prime}_{k}\to z_{w}$ such that

${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{w})=\lim_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z^{\prime}_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}.$

Since ${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{w})<\infty$,
we can assume without loss of generality that
$\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z^{\prime}_{k}\in\mbox{\rm dom}\,f$ for
all $k\in{\rm I\\!N}$. Using these together with the Lipschitz continuity of
$f$ around $\bar{x}$ relative to its domain, we have for all $k$ sufficiently
large that

$\displaystyle\frac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}$ $\displaystyle=$
$\displaystyle\frac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z^{\prime}_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle+\frac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z^{\prime}_{k})}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle\leq$
$\displaystyle\frac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z^{\prime}_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\hbox{${1\over 2}$}t_{k}^{2}}$
$\displaystyle+\ell\|z_{k}-z^{\prime}_{k}\|.$

Passing to the limit results in the inequality

${\rm d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)\leq{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{w})+\ell\|z-z_{w}\|,$
(4.2)

which in turn yields ${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)<\infty$, i.e.,
$z\in\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$. This
justifies the opposite inclusion in (4.1) and hence proves (i).

Turning now to (ii), we conclude from (4.1) and the parabolic epi-
differentiability of $f$ at $\bar{x}$ for $w$ that the second-order tangent
set $T_{\scriptsize\mbox{\rm dom}\,f}^{2}(\bar{x},w)$ is nonempty. Moreover,
it follows from [21, Example 13.62(b)] that the parabolic epi-
differentiability of $f$ at $\bar{x}$ for $w$ yields the parabolic
derivability of $\mbox{\rm epi}\,f$ at $(\bar{x},f(\bar{x}))$ for $(w,{\rm
d}f(\bar{x})(w))$. The latter clearly enforces the same property for
$\mbox{\rm dom}\,f$ at $\bar{x}$ for $w$ and hence completes the proof.

It is important to notice the parabolic epi-differentiability of $f$ in
Proposition 4.1 is essential to ensure that condition (i) therein, namely the
characterization of the domain of the parabolic subderivative, is satisfied.
Indeed, as mentioned in the proof of this proposition, inclusion (4.1) always
holds. If the latter condition fails, this inclusion can be strict. For
example, the function $f$ from Example 3.5 is not parabolic epi-differentiable
at $\bar{x}=(0,0)$ for any vector $w=(w_{1},w_{2})\in K_{f}(\bar{x},\bar{v})$
with $w_{1}\neq 0$ since $\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)=\emptyset$.
On the other hand, we have $\mbox{\rm dom}\,f={\rm I\\!R}^{2}$ and thus
$T_{\scriptsize\mbox{\rm dom}\,f}^{2}(\bar{x},w)={\rm I\\!R}^{2}$ for any such
a vector $w\in K_{f}(\bar{x},\bar{v})$, and so condition (i) in Proposition
4.1 fails.

Given a function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ finite at
$\bar{x}$, in the rest of this paper, we mainly focus on the case when this
function has a representation of the form

$f(x)=(g\circ F)(x)\quad\mbox{for all}\;\;x\in{\cal O},$ (4.3)

where ${\cal O}$ is a neighborhood of $\bar{x}$ and where the functions $F$
and $g$ are satisfying the following conditions:

  * •

$F:{\mathbb{X}}\to{\mathbb{Y}}$ is twice differentiable at $\bar{x}$;

  * •

$g:{\mathbb{Y}}\to\overline{{\rm I\\!R}}$ is proper, l.s.c., convex, and
Lipschitz continuous around $F(\bar{x})$ relative to its domain with constant
$\ell\in{\rm I\\!R}_{+}$.

It is not hard to see that the imposed assumptions on $g$ from representation
(4.3) implies that $\mbox{\rm dom}\,g$ is locally closed around $F(\bar{x})$,
namely for some $\varepsilon>0$ the set $(\mbox{\rm
dom}\,g)\cap\mathbb{B}_{\varepsilon}(F(\bar{x}))$ is closed. Taking the
neighborhood ${\cal O}$ from (4.3), we obtain

$(\mbox{\rm dom}\,f)\cap{\cal O}=\big{\\{}x\in{\cal O}|\>F(x)\in\mbox{\rm
dom}\,g\big{\\}}.$ (4.4)

It has been well understood that the second-order variational analysis of the
composite form (4.3) requires a certain qualification condition. The following
definition provides the one we utilize in this paper.

######  Definition 4.2 (metric subregularity constraint qualification).

Assume that the function $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ has
representation (4.3) around $\bar{x}\in\mbox{\rm dom}\,f$. We say that the
metric subregularity constraint qualification holds for the constraint set
(4.4) at $\bar{x}$ if there exist a constants $\kappa\in{\rm I\\!R}_{+}$ and a
neighborhood $U$ of $\bar{x}$ such that

$d(x,\mbox{\rm dom}\,f)\leq\kappa\>d(F(x),\mbox{\rm dom}\,g)\quad\mbox{for
all}\;\;x\in U.$ (4.5)

By definition, the metric subregularity constraint qualification for the
constraint set (4.4) at $\bar{x}$ amounts to the metric subregularity of the
mapping $x\mapsto F(x)-\mbox{\rm dom}\,g$ at $(\bar{x},0)$. The more
traditional and well known constraint qualification for (4.3) is

$\partial^{\infty}g\big{(}F(\bar{x})\big{)}\cap\mbox{\rm ker}\,\nabla
F(\bar{x})^{*}=\\{0\\},$

where $\partial^{\infty}\varphi(\bar{x})$ stands for the singular
subdifferential of $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ at
$\bar{x}\in\mbox{\rm dom}\,\varphi$ defined by

$\partial^{\infty}\varphi(\bar{x}):=\big{\\{}v\in{\rm
I\\!R}^{n}\big{|}\;(v,0)\in N_{{\scriptsize\mbox{\rm
epi}\,\varphi}}\big{(}\bar{x},\varphi(\bar{x})\big{)}\big{\\}}.$

By the coderivative criterion from [12, Theorem 3.3], the latter constraint
qualification amounts to the metric regularity of the mapping
$(x,\alpha)\mapsto(F(x),\alpha)-\mbox{\rm epi}\,g$ around
$\big{(}(\bar{x},g(F(\bar{x}))),(0,0)\big{)}$. Since $g$ is convex, by [12,
Proposition 1.25], the aforementioned constraint qualification can be
equivalently written as

$N_{\scriptsize\mbox{\rm dom}\,g}\big{(}F(\bar{x})\big{)}\cap\mbox{\rm
ker}\,\nabla F(\bar{x})^{*}=\\{0\\},$ (4.6)

which by the coderivative criterion from [12, Theorem 3.3] is equivalent to
the metric regularity of the mapping $x\mapsto F(x)-\mbox{\rm dom}\,g$ around
$(\bar{x},0)$. Thus, for the composite form (4.3), the metric regularity of
$(x,\alpha)\mapsto(F(x),\alpha)-\mbox{\rm epi}\,g$ around
$\big{(}(\bar{x},g(F(\bar{x}))),(0,0)\big{)}$ amounts to that of $x\mapsto
F(x)-\mbox{\rm dom}\,g$ around $(\bar{x},0)$. This may not be true if the
metric regularity is replaced with the metric subregularity; see [13,
Proposition 3.1] and [13, Example 3.3] for more details and discussions about
these conditions. So, it is worth reiterating that instead of using the metric
subregularity of the epigraphical mapping, our second-order variational
analysis will be carried out under a weaker (and simpler) metric subregularity
of the domain mapping.

As observed recently in [13], (4.5) suffices to conduct first- and second-
order variational analysis of (4.3) when the convex function $g$ therein is
merely piecewise linear-quadratic. In what follows, we will show using a
different approach that such results can be achieved for (4.3) as well. We
continue our analysis by recalling the following first- and second-order chain
rules, obtained recently in [13, 14].

######  Proposition 4.3 (first- and second-order chain rules).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ have the composite
representation (4.3) at $\bar{x}\in\mbox{\rm dom}\,f$ and $\bar{v}\in\partial
f(\bar{x})$ and let the metric subregularity constraint qualification hold for
the constraint set (4.4) at $\bar{x}$. Then the following hold:

  * (i)

for any $w\in{\mathbb{X}}$, the following subderivative chain rule for $f$ at
$\bar{x}$ holds:

${\rm d}f(\bar{x})(w)={\rm d}g(F(\bar{x}))(\nabla F(\bar{x})w);$

  * (ii)

we have the chain rules

$\partial^{p}f(\bar{x})=\partial f(\bar{x})=\nabla F(\bar{x})^{*}\partial
g(F(\bar{x}))\quad\mbox{and}\quad T_{\scriptsize\mbox{\rm
dom}\,f}(\bar{x})=\big{\\{}w\in{\mathbb{X}}|\;\nabla F(\bar{x})w\in
T_{\scriptsize\mbox{\rm dom}\,g}(F(\bar{x}))\big{\\}}.$

If, in addition, $w\in T_{\scriptsize\mbox{\rm dom}\,f}(\bar{x})$ and the
function $g$ from (4.3) is parabolically epi-differentiable at $F(\bar{x})$
for $\nabla F(\bar{x})w$, then we have

$z\in T^{2}_{\scriptsize\mbox{\rm dom}\,f}(\bar{x},w)\iff\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w)\in T^{2}_{\scriptsize\mbox{\rm
dom}\,g}\big{(}F(\bar{x}),\nabla F(\bar{x})w\big{)}.$ (4.7)

Moreover, $\mbox{\rm dom}\,f$ is parabolically derivable at $\bar{x}$ for $w$.

[Proof. ]The subderivative chain rule in (i) was established recently in [13,
Theorem 3.4]. The subdifferential chain rule in (ii) was taken from [13,
Theorem 3.6]. As mentioned in Section 2, the inclusion
$\partial^{p}f(\bar{x})\subset\partial f(\bar{x})$ always holds. The opposite
inclusion can be justified using the aforementioned subdifferential chain rule
and the convexity of $g$; see [13, Theorem 4.4] for a similar result. The
chain rule for the tangent cone to $\mbox{\rm dom}\,f$ at $\bar{x}$ results
from Proposition 2.2 and the subderivative chain rule for $f$ at $\bar{x}$ in
(i). If in addition $w\in T_{\scriptsize\mbox{\rm dom}\,f}(\bar{x})$ and $g$
is parabolically epi-differentiable at $F(\bar{x})$ for $\nabla F(\bar{x})w$,
then it follows from Proposition 4.1 that $\mbox{\rm dom}\,g$ is parabolically
derivable at $F(\bar{x})$ for $\nabla F(\bar{x})w$. Appealing now to [14,
Theorem 4.5] implies that $\mbox{\rm dom}\,f$ is parabolically derivable at
$\bar{x}$ for $w$. Finally, the chain rule (4.7) was taken from [14, Theorem
4.5]. This completes the proof.

We continue by establishing a chain rule for the parabolic subderivative,
which is important for our developments in the next section.

######  Theorem 4.4 (chain rule for parabolic subderivatives).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ have the composite
representation (4.3) at $\bar{x}\in\mbox{\rm dom}\,f$ and $w\in
T_{\scriptsize\mbox{\rm dom}\,f}(\bar{x})$ and let the metric subregularity
constraint qualification hold for the constraint set (4.4) at $\bar{x}$.
Assume that the function $g$ from (4.3) is parabolically epi-differentiable at
$F(\bar{x})$ for $\nabla F(\bar{x})w$. Then the following conditions are
satisfied:

  * (i)

for any $z\in{\mathbb{X}}$ we have

${\rm d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)={\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w));$ (4.8)

  * (ii)

the domain of the parabolic subderivative of $f$ at $\bar{x}$ for $w$ is given
by

$\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)=T_{\scriptsize\mbox{\rm
dom}\,f}^{2}(\bar{x},w);$

  * (iii)

$f$ is parabolically epi-differentiable at $\bar{x}$ for $w$.

[Proof. ]Pick $z\in{\mathbb{X}}$ and set $u:=\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w)$. We prove (i)-(iii) in a parallel way.
Assume that $z\notin T_{\scriptsize\mbox{\rm dom}\,f}^{2}(\bar{x},w)$. As
mentioned in the proof of Proposition 4.1, inclusion (4.1) always holds. This
implies that ${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)=\infty$. On
the other hand, by (4.7) we get $u\notin T^{2}_{\scriptsize\mbox{\rm
dom}\,g}\big{(}F(\bar{x}),\nabla F(\bar{x})w\big{)}$. Employing Proposition
4.1(i) for the function $g$ and $\nabla F(\bar{x})w\in T_{\scriptsize\mbox{\rm
dom}\,g}(F(\bar{x}))$ gives us

$\mbox{\rm dom}\,{\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\cdot)=T_{\scriptsize\mbox{\rm
dom}\,g}^{2}(F(\bar{x}),\nabla F(\bar{x})w).$ (4.9)

Combining these tells us that ${\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u)=\infty,$ which in
turn justifies (4.8) for every $z\notin T_{\scriptsize\mbox{\rm
dom}\,f}^{2}(\bar{x},w)$. Consider an arbitrary sequence $t_{k}\downarrow 0$
and set $z_{k}:=z$ for all $k\in{\rm I\\!N}$. Then we have

$\displaystyle{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)$
$\displaystyle\leq$
$\displaystyle\liminf_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}$ $\displaystyle\leq$
$\displaystyle\limsup_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}$ $\displaystyle\leq$
$\displaystyle\infty={\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z),$

which in turn justifies (3.11) for all $z\notin T_{\scriptsize\mbox{\rm
dom}\,f}^{2}(\bar{x},w)$.

Since $g$ is parabolically epi-differentiable at $F(\bar{x})$ for $\nabla
F(\bar{x})w$, Proposition 4.1(ii) tells us that $\mbox{\rm dom}\,g$ is
parabolically derivable at $F(\bar{x})$ for $\nabla F(\bar{x})w$. We conclude
from Proposition 4.3 that $\mbox{\rm dom}\,f$ is parabolically derivable at
$\bar{x}$ for $w$. In particular, we have

$T_{\scriptsize\mbox{\rm dom}\,f}^{2}(\bar{x},w)\neq\emptyset.$ (4.10)

Pick now $z\in T_{\scriptsize\mbox{\rm dom}\,f}^{2}(\bar{x},w)$ and then
consider an arbitrary sequence $t_{k}\downarrow 0$. Thus, by definition, for
the aforementioned sequence $t_{k}$, we find a sequence $z_{k}\to z$ as
$k\to\infty$ such that

$x_{k}:=\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k}\in\mbox{\rm
dom}\,f\quad\mbox{for all}\;\;k\in{\rm I\\!N}.$ (4.11)

Moreover, since $g$ is parabolically epi-differentiable at $F(\bar{x})$ for
$\nabla F(\bar{x})w$, we find a sequence $u_{k}\to u$ such that

${\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u)=\lim_{k\to\infty}\dfrac{g(F(\bar{x})+t_{k}\nabla
F(\bar{x})w+\frac{1}{2}t_{k}^{2}u_{k})-g(F(\bar{x}))-t_{k}{\rm
d}g(F(\bar{x}))(\nabla F(\bar{x})w)}{\frac{1}{2}t_{k}^{2}}.$ (4.12)

It follows from (4.7) that $u\in T^{2}_{\scriptsize\mbox{\rm
dom}\,g}\big{(}F(\bar{x}),\nabla F(\bar{x})w\big{)}$. Combining this with
(4.9) tells us that ${\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u)<\infty$. This implies
that $y_{k}:=F(\bar{x})+t_{k}\nabla
F(\bar{x})w+\frac{1}{2}t_{k}^{2}u_{k}\in\mbox{\rm dom}\,g$ for all $k$
sufficiently large. Remember that $g$ is Lipschitz continuous around
$F(\bar{x})$ relative to its domain with constant $\ell$. Using this together
with Proposition 4.3(i), (4.11), and (4.12), we obtain

$\displaystyle{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)$
$\displaystyle\leq$
$\displaystyle\liminf_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}$ (4.13) $\displaystyle\leq$
$\displaystyle\limsup_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}$ $\displaystyle=$
$\displaystyle\limsup_{k\to\infty}\dfrac{g(F(x_{k}))-g(F(\bar{x}))-t_{k}{\rm
d}g(F(\bar{x}))(\nabla F(\bar{x})w)}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle\leq$
$\displaystyle\lim_{k\to\infty}\dfrac{g(y_{k})-g(F(\bar{x}))-t_{k}{\rm
d}g(F(\bar{x}))(\nabla
F(\bar{x})w)}{\frac{1}{2}t_{k}^{2}}+\limsup_{k\to\infty}\dfrac{g(F(x_{k}))-g(y_{k})}{\frac{1}{2}t_{k}^{2}}$
$\displaystyle\leq$ $\displaystyle{\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u)+\limsup_{k\to\infty}\ell\|\nabla
F(\bar{x})z_{k}+\nabla^{2}F(\bar{x})(w,w)-u_{k}+\frac{o(t_{k}^{2})}{t_{k}^{2}}\|$
$\displaystyle=$ $\displaystyle{\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u).$

On the other hand, it is not hard to see that for any $z\in{\mathbb{X}}$, we
always have

${\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u)\leq{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z).$

Combining this and (4.13) implies that

${\rm d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)={\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u)$

and that

${\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)=\lim_{k\to\infty}\dfrac{f(\bar{x}+t_{k}w+\frac{1}{2}t_{k}^{2}z_{k})-f(\bar{x})-t_{k}{\rm
d}f(\bar{x})(w)}{\frac{1}{2}t_{k}^{2}}.$

These prove (4.8) and (3.11) for any $z\in T_{\scriptsize\mbox{\rm
dom}\,f}^{2}(\bar{x},w)$, respectively, and hence we finish the proof of (i).

Next, we are going to verify (ii). We already know that inclusion (4.1) always
holds. To derive the opposite inclusion, pick $z\in T_{\scriptsize\mbox{\rm
dom}\,f}^{2}(\bar{x},w)$, which amounts to $u\in T^{2}_{\scriptsize\mbox{\rm
dom}\,g}\big{(}F(\bar{x}),\nabla F(\bar{x})w\big{)}$ due to (4.7). By (i) and
(4.9), we obtain

${\rm d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)={\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u)<\infty.$

This tells us that $z\in\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$ and hence
completes the proof of (ii).

Finally, to justify (iii), we require to prove the fulfillment of (3.11) for
all $z\in{\mathbb{X}}$ and to show that $\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)\neq\emptyset$.
The former was proven above and so we proceed with the proof of the latter.
This, indeed, follows from (4.10) and the characterization of $\mbox{\rm
dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$, achieved
in (ii), and thus completes the proof.

It is worth mentioning that a chain rule for parabolic subderivatives for the
composite form (4.3) was achieved in [21, Exercise 13.63] and [2, Proposition
3.42] when $g$ is merely a proper l.s.c. function and the basic constraint
qualification (4.6) is satisfied. Replacing the latter condition with the
significantly weaker condition (4.5), we can achieve a similar result if we
assume further that $g$ is convex and locally Lipschitz continuous relative to
its domain. Another important difference between Theorem 4.4 and those
mentioned above is that the chain rule (4.8) obtained in [2, 21] does not
require the parabolic epi-differentiability of $g$. Indeed, the usage of the
basic constraint qualification (4.6) in [2, 21] allows to achieve (4.8) via a
chain rule for the epigraphs of $f$ and $g$ similar to the one in (4.7), which
is not conceivable under (4.5). These extra assumptions on $g$ automatically
fulfill in many important composite and constrained optimization problems and
so do not seem to be restrictive in our developments.

We continue by establishing two important properties for parabolic
subderivatives that play crucial roles in our developments in the next
section. One notable difference between the following results and those
obtained in Proposition 4.1 and Theorem 4.4 is that we require the parabolic
subderivative be proper. This can be achieved if the parabolic subderivative
is bounded below. In general, we may not be able to guarantee this. It turns
out, however, that if the vector $w$ in the pervious results is taken from the
critical cone to the function in question, which is a subset of the tangent
cone to the domain of that function, this can be accomplished via (3.14).
Since we only conduct our analysis in the next section over the critical cone,
this will provide no harm. Below, we first show that the parabolic
subderivative of an extended-real-valued function, which is locally Lipschitz
continuous relative to its domain, is Lipschitz continuous relative to its
domain.

######  Proposition 4.5 (Lipschitz continuity of of parabolic subderivatives).

Let $\psi:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ be finite at $\bar{x}$ and
$\bar{v}\in\partial^{p}\psi(\bar{x})$, and let $\psi$ be Lipschitz continuous
around $\bar{x}$ relative to its domain with constant $\ell\in{\rm
I\\!R}_{+}$. Assume that $w\in K_{\psi}(\bar{x},\bar{v})$ and that $\psi$ is
parabolically epi-differentiable at $\bar{x}$ for $w$. Then the parabolic
subderivative ${\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$ is
proper, l.s.c., and Lipschitz continuous relative to its domain with constant
$\ell$.

[Proof. ]Since $\psi$ is parabolically epi-differentiable at $\bar{x}$ for
$w$, we get $\mbox{\rm dom}\,{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)\neq\emptyset$.
Let $z\in\mbox{\rm dom}\,{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$. By
Proposition 3.4, we find $r\in{\rm I\\!R}_{+}$ such that

$-r\|w\|^{2}\leq{\rm
d}^{2}\psi(\bar{x}\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\bar{v})(w)\leq{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle.$ (4.14)

This tells us that ${\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)$ is finite
for every $z\in\mbox{\rm dom}\,{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$ and
thus the parabolic subderivative ${\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$ is
proper. Pick now $z_{i}\in\mbox{\rm dom}\,{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)$ for
$i=1,2$. By Proposition 4.1(i), we have $z_{i}\in T_{\scriptsize\mbox{\rm
dom}\,\psi}^{2}(\bar{x},w)$ for $i=1,2$. Letting $z:=z_{1}$ and $z_{w}:=z_{2}$
in (4.2) results in

${\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{1})\leq{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{2})+\ell\|z_{1}-z_{2}\|.$

Similarly, we can let $z:=z_{2}$ and $z_{w}:=z_{1}$ in (4.2) and obtain

${\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{2})\leq{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z_{1})+\ell\|z_{1}-z_{2}\|.$

Combining these implies that the parabolic subderivative is Lipschitz
continuous relative to its domain. By [21, Proposition 13.64], the parabolic
subderivative is always an l.s.c. function, which completes the proof.

We end this section by obtaining an exact formula for the conjugate function
of the parabolic subderivative of a convex function.

######  Proposition 4.6 (conjugate of parabolic subderivatives).

Let $\psi:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ be an l.s.c. convex function
with $\psi(\bar{x})$ finite, $\bar{v}\in\partial\psi(\bar{x}),and$ $w\in
K_{\psi}(\bar{x},\bar{v})$. Define the function $\varphi$ by $\varphi(z):={\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)$ for any
$z\in{\mathbb{X}}$. If $\psi$ is parabolically epi-differentiable at $\bar{x}$
for $w$ and parabolically regular at $\bar{x}$ for every
$v\in\partial\psi(\bar{x})$, then $\varphi$ is a proper, l.s.c., and convex
function and its conjugate function is given by

$\varphi^{*}(v)=\begin{cases}-{\rm
d}^{2}\psi(\bar{x},v)(w)&\mbox{if}\;\;v\in{\cal A}(\bar{x},w),\\\
\infty&\mbox{otherwise},\end{cases}$ (4.15)

where ${\cal A}(\bar{x},w):=\\{v\in\partial\psi(\bar{x})|\,{\rm
d}\psi(\bar{x})(w)=\langle v,w\rangle\\}$.

[Proof. ]It follows from [21, Proposition 13.64] that $\varphi$ is l.s.c.
Using similar arguments as the beginning of the proof of Proposition 4.5
together with (4.14) tells us that $\varphi$ is proper. Also we deduce from
[21, Example 13.62] that

$\mbox{\rm epi}\,\varphi=T^{2}_{\scriptsize\mbox{\rm
epi}\,\psi}\big{(}(\bar{x},\psi(\bar{x})),(w,{\rm d}\psi(\bar{x})(w))\big{)},$

and thus the parabolic epi-differentiability of $\psi$ at $\bar{x}$ for $w$
amounts to the parabolic derivability of $\mbox{\rm epi}\,\psi$ at
$(\bar{x},\psi(\bar{x}))$ for $(w,{\rm d}\psi(\bar{x})(w))$. The latter
combined with the convexity of $\psi$ tells us that $\mbox{\rm epi}\,\varphi$
is a convex set in ${\mathbb{X}}\times{\rm I\\!R}$ and so $\varphi$ is convex.

To verify (4.15), pick $v\in{\cal A}(\bar{x},w)$. This yields
$v\in\partial\psi(\bar{x})=\partial^{p}\psi(\bar{x})$ and $w\in
K_{\psi}(\bar{x},v)$, namely the critical cone of $\psi$ at $(\bar{x},v)$.
Using Proposition 3.6 and parabolic regularity of $\psi$ at $\bar{x}$ for $v$
implies that

${\rm d}^{2}\psi(\bar{x},v)(w)=\inf_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}\psi(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,v\rangle\big{\\}}=-\varphi^{*}(v),$

which clearly proves (4.15) in this case. Assume now that $v\notin{\cal
A}(\bar{x},w)$. This means either $v\notin\partial\psi(\bar{x})$ or ${\rm
d}\psi(\bar{x})(w)\neq\langle v,w\rangle$. Define the parabolic difference
quotients for $\psi$ at $\bar{x}$ for $w$ by

$\vartheta_{t}(z)=\dfrac{\psi(\bar{x}+tw+\frac{1}{2}t^{2}z)-\psi(\bar{x})-t{\rm
d}\psi(\bar{x})(w)}{\frac{1}{2}t^{2}},\quad z\in{\mathbb{X}},\;\;t>0.$

It is not hard to see that $\vartheta_{t}$ are proper, convex, and

$\vartheta_{t}^{*}(v)=\dfrac{\psi(\bar{x})+\psi^{*}(v)-\langle
v,\bar{x}\rangle}{\frac{1}{2}t^{2}}+\frac{{\rm d}\psi(\bar{x})(w)-\langle
v,w\rangle}{\frac{1}{2}t},\quad v\in{\mathbb{X}}.$

Remember that by [21, Definition 13.59] the parabolic epi-differentiability of
$\psi$ at $\bar{x}$ for $w$ amounts to the sets $\mbox{\rm
epi}\,\vartheta_{t}$ converging to $\mbox{\rm epi}\,\varphi$ as $t\downarrow
0$ and that the functions $\vartheta_{t}$ and $\varphi$ are proper, l.s.c.
and convex. Appealing to [21, Theorem 11.34] tells us that the former is
equivalent to the sets $\mbox{\rm epi}\,\vartheta_{t}^{*}$ converging to
$\mbox{\rm epi}\,\varphi^{*}$ as $t\downarrow 0$. This, in particular, means
that for any $v\notin{\cal A}(\bar{x},w)$ and any sequence $t_{k}\downarrow
0$, there exists a sequence $v_{k}\to v$ such that

$\varphi^{*}(v)=\lim_{k\to\infty}\vartheta_{t_{k}}^{*}(v_{k}).$

If $v\notin\partial\psi(\bar{x})$, then we have

$\psi(\bar{x})+\psi^{*}(v)-\langle v,\bar{x}\rangle>0.$

Since $\psi^{*}$ is l.s.c., we get

$\liminf_{k\to\infty}\dfrac{\psi(\bar{x})+\psi^{*}(v_{k})-\langle
v_{k},\bar{x}\rangle}{\frac{1}{2}t_{k}}+\frac{{\rm d}\psi(\bar{x})(w)-\langle
v_{k},w\rangle}{\frac{1}{2}}\geq\infty,$

which in turn confirms that

$\varphi^{*}(v)=\lim_{k\to\infty}\vartheta_{t_{k}}^{*}(v_{k})=\lim_{k\to\infty}\frac{1}{t_{k}}\big{(}\dfrac{\psi(\bar{x})+\psi^{*}(v_{k})-\langle
v_{k},\bar{x}\rangle}{\frac{1}{2}t_{k}}+\frac{{\rm d}\psi(\bar{x})(w)-\langle
v_{k},w\rangle}{\frac{1}{2}}\big{)}=\infty.$

If $v\in\partial\psi(\bar{x})$ but ${\rm d}\psi(\bar{x})(w)\neq\langle
v,w\rangle$, we obtain $\langle v,w\rangle<{\rm d}\psi(\bar{x})(w)$. Since we
always have

$\psi(\bar{x})+\psi^{*}(v_{k})-\langle v_{k},\bar{x}\rangle\geq 0\quad\mbox{
for all}\;\;k\in{\rm I\\!N},$

we arrive at

$\varphi^{*}(v)=\lim_{k\to\infty}\vartheta_{t_{k}}^{*}(v_{k})\geq\lim_{k\to\infty}\frac{{\rm
d}\psi(\bar{x})(w)-\langle v_{k},w\rangle}{\frac{1}{2}t_{k}}=\infty,$

which justifies (4.15) when $v\notin{\cal A}(\bar{x},w)$ and hence finishes
the proof.

Proposition 4.6 was first established using a different method in [18,
Proposition 3.5] for convex piecewise linear-quadratic functions. It was
extended in [7, Theorem 3.1] for any convex functions under a restrictive
assumption. Indeed, this result demands that the second subderivative be the
same as the second-order directional derivative. Although this condition holds
for convex piecewise linear-quadratic functions, it fails for many important
functions occurring in constrained and composite optimization problems
including the set indicator functions and eigenvalue functions. As discussed
below, however, our assumptions are satisfied for all these examples.

######  Example 4.7.

Suppose that $g:{\mathbb{Y}}\to\overline{{\rm I\\!R}}$ is an l.s.c. convex
function and $\bar{z}\in{\mathbb{Y}}$.

  * (a)

If ${\mathbb{Y}}={\rm I\\!R}^{m}$, $g$ is convex piecewise linear-quadratic
(Example 3.2), and $\bar{z}\in\mbox{\rm dom}\,g$, then it follows from Example
3.2 and [21, Exercise 13.61] that $g$ is parabolically regular at $\bar{z}$
for every $y\in\partial g(\bar{z})$ and parabolically epi-differentiable at
$\bar{z}$ for every $w\in\mbox{\rm dom}\,{\rm d}g(\bar{z})$, respectively, and
thus all the assumptions of Proposition 4.6 are satisfied for this function.

  * (b)

If ${\mathbb{Y}}={\mathbb{S}}^{m}$, $g$ is either the maximum eigenvalue
function $\lambda_{\max}$ from (3.9) or the function $\sigma_{i}$ from (3.10),
and $A\in{\mathbb{S}}^{n}$, then by Example 3.3 $g$ is parabolically regular
at $A$ for every $V\in\partial g(A)$. Moreover, we deduce from [23,
Proposition 2.2] that $g$ is parabolically epi-differentiable at $A$ for every
$W\in{\mathbb{S}}^{n}$ and thus all the assumptions of Proposition 4.6 are
satisfied for these functions.

  * (c)

If $g=\delta_{C}$ and $\bar{z}\in C$, where $C$ is a closed convex set in
${\mathbb{Y}}$ that is parabolically derivable at $\bar{z}$ for every $w\in
T_{C}(\bar{z})$ and parabolically regular at $\bar{z}$ for every $v\in
N_{C}(\bar{z})$, then $g$ satisfies the assumptions imposed in Proposition
4.6. This example of $g$ was recently explored in detail in [14] and
encompasses important sets appearing in constrained optimization problems such
as polyhedral convex sets, the second-order cone, and the cone of positive
semidefinite symmetric matrices.

  * (d)

Assume that $g$ is differentiable at $\bar{z}$ and that there exists a
continuous function $h:{\mathbb{Y}}\to{\rm I\\!R}$, which is positively
homogeneous of degree $2$, such that

$g(z)=g(\bar{z})+\langle\nabla g(\bar{z}),z-\bar{z}\rangle+\hbox{${1\over
2}$}h(z-\bar{z})+o(\|z-\bar{z}\|^{2}).$

Such a function $g$ is called twice semidifferentiable (cf. [21, Example
13.7]) and often appears in the augmented Lagrangian function associated with
(1.1); see [14, Section 8] for more detail. This second-order expansion
clearly justifies the parabolic epi-differentiability of $g$ at $\bar{z}$ for
every $w\in{\mathbb{Y}}$. Moreover, one has

${\rm d}^{2}g(\bar{z},\nabla g(\bar{z}))(w)=h(w)={\rm
d}^{2}g(\bar{z})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;u)-\langle\nabla
g(\bar{z}),u\rangle\;\;\mbox{for all}\;\;u,w\in{\mathbb{Y}},$

which in turn shows that $g$ is parabolically regular at $\bar{z}$ for $\nabla
g(\bar{z})$ due to Proposition 3.6.

It is important to mention that the restrictive assumption on the second
subderivative, used in [7, Theorem 3.1], does not hold for cases (b)-(d) in
Example 4.7.

##  5  A Chain Rule for Parabolically Regular Functions

Our main objective in this section is to derive a chain rule for the parabolic
regularity of the composite representation (4.3). This opens the door to
obtain a chain rule for the second subderivative, and, more importantly,
allows us to establish the twice epi-differentiability of the latter composite
form.

Taking into account representation (4.3) and picking a subgradient
$\bar{v}\in\partial f(\bar{x})$, we define the set of Lagrangian multipliers
associated with $(\bar{x},\bar{v})$ by

$\Lambda(\bar{x},\bar{v})=\big{\\{}y\in{\mathbb{Y}}|\;\nabla
F(\bar{x})^{*}y=\bar{v},\;y\in\partial g(F(\bar{x}))\big{\\}}.$

In what follows, we say that a function $f:{\mathbb{X}}\to\overline{{\rm
I\\!R}}$ with $(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial f$ and having the
composite representation (4.3) at $\bar{x}$ satisfies the basic assumptions at
$(\bar{x},\bar{v})$ if in addition the following conditions fulfill:

  * (H1)

the metric subregularity constraint qualification holds for the constraint set
(4.4) at $\bar{x}$;

  * (H2)

for any $y\in\Lambda(\bar{x},\bar{v})$, the function $g$ from (4.3) is
parabolically epi-differentiable at $F(\bar{x})$ for every $u\in
K_{g}(F(\bar{x}),y)$;

  * (H3)

for any $y\in\Lambda(\bar{x},\bar{v})$, the function $g$ is parabolically
regular at $F(\bar{x})$ for $y$.

We begin with the following result in which we collect lower and upper
estimates for the second subderivative of $f$ taken from (4.3).

######  Proposition 5.1 (properities of second subderivatives for composite
functions).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ have the composite
representation (4.3) at $\bar{x}\in\mbox{\rm dom}\,f$, $\bar{v}\in\partial
f(\bar{x})$, and let the basic assumptions (H1) and (H2) hold for $f$ at
$(\bar{x},\bar{v})$. Then the second subderivative ${\rm
d}^{2}f(\bar{x},\bar{v})$ is a proper l.s.c. function with

$\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})=K_{f}(\bar{x},\bar{v}).$ (5.1)

Moreover, for every $w\in{\mathbb{X}}$ we have the lower estimate

${\rm
d}^{2}f(\bar{x},\bar{v})(w)\geq\sup_{y\in\Lambda(\bar{x},\bar{v})}\big{\\{}\langle
y,\nabla^{2}F(\bar{x})(w,w)\rangle+{\rm d}^{2}g(F(\bar{x}),y)(\nabla
F(\bar{x})w)\big{\\}},$ (5.2)

while for every $w\in K_{f}(\bar{x},\bar{v})$ we obtain the upper estimate

$\displaystyle{\rm
d}^{2}f(\bar{x},\bar{v})(w)\leq\inf_{z\in{\mathbb{X}}}\big{\\{}-\langle
z,\bar{v}\rangle+{\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w))\big{\\}}<\infty.$ (5.3)

[Proof. ]By Proposition 4.3(ii), we have $\partial^{p}f(\bar{x})=\partial
f(\bar{x})$. Appealing now to Propositions 2.1(iii) and 3.4 confirms,
respectively, that ${\rm d}^{2}f(\bar{x},\bar{v})$ is a proper l.s.c. function
and that (5.1) holds. The lower estimate (5.2) can be justified as [21,
Theorem 13.14] in which this estimate was derived under condition (4.6). To
obtain (5.3), observe first that the basic assumption (H1) yields

$w\in K_{f}(\bar{x},\bar{v})\iff\nabla F(\bar{x})w\in K_{g}(F(\bar{x}),y)$
(5.4)

for every $y\in\Lambda(\bar{x},\bar{v})$. Pick $w\in K_{f}(\bar{x},\bar{v})$.
Since $g$ is parabolically epi-differentiable at $F(\bar{x})$ for $\nabla
F(\bar{x})w$ due to (H2), Theorem 4.4(iii) implies that $f$ is parabolically
epi-differentiable at $\bar{x}$ for $w$, and so $\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)\neq\emptyset$.
This combined with (3.14) and (4.8) results in (5.3) and hence completes the
proof.

While looking simple, the above result carries important information by which
we can achieve a chain rule for the second subderivative. To do so, we should
look for conditions under which the lower and upper estimates (5.2) and (5.3),
respectively, coincide. This motivates us to consider the unconstrained
optimization problem

$\min_{z\in{\mathbb{X}}}\;\;-\langle z,\bar{v}\rangle+{\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w)).$ (5.5)

When the basic assumptions (H1)-(H3) are satisfied, (5.5) is a convex
optimization problem for any $w\in K_{f}(\bar{x},\bar{v})$. Using Proposition
4.6 allows us to obtain the dual problem of (5.5) and then examine whether
their optimal values coincide. We pursue this goal in the following result.

######  Theorem 5.2 (duality relationships).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ have the composite
representation (4.3) at $\bar{x}\in\mbox{\rm dom}\,f$, $\bar{v}\in\partial
f(\bar{x})$, and let the basic assumptions (H1)-(H3) hold for $f$ at
$(\bar{x},\bar{v})$. Then for each $w\in K_{f}(\bar{x},\bar{v})$, the
following assertions are satisfied:

  * (i)

the dual problem of (5.5) is given by

$\max_{y\in{\mathbb{Y}}}\;\;\langle y,\nabla^{2}F(\bar{x})(w,w)\rangle+{\rm
d}^{2}g(F(\bar{x}),y)(\nabla F(\bar{x})w)\quad\mbox{subject
to}\;\;y\in\Lambda(\bar{x},\bar{v});$ (5.6)

  * (ii)

the optimal values of the primal and dual problems (5.5) and (5.6),
respectively, are finite and coincide; moreover, we have
$\Lambda(\bar{x},\bar{v},w)\cap(\tau\mathbb{B})\neq\emptyset$, where
$\Lambda(\bar{x},\bar{v},w)$ stands for the set of optimal solutions to the
dual problem (5.6) and where

$\tau:=\kappa\ell\|\nabla F(\bar{x})\|+\kappa\|\bar{v}\|+\ell$ (5.7)

with $\ell$ and $\kappa$ taken from (4.3) and (4.5), respectively.

[Proof. ]Pick $w\in K_{f}(\bar{x},\bar{v})$ and observe from (5.4) that
$\nabla F(\bar{x})w\in K_{g}(F(\bar{x}),y)$ for all
$y\in\Lambda(\bar{x},\bar{v})$. This together with Proposition 4.6 ensures
that the parabolic subderivative of $g$ at $F(\bar{x})$ for $\nabla
F(\bar{x})w$ is a proper, l.s.c., and convex function. Using this combined
with [21, Example 11.41] and (4.15) tells us that the dual problem of (5.5) is

$\max_{y\in{\mathbb{Y}}}\;\;\langle y,\nabla^{2}F(\bar{x})(w,w)\rangle+{\rm
d}^{2}g(F(\bar{x}),y)(\nabla F(\bar{x})w)\quad\mbox{subject
to}\;\;y\in\Lambda(\bar{x},\bar{v})\cap{\cal D},$

where ${\cal D}:=\\{y\in{\mathbb{Y}}|\,{\rm d}g(F(\bar{x}))(\nabla
F(\bar{x})w)=\langle y,\nabla F(\bar{x})w\rangle\\}$. Since $\nabla
F(\bar{x})w\in K_{g}(F(\bar{x}),y)$ for all $y\in\Lambda(\bar{x},\bar{v})$, we
obtain

$y\in\Lambda(\bar{x},\bar{v})\cap{\cal D}\iff y\in\Lambda(\bar{x},\bar{v}).$

Combining these confirms that the dual problem of (5.5) is equivalent to (5.6)
and thus finishes the proof of (i). To prove (ii), consider the optimal value
function $\vartheta:{\mathbb{Y}}\to[-\infty,\infty]$, defined by

$\vartheta(p)=\inf_{z\in{\mathbb{X}}}\big{\\{}-\langle\bar{v},z\rangle+{\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.99168pt]{0.56905pt}{10.52737pt}\;\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w)+p)\big{\\}},\quad p\in{\mathbb{Y}}.$
(5.8)

We proceed with the following claim:

Claim.We have $\partial\vartheta(0)\neq\emptyset$.

To justify the claim, we first need to show $\vartheta(0)\in{\rm I\\!R}$. To
do so, observe that $\bar{v}\in\partial f(\bar{x})=\partial^{p}f(\bar{x})$ due
to Proposition 4.3(ii). Thus, it follows from Proposition 2.1(iii) and (5.3)
that there is a constant $r\in{\rm I\\!R}_{+}$ such that for any $w\in
K_{f}(\bar{x},\bar{v})$ we have

$-r\|w\|^{2}\leq{\rm d}^{2}f(\bar{x},\bar{v})(w)\leq\vartheta(0)<\infty,$

which in turn implies that $\vartheta(0)\in{\rm I\\!R}$. Next, we are going to
show that

$\vartheta(p)\geq\vartheta(0)-\tau\|p\|\quad\mbox{for
all}\;\;p\in{\mathbb{X}},$ (5.9)

where $\tau$ is taken from (5.7). To this end, take
$(p,z)\in{\mathbb{Y}}\times{\mathbb{X}}$ such that

$u_{p}:=\nabla F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w)+p\in\mbox{\rm dom}\,{\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\cdot).$

By (4.9), we get $u_{p}\in T_{\scriptsize\mbox{\rm
dom}\,g}^{2}(F(\bar{x}),\nabla F(\bar{x})w)$. Define now the set-valued
mapping $S_{w}:{\mathbb{Y}}\rightrightarrows{\mathbb{X}}$ by

$S_{w}(p):=\big{\\{}z\in{\mathbb{X}}|\;\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w)+p\in T_{\scriptsize\mbox{\rm
dom}\,g}^{2}(F(\bar{x}),\nabla F(\bar{x})w)\big{\\}},\;\;p\in{\mathbb{Y}}.$

So, we get $z\in S_{w}(p)$. It was recently observed in [14, Theorem 4.3] that
the mapping $S_{w}$ enjoys the uniform outer Lipschitzian property at $0$ with
constant $\kappa$ taken from (4.5), namely for every $p\in{\mathbb{Y}}$ we
have

$S_{w}(p)\subset S_{w}(0)+\kappa\|p\|\mathbb{B}.$

This combined with $z\in S_{w}(p)$ results in the existence of $z_{0}\in
S_{w}(0)$ and $b\in\mathbb{B}$ such that $z=z_{0}+\kappa\|p\|b$. It follows
from (4.9) and $z_{0}\in S_{w}(0)$ that

$\nabla F(\bar{x})z_{0}+\nabla^{2}F(\bar{x})(w,w)\in\mbox{\rm dom}\,{\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\cdot).$

Since we have

$u_{p}-\big{(}\nabla
F(\bar{x})z_{0}+\nabla^{2}F(\bar{x})(w,w)\big{)}=p+\kappa\|p\|\nabla
F(\bar{x})b,$

and since the parabolic subderivative ${\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\cdot)$ is Lipschitz
continuous relative to its domain due to Proposition 4.5, we get the
relationships

$\displaystyle-\langle\bar{v},z\rangle+{\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u_{p})$
$\displaystyle\geq$ $\displaystyle-\langle\bar{v},z_{0}\rangle+{\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\nabla
F(\bar{x})z_{0}+\nabla^{2}F(\bar{x})(w,w))$
$\displaystyle-\ell\,\|p+\kappa\;\|p\|\nabla
F(\bar{x})b\;\|-\kappa\|p\|\langle\bar{v},b\rangle$ $\displaystyle\geq$
$\displaystyle\vartheta(0)-\big{(}\ell\kappa\|\nabla
F(\bar{x})\|+\kappa\|\bar{v}\|+\ell\big{)}\|p\|,$

which together with (5.7) justify (5.9). Remember that the parabolic
subderivative of $g$ at $F(\bar{x})$ for $\nabla F(\bar{x})w$ is a proper and
convex function. This implies that the function

$(z,p)\mapsto-\langle\bar{v},z\rangle+{\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.99168pt]{0.56905pt}{10.52737pt}\;\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w)+p)$

is convex on ${\mathbb{X}}\times{\mathbb{Y}}$. Using this together with [21,
Proposition 2.22] tells us that $\vartheta$ is a convex function on
${\mathbb{Y}}$. Thus, we conclude from (5.9) and [14, Proposition 5.1] that
there exists a subgradient $\bar{y}$ of $\vartheta$ at $0$ such that

$\bar{y}\in\partial\vartheta(0)\cap(\tau\mathbb{B}),$ (5.10)

which completes the proof of the claim.

Employing now (5.10) and [2, Theorem 2.142] confirms that the optimal values
of the primal and dual problems (5.5) and (5.6), respectively, coincide and
that

$\Lambda(\bar{x},\bar{v},w)=\partial\vartheta(0).$

This together with (5.10) justifies (ii) and hence completes the proof.

The above theorem extends the recent results obtained in [14, Propositions 5.4
& 5.5] for constraint sets, namely when the function $g$ in (4.3) is the
indicator function of a closed convex set. We should add here that for
constraint sets, the dual problem (5.6) can be obtained via elementary
arguments. However, for the composite form (4.3) a similar result requires
using rather advanced theory of epi-convergence.

######  Remark 5.3 (duality relationship under metric regularity).

In the framework of Theorem 5.2, we want to show that replacing assumption
(H1) with the strictly stronger constraint qualification (4.6) allows us not
only to drop the imposed Lipschitz continuity of $g$ from (4.3) but also to
simplify the proof of Theorem 5.2. To this end, let $w\in
K_{f}(\bar{x},\bar{v})$ and define the function

$\psi(u):={\rm d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;u),\;\;u\in{\mathbb{X}}.$

By Proposition 4.6, $\psi$ is a proper, l.s.c., and convex function. Employing
[21, Proposition 13.12] tells us that

$T_{\scriptsize\mbox{\rm epi}\,g}(p)+T^{2}_{\scriptsize\mbox{\rm
epi}\,g}\big{(}p,q)\subset T^{2}_{\scriptsize\mbox{\rm
epi}\,g}\big{(}p,q)=\mbox{\rm epi}\,\psi,$ (5.11)

where $p:=\big{(}F(\bar{x}),g(F(\bar{x}))\big{)}$ and $q:=\big{(}\nabla
F(\bar{x})w,{\rm d}g(F(\bar{x}))(\nabla F(\bar{x})w)\big{)}$ and where the
equality in the right side comes from [21, Example 13.62(b)]. We are going to
show that the validity of (4.6) yields

$N_{\scriptsize\mbox{\rm dom}\,\psi}(u)\cap\mbox{\rm ker}\,\nabla
F(\bar{x})^{*}=\\{0\\}$ (5.12)

for any $u\in\mbox{\rm dom}\,\psi$. To this end, pick $u\in\mbox{\rm
dom}\,\psi$ and conclude from (5.11) and [21, Exercise 6.44] that

$N_{\scriptsize\mbox{\rm epi}\,\psi}\big{(}u,\psi(u)\big{)}\subset
N_{\scriptsize T_{\scriptsize{\mbox{\rm epi}\,g}}(p)}(0)\cap
N_{\scriptsize\mbox{\rm
epi}\,\psi}\big{(}u,\psi(u)\big{)}=N_{\scriptsize\mbox{\rm epi}\,g}(p)\cap
N_{\scriptsize\mbox{\rm epi}\,\psi}\big{(}u,\psi(u)\big{)}.$

This together with (4.6) and the relationship $N_{\scriptsize\mbox{\rm
dom}\,\psi}(u)=\partial^{\infty}\psi(u)$ stemming from the convexity of $\psi$
confirms the validity of (5.12). Appealing now to [2, Theorem 2.165] gives
another proof of Theorem 5.2 when assumption (H1) therein is replaced with the
strictly stronger constraint qualification (4.6).

The established duality relationships in Theorem 5.2 open the door to derive a
chain rule for parabolically regular functions and to find an exact chain rule
for the second subderivative of the composite function (4.3) under our basic
assumptions.

######  Theorem 5.4 (chain rule for parabolic regularity).

Let $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ have the composite
representation (4.3) at $\bar{x}\in\mbox{\rm dom}\,f$, $\bar{v}\in\partial
f(\bar{x})$, and let the basic assumptions (H1)-(H3) hold for $f$ at
$(\bar{x},\bar{v})$. Then $f$ is parabolically regular at $\bar{x}$ for
$\bar{v}$. Furthermore, for every $w\in{\mathbb{X}}$, the second subderivative
of $f$ at $\bar{x}$ for $\bar{v}$ is calculated by

$\displaystyle{\rm d}^{2}f(\bar{x},\bar{v})(w)$ $\displaystyle=$
$\displaystyle\max_{y\in\Lambda(\bar{x},\bar{v})}\big{\\{}\langle
y,\nabla^{2}F(\bar{x})(w,w)\rangle+{\rm d}^{2}g(F(\bar{x}),y)(\nabla
F(\bar{x})w)\big{\\}}$ $\displaystyle=$
$\displaystyle\max_{y\in\Lambda(\bar{x},\bar{v})\,\cap\,(\tau\mathbb{B})}\big{\\{}\langle
y,\nabla^{2}F(\bar{x})(w,w)\rangle+{\rm d}^{2}g(F(\bar{x}),y)(\nabla
F(\bar{x})w)\big{\\}},$

where $\tau$ is taken from (5.7).

[Proof. ]It was recently observed in [13, Corollary 3.7] that the Lagrange
multiplier set $\Lambda(\bar{x},\bar{v})$ enjoys the following property:

$\Lambda(\bar{x},\bar{v})\,\cap\,(\tau\mathbb{B})\neq\emptyset.$ (5.14)

Take $w\in K_{f}(\bar{x},\bar{v})$. By (5.2) and Theorem 5.2(ii), we obtain

$\max_{y\in\Lambda(\bar{x},\bar{v})}\big{\\{}\langle
y,\nabla^{2}F(\bar{x})(w,w)\rangle+{\rm d}^{2}g(F(\bar{x}),y)(\nabla
F(\bar{x})w)\big{\\}}\leq{\rm d}^{2}f(\bar{x},\bar{v})(w).$ (5.15)

On the other hand, using (3.14), (4.8), and Theorem 5.2(ii), respectively,
gives us the inequalities

$\displaystyle{\rm d}^{2}f(\bar{x},\bar{v})(w)$ $\displaystyle\leq$
$\displaystyle\inf_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle\big{\\}}$ $\displaystyle=$
$\displaystyle\inf_{z\in{\mathbb{X}}}\big{\\{}-\langle z,\bar{v}\rangle+{\rm
d}^{2}g(F(\bar{x}))(\nabla
F(\bar{x})w\;\rule[-1.42262pt]{0.56905pt}{9.38945pt}\;\nabla
F(\bar{x})z+\nabla^{2}F(\bar{x})(w,w))\big{\\}}$ $\displaystyle=$
$\displaystyle\max_{y\in\Lambda(\bar{x},\bar{v})\,\cap\,(\tau\mathbb{B})}\big{\\{}\langle
y,\nabla^{2}F(\bar{x})(w,w)\rangle+{\rm d}^{2}g(F(\bar{x}),y)(\nabla
F(\bar{x})w)\big{\\}}.$

These combined with (5.15) ensure that the claimed second subderivative
formulas for $f$ at $\bar{x}$ for $\bar{v}$ hold for any $w\in
K_{f}(\bar{x},\bar{v})$ and that

${\rm d}^{2}f(\bar{x},\bar{v})(w)=\inf_{z\in{\mathbb{X}}}\big{\\{}{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;z)-\langle
z,\bar{v}\rangle\big{\\}}\quad\mbox{for all}\;\;w\in K_{f}(\bar{x},\bar{v}).$

Appealing now to Proposition 3.6, we conclude that $f$ is parabolically
regular at $\bar{x}$ for $\bar{v}$.

What remains is to validate the second subderivative formulas for $w\notin
K_{f}(\bar{x},\bar{v})$. It follows from Theorem 4.4(iii) that $f$ is
parabolically epi-differentiable at $\bar{x}$ for every $w\in
K_{f}(\bar{x},\bar{v})$ and thus $\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x})(w\;\rule[-1.13809pt]{0.56905pt}{7.68236pt}\;\cdot)\neq\emptyset$
for every $w\in K_{f}(\bar{x},\bar{v})$. So, by Proposition 3.4 we have
$\mbox{\rm dom}\,{\rm d}^{2}f(\bar{x},\bar{v})=K_{f}(\bar{x},\bar{v})$. Since
the second subderivative ${\rm d}^{2}f(\bar{x},\bar{v})$ is a proper function,
we obtain ${\rm d}^{2}f(\bar{x},\bar{v})(w)=\infty$ for all $w\notin
K_{f}(\bar{x},\bar{v})$. On the other hand, we understand from (5.4) that
$w\notin K_{f}(\bar{x},\bar{v})$ amounts to $\nabla F(\bar{x})w\notin
K_{g}(F(\bar{x}),y)$ for every $y\in\Lambda(\bar{x},\bar{v})$. Combining the
basic assumption (H2) and Proposition 3.4 tells us that for every
$y\in\Lambda(\bar{x},\bar{v})$ we have ${\rm d}^{2}g(F(\bar{x}),y)(\nabla
F(\bar{x})w)=\infty$ whenever $w\notin K_{f}(\bar{x},\bar{v})$. This together
with (5.14) confirms that both sides in (5.4) are $\infty$ for every $w\notin
K_{f}(\bar{x},\bar{v})$ and thus the claimed formulas for the second
subderivative of $f$ hold for this case. This completes the proof.

A chain rule for parabolic regularity of the composite function (4.3), where
$g$ is not necessarily locally Lipschitz continuous relative to its domain,
was established in [2, Proposition 3.104]. The assumptions utilized in the
latter result were stronger than those used in Theorem 5.4. Indeed, [2,
Proposition 3.104] assumes that $g$ is second-order regular in the sense of
[2, Definition 3.93] and the basic constraint qualification (4.6) is satisfied
and uses a different approach to derive this result. When $g$ is a convex
piecewise linear-quadratic, parabolic regularity of the composite function
(4.3) was established in [21, Theorem 13.67] under the stronger condition
(4.6). Theorem 5.4 covers the aforementioned results and shows that we can
achieve a similar conclusion under the significantly weaker condition (4.5).

As an immediate consequence of the above theorem, we can easily guarantee the
twice epi-differentiability of the composite form (4.3) under our basic
assumptions.

######  Corollary 5.5 (chain rule for twice epi-differentiability).

Let the function $f$ from (4.3) satisfy all the assumptions of Theorem 5.4.
Then $f$ is twice epi-differentiable at $\bar{x}$ for $\bar{v}$.

[Proof. ]By Theorem 4.4(iii), $f$ is parabolically epi-differentiable at
$\bar{x}$ for every $w\in K_{f}(\bar{x},\bar{v})$. Employing now Theorems 5.4
and 3.8 implies that $f$ is twice epi-differentiable at $\bar{x}$ for
$\bar{v}$.

######  Remark 5.6 (discussion on twice epi-differentiability).

Corollary 5.5 provides a far-going extension of the available results for the
twice epi-differentiability of extended-real-valued functions. To elaborate
more, suppose that $f:{\mathbb{X}}\to\overline{{\rm I\\!R}}$ has a composite
form (4.3) at $\bar{x}\in\mbox{\rm dom}\,f$. Then the following observations
hold:

  * (a)

If ${\mathbb{X}}={\rm I\\!R}^{n}$, ${\mathbb{Y}}={\rm I\\!R}^{m}$, and $g$ in
(4.3) is convex piecewise linear-quadratic, then Rockafellar proved in [18]
that under the fulfillment of the basic constraint qualification (4.6), $f$ is
twice epi-differentiable. This result was improved recently in [13, Theorem
5.2], where it was shown that using the strictly weaker condition (4.5) in the
Rockafellar’s framework [18] suffices to ensure the twice epi-
differentiability of $f$. Taking into account Example 4.7(a) tells us both
these results can be derived from Corollary 5.5.

  * (b)

If ${\mathbb{X}}={\rm I\\!R}^{n}$, ${\mathbb{Y}}={\mathbb{S}}^{m}$, and $g$ is
either the maximum eigenvalue function $\lambda_{\max}$ from (3.9) or the
function $\sigma_{i}$ from (3.10), then we fall into the framework considered
by Turki in [24, Theorems 2.3 & 2.5] in which he justified the twice epi-
differentiability of $f$. Since in this framework we have $\mbox{\rm
dom}\,g={\mathbb{S}}^{m}$, both conditions (4.6) and (4.5) are automatically
satisfied. By Example 4.7(b), the twice epi-differentiability of $f$ can be
deduced from Corollary 5.5.

  * (c)

If ${\mathbb{X}}={\rm I\\!R}^{n}$, ${\mathbb{Y}}={\rm I\\!R}^{m}$, and
$g=\delta_{C}$ with the closed convex set $C$ taken from Example 4.7(c), we
fall into the framework considered in [14]. In this case, Corollary 5.5 can
cover the twice epi-differentiability of $f$ obtained in [14, Corollary 5.11].

  * (d)

If ${\mathbb{X}}={\rm I\\!R}^{n}$, ${\mathbb{Y}}={\rm I\\!R}^{m}$, and $g$ is
a proper, convex, l.s.c., and positively homogeneous, then we fall into the
framework, considered by Shapiro in [22]. In this case, the composite form
(4.3) is called decomposable; see [22, 9] for more detail about this class of
extended-real-valued functions. It was proven in [9, Lemma 5.3.27] that for
this case of $g$, the composite form (4.3) is twice epi-differentiable if it
is convex and if the nondegeneracy condition for this setting holds; see [9,
Definition 5.3.1] for the definition of this condition. In this framework, by
the positive homogeneity of $g$ and $F(\bar{x})=0$, coming from [9, Definition
5.3.1], we can easily show that $g$ is parabolically regular. Moreover the
assumed nondegeneracy condition in [9, Lemma 5.3.27] yields the validity of
condition (4.6). As pointed out in Remark 5.3, the Lipschitz continuity of $g$
in the composite form (4.3) can be relaxed when condition (4.6) is satisfied.
Since the nondegeneracy condition implies that the set of Lagrange multipliers
${\Lambda}(\bar{x},\bar{v})$ is a singleton, we can use estimates (5.2) and
(5.3) to justify parabolic regularity of the composite form (4.3) in the
framework of [9]. This together with Corollary 5.5 allows to recover [9, Lemma
5.3.27]. Furthermore, we can drop the convexity of the composite form (4.3),
assumed in [9].

##  6 Second-Order Optimality Conditions for Composite Problems

In this section, we focus mainly on obtaining second-order optimality
conditions for the composite problem (1.1), where $\varphi:{\mathbb{X}}\to{\rm
I\\!R}$ and $F:{\mathbb{X}}\to{\mathbb{Y}}$ are twice differentiable and the
function $g:{\mathbb{Y}}\to\overline{{\rm I\\!R}}$ is an l.s.c. convex
function that is locally Lipschitz continuous relative to its domain. The
latter means that for any $y\in\mbox{\rm dom}\,g$, the function $g$ is
Lipschitz continuous around $y$ relative to its domain. Important examples of
constrained and composite optimization problems can be achieved when $g$ is
one of the functions considered in Example 4.7. For any pair
$(x,y)\in{\mathbb{X}}\times{\mathbb{Y}}$, the Lagrangian associated with the
composite problem (1.1) is defined by

$L(x,y)=\varphi(x)+\langle F(x),y\rangle-g^{*}(y),$

where $g^{*}$ is the Fenchel conjugate of the convex function $g$. We begin
with the following result in which we collect second-order optimality
conditions for (1.1) when our basic assumptions are satisfied. Recall that a
point $\bar{x}\in{\mathbb{X}}$ is called a feasible solution to the composite
problem (1.1) if we have $F(\bar{x})\in\mbox{\rm dom}\,g$.

######  Theorem 6.1 (second-order optimality conditions).

Let $\bar{x}$ be a feasible solution to problem (1.1) and let $f:=g\circ F$
and $\bar{v}:=-\nabla\varphi(\bar{x})\in\partial f(\bar{x})$ with $\varphi$,
$g$, and $F$ taken from (1.1). Assume that the basic assumptions (H1)-(H3)
hold for $f$ at $(\bar{x},\bar{v})$. Then the following second-order
optimality conditions for the composite problem (1.1) are satisfied:

  * (i)

if $\bar{x}$ is a local minimum of (1.1), then the second-order necessary
condition

$\max_{y\in\Lambda(\bar{x},\bar{v})}\big{\\{}\langle\nabla_{xx}^{2}L(\bar{x},y)w,w\rangle+{\rm
d}^{2}g(F(\bar{x}),y)(\nabla F(\bar{x})w)\big{\\}}\geq 0$

holds for all $w\in K_{f}(\bar{x},\bar{v})$;

  * (ii)

the validity of the second-order condition

$\max_{y\in\Lambda(\bar{x},\bar{v})}\big{\\{}\langle\nabla_{xx}^{2}L(\bar{x},y)w,w\rangle+{\rm
d}^{2}g(F(\bar{x}),y)(\nabla F(\bar{x})w)\big{\\}}>0\quad\mbox{for all}\quad
w\in K_{f}(\bar{x},\bar{v})\setminus\\{0\\}$ (6.1)

amounts to the existence of constants $\ell>0$ and $\varepsilon>0$ such that
the second-order growth condition

$\psi(x)\geq\psi(\bar{x})+\hbox{${\ell\over
2}$}\|x-\bar{x}\|^{2}\quad\mbox{for
all}\;\;x\in\mathbb{B}_{\varepsilon}(\bar{x})$ (6.2)

holds, where $\psi:=\varphi+g\circ F$.

[Proof. ]To justify (i), note that since $\bar{x}$ is a local minimum of
(1.1), it is a local minimum of $\psi=\varphi+f$. Moreover,
$-\nabla\varphi(\bar{x})\in\partial f(\bar{x})$ amounts to
$0\in\partial\psi(\bar{x})$. Thus, by definition, we arrive at ${\rm
d}^{2}\psi(\bar{x},0)(w)\geq 0$ for all $w\in{\mathbb{X}}$. Since $\varphi$ is
twice differentiable at $\bar{x}$, we obtain the following sum rule for the
second subderivatives:

${\rm
d}^{2}\psi(\bar{x},0)(w)=\langle\nabla^{2}\varphi(\bar{x})w,w\rangle+{\rm
d}^{2}f(\bar{x},\bar{v})(w)\quad\mbox{for all}\;\;w\in{\mathbb{X}}.$ (6.3)

Combing these with the chain rule (5.4) proves (i).

Turing now to (ii), we infer from [21, Theorem 13.24(c)] that ${\rm
d}^{2}\psi(\bar{x},0)(w)>0$ for all $w\in{\mathbb{X}}\setminus\\{0\\}$ amounts
to the existence of some constants $\ell>0$ and $\varepsilon>0$ for which the
second-order growth condition (6.2) holds. Remember from (5.1) and (6.3) that

$\mbox{\rm dom}\,{\rm d}^{2}\psi(\bar{x},0)=\mbox{\rm dom}\,{\rm
d}^{2}f(\bar{x},\bar{v})=K_{f}(\bar{x},\bar{v}).$ (6.4)

Using these, the chain rule (5.4), and the sum rule (6.3) proves the claimed
equivalence in (ii) and thus finishes the proof.

######  Remark 6.2 (discussion on second-order optimality conditions).

The second-order optimality conditions for composite problems were established
in [2, Theorems 3.108 & 3.109] for (1.1) by expressing (1.1) equivalently as a
constrained problem and then appealing to the theory of second-order
optimality conditions for the latter class of problems. While not assuming
that $g$ is locally Lipschitz continuous relative to its domain, theses
results were established under condition (4.6) and the second-order regularity
in the sense of [2, Definition 3.93] that are strictly stronger than condition
(4.5) and the parabolic regularity, respectively, we imposed in Theorem 6.1.
Another major difference is that we require that $g$ be parabolically epi-
differentiable (assumption (H2)), which was not assumed in [2]. This
assumption plays an important role in our developments and has two important
consequences: 1) it makes the parabolic subderivative be a convex function and
help us obtain a precise formula for the Fenchel conjugate of the parabolic
subderivative in our framework; 2) it allows to establish the equivalence
between (6.1) and the growth condition in Theorem 6.1. These facts were not
achieved in [2]; indeed, [2, Theorem 3.109] was written in terms of the
conjugate of the parabolic subderivative and only states that condition (6.1)
implies the growth condition therein.As discussed in Remark 5.3, if we replace
condition (4.5) with the stronger condition (4.6), the imposed Lipschitz
continuity of $g$ can be relaxed in our developments. It is worth mentioning
that the imposed Lipschitz continuity of $g$ relative to its domain, utilized
in this paper, does not seem to be restrictive and allows us to provide an
umbrella under which second-order variational analysis for composite problems
can be carried out under condition (4.6) in the same level of perfection as
those for constrained problems. We believe that if we strengthen condition
(4.6) to the metric subregularity of the epigraphical mapping
$(x,\alpha)\mapsto(F(x),\alpha)-\mbox{\rm epi}\,g$, the imposed Lipschitz
continuity of $g$ can be relaxed in our developments.

Cominetti [7, Theorem 5.1] established second-order optimality conditions for
the composite problem (1.1) similar to Theorem 6.1 without making a connection
between (6.1) and the growth condition (6.2). As mentioned in our discussion
after Example 4.7, the results in [7] were established under condition (4.6)
and a restrictive assumption on the second subderivative, which does not hold
for important classes of composite problems. When we are in the framework of
Remark 5.6(a), Theorem 6.1 was first achieved by Rockafellar in [19, Theorem
4.2] under condition (4.6) and was improved recently in [13, Theorem 6.2] by
replacing the latter condition with (4.5). For the framework of Remark 5.6(b),
the second-order optimality conditions from Theorem 6.1 were obtained in [24,
Theorem 4.2]. Finally, if we are in the framework of Remark 5.6(c), Theorem
6.1 covers our recent developments in [14].

We end this section by obtaining a characterization of strong metric
subregularity of the subgradient mapping of the objective function of the
composite problem (1.1).

######  Theorem 6.3 (strong metric subregularity of the subgradient mappings
in composite problems).

Let $\bar{x}$ be a feasible solution to problem (1.1) and let $f:=g\circ F$
and $\bar{v}:=-\nabla\varphi(\bar{x})\in\partial f(\bar{x})$ with $\varphi$,
$g$, and $F$ taken from (1.1). Assume that the basic assumptions (H1)-(H3)
hold for $f$ at $(\bar{x},\bar{v})$ and that both $\varphi$ and $F$ are ${\cal
C}^{2}$-smooth around $\bar{x}$. Then the following conditions are equivalent:

  * (i)

the point $\bar{x}$ is a local minimizer for $\psi=\varphi+f$ and the
subgradient mapping $\partial\psi$ is strongly metrically subregular at
$(\bar{x},0)$;

  * (ii)

the second-order sufficient condition (6.1) holds.

[Proof. ]We conclude from (6.3) and (6.4) that (6.1) amounts to the
fulfillment of the condition

${\rm d}^{2}\psi(\bar{x},0)(w)>0\quad\mbox{for
all}\;\;w\in{\mathbb{X}}\setminus\\{0\\}.$ (6.5)

If (i) holds, we conclude from the local optimality of $\bar{x}$ that ${\rm
d}^{2}\psi(\bar{x},0)(w)\geq 0$ for all $w\in{\mathbb{X}}$. Since (ii) is
equivalent to (6.5), it suffices to show that there is no
$w\in{\mathbb{X}}\setminus\\{0\\}$ such that ${\rm
d}^{2}\psi(\bar{x},0)(w)=0$. Suppose on the contrary that there exists
$\bar{w}\in{\mathbb{X}}\setminus\\{0\\}$ satisfying the latter condition. This
means that $\bar{w}$ is a minimizer for the problem

$\mbox{minimize}\;\hbox{${1\over 2}$}{\rm
d}^{2}\psi(\bar{x},0)(w)\quad\mbox{subject to }\;\;w\in{\mathbb{X}}.$

Since both $\varphi$ and $F$ are ${\cal C}^{2}$-smooth around $\bar{x}$, we
can show using similar arguments as [13, Proposition 7.1] that $\psi$ is prox-
regular and subdifferentially continuousat $\bar{x}$ for $0$. This together
with the Fermat stationary principle and (3.21) results in

$\displaystyle 0\in\partial\big{(}\hbox{${1\over 2}$}{\rm
d}^{2}\psi(\bar{x},0)\big{)}(\bar{w})=D(\partial\psi)(\bar{x},0)(\bar{w}).$
(6.6)

Since $\partial\psi$ is strongly metrically subregular at $(\bar{x},0)$, we
deduce from (2.2) that $\bar{w}=0$, a contradiction. This proves (ii).

To justify the opposite implication, assume that (ii) holds. According to
Theorem 6.1(ii), $\bar{x}$ is a local minimizer for $\psi$. Pick now
$w\in{\mathbb{X}}$ such that $0\in D(\partial\psi)(\bar{x},0)(w)$. To obtain
(i), we require by (2.2) to show that $w=0$. Employing now (6.6) yields
$0\in\partial\big{(}\hbox{${1\over 2}$}{\rm d}^{2}\psi(\bar{x},0)\big{)}(w)$.
This combined with [6, Lemma 3.7] confirms that ${\rm
d}^{2}\psi(\bar{x},0)(w)=\langle 0,w\rangle=0$. Remember that (ii) is
equivalent to (6.5). Combining these results in $w=0$ and thus proves (i).

The above result was first observed in [8, Theorem 4G.1] for a subclass of
nonlinear programming problems and was extended in [6, Theorem 4.6] for ${\cal
C}^{2}$-cone reducible constrained optimization problems and in [14, Theorem
9.2] for parabolically regular constrained optimization problems. The theory
of the twice epi-differentiability, obtained in this paper, provides an easy
path to achieve a similar result for the composite problem (1.1).

It is worth mentioning that similar characterizations as [14, Theorem 4.2] can
be achieved for the KKT system of (1.1). Furthermore, Corollary 3.9 provides a
systematic method to calculate proto-derivatives of subgradient mappings of
functions enjoying the composite form (4.3), a path we will pursue in our
future research.

Acknowledgements. The second author would like to thank Asen Dontchev for
bringing [8, Theorem 4G.1] to his attention, which inspired the equivalence
obtained in Theorem 6.3. Special thanks go to Boris Mordukhovich for numerous
discussions on the subject of this paper and second-order variational analysis
and for the insightful advice and comments. We also thank two anonymous
reviewers for their useful comments that allowed us to improve the original
presentation. Reference [9] was brought to our attention by one of the
referees that is highly appreciated.

## References

  * [1] A. Ben-Tal and J. Zowe, A unified theory of first- and second-order conditions for extremum problems in topological vector spaces, Math. Program. 19 (1982), 39–76.
  * [2] J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, New York, 2000.
  * [3] J. F. Bonnans, R. Cominetti and A. Shapiro, Second-order optimality conditions based on parabolic second-order tangent sets, SIAM J. Optim. 9 (1998), 466–492.
  * [4] J. V. Burke, A. S. Lewis, and M. L. Overton, Optimal stability and eigenvalue multiplicity, Found. Comput. Math. 1 (2001), 205–225.
  * [5] R. W. Chaney, On second derivatives for nonsmooth functions, Nonlinear Anal. 9 (1985), 1189–1209.
  * [6] N. H. Chieu, L. V. Hien, T. T. A. Nghia, and H. A. Tuan, Second-order optimality conditions for strong local minimizers via subgradient graphical derivative, (2019), arXiv:1903.05746.
  * [7] R. Cominetti, On pseudo-differentiability, Trans. Amer. Math. Soc. 324 (1991), 843–847.
  * [8] A. L. Dontchev and R. T. Rockafellar, Implicit Functions and Solution Mappings: A View from Variational Analysis, 2nd edition, Springer, Dordrecht, 2014.
  * [9] A. Milzarek, Numerical Methods and Second Order Theory for Nonsmooth Problems, Ph.D. Dissertation, University of Munich, 2016.
  * [10] A.D. Ioffe, Variational analysis of a composite function: A formula for the lower second-order epi-derivative, J. Math. Anal. Appl. 160 (1991) 379–405.
  * [11] A. B. Levy, Second-order epi-derivatives of composite functionals, Ann. Oper. Res. 101 (2001), 267–281.
  * [12] B. S. Mordukhovich, Variational Analysis and Applications, Springer Monographs in Mathematics, Springer, Cham, Switzerland, 2018.
  * [13] A. Mohammadi, B. Mordukhovich and M. E. Sarabi, Variational analysis of composite models with applications to continuous optimization, To appear in Math. Oper. Res. (2020), arXiv:1905.08837.
  * [14] A. Mohammadi, B. Mordukhovich and M. E. Sarabi, Parabolic regularity via geometric variational analysis, (2019), arXiv:1909.00241.
  * [15] A. Mohammadi, B. Mordukhovich and M. E. Sarabi, Stability of KKT systems and superlinear convergence of the SQP method under parabolic regularity, (2019), arXiv:1910.06894.
  * [16] R. A. Poliquin and R. T. Rockafellar, Prox-regular functions in variational analysis  Trans. Amer. Math. Soc. 348 (1996), 1805–1838.
  * [17] R. T. Rockafellar, Maximal monotone relations and the second derivatives of nonsmooth functions, Ann. Inst. H. Poincaré Analyse Non Linéaire 2 (1985), 167–184.
  * [18] R. T. Rockafellar, first- and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc. 307 (1988), 75–108.
  * [19] R. T. Rockafellar, Second-order optimality conditions in nonlinear programming obtained by way of epi-derivatives, Math. Oper. Res. 14 (1989), 462–484.
  * [20] R. T. Rockafellar, Generalized second derivatives of convex functions and saddle functions, Trans. Amer. Math. Soc. 322 (1990), 51–77.
  * [21] R. T. Rockafellar and R. J-B. Wets, Variational Analysis, Grundlehren Series (Fundamental Principles of Mathematical Sciences), Vol. 317, Springer, Berlin, 2006.
  * [22] A. Shapiro, On a class of nonsmooth composite functions, Math. Oper. Res. 28 (2003), 677–692.
  * [23] M. Torki, Second-order directional derivatives of all eigenvalues of a symmetric matrix, Nonlinear Anal. 46 (2001), 1133–1150.
  * [24] M. Torki, First- and second-order epi-differentiability in eigenvalue optimization, J. Math. Anal. Appl. 234 (1999), 391–416.