Variational Analysis of Composite Models
with Applications to Continuous Optimization
ASHKAN MOHAMMADI***Department of Mathematics, Wayne State University, Detroit,
MI 48202, USA (ashkan.mohammadi@wayne.edu). BORIS S. MORDUKHOVICH†††Department
of Mathematics, Wayne State University, Detroit, MI 48202, USA
(boris@math.wayne.edu). and M. EBRAHIM SARABI‡‡‡Department of Mathematics,
Miami University, Oxford, OH 45065, USA (sarabim@miamioh.edu).

Abstract. The paper is devoted to a comprehensive study of composite models in
variational analysis and optimization the importance of which for numerous
theoretical, algorithmic, and applied issues of operations research is
difficult to overstate. The underlying theme of our study is a systematical
replacement of conventional metric regularity and related requirements by much
weaker metric subregulatity ones that lead us to significantly stronger and
completely new results of first-order and second-order variational analysis
and optimization. In this way we develop extended calculus rules for first-
order and second-order generalized differential constructions with paying the
main attention in second-order variational theory to the new and rather large
class of fully subamenable compositions. Applications to optimization include
deriving enhanced no-gap second-order optimality conditions in constrained
composite models, complete characterizations of the uniqueness of Lagrange
multipliers and strong metric subregularity of KKT systems in parametric
optimization, etc.
Keywords. Composite constrained optimization, first-order and second-order
variational analysis and generalized differentiation, no-gap second-order
optimality conditions, metric subregularity and strong metric regularity,
subamenable compositions, parametric optimization.

##  1 Introduction and Overview

It has been well recognized in variational analysis, continuous optimization,
and their various applications that composite models involving extended-real-
valued functions of the type

$(\vartheta\circ f)(x):=\vartheta\big{(}f(x)\big{)},\quad x\in{\rm
I\\!R}^{n},$ (1.1)

constitute a very convenient framework for developing both theoretical and
algorithmic issues of constrained optimization with applications to practical
modeling in operations research. Standard assumptions under which composite
functions of type (1.1) are investigated and applied in constrained
optimization require that the mapping $f\colon{\rm I\\!R}^{n}\to{\rm
I\\!R}^{m}$ be twice continuously differentiable (${\cal C}^{2}$-smooth), that
the extended-real-valued function $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}:=(-\infty,\infty]$ be lower semicontinuous
(l.s.c.) and convex, and that the epigraphical set-valued mapping $H\colon{\rm
I\\!R}^{n}\times{\rm I\\!R}\rightrightarrows{\rm I\\!R}^{m}\times{\rm I\\!R}$
with $H(x,\alpha):=(f(x),\alpha)-\mbox{\rm epi}\,\vartheta$ be metrically
regular around the point in question. We refer the reader to the book by
Rockafellar and Wets [39] and the bibliographies therein for major facts on
the theory and applications of such compositions known as (strongly) amenable
functions, where the most perfect and complete results are obtained in the
case of fully amenable compositions dealing with piecewise linear-quadratic
outer functions $\vartheta$ in (1.1). The crucial metric regularity assumption
mentioned above can be equivalently described as the basic qualification
condition (or constraint qualification) expressed precisely at the reference
point in question; see Section 3 for more details and discussions.

It is important to emphasize that the possibility for $\vartheta$ to take the
infinity value $\infty$ allows us to incorporate constraints in the composite
unconstrained framework of (1.1). Indeed, while minimizing $\vartheta\circ f$
therein we automatically have the constraint $x\in{\Omega}:=\\{x\in{\rm
I\\!R}^{n}|\;f(x)\in\mbox{\rm dom}\,\vartheta\\}$, where $\mbox{\rm
dom}\,\vartheta:=\big{\\{}y\in{\rm I\\!R}^{m}|\;\vartheta(y)<\infty\\}$. On
the other hand, the constrained optimization problem

$\mbox{minimize }\;\varphi_{0}(x)\;\mbox{ subject to
}\;g(x)\in\Theta\subset{\rm I\\!R}^{m}$

can be written in the unconstrained form (1.1) via the functions
$\vartheta(\alpha,y):=\alpha+\delta_{\Theta}(y)$ and
$f(x):=(\varphi_{0}(x),g(x))$, where $\vartheta:{\rm
I\\!R}^{m+1}\to\overline{{\rm I\\!R}}$ is l.s.c. and $\delta_{\Theta}$ is the
indicator function of the set $\Theta$ that equals to $0$ on $\Theta$ and
$\infty$ otherwise. This framework encompasses, in particular, problems of
nonlinear programming (NLPs) where $\Theta$ is a polyhedron and problems of
conic programming where $\Theta$ is a closed convex cone.

The aforementioned metric regularity and the equivalent notions of linear
openness/covering and robust Lipschitzian behavior of set-valued
mappings/multifunctions are largely investigated in variational analysis and
are broadly applied to numerous topics in theoretical and computational
optimization, equilibria, sensitivity analysis, optimal control. The reader
may consult with the books by Borwein and Zhu [4], Dontchev and Rockafellar
[11], Ioffe [20], Klatte and Kummer [23], Mordukhovich [29, 30], Penot [32],
and Rockafellar and Wets [39] together with the references and commentaries
therein along with the enormous amount of other publications.

Among the main intentions of this paper is to develop a new variational
technique, which allows us to systematically replace metric regularity
qualification conditions by much more subtle metric subregularity ones. The
property of metric subregularity and its calmness equivalent for inverse
mappings are less developed and applied in comparison with their robust metric
regularity/Lipschitzian counterparts. While the latter properties admit
complete characterizations, which open the door for developing comprehensive
generalized differential calculus and various applications to optimization,
stability, and other areas of nonlinear analysis and operations research, the
study of metric subregularity and calmness is essentially more involved and
the obtained results are by far more limited. On the other hand, such
properties hold in many important settings where their robust counterparts are
out of reach. Some results and discussions related to these topics can be
found in the aforementioned monographs. We also refer the reader to the papers
by Aragón Artacho and Geoffroy [1], Chieu et al. [7], Drusvyatskiy et al.
[12], Gfrerer [13], Gfrerer and Outrata [16], Henrion and Outrata [18], Ioffe
and Outrata [21], Kruger [24], Li and Mordukhovich [25], Ye and Ye [40], and
Zheng and Ng [41] with the additional bibliographies therein for various
developments on metric subregularity and calmness properties and their
applications to optimality and stability conditions, error bounds, and
convergence of numerical algorithms.

The major goals of this paper are largely different from those considered in
the literature on metric regularity, calmness, and their applications. Along
with deriving refined calculus rules of first-order variational analysis under
enhanced metric subregularity qualification conditions, we mainly concentrate
on second-order variational analysis of compositions (1.1) for a novel class
of fully subamenable functions, where $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is l.s.c., convex, and piecewise linear-
quadratic, where $f\colon{\rm I\\!R}^{m}\to{\rm I\\!R}^{m}$ is twice
differentiable at the reference point, and where certain metric subregularity
qualification conditions are satisfied. This class of functions is a direct
extension of the fully amenable one, introduced by Rockafellar [36], who
imposed more restrictive metric regularity constraint qualifications, which
allowed him to employ robust machinery of generalized differentiation; see the
book [39] by Rockafellar and Wets for further developments and applications.
The subregularity framework adopted here covers an essentially larger
territory (including important settings where our subregularity conditions
hold automatically), while it requires to develop fairly different techniques.
The suggested variational approach allows us not only to significantly extend
the known second-order calculus rules, but also to simplify their proofs and
to obtain important results, which are new even in the case of metric
regularity constraint qualifications.

Arguing in this way with a systematic usage of metric subregularity and
variational ideas, we establish enhanced first-order chain rules for
subderivatives and subdifferential mappings in rather general settings and
then proceed with developing advanced second-order calculus for fully
subamenable compositions. Our analysis in this paper mainly addresses second-
order generalized differential constructions of the primal type (second and
parabolic subderivatives) and primal-dual type (subgradient graphical
derivatives) along with the associated second-order geometric objects. For all
of them we develop extended second-order calculus rules under metric
subregularity qualification conditions and also efficiently compute these
constructions for fully subamenable compositions.

Besides employing variational techniques to derive the major second-order
calculus and computational results, this paper develops a variety of
applications to composite optimization and variational stability under the
metric subregularity constraint qualification. Among such applications we
mention no-gap second-order optimality conditions for composite optimization
problems, characterizations of the uniqueness of Lagrange multipliers in the
corresponding KKT (Karush-Kuhn-Tucker) systems, and characterizations of
robust isolated calmness for solution maps to parameterized generalizes
equations.

The rest of the paper is organized as follows. In Section 2 we recall the
basic notions of variational analysis that are broadly used below and present
some preliminary results. Section 3 is devoted to first-order variational
analysis of compositions (1.1). We introduce here a new metric subregularity
qualification condition for (1.1), discuss its relationships with the known
ones in this setting, and employ it to derive enhanced first-order chain rules
of the equality type for subderivatives and subgradient mappings.

In Section 4 we start developing second-order variational analysis of
composite functions with the main emphasis on a novel class of fully
subamenable compositions. First we define the critical cone of an l.s.c.
function and prove that the critical cone agrees with the domain of the second
subderivative under a certain second-order sufficient condition. Then we show
that this second-order condition automatically holds if the function in
question is fully subamenable.

In the Section 5, we prove that any fully subamenable function enjoys the
powerful property of twice epi-differentiability and derive precise formulas
for calculating its second subderivative. Section 6 develops applications of
the obtained second-order calculus to deriving no-gap second-order necessary
and sufficient optimality conditions for optimization problems with
constraints given by fully subamenable compositions. The underlying metric
subregularity qualification condition serves now as a refined constraint
qualification ensuring in generality the validity of first-order
optimality/stationarity conditions in the normal/KKT form and then the
fulfillment of the aforementioned no-gap second-order optimality conditions in
the case of fully subamenable constraints.

Section 7 addresses yet another second-order generalized derivative for l.s.c.
functions known as the proto-derivative. For fully subamenable compositions,
we derive a precise calculation formula representing the proto-derivative of
their subgradient mappings entirely via the given data.

Section 8 is devoted to applications of the above computations of the proto-
derivative to the important and somewhat interconnected issues of parametric
composite optimization concerning the uniqueness of Lagrange multiplies and
strong metric subregularity of solution maps to KKT systems. In this way we
derive, in particular, constructive second-order characterizations of strong
metric subregularity of solution maps to the KKT systems associated with
(1.1), where the outer function $\vartheta$ is piecewise linear-quadratic. One
of the these characterizations provides a new and much simpler proof of the
recent result due to Burke and Engle [6]. Concluding remarks in Section 9
briefly summarize major results of the paper and discuss some directions of
the future research.

Notation and terminology of this paper are standard in variational analysis
and optimization. They are mainly taken, together with the preliminaries in
Section 2, from the books by Rockafellar and Wets [39] and by Mordukhovich
[30]. For the reader’s convenience and notational unification we usually use
small Greek letters to denote scalar and extended-real-valued functions, small
Latin letters for vectors and single-valued mappings/vector functions, and
capital letters for sets, set-valued mappings, and matrices. Given a nonempty
set ${\Omega}$ and vector $x$ in the Euclidean space ${\rm I\\!R}^{n}$, denote
by ${\rm dist}(x;{\Omega})$ the distance between $x$ and ${\Omega}$. The
notation $\mbox{\rm co}\,{\Omega}$ stands for the convex hull of ${\Omega}$,
while the symbol $x\stackrel{{\scriptstyle{\Omega}}}{{\to}}\bar{x}$ indicates
that $x\to\bar{x}$ with $x\in{\Omega}$. 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$. The symbol $\\{v\\}^{\bot}$
with $v\in{\rm I\\!R}^{n}$ stands for the orthogonal subspace $\\{w\in{\rm
I\\!R}^{n}|\;\langle w,v\rangle=0\\}$. The space of $n\times n$ matrices is
denoted by ${\rm I\\!R}^{n\times n}$. As always, the vector quantity $x=o(t)$
with $t>0$ means that $\|x\|/t\to 0$ as $t\downarrow 0$. Recall also that
${\rm I\\!R}_{+}$ and ${\rm I\\!R}_{-}$ signify, respectively, the collection
of nonnegative and nonpositive real numbers, and that ${\rm
I\\!N}:=\\{1,2,\ldots\\}$. Given a scalar function $\varphi\colon{\rm
I\\!R}^{n}\to{\rm I\\!R}$, denote by $\nabla\varphi(\bar{x})$ and
$\nabla^{2}\varphi(\bar{x})$ the gradient and Hessian of $\varphi$ at
$\bar{x}$, respectively. If $f=(f_{1},\ldots,f_{m})\colon{\rm
I\\!R}^{n}\to{\rm I\\!R}^{m}$ is a vector function twice differentiable at
$\bar{x}\in{\rm I\\!R}^{n}$, its second derivative at this point, denoted by
$\nabla^{2}f(\bar{x})$, is a bilinear mapping from ${\rm I\\!R}^{n}\times{\rm
I\\!R}^{n}$ into ${\rm I\\!R}^{m}$. In what follows we use the notation
$\nabla^{2}f(\bar{x})(w,v)$, which means that

$\nabla^{2}f(\bar{x})(w,v)=\big{(}\big{\langle}\nabla^{2}f_{1}(\bar{x})w,v\big{\rangle},\ldots,\big{\langle}\nabla^{2}f_{m}(\bar{x})w,v\big{\rangle}\big{)}\;\mbox{
for all }\;v,w\in{\rm I\\!R}^{n}.$

##  2 Basic Definitions and Preliminaries

We begin with recalling the well-known notions of variational analysis and
generalized differentiation that are largely utilized and studied throughout
the entire paper. Given a nonempty set ${\Omega}\subset{\rm I\\!R}^{n}$ with
$\bar{x}\in{\Omega}$, the (Bouligand-Severi) tangent/contingent cone
$T_{\Omega}(\bar{x})$ to ${\Omega}$ at $\bar{x}\in{\Omega}$ is

$T_{\Omega}(\bar{x}):=\big{\\{}w\in{\rm
I\\!R}^{n}\big{|}\;\exists\,t_{k}{\downarrow}0,\;\exists\,w_{k}\to w\;\mbox{
as }\;k\to\infty\;\;\mbox{with}\;\;\bar{x}+t_{k}w_{k}\in{\Omega}\big{\\}}.$
(2.1)

We say that a tangent vector $w\in T_{\Omega}(\bar{x})$ is derivable if there
exists $\xi\colon[0,\varepsilon]\to{\Omega}$ with $\varepsilon>0$,
$\xi(0)=\bar{x}$, and $\xi^{\prime}_{+}(0)=w$, where the right derivative
$\xi^{\prime}_{+}$ of $\xi$ at $0$ is defined by

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

The set ${\Omega}$ is geometrically derivable at $\bar{x}$ if every tangent
vector $w$ to ${\Omega}$ at $\bar{x}$ is derivable. This class of sets is
sufficiently broad and includes, in particular, prox-regular sets and
subdifferential graphs of convex piecewise linear-quadratic functions that are
widely used in what follows.

The (Fréchet) regular normal cone to ${\Omega}$ at $\bar{x}\in{\Omega}$ is

$\widehat{N}_{\Omega}(\bar{x}):=\Big{\\{}v\in{\rm
I\\!R}^{n}\Big{|}\;\limsup_{x\stackrel{{\scriptstyle{\Omega}}}{{\to}}\bar{x}}\frac{\langle
v,x-\bar{x}\rangle}{\|x-\bar{x}\|}\leq 0\Big{\\}},$ (2.2)

which can be equivalently described as the polar of the contingent cone
$\widehat{N}_{\Omega}(\bar{x})=T_{\Omega}(\bar{x})^{*}$. The (Mordukhovich)
basic/limiting normal cone to ${\Omega}$ at $\bar{x}$ is defined by

$\displaystyle N_{\Omega}(\bar{x})=\big{\\{}v\in{\rm
I\\!R}^{n}\;\big{|}\;\exists\,x\stackrel{{\scriptstyle{\Omega}}}{{\to}}\bar{x},\;v_{k}\to
v\;\;\mbox{with}\;\;v_{k}\in\widehat{N}_{\Omega}(x_{k})\;\mbox{ for all
}\;k\in{\rm I\\!N}\big{\\}}.$ (2.3)

If the set ${\Omega}$ is convex, then both constructions (2.2) and (2.3)
reduce to the classical normal cone of convex analysis. We say that ${\Omega}$
normally regular at $\bar{x}\in{\Omega}$ if
$\widehat{N}_{\Omega}(\bar{x})=N_{\Omega}(\bar{x})$.

Given a function $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ with
$\bar{x}\in\mbox{\rm dom}\,\varphi:=\\{x\in{\rm
I\\!R}^{n}|\;\varphi(x)<\infty\\}$, the regular subdifferential and the
limiting subdifferential of $\varphi$ at $\bar{x}$ are defined via the regular
(2.2) and limiting (2.3) normal cones to the epigraph $\mbox{\rm
epi}\,\varphi:=\\{(x,\alpha)\in{\rm I\\!R}^{n}\times{\rm
I\\!R}|\;\alpha\geq\varphi(x)\\}$ of $\varphi$ by

$\displaystyle\begin{array}[]{ll}&\widehat{\partial}\varphi(\bar{x}):=\big{\\{}v\in{\rm
I\\!R}^{n}\big{|}\;(v,-1)\in\widehat{N}_{{\scriptsize\mbox{\rm
epi}\,\varphi}}\big{(}\bar{x},\varphi(\bar{x})\big{)}\big{\\}},\\\
&\partial\varphi(\bar{x}):=\big{\\{}v\in{\rm I\\!R}^{n}\big{|}\;(v,-1)\in
N_{{\scriptsize\mbox{\rm
epi}\,\varphi}}\big{(}\bar{x},\varphi(\bar{x})\big{)}\big{\\}},\end{array}$
(2.6)

respectively. We say that $\varphi$ is lower regular at $\bar{x}$ if
$\partial\varphi(\bar{x})=\widehat{\partial}\varphi(\bar{x})$. Note that this
notion does not reduce to the subdifferential regularity for non-Lipschitzian
functions $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$. On the
other hand, the normal regularity of sets agrees for locally closed sets in
finite-dimensional spaces (while not in infinite dimensions) with the
(directional) Clarke regularity; see Corollary 6.29 in the book by Rockafellar
and Wets [39]. In what follows we prefer to use the regularity terminology
from the books by Mordukhovich [29, 30].

For a set-valued mapping $F\colon{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{m}$ with its domain and graph given by

$\mbox{\rm dom}\,F:=\big{\\{}x\in{\rm
I\\!R}^{n}\big{|}\;F(x)\neq\emptyset\big{\\}}\;\mbox{ and }\;\mbox{\rm
gph}\,F:=\big{\\{}(x,y)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}\big{|}\;y\in
F(x)\big{\\}},$

respectively, its graphical derivative $DF(\bar{x},\bar{y})\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ at $(\bar{x},\bar{y})\in\mbox{\rm
gph}\,F$ is defined via the tangent cone (2.1) to its graph at
$(\bar{x},\bar{y})$ by

$DF(\bar{x},\bar{y})(u):=\big{\\{}v\in{\rm I\\!R}^{m}\big{|}\;(u,v)\in
T_{\scriptsize{\mbox{\rm gph}\,F}}(\bar{x},\bar{y})\big{\\}}\;\mbox{ for all
}\;u\in{\rm I\\!R}^{n},$ (2.7)

while its coderivative $D^{*}F(\bar{x},\bar{y})\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ at this point is given by

$D^{*}F(\bar{x},\bar{y})(v):=\big{\\{}u\in{\rm I\\!R}^{n}\big{|}\;(u,-v)\in
N_{\scriptsize{\mbox{\rm gph}\,F}}(\bar{x},\bar{y})\big{\\}},\quad v\in{\rm
I\\!R}^{m}.$ (2.8)

One of the central well-posedness concepts in nonlinear analysis with great
many applications is the metric regularity of $F\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ around
$(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$ postulated as the existence of a
constant $\kappa\in{\rm I\\!R}_{+}$ and neighborhoods $U$ of $\bar{x}$ and $V$
of $\bar{y}$ such that

${\rm dist}\big{(}x;F^{-1}(y)\big{)}\leq\kappa\,{\rm
dist}\big{(}y;F(x)\big{)}\quad\mbox{for all}\quad(x,y)\in U\times V.$ (2.9)

If $y=\bar{y}$ in (2.9), the mapping $F$ is said to be metrically subregular
at $(\bar{x},\bar{y})$.

As mentioned in Section 1, metric regularity and the equivalent
covering/linear openness and Lipschitzian properties of multifunctions admit
complete characterizations via generalized differentiation. In this paper we
employ the following result known as the Mordukhovich/coderivative criterion,
which amounts to saying that a closed-graph mapping $F\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ is metrically regular around
$(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$ with some modulus $\kappa\in{\rm
I\\!R}_{+}$ if and only if

${\rm ker}\,D^{*}F(\bar{x},\bar{y})=\big{\\{}0\big{\\}},$ (2.10)

where ${\rm ker}\,G:=\\{v\in{\rm I\\!R}^{m}|\;0\in G(v)\\}$ is the kernel of a
set-valued mapping $G\colon{\rm I\\!R}^{m}\rightrightarrows{\rm I\\!R}^{n}$;
see Mordukhovich [28, 29, 30] and the book by Rockafellar and Wets [39] with
the references therein for different proofs and discussions. The broad
applicability of criterion (2.10) is largely due to full calculus available
for the coderivative (2.8) that is based on variational and extremal
principles of variational analysis.

Results of such a type are not available for metric subregularity in general.
This makes the justification of this property significantly more challenging
for major classes of constrained and composite optimization problems. Yet the
latter property is satisfied in many important situations where metric
regularity fails. This can happen, in particular, for problems with a
polyhedral structure including the composite function (1.1) with a convex
piecewise linear-quadratic outer function $\vartheta$ and an affine inner
function $f$.

We say that $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is
piecewise linear-quadratic (PWLQ) if $\mbox{\rm
dom}\,\varphi=\cup_{i=1}^{s}{\Omega}_{i}$ with ${\Omega}_{i}$ being polyhedral
convex sets for $i=1,\ldots,s$, and if $\varphi$ has a representation of the
form

$\varphi(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{\Omega}_{i},$ (2.11)

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 all $i=1,\ldots,s$. Recall also that
$\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is (locally) Lipschitz
continuous around $\bar{x}\in\mbox{\rm dom}\,\varphi$ relative to some set
${\Omega}\subset\mbox{\rm dom}\,\varphi$ if there exist a constant
$\ell\in{\rm I\\!R}_{+}$ and a neighborhood $U$ of $\bar{x}$ such that

$|\varphi(x)-\varphi(u)|\leq\ell\|x-u\|\quad\mbox{for all }\quad
x,u\in{\Omega}\cap U.$

Piecewise linear-quadratic and indicator functions are simple albeit important
examples of extended-real-valued functions that are Lipschitz continuous
relative to their domains around every point therein.

A more delicate property (than the local Lipschitz continuity) of extended-
real-valued functions $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$
at the point in question is the calmness from below of $\varphi$ at
$\bar{x}\in\mbox{\rm dom}\,\varphi$ meaning that there exist a constant
$\ell\in{\rm I\\!R}_{+}$ and a neighborhood $U$ of $\bar{x}$ such that

$\varphi(x)\geq\varphi(\bar{x})-\ell\|x-\bar{x}\|\quad\mbox{for all}\quad x\in
U.$ (2.12)

The following proposition describes useful consequences of this notion that is
employed below.

######  Proposition 2.1 (existence of subgradients).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be l.s.c. around
$\bar{x}\in\mbox{\rm dom}\,\varphi$ and calm from below at this point with
constant $\ell\in{\rm I\\!R}_{+}$. Then we have
$\partial\varphi(\bar{x})\cap\ell\mathbb{B}\neq\emptyset$. This ensures that
$\partial\varphi(\bar{x})\neq\emptyset$ for any function $\varphi$ that is
piecewise linear-quadratic.

[Proof.] The calmness from below (2.12) clearly implies that the function

$\psi(x):=\varphi(x)+\ell\|x-\bar{x}\|,\quad x\in{\rm I\\!R}^{n},$

attains its local minimum at $\bar{x}$. Then the subdifferential Fermat rule
tells us that $0\in\partial\psi(\bar{x})$. Taking into account that $\varphi$
is l.s.c. around $\bar{x}$ while the function $x\mapsto\|x-\bar{x}\|$ is
obviously locally Lipschitzian, we use the semi-Lipschitzian sum rule from
Theorem 2.33(c) in Mordukhovich [29] to conclude that
$0\in\partial\psi(\bar{x})\subset\partial\varphi(\bar{x})+\ell\mathbb{B}$,
which verifies the first assertion of the proposition.

If $\varphi$ is piecewise linear-quadratic, it follows from (2.11) that

$\varphi(x)=\min_{1\leq i\leq
s}\big{\\{}\varphi_{i}(x)+\delta_{{\Omega}_{i}}(x)\big{\\}}\;\mbox{ with
}\varphi_{i}(x):=\hbox{${1\over 2}$}\langle A_{i}x,x\rangle+\langle
a_{i},x\rangle+\alpha_{i}$

and with ${\Omega}_{i}$ taken from (2.11). This representation easily implies
that $\varphi$ is calm from below with some constant $\kappa\in{\rm
I\\!R}_{+}$ at any point of its domain. This yields
$\partial\varphi(\bar{x})\neq\emptyset$ for any $\bar{x}\in\mbox{\rm
dom}\,\varphi$ due to the first assertion of this proposition.

Note that the first part of Proposition 2.1 can be deduced from Proposition
8.32 in Rockafellar and Wets [39] by using a different approach, while the
second part is verified in Proposition 10.21 of that book when $\varphi$ is
assumed in addition to be convex.

To finish with the first-order constructions, recall that the subderivative of
$\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ at
$\bar{x}\in\mbox{\rm dom}\,\varphi$ is a positively homogeneous function ${\rm
d}\varphi(\bar{x})\colon{\rm I\\!R}^{n}\to[-\infty,\infty]$ defined by

${\mathrm{d}}\varphi(\bar{x})(\bar{w}):=\displaystyle\liminf_{\begin{subarray}{c}t\downarrow
0\\\
w\to\bar{w}\end{subarray}}{\frac{\varphi(\bar{x}+tw)-\varphi(\bar{x})}{t}}\;\mbox{
for any }\;\bar{w}\in{\rm I\\!R}^{n}.$ (2.13)

There is the well-known duality correspondence between the subderivative
(2.13) and the regular subdifferential of $\varphi$ at $\bar{x}$ taken from
(2.6):

$\widehat{\partial}\varphi(\bar{x})=\big{\\{}v\in{\rm
I\\!R}^{n}\big{|}\;\langle v,w\rangle\leq{\rm d}\varphi(\bar{x})(w),\quad
w\in{\rm I\\!R}^{n}\big{\\}}.$ (2.14)

If $\varphi$ is convex and piecewise linear-quadratic, then for any
$\bar{x}\in\mbox{\rm dom}\,\varphi$ we get from Proposition 10.21 in
Rockafellar and Wets [39] that

$\mbox{\rm dom}\,{\rm d}\varphi(\bar{x})=T_{\scriptsize\mbox{\rm
dom}\,\varphi}(\bar{x})=\bigcup_{i\in
I(\bar{x})}T_{{\Omega}_{i}}(\bar{x})\quad\mbox{with}\quad
I(\bar{x}):=\big{\\{}i\in\\{1,\ldots,s\\}\big{|}\;\bar{x}\in{\Omega}_{i}\big{\\}}.$
(2.15)

Furthermore, for any $w\in\mbox{\rm dom}\,{\rm d}\varphi(\bar{x})$ there
exists an index $i\in I(\bar{x})$ such that $w\in T_{{\Omega}_{i}}(\bar{x})$
and

${\rm d}\varphi(\bar{x})(w)=\langle A_{i}\bar{x}+a_{i},w\rangle.$ (2.16)

Proceed now with the primal second-order constructions studied in this paper.
Form the parametric family of second-order difference quotients of $\varphi$
at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for some $\bar{v}\in{\rm I\\!R}^{n}$ by

$\Delta_{t}^{2}\varphi(\bar{x},\bar{v})(w):=\dfrac{\varphi(\bar{x}+tw)-\varphi(\bar{x})-t\langle\bar{v},w\rangle}{\hbox{${1\over
2}$}t^{2}}\quad\mbox{with }\;w\in{\rm I\\!R}^{n},\;t>0.$

The second-order subderivative ${\rm d}^{2}\varphi(\bar{x},\bar{v})\colon{\rm
I\\!R}^{n}\to[-\infty,\infty]$ of $\varphi$ at $\bar{x}$ for $\bar{v}$ is
defined by

${\rm
d}^{2}\varphi(\bar{x},\bar{v})(w):=\liminf_{\begin{subarray}{c}t\downarrow
0\\\ u\to w\end{subarray}}\Delta_{t}^{2}\varphi(\bar{x},\bar{v})(u),\quad
w\in{\rm I\\!R}^{n}.$ (2.17)

It is said that $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is
twice epi-differentiable at $\bar{x}$ for $\bar{v}$ if the second-order
difference quotients $\Delta_{t}^{2}\varphi(\bar{x},\bar{v})$ epi-converge to
${\rm d}^{2}\varphi(\bar{x},\bar{v})$ as $t\downarrow 0$; see Definition 7.1
in Rockafellar and Wets [39]. If in addition the second subderivative (2.17)
is a proper function, then $\varphi$ is called properly twice epi-
differentiable at $\bar{x}$ for $\bar{v}$. Recall that the above properness
means that ${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)>-\infty$ for all $w\in{\rm
I\\!R}^{n}$ with $\mbox{\rm dom}\,{\rm
d}^{2}\varphi(\bar{x},\bar{v})\neq\emptyset$. Recall also from Proposition 7.2
in Rockafellar and Wets [39] that the twice epi-differentiability of $\varphi$
at $\bar{x}$ for $\bar{v}$ can be equivalently described as follows: for every
$w\in{\rm I\\!R}^{n}$ and every sequence $t_{k}\downarrow 0$ there exists a
sequence $w_{k}\to w$ such that

$\Delta_{t_{k}}^{2}\varphi(\bar{x},\bar{v})(w_{k})\to{\rm
d}^{2}\varphi(\bar{x},\bar{v})(w)\;\mbox{ as }\;k\to\infty.$ (2.18)

Turning to second-order variational geometry and given ${\Omega}\subset{\rm
I\\!R}^{n}$ with $\bar{x}\in{\Omega}$, define the second-order tangent set to
${\Omega}$ at $\bar{x}$ for a tangent vector $w\in T_{\Omega}(\bar{x})$ by

$T_{\Omega}^{2}(\bar{x},w)=\big{\\{}u\in{\rm
I\\!R}^{n}\big{|}\;\exists\,t_{k}{\downarrow}0,\;\exists\,u_{k}\to u\;\mbox{
as }\;k\to\infty\;\;\mbox{with}\;\;\bar{x}+t_{k}w+\hbox{${1\over
2}$}t_{k}^{2}u_{k}\in{\Omega}\big{\\}}.$ (2.19)

A set ${\Omega}$ is said to be parabolically derivable at $\bar{x}$ for $w$ if
$T_{\Omega}^{2}(\bar{x},w)\neq\emptyset$ and for each $u\in
T_{\Omega}^{2}(\bar{x},w)$ there exists $\xi\colon[0,\varepsilon]\to{\Omega}$
with $\varepsilon>0$, $\xi(0)=\bar{x}$, and $\xi^{\prime}_{+}(0)=w$ such that
$\xi^{\prime\prime}_{+}(0)=u$, where

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

We conclude this section with the following simple and useful fact about the
second-order tangent set to the domain of a convex piecewise linear-quadratic
function.

######  Proposition 2.2 (second-order tangent sets to domains of convex PWLQ
functions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a convex
piecewise linear-quadratic function with $\bar{x}\in\mbox{\rm dom}\,\varphi$,
and let $w\in\mbox{\rm dom}\,{\rm d}\varphi(\bar{x})$. Then we have the
representation

$T_{\scriptsize\mbox{\rm dom}\,\varphi}^{2}(\bar{x},w)=\bigcup_{i\in
J(\bar{x},w)}T_{{\Omega}_{i}}^{2}(\bar{x},w),$ (2.20)

where ${\Omega}_{i}$ are taken from (2.11), and where

$J(\bar{x},w):=\big{\\{}i\in I(\bar{x})\big{|}\;w\in
T_{{\Omega}_{i}}(\bar{x})\big{\\}}$ (2.21)

with the index set $I(\bar{x})$ defined in (2.15).

[Proof.] The inclusion “$\supset$” in (2.20) is an immediate consequence of
the fact that ${\Omega}_{i}\subset\mbox{\rm dom}\,\varphi$ for all
$i=1,\ldots,s$. The opposite inclusion therein follows from the representation
of $\mbox{\rm dom}\,\varphi$ as the finite union of the polyhedral convex sets
${\Omega}_{i}$.

##  3 First-Order Chain Rules under Metric Subregularity

This section is mainly devoted to first-order variational analysis of general
composite functions of type (1.1). Among other issues, it contains the
introduction and study of the new metric subregularity qualification
condition, which plays a crucial role in both first-order and second-order
variational analysis conducted in this paper as well as in their applications
to optimization.

We begin with the following proposition, which formulates major qualification
conditions (including the new one) for deriving chain rules for compositions
(1.1) and then establishes relationships between them. Note that in
applications to optimization, where compositions (1.1) are used for modeling
constraints, such conditions play a role of constraint qualifications and are
often labeled in this way. On the other hand, we consider them as a tool of
analysis, which is not applied only to constrained optimization. Observe that
the qualification conditions formulated below specifically address
compositions of type (1.1) and are not defined for arbitrary set-valued or
single-valued mappings.

######  Proposition 3.1 (relationships between qualification conditions).

Let $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ be a single-valued mapping
differentiable at some point $\bar{x}\in R^{n}$, and let $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ be a proper extended-real-valued function
continuous relative to its domain. Form the composition (1.1), assume that
$\vartheta(f(\bar{x}))$ is finite, and consider the following qualification
conditions:

(i) The set-valued mapping $H\colon{\rm I\\!R}^{n}\times{\rm
I\\!R}\rightrightarrows{\rm I\\!R}^{m}\times{\rm I\\!R}$ defined by
$H(x,\alpha):=(f(x),\alpha)-\mbox{\rm epi}\,\vartheta$ is metrically regular
around the point $\big{(}(\bar{x},\vartheta(f(\bar{x}))),(0,0)\big{)}$.

(ii) The set-valued mapping $H$ defined in (i) is metrically subregular at
$\big{(}(\bar{x},\vartheta(f(\bar{x}))),(0,0)\big{)}$.

(iii) The set-valued mapping $G\colon{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}$ defined by $G(x):=f(x)-\mbox{\rm dom}\,\vartheta$ is metrically
subregular at the point $(\bar{x},0)$.
Then we always have the implications (i)$\implies$(ii)$\implies$(iii).

[Proof.] Implication (i)$\implies$(ii) is obvious. To verify the second
implication, suppose that (ii) holds and thus find a constant $\kappa\geq 0$
as well as the neighborhoods $U$ of $\bar{x}$ and $V$ of
$\vartheta(f(\bar{x}))$ such that

${\rm dist}\big{(}(x,\alpha);\mbox{\rm epi}\,\varphi)\leq\kappa\,{\rm
dist}\big{(}(f(x),\alpha);\mbox{\rm epi}\,\vartheta)\quad\mbox{for
all}\quad(x,\alpha)\in U\times V.$ (3.1)

Picking $x\in U$ and $\varepsilon>0$, we get a vector $y\in\mbox{\rm
dom}\,\vartheta$ such that

$\|f(x)-y\|<{\rm dist}\big{(}f(x);\mbox{\rm
dom}\,\vartheta\big{)}+\varepsilon,$

which implies in turn the upper estimates

$\|y-f(\bar{x})\|\leq\|f(x)-f(\bar{x})\|+\|y-f(x)\|\leq
2\|f(x)-f(\bar{x})\|+\varepsilon.$

Since $\vartheta$ is continuous at $f(\bar{x})$ relative to its domain,
suppose by shrinking the neighborhood $U$ if necessary that $\vartheta(y)\in
V$. Using this together with (3.1) ensures the inequalities

$\displaystyle{\rm dist}\big{(}(x,\vartheta(y));\mbox{\rm
epi}\,\varphi\big{)}$ $\displaystyle\leq$ $\displaystyle\kappa\,{\rm
dist}\big{(}(f(x);\vartheta(y));\mbox{\rm epi}\,\vartheta\big{)}$
$\displaystyle\leq$
$\displaystyle\kappa\|f(x)-y\|+|\vartheta(y)-\vartheta(y)|<\kappa\,{\rm
dist}\big{(}f(x);\mbox{\rm dom}\,\vartheta\big{)}+\varepsilon.$

On the other hand, for all $(x,\alpha)\in{\rm I\\!R}^{n}\times{\rm I\\!R}$ we
always have

${\rm dist}(x;\mbox{\rm dom}\,\varphi)\leq{\rm
dist}\big{(}(x,\alpha);\mbox{\rm epi}\,\varphi\big{)}.$

Combining the above inequalities with $G^{-1}(0)=\mbox{\rm dom}\,\varphi$ and
(3.1) brings us to the inequalities

${\rm dist}\big{(}x;G^{-1}(0)\big{)}={\rm dist}(x;\mbox{\rm
dom}\,\varphi)\leq\kappa\,{\rm dist}\big{(}(x,\vartheta(y));\mbox{\rm
epi}\,\varphi\big{)}\leq\kappa^{2}\,{\rm dist}\big{(}f(x);\mbox{\rm
dom}\,\vartheta\big{)}+\kappa\varepsilon,$

and therefore results in the distance estimate

${\rm dist}\big{(}x;G^{-1}(0)\big{)}\leq\kappa^{2}\,{\rm
dist}\big{(}f(x);\mbox{\rm dom}\,\vartheta\big{)}\quad\mbox{for all}\quad x\in
U.$

This clearly yields (iii) and hence completes the proof.

It easily follows from the coderivative criterion for metric regularity (2.10)
applied to the set-valued mapping $H$ in Proposition 3.1 that the
qualification condition in (i) of that proposition can be equivalently
written, in the case where $f$ is smooth and $\vartheta$ is l.s.c., as

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

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{\\}},$ (3.3)

and where the symbol ∗ stands for the matrix transposition/adjoint operator.
The metric regularity qualification condition (3.3) serves as the most
advanced constraint qualification in first-order variational analysis and its
various applications to constrained and composite optimization problems; see,
e.g., the monographs by Mordukhovich [29, 30] and by Rockafellar and Wets [39]
with the references therein. For particular classes of optimization problems,
condition (3.2) reduces to the classical Mangasarian-Fromovitz constraint
qualification in nonlinear programming, and to the Robinson constraint
qualification in conic programming, where $\vartheta$ is the indicator
function of a closed convex cone. Note that when $\vartheta$ is convex, the
metric regularity qualification condition (3.2) can be equivalently
represented in the form

$N_{\scriptsize\mbox{\rm dom}\,\vartheta}\big{(}f(\bar{x})\big{)}\cap\mbox{\rm
ker}\,\nabla f(\bar{x})^{*}=\\{0\\}.$ (3.4)

It has been well recognized in variational analysis and documented in the
aforementioned monographs that the metric regularity qualification condition
and its implementations in (3.2) and (3.4) ensure the first-order
subdifferential chain rule

$\partial(\vartheta\circ f)(\bar{x})\subset\nabla
f(\bar{x})^{*}\partial\vartheta\big{(}f(\bar{x})\big{)},$

which holds as equality provided that $\vartheta$ is lower regular at
$\bar{y}:=f(\bar{x})$. Ioffe and Outrata [21] significantly improved this
chain rule by replacing in its assumptions the metric regularity qualification
condition (3.2) (labeled in [21] as the “standard Mordukhovich-Rockafellar
subdifferential qualification condition”) with the metric subregularity of the
epigraphical mapping $H$ in Proposition 3.1(ii). However, this result does not
cover, e.g., a particular setting of our interest in this paper for the
composite function (1.1), where $\vartheta$ is a convex piecewise linear-
quadratic function and $f$ is an affine mapping. The chain rule of the
equality type for the latter case, important in first-order and second-order
variational analysis, holds automatically if the metric subregularity of the
epigraphical mapping $H$ in Proposition 3.1(ii) is replaced by a weaker (and
simpler) metric subregularity of the domain mapping $G(x)=f(x)-\mbox{\rm
dom}\,\vartheta$ from condition (iii) of that proposition. Indeed, the metric
subregularity of this domain mapping results from the classical Hoffman lemma
[19] for the aforementioned case of (1.1); see Corollary 3.8 below.

The above discussion motivates the following definition that plays a central
role in both first-order and second-order developments and their applications
in this paper.

######  Definition 3.2 (metric subregularity qualification condition).

Given $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ and $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$, we say that the composition
$\vartheta\circ f$ satisfies the metric subregularity qualification condition
(MSQC) at $\bar{x}\in\mbox{\rm dom}\,f$ with constant $\kappa\in{\rm
I\\!R}_{+}$ if the mapping $x\mapsto f(x)-\mbox{\rm dom}\,\vartheta$ is
metrically subregular at $(\bar{x},0)$ with this constant.

Taking into account the structure of the mapping $f-\mbox{\rm dom}\,\vartheta$
in Definition 3.2 and using (2.9) with the fixed vector $y=\bar{y}=0$, observe
that the introduced MSQC with a prescribed constant $\kappa\in{\rm I\\!R}_{+}$
can be equivalently described via the existence of a neighborhood $U$ of
$\bar{x}$ such that the distance estimate

${\rm dist}(x;{\Omega})\leq\kappa\,{\rm dist}\big{(}f(x);\mbox{\rm
dom}\,\vartheta\big{)}\quad\mbox{with}\quad{\Omega}:=\big{\\{}x\in{\rm
I\\!R}^{n}\big{|}\;f(x)\in\mbox{\rm dom}\,\vartheta\big{\\}}$ (3.5)

is satisfied for all $x\in U$ with the same number $\kappa$ as in Definition
3.2.

As mentioned earlier, while metric regularity can be fully characterized via
the coderivative, finding conditions under which metric subregularity holds is
rather challenging. When, however, the outer function $\vartheta$ is convex
piecewise linear-quadratic that yields the polyhedrality of $\mbox{\rm
dom}\,\vartheta$, Gfrerer [14, Theorem 2.6] achieved a rather simple and
verifiable second-order condition to ensure the validity of the MSCQ (3.5).
His second-order condition in the framework of Definition 3.2 demonstrates
that if in addition $f$ is twice differentiable at $\bar{x}$ and if for every
$w\in{\rm I\\!R}^{n}\setminus\\{0\\}$ with $\nabla f(\bar{x})w\in
T_{\scriptsize\mbox{\rm dom}\,\vartheta}(f(\bar{x}))$ and every $\lambda\in
N_{\scriptsize\mbox{\rm dom}\,\vartheta}\big{(}f(\bar{x})\big{)}\cap\mbox{\rm
ker}\,\nabla f(\bar{x})^{*}$ the implication

$\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\rangle\geq 0\implies\lambda=0$ (3.6)

holds, then the mapping $x\mapsto f(x)-\mbox{\rm dom}\,\vartheta$ is
metrically subregular at $(\bar{x},0)$.

The following example provides two cases of the composite functions (1.1) with
$\vartheta$ being convex piecewise linear-quadratic such that the metric
regularity qualification condition fails while the metric subregularity
qualification condition is satisfied.

######  Example 3.3 (failure of metric regularity for composite functions).

Consider the class of extended-real-valued functions $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ defined by

$\vartheta(y):=\sup_{u\in Z}\big{\\{}\langle y,z\rangle-\hbox{${1\over
2}$}\langle Bz,z\rangle\big{\\}},$ (3.7)

where $Z$ is a polyhedral convex set, and where $B$ is an $m\times m$
positive-semidefinite symmetric matrix. This type of penalty functions was
introduced by Rockafellar [38], where he formulated an important class of
composite optimization problems under the name of extended nonlinear
programming (ENLP). It is not hard to see that $\vartheta$ is a convex
piecewise linear-quadratic function.

(a) Consider the function $\vartheta$ from (3.7) with $m=2$,

$Z:={\rm I\\!R}^{2},\;\mbox{ and }\;B:=\begin{pmatrix}1&0\\\ 0&0\end{pmatrix}$

and define the constraint mapping $f\colon{\rm I\\!R}^{2}\to{\rm I\\!R}^{2}$
by $f(x_{1},x_{2}):=(x_{1}-x_{2},0)$. It is easy to check that $\mbox{\rm
dom}\,\vartheta=\\{(y_{1},y_{2})|\;y_{2}=0\\}$. For $\bar{x}:=(0,0)\in{\rm
I\\!R}^{2}$ we have

$N_{\scriptsize\mbox{\rm dom}\,\vartheta}\big{(}f(\bar{x})\big{)}\cap\mbox{\rm
ker}\,\nabla f(\bar{x})^{*}=\big{\\{}(\lambda_{1},\lambda_{2})\in{\rm
I\\!R}^{2}\big{|}\;\lambda_{1}=0\big{\\}},$

which shows that the metric regularity qualification condition (3.2) fails at
$\bar{x}$. On the other hand, MSQC (3.5) holds at $\bar{x}$ since the mapping
$x\mapsto f(\bar{x})-\mbox{\rm dom}\,\vartheta$ is metrically subregular at
$(\bar{x},0)$. This follows from the aforementioned Hoffman lemma since $f$ is
an affine mapping and $\mbox{\rm dom}\,\vartheta$ is a polyhedral convex set.

(b) Consider the function $\vartheta$ from (3.7) with $m=3$, $Z:={\rm
I\\!R}_{+}^{3}$, and $B:=0\in{\rm I\\!R}^{3\times 3}$. Define the constraint
mapping $f:{\rm I\\!R}^{3}\to{\rm I\\!R}^{3}$ by $f=(f_{1},f_{2},f_{3})$ with
$x=(x_{1},x_{2},x_{3})\in{\rm I\\!R}^{3}$ and

$f_{1}(x):=x_{1}-\hbox{${1\over 2}$}x^{2}_{2},\quad
f_{2}(x):=x_{1}-\hbox{${1\over 2}$}x^{2}_{3},\quad
f_{3}(x):=-x_{1}-\hbox{${1\over 2}$}x^{2}_{1}-\hbox{${1\over
2}$}x^{2}_{2}-\hbox{${1\over 2}$}x^{2}_{3}.$

Letting $\bar{x}:=(0,0,0)\in{\rm I\\!R}^{3}$, deduce from $\mbox{\rm
dom}\,\vartheta={\rm I\\!R}_{-}^{3}$ that

$N_{\scriptsize\mbox{\rm dom}\,\vartheta}\big{(}f(\bar{x})\big{)}\cap\mbox{\rm
ker}\,\nabla
f(\bar{x})^{*}=\big{\\{}(\lambda_{1},\lambda_{2},\lambda_{3})\in{\rm
I\\!R}_{+}^{3}\big{|}\;\lambda_{1}+\lambda_{2}-\lambda_{3}=0\big{\\}},$ (3.8)

which implies that the metric regularity qualification condition (3.2) fails
at $\bar{x}$. For any $\lambda=(\lambda_{1},\lambda_{2},\lambda_{3})$ from
(3.8) and any $w=(w_{1},w_{2},w_{3})\in{\rm I\\!R}^{3}\setminus\\{0\\}$ with
$\nabla f(\bar{x})w\in T_{\scriptsize\mbox{\rm
dom}\,\vartheta}(f(\bar{x}))={\rm I\\!R}^{3}_{-}$ we conclude from the
conditions

$\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\rangle=-\lambda_{3}w_{1}^{2}-(\lambda_{1}+\lambda_{3})w_{2}^{2}-(\lambda_{2}+\lambda_{3})w_{3}^{2}\geq
0$

that $\lambda=0$, which confirms that (3.6) is satisfied. This tells us that
the constraint mapping $x\mapsto f(x)-\mbox{\rm dom}\,\vartheta$ is metrically
subregular at $(\bar{x},0)$.

We begin our first-order analysis with a new chain rule for the subderivative
of the composite function (1.1). The following theorem is significantly
different from the best results in this direction given in Theorem 10.6 of
Rockafellar and Wets [39]. The main improvement is the replacement of the
metric regularity qualification condition (3.2) therein with the much weaker
MSQC (3.5). Also, contrary to that book, we establish the subderivative chain
rule as equality without any subdifferential regularity. Finally, the
smoothness requirement on the inner mapping $f$ in (1.1) is weakened to its
merely (Fréchet) differentiability at the point in question. On the other
hand, we impose the local Lipschitz continuity of the outer function
$\vartheta$ relative to its domain, which is not assumed in Rockafellar and
Wets [39, Theorem 10.6].

######  Theorem 3.4 (subderivative chain rules as equalities under metric
subregularity).

Let $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ be differentiable at
$\bar{x}\in{\rm I\\!R}^{n}$, and let $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ be Lipschitz continuous around
$f(\bar{x})$ relative to its domain. If MSQC (3.5) is satisfied at $\bar{x}$
with some constant $\kappa\in{\rm I\\!R}_{+}$, then we have

${\rm d}(\vartheta\circ f)(\bar{x})(w)={\rm
d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla f(\bar{x})w\big{)},\quad
w\in{\rm I\\!R}^{m}.$ (3.9)

[Proof.] Pick any $\bar{w}\in{\rm I\\!R}^{n}$ and deduce from the
differentiability of $f$ at $\bar{x}$ that $\nabla
f(\bar{x})w+\frac{o(t\|w\|)}{t}\to\nabla f(\bar{x})\bar{w}$ as $t\downarrow 0$
and $w\to\bar{w}$. Based on this and (2.13), we get the relationships

$\displaystyle\displaystyle{\rm d}(\vartheta\circ f)(\bar{x})(\bar{w})$
$\displaystyle=$ $\displaystyle\liminf_{\begin{subarray}{c}t\downarrow 0\\\
w\to\bar{w}\end{subarray}}\frac{\vartheta\big{(}f(\bar{x}+tw)\big{)}-\vartheta\big{(}f(\bar{x})\big{)}}{t}$
$\displaystyle=$ $\displaystyle\liminf_{\begin{subarray}{c}t\downarrow 0\\\
w\to\bar{w}\end{subarray}}\frac{\vartheta\big{(}f(\bar{x})+t\nabla
f(\bar{x})w+o(t\|w\|)\big{)}-\vartheta\big{(}f(\bar{x})\big{)}}{t}$
$\displaystyle=$ $\displaystyle\liminf_{\begin{subarray}{c}t\downarrow 0\\\
w\to\bar{w}\end{subarray}}\frac{\vartheta\big{(}f(\bar{x})+t(\nabla
f(\bar{x})w+\frac{o(t\|w\|)}{t})\big{)}-\vartheta\big{(}f(\bar{x})\big{)}}{t}$
$\displaystyle\geq$ $\displaystyle{\rm
d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})\bar{w}\big{)}\;\mbox{ whenever }\;\bar{w}\in{\rm
I\\!R}^{n},\displaystyle$

which verify the inequality “$\geq$” in (3.9). Proceeding next with the proof
of the opposite inequality in (3.9), take any $w\in{\rm I\\!R}^{n}$ and
observe from the Lipschitz continuity of $\vartheta$ around $f(\bar{x})$
relative to its domain that ${\rm d}\vartheta(f(\bar{x}))(\nabla
f(\bar{x})w)>-\infty$. Since the latter inequality is obvious if ${\rm
d}\vartheta(f(\bar{x}))(\nabla f(\bar{x})w)=\infty$, we may assume that the
value ${\rm d}\vartheta(f(\bar{x}))(\nabla f(\bar{x})w)$ is finite. By
definition, there exist sequences $t_{k}\downarrow 0$ and $v_{k}\to\nabla
f(\bar{x})w$ such that

${\rm d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}=\lim_{\begin{subarray}{c}n\to\infty\end{subarray}}\frac{\vartheta\big{(}f(\bar{x})+t_{k}v_{k}\big{)}-\vartheta\big{(}f(\bar{x})\big{)}}{t_{k}}.$
(3.10)

Remembering that $\big{|}{\rm d}\vartheta(f(\bar{x}))(\nabla
f(\bar{x})w)\big{|}<\infty$, suppose without lost of generality that
$f(\bar{x})+t_{k}v_{k}\in\mbox{\rm dom}\,\vartheta$ for all $k\in{\rm I\\!N}$.
Then the imposed MSQC (3.5) at $\bar{x}$ yields

${\rm dist}(\bar{x}+t_{k}w;{\Omega})\leq\kappa\,{\rm
dist}\big{(}f(\bar{x}+t_{k}w);\mbox{\rm dom}\,\vartheta\big{)},\quad k\in{\rm
I\\!N},$

which in turn brings us to the relationships

$\displaystyle{\rm dist}\Big{(}w;\frac{{\Omega}-\bar{x}}{t_{k}}\Big{)}$
$\displaystyle\leq$ $\displaystyle\frac{\kappa}{t_{k}}\,{\rm
dist}\big{(}f(\bar{x})+t_{k}\nabla f(\bar{x})w+o(t_{k});\mbox{\rm
dom}\,\vartheta\big{)}$ $\displaystyle\leq$
$\displaystyle\frac{\kappa}{t_{k}}\,\big{\|}f(\bar{x})+t_{k}\nabla
f(\bar{x})w+o(t_{k})-f(\bar{x})-t_{k}v_{k}\big{\|}$ $\displaystyle=$
$\displaystyle\kappa\,\Big{\|}\nabla
f(\bar{x})w-v_{k}+\frac{o(t_{k})}{t_{k}}\Big{\|}\;\mbox{ for all }\;k\in{\rm
I\\!N}.\displaystyle$

This allows us to find vectors $w_{k}\in\frac{{\Omega}-\bar{x}}{t_{k}}$
satisfying

$\|w-w_{k}\|\leq\kappa\,\Big{\|}\nabla
f(\bar{x})w-v_{k}+\frac{o(t_{k})}{t_{k}}\Big{\|}+\frac{1}{k}.$

Thus we have $\bar{x}+t_{k}w_{k}\in{\Omega}$ for all $k$ and $w_{k}\to w$ as
$k\to\infty$. Combining these with (3.10), we arrive at

$\displaystyle{\rm d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}$ $\displaystyle=$
$\displaystyle\displaystyle\lim_{k\to\infty}\Big{[}\frac{\vartheta\big{(}f(\bar{x}+t_{k}w_{k})\big{)}-\vartheta\big{(}f(\bar{x})\big{)}}{t_{k}}+\frac{\vartheta\big{(}f(\bar{x})+t_{k}v_{k})\big{)}-\vartheta\big{(}f(\bar{x}+t_{k}w_{k})\big{)}}{t_{k}}\Big{]}$
$\displaystyle\geq$
$\displaystyle\displaystyle\liminf_{k\to\infty}\frac{\vartheta\big{(}f(\bar{x}+t_{k}w_{k})\big{)}-\vartheta\big{(}f(\bar{x})\big{)}}{t_{k}}-\ell\lim_{k\to\infty}\Big{\|}\frac{f(\bar{x}+t_{k}w_{k})-f(\bar{x})}{t_{k}}-v_{k}\Big{\|}$
$\displaystyle\geq$ $\displaystyle{\rm d}(\vartheta\circ
f)(\bar{x})(w)-\ell\lim_{k\to\infty}\Big{\|}\nabla
f(\bar{x})w_{k}+\frac{o(t_{k})}{t_{k}}-v_{k}\Big{\|}={\rm d}(\vartheta\circ
f)(\bar{x})(w),$

where $\ell\in{\rm I\\!R}_{+}$ is a Lipschitz constant of $\vartheta$ around
$f(\bar{x})$ relative to its domain. This verifies the inequality “$\geq$” in
(3.9) and completes the proof of the theorem.

Our next goal is to derive a subdifferential chain rule in the equality form
for the limiting subdifferential in (2.6) under the new metric subregularity
qualification condition (3.5). First we present the following lemma, which is
of its own interest.

######  Lemma 3.5 (extension of Lipschitz continuity).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a Lipschitz
continuous function around $\bar{x}$ relative to its domain with constant
$\ell\in{\rm I\\!R}_{+}$. Then there exist a number $\varepsilon>0$ and a
function $\psi\colon{\rm I\\!R}^{n}\to{\rm I\\!R}$, which agrees with
$\varphi$ on $\mathbb{B}_{\varepsilon}(\bar{x})\cap\mbox{\rm dom}\,\varphi$
and which is Lipschitz continuous on ${\rm I\\!R}^{n}$ with the same constant
$\ell$. If in addition $\varphi$ is convex, then the function $\psi$ can be
chosen to be convex as well.

[Proof.] The local Lipschitz continuity of $\varphi$ relative to $\mbox{\rm
dom}\,\varphi$ gives us $\varepsilon>0$ such that $\varphi$ is Lipschitz
continuous on the set
${\Omega}:=\mathbb{B}_{\varepsilon}(\bar{x})\cap\mbox{\rm dom}\,\varphi$ with
constant $\ell$. Considering the function

$\psi(x):=\inf_{u\in{\Omega}}\big{\\{}\varphi(u)+\ell\|x-u\|\big{\\}},\quad
x\in{\rm I\\!R}^{n},$

we can easily check (see, e.g., Rockafellar and Wets [39, Exercise 9.12]) that
$\psi$ agrees with $\varphi$ on ${\Omega}$ while being Lipschitz continuous on
${\rm I\\!R}^{n}$ with the same constant $\ell$. Furthermore, the convexity of
$\varphi$ clearly yields the convexity of the function

$\theta(x,u):=\varphi(u)+\delta_{{\Omega}}(u)+\ell\|x-u\|,\quad(x,u)\in{\rm
I\\!R}^{n}\times{\rm I\\!R}^{n},$

with respect to both variables. Having the representation
$\psi(x)=\inf_{u\in{\rm I\\!R}^{n}}\theta(x,u)$, we deduce directly from the
definition that $\psi$ is convex on ${\rm I\\!R}^{n}$.

Now we are ready to establish the main result of this section providing the
equality-type chain rule for limiting subgradients under the metric
subregularity qualification condition (3.5). Recall that a mapping
$f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ is strictly differentiable at
$\bar{x}$ with its strict derivative/Jacobian matrix $\nabla f(\bar{x})$ if we
have

$\displaystyle\lim_{x,u\to\bar{x}}\frac{f(x)-f(u)-\nabla
f(\bar{x})(x-u)}{\|x-u\|}=0.$

Observe that this differentiability notion lies between the usual Fréchet
differentiability of $f$ at $\bar{x}$ and its continuous differentiability
around this point. Note also that the replacement in the next theorem of the
conventional ${\cal C}^{1}$-smoothness of $f$ around $\bar{x}$ by its merely
strict differentiability at this point is necessary for applications to
second-order analysis conducted in this paper. Indeed, our second-order
analysis for (1.1) is achieved under the twice differentiability of $f$ at the
reference point. While implying the strict differentiability of $f$, this
condition does not necessarily yield the ${\cal C}^{1}$-smoothness of this
function.

######  Theorem 3.6 (equality chain rule for limiting subgradients under
metric subregularity).

Let $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ be strictly differentiable at
$\bar{x}\in{\rm I\\!R}^{n}$, and let $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ be convex, l.s.c. around $f(\bar{x})$,
and Lipschitz continuous around this point relative to its domain with
constant $\ell\in{\rm I\\!R}_{+}$. If MSQC (3.5) holds at $\bar{x}$ with some
constant $\kappa\in{\rm I\\!R}_{+}$, then the composition $\vartheta\circ f$
is lower regular at this point and we have the equality chain rule

$\partial(\vartheta\circ f)(\bar{x})=\widehat{\partial}(\vartheta\circ
f)(\bar{x})=\nabla f(\bar{x})^{*}\partial\vartheta\big{(}f(\bar{x})\big{)}.$
(3.11)

[Proof.] Since our analysis is local around the points in question, there is
no harm to suppose that $\vartheta$ is convex, l.s.c., and Lipschitz
continuous relative to its entire domain. Remember that the inclusions

$\partial(\vartheta\circ f)(\bar{x})\supset\widehat{\partial}(\vartheta\circ
f)(\bar{x})\supset\nabla
f(\bar{x})^{*}\partial\vartheta\big{(}f(\bar{x})\big{)}$

always hold, we proceed with verifying the inclusion
$\widehat{\partial}(\vartheta\circ f)(\bar{x})\subset\nabla
f(\bar{x})^{*}\partial\vartheta\big{(}f(\bar{x})\big{)}$, which justifies the
claimed lower regularity of $\vartheta\circ f$ at $\bar{x}$ together with the
chain rule (3.11). To this end, conclude from Lemma 3.5 that there exists a
Lipschitz continuous function $\psi\colon{\rm I\\!R}^{m}\to{\rm I\\!R}$ with
constant $\ell$ such that $\vartheta=\psi+\delta_{\scriptsize\mbox{\rm
dom}\,\vartheta}$. This allows us to observe that

$\vartheta\circ f=\psi\circ f+\delta_{\scriptsize\mbox{\rm
dom}\,\vartheta}\circ f.$

It follows from the above representation of $\vartheta$ and the lower
semicontinuity of $\vartheta$ that $\delta_{\scriptsize\mbox{\rm
dom}\,\vartheta}$ is l.s.c., and therefore $\mbox{\rm dom}\,\vartheta$ is
closed. Using Lemma 2.1 from Gfrerer and Mordukhovich [15] gives us

$\partial(\delta_{\scriptsize\mbox{\rm dom}\,\vartheta}\circ
f)(\bar{x})\subset\nabla f(\bar{x})^{*}N_{\scriptsize\mbox{\rm
dom}\,\vartheta}\big{(}f(\bar{x})\big{)},$

which in fact holds as equality since $\mbox{\rm dom}\,\vartheta$ is convex.
Employing the well-known chain and sum rules for Lipschitz continuous
functions, we get

$\displaystyle\partial(\vartheta\circ f)(\bar{x})$ $\displaystyle\subset$
$\displaystyle\partial(\psi\circ
f)(\bar{x})+\partial(\delta_{\scriptsize\mbox{\rm dom}\,\vartheta}\circ
f)(\bar{x})$ $\displaystyle\subset$ $\displaystyle\nabla
f(\bar{x})^{*}\partial\psi\big{(}f(\bar{x})\big{)}+\nabla
f(\bar{x})^{*}N_{\scriptsize\mbox{\rm
dom}\,\vartheta}\big{(}f(\bar{x})\big{)}$ $\displaystyle=$
$\displaystyle\nabla f(\bar{x})^{*}\partial\vartheta\big{(}f(\bar{x})\big{)},$

where the first inclusion follows from [30, Theorems 2.19] and the second one
comes from [39, Exercise 10.7]. This verifies the claimed inclusion and thus
completes the proof of the theorem.

All the assumptions on the outer function $\vartheta$ in Theorem 3.6 are
automatically satisfied for fairly broad classes of extended-real-valued
functions important in variational analysis and optimization; e.g., for the
convex piecewise linear-quadratic function $\vartheta$ defined in (3.7). It is
worth mentioning that both composite functions considered in Example 3.3 enjoy
MSQC (3.5), and hence the chain rule (3.11) holds for them. As shown therein,
the metric regularity qualification condition (3.2) fails for these composite
functions.

The next corollary plays a significant role in deriving subsequent second-
order results. It establishes the boundedness (with quantitative estimates) of
dual elements under MSQC (3.5). The latter is well known and rather easy to
check under metric regularity.

######  Corollary 3.7 (bounded multipliers).

Let $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ be strictly differentiable at
$\bar{x}\in{\rm I\\!R}^{n}$, and let $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ be convex, l.s.c. around $f(\bar{x})$,
and Lipschitz continuous around this point relative to its domain with
constant $\ell\in{\rm I\\!R}_{+}$. If MSQC (3.5) holds at $\bar{x}$ with some
constant $\kappa\in{\rm I\\!R}_{+}$, then for every vector
$v\in\partial(\vartheta\circ f)(\bar{x})$ there exists
$\lambda\in\partial\vartheta(f(\bar{x}))$ such that

$v=\nabla f(\bar{x})^{*}\lambda\;\mbox{ with
}\;\|\lambda\|\leq\ell+\kappa\|v\|+\kappa\ell\|\nabla f(\bar{x})\|.$ (3.13)

[Proof.] Assume without lost of generality that $\vartheta$ is Lipschitz
continuous relative to its entire domain. Applying Lemma 3.5 to the convex
outer function $\vartheta$ in composition (1.1), we find a convex Lipschitz
continuous function $\psi\colon{\rm I\\!R}^{m}\to{\rm I\\!R}$ such that
$\vartheta=\psi+\delta_{\scriptsize\mbox{\rm dom}\,\vartheta}$. Pick
$v\in\partial(\vartheta\circ f)(\bar{x})$. It follows from (3) that there
exist $\lambda_{1}\in\partial\psi(f(\bar{x}))$ and $\lambda_{2}\in
N_{\scriptsize\mbox{\rm dom}\,\vartheta}(f(\bar{x}))$ such that $v=\nabla
f(\bar{x})^{*}(\lambda_{1}+\lambda_{2})$. Since $\psi$ is Lipschitz continuous
with the same constant $\ell$ due to Lemma 3.5, we have
$\|\lambda_{1}\|\leq\ell$. On the other hand, we can deduce from Lemma 2.1 in
Gfrerer and Mordukhovich [15] that the following condition

$\|\lambda_{2}\|\leq\kappa\|\nabla
f(\bar{x})^{*}\lambda_{2}\|=\kappa\|v-\nabla f(\bar{x})^{*}\lambda_{1}\|.$

holds. Setting now $\lambda:=\lambda_{1}+\lambda_{2}$ leads us to

$\lambda\in\partial\psi\big{(}f(\bar{x})\big{)}+N_{\scriptsize\mbox{\rm
dom}\,\vartheta}\big{(}f(\bar{x})\big{)}=\partial\vartheta\big{(}f(\bar{x})\big{)}.$

Furthermore, it follows from the above discussion that

$\displaystyle\|\lambda\|=\|\lambda_{1}+\lambda_{2}\|\leq\|\lambda_{1}\|+\kappa\|v-\nabla
f(\bar{x})^{*}\lambda_{1}\|\leq\ell+\kappa\|v\|+\kappa\ell\,\|\nabla
f(\bar{x})\|,$

which readily verifies representation (3.13).

We conclude this section by a consequence of the obtained chain rules, where
the metric subregularity qualification condition (3.5) is automatically
satisfied. These results cannot be deduced from the known qualification
conditions formulated in Proposition 3.1(i,ii). While the chain rules below
were mentioned in Rockafellar and Wets [39, Exercise 10.22(b)], the provided
guide to the proof therein utilizes a number of rather involved results of
variational analysis that are significantly different from our device.

######  Corollary 3.8 (chain rules for piecewise linear-quadratic functions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be defined by
$\varphi(x):=\vartheta(Ax+a)$, where $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a convex piecewise linear-quadratic
function, $A$ is an $m\times n$ matrix, and $a\in{\rm I\\!R}^{n}$. Then for
any point $x\in\mbox{\rm dom}\,\varphi$ we have

${\rm d}\varphi(x)(w)={\rm
d}\vartheta(Ax+a)(Aw)\quad\mbox{and}\quad\partial\varphi(x)=A^{*}\partial\vartheta(Ax+a).$

[Proof.] Since $\vartheta$ is a convex piecewise linear-quadratic function,
its domain is a polyhedral convex set. Then the Hoffman lemma tells us that
MSQC (3.5) with $f(x):=Ax+a$ holds automatically at any point $x\in\mbox{\rm
dom}\,\varphi$. The claimed chain rules follow now from Theorems 3.4 and 3.6.

##  4 Fully Subamenable Functions

In this section we start the study and applications of major generalized
differential constructions of second-order variational analysis. Our main
attention is paid to the new class of fully subamenable functions. Prior to
this, we recall yet another first-order subgradient notion and employ it to
calculate the domain of second subderivatives (2.17) for a more general class
of extended-real-valued functions.

Given $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and
$\bar{x}\in\mbox{\rm dom}\,\varphi$, we say that $\bar{v}\in{\rm I\\!R}^{n}$
is a proximal subgradient of $\varphi$ at $\bar{x}$ if there are positive
numbers $\gamma$ and $r$ such that

$\varphi(x)\geq\varphi(\bar{x})+\langle\bar{v},x-\bar{x}\rangle-\hbox{${r\over
2}$}\|x-\bar{x}\|^{2}\quad\mbox{for all}\quad
x\in\mathbb{B}_{\gamma}(\bar{x}).$ (4.1)

The set of all such $\bar{v}$ is called the proximal subdifferential of
$\varphi$ at $\bar{x}$ and is denoted by $\partial_{p}\varphi(\bar{x})$.

The next theorem is important for its own sake and is also helpful for the
subsequent derivations of second-order calculus rules and their applications.

######  Theorem 4.1 (domain of second subderivatives).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$, and let
$\bar{v}\in\partial_{p}\varphi(\bar{x})$ with $\bar{x}\in\mbox{\rm
dom}\,\varphi$. The following assertions hold:

(i) The second subderivative ${\rm d}^{2}\varphi(\bar{x},\bar{v})$ is an
l.s.c. function such that ${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)>-r\|w\|^{2}$
for some $r>0$ and all $w\in{\rm I\\!R}^{n}$. In particular, the function
${\rm d}^{2}\varphi(\bar{x},\bar{v})$ is proper.

(ii) If $T^{2}_{\scriptsize{\mbox{\rm
epi}\,\varphi}}(\bar{z},q_{w})\neq\emptyset$ with
$\bar{z}:=(\bar{x},\varphi(\bar{x}))$ and $q_{w}:=(w,{\rm
d}\varphi(\bar{x})(w))$ for all $w\in{\rm I\\!R}^{n}$ satisfying ${\rm
d}\varphi(\bar{x})(w)=\langle\bar{v},w\rangle$, then we have

$\mbox{\rm dom}\,{\rm d}^{2}\varphi(\bar{x},\bar{v})=\big{\\{}w\in{\rm
I\\!R}^{n}\big{|}\;{\rm
d}\varphi(\bar{x})(w)=\langle\bar{v},w\rangle\big{\\}}.$ (4.2)

[Proof.] The l.s.c. property of ${\rm d}^{2}\varphi(\bar{x},\bar{v})$ was
proved in Rockafellar and Wets [39, Proposition 3.5]. To verify the lower
estimate in (i), we take the triple $(\bar{v},r,\gamma)$ from (4.1), fix
$w\in{\rm I\\!R}^{n}$, select $\varepsilon>0$ with
$\varepsilon^{2}+\varepsilon<\gamma$, and pick any
$u\in\mathbb{B}_{\varepsilon}(w)$ and $t\in(0,\varepsilon)$. If either $w=0$
or $\|w\|=1$, then $\bar{x}+tu\in\mathbb{B}_{\gamma}(\bar{x})$ and thus deduce
from (4.1) that

$\Delta_{t}^{2}\varphi(\bar{x},\bar{v})(u)=\frac{\varphi(\bar{x}+tu)-\varphi(\bar{x})-t\langle\bar{v},u\rangle}{\hbox{${1\over
2}$}t^{2}}\geq-r\|u\|^{2}.$

This readily implies that for such $w$ we have the estimates

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)\geq-r\|w\|^{2}>-\infty.$ (4.3)

Since $w\mapsto{\rm d}^{2}\varphi(\bar{x},\bar{v})(w)$ is positively
homogeneous of degree $2$, we get

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)=\|w\|^{2}{\rm
d}^{2}\varphi(\bar{x},\bar{v})\Big{(}\frac{w}{\|w\|}\Big{)}>-r\|w\|^{2}\Big{\|}\frac{w}{\|w\|}\Big{\|}^{2}=-r\|w\|^{2}>-\infty,$

whenever $w\neq 0$, which verifies the estimates in (4.3) for all $w\in{\rm
I\\!R}^{n}$. It is easy to observe that ${\rm
d}^{2}\varphi(\bar{x},\bar{v})(0)=0$, and thus ${\rm
d}^{2}\varphi(\bar{x},\bar{v})$ is a proper function.

To proceed next with the proof of (ii), note that the inclusion “$\subset$” in
(4.2) was already established in Rockafellar and Wets [39, Proposition 13.5].
Let us derive the opposite inclusion for any fixed $w\in{\rm I\\!R}^{n}$
satisfying ${\rm d}\varphi(\bar{x})(w)=\langle\bar{v},w\rangle$. By the
assumed nonemptiness of the second-order set therein, we get $(u,\alpha)\in
T^{2}_{\scriptsize{\mbox{\rm epi}\,\varphi}}(\bar{z},q_{w})$ for the pair
$(\bar{z},q_{w})$ in the statement of the theorem. Then (2.19) gives us
sequences $t_{k}\downarrow 0$ and $(u_{k},\alpha_{k})\to(u,\alpha)$ as
$k\to\infty$ such that

$\big{(}\bar{x},\varphi(\bar{x})\big{)}+t_{k}\big{(}w,{\rm
d}\varphi(\bar{x})(w)\big{)}+\hbox{${1\over
2}$}t^{2}_{k}(u_{k},\alpha_{k})\in\mbox{\rm epi}\,\varphi\;\mbox{ for all
}\;k\in{\rm I\\!N}.$

This tells us therefore that

$\frac{\varphi\big{(}\bar{x}+t_{k}w+\hbox{${1\over
2}$}t^{2}_{k}u_{k}\big{)}-\varphi(\bar{x})-t_{k}{\rm
d}\varphi(\bar{x})(w)}{\hbox{${1\over 2}$}t^{2}_{k}}\leq\alpha_{k}.$

Denote $w_{k}:=w+\hbox{${1\over 2}$}t_{k}u_{k}$ and deduce from ${\rm
d}\varphi(\bar{x})(w)=\langle\bar{v},w\rangle$ that

$\Delta_{t_{k}}^{2}\varphi(\bar{x},\bar{v})(w_{k})=\frac{\varphi(\bar{x}+t_{k}w_{k})-\varphi(\bar{x})-t_{k}\langle\bar{v},w_{k}\rangle}{\hbox{${1\over
2}$}t^{2}_{k}}\leq\alpha_{k}-\langle\bar{v},u_{k}\rangle.$

Since $w_{k}\to w$ as $k\to\infty$, we arrive at the inequalities

${\rm
d}^{2}\varphi(\bar{x},\bar{v})(w)\leq\alpha-\langle\bar{v},u\rangle<\infty,$

which show that $w\in\mbox{\rm dom}\,{\rm d}^{2}\varphi(\bar{x},\bar{v})$ and
hence complete the proof of the theorem.

Next we introduce a fairly broad class of composite functions playing a
crucial role in the rest of this paper. One of the nice properties of this
class is that the sufficient condition for the validity of the domain formula
(4.2) in Theorem 4.1 always holds for such functions, and thus we can use this
formula for deriving the main second-order results.

######  Definition 4.2 (fully subamenable functions).

We say that $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is fully
subamenable at $\bar{x}\in\mbox{\rm dom}\,\varphi$ if it there is a
neighborhood $U$ of $\bar{x}$ on which $\varphi$ is represented as
$\varphi=\vartheta\circ f$, where $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$
is twice differentiable at $\bar{x}$, and where $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is convex piecewise linear-quadratic
under the fulfillment of MSQC (3.5) at $\bar{x}$.

The composition format of Definition 4.2 goes back to Rockafellar [36] who
introduced the class of fully amenable functions, where MSQC (3.5) is replaced
by the metric regularity qualification condition from Proposition 3.1(i), and
where $f$ is assumed to be ${\cal C}^{2}$-smooth. Note that the latter metric
regularity condition in this framework can be equivalently written in the
Robinson constraint qualification form (3.4). We should point out here that
both composite functions in Example 3.3 are clearly fully subamenable at the
points in question. Moreover, the arguments in this example tell us that they
are not fully amenable since the metric regularity qualification condition
(3.2) fails for these composite functions.

Gfrerer and Mordukhovich [15] introduced the notions of (strongly, fully)
subamenable sets of the type $\\{x\in{\rm I\\!R}^{n}|\;f(x)\in\Theta\\}$ with
the replacement of the metric regularity condition in Rockafellar [36] by the
corresponding metric subregularity. This inspires the subamenability
terminology in Definition 4.2.

The result of Theorem 4.1(ii) motivates the following notion of the critical
cone for extended-real-value functions. Given $\psi\colon{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$, define the critical cone of $\psi$ at
$\bar{x}$ for $\bar{v}$ with $(\bar{x},\bar{v})\in\mbox{\rm
gph}\,\partial\psi$ by

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

When $\psi=\delta_{\Omega}$ with ${\Omega}\subset{\rm I\\!R}^{n}$, we get
${\rm d}\psi(\bar{x})(w)=\delta_{T_{\Omega}(\bar{x})}(w)$ whenever $w\in{\rm
I\\!R}^{n}$, which gives us the well-known critical cone construction for
sets:

$K_{\psi}(\bar{x},\bar{v})=T_{\Omega}(\bar{x})\cap\\{\bar{v}\\}^{\bot}.$

When $\vartheta\colon{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ a convex
piecewise linear-quadratic function, it follows from [39, Theorem 13.14] that
the critical cone (4.4) of $\vartheta$ at $(\bar{x},\bar{v})\in\mbox{\rm
gph}\,\partial\vartheta$ can be equivalently described by

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

Theorem 4.1(ii) provides a useful sufficient condition under which the domain
of the second subderivative and the critical cone agree. We show below that
this condition is satisfied for fully subamenable functions. To proceed, let
us first present the following chain rule for second-order tangent sets
(2.19). This result extends, with a different proof, the one in Rockafellar
and Wets [39, Proposition 13.13] from the fully amenable to fully subamenable
setting.

######  Proposition 4.3 (chain rule for second-order tangent sets).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a fully
subamenable composition at $\bar{x}$. The following assertions hold:

(i) The second-order tangent set $T^{2}_{\Omega}(\bar{x},w)$ is nonempty for
any tangent vector $w\in T_{\Omega}(\bar{x})$, where the set ${\Omega}$ is
defined in (3.5).

(ii) If $w\in T_{\Omega}(\bar{x})$ and the vector $z\in{\rm I\\!R}^{n}$
satisfy the inclusion

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

then $z\in T^{2}_{\Omega}(\bar{x},w)$. Furthermore, there exist a number
$\varepsilon>0$ and an arc $\xi\colon[0,\varepsilon]\to{\Omega}$ such that
$\xi(0)=\bar{x}$, $\xi_{+}^{\prime}(0)=w$, and $\xi_{+}^{\prime\prime}(0)=z$.

[Proof.] To verify (i), observe first that the inclusion $w\in
T_{\Omega}(\bar{x})$ implies by MSQC (3.5) that $\nabla f(\bar{x})w\in
T_{\scriptsize\mbox{\rm dom}\,\vartheta}(f(\bar{x}))$. Since $\mbox{\rm
dom}\,\vartheta$ is a polyhedral convex set, it follows that
$f(\bar{x})+t\nabla f(\bar{x})w\in\mbox{\rm dom}\,\vartheta$ for all small
$t>0$. Appealing now to (3.5), we get for such $t$ that

$\displaystyle{\rm dist}(\bar{x}+tw;{\Omega})$ $\displaystyle\leq$
$\displaystyle\kappa\,{\rm dist}\big{(}f(\bar{x}+tw);\mbox{\rm
dom}\,\vartheta\big{)}$ $\displaystyle\leq$
$\displaystyle\kappa\,\big{\|}f(\bar{x}+tw)-f(\bar{x})-t\nabla
f(\bar{x})w\big{\|}=\frac{\kappa
t^{2}}{2}\,\Big{\|}\nabla^{2}f(\bar{x})(w,w)+\frac{o(t^{2})}{2t^{2}}\Big{\|}.$

Thus there exists $u_{t}\in{\Omega}$ such that the parametric family of
$z_{t}:=[u_{t}-\bar{x}-tw]/\hbox{${1\over 2}$}t^{2}$ is bounded for all small
$t>0$. Consequently, we find a sequence $t_{k}\downarrow 0$ for which
$\bar{x}+t_{k}w+\hbox{${1\over 2}$}t_{k}^{2}z_{k}\in\mbox{\rm dom}\,\vartheta$
and $z_{k}\to z$ as $k\to\infty$ with some $z\in{\rm I\\!R}^{n}$. By (2.19),
this yields $z\in T^{2}_{\Omega}(\bar{x},w)$ and hence verifies assertion (i).

Turning now to the proof of (ii), take $w\in T_{\Omega}(\bar{x})$ satisfying
the relationships

$u:=\nabla f(\bar{x})z+\nabla^{2}f(\bar{x})(w,w)\in
T^{2}_{\scriptsize\mbox{\rm dom}\,\vartheta}\big{(}f(\bar{x}),\nabla
f(\bar{x})w\big{)}=T_{T_{\scriptsize\mbox{\rm
dom}\,\vartheta}(f(\bar{x}))}\big{(}\nabla f(\bar{x})w\big{)},$

where the equality is due to the polyhedrality of $\mbox{\rm dom}\,\vartheta$
and Proposition 13.12 in Rockafellar and Wets [39]. Hence we have
$f(\bar{x})+t\nabla f(\bar{x})w+\hbox{${1\over 2}$}t^{2}u\in\mbox{\rm
dom}\,\vartheta$ for all small $t>0$. Then it follows from (3.5) that

$\displaystyle{\rm dist}\big{(}\bar{x}+tw+\hbox{${1\over
2}$}t^{2}z;{\Omega}\big{)}$ $\displaystyle\leq$ $\displaystyle\kappa\,{\rm
dist}\big{(}f(\bar{x}+tw+\hbox{${1\over 2}$}t^{2}z);\mbox{\rm
dom}\,\vartheta\big{)}$ $\displaystyle\leq$
$\displaystyle\kappa\big{\|}f\big{(}\bar{x}+tw+\hbox{${1\over
2}$}t^{2}z\big{)}-\big{[}f(\bar{x})+t\nabla f(\bar{x})w+\hbox{${1\over
2}$}t^{2}u\big{]}\big{\|}=o(t^{2}).$

Thus we find $z_{t}\in{\Omega}$ such that $\bar{x}+tw+\hbox{${1\over
2}$}t^{2}z-z_{t}=o(t^{2})$ for all small $t>0$. Defining finally the arc
$\xi(t):=z_{t}=\bar{x}+tw+\hbox{${1\over 2}$}t^{2}z+o(t^{2})$ verifies (ii)
and completes the proof of the proposition.

Now we are ready to derive the aforementioned result, which ensures the
validity of the major assumption of Theorem 4.1 and of the critical cone
formula for fully subamenable functions.

######  Theorem 4.4 (critical cone for fully subamenable functions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a fully
subamenable function at $\bar{x}$ in the notation of Theorem 4.1. Then we have
$\partial\varphi(\bar{x})=\partial_{p}\varphi(\bar{x})$ and
$T^{2}_{\scriptsize{\mbox{\rm epi}\,\varphi}}(\bar{z},q_{w})\neq\emptyset$ for
any $w\in T_{\Omega}(\bar{x})$. Consequently

$K_{\varphi}(\bar{x},\bar{v})=\mbox{\rm dom}\,{\rm
d}^{2}\varphi(\bar{x},\bar{v})\;\mbox{ whenever
}\;\bar{v}\in\partial\varphi(\bar{x}).$ (4.5)

[Proof.] To verify the first statement, observe that we always have
$\partial_{p}\varphi(\bar{x})\subset\partial\varphi(\bar{x})$ and proceed with
the proof of the opposite inclusion. Pick $\bar{v}\in\partial\varphi(\bar{x})$
and find by (3.11) a vector $\bar{\lambda}\in\partial\vartheta(f(\bar{x}))$
with $\bar{v}=\nabla f(\bar{x})^{*}\bar{\lambda}$. It follows from the twice
differentiability of $f$ at $\bar{x}$ that

$f(x)-f(\bar{x})=\nabla
f(\bar{x})(x-\bar{x})+\nabla^{2}f(\bar{x})(x-\bar{x},x-\bar{x})+o(\|x-\bar{x}\|^{2}).$

Combining it with the convexity of $\vartheta$ gives us $\varepsilon>0$ such
that

$\displaystyle\vartheta\big{(}f(x)\big{)}-\vartheta\big{(}f(\bar{x})\big{)}\geq\langle\bar{\lambda},f(x)-f(\bar{x})\rangle$
$\displaystyle\geq$ $\displaystyle\langle\bar{\lambda},\nabla
f(\bar{x})(x-\bar{x})\rangle-\|\bar{\lambda}\|(1+\|\nabla^{2}f(\bar{x})\|)\|x-\bar{x}\|^{2}$
$\displaystyle=$
$\displaystyle\langle\bar{v},x-\bar{x}\rangle-\|\bar{\lambda}\|(1+\|\nabla^{2}f(\bar{x})\|)\|x-\bar{x}\|^{2}$

for all $x\in\mathbb{B}_{\varepsilon}(\bar{x})$. This shows that
$\bar{v}\in\partial_{p}\varphi(\bar{x})$ and thus justifies the claimed
inclusion.

To verify next that $T^{2}_{\scriptsize{\mbox{\rm
epi}\,\varphi}}(\bar{z},q_{w})\neq\emptyset$, fix $w\in T_{\Omega}(\bar{x})$
and get from Proposition 4.3(i) that $T^{2}_{\Omega}(\bar{x},w)\neq\emptyset$.
Picking $u\in T^{2}_{\Omega}(\bar{x},w)$, we find a sequence $t_{k}\downarrow
0$ such that

$\bar{x}+t_{k}w+\hbox{${1\over 2}$}t_{k}^{2}u+o(t_{k}^{2})\in{\Omega}\;\mbox{
for all }\;k\in{\rm I\\!N}.$

Denote $w_{k}:=w+\frac{1}{2}t_{k}u+\frac{o(t_{k}^{2})}{t_{k}}$ and deduce from
the definition of ${\Omega}$ in (3.5) that $f(\bar{x}+t_{k}w_{k})\in\mbox{\rm
dom}\,\vartheta$, which gives us the relationships

$f(\bar{x}+t_{k}w_{k})=f(\bar{x})+t_{k}\nabla f(\bar{x})w_{k}+\hbox{${1\over
2}$}t_{k}^{2}\nabla^{2}f(\bar{x})(w_{k},w_{k})+o(t_{k}^{2})\in\mbox{\rm
dom}\,\vartheta.$

Since $\vartheta$ is piecewise linear quadratic, we have $\mbox{\rm
dom}\,\vartheta=\cup_{j=1}^{s}{\Omega}_{j}$, where each ${\Omega}_{j}$ is a
polyhedral convex set. Passing to a subsequence if necessary, choose an index
$i\in\\{1,\ldots,s\\}$ for which

$y_{k}:=f(\bar{x}+t_{k}w_{k})=f(\bar{x})+t_{k}\nabla
f(\bar{x})w_{k}+\hbox{${1\over
2}$}t_{k}^{2}\nabla^{2}f(\bar{x})(w_{k},w_{k})+o(t_{k}^{2})\in{\Omega}_{i}$

whenever $k\in{\rm I\\!N}$. Remembering that $\vartheta(y)=\alpha_{i}+\langle
a_{i},y\rangle+\hbox{${1\over 2}$}\langle A_{i}y,y\rangle$ for all
$y\in{\Omega}_{i}$ yields

$\displaystyle\varphi(\bar{x}+t_{k}w_{k})$ $\displaystyle=$
$\displaystyle\vartheta\big{(}f(\bar{x}+t_{k}w_{k})\big{)}=\vartheta(y_{k})=\alpha_{i}+\langle
a_{i},y_{k}\rangle+\hbox{${1\over 2}$}\langle A_{i}y_{k},y_{k}\rangle$
$\displaystyle=$ $\displaystyle\alpha_{i}+\langle
a_{i},f(\bar{x})\rangle+\hbox{${1\over 2}$}\langle
A_{i}f(\bar{x}),f(\bar{x})\rangle+t_{k}\langle A_{i}f(\bar{x})+a_{i},\nabla
f(\bar{x})w_{k}\rangle$ $\displaystyle+\hbox{${1\over
2}$}t_{k}^{2}\big{[}\langle A_{i}\nabla f(\bar{x})w_{k},\nabla
f(\bar{x})w_{k}\rangle+\langle a_{i},\nabla^{2}f(\bar{x})(w_{k},w_{k})\rangle$
$\displaystyle+2\langle
A_{i}f(\bar{x}),\nabla^{2}f(\bar{x})(w_{k},w_{k})\rangle\big{]}+o(t_{k}^{2})$
$\displaystyle=$ $\displaystyle\varphi(\bar{x})+t_{k}\langle
A_{i}f(\bar{x})+a_{i},\nabla f(\bar{x})w\rangle+\hbox{${1\over 2}$}\langle
A_{i}f(\bar{x})+a_{i},\nabla f(\bar{x})u\rangle+o(t_{k}^{2})$
$\displaystyle+\hbox{${1\over 2}$}t_{k}^{2}\big{[}\langle A_{i}\nabla
f(\bar{x})w_{k},\nabla f(\bar{x})w_{k}\rangle+\langle
a_{i},\nabla^{2}f(\bar{x})(w_{k},w_{k})\rangle\big{]},$

where in the last equality we used that $w_{k}=w+\hbox{${1\over
2}$}t_{k}u+\frac{o(t_{k}^{2})}{t_{k}}$. This tells us that

$\displaystyle\big{(}\bar{x}+t_{k}w_{k},\varphi(\bar{x}+t_{k}w_{k})\big{)}$
$\displaystyle=$
$\displaystyle\big{(}\bar{x},f(\bar{x})\big{)}+t_{k}\Big{(}w,\big{\langle}A_{i}f(\bar{x})+a_{i},\nabla
f(\bar{x})w\big{\rangle}\Big{)}$ $\displaystyle+\hbox{${1\over
2}$}t_{k}^{2}\Big{(}u,\big{\langle}A_{i}\nabla f(\bar{x})w_{k},\nabla
f(\bar{x})w_{k}\big{\rangle}+\big{\langle}a_{i},\nabla^{2}f(\bar{x})(w_{k},w_{k})+\nabla
f(\bar{x})u\big{\rangle}$
$\displaystyle+2\big{\langle}A_{i}f(\bar{x}),\nabla^{2}f(\bar{x})(w_{k},w_{k})+\nabla
f(\bar{x})u\big{\rangle}\Big{)}+o(t_{k}^{2})\in\mbox{\rm
gph}\,\varphi\subset\mbox{\rm epi}\,\varphi.$

It follows from the chain rule for subderivatives in Theorem 3.4 and from the
subderivative representation for piecewise linear-quadratic functions in
(2.16) that

${\rm d}\varphi(\bar{x})(w)={\rm
d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}=\big{\langle}A_{i}f(\bar{x})+a_{i},\nabla
f(\bar{x})w\big{\rangle}.$

Combining these and letting $k\to\infty$, we arrive at $(u,p)\in
T^{2}_{\scriptsize{\mbox{\rm epi}\,\varphi}}(\bar{x},q_{w})$ with

$p:=\big{\langle}A_{i}\nabla f(\bar{x})w,\nabla
f(\bar{x})w\big{\rangle}+\big{\langle}a_{i},\nabla^{2}f(\bar{x})(w,w)+\nabla
f(\bar{x})u\big{\rangle}+2\langle
A_{i}f(\bar{x}),\nabla^{2}f(\bar{x})(w,w)+\nabla f(\bar{x})u\rangle,$

which justifies the claimed nonemptiness of the second-order tangent set.

It remains to verify the critical cone formula (4.5). Pick
$\bar{v}\in\partial\varphi(\bar{x})$ and fix a vector $w\in{\rm I\\!R}^{n}$
satisfying ${\rm d}\varphi(\bar{x})(w)=\langle\bar{v},w\rangle$. Furthermore,
it follows from the assumed MSQC (3.5) and from the given formula for the
domain of ${\rm d}\vartheta(f(\bar{x}))$ in (2.15) that

$T_{\Omega}(\bar{x})=\big{\\{}w\in{\rm I\\!R}^{n}\big{|}\;\nabla
f(\bar{x})w\in T_{\scriptsize\mbox{\rm
dom}\,\vartheta}\big{(}f(\bar{x})\big{)}\big{\\}}=\big{\\{}w\in{\rm
I\\!R}^{n}\big{|}\;\nabla f(\bar{x})w\in\mbox{\rm dom}\,{\rm
d}\vartheta\big{(}f(\bar{x})\big{)}\big{\\}},$

which yields $w\in T_{\Omega}(\bar{x})$, and hence
$T^{2}_{\scriptsize{\mbox{\rm epi}\,\varphi}}(\bar{z},q_{w})\neq\emptyset$ as
shown above. Appealing now to Theorem 4.1(ii) justifies (4.5) and thus
completes the proof.

Theorem 4.4 plays a key role in the variational approach to second-order
calculus and applications of fully subamenable compositions developed in the
subsequent sections. This is largely due to the next theorem that establishes
the existence of optimal solutions to a special class of constrained
optimization problems constructed via the second-order data of fully
subamenable functions. To define such a problem for a given fully subamenable
function $\varphi$ at $\bar{x}$, deduce first from the subdifferential chain
rule (3.11) and Proposition 2.1 that $\partial\varphi(\bar{x})\neq\emptyset$.
Pick $\bar{v}\in\partial\varphi(\bar{x})$ and define the multiplier set
associated with $(\bar{x},\bar{v})$ by

$\Lambda(\bar{x},\bar{v}):=\big{\\{}\lambda\in{\rm I\\!R}^{m}\big{|}\;\nabla
f(x)^{*}\lambda=\bar{v},\;\lambda\in\partial\vartheta\big{(}f(\bar{x})\big{)}\big{\\}}.$
(4.6)

The imposed MSQC (3.5) ensures that this set is nonempty. Moreover,
$\Lambda(\bar{x},\bar{v})$ is a polyhedral convex set since the function
$\vartheta$ is convex and piecewise linear-quadratic. Fix now a vector
$w\in{\rm I\\!R}^{n}$ and consider the constrained optimization problem:

$\max_{\lambda\in{\rm
I\\!R}^{m}}\;\;\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle+{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\lambda\big{)}\big{(}\nabla
f(\bar{x})w\big{)}\quad\mbox{subject
to}\quad\lambda\in\Lambda(\bar{x},\bar{v}).$ (4.7)

We need to use the following result on second subderivatives of convex
piecewise linear-quadratic functions that can be extracted from the proof of
Proposition 13.9 in Rockafellar and Wets [39]: Let $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ be given in form (2.11) with
$\bar{y}\in\mbox{\rm dom}\,\vartheta$. Then $\vartheta$ is properly twice epi-
differentiable at $\bar{y}$ for any $\bar{u}\in\partial\vartheta(\bar{y})$
with the representations

$\mbox{\rm dom}\,{\rm d}^{2}\vartheta(\bar{y},\bar{u})=\bigcup_{i\in
I(\bar{y})}T_{{\Omega}_{i}}(\bar{y})\cap\\{\bar{u}_{i}\\}^{\bot},\;{\rm
d}^{2}\vartheta(\bar{y},\bar{u})(w)=\begin{cases}\langle
A_{i}w,w\rangle&\mbox{if}\;\;w\in
T_{{\Omega}_{i}}(\bar{y})\cap\\{\bar{u}_{i}\\}^{\bot},\\\
\infty&\mbox{otherwise},\end{cases}$ (4.8)

where $\bar{u}_{i}:=\bar{u}-A_{i}\bar{y}-a_{i}$, and where the index set
$I(\bar{y})$ is taken from (2.15). Now we are ready to establish the
aforementioned existence result.

######  Theorem 4.5 (existence of optimal solutions along critical
directions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a fully
subamenable function at $\bar{x}$, and let
$\bar{v}\in\partial\varphi(\bar{x})$. Then for any critical direction $w\in
K_{\varphi}(\bar{x},\bar{v})$ we have:

(i) There exists an optimal solution to problem (4.7).

(ii) Denoting ${\cal
A}:=\big{\\{}\lambda\in\partial\vartheta(f(\bar{x}))\big{|}\;{\rm
d}\vartheta(f(\bar{x}))(\nabla f(\bar{x})w)=\langle\nabla
f(\bar{x})w,\lambda\rangle\big{\\}}$, there exists an optimal solution to the
modified problem

$\max_{\lambda\in{\rm
I\\!R}^{m}}\;\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle+{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\lambda\big{)}\big{(}\nabla
f(\bar{x})w\big{)}\;\mbox{ subject to }\;\nabla
f(x)^{*}\lambda=\bar{v},\;\lambda\in{\cal A}.$ (4.9)

Moreover, the sets of optimal solutions to problems (4.7) and (4.9) coincide.

[Proof.] Fix $w\in{\rm I\\!R}^{n}$ and pick any
$\lambda\in\Lambda(\bar{x},\bar{v})$. Arguing similarly to the beginning of
the proof of Theorem 13.14 in Rockafellar and Wets [39] (this part of the
proof can be carried out for fully subamenable functions, not just for fully
amenable ones as assumed therein), we get

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)\geq{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\lambda\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle.$
(4.10)

Take now $w\in K_{\varphi}(\bar{x},\bar{v})$, which is equivalent by MSQC
(3.5) to $\nabla f(\bar{x})w\in K_{\vartheta}(f(\bar{x}),\lambda)$. It follows
from (4.5) that both numbers ${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)$ and
${\rm d}^{2}\vartheta(f(\bar{x}),\lambda)(\nabla f(\bar{x})w)$ are finite, and
hence

$\sup_{\lambda\in\Lambda(\bar{x},\bar{v})}\big{\\{}\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle+{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\lambda\big{)}(\nabla
f(\bar{x})w)\big{\\}}\leq{\rm d}^{2}\varphi(\bar{x},\bar{v})(w)<\infty.$

This ensures that the optimal value of (4.7) is finite. Furthermore, we
observe from (4.8) that for any $w\in K_{\varphi}(\bar{x},\bar{v})$ the second
subderivative ${\rm d}^{2}\vartheta(f(\bar{x}),\lambda)(\nabla f(\bar{x})w)$
is actually independent of $\lambda$. This tells us that problem (4.7) is a
linear program, where the optimal value is finite. This yields the existence
of optimal solutions to (4.7), which verifies (i).

To check (ii), we deduce from $w\in K_{\varphi}(\bar{x},\bar{v})$ and formula
(4.5) in Theorem 4.4 that ${\rm
d}\varphi(\bar{x})(w)=\langle\bar{v},w\rangle$. Employing the chain rule for
subderivatives from (3.9) gives us

${\rm d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}=\langle\nabla f(\bar{x})w,\lambda\rangle\quad\mbox{for
all}\quad\lambda\in\Lambda(\bar{x},\bar{v}).$

This means that the constraint ${\rm d}\vartheta(f(\bar{x}))(\nabla
f(\bar{x})w)=\langle\nabla f(\bar{x})w,\lambda\rangle$ is an implicit
constraint for problem (4.7), and therefore the sets of feasible solutions to
problems (4.7) and (4.9) agree. This verifies by using (i) that for any $w\in
K_{\varphi}(\bar{x},\bar{v})$ the sets of optimal solutions to problems (4.9)
and (4.7) are the same.

Besides the optimization problem (4.7) and its equivalent subderivative form
(4.9), in the next section we deal with its dual problem constructed by using
parabolic subderivatives. Given $\psi\colon{\rm I\\!R}^{n}\to\overline{{\rm
I\\!R}}$ finite at $\bar{x}$ and given $w\in{\rm I\\!R}^{n}$ where ${\rm
d}\psi(\bar{x})(w)$ is finite, the parabolic subderivative of $\psi$ at
$\bar{x}$ for $w$ with respect to $z\in{\rm I\\!R}^{m}$ is defined by

${\rm d}^{2}\psi(\bar{x})(w;z):=\liminf_{\begin{subarray}{c}t\downarrow 0\\\
u\to z\end{subarray}}\dfrac{\psi(\bar{x}+tw+\hbox{${1\over
2}$}t^{2}u)-\psi(\bar{x})-t{\rm d}\psi(\bar{x})(w)}{\hbox{${1\over
2}$}t^{2}}.$ (4.11)

Let us first summarize some well-known properties of parabolic subderivatives
for the class of convex piecewise linear-quadratic functions.

######  Proposition 4.6 (properties of parabolic subderivatives and Fenchel
conjugates).

Let $\psi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be convex piecewise
linear-quadratic with $\bar{x}\in\mbox{\rm dom}\,\psi$, and let $w\in\mbox{\rm
dom}\,{\rm d}\psi(\bar{x})$. Then the function $z\mapsto{\rm
d}^{2}\psi(\bar{x})(w;z)$ is proper, l.s.c., and convex piecewise linear with
its Fenchel conjugate calculated by

$v\mapsto\begin{cases}-{\rm
d}^{2}\psi(\bar{x},v)(w)&\mbox{if}\;v\in\partial\psi(\bar{x})\;\mbox{ with
}\;{\rm d}\psi(\bar{x})(w)=\langle w,v\rangle,\\\
\infty&\mbox{otherwise}.\end{cases}$ (4.12)

Furthermore, we have the equivalence

${\rm d}^{2}\psi(\bar{x})(w;z)<\infty\iff z\in T_{T_{\scriptsize\mbox{\rm
dom}\,\psi}(\bar{y})}(w)=T^{2}_{\scriptsize\mbox{\rm dom}\,\psi}(\bar{x},w).$
(4.13)

[Proof.] It is easy to derive the listed general properties from the
definitions of parabolic subderivatives and piecewise linear-quadratic
functions. The Fenchel conjugate formula (4.12) is due to Rockafellar [36,
Proposition 3.5], while the equivalence (4.13) is discussed in Rockafellar and
Wets [39, Exercise 13.61].

Employing finally Theorem 4.5 together with Proposition 4.6 leads us to
duality relationships for piecewise linear-quadratic programs that extend the
classical ones in linear programming by taking into account specific
structures of problems (4.7) and (4.9).

######  Corollary 4.7 (duality relationships along critical directions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a fully
subamenable function at $\bar{x}$, and let
$\bar{v}\in\partial\varphi(\bar{x})$. Then for any $w\in
K_{\varphi}(\bar{x},\bar{v})$ we have:

(i) The dual problem of the piecewise linear-quadratic program (4.9) is given
by

$\min_{z\in{\rm I\\!R}^{n}}\;-\left\langle\bar{v},z\right\rangle+{\rm
d}^{2}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla f(\bar{x})w;\nabla
f(\bar{x})z+\nabla^{2}f(\bar{x})(w,w)\big{)},$ (4.14)

and it admits an optimal solution.

(ii) The optimal value of (4.9) coincides with the optimal value of (4.14).

[Proof.] The duality in (i) follows from Proposition 4.6, while the existence
of optimal solutions to (4.14) and the claim in (ii) are consequences of
Theorem 4.5.

##  5 Second Subderivatives of Fully Subamenable Functions

The main goal of this section is to establish twice epi-differentiability of
every fully subamenable function. For fully amenable functions it was done by
Rockafellar in [36] with the detailed proof given in Theorem 13.14 of his book
with Wets [39]. Our approach here is significantly different and in fact much
simpler even for fully amenable functions; see the comments after the proof.
One of the new ingredients is involving into the proof the parabolic
subderivatives (4.11). Furthermore, we obtain precise formulas for second
subderivatives of fully subamenable functions that are expressed entirely via
the given data.

The following lemma of its own interest is useful in the proof of the main
result of this section. It reveals an important second-order property of outer
functions that appear in fully subamenable compositions.

######  Lemma 5.1 (parabolic subderivatives of piecewise linear-quadratic
functions).

Let $\vartheta\colon{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ be a convex
piecewise linear-quadratic function with representation (2.11). Then for any
$\bar{y}\in\mbox{\rm dom}\,\vartheta$, $w\in\mbox{\rm dom}\,{\rm
d}\vartheta(\bar{y})$, and $z\in T^{2}_{\scriptsize\mbox{\rm
dom}\,\vartheta}(\bar{y},w)$ we have

${\rm d}^{2}\vartheta(\bar{y})(w,z)=\lim_{t\downarrow
0}\dfrac{\vartheta(\bar{y}+tw+\hbox{${1\over
2}$}t^{2}z)-\vartheta(\bar{y})-t{\rm d}\vartheta(\bar{y})(w)}{\hbox{${1\over
2}$}t^{2}}.$ (5.1)

[Proof.] To verify the claimed representation (5.1), remember that $z\in
T^{2}_{\scriptsize\mbox{\rm dom}\,\vartheta}(\bar{y},w)$, and thus it follows
from the equivalence in (4.13) that ${\rm d}^{2}\vartheta(\bar{y})(w,z)$ is
finite. Thus by the definition of the parabolic subderivative, we find
sequences $t_{k}\downarrow 0$ and $z_{k}\to z$ such that

$\lim_{k\to\infty}\dfrac{\vartheta\big{(}\bar{y}+t_{k}w+\hbox{${1\over
2}$}t_{k}^{2}z_{k}\big{)}-\vartheta(\bar{y})-t_{k}{\rm
d}\vartheta(\bar{y})(w)}{\hbox{${1\over 2}$}t_{k}^{2}}={\rm
d}^{2}\vartheta(\bar{y})(w,z).$

Since ${\rm d}^{2}\vartheta(\bar{y})(w,z)$ is finite, we have
$\bar{y}+t_{k}w+\hbox{${1\over 2}$}t_{k}^{2}z_{k}\in\mbox{\rm
dom}\,\vartheta=\cup_{i=1}^{s}{\Omega}_{i}$ for all $k$ sufficiently large.
Passing to a subsequence if necessary, find an index
$i_{0}\in\\{1,\ldots,s\\}$ with $\bar{y}+t_{k}w+\hbox{${1\over
2}$}t_{k}^{2}z_{k}\in{\Omega}_{i_{0}}$ for such large $k\in{\rm I\\!N}$. It
ensures therefore that $i_{0}\in J(\bar{y},w)$. Appealing now to (2.11) gives
us

$\displaystyle\vartheta\big{(}\bar{y}+t_{k}(w+\hbox{${1\over
2}$}t_{k}z_{k})\big{)}-\vartheta(\bar{y})$ $\displaystyle=$ $\displaystyle
t_{k}\big{\langle}A_{i}\bar{y}+a_{i},w+\hbox{${1\over
2}$}t_{k}z_{k}\big{\rangle}+\hbox{${1\over
2}$}t_{k}^{2}\big{\langle}A_{i}\big{(}w+\hbox{${1\over
2}$}t_{k}z_{k}\big{)},\big{(}w+\hbox{${1\over
2}$}t_{k}z_{k}\big{)}\big{\rangle}$ $\displaystyle=$ $\displaystyle t_{k}{\rm
d}\vartheta(\bar{y})(w)+\hbox{${1\over 2}$}t_{k}^{2}\langle
A_{i}\bar{y}+a_{i},z_{k}\rangle+\hbox{${1\over 2}$}t_{k}^{2}\langle
w,A_{i}w\rangle+o(t_{k}^{2}).$

It follows from $i_{0}\in J(\bar{y},w)$ that $i_{0}\in I(\bar{y})$ and thus
${\rm d}\vartheta(\bar{y})(w)=\langle A_{i_{0}}\bar{y}+a_{i_{0}},w\rangle$ by
(2.16). Combining these in turn brings us to the equality

$\lim_{k\to\infty}\dfrac{\vartheta\big{(}\bar{y}+t_{k}w+\hbox{${1\over
2}$}t_{k}^{2}z_{k}\big{)}-\vartheta(\bar{y})-t_{k}{\rm
d}\vartheta(\bar{y})(w)}{\hbox{${1\over 2}$}t_{k}^{2}}=\langle
A_{i_{0}}\bar{y}+a_{i_{0}},z\rangle+\langle w,A_{i_{0}}w\rangle.$ (5.2)

The above arguments verify that $z\in T^{2}_{{\Omega}_{i_{0}}}(\bar{y},w)$.
The polyhedrality of ${\Omega}_{i_{0}}$ ensures the existence of
$\varepsilon>0$ with $\bar{y}+tw+\hbox{${1\over 2}$}t^{2}z\in{\Omega}_{i_{0}}$
for all $t\in[0,\varepsilon]$. Arguing as in the proof of (5.2) yields

$\lim_{t\downarrow 0}\dfrac{\vartheta\big{(}\bar{y}+tw+\hbox{${1\over
2}$}t^{2}z\big{)}-\vartheta(\bar{y})-t{\rm
d}\vartheta(\bar{y})(w)}{\hbox{${1\over 2}$}t^{2}}=\langle
A_{i_{0}}\bar{y}+a_{i_{0}},z\rangle+\langle w,A_{i_{0}}w\rangle.$

This along with (5.2) confirms that both sides of the equality in (5.1) agree
with each other for any second-order tangent vector $z\in
T^{2}_{\scriptsize\mbox{\rm dom}\,\vartheta}(\bar{y},w)$.

Now we are ready to prove the twice epi-differentiability of fully subamenable
functions and derive an explicit formula for their second subderivatives.

######  Theorem 5.2 (twice epi-differentiability of fully subamenable
functions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a fully
subamenable function at $\bar{x}\in\mbox{\rm dom}\,\varphi$. Then $\varphi$ is
properly twice epi-differentiable at $\bar{x}$ for every
$\bar{v}\in\partial\varphi(\bar{x})$, and its second subderivative (2.17) is
calculated by

${\rm
d}^{2}\varphi(\bar{x},\bar{v})(w)=\max_{\lambda\in\Lambda(\bar{x},\bar{v})}\big{\\{}{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\lambda\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle\\}$
(5.3)

for all $w\in{\rm I\\!R}^{n}$, where the set of multiplies
$\Lambda(\bar{x},\bar{v})$ is taken from (4.6).

[Proof.] The inequality “$\geq$” in (5.3) is given in (4.10). Now we proceed
with the simultaneous verification of the opposite inequality in (5.3) and the
twice epi-differentiability of $f$ in (2.18). It only suffices to prove these
relationships for critical directions $w\in K_{\varphi}(\bar{x},\bar{v})$.
Indeed, for $w\notin K_{\varphi}(\bar{x},\bar{v})$, which is equivalent to
$\nabla f(\bar{x})w\notin K_{\vartheta}(f(\bar{x}),\lambda)$ whenever
$\lambda\in\Lambda(\bar{x},\bar{v})$, both sides of (5.3) become $\infty$. To
obtain (2.18) for this case, pick a sequence $t_{k}\downarrow 0$ and then let
the sequence $w_{k}:=w$ for any $k$. It is easy to observe that (2.18) holds
for the aforementioned sequence. Fix further $w\in
K_{\varphi}(\bar{x},\bar{v})$ and pick any
$\bar{v}\in\partial\varphi(\bar{x})$. This together with the chain rule for
subderivatives (3.9) ensures the equalities

${\rm d}\varphi(\bar{x})(w)={\rm
d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}=\langle\bar{v},w\rangle.$ (5.4)

Corollary 4.7(i) tells us that the piecewise linear-quadratic program (4.14)
admits an optimal solution denoted by $\bar{z}$, and its optimal value is
finite. Hence the parabolic subderivative ${\rm
d}^{2}\vartheta(f(\bar{x}))\big{(}\nabla f(\bar{x})w;\nabla
f(\bar{x})\bar{z}+\nabla^{2}f(\bar{x})(w,w)\big{)}$ is also finite. This
together with (4.13) implies that

$\bar{u}:=\nabla^{2}f(\bar{x})(w,w)+\nabla f(\bar{x})\bar{z}\in
T_{\scriptsize\mbox{\rm dom}\,\vartheta}^{2}\big{(}f(\bar{x}),\nabla
f(\bar{x})w\big{)}.$ (5.5)

Since $\mbox{\rm dom}\,\vartheta$ is a polyhedral convex set, we find a number
$\delta>0$ such that

$f(\bar{x})+t\nabla f(\bar{x})w+\hbox{${1\over 2}$}t^{2}\bar{u}\in\mbox{\rm
dom}\,\vartheta\quad\mbox{for all}\quad t\in[0,\delta].$ (5.6)

Moreover, we conclude from (5.5) and Proposition 4.3(ii) that $\bar{z}\in
T_{\Omega}^{2}(\bar{x},w)$. The latter proposition also ensures the existence
of a number $\varepsilon\in(0,\delta)$ and an arc
$\xi\colon[0,\varepsilon]\to{\Omega}$ for which we have

$\xi(0)=\bar{x},\;\xi^{\prime}_{+}(0)=w,\;\mbox{ and
}\;\xi^{\prime\prime}_{+}(0)=z.$ (5.7)

Define now $w_{t}:=\displaystyle\frac{\xi(t)-\xi(0)}{t}$ for all
$t\in[0,\varepsilon]$ and observe that $\bar{x}+tw_{t}=\xi(t)\in{\Omega}$ for
such $t$. It follows from the second equality in (5.7) that $w_{t}\to w$ as
$t\downarrow 0$. Thus for all $t\in[0,\varepsilon]$ we deduce from the
relationships in (5.4)–(5.7) that

$\displaystyle\begin{array}[]{ll}&\Delta_{t}^{2}\varphi(\bar{x},\bar{v})(w_{t})=\dfrac{\varphi(\bar{x}+tw_{t})-\varphi(\bar{x})-t\langle\bar{v},w_{t}\rangle}{\hbox{${1\over
2}$}t^{2}}=\dfrac{\vartheta\big{(}f(\bar{x}+tw_{t})\big{)}-\vartheta\big{(}f(\bar{x})\big{)}-t\langle\bar{v},w_{t}\rangle}{\hbox{${1\over
2}$}t^{2}}\\\
&=\dfrac{\vartheta\big{(}f(\xi(t))\big{)}-\vartheta\big{(}f(\bar{x})\big{)}-t\,{\rm
d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}}{\hbox{${1\over
2}$}t^{2}}-\Big{\langle}\bar{v},\dfrac{\xi(t)-\xi(0)-tw}{\hbox{${1\over
2}$}t^{2}}\Big{\rangle}\\\ &=\dfrac{\vartheta\big{(}f(\bar{x})+t\nabla
f(\bar{x})w+\hbox{${1\over
2}$}t^{2}\bar{u}\big{)}-\vartheta\big{(}f(\bar{x})\big{)}-t\,{\rm
d}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}}{\hbox{${1\over 2}$}t^{2}}\\\
&+\dfrac{\vartheta\big{(}f(\xi(t))\big{)}-\vartheta\big{(}f(\bar{x})+t\nabla
f(\bar{x})w+\hbox{${1\over 2}$}t^{2}\bar{u}\big{)}}{\hbox{${1\over
2}$}t^{2}}-\Big{\langle}\bar{v},\dfrac{\xi(t)-\xi(0)-t\xi^{\prime}_{+}(0)}{\hbox{${1\over
2}$}t^{2}}\Big{\rangle}.\end{array}$ (5.12)

Looking at the last equality in (5.12), we see that the first term therein
converges to ${\rm d}^{2}\vartheta(f(\bar{x}))(\nabla f(\bar{x})w;\bar{u})$ as
$t\downarrow 0$ due to Lemma 5.1. The third term clearly converges to
$-\langle\bar{v},\bar{z}\rangle$. Turing to the second term in this equality,
remember that $\vartheta$ is Lipschitz continuous relative to its domain,
which implies by (5.6) and $f(\xi(t))\in\mbox{\rm dom}\,\vartheta$ that the
second term converges to zero since

$\frac{f\big{(}\xi(t)\big{)}-f(\bar{x})-t\nabla f(\bar{x})w}{\hbox{${1\over
2}$}t^{2}}\to\bar{u}\quad\mbox{as}\quad t\downarrow 0.$

Getting all the above together, we arrive at the equalities

$\displaystyle\lim_{t\downarrow
0}\Delta_{t}^{2}\varphi(\bar{x},\bar{v})(w_{t})$ $\displaystyle=$
$\displaystyle{\rm d}^{2}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w;\bar{u}\big{)}-\langle\bar{v},\bar{z}\rangle$ $\displaystyle=$
$\displaystyle{\rm d}^{2}\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w;\nabla
f(\bar{x})\bar{z}+\nabla^{2}f(\bar{x})(w,w)\big{)}-\langle\bar{v},\bar{z}\rangle$
$\displaystyle=$
$\displaystyle\max_{\lambda\in\Lambda(\bar{x},\bar{v})}\big{\\{}{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\lambda\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle\big{\\}},$

where the last one comes from Proposition 4.7(ii). This verifies the
inequality “$\leq$” in (5.3) as well as the convergence in (2.18), and thus
completes the proof of the theorem.

As mentioned above, the results of Theorem 5.2 extend those in Rockafellar and
Wets [39, Theorem 13.14] obtained under the metric regularity qualification
condition in form (3.4). Our proof, based on metric subregularity in (3.5), is
largely different and essentially simpler than the one from [39, Theorem
13.14]. The major difference is that we use in the proof another pair of
primal-dual problems and involve parabolic subderivatives. Our approach allows
us to deal with more general frameworks and applications, which is the main
subject of our subsequent research [26].

Remember that the equivalent optimization problems (4.7) and (4.9) are in fact
problems of linear programming due to the second subderivative calculation
(4.8). Next we derive equivalent representations for the second subderivative
of $\varphi$ in (5.3), which are useful for proto-derivative calculations in
Section 7.

######  Corollary 5.3 (chain rules for second subderivatives of fully
subamenable compositions).

In the framework and under the assumptions of Theorem 5.2, take any
$\bar{\lambda}\in\Lambda(\bar{x},\bar{v})$. Then we have the second-order
chain rules:

(i) The second subderivative of $\varphi$ at $\bar{x}$ for $\bar{v}$ is
represented by

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)={\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\bar{\lambda}\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\max_{\lambda\in\Lambda(\bar{x},\bar{v})}\big{\langle}\lambda,\nabla^{2}f(\bar{x})(w,w)\big{\rangle}.$
(5.13)

(ii) There exits $\bar{r}>0$ such that for any $r>\bar{r}$ and any $w\in{\rm
I\\!R}^{n}$ we have

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)={\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\bar{\lambda}\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\max_{\lambda\in[\Lambda(\bar{x},\bar{v})\,\cap\,r\mathbb{B}]}\big{\langle}\lambda,\nabla^{2}f(\bar{x})(w,w)\big{\rangle}.$
(5.14)

[Proof.] We get from the critical cone definition and the subderivative chain
rule under MSQC (3.5) that

$w\in K_{\varphi}(\bar{x},\bar{v})\iff\nabla f(\bar{x})w\in
K_{\vartheta}\big{(}f(\bar{x}),\lambda\big{)}\;\mbox{ for all
}\;\lambda\in\Lambda(\bar{x},\bar{v}).$ (5.15)

If $w\notin K_{\varphi}(\bar{x},\bar{v})$, then both sides in (5.13) become
$\infty$, and so the equality holds therein. Similarly we get (5.14) for any
$r>0$ in this case.

Consider now the case where $w\in K_{\varphi}(\bar{x},\bar{v})$. To verify
(i), deduce from (4.8) that the second subderivative ${\rm
d}^{2}\vartheta(f(\bar{x}),\bar{\lambda})(\nabla f(\bar{x})w)$ is actually
independent of $\bar{\lambda}$ for such critical directions $w$, and so the
sets on the right-hand sides in (5.13) and (5.3) are the same, which justifies
(i).

To verify assertion (ii), note that for all $w\in
K_{\varphi}(\bar{x},\bar{v})$ the optimal value of the linear program

$\max_{\lambda\in\Lambda(\bar{x},\bar{v})}\big{\langle}\lambda,\nabla^{2}f(\bar{x})(w,w)\big{\rangle}$
(5.16)

is finite, and thus this problem admits an optimal solution. We know from
standard theory of linear programming that the set of optimal solutions to a
linear program is a face of its feasible solution set. Denote by
$G_{1},\ldots,G_{l}$ all the finitely many faces of the polyhedral convex set
$\Lambda(\bar{x},\bar{v})$. Select $\lambda_{i}\in G_{i}$ for each
$i=1,\ldots,l$ and define $E:=\\{\lambda_{i}|\;i=1,\ldots,l\\}$. Choose
further a positive number $r$ such that
$E\subset\Lambda(\bar{x},\bar{v})\,\cap\,r\mathbb{B}$ and observe the
equalities

$\max_{\lambda\in\Lambda(\bar{x},\bar{v})}\\{\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle\\}=\max_{\lambda\in
E}\\{\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle\\}=\max_{\lambda\in[\Lambda(\bar{x},\bar{v})\,\cap\,r\mathbb{B}]}\\{\left\langle\lambda,\nabla^{2}f(\bar{x})(w,w)\right\rangle\\},$
(5.17)

which readily justify the second subderivative chain rule in (ii).

We finish this section by showing that the full subamenability of functions is
preserved under various operations including the summation of functions and
taking the second subderivative.

######  Theorem 5.4 (preservation of full subamenability under summation).

Let $\varphi:=\sum_{i=1}^{s}\varphi_{i}$ on ${\rm I\\!R}^{n}$, where each
$\varphi_{i}\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is fully
subamenable at $\bar{x}\in\cap_{i=1}^{s}\mbox{\rm dom}\,\varphi_{i}$, and let
$\bar{v}\in\varphi(\bar{x})$. Impose the following subregularity qualification
condition: there exist numbers $\kappa\in{\rm I\\!R}_{+}$ and $\varepsilon>0$
such that

${\rm dist}\Big{(}x;\bigcap_{i=1}^{s}\mbox{\rm
dom}\,\varphi_{i}\Big{)}\leq\kappa\,\sum_{i=1}^{s}{\rm dist}(x;\mbox{\rm
dom}\,\varphi_{i})\quad\mbox{for all}\quad
x\in\mathbb{B}_{\varepsilon}(\bar{x}).$ (5.18)

Then $\varphi$ is fully subamenable at $\bar{x}$ and its second subderivative
is represented by

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)=\max\Big{\\{}\sum_{i=1}^{s}{\rm
d}^{2}\varphi_{i}(\bar{x},v_{i})(w)\Big{|}\;v_{i}\in\partial\varphi_{i}(\bar{x}),\;\sum_{i=1}^{s}v_{i}=\bar{v}\Big{\\}},\quad
w\in{\rm I\\!R}^{n}.$ (5.19)

[Proof.] Since the functions $\varphi_{i}$ are fully subamenable at $\bar{x}$,
for each $i\in\\{1,\ldots,s\\}$ there is a neighborhood $U_{i}$ of $\bar{x}$
on which $\varphi_{i}$ admits the representation
$\varphi_{i}=\vartheta_{i}\circ f_{i}$, where $\vartheta_{i}\colon{\rm
I\\!R}^{p_{i}}\to\overline{{\rm I\\!R}}$ is convex piecewise linear-quadratic,
where $f_{i}\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{p_{i}}$ is twice
differentiable at $\bar{x}$, and where the mapping $x\mapsto
f_{i}(x)-\mbox{\rm dom}\,\vartheta_{i}$ is metrically subregular at
$(\bar{x},0)$ with constant $\kappa_{i}\in{\rm I\\!R}_{+}$. Denote
$p:=\sum_{i=1}^{s}p_{i}$ and define $\vartheta\colon{\rm
I\\!R}^{p}\to\overline{{\rm I\\!R}}$ and $f\colon{\rm I\\!R}^{n}\to{\rm
I\\!R}^{p}$ by, respectively,

$\vartheta(y_{p_{1}},\ldots,y_{p_{s}}):=\vartheta_{1}(y_{p_{1}})+\ldots+\vartheta_{s}(y_{p_{s}})\;\mbox{
as }\;y_{p_{i}}\in{\rm I\\!R}^{p_{i}}\;\mbox{ and
}\;f(x):=\big{(}f_{1}(x),\ldots,f_{s}(x)\big{)}.$

It is easy to check that the function $\vartheta$ is convex piecewise linear-
quadratic and also that the mapping $x\mapsto f(x)-\mbox{\rm dom}\,\vartheta$
is metrically subregular at $(\bar{x},0)$ with constant
$\bar{\kappa}:=\max\\{\kappa\kappa_{i}|\;i=1,\ldots,s\\}$ under the imposed
subregularity qualification condition (5.18). This shows that
$\varphi=\vartheta\circ f$ on $U=\cap_{1=1}^{s}U_{i}$, and so $\varphi$ is
fully subamenable at $\bar{x}$. The first-order chain rules from (3.9) and
(3.11) applied to the composition $\varphi=\vartheta\circ f$ allow us to
arrive at the corresponding sum rules

$\partial\varphi(\bar{x})=\partial\varphi_{1}(\bar{x})+\ldots+\partial\varphi_{s}(\bar{x})\quad\mbox{and}\quad{\rm
d}\varphi(\bar{x})(w)=\sum_{i=1}^{s}{\rm d}\varphi_{i}(\bar{x})(w)\;\mbox{ for
all }\;w\in{\rm I\\!R}^{n}.$ (5.20)

Next we verify representation (5.19). Pick
$\bar{v}\in\partial\varphi(\bar{x})$ and choose subgradients
$v_{i}\in\partial\varphi_{i}(\bar{x})$ such that
$\sum_{i=1}^{s}v_{i}=\bar{v}$. It comes directly from the definition of the
second subderivative that

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)\geq\sum_{i=1}^{s}{\rm
d}^{2}\varphi_{i}(\bar{x},v_{i})(w)\;\mbox{ for all }\;w\in{\rm I\\!R}^{n},$

which gives us the inequality “$\geq$” in (5.19). To prove the opposite
inequality, consider first the case where $w\notin
K_{\varphi}(\bar{x},\bar{v})$. It follows from definition (4.4) and the
subderivative sum rule in (5.20) that

$\sum_{i=1}^{s}\langle v_{i},w\rangle=\langle\bar{v},w\rangle<{\rm
d}\varphi(\bar{x})(w)=\sum_{i=1}^{s}{\rm d}\varphi_{i}(\bar{x})(w),$

which implies that there exists an index $i\in\\{1,\ldots,s\\}$ with $\langle
v_{i},w\rangle<{\rm d}\varphi_{i}(\bar{x})(w)$. This ensures by the critical
cone representation (4.5) that ${\rm
d}^{2}\varphi_{i}(\bar{x},v_{i})(w)=\infty$. Since all $\varphi_{i}$ are fully
amenable at $\bar{x}$, the second subderivatives ${\rm
d}^{2}\varphi_{i}(\bar{x},v_{i})$ are proper and thus both sides in (5.19)
become $\infty$, which proves (5.19) for all the noncritical vectors $w\notin
K_{\varphi}(\bar{x},\bar{v})$.

Consider now the remaining case where $w\in K_{\varphi}(\bar{x},\bar{v})$. Let
$\bar{\lambda}\in\Lambda(\bar{x},\bar{v})$ be a vector realizing the maximum
in the second subderivative representation (5.3). Take
$\bar{\lambda}_{i}\in\partial\vartheta_{i}(f_{i}(\bar{x}))$ such that

$\bar{\lambda}=(\bar{\lambda}_{1},\ldots,\bar{\lambda}_{s})\;\mbox{ and
}\;\bar{v}=\sum_{i=1}^{s}\bar{v}_{i}\;\mbox{ with }\;\bar{v}_{i}=\nabla
f_{i}(\bar{x})^{*}\bar{\lambda}_{i}.$

This implies by using (5.3) the relationships

$\displaystyle{\rm d}^{2}\varphi(\bar{x},\bar{v})(w)$ $\displaystyle=$
$\displaystyle{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\bar{\lambda}\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\left\langle\bar{\lambda},\nabla^{2}f(\bar{x})(w,w)\right\rangle$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{s}{\rm
d}^{2}\vartheta_{i}\big{(}f_{i}(\bar{x}),\bar{\lambda}_{i}\big{)}\big{(}\nabla
f_{i}(\bar{x})w\big{)}+\left\langle\bar{\lambda}_{i},\nabla^{2}f_{i}(\bar{x})(w,w)\right\rangle$
$\displaystyle\leq$ $\displaystyle\sum_{i=1}^{s}{\rm
d}^{2}\varphi_{i}(\bar{x},\bar{v}_{i})(w),$

which yield the inequality “$\leq$” in (5.19) and thus complete the proof.

The subregularity condition (5.18) has been used in first-order theory of
variational analysis under the name of “metric qualification condition as,
e.g., in [21]. When in addition the sets in (5.18) are convex and $x$ is taken
from the entire space under consideration, (5.18) reduces to “linear
regularity” that has been broadly studied in convex analysis and optimization.
We refer the reader to [2, 5] for more details on the linear regularity in the
convex framework.

The final result of this section shows that the second subderivative of a
fully subamenable function is fully subamenable itself on the whole space.

######  Corollary 5.5 (full subamenability of second subderivatives).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a fully
subamenable function at $\bar{x}$, and let
$\bar{v}\in\partial\varphi(\bar{x})$. Then the second subderivative
$w\mapsto{\rm d}^{2}\varphi(\bar{x},\bar{v})(w)$ is a fully subamenable
function at every $w\in{\rm I\\!R}^{n}$.

[Proof.] It follows from the proof of Corollary 5.3(ii) that whenever
$\bar{\lambda}\in\Lambda(\bar{x},\bar{v})$ we have

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)={\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\bar{\lambda})\big{(}\nabla
f(\bar{x})w\big{)}+\max_{\lambda\in
E}\big{\langle}\lambda,\nabla^{2}f(\bar{x})(w,w)\big{\rangle},$ (5.21)

where $E:=\\{\lambda_{i}|\>i=1,\ldots,p\\}$ for some
$\lambda_{i}\in\Lambda(\bar{x},\bar{v})$ and $p\in{\rm I\\!N}$. Define the
function $\psi\colon{\rm I\\!R}^{p}\to{\rm I\\!R}$ by
$\psi(y_{1},\ldots,y_{p}):=\max\\{y_{1},\ldots,y_{p}\\}$ and the mapping
$g\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{p}$ by

$g(w):=\big{(}\big{\langle}\lambda_{1},\nabla^{2}f(\bar{x})(w,w)\big{\rangle},\ldots,\big{\langle}\lambda_{p},\nabla^{2}f(\bar{x})(w,w)\big{\rangle}\big{)}.$

It is obvious that $\psi$ is convex piecewise linear-quadratic with $\mbox{\rm
dom}\,\psi={\rm I\\!R}^{p}$, that $g$ is a ${\cal C}^{2}$-smooth, and that
MSQC (3.5) is satisfied at any point $w\in{\rm I\\!R}^{n}$ for the composition
$\psi\circ g$. Thus the latter is fully subamenable at $w$. The second-order
chain rule (5.21) can be rewritten as

${\rm d}^{2}\varphi(\bar{x},\bar{v})(w)=\theta(w)+(\psi\circ g)(w)\;\mbox{
with }\;\theta(w):={\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\bar{\lambda}\big{)}\big{(}\nabla
f(\bar{x})w\big{)}\;\mbox{ for all }\;w\in{\rm I\\!R}^{n}.$

Remember that both $\theta$ and $\psi\circ g$ are subamenable at any point
$w\in{\rm I\\!R}^{n}$. To conclude that ${\rm d}^{2}\varphi(\bar{x},\bar{v})$
is fully subamenable at $w$ by using Theorem 5.4, it remains to check that the
subregularity qualification condition (5.18) holds in our setting. This
follows directly from the Hoffman lemma since the domains of $\theta$ and
$\psi\circ g$ are polyhedral.

##  6 Second-Order Optimality Conditions for Composite Problems

Having in hand the developed calculus rules for second subderivatives, we are
now in a position to derive no-gap second-order optimality conditions (i.e.,
such conditions where the difference between necessary and sufficient ones is
in the replacement of the nonstrict inequality for its strict counterpart) for
composite optimization problems written in the unconstrained format

$\mbox{minimize }\;\varphi_{0}(x)+(\vartheta\circ f)(x)\;\mbox{ over
}\;x\in{\rm I\\!R}^{n}.$ (6.1)

Our assumptions here require that the mappings $\varphi_{0}\colon{\rm
I\\!R}^{n}\to{\rm I\\!R}$ and $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ are
twice differentiable at $\bar{x}$, and that $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a convex piecewise linear-quadratic
function. As already mentioned in Section 1, the possibility of taking the
value $\vartheta(y)=\infty$ for the outer function in the composition from
(6.1) allows us to convert constrained problems into unconstrained problems.
However, the realization of this approach to constrained optimization requires
adequate generalized differential calculus to deal with extended-real-valued
functions.

As discussed in Section 1, the composite format (6.1) clearly covers classical
problems of nonlinear programming, which correspond to the case where
$\vartheta$ is the indicator function of a polyhedral convex set. Another
particular setting of (6.1) is when $\vartheta\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is defined by (3.7). As mentioned in
Example 3.3, this allows us to address ENLPs the importance of which has been
highly recognized in theoretical developments, computational methods, and
applications dealing with broad areas of optimization including stochastic
programming, robust optimization; see, e.g., Rockafellar and Wets [39] for
further information. We also refer the reader to the more recent papers by
Mordukhovich et al. [27] and Do et al. [9], devoted to the study of various
stability issues, criticality of multipliers, and other aspects of ENLP
important for numerical methods and applications.

Now we derive no-gap second-order necessary and sufficient conditions for
local optimality in composite problems described by fully subamenable
functions. They are surely applied to ENLPs.

######  Theorem 6.1 (no-gap second-order optimality conditions for fully
subamenable composite problems).

Consider the composite optimization problem (6.1), where
$\varphi_{0}\colon{\rm I\\!R}^{n}\to{\rm I\\!R}$ and $f\colon{\rm
I\\!R}^{n}\to{\rm I\\!R}^{m}$ are twice differentiable at $\bar{x}$, and where
$\vartheta\colon{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is a convex
piecewise linear-quadratic function with $f(\bar{x})\in\mbox{\rm
dom}\,\vartheta$. Let $\varphi:=\vartheta\circ f$, and let MSQC (3.5) hold at
$\bar{x}$ satisfying the stationary condition
$0\in\nabla\varphi_{0}(\bar{x})+\partial\varphi(\bar{x})$. Take further
$K_{\varphi}(\bar{x},\bar{v})$ from (4.4) with
$\bar{v}:=-\nabla\varphi_{0}(\bar{x})$. The following hold:

(i) If $\bar{x}$ is a local minimizer of (6.1), then the second-order
necessary condition

${\rm d}^{2}\vartheta\big{(}f(\bar{x}),\bar{\lambda}\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\max_{\lambda\in\Lambda(\bar{x},\bar{v})}\big{\langle}\nabla^{2}_{xx}L(\bar{x},\lambda)w,w\big{\rangle}\geq
0\;\mbox{ whenever }\;w\in K_{\varphi}(\bar{x},\bar{v})$ (6.2)

is satisfied for any $\bar{\lambda}\in\Lambda(\bar{x},\bar{v})$, where $L$ is
the Lagrangian associated with (6.1) and defined by
$L(x,\lambda):=\varphi_{0}(x)+\langle\lambda,f(x)\rangle-\vartheta^{*}(\lambda)$
as $x\in{\rm I\\!R}^{n}$ and $\lambda\in{\rm I\\!R}^{m}$.

(ii) The validity of the second-order condition

${\rm d}^{2}\vartheta\big{(}f(\bar{x}),\bar{\lambda}\big{)}\big{(}\nabla
f(\bar{x})w\big{)}+\max_{\lambda\in\Lambda(\bar{x},\bar{v})}\big{\langle}\nabla^{2}_{xx}L(\bar{x},\lambda)w,w\big{\rangle}>0\mbox{
whenever }w\in K_{\varphi}(\bar{x},\bar{v})\setminus\\{0\\}$ (6.3)

for any $\bar{\lambda}\in\Lambda(\bar{x},\bar{v})$ amounts to the existence of
numbers $\ell\geq 0$ and $\varepsilon>0$ such that

$\psi(x)\geq\psi(\bar{x})+\ell\|x-\bar{x}\|^{2}\;\mbox{ if
}\;x\in\mathbb{B}_{\varepsilon}(\bar{x})$ (6.4)

with $\psi:=\varphi_{0}+\vartheta\circ f$. In particular, condition (6.3) is
sufficient for local optimality of $\bar{x}$ in (6.1).

[Proof.] Since $\varphi_{0}$ is twice differentiable at $\bar{x}$, it is easy
to deduce from the definitions that

${\rm
d}^{2}(\varphi_{0}+\varphi)(\bar{x},0)(w)=\langle\nabla^{2}\varphi_{0}(\bar{x})w,w\rangle+{\rm
d}^{2}\varphi(\bar{x},\bar{v})(w)\;\mbox{ for any }\;w\in{\rm I\\!R}^{n}.$
(6.5)

To verify (i), let $\bar{x}$ be a local minimizer of (6.1), i.e., it provides
a local minimum for $\psi=\varphi_{0}+\varphi$. It is an immediate consequence
of definition (2.17) that ${\rm d}^{2}\psi(\bar{x},0)(w)\geq 0$ for all
$w\in{\rm I\\!R}^{n}$. Applying the second-order sum rule (6.5) to $\psi$ and
then the second-order chain rule (5.13) to $\varphi=\vartheta\circ f$, we
arrive at the second-order necessary condition (6.2) whenever $w\in
K_{\varphi}(\bar{x},\bar{v})$, which justifies (i).

To proceed with (ii), we first use Theorem 13.24(c) from Rockafellar and Wets
[39] telling us that for any proper function $\psi\colon{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ the simultaneous fulfillment of the
conditions $0\in\partial\psi(\bar{x})$ and ${\rm d}^{2}\psi(\bar{x},0)(w)>0$
when $w\neq 0$ amounts to the second-order growth condition (6.4). Since
$\psi=\varphi_{0}+\vartheta\circ f$, we see from the elementary first-order
subdifferential sum rule that the stationary point $\bar{x}$ with
$0\in\nabla\varphi_{0}(\bar{x})+\partial(\vartheta\circ f)(\bar{x})$ satisfies
$0\in\partial\psi(\bar{x})$. Furthermore, by Theorem 4.4 and the
aforementioned sum rule for second subderivatives we get $\mbox{\rm dom}\,{\rm
d}^{2}\psi(\bar{x},0)=K_{\varphi}(\bar{x},\bar{v})$. Applying as above the
equality-type sum and chain rules for the second subderivative of $\psi$ shows
that the condition ${\rm d}^{2}\psi(\bar{x},0)(w)>0$ amounts to (6.3). This
completes the proof of the theorem.

The no-gap second-order optimality conditions of Theorem 6.1 are new while
they can be derived in the same way by using the results in Rockafellar and
Wets [39] (mainly the second-order chain rule in Theorem 13.14 therein) under
the metric regularity qualification condition (3.2) as well as the ${\cal
C}^{2}$-smoothness of $\varphi_{0}$ and $f$ in (6.1). We also refer the reader
to the concurrent preprint by Chieu et al. [7], where the second-order
optimality conditions are obtained under a certain metric subregularity by a
different approach for problems with the so-called ${\cal C}^{2}$-cone
reducible constraints (in the sense of Bonnans and Shapiro [3]), which do not
generally cover the case of subamenable compositions in (6.1). Note finally
that the possibility of replacing ${\cal C}^{2}$-smoothness assumptions in
conventional second-order optimality conditions for problems of nonlinear
programming by merely twice differentiability of their data has been already
observed before; see [22, Theorems 1.19, 1.20].

The following example demonstrates two simple composite problems for which the
second-order optimality conditions from Theorem 6.1 can be applied while those
in [39, Theorem 13.14], obtained under the metric regularity qualification
condition (3.2), cannot be used.

######  Example 6.2 (second-order optimality conditions in the absence of
metric regularity).

Consider the composite optimization problem (6.1) with the following initial
data:

(a) Take $f$ and $\vartheta$ from Example 3.3(a) and choose
$\varphi_{0}(x)\equiv 0$ for $x\in{\rm I\\!R}^{2}$. It is easy to see that

$\vartheta(f(x))=\hbox{${1\over 2}$}(x_{1}-x_{2})^{2}\quad\mbox{for
all}\;\;x=(x_{1},x_{2})\in{\rm I\\!R}^{2}.$

This clearly indicates that $\bar{x}=(0,0)$ is an optimal solution to (6.1).
Remember that Example 3.3(a) tells us that MSQC (3.5) is satisfied for the
composite function $\varphi=\vartheta\circ f$ at $\bar{x}$, and thus this
function is fully subamenable at $\bar{x}$. Appealing to Theorem 6.1(i) tells
us that the second-order necessary optimality condition (6.2) holds for this
problem. In fact, simple calculations show that

$K_{\varphi}(\bar{x},\bar{v})=\big{\\{}(w_{1},w_{2})\in{\rm
I\\!R}^{2}\big{|}\;w_{2}=0\big{\\}},\;\;\Lambda(\bar{x},\bar{v})=\big{\\{}(\lambda_{1},\lambda_{2})\in{\rm
I\\!R}^{2}\big{|}\;\lambda_{1}=0\big{\\}}\;\;\mbox{with}\;\;\bar{v}=(0,0).$

Moreover, for any
$\lambda=(\lambda_{1},\lambda_{2})\in\Lambda(\bar{x},\bar{v})$ and any
$w=(w_{1},w_{2})\in{\rm I\\!R}^{2}$ we conclude that

$\big{\langle}\nabla^{2}_{xx}L(\bar{x},\lambda)w,w\big{\rangle}=0\quad\mbox{and}\quad{\rm
d}^{2}\vartheta\big{(}f(\bar{x}),\lambda\big{)}(w)=w_{1}^{2}+\delta_{K_{\varphi}(\bar{x},\bar{v})}(w),$

which readily confirms the fulfillment of (6.2) for this composite problem. It
is worth mentioning that any point $x=(x_{1},x_{2})\in{\rm I\\!R}^{2}$ with
$x_{1}=x_{2}$ is also an optimal solution to (6.1) at which the composite
function $\varphi$ is fully subamenable. Hence Theorem 6.1(i) can be utilized
to achieve the necessary optimality condition for all such points while [39,
Theorem 13.14] cannot be used since the metric regularity qualification
condition (3.2) fails at these points.

(b) Take $f$ and $\vartheta$ from Example 3.3(b) and define the function
$\varphi_{0}\colon{\rm I\\!R}^{3}\to{\rm I\\!R}$ by
$\varphi_{0}(x):=-x_{1}+x^{2}_{2}+x^{2}_{3}$ with
$x=(x_{1},x_{2},x_{3})\in{\rm I\\!R}^{3}$. According to Example 3.3(b), MSCQ
(3.5) holds at $\bar{x}=(0,0,0)$ while the metric regularity qualification
condition (3.2) fails at this point. Thus the function $\varphi=\vartheta\circ
f$ is fully subamenable (but not fully amenable) at $\bar{x}$. It is easy to
see that $\vartheta=\delta_{{\rm I\\!R}_{-}^{3}}$. Simple calculations show
that $\bar{v}=-\nabla\varphi_{0}(\bar{x})=(1,0,0)$, that

$\displaystyle K_{\varphi}(\bar{x},\bar{v})$ $\displaystyle=$
$\displaystyle\big{\\{}w=(w_{1},w_{2},w_{3})\in{\rm
I\\!R}^{3}\big{|}\;d\varphi(\bar{x})(w)=w_{1}\big{\\}}$ $\displaystyle=$
$\displaystyle\big{\\{}w=(w_{1},w_{2},w_{3})\in{\rm
I\\!R}^{3}\big{|}\;d\vartheta\big{(}f(\bar{x})\big{)}\big{(}\nabla
f(\bar{x})w\big{)}=w_{1}\big{\\}}$ $\displaystyle=$
$\displaystyle\big{\\{}w=(w_{1},w_{2},w_{3})\in{\rm
I\\!R}^{3}\big{|}\;\delta_{{\rm
I\\!R}_{-}^{3}}(w_{1},w_{2},-w_{3})=w_{1}\big{\\}}=\\{0\\}\times{\rm
I\\!R}_{-}\times{\rm I\\!R}_{+},$

and that the Lagrange multiplier set is calculated by

$\Lambda(\bar{x},\bar{v})=\big{\\{}(\lambda_{1},\lambda_{2},\lambda_{3})\in{\rm
I\\!R}_{+}^{3}\big{|}\;\lambda_{1}+\lambda_{2}-\lambda_{3}=1\big{\\}}.$

Since the latter set has the two extreme points $(1,0,0)$ and $(0,1,0)$, we
get

$\displaystyle\max\big{\\{}\big{\langle}\nabla^{2}_{xx}L(\bar{x},\lambda)w,w\big{\rangle}\big{|}\;\lambda\in\Lambda(\bar{x},\bar{v})\big{\\}}$
$\displaystyle=$
$\displaystyle\max\Big{\\{}-\lambda_{3}w_{1}^{2}+(2-\lambda_{1}-\lambda_{3})w_{2}^{2}+(2-\lambda_{2}-\lambda_{3})w_{3}^{2}\Big{|}\;\lambda=(\lambda_{1},\lambda_{2},\lambda_{3})\in\Lambda(\bar{x},\bar{v})\Big{\\}}$
$\displaystyle=$
$\displaystyle\max\big{\\{}w^{2}_{2}+2w^{2}_{3},2w^{2}_{2}+w^{2}_{3}\big{\\}}.$

Furthermore, it follows that
$d^{2}\vartheta(f(\bar{x}),\lambda)=\delta_{\scriptsize
K_{\vartheta}(f(\bar{x}),\lambda)}$ for any
$\lambda\in\Lambda(\bar{x},\bar{v})$. Thus the second-order sufficient
condition (6.3) holds at $\bar{x}$, which ensures that the second-order growth
condition (6.4) is also satisfied at this point. It allows us to conclude that
$\bar{x}$ is a strict local minimizer of (6.1) for this choice of the
functions $\varphi_{0}$, $\vartheta$, and $f$.

##  7 Calculating Proto-Derivatives of Subdifferentiable Mappings

This section is devoted to deriving a precise calculus formula for the proto-
derivative of the subdifferential mapping associated with fully subamenable
compositions. Recall that a set-valued mapping $S:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ is proto-differentiable at
$\bar{x}$ for $\bar{y}\in S(\bar{x})$ if $\mbox{\rm gph}\,S$ is geometrically
derivable at $(\bar{x},\bar{y})$. When this condition holds for $S$, we refer
to $DS(\bar{x},\bar{y})$ as the proto-derivative of $S$ at $\bar{x}$ for
$\bar{y}$.

To achieve our goals, we implement a brilliant result first discovered by
Rockafellar [37] for convex functions and then extended by Poliquin and
Rockafellar [34] to a significantly larger class of prox-regular and
subdifferentially continuous functions. This result establishes a precise
relationship between graphical derivatives of subdifferential mapping of a
function and its second subderivative, which also leads us to new applications
to parametric optimization developed in the next section.

To formulate this result, recall that a function $\psi\colon{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is prox-regular at $\bar{x}\in\mbox{\rm
dom}\,\psi$ for $\bar{v}\in\partial\psi(\bar{x})$ if it is l.s.c. around
$\bar{x}$ and there exist constants $\varepsilon>0$ and $r>0$ such that for
all $x\in\mathbb{B}_{\varepsilon}(\bar{x})$ with
$\psi(x)\leq\psi(\bar{x})+\varepsilon$ we have the condition

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

It is said that $\psi$ is subdifferentially continuous at $\bar{x}$ for
$\bar{v}$ if the convergence $(x_{k},v_{k})\to(\bar{x},\bar{v})$ with
$v_{k}\in\partial\psi(x_{k})$ yields $\psi(x_{k})\to\varphi(\bar{x})$ as
$k\to\infty$.

The aforementioned result by Poliquin and Rockafellar [34, Theorem 6.1] tells
us that if $\psi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is prox-
regular and subdifferentially continuous at $\bar{x}$ for
$\bar{v}\in\partial\psi(\bar{x})$, then $\psi$ is twice epi-differentiable at
$\bar{x}$ for $\bar{v}$ if and only if $\partial\psi$ is proto-differentiable
at $\bar{x}$ for $\bar{v}$ and its proto-derivative can be calculated by

$\big{(}D\partial\psi\big{)}(\bar{x},\bar{v})(w)=\hbox{${1\over
2}$}\partial\big{(}{\rm d}^{2}\psi(\bar{x},\bar{v})\big{)}(w)\;\mbox{ whenever
}\;w\in{\rm I\\!R}^{n}.$ (7.1)

The fundamental relationship (7.1) would allow us to employ the results
obtained above for second subderivatives of fully subamenable functions if we
show that such functions are prox-regular and subdifferentially continuous.
This requires to assume in addition that the mapping $f$ in Definition 4.2 is
${\cal C}^{2}$-smooth around the reference point.

######  Proposition 7.1 (prox-regularity and subdifferential continuity of
fully subamenable functions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ admit the
representation $\varphi=\vartheta\circ f$ locally around $\bar{x}$, where
$\vartheta\colon{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is convex piecewise
linear-quadratic, and where $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ is a
${\cal C}^{2}$-smooth mapping around $\bar{x}$ with $f(\bar{x})\in\mbox{\rm
dom}\,\vartheta$ under the fulfillment of MSQC (3.5) at $\bar{x}$. Then
$\varphi$ is prox-regular and subdifferentially continuous at $\bar{x}$ for
any subgradient vector $\bar{v}\in\partial\varphi(\bar{x})$.

[Proof.] Since $f$ is ${\cal C}^{2}$-smooth around $\bar{x}$, the
subdifferential chain rule (3.11) from Theorem 3.6 ensures the existence of
$\varepsilon>0$ such that

$\partial\varphi(u)=\nabla f(u)^{*}\partial\vartheta\big{(}f(u)\big{)}\;\mbox{
whenever }\;u\in\mathbb{B}_{\varepsilon}(\bar{x}).$

Furthermore, the ${\cal C}^{2}$-smoothness of $f$ yields the boundedness
property (3.13) for all $u\in\mathbb{B}_{\varepsilon}(\bar{x})$ with the same
constants on the right-hand side of the inequality in (3.13). Picking now any
$(u,v)\in(\mbox{\rm
gph}\,\partial\varphi)\cap\mathbb{B}_{\varepsilon}(\bar{x},\bar{v})$ and
appealing again to Corollary 3.7, we find $\gamma>0$ and
$\lambda\in\partial\varphi(f(u))$ for which

$v=\nabla f(u)^{*}\lambda\quad\mbox{and}\quad\|\lambda\|\leq\gamma.$

Combining the latter with the convexity of $\vartheta$ and the ${\cal
C}^{2}$-smoothness of $f$ ensures the existence of $r>0$ such that for any
$(u,v)\in(\mbox{\rm
gph}\,\partial\varphi)\cap\mathbb{B}_{\varepsilon}(\bar{x},\bar{v})$ and any
$x\in\mathbb{B}_{\varepsilon}(\bar{x})$ the relationships

$\displaystyle\vartheta\big{(}f(x)\big{)}-\vartheta\big{(}f(u)\big{)}\geq\langle\lambda,f(x)-f(u)\rangle\geq\langle\nabla
f(u)^{*}\lambda,x-u\rangle-\frac{r}{2}\|x-u\|^{2}=\langle
v,x-u\rangle-\frac{r}{2}\|x-u\|^{2}$

are satisfied. This verifies the prox-regularity of $\varphi$ at $\bar{x}$ for
$\bar{v}$. The subdifferential continuity of $\varphi$ clearly follows from
the fact that $\vartheta$ is continuous relative to its domain.

Now we are ready to derive the following second-order chain rule for proto-
derivatives of fully subamenable compositions.

######  Theorem 7.2 (calculating proto-derivatives of fully subamenable
functions).

In the framework of Proposition 7.1, assume that
$(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial\varphi$. Then the subgradient
mapping $\partial\varphi$ is proto-differentiable at $\bar{x}$ for $\bar{v}$
and whenever $w\in K_{\varphi}(\bar{x},\bar{v})$ the proto-derivative of
$\partial\varphi$ is calculated by