Variational Convexity of Functions and
Variational Sufficiency in Optimization
PHAM DUY KHANH***Department of Mathematics, HCMC University of Education, Ho
Chi Minh City, Vietnam. E-mail<EMAIL_ADDRESS>BORIS S.
MORDUKHOVICH†††Department of Mathematics, Wayne State University, Detroit,
Michigan, USA. E-mail: aa1086wayne.edu. Research of this author was partly
supported by the US National Science Foundation under grants DMS-1808978 and
DMS-2204519, by the Australian Research Council under Discovery Project
DP-190100555, and by Project 111 of China under grant D21024. and VO THANH
PHAT ‡‡‡Department of Mathematics, HCMC University of Education, Ho Chi Minh
City, Vietnam and Department of Mathematics, Wayne State University, Detroit,
Michigan, USA. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>The research of
this author was partly supported by the US National Science Foundation under
grants DMS-1808978 and DMS-2204519.

Abstract. The paper is devoted to the study, characterizations, and
applications of variational convexity of functions, the property that has been
recently introduced by Rockafellar together with its strong counterpart. First
we show that these variational properties of an extended-real-valued function
are equivalent to, respectively, the conventional (local) convexity and strong
convexity of its Moreau envelope. Then we derive new characterizations of both
variational convexity and variational strong convexity of general functions
via their second-order subdifferentials (generalized Hessians), which are
coderivatives of subgradient mappings. We also study relationships of these
notions with local minimizers and tilt-stable local minimizers. The obtained
results are used for characterizing related notions of variational and strong
variational sufficiency in composite optimization with applications to
nonlinear programming.
Key words. variational convexity, variational strong convexity, Moreau
envelopes, second-order subdifferentials, composite optimization, variational
and strong variational sufficiency, tilt-stable local minimizers
AMS subject classification. 49J53, 49J52, 90C31

##  1 Introduction

The properties of variational convexity and variational strong convexity of
extended-real-valued lower semicontinuous (l.s.c.) functions
$\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}:=(-\infty,\infty]$ have
been recently introduced by Rockafellar [49]. It has been well recognized and
utilized in convex and variational analysis that the subgradient mapping
$\partial\varphi$ associated with an l.s.c. function $\varphi$ is maximal
monotone if and only if the function is convex on the entire space. This
result is fundamental in convex analysis and its numerous applications,
particularly those to optimization-related problems; see, e.g., the books [1,
30, 32, 48, 52] for more details and references therein. Loosely speaking,
variational convexity corresponds to the graphical localization of the maximal
monotonicity property in terms of the limiting subdifferential around the
point in question. Variational strong convexity can be defined in this scheme
with replacing monotonicity of the subgradient mapping by strong monotonicity
(with some modulus). The latter property is closely related to the notion of
tilt stability of local minimizers introduced earlier in Poliquin and
Rockafellar [46].

Both variational convexity and variational strong convexity properties of a
function are more subtle than the conventional notions of local convexity and
strong local convexity of the function relative to some neighborhood of the
reference point. It is easy to illustrate by simple one-dimensional examples
that the corresponding variational properties are satisfied without any local
convexity. The importance of variational convexity and its strong counterpart
for the study of nonconvex optimization problems has been demonstrated in the
recent papers by Rockafellar [49, 50, 51], where the reader can find, in
particular, applications to the proximal point and augmented Lagrangian
methods in rather general frameworks.

Our first principal result in this paper reveals that the variational
convexity of an l.s.c. prox-bounded function is equivalent to the usual local
convexity of the Moreau envelope together with the prox-regularity of the
function in question. We prove in this way that minimizing a nonsmooth
variationally convex function can be reduced to the minimization of its smooth
and convex Moreau envelope. A parallel characterization is established for
variational strong convexity of extended-real-valued functions.

Since both Moreau envelope and prox-regularity notions are well understood and
employed in variational analysis and optimization, the obtained
characterizations open the door for further developments and applications.
Note that the reduction of minimizing prox-regular functions to the
minimization of their smooth Moreau envelopes have been recently exploited in
[21, 22, 23, 44] for the design and justification of generalized Newton-type
algorithms in nonsmooth optimization. The additional convexity of Moreau
envelopes in the case of variationally convex cost functions creates new
numerical perspectives for this approach by applying powerful theoretical and
algorithmic tools of convex analysis and optimization.

The aforementioned principal results and machinery of second-order variational
analysis allow us to derive coderivative-based second-order characterizations
of variational convexity and variational strong convexity with prescribed
moduli for general classes of l.s.c. functions. These characterizations are
obtained in both neighborhood and pointbased forms via the second-order
subdifferentials introduced by Mordukhovich [29], which have been broadly
developed in variational theory and applications, including more recent ones
to numerical algorithms of nonsmooth optimization; see below. In this way we
also shed new light on the study of tilt-stable minimizers.

Related topics addressed in this paper concern problems of composite
optimization written in the form

(1.1) $\mbox{\rm minimize}\quad\varphi(x)+\psi\big{(}g(x)\big{)},\quad
x\in{\rm I\\!R}^{n},$

where $\varphi\colon{\rm I\\!R}^{n}\to{\rm I\\!R}$ and $g\colon{\rm
I\\!R}^{n}\to{\rm I\\!R}^{m}$ are ${\cal C}^{2}$-smooth, while $\psi\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is merely lower semicontinuous. Since the
function $\psi$ is generally extended-real-valued, format (1.1) includes
problems of constrained optimization with the domain constraints
$g(x)\in\mbox{\rm dom}\,\psi$. Our major attention here is paid to
Rockafellar’s recent notions of variational and strong variational sufficiency
for local optimality in (1.1) that are proved to be important for developing
both theoretical and computational aspects of optimization. Based on the
second-order subdifferential characterizations of variational convexity and
its strong counterpart, we derive complete characterizations of variational
and strong variational sufficiency for large classes of composite optimization
problems. The obtained results are specified for problems of nonlinear
programming, where they are expressed entirely via the program data due to the
explicit computations of second-order subdifferentials.

The rest of the paper is organized as follows. Section 2 overviews those
notions of variational analysis and generalized differentiation, which are
broadly used in the formulations and proofs of the main results obtained
below. In Sections 3 and 4, we recall and discuss the notions of variational
convexity and strong variational convexity, respectively, and establish the
equivalence between these properties of the function in question and local
convexity/strong local convexity of its Moreau envelope. Section 5 is devoted
to deriving neighborhood and pointbased characterizations of variational
convexity and variational strong convexity of extended-real-valued functions
in terms of coderivative-based second-order subdifferentials. Section 6
addresses second-order subdifferential characterization of variational and
strong variational sufficiency for local optimality in problems of composite
optimization (1.1). Applications of these results to nonlinear programs are
given in Section 7. The concluding Section 8 summarizes the main results of
the paper and discusses some important topics of our future research.

##  2 Preliminaries and Discussions

In this section, we recall and discuss some basic notions and facts from
variational analysis that are largely in what follows; see [30, 31, 52] for
more details. Let $F$ be a set-valued mapping (multifunction) between
Euclidean spaces ${\rm I\\!R}^{n}$ and ${\rm I\\!R}^{m}$. As usual, the
effective domain and the graph of $F$ are given, respectively, by

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

The (Painlevé-Kuratowski) outer limit of $F$ as $x\rightarrow\bar{x}$ is
defined as

(2.1) $\underset{x\rightarrow\bar{x}}{\mathop{{\rm Lim}\,{\rm
sup}}}\;F(x):=\big{\\{}y\in{\rm
I\\!R}^{n}\;\big{|}\;\exists\,x_{k}\to\bar{x},\ y_{k}\rightarrow y\;\mbox{
with }y_{k}\in F(x_{k}),\;k=1,2,\ldots\big{\\}}.$

Considering an extended-real-valued function $\varphi\colon{\rm
I\\!R}^{n}\rightarrow\overline{{\rm I\\!R}}$, we always assume that $\varphi$
is proper, i.e., $\mbox{\rm dom}\,\varphi:=\\{x\in{\rm
I\\!R}^{n}\;|\;\varphi(x)<\infty\\}\neq\emptyset$. The (Fréchet) regular
subdifferential of $\varphi$ at $\bar{x}\in\mbox{\rm dom}\,\varphi$ is

(2.2) $\widehat{\partial}\varphi(\bar{x})=\Big{\\{}v\in{\rm
I\\!R}^{n}\;\Big{|}\;\liminf\limits_{x\to\overline{x}}\frac{\varphi(x)-\varphi(\bar{x})-\langle
v,x-\bar{x}\rangle}{\|x-\bar{x}\|}\geq 0\Big{\\}}.$

The (Mordukhovich) limiting/basic/general subdifferential and singular/horizon
subdifferential of $\varphi$ at $\bar{x}$ are defined, respectively, via the
outer limit (2.1) by

(2.3)
$\partial\varphi(\bar{x}):=\underset{x\overset{\varphi}{\to}\bar{x}}{\mathop{{\rm
Lim}\,{\rm sup}}}\;\widehat{\partial}\varphi(x)\;\mbox{ and
}\;\partial^{\infty}\varphi(\bar{x}):=\underset{x\overset{\varphi}{\to}\bar{x}\atop\lambda\downarrow
0}{\mathop{{\rm Lim}\,{\rm sup}}}\;\lambda\widehat{\partial}\varphi(x),$

where $x\overset{\varphi}{\to}\bar{x}$ means that $x\rightarrow\bar{x}$ with
$\varphi(x)\rightarrow\varphi(\bar{x})$. In the case where
$\widehat{\partial}\varphi(\bar{x})=\partial\varphi(\bar{x})$, the function
$\varphi$ is called lower regular at $\bar{x}$; see [30]. This agrees with the
subdifferential (or Clarke) regularity of $\varphi$ at $\bar{x}$ in the sense
of [52] provided that $\varphi$ is locally Lipschitzian around $\bar{x}$.
Observe that both regular and limiting subdifferentials reduce to the
classical gradient $\nabla\varphi(\bar{x})$ for continuously differentiable
functions, while the singular subdifferential of an l.s.c. function reduces to
$\\{0\\}$ if and only if $\varphi$ is locally Lipschitzian around $\bar{x}$.

Given a set $\Omega\subset{\rm I\\!R}^{n}$ with its indicator function
$\delta_{\Omega}(x)$ equal to $0$ for $x\in\Omega$ and to $\infty$ otherwise,
the regular and limiting normal cones to $\Omega$ at $\bar{x}\in\Omega$ are
defined, respectively, via the subdifferentials (2.2) and (2.3) by

(2.4)
$\widehat{N}_{\Omega}(\bar{x}):=\widehat{\partial}\delta_{\Omega}(\bar{x})\quad\text{and}\quad
N_{\Omega}(\bar{x}):=\partial\delta_{\Omega}(\bar{x}).$

The coderivative constructions for $F\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ at $(\bar{x},\bar{y})\in\mbox{\rm
gph}\,F$ are defined via the normal cones (2.4) to the graph of $F$ at this
point. They are the regular coderivative and the limiting coderivative of $F$
at $(\bar{x},\bar{y})$ given by

(2.5) $\widehat{D}^{*}F(\bar{x},\bar{y})(v):=\big{\\{}u\in{\rm
I\\!R}^{n}\;\big{|}\;(u,-v)\in\widehat{N}_{{\rm
gph}\,F}(\bar{x},\bar{y})\big{\\}},\quad v\in{\rm I\\!R}^{m},$ (2.6)
$D^{*}F(\bar{x},\bar{y})(v):=\big{\\{}u\in{\rm I\\!R}^{n}\;\big{|}\;(u,-v)\in
N_{{\rm gph}\,F}(\bar{x},\bar{y})\big{\\}},\quad v\in{\rm I\\!R}^{m},$

respectively. In the case where $F(\bar{x})$ is the singleton $\\{\bar{y}\\}$,
we omit $\bar{y}$ in the notation of (2.5) and (2.6). Note that if
$F\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ is ${\cal C}^{1}$-smooth around
$\bar{x}$, then

$\widehat{D}^{*}F(\bar{x})(u)=D^{*}F(\bar{x})(u)=\big{\\{}\nabla
F(\bar{x})^{*}u\big{\\}},\quad u\in{\rm I\\!R}^{n},$

where $\nabla F(\bar{x})^{*}$ is the adjoint/transpose matrix of the Jacobian
$\nabla F(\bar{x})$.

######  Definition 2.1 (second-order subdifferentials).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and
$\bar{x}\in\mbox{\rm dom}\,\varphi$.

(i) For any $\bar{y}\in{\partial}\varphi(\bar{x})$, the mapping
${\partial}^{2}\varphi(\bar{x},\bar{y}):{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{n}$ with the values

(2.7)
${\partial}^{2}\varphi(\bar{x},\bar{y})(u):=({D}^{*}{\partial}\varphi)(\bar{x},\bar{y})(u),\quad
u\in{\rm I\\!R}^{n},$

is said to be the basic/limiting second-order subdifferential of $\varphi$ at
$\bar{x}$ relative to $\bar{y}$.

(ii) For any $\bar{y}\in\partial\varphi(\bar{x})$, the mapping
$\breve{\partial}^{2}\varphi(\bar{x},\bar{y}):{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ with the values

(2.8)
$\breve{\partial}^{2}\varphi(\bar{x},\bar{y})(u):=(\widehat{D}^{*}\partial\varphi)(\bar{x},\bar{y})(u),\quad
u\in{\rm I\\!R}^{n},$

is said to be the combined second-order subdifferential of $\varphi$ at
$\bar{x}$ relative to $\bar{y}$.

Clearly, we have the following inclusion

(2.9)
$\breve{\partial}^{2}\varphi(x,y)(w)\subset\partial^{2}\varphi(x,y)(w)\;\text{
for all }\;(x,y)\in\mbox{\rm gph}\,\partial\varphi,\;w\in{\rm I\\!R}^{n}.$

We omit $\bar{y}=\nabla\varphi(\bar{x})$ in the above second-order
subdifferential notation if $\varphi$ is $\mathcal{C}^{1}$-smooth around
$\bar{x}$. If $\varphi$ is $\mathcal{C}^{2}$-smooth around $\bar{x}$, then we
get, via the symmetric Hessian matrix that

$\breve{\partial}^{2}\varphi(\bar{x})(u)=\partial^{2}\varphi(\bar{x})(u)=\big{\\{}\nabla^{2}\varphi(\bar{x})u\big{\\}}\;\mbox{
for all }\;u\in{\rm I\\!R}^{n}.$

This justifies the names of generalized Hessians for the second-order
constructions from Definition 2.1.

It has been recognized in variational analysis and applications to
optimization and related topics that the basic second-order subdifferential
(2.7) enjoys well-developed calculus rules in both finite and infinite
dimensions [30, 31, 39, 38, 42, 43] and admits efficient computations for
major classes of extended real-valued functions encountered in variational
analysis, optimization, machine learning, statistics, stochastic systems,
optimal control, etc. as, e.g., in [9, 10, 12, 17, 18, 19, 21, 22, 42, 43, 45,
53]. Involving these calculus and computations, the second-order construction
(2.7) has been instrumental, among other applications, to provide complete
characterizations of the fundamental notions of tilt and full stability in
optimization, optimal control, and variational systems as, e.g., in [13, 14,
15, 26, 33, 35, 36, 34, 37, 40, 42, 43, 46, 47], to characterize global and
local monotonicity properties of subgradient mappings [7, 36], and to
characterize convexity and generalized convexity properties of various classes
of extended-real-valued functions; see [4, 6, 7, 24, 25].

Although calculus rules available for the combined second-order
subdifferential (2.8) are less impressive in comparison with those for (2.7),
the second-order construction (2.8) is proved to be useful, especially in
infinite dimensions, to establish neighborhood characterizations of tilt and
full stability properties of variational systems, monotonicity properties of
multifunctions, and (generalized) convexity properties of extended-real-valued
functions; see, e.g., [4, 6, 7, 35, 36, 34, 43] and the references therein.
Note that it is often easier to compute (2.8) than (2.7), and then to employ
the computation of (2.8) for the subsequent computation of the more robust
construction (2.7).

We need to recall yet another notion of generalized second-order derivatives
including second subderivatives [52] and quadratic bundles [50]. Given
$\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ with
$\bar{x}\in\mbox{\rm dom}\,\varphi$, define the second subderivative of
$\varphi$ at $\bar{x}$ for $v\in{\rm I\\!R}^{n}$ and $w\in{\rm I\\!R}^{n}$ by
the lower limit of the second-order quotients

$d^{2}\varphi(\bar{x},v)(w):=\liminf_{\tau\downarrow 0\atop u\to
w}\frac{\varphi(\bar{x}+\tau u)-\varphi(\bar{x})-\tau\langle
v,u\rangle}{\frac{1}{2}\tau^{2}}.$

Then $\varphi$ is said to be twice epi-differentiable at $\bar{x}$ for $v$ if
for every $w\in{\rm I\\!R}^{n}$ and every choice of $\tau_{k}\downarrow 0$,
there exists a sequence $w^{k}\to w$ such that

$\frac{\varphi(\bar{x}+\tau_{k}w^{k})-\varphi(\bar{x})-\tau_{k}\langle
v,w^{k}\rangle}{\frac{1}{2}\tau_{k}^{2}}\to d^{2}\varphi(\bar{x},v)(w)\;\mbox{
as }\;k\to\infty.$

Twice epi-differentiability has been recognized as an important concept of
second-order variational analysis with numerous applications to optimization;
see the aforementioned monograph by Rockafellar and Wets and the recent papers
[27, 28]. A function $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is
called a generalized quadratic form if $\varphi(0)=0$ and the mapping
$\partial\varphi$ is generalized linear, i.e., $\mbox{\rm
gph}\,\partial\varphi$ is a subspace of ${\rm I\\!R}^{n}\times{\rm
I\\!R}^{n}$. The function $\varphi$ is called generalized twice differentiable
at $\bar{x}$ for a subgradient $\bar{v}\in\partial\varphi(\bar{x})$ if it is
twice epi-differentiable at $\bar{x}$ for $\bar{v}$ with the second-order
subderivative $d^{2}\varphi(\bar{x},\bar{v})$ being a generalized quadratic
form. This allows us to define the quadratic bundle of $\varphi$ at $\bar{x}$
for $\bar{v}$ by

(2.10) $\text{\rm
quad}\;\varphi(\bar{x},\bar{v}):=\left[\begin{array}[]{l}\text{ the collection
of generalized quadratic forms }q\text{ for which }\\\
\exists\left(x_{k},v_{k}\right)\rightarrow(\bar{x},\bar{v})\text{ with
}\varphi\text{ generalized twice differentiable }\\\ \text{ at }x_{k}\text{
for }v_{k}\text{ and such that the generalized quadratic }\\\ \text{ forms
}q_{k}=\frac{1}{2}d^{2}\varphi\left(x_{k},v_{k}\right)\text{ converge
epigraphically to }q,\end{array}\right.$

Next we recall some classes of extended-real-valued functions
$\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ broadly used in the
paper. As usual, $\varphi$ is convex on a convex set $\Omega\subset{\rm
I\\!R}^{n}$ if

$\varphi\big{(}(1-\lambda)x+\lambda
y\big{)}\leq(1-\lambda)\varphi(x)+\lambda\varphi(y)\quad\text{for all
}\;x,y\in\Omega,\;\lambda\in[0,1].$

We say that $\varphi$ is strongly convex on $\Omega$ with modulus $\kappa>0$
if its quadratic shift $\varphi-(\kappa/2)\|\cdot\|^{2}$ is convex on
$\Omega$, i.e.,

(2.11) $\varphi((1-\lambda)x+\lambda
y)\leq(1-\lambda)\varphi(x)+\lambda\varphi(y)-\frac{\kappa}{2}\lambda(1-\lambda)\|x-y\|^{2},$

for any $x,y\in\Omega$, $\lambda\in[0,1]$. It is easy to see that if $\varphi$
is strongly convex on $\Omega$ with modulus $\kappa>0$, then the function $h$
defined by $h(x):=\varphi(ax+b)$ is strongly convex on $\Omega$ with modulus
$\kappa a^{2}$, where $a\neq 0$ and $b\in{\rm I\\!R}$ are taken from (2.11).

An l.s.c. function $\varphi$ is prox-regular at $\bar{x}\in\mbox{\rm
dom}\,\varphi$ for $\bar{v}\in\partial\varphi(\bar{x})$ if there exist
$\varepsilon>0$ and $r\geq 0$ such that

(2.12) $\varphi(x)\geq\varphi(u)+\langle v,x-u\rangle-\frac{r}{2}\|x-u\|^{2}\
$

for all $x\in\mathbb{B}_{\varepsilon}(\bar{x})$ and $(u,v)\in\mbox{\rm
gph}\,\partial\varphi\cap(\mathbb{B}_{\varepsilon}(\bar{x})\times\mathbb{B}_{\varepsilon}(\bar{v}))$
with $\varphi(u)<\varphi(\bar{x})+\varepsilon$, where
$\mathbb{B}_{\varepsilon}(a)$ stands for the closed ball centred at $a$ with
radius $\varepsilon$. If this holds for all $v\in\partial\varphi(\bar{x})$,
then $\varphi$ is said to be prox-regular at $\bar{x}$.

We say that $\varphi$ is subdifferentially continuous at $\bar{x}$ for
$\bar{v}\in\partial\varphi(\bar{x})$ if for any $\varepsilon>0$ there exists
$\delta>0$ such that $|\varphi(x)-\varphi(\bar{x})|<\varepsilon$ whenever
$(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap(\mathbb{B}_{\delta}(\bar{x})\times\mathbb{B}_{\delta}(\bar{v}))$.
When this holds for all $v\in\partial\varphi(\bar{x})$, the function $\varphi$
is said to be subdifferentially continuous at $\bar{x}$. It is easy to see
that if $\varphi$ is subdifferentially continuous at $\bar{x}$ for $\bar{v}$,
then the inequality “$\varphi(x)<\varphi(\bar{x})+\varepsilon$” in the
definition of prox-regularity can be omitted. Functions that are both prox-
regular and subdifferentially continuous are called continuously prox-regular.
This is a major class of extended-real-valued functions in second-order
variational analysis, being a common roof for particular collections of
functions important for applications as, e.g., amenable functions, etc.; see
[52, Chapter 13].

The following two well-known constructions play a crucial role in this paper.
Given an l.s.c. function $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$
and a parameter value $\lambda>0$, the Moreau envelope $e_{\lambda}\varphi$
and proximal mapping $\textit{\rm Prox}_{\lambda\varphi}$ are defined by

(2.13)
$e_{\lambda}\varphi(x):=\inf\Big{\\{}\varphi(y)+\frac{1}{2\lambda}\|y-x\|^{2}\;\Big{|}\;y\in{\rm
I\\!R}^{n}\Big{\\}},\quad x\in{\rm I\\!R}^{n},$ (2.14)
$\operatorname{Prox}_{\lambda\varphi}(x):=\operatorname{argmin}\Big{\\{}\varphi(y)+\frac{1}{2\lambda}\|y-x\|^{2}\;\Big{|}\;y\in{\rm
I\\!R}^{n}\Big{\\}},\quad x\in{\rm I\\!R}^{n}.$

A function $\varphi$ is said to be prox-bounded if there exists $\lambda>0$
such that $e_{\lambda}\varphi(x)>-\infty$ for some $x\in{\rm I\\!R}^{n}$.

We now present important properties of the Moreau envelope and the proximal
mapping that are taken from [52, Proposition 13.37]. Recall that the
$\varphi$-attentive $\varepsilon$-localization of the subgradient mapping
$\partial\varphi$ around $(\bar{x},\bar{v})$ is the set-valued mapping
$T\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ defined by

(2.15)
$T(x):=\begin{cases}\big{\\{}v\in\partial\varphi(x)\;\big{|}\;\|v-\bar{v}\|<\varepsilon\big{\\}}&\text{if}\quad\|x-\bar{x}\|<\varepsilon\;\text{
and }\;|\varphi(x)-\varphi(\bar{x})|<\varepsilon,\\\
\emptyset&\text{otherwise}.\end{cases}$

If $\varphi$ is an l.s.c. function, a localization can be taken with just
$\varphi(x)<\varphi(\bar{x})+\varepsilon$ in (2.15). Recall also that a
function $\varphi$ is of class $C^{1,1}$ (or ${\cal C}^{1.+})$) around
$\bar{x}$ if it is ${\cal C}^{1}$-smooth and its gradient is Lipschitz
continuous around this point.

######  Proposition 2.2 (Moreau envelopes and proximal mappings for prox-
regular functions).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. and
prox-bounded function which is prox-regular at $\bar{x}$ for
$\bar{v}\in\partial\varphi(\bar{x})$. Then there exists a $\varphi$-attentive
$\varepsilon$-localization $T$ of $\partial\varphi$ such that for all
sufficiently small numbers $\lambda>0$ there is a convex neighborhood
$U_{\lambda}$ of $\bar{x}+\lambda\bar{v}$ on which the following hold:
(i) The Moreau envelope $e_{\lambda}\varphi$ from (2.13) is of class ${\cal
C}^{1,1}$ on the set $U_{\lambda}$.
(ii) The proximal mapping $\text{\rm Prox}_{\lambda\varphi}$ from (2.14) is
single-valued, monotone, and Lipschitz continuous on $U_{\lambda}$ satisfying
the condition ${\rm Prox}_{\lambda\varphi}(\bar{x}+\lambda\bar{v})=\bar{x}$.
(iii) The gradient of $e_{\lambda}\varphi$ is calculated by:

(2.16) $\nabla e_{\lambda}\varphi(x)=\frac{1}{\lambda}\Big{(}x-\text{\rm
Prox}_{\lambda\varphi}(x)\Big{)}=\big{(}\lambda
I+T^{-1}\big{)}^{-1}(x)\;\mbox{ for all }\;x\in U_{\lambda}.$

If in addition $\varphi$ is subdifferentially continuous at $\bar{x}$ for
$\bar{v}$, then $T$ in (2.16) can be replaced by $\partial\varphi$.

Next we formulate the main properties of extended-real-valued functions
studied in this paper, which have been recently introduced and investigated by
Rockafellar in [49, 50, 51].

######  Definition 2.3 (variationally convex functions).

An l.s.c. function $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is
called variationally convex at $\bar{x}$ for
$\bar{v}\in\partial\varphi(\bar{x})$ if for some convex neighborhood $U\times
V$ of $(\bar{x},\bar{v})$ there exist an l.s.c. convex function
$\psi\leq\varphi$ on $U$ and a number $\varepsilon>0$ such that

(2.17) $(U_{\varepsilon}\times V)\cap\mbox{\rm gph}\,\partial\varphi=(U\times
V)\cap\mbox{\rm gph}\,\partial\psi\;\text{and}\;\varphi(x)=\psi(x)\;\text{at
the common elements}\;(x,v),$

where $U_{\varepsilon}:=\\{x\in
U\;|\;\varphi(x)<\varphi(\bar{x})+\varepsilon\\}$. We say that $\varphi$ is
variationally strongly convex at $\bar{x}$ for $\bar{v}$ with modulus
$\sigma>0$ if (2.17) holds with $\psi$ being strongly convex on $U$ with this
modulus.

Let us illuminate some remarkable features of Rockafellar’s notions from
Definition 2.3.

######  Remark 2.4 (discussion on variational and strong variational
convexity).

Observe the following:

(i) It is easy to see from Definition 2.3 that if $V={\rm I\\!R}^{n}$ in
(2.17), then the variational convexity (variational strong convexity) reduces
to the local convexity (local strong convexity) of $\varphi$ around $\bar{x}$,
but not necessarily otherwise; cf. [49, Examples 6 and 7].

(ii) In Definition 2.3 of variational convexity, the function $\psi$ is
locally convex (i.e., convex on $U$). In fact, it is possible to equivalently
replace there the local convexity by the global one. Indeed, if there exists a
locally convex function $\psi$ satisfying (2.17), we can define the function
$\overline{\psi}:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ by:

$\overline{\psi}(x):=\begin{cases}\psi(x)&\text{if}\quad x\in U,\\\
\infty&\text{otherwise}.\end{cases}$

It is clear that $\overline{\psi}$ is an l.s.c. convex function on ${\rm
I\\!R}^{n}$ with $\partial\overline{\psi}(x)=\partial\psi(x)$ for any $x\in
U$, which implies that

$(U_{\varepsilon}\times V)\cap\mbox{\rm gph}\,\partial\varphi=(U\times
V)\cap\mbox{\rm
gph}\,\partial\overline{\psi}\;\text{and}\;\varphi(x)=\overline{\psi}(x)\;\text{at
the common elements}\;(x,v).$

Similarly, the local strong convexity of $\psi$ can be replaced by the global
one for variational strong convexity.

(iii) The prox-regularity of $\varphi$ at $\bar{x}$ holds automatically if
$\varphi$ is variationally convex for this pair $(\bar{x},\bar{v})$. Indeed,
we have by the convexity of $\psi$ in Definition 2.3 that

$\psi(x)\geq\psi(u)+\langle v,x-u\rangle\quad\text{for all }\;x,u\in{\rm
I\\!R}^{n},\;v\in\partial\psi(u).$

Combining this with (2.17) and $\psi\leq\varphi$ on $U$ yields

$\varphi(x)\geq\varphi(u)+\langle v,x-u\rangle\quad\text{for all }\;x\in
U,\;(u,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U_{\varepsilon}\times V),$

which tells us that $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$. When
$\varphi$ is subdifferentially continuous at $\bar{x}$ for $\bar{v}$, we can
replace the set $U_{\varepsilon}$ by the neighborhood $U$ in Definition 2.3.

(iv) If $\varphi$ is $\mathcal{C}^{1}$-smooth around $\bar{x}$, then the
variational convexity (variational strong convexity) of $\varphi$ at $\bar{x}$
for $\bar{v}=\nabla\varphi(\bar{x})$ reduces to the local convexity (local
strong convexity) around $\bar{x}$. Indeed, the underlying condition (2.17)
reads for smooth functions $\varphi$ as

$(U\times V)\cap\mbox{\rm gph}\,\nabla\varphi=(U\times V)\cap\mbox{\rm
gph}\,\partial\psi\;\text{and}\;\varphi(x)=\psi(x)\;\text{at the common
elements}\;(x,v).$

Due to the continuity of $\nabla\varphi$ around $\bar{x}$, we can find a
neighborhood $\widetilde{U}\subset U$ of $\bar{x}$ such that
$\nabla\varphi(\widetilde{U})\subset V$, which implies that
$\varphi(x)=\psi(x)$ for any $x\in\widetilde{U}$. Therefore, $\varphi$ is
convex (strongly convex) on $\widetilde{U}$, which means the local convexity
(local strong convex) of $\varphi$ around $\bar{x}$. This remark tells us that
the novelty of variational convexity (variational strong convexity) vs. local
convexity (local strong convexity) emerges only in nonsmooth functions.

The following example presents a nonconvex variationally convex function,
which is called $\ell^{0}$ pseudo-norm and is commonly used in compressive
sensing; see, e.g., [3, 11].

######  Example 2.5 (variational convexity of $\ell^{0}$ pseudo-norm).

Let $\varphi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ given by $\varphi(x):=\|x\|_{0}$,
which is the $\ell^{0}$ norm of $x$, counting the number of nonzero elements
of $x$. In other words, we can represent $\varphi$ as

$\varphi(x)=\sum_{i=1}^{n}I(x_{i})\;\text{ for all
}\;x=(x_{1},\ldots,x_{n})\in{\rm I\\!R}^{n}$

by using the standard notation

$I(t):=\begin{cases}1&\text{if}\quad t\neq 0,\\\
0&\text{otherwise}.\end{cases}$

It is easy to calculate the subdifferential of $\varphi$ by

$\partial\varphi(x)=\left\\{v=(v_{1},v_{2},\ldots,v_{n})\in{\rm
I\\!R}^{n}\;\bigg{|}\;\begin{array}[]{@{}cc@{}}v_{i}=0,\;\text{if }\;x_{i}\neq
0,\\\ v_{i}\in{\rm I\\!R},\;\text{if }\;x_{i}=0\end{array}\right\\}.$

Let us show that $\varphi$ is variationally convex at $\bar{x}=0$ for any
$\bar{v}\in\partial\varphi(\bar{x})$. Indeed, take $\varepsilon\in(0,1)$ and
denote

$U:=\text{\rm int}\,\mathbb{B}_{\delta_{1}}(0)\times\ldots\times\text{\rm
int}\,\mathbb{B}_{\delta_{n}}(0)\;\text{ and }\;V:=\text{\rm
int}\,\mathbb{B}_{\varepsilon}(\bar{v}_{1})\times\ldots\times\text{\rm
int}\,\mathbb{B}_{\varepsilon}(\bar{v}_{n}).$

where $\delta_{i}:=(1+|\bar{v}_{i}|)^{-1}$ for $i=1,\ldots,n$. Define further
the l.s.c. convex function $\psi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ by

$\psi(x):=\|x\|_{1}+\langle\bar{v},x\rangle\;\text{ for all }\;x\in{\rm
I\\!R}^{n}.$

It is clear that $\psi\leq\varphi$ on $U$ and that $U_{\varepsilon}=\\{0\\}$.
Moreover, the simple computation tells us that

$\partial\psi(x)=\left\\{v=(v_{1},\ldots,v_{n})\in{\rm
I\\!R}^{n}\;\bigg{|}\;\begin{array}[]{@{}cc@{}}v_{i}=\bar{v}_{i}+\text{\rm
sgn}(x_{i}),\;\text{if }\;x_{i}\neq 0,\\\
v_{i}\in\bar{v}_{i}+[-1,1],\;\text{if }\;x_{i}=0\end{array}\right\\},$

which implies therefore the equalities

$(U_{\varepsilon}\times V)\cap\mbox{\rm gph}\,\partial\varphi=(U\times
V)\cap\mbox{\rm gph}\,\partial\psi=\\{0\\}\times V\;\text{and
}\;\psi(0)=\varphi(0)$

This justifies (2.17) and thus shows that $\varphi$ is variationally convex at
$\bar{x}$ for $\bar{v}$.

Next we recall some notions of monotonicity of set-valued mappings and their
local counterparts. A multifunction $T:{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{n}$ is monotone relative to a subset $W\subset{\rm
I\\!R}^{n}\times{\rm I\\!R}^{n}$ if

(2.18) $\langle v_{1}-v_{2},u_{1}-u_{2}\rangle\geq 0\quad\text{for all
}\;(u_{1},v_{1}),(u_{2},v_{2})\in\mbox{\rm gph}\,T\cap W.$

Condition (2.18) is referred to as global monotonicity when $W={\rm
I\\!R}^{n}\times{\rm I\\!R}^{n}$. Similarly, strong monotonicity with modulus
$\sigma>0$ corresponds to replacing $\langle
v_{1}-v_{2},u_{1}-u_{2}\rangle\geq 0$ in (2.18) by $\langle
v_{1}-v_{2},u_{1}-u_{2}\rangle\geq\sigma\|u_{1}-u_{2}\|^{2}$.

Monotonicity can also be defined locally around a given point. More
specifically, $T\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ is
locally monotone around $(\bar{x},\bar{v})\in\mbox{\rm gph}\,T$ if there
exists a neighborhood $W\subset{\rm I\\!R}^{n}\times{\rm I\\!R}^{n}$ of
$(\bar{x},\bar{v})$ such that $T$ is monotone relative to this neighborhood.
For an l.s.c. function $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$, the
subgradient mapping $\partial\varphi:{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{n}$ is said to be $\varphi$-locally monotone around
$(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial\varphi$ if there exists a convex
neighborhood $U\times V$ of $(\bar{x},\bar{v})$ such that $\partial\varphi$ is
monotone relative to the set

(2.19) $W:=\big{\\{}(x,y)\in U\times
V\big{|}\;\varphi(x)<\varphi(\bar{x})+\varepsilon\big{\\}}$

for some $\varepsilon>0$. The same pattern defines the notion of
$\varphi$-local strong monotonicity.

It is clear that if $T:=\partial\varphi$ is locally monotone around
$(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial\varphi$, then it is also
$\varphi$-locally monotone around this point. The reverse implication is not
correct. Indeed, consider the nonsmooth l.s.c. function $\varphi:{\rm
I\\!R}\to{\rm I\\!R}$ defined by $\varphi(x):=0$ if $x\leq 0$ and
$\varphi(x):=1$ if $x>0$. It is easy to check that

$\widehat{\partial}\varphi(x)=\partial\varphi(x)=\begin{cases}\\{0\\}&\text{if}\quad
x\neq 0,\\\ [0,\infty)&\text{otherwise}.\end{cases}$

We see that $\partial\varphi$ is not locally monotone around
$(\bar{x},\bar{v}):=(0,0)$, but it is $\varphi$-locally monotone around this
point because $\partial\varphi$ is locally monotone relative to the set

$W:=\big{\\{}(x,y)\in\mathbb{B}_{\varepsilon}(\bar{x})\times\mathbb{B}_{\varepsilon}(\bar{v})\;\big{|}\;\varphi(x)<\varphi(\bar{x})+\varepsilon\big{\\}},$

where $\varepsilon\in(0,1)$. When $\varphi$ is subdifferentially continuous at
$\bar{x}$ for $\bar{v}$, there is no difference between the local monotonicity
and $\varphi$-local monotonicity of $T:=\partial\varphi$ around
$(\bar{x},\bar{v})$.

Next we consider a continuous (i.e., certainly being subdifferentially
continuous) and variationally convex function on ${\rm I\\!R}$, which is known
as the log-sum penalty function. This function is commonly used to bridge the
gap between the $\ell_{0}$ and $\ell_{1}$ norms in compressive sensing [3] and
as a nonconvex surrogate function of the matrix rank function in the low-rank
regularization [11].

######  Example 2.6 (log-sum penalty function).

Let $\varphi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ given by

$\varphi(x)=\sum_{i=1}^{n}\log(1+|x_{i}|)\;\text{for all
}\;x=(x_{1},\ldots,x_{n})\in{\rm I\\!R}^{n}.$

We clearly have the subdifferential representation

$\partial\varphi(x)=\big{\\{}v=(v_{1},v_{2},\ldots,v_{n})\in{\rm
I\\!R}^{n}\;\big{|}\;v_{i}\in G(x_{i}),\;i=1,\ldots,n\big{\\}},$

where the multifunction $G:{\rm I\\!R}\rightrightarrows{\rm I\\!R}$ is defined
by

$G(t):=\begin{cases}\displaystyle\frac{1}{t-1}&\text{if }\quad t<0,\\\
[-1,1]&\text{if }\quad t=0,\\\ \displaystyle\frac{1}{t+1}&\text{if }\quad
t>0.\end{cases}$

To show that $\varphi$ is variationally convex at $\bar{x}:=0$ for any
$\bar{v}\in\text{\rm int}\,\partial\varphi(\bar{x})=(-1,1)^{n}$, observe that
$\partial\varphi$ is locally monotone around $(\bar{x},\bar{v})$. Then the
claimed variational convexity of $\varphi$ follows from [49, Theorem 1].

Finally in this section, we recall the fundamental notion of tilt stability of
local minimizers introduced by Poliquin and Rockafellar [46] and then
comprehensively investigated in many publications mentioned above (see also
the references therein) with numerous applications in variational analysis and
optimization.

######  Definition 2.7 (tilt-stable local minimizers).

Given $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$, a point
$\bar{x}\in\mbox{\rm dom}\,\varphi$ is a tilt-stable local minimizer of
$\varphi$ if there exists a number $\gamma>0$ such that the mapping

(2.20) $M_{\gamma}\colon v\mapsto{\rm argmin}\big{\\{}\varphi(x)-\langle
v,x\rangle\;\big{|}\;x\in\mathbb{B}_{\gamma}(\bar{x})\big{\\}}$

is single-valued and Lipschitz continuous on some neighborhood of $0\in{\rm
I\\!R}^{n}$ with $M_{\gamma}(0)=\\{\bar{x}\\}$.

We also consider in what follows a quantitative version of this notion that
specifies a modulus of tilt stability. Namely, $\bar{x}$ is a tilt-stable
minimizer of $\varphi$ with modulus $\kappa>0$ if the mapping $M_{\gamma}$ is
Lipschitz continuous with constant $\kappa$ in the framework of Definition
2.7.

The remark below discusses relationships between variational convexity and
local minimizers as well as between variational strong convexity and tilt-
stable local minimizers.

######  Remark 2.8 (variational convexity and local minimizers).

Considering an extended-real-valued l.s.c. function $\varphi:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$, observe the following:

(i) If $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is variationally
convex at $\bar{x}$ for $0\in\partial\varphi(\bar{x})$, then $\bar{x}$ is a
local minimizer of $\varphi$. The reverse implication fails in general.
Indeed, consider the continuous function

(2.21) $\varphi(x):=\begin{cases}\text{\rm
min}\left\\{\displaystyle\left(1+\frac{1}{n}\right)|x|-\frac{1}{n(n+1)},\frac{1}{n}\right\\}&\text{if}\quad\displaystyle\frac{1}{n+1}\leq|x|\leq\frac{1}{n},\\\
0&\text{if}\quad x=0\end{cases}$

taken from [13, Example 3.4]. It is easy to check that this function is not
prox-regular at its local minimizer $\bar{x}=0$ for $\bar{v}=0$, and hence it
is not variationally convex for these points by Remark 2.4(iii).

(ii) It follows from [49, Theorems 2.3] that if $\varphi:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is variationally strongly convex at
$\bar{x}$ for $0\in\partial\varphi(\bar{x})$ with modulus $\sigma>0$, then
$\bar{x}$ is a tilt-stable local minimizer of $\varphi$ with modulus
$\sigma^{-1}$. However, the reverse implication may fail in simple situations.
As shown in [13, Example 3.4], the point $\bar{x}=0$ is a tilt-stable local
minimizer of $\varphi$ from (2.21). However, by (i) this function is not even
variationally convex at $\bar{x}$ for $\bar{v}=0$.

Note that the failure of the reverse implication in Remark 2.8(ii) is
impossible if a function $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm
I\\!R}}$ is continuously prox-regular at $\bar{x}$ for $0$. This is proved in
the next proposition.

######  Proposition 2.9 (equivalent descriptions of variational strong
convexity).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be continuously prox-
regular at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for
$0\in\partial\varphi(\bar{x})$. Then the following assertions are equivalent:

(i) $\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}=0$
with modulus $\sigma>0$.

(ii) $\bar{x}$ is a tilt-stable local minimizer of $\varphi$ with modulus
$\sigma^{-1}$.

(iii) $\partial\varphi$ is locally strongly monotone around $(\bar{x},0)$ with
modulus $\sigma>0$.

[Proof.] Due to the continuous prox-regularity of $\varphi$ at $\bar{x}$ for
$0$ and [49, Lemma 4.1], the variational strong convexity of $\varphi$ at
$\bar{x}$ for $0$ with modulus $\sigma>0$ is equivalent to the existence of
neighborhoods $U$ of $\bar{x}$ and $V$ of $0$ such that

$\varphi(x)\geq\varphi(u)+\langle
v,x-u\rangle+\frac{\sigma}{2}\|x-u\|^{2}\;\mbox{ for all }\;x\in
U,\;(u,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U\times V).$

The latter condition is equivalent to $\bar{x}$ being a tilt-stable local
minimizer of $\varphi$ with modulus $\sigma^{-1}$ by [35, Theorem 3.2], which
justifies therefore the equivalence between (i) and (ii). The equivalence
between the assertions (i) and (iii) follows from [49, Theorem 2].

######  Remark 2.10 (on second-order characterizations of variational strong
convexity).

It is known that the tilt stability of a continuously prox-regular function
$\varphi$ at $\bar{x}$ for $0$ is equivalent to the positive-definiteness of
the second-order subdifferential $\partial^{2}\varphi(\bar{x},0)$; see [46].
Therefore, by the equivalent descriptions of the variational strong convexity
in Proposition 2.9, we can immediately obtain the second-order
characterizations for variational strong convexity at $\bar{x}$ for
$\bar{v}=0$ in the case where $\varphi$ is continuously prox-regular. It is
shown in Section 5 that we can obtain the coderivative-based characterizations
of both variational convexity and variational strong convexity without using
the characterizations of tilt stability. This new approach is mainly based on
the usage of the “hidden convexity” of Moreau envelopes established in the
next section.

##  3 Variational Convexity via Moreau Envelopes

As mentioned in Section 2, a variationally convex function around a given
point is not necessarily convex around this point. In this section, we show
that the variational convexity of an l.s.c. function is equivalent to the
local convexity of its Moreau envelope. This kind of “hidden convexity” is not
only significant for its own sake, but also plays a crucial role in
establishing the new characterizations of variational convexity via second-
order subdifferentials (2.7) and (2.8), which are provided in Section 5.

To proceed, we begin with the following lemma taken from [49, Theorem 1],
which lists the characterizations of variationally convex functions via some
properties of their limiting subdifferentials (2.3).

######  Lemma 3.1 (subgradient characterizations of variational convexity).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. function
with $\bar{x}\in\mbox{\rm dom}\,\varphi$ and
$\bar{v}\in\widehat{\partial}\varphi(\bar{x})$. The following assertions are
equivalent:

(i) $\varphi$ is variationally convex at $\bar{x}$ for $\bar{v}$.

(ii) $\partial\varphi$ is $\varphi$-locally monotone around
$(\bar{x},\bar{v})$.

(iii) There are neighborhoods $U$ of $\bar{x}$, $V$ of $\bar{v}$, and a number
$\varepsilon>0$ such that

(3.1) $\varphi(x)\geq\varphi(u)+\langle v,x-u\rangle\quad\text{for all }\;x\in
U,\;(u,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U_{\varepsilon}\times V),$

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

Here is the aforementioned interconnection of variational convexity of
extended-real-valued functions and local convexity of their Moreau envelopes.

######  Theorem 3.2 (characterization of variational convexity via Moreau
envelopes).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. and prox-
bounded function with $\bar{x}\in\mbox{\rm dom}\,\varphi$ and
$\bar{v}\in\partial\varphi(\bar{x})$. The following assertions are equivalent:

(i) $\varphi$ is variationally convex at $\bar{x}$ for $\bar{v}$.

(ii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$, and the Moreau
envelope $e_{\lambda}\varphi$ is locally convex around
$\bar{x}+\lambda\bar{v}$ for small $\lambda>0$.

[Proof.] By Remark 2.4(iii), the variational convexity of a function yields
its prox-regularity. Therefore, we only need to verify that assertion (i) is
equivalent to the fact that the Moreau envelope $e_{\lambda}\varphi$ is
locally convex around $\bar{x}+\lambda\bar{v}$ for all $\lambda>0$
sufficiently small, provided that $\varphi$ is prox-regular at $\bar{x}$ for
$\bar{v}$. Observe first that it follows directly from definitions (2.12) of
prox-regularity and (2.2) of regular subgradients that
$\bar{v}\in\widehat{\partial}\varphi(\bar{x})$. Proposition 2.2 tells us that
the assumed lower semicontinuity, prox-boundedness, and prox-regularity
properties of $\varphi$ guarantee the existence of $\lambda_{0}>0$ and a
$\varphi$-attentive $\gamma$-localization $T:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ given by

(3.2)
$T(x):=\begin{cases}\big{\\{}v\in\partial\varphi(x)\big{|}\;\|v-\bar{v}\|<\gamma\big{\\}}&\text{if}\quad\|x-\bar{x}\|<\gamma\;\text{
and }\;\varphi(x)<\varphi(\bar{x})+\gamma,\\\
\emptyset&\text{otherwise}\end{cases}$

such that for any $\lambda\in(0,\lambda_{0})$ there is a neighborhood
$U_{\lambda}$ of $\bar{x}+\lambda\bar{v}$ on which $e_{\lambda}\varphi$ is of
class $\mathcal{C}^{1,1}$, that the proximal mapping $\text{\rm
Prox}_{\lambda\varphi}$ is single-valued and Lipschitz continuous on
$U_{\lambda}$ with ${\rm
Prox}_{\lambda\varphi}(\bar{x}+\lambda\bar{v})=\bar{x}$, and that the gradient
expression for the Moreau envelope (2.16) holds with $T$ taken from (3.2).

To verify (i)$\Longrightarrow$(ii), suppose that $\varphi$ is variationally
convex at $\bar{x}$ for $\bar{v}$ and deduce from Lemma 3.1 that
$\partial\varphi$ is $\varphi$-locally monotone around $(\bar{x},\bar{v})$.
Then there exists $\varepsilon>0$ such that the subgradient mapping
$\partial\varphi$ is monotone relative to the set $W$ from (2.19). Fixing any
$\lambda\in(0,\lambda_{0})$, we get from (2.16) that

(3.3) $(I-\lambda\nabla
e_{\lambda}\varphi)(\bar{x}+\lambda\bar{v})=\bar{x}\quad\text{and }\;\nabla
e_{\lambda}\varphi(\bar{x}+\lambda\bar{v})=\bar{v}.$

It follows from (3.3) and from the continuity of the mappings
$\psi_{\lambda}:=e_{\lambda}\varphi-\frac{1}{2\lambda}\|\text{\rm
Prox}_{\lambda\varphi}(\cdot)-\cdot\|^{2}$ and $\nabla e_{\lambda}\varphi$,
$I-\lambda\nabla e_{\lambda}\varphi$ around $\bar{x}+\lambda\bar{v}$ that
there exists a neighborhood $U\subset U_{\lambda}$ of $\bar{x}+\lambda\bar{v}$
such that

(3.4) $\big{(}(I-\lambda\nabla e_{\lambda}\varphi)(x)\times\nabla
e_{\lambda}\varphi(x)\big{)}\in\mathbb{B}_{\varepsilon}(\bar{x})\times\mathbb{B}_{\varepsilon}(\bar{v})\quad\text{and
}\;\psi_{\lambda}(x)-\psi_{\lambda}(\bar{x}+\lambda\bar{v})<\varepsilon\quad\text{for
all }\;x\in U.$

Definitions (2.13), (2.14) and the above construction of $\psi_{\lambda}$
ensure that $\psi_{\lambda}(x)=\varphi(\text{\rm Prox}_{\lambda\varphi}(x))$
for all $x\in U$. Fixing now any $x_{1},x_{2}\in U$ and using (2.16) and
(3.4), we get for $i=1,2$ the relationships

$\nabla e_{\lambda}\varphi(x_{i})\in T\big{(}x_{i}-\lambda\nabla
e_{\lambda}\varphi(x_{i})\big{)},$
$\begin{array}[]{ll}\varphi\big{(}x_{i}-\lambda\nabla
e_{\lambda}\varphi(x_{i})\big{)}=\varphi\big{(}(\text{\rm
Prox}_{\lambda\varphi}(x_{i})\big{)}=\psi_{\lambda}(x_{i})\\\
<\psi_{\lambda}(\bar{x}+\lambda\bar{v})+\varepsilon=\varphi\big{(}\text{\rm
Prox}_{\lambda\varphi}(\bar{x}+\lambda\bar{v})\big{)}+\varepsilon=\varphi(\bar{x})+\varepsilon.\end{array}$

By (2.19), this justifies the inclusions $(x_{i}-\lambda\nabla
e_{\lambda}\varphi(x_{i}),\nabla e_{\lambda}\varphi(x_{i}))\in W\cap\mbox{\rm
gph}\,T$ for $i=1,2$. Combining the latter with the monotonicity of
$\partial\varphi$ relative to $W$, we arrive at

$\big{\langle}\nabla e_{\lambda}\varphi(x_{1})-\nabla
e_{\lambda}\varphi(x_{2}),x_{1}-x_{2}\big{\rangle}\geq\lambda\|\nabla
e_{\lambda}\varphi(x_{1})-\nabla e_{\lambda}\varphi(x_{2})\|^{2}\geq 0,$

which verifies the convexity of $e_{\lambda}\varphi$ on $U$ due to [20,
Theorem 4.1.4], and therefore (ii) holds.

To prove next the reverse implication (ii)$\Longrightarrow$(i), assume that
the Moreau envelope $e_{\lambda}\varphi$ is locally convex around
$\bar{x}+\lambda\bar{v}$ for $\lambda>0$ sufficiently small. Fixing
$\lambda\in(0,\lambda_{0})$, suppose without loss of generality that
$e_{\lambda}\varphi$ is convex on $U_{\lambda}$. Utilizing the first-order
characterization of ${\cal C}^{1}$-smooth convex functions in [20, Theorem
4.1.1] gives us

(3.5) $e_{\lambda}\varphi(x)\geq e_{\lambda}\varphi(u)+\langle\nabla
e_{\lambda}\varphi(u),x-u\rangle\;\mbox{ for all }\;x,u\in U_{\lambda}.$

Select neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{v}$ such that
$U\subset{\rm int}\,\mathbb{B}_{\gamma}(\bar{x})$, $V\subset{\rm
int}\,\mathbb{B}_{\gamma}(\bar{v})$, and

(3.6) $x+\lambda v\in U_{\lambda}\;\mbox{ whenever }\;x\in U\;\mbox{ and
}\;v\in V.$

By Lemma 3.1, it suffices to verify that

(3.7) $\varphi(x)\geq\varphi(u)+\langle v,x-u\rangle\;\mbox{ for all }\;x\in
U,\;(u,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U_{\gamma}\times V),$

where $U_{\gamma}$ as defined as in Lemma 3.1. Pick $x\in U$,
$(u,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U_{\gamma}\times V)$ and deduce
from (3.2) that $(u,v)\in\mbox{\rm gph}\,T$, which yields $u+\lambda
v\in(\lambda I+T^{-1})(v)$. It follows from (2.16) and (3.6) that

$\nabla e_{\lambda}\varphi(u+\lambda v)=(\lambda I+T^{-1})^{-1}(u+\lambda
v)=v,$ $\text{\rm Prox}_{\lambda\varphi}(u+\lambda v)=u+\lambda
v-\lambda\nabla e_{\lambda}\varphi(u+\lambda v)=u,$

which implies in turn the equalities

$\begin{array}[]{ll}e_{\lambda}\varphi(u+\lambda v)=\varphi\big{(}\text{\rm
Prox}_{\lambda\varphi}(u+\lambda
v)\big{)}+\displaystyle\frac{1}{2\lambda}\|u+\lambda v-\text{\rm
Prox}_{\lambda\varphi}(u+\lambda v)\|^{2}\\\
=\varphi(u)+\displaystyle\frac{1}{2\lambda}\|u+\lambda
v-u\|^{2}=\varphi(u)+\frac{\lambda}{2}\|v\|^{2}.\end{array}$

By (3.5), we get the relationships

$\displaystyle\begin{array}[]{ll}\varphi(x)+\displaystyle\frac{\lambda}{2}\|v\|^{2}=\varphi(x)+\frac{1}{2\lambda}\|x+\lambda
v-x\|^{2}\geq e_{\lambda}\varphi(x+\lambda v)\\\ \geq
e_{\lambda}\varphi(u+\lambda v)+\langle\nabla e_{\lambda}\varphi(u+\lambda
v),x+\lambda v-(u+\lambda
v)\rangle=\varphi(u)+\displaystyle\frac{\lambda}{2}\|v\|^{2}+\langle
v,x-u\rangle.\end{array}$

Subtracting the term $(\lambda/2)\|v\|^{2}$ from both sides of the above
inequalities, we arrive at the desired condition (3.7) and thus completes the
proof of the theorem.

Finally in this section, we discuss some applications of Theorem 3.2 to
numerical optimization.

######  Remark 3.3 (applications of variational convexity to generalized
Newton methods).

In the recent papers [21, 22, 23] and [44], several generalized Newton methods
of nonsmooth optimization have been designed and justified in the following
pattern: dealing first with problems of ${\cal C}^{1,1}$ optimization and then
propagating the algorithms and the imposed assumptions to extended-real-valued
prox-regular functions by using their Moreau envelopes and proximal mappings.
In this way, well-posedness and superlinear local and global convergence of
the proposed generalized Newton algorithms have been established for problems
of minimizing prox-regular functions, and hence for problems of constrained
optimization, in terms of their given data as well as of solutions to
subproblems in (2.13) and/or (2.14). Although constructive applications of
this procedure to solving some practical models, which appear in machine
learning, statistics, etc., are developed in the aforementioned papers, the
implementation of the designed algorithms for general classes of prox-regular
functions is a challenging issue. However, the variational convexity of the
original cost function allows us to reduce, by Theorem 3.2, the minimization
subproblems in (2.13) and (2.14) to problems of convex optimization, which
admit the much more elaborated machinery to be constructively resolved.
Detailed investigations in this direction will be conducted in our future
research.

##  4 Variational Strong Convexity via Moreau Envelopes

The main goal of this section is to establish characterizations of variational
strong convexity of extended-real-valued functions via strong convexity of
Moreau envelopes with precise relationships between the corresponding moduli.

We begin with recalling subgradient characterizations of variational strong
convexity taken from [49, Theorem 2].

######  Lemma 4.1 (subgradient characterizations of variational strong
convexity).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. function
with $\bar{x}\in\mbox{\rm dom}\,\varphi$ and
$\bar{v}\in\widehat{\partial}\varphi(\bar{x})$. The following assertions are
equivalent:

(i) $\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$ with
modulus $\sigma>0$.

(ii) $\partial\varphi$ is $\varphi$-locally strongly monotone around
$(\bar{x},\bar{v})$ with modulus $\sigma>0$.

(iii) There exist neighborhoods $U$ of $\bar{x}$, $V$ of $\bar{v}$, and a
number $\varepsilon>0$ such that

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

where $U_{\varepsilon}$ is defined in Lemma 3.1.

Given an l.s.c. function $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$
with $\bar{x}\in\mbox{\rm dom}\,\varphi$ and $\sigma\neq 0$, consider its
$\sigma$-quadratic shift

(4.2)
$\vartheta(x):=\varphi(x)-\frac{\sigma}{2}\|x-\bar{x}\|^{2}\quad\text{for all
}\;x\in{\rm I\\!R}^{n}.$

The next lemma presents relationships between variational strong convexity of
a function and variational convexity of its quadratic shift (4.2).

######  Lemma 4.2 (variational strong convexity via quadratic shifts).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. function
with $\bar{x}\in\mbox{\rm dom}\,\varphi$ and
$\bar{v}\in\partial\varphi(\bar{x})$, and let $\vartheta$ be defined in (4.2)
with some $\sigma>0$. Then the following hold:

(i) $\partial\varphi$ is $\varphi$-locally strongly monotone around
$(\bar{x},\bar{v})$ with modulus $\sigma$ if and only if $\partial\vartheta$
is $\vartheta$-locally monotone around the pair $(\bar{x},\bar{v})$.

(ii) $\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$
with modulus $\sigma$ if and only if the quadratically shifted function
$\vartheta$ is variationally convex at $\bar{x}$ for $\bar{v}$.

[Proof.] The elementary sum rule for limiting subdifferentials from [31,
Proposition 1.30] gives us

$\partial\vartheta(x)=\partial\varphi(x)-\sigma(x-\bar{x})\quad\text{\rm
whenever }\;x\in\mbox{\rm dom}\,\varphi.$

Therefore, we have $\bar{v}\in\partial\vartheta(\bar{x})$ if and only if
$\bar{v}\in\partial\varphi(\bar{x})$. Since (ii) follows directly from (i) by
using the equivalences in Lemmas 3.1 and 4.1, it suffices to verify (i). To
furnish this, fix $\varepsilon>0$ and denote $U:={\rm
int}\,\mathbb{B}_{\sqrt{\varepsilon/\sigma}}(\bar{x})$. Define

$U_{\varepsilon}^{\varphi}:=\big{\\{}x\in
U\;\big{|}\;\varphi(x)<\varphi(\bar{x})+\varepsilon\big{\\}},$
$U_{\varepsilon/2}^{\vartheta}:=\big{\\{}x\in
U\;\big{|}\;\vartheta(x)<\vartheta(\bar{x})+\varepsilon/2\big{\\}},\;\text{and
}\;U_{\varepsilon}^{\vartheta}:=\big{\\{}x\in
U\;\big{|}\;\vartheta(x)<\vartheta(\bar{x})+\varepsilon\big{\\}}.$

Given a convex neighborhood $V$ of $\bar{v}$, both sets $V+\sigma(U-\bar{x})$
and $V-\sigma(U-\bar{x})$ are also convex neighborhoods of $\bar{v}$ with the
fulfillment of implications

(4.3) $(x,v)\in\mbox{\rm
gph}\,\partial\vartheta\cap(U_{\varepsilon/2}^{\vartheta}\times
V)\Longrightarrow\big{(}x,v+\sigma(x-\bar{x})\big{)}\in\mbox{\rm
gph}\,\partial\varphi\cap\big{(}U_{\varepsilon}^{\varphi}\times[V+\sigma(U-\bar{x})]\big{)},$
(4.4) $(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap(U_{\varepsilon}^{\varphi}\times
V)\Longrightarrow\big{(}x,v-\sigma(x-\bar{x})\big{)}\in\mbox{\rm
gph}\,\partial\vartheta\cap\big{(}U_{\varepsilon}^{\vartheta}\times[V-\sigma(U-\bar{x})]\big{)}.$

Furthermore, we have the following equivalences:

(4.5) $\langle v_{1}-v_{2},x_{1}-x_{2}\rangle\geq
0\Longleftrightarrow\langle[v_{1}+\sigma(x_{1}-\bar{x})]-[v_{2}+\sigma(x_{2}-\bar{x})],x_{1}-x_{2}\rangle\geq\sigma\|x_{1}-x_{2}\|^{2},$
(4.6) $\langle
v_{1}-v_{2},x_{1}-x_{2}\rangle\geq\sigma\|x_{1}-x_{2}\|^{2}\Longleftrightarrow\langle[v_{1}-\sigma(x_{1}-\bar{x})]-[v_{2}-\sigma(x_{2}-\bar{x})],x_{1}-x_{2}\rangle\geq
0.$

Combining (4.3) and (4.5) gives us the implication

$\varphi$-locally strong monotonicity of $\partial\varphi$ around
$(\bar{x},\bar{v})$ $\Longrightarrow$ $\vartheta$-local monotonicity of
$\partial\vartheta$ around $(\bar{x},\bar{v})$.

Finally, combining (4.4) and (4.6) tells us that

$\vartheta$-local monotonicity of $\partial\vartheta$ around
$(\bar{x},\bar{v})$ $\Longrightarrow$ $\varphi$-locally strong monotonicity of
$\partial\varphi$ around $(\bar{x},\bar{v})$,

which therefore completes the proof of the lemma.

The next lemma calculated the Moreau envelope of the quadratically shifted
function (4.2).

######  Lemma 4.3 (Moreau envelope of quadratic shifts).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. and prox-
bounded function, and let $\bar{x}\in\mbox{\rm dom}\,\varphi$. Given
$\sigma\neq 0$, consider the quadratic shift (4.2). Then for each
$\gamma\in(0,|\sigma|^{-1})$ we have

(4.7)
$e_{\gamma}\vartheta(x)=e_{{\gamma}/(1-\sigma\gamma)}\varphi\left(\frac{x-\sigma\gamma\bar{x}}{1-\sigma\gamma}\right)-\frac{\sigma}{2(1-\sigma\gamma)}\|x-\bar{x}\|^{2},\quad
x\in{\rm I\\!R}^{n}.$

Consequently, the following holds for any $\lambda\in(0,|\sigma|^{-1})$:

(4.8)
$e_{\lambda}\varphi(x)=e_{\lambda/(1+\sigma\lambda)}\vartheta\left(\frac{x+\sigma\lambda\bar{x}}{1+\sigma\lambda}\right)+\frac{\sigma}{2(1+\sigma\lambda)}\|x-\bar{x}\|^{2},\quad
x\in{\rm I\\!R}^{n}.$

[Proof.] Pick any $\gamma\in(0,|\sigma|^{-1})$ and get by definition (2.13) of
the Moreau envelope that

$\displaystyle e_{\gamma}\vartheta(x)$ $\displaystyle=\inf_{y\in{\rm
I\\!R}^{n}}\left\\{\vartheta(y)+\frac{1}{2\gamma}\|y-x\|^{2}\right\\}=\inf_{y\in{\rm
I\\!R}^{n}}\left\\{\varphi(y)-\frac{\sigma}{2}\|y-\bar{x}\|^{2}+\frac{1}{2\gamma}\|y-x\|^{2}\right\\}$
$\displaystyle=\inf_{y\in{\rm
I\\!R}^{n}}\left\\{\varphi(y)-\frac{\sigma}{2}\|y-\bar{x}\|^{2}+\frac{1}{2\gamma}\|y-\bar{x}\|^{2}+\frac{1}{\gamma}\langle
y-\bar{x},\bar{x}-x\rangle+\frac{1}{2\gamma}\|x-\bar{x}\|^{2}\right\\}$
$\displaystyle=\inf_{y\in{\rm
I\\!R}^{n}}\left\\{\varphi(y)+\frac{1-\sigma\gamma}{2\gamma}\|y-\bar{x}\|^{2}+\frac{1}{\gamma}\langle
y-\bar{x},\bar{x}-x\rangle+\frac{1}{2\gamma(1-\sigma\gamma)}\|x-\bar{x}\|^{2}+\left(\frac{1}{2\gamma}-\frac{1}{2\gamma(1-\sigma\gamma)}\right)\|\bar{x}-x\|^{2}\right\\}$
$\displaystyle=\inf_{y\in{\rm
I\\!R}^{n}}\Bigg{\\{}\varphi(y)+\frac{1}{2\left(\frac{\gamma}{1-\sigma\gamma}\right)}\Big{\|}y-\frac{x-\sigma\gamma\bar{x}}{1-\sigma\gamma}\Big{\|}^{2}\Bigg{\\}}-\frac{\sigma}{2(1-\sigma\gamma)}\|x-\bar{x}\|^{2}$
$\displaystyle=e_{\gamma/(1-\sigma\gamma)}\varphi\left(\frac{x-\sigma\gamma\bar{x}}{1-\sigma\gamma}\right)-\frac{\sigma}{2(1-\sigma\gamma)}\|x-\bar{x}\|^{2},\quad
x\in{\rm I\\!R}^{n},$

which verifies (4.7). The second representation (4.8) follows from (4.7) since
$\varphi$ can be seen as the shifted function of $\vartheta$ with modulus
$-\sigma$, i.e., $\varphi(x)=\vartheta(x)-(-\sigma/2)\|x-\bar{x}\|^{2}$.

Now we are ready to derive the main result of this section that establishes
the equivalence between the variational strong convexity of an extended-real-
valued function and the local strong convexity of its Moreau envelope with a
precise relationship between the corresponding moduli.

######  Theorem 4.4 (quantitative characterization of variational strong
convexity via Moreau envelopes).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be l.s.c. and prox-
bounded with $\bar{x}\in\mbox{\rm dom}\,\varphi$ and
$\bar{v}\in\partial\varphi(\bar{x})$. Then the following are equivalent:

(i) $\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$ with
modulus $\sigma>0$.

(ii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$ and
$e_{\lambda}\varphi$ is locally strongly convex around
$\bar{x}+\lambda\bar{v}$ with modulus $\frac{\sigma}{1+\sigma\lambda}$ for all
numbers $\lambda>0$ sufficiently small.

[Proof.] We start with verifying implication (i)$\Longrightarrow$(ii). Note
that the claimed prox-regularity of $\varphi$ under (i) is checked in Remark
2.4(iii). Considering the shifted function $\vartheta$ from(4.2), we get by
Lemma 4.2 that $\vartheta$ is variationally convex at $\bar{x}$ for $\bar{v}$.
Utilizing Theorem 3.2 tells us that $e_{\lambda}\vartheta$ is locally convex
around $\bar{x}+\lambda\bar{v}$ for all small $\lambda>0$. Fix such a number
$\lambda$ and define $\gamma:=\lambda/(1+\sigma\lambda)$. Since
$\gamma<\lambda$, we find $\eta>0$ ensuring that $e_{\gamma}\vartheta$ is
convex on $\mathbb{B}_{\eta}(\bar{x}+\gamma\bar{v})$. Letting
$\varepsilon:=(1+\sigma\lambda)\eta>0$ gives us the implication

$x\in\mathbb{B}_{\varepsilon}(\bar{x}+\lambda\bar{v})\Longrightarrow\frac{x+\lambda\sigma\bar{x}}{1+\sigma\lambda}\in\mathbb{B}_{\eta}(\bar{x}+\gamma\bar{v}).$

Define further the function
$\theta:\mathbb{B}_{\varepsilon}(\bar{x}+\lambda\bar{v})\to\mathbb{B}_{\eta}(\bar{x}+\gamma\bar{v})$
by

(4.9) $\theta(x):=\frac{x+\lambda\sigma\bar{x}}{1+\sigma\lambda}$

and deduce from (4.8) that the following representation of the Moreau
envelope:

$e_{\lambda}\varphi=(e_{\gamma}\vartheta)\circ\theta+\frac{\sigma}{2(1+\sigma\lambda)}\|\cdot-\bar{x}\|^{2}.$

Since $(e_{\gamma}\vartheta)\circ\theta$ is a composition of a convex function
and an affine one, it is convex on
$\mathbb{B}_{\varepsilon}(\bar{x}+\lambda\bar{v})$. This tells us that
$e_{\lambda}\varphi$ is strongly convex on
$\mathbb{B}_{\varepsilon}(\bar{x}+\lambda\bar{v})$ with modulus
$\sigma/(1+\sigma\lambda)$, which justifies the claimed implication.

Next we verify implication (ii)$\Longrightarrow$(i). Suppose that the Moreau
envelope $e_{\lambda}\varphi$ is locally strongly convex around
$\bar{x}+\lambda\bar{v}$ with modulus $\mu(\lambda):=\sigma/(1+\sigma\lambda)$
for all $\lambda\in(0,\sigma^{-1})$ sufficiently small. Fixing such a number
$\lambda$, for each $\gamma\in(0,\lambda/(1+\sigma\lambda))$ we have
$0<\gamma/(1-\sigma\gamma)<\lambda$. This allows us to choose $\eta>0$ so that
$e_{\gamma/(1-\sigma\gamma)}\varphi$ is strongly convex on
$\mathbb{B}_{\eta}\left(\bar{x}+\frac{\gamma}{1-\sigma\gamma}\bar{v}\right)$
with modulus $\mu(\gamma/(1-\sigma\gamma))=\sigma(1-\sigma\gamma)$. Letting
$\varepsilon:=(1-\sigma\gamma)\eta>0$ yields the implication

$x\in\mathbb{B}_{\varepsilon}(\bar{x}+\gamma\bar{v})\Longrightarrow\frac{x-\sigma\gamma\bar{x}}{1-\sigma\gamma}\in\mathbb{B}_{\eta}\left(\bar{x}+\frac{\gamma}{1-\sigma\gamma}\bar{v}\right).$

Symmetrically to (4.9), define the function
$\widetilde{\theta}:\mathbb{B}_{\varepsilon}(\bar{x}+\gamma\bar{v})\to\mathbb{B}_{\eta}\left(\bar{x}+\frac{\gamma}{1-\sigma\gamma}\bar{v}\right)$
by

$\widetilde{\theta}(x):=\frac{x-\gamma\sigma\bar{x}}{1-\sigma\gamma}$

and then deduce from (4.7) the representation

$e_{\gamma}\vartheta=(e_{\gamma/(1-\sigma\gamma)}\varphi)\circ\widetilde{\theta}-\frac{\sigma}{2(1-\sigma\gamma)}\|\cdot-\bar{x}\|^{2},$

where $\vartheta$ is taken from(4.2). As follows from the discussion after the
definition of strong convexity in (2.11), the composite function
$(e_{\gamma/(1-\sigma\gamma)}\varphi)\circ\widetilde{\theta}$ is strongly
convex on $\mathbb{B}_{\varepsilon}(\bar{x}+\gamma\bar{v})$ with modulus

$\sigma(1-\sigma\gamma)\left(\frac{1}{1-\sigma\gamma}\right)^{2}=\frac{\sigma}{1-\sigma\gamma}.$

This tells us that $e_{\gamma}\vartheta$ is convex on
$\mathbb{B}_{\varepsilon}(\bar{x}+\gamma\bar{v})$, which implies by Theorem
3.2 that $\vartheta$ is variationally convex at $\bar{x}$ for $\bar{v}$.
Utilizing finally Lemma 4.2, we verify (i) and thus complete the proof.

When the modulus of variational strong convexity is not involved, we have yet
another equivalence.

######  Theorem 4.5 (equivalence between variational strong convexity and
local strong convexity of Moreau envelopes).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. and prox-
bounded function with $\bar{x}\in\mbox{\rm dom}\,\varphi$, and let
$\bar{v}\in\partial\varphi(\bar{x})$. Then the following assertions are
equivalent:

(i) $\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$.

(ii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$ and
$e_{\lambda}\varphi$ is locally strongly convex around
$\bar{x}+\lambda\bar{v}$ for all small $\lambda>0$.

[Proof.] Implication (i)$\Longrightarrow$(ii) is an immediate consequence of
Theorem 4.4. Suppose that (ii) holds and find $\lambda_{0}>0$ such that
$e_{\lambda}\varphi$ is locally strongly convex around
$\bar{x}+\lambda\bar{v}$ with some modulus $\sigma_{\lambda}>0$ for any
$\lambda\in(0,\lambda_{0})$. It follows from Proposition 2.2 that there exists
a $\varphi$-attentive $\gamma$-localization $T$ of $\varphi$ given by (3.2)
such that for all $\lambda>0$ sufficiently small there is a convex
neighborhood $U_{\lambda}$ of $\bar{x}+\lambda\bar{v}$ on which
$e_{\lambda}\varphi$ is $\mathcal{C}^{1,1}$ on $U_{\lambda}$ satisfying ${\rm
Prox}_{\lambda\varphi}(\bar{x}+\lambda\bar{v})=\bar{x}$ with (2.16). Fix
$\lambda\in(0,\lambda_{0})$ and suppose without loss of generality that
$e_{\lambda}\varphi$ is strongly convex on $U_{\lambda}$ with modulus
$\sigma_{\lambda}$. Utilizing the first-order description of ${\cal
C}^{1}$-smooth strongly convex functions from [20, Theorem 4.1.1] gives us

(4.10) $e_{\lambda}\varphi(x)\geq e_{\lambda}\varphi(u)+\langle\nabla
e_{\lambda}\varphi(u),x-u\rangle+\frac{\sigma_{\lambda}}{2}\|x-u\|^{2}\;\mbox{
for all }\;x,u\in U_{\lambda}.$

Let $U$ and $V$ be neighborhoods of $\bar{x}$ and $\bar{v}$, respectively,
such that $U\subset{\rm int}\,\mathbb{B}_{\gamma}(\bar{x})$, $V\subset{\rm
int}\,\mathbb{B}_{\gamma}(\bar{v})$, and

(4.11) $x+\lambda v\in U_{\lambda}\;\mbox{ whenever }\;x\in U,\;v\in V.$

By Lemma 4.1, it is sufficient to prove that

(4.12) $\varphi(x)\geq\varphi(u)+\langle
v,x-u\rangle+\frac{\sigma_{\lambda}}{2}\|x-u\|^{2}\;\mbox{ for all }\;x\in
U,\;(u,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U_{\gamma}\times V),$

where $U_{\gamma}$ is defined in Lemma 4.1. Picking $x\in U$ and
$(u,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U_{\gamma}\times V)$, we get by
(3.2) that $(u,v)\in\mbox{\rm gph}\,T$, which yields $u+\lambda v\in(\lambda
I+T^{-1})(v)$. It follows from (2.16) and (4.11) that

$\nabla e_{\lambda}\varphi(u+\lambda v)=(\lambda I+T^{-1})^{-1}(u+\lambda
v)=v,$ $\text{\rm Prox}_{\lambda\varphi}(u+\lambda v)=u+\lambda
v-\lambda\nabla e_{\lambda}\varphi(u+\lambda v)=u$

leading us to the envelope representation

$\displaystyle e_{\lambda}\varphi(u+\lambda v)$
$\displaystyle=\varphi\big{(}\text{\rm Prox}_{\lambda\varphi}(u+\lambda
v)\big{)}+\frac{1}{2\lambda}\big{\|}u+\lambda v-\text{\rm
Prox}_{\lambda\varphi}(u+\lambda v)\big{\|}^{2}$
$\displaystyle=\varphi(u)+\frac{1}{2\lambda}\|u+\lambda
v-u\|^{2}=\varphi(u)+\frac{\lambda}{2}\|v\|^{2}.$

Apply further the estimate in (4.10) to get the relationships

$\displaystyle\varphi(x)+\frac{\lambda}{2}\|v\|^{2}$ $\displaystyle=$
$\displaystyle\varphi(x)+\frac{1}{2\lambda}\|x+\lambda v-x\|^{2}\geq
e_{\lambda}\varphi(x+\lambda v)$ $\displaystyle\geq$ $\displaystyle
e_{\lambda}\varphi(u+\lambda v)+\langle\nabla e_{\lambda}\varphi(u+\lambda
v),x+\lambda v-(u+\lambda v)\rangle+\frac{\sigma_{\lambda}}{2}\|x-u\|^{2}$
$\displaystyle=$ $\displaystyle\varphi(u)+\frac{\lambda}{2}\|v\|^{2}+\langle
v,x-u\rangle+\frac{\sigma_{\lambda}}{2}\|x-u\|^{2}.$

Subtracting the term $\frac{\lambda}{2}\|v\|^{2}$ from both sides above, we
arrive at (4.12) and thus complete the proof.

Note that the characterization of variational convexity and variational strong
convexity for extended-real-valued functions, which are obtained in Sections 3
and 4 via Moreau envelopes, significantly employ the prox-regularity of the
function in question while not its continuous prox-regularity, i.e., the
subdifferential continuity of the function is not assumed. In contrast, the
latter property is essential for establishing coderivative characterizations
of both variational convexity properties that are given in the next section.

##  5 Coderivative-Based Characterizations of Variational Convexity

This section is devoted to deriving complete characterizations of both
variational convexity and variational strong convexity properties of
continuously prox-regular functions via their combined and limiting second-
order subdifferentials taken from Definition 2.1.

We begin with the lemma, which provides a second-order sufficient condition
for convexity of smooth functions.

######  Lemma 5.1 (second-order condition for convexity of
$\mathcal{C}^{1}$-smooth functions).

Let $\varphi:\Omega\to{\rm I\\!R}$ be a $\mathcal{C}^{1}$-smooth function,
where $\emptyset\neq\Omega\subset{\rm I\\!R}^{n}$ be an open convex set. Then
$\varphi$ is convex on $\Omega$ if we have

$\langle z,w\rangle\geq 0\quad\text{for all
}\;z\in(\widehat{D}^{*}\nabla\varphi)(x)(w),\;x\in\Omega,\;w\in{\rm
I\\!R}^{n}.$

[Proof.] It follows from the proof of [6, Theorem 3.1].

Now we are ready to obtain the main coderivative-based second-order
characterizations of variational convexity.

######  Theorem 5.2 (second-order subdifferential characterizations of
variational convexity).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be subdifferentially
continuous at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for
$\bar{v}\in\partial\varphi(\bar{x})$. Then the following assertions are
equivalent:

(i) $\varphi$ is variationally convex at $\bar{x}$ for $\bar{v}$.

(ii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$ and there exist
neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{v}$ such that

(5.1) $\langle z,w\rangle\geq 0\;\text{
whenever}\;z\in\breve{\partial}^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

(iii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$ and there exist
neighborhoods $U$ of $\bar{x}$, and $V$ of $\bar{v}$ such that

(5.2) $\langle z,w\rangle\geq 0\;\text{ whenever
}\;z\in\partial^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

[Proof.] We start with verifying implication (i)$\Longrightarrow$(iii). As
mentioned, variational convexity in (i) yields the prox-regularity of
$\varphi$ at $\bar{x}$ for $\bar{v}$. Due to the imposed subdifferential
continuity of $\varphi$, this ensures the existence of neighborhoods $U$ of
$\bar{x}$ and $V$ of $\bar{v}$ as well as of an l.s.c. convex function $\psi$
such that $\psi\leq\varphi$ on $U$ and

(5.3) $(U\times V)\cap\mbox{\rm gph}\,\partial\varphi=(U\times V)\cap\mbox{\rm
gph}\,\partial\psi\quad\text{and }\;\varphi(x)=\psi(x)\;\text{ at the common
elements }\;(x,v).$

Picking any $(x,y)\in\mbox{\rm gph}\,\partial\varphi\cap(U\times V)$,
$w\in{\rm I\\!R}^{n}$, and $z\in\partial^{2}\varphi(x,y)(w)$ implies by (5.3)
that

$\partial^{2}\varphi(x,y)(w)=\partial^{2}\psi(x,y)(w),$

which tells us in turn that $z\in\partial^{2}\psi(x,y)(w)$. Applying now to
$\psi$ the second-order necessary condition for convexity of l.s.c. functions
from [4, Theorem 3.2], we get $\langle z,w\rangle\geq 0$ and therefore
justifies assertion (iii). Implication (iii)$\Longrightarrow$(ii) follows from
the inclusion in (2.9), valid for all $(x,y)\in\mbox{\rm
gph}\,\partial\varphi$ and $w\in{\rm I\\!R}^{n}$, which thus verifies (5.1).

It remains to verify the reverse implication (ii)$\Longrightarrow$(i). To
furnish this, observe first that the imposed prox-regularity in (ii) allows us
to suppose without loss of generality that $\varphi$ is prox-bounded. Indeed,
we can always get this property by adding to $\varphi$ the indicator function
of some compact set containing a neighborhood of $\bar{x}$. Therefore, the
properties of Moreau envelopes from Proposition 2.2 give us $\lambda_{0}>0$
such that for any $\lambda\in(0,\lambda_{0})$ there exists a convex
neighborhood $U_{\lambda}$ of $\bar{x}+\lambda\bar{v}$ on which

(5.4) $\text{\rm the Moreau envelope $e_{\lambda}\varphi$ is
$\mathcal{C}^{1,1}$ on $U_{\lambda}$}\;\text{ and }\;\nabla
e_{\lambda}\varphi(x)=\big{(}\lambda
I+(\partial\varphi)^{-1}\big{)}^{-1}(x)\;\text{ for all }\;x\in U_{\lambda}.$

Since (ii) holds, there are neighborhoods $U$ of $\bar{x}$ and $V$ of
$\bar{v}$ where (5.1) is satisfied. Fixing any $\lambda\in(0,\lambda_{0})$, it
follows from the continuity of the mappings $\nabla e_{\lambda}\varphi$ and
$I-\lambda\nabla e_{\lambda}\varphi$ around $\bar{x}+\lambda\bar{v}$ and from
$\nabla e_{\lambda}\varphi(\bar{x}+\lambda\bar{v})=\bar{v}$ with
$(I-\lambda\nabla e_{\lambda}\varphi)(\bar{x}+\lambda\bar{v})=\bar{x}$ that
there exists a convex neighborhood $\widetilde{U}\subset U_{\lambda}$ of
$\bar{x}+\lambda\bar{v}$ on which

(5.5) $(I-\lambda\nabla e_{\lambda}\varphi)(x)\times\nabla
e_{\lambda}\varphi(x)\in U\times V,\quad x\in\widetilde{U}.$

By using Lemma 5.1, let us now show that $e_{\lambda}\varphi$ is convex on
$\widetilde{U}$. Indeed, take $x\in\widetilde{U},\;u\in{\rm I\\!R}^{n}$, and
$z~{}\in~{}(\widehat{D}^{*}\nabla e_{\lambda}\varphi)(x)(u)$. It is easy to
check that $-u\in\widehat{D}^{*}(\nabla e_{\lambda}\varphi)^{-1}(\nabla
e_{\lambda}\varphi(x),x)(-z)$. Furthermore, it follows from (5.4) and the
coderivative sum rule in [30, Theorem 1.62] that

$\displaystyle\widehat{D}^{*}(\nabla e_{\lambda}\varphi)^{-1}\big{(}\nabla
e_{\lambda}\varphi(x),x\big{)}(-z)$ $\displaystyle=$
$\displaystyle\widehat{D}^{*}\big{(}\lambda
I+(\partial\varphi)^{-1}\big{)}\big{(}\nabla
e_{\lambda}\varphi(x),x\big{)}(-z)$ $\displaystyle=$ $\displaystyle-\lambda
z+\widehat{D}^{*}(\partial\varphi)^{-1}\big{(}\nabla
e_{\lambda}\varphi(x),x-\lambda\nabla e_{\lambda}\varphi(x)\big{)}(-z),$

which implies that $\lambda z-u\in\widehat{D}^{*}(\partial\varphi)^{-1}(\nabla
e_{\lambda}\varphi(x),x-\lambda\nabla e_{\lambda}\varphi(x))(-z)$. In other
words,

$z\in(\widehat{D}^{*}\partial\varphi)\big{(}x-\lambda\nabla
e_{\lambda}\varphi(x),\nabla e_{\lambda}\varphi(x)\big{)}(u-\lambda z).$

Using (5.1) and (5.5), we obtain the inequality $\langle z,u-\lambda
z\rangle\geq 0$, and so $\langle z,u\rangle\geq 0$. Therefore,

$\langle z,u\rangle\geq 0\;\mbox{ for all }\;z\in(\widehat{D}^{*}\nabla
e_{\lambda}\varphi)(x)(u),\;u\in{\rm I\\!R}^{n},\;x\in\widetilde{U}.$

By Lemma 5.1, the function $e_{\lambda}\varphi$ is convex on $\widetilde{U}$.
Finally, we apply Theorem 3.2 on the characterization of variational convexity
via Moreau envelopes, which verifies (i) and thus completes the proof of the
theorem.

As a consequence of Theorem 5.2, we arrive at the new second-order sufficient
conditions for minimizing extended-real-valued continuously prox-regular
functions.

######  Corollary 5.3 (second-order sufficient optimality conditions for
continuously prox-regular functions).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be continuously prox-
regular at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for
$0\in\partial\varphi(\bar{x})$. Then $\bar{x}$ is a local minimizer of
$\varphi$ if either one of the following conditions is satisfied:

(i) There exist neighborhoods $U$ of $\bar{x}$ and $V$ of the origin in ${\rm
I\\!R}^{n}$ such that

$\langle z,w\rangle\geq 0\;\text{ whenever
}\;z\in\breve{\partial}^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

(ii) There are neighborhoods $U$ of $\bar{x}$ and $V$ of the origin in ${\rm
I\\!R}^{n}$ such that

$\langle z,w\rangle\geq 0\;\text{ whenever
}\;z\in\partial^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

[Proof.] It follows immediately from Theorem 5.2 and Remark 2.8(i).

The next theorem provides second-order subdifferential characterizations of
variational strong convexity with a prescribed modulus for extended-real-
valued continuously prox-regular functions.

######  Theorem 5.4 (second-order characterizations of variational strong
convexity).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be subdifferentially
continuous at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for
$\bar{v}\in\partial\varphi(\bar{x})$. Then the following assertions are
equivalent:

(i) $\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$ with
modulus $\sigma>0$.

(ii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$ and there exist
neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{v}$ such that

(5.6) $\langle z,w\rangle\geq\sigma\|w\|^{2}\;\text{ whenever
}\;z\in\breve{\partial}^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

(iii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$ and there are
neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{v}$ such that

(5.7) $\langle z,w\rangle\geq\sigma\|w\|^{2}\;\text{ whenever
}\;z\in\partial^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

[Proof.] First we justify implication (i)$\Longrightarrow$(iii). Since the
prox-regularity is automatic under (i), we proceed with verifying (5.7). It
follows from Lemma 4.2 that the $\sigma$-quadratic shift
$\vartheta:=\varphi-\frac{\sigma}{2}\|\cdot-\bar{x}\|^{2}$ is variationally
convex at $\bar{x}$ for $\bar{v}$. Applying to $\vartheta$ the second-order
characterization of variational convexity from Theorem 5.2(iii), we find
neighborhoods $\widetilde{U}$ of $\bar{x}$ and $\widetilde{V}$ of $\bar{v}$
such that

(5.8) $\langle z,w\rangle\geq 0\;\text{ whenever
}\;z\in\partial^{2}\vartheta(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\vartheta\cap(\widetilde{U}\times\widetilde{V}),\;w\in{\rm
I\\!R}^{n}.$

The elementary sum rule for limiting subgradients from [31, Proposition 1.30]
yields

(5.9) $\partial\vartheta(x)=\partial\varphi(x)-\sigma(x-\bar{x})\;\text{ for
any }\;x\in\mbox{\rm dom}\,\varphi.$

Defining the affine transformation $L:{\rm I\\!R}^{n}\times{\rm
I\\!R}^{n}\to{\rm I\\!R}^{n}\times{\rm I\\!R}^{n}$ by
$L(x,y):=(x,y-\sigma(x-\bar{x}))$ for all $(x,y)\in{\rm I\\!R}^{n}\times{\rm
I\\!R}^{n}$, we find neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{v}$ such
that $L(U\times V)\subset\widetilde{U}\times\widetilde{V}$, which implies that

(5.10) $(x,y)\in U\times
V\Longrightarrow(x,y-\sigma(x-\bar{x}))\in\widetilde{U}\times\widetilde{V}.$

To verify now (5.7), pick any $(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V)$ and deduce from (5.9) and (5.10) that

(5.11) $\big{(}x,y-\sigma(x-\bar{x})\big{)}\in\mbox{\rm
gph}\,\partial\vartheta\cap(\widetilde{U}\times\widetilde{V}).$

Fix $w\in{\rm I\\!R}^{n}$ and
$z\in\partial^{2}\varphi(x,y)(w)=({D}^{*}\partial\varphi)(x,y)(w)$. It follows
from the limiting coderivative sum rule in [30, Theorem 1.62(ii)] that we have

$(D^{*}\partial\varphi)(x,y)(w)=D^{*}\partial\vartheta\big{(}x,y-\sigma(x-\bar{x})\big{)}(w)+\sigma
w,$

which tells us that $z-\sigma
w\in(D^{*}\partial\vartheta)(x,y-\sigma(x-\bar{x}))(w)=\partial^{2}\vartheta(x,y-\sigma(x-\bar{x}))(w)$.
Combining the latter inclusion with (5.8) and (5.11), we arrive at $\langle
z-\sigma w,w\rangle\geq 0$, i.e., at $\langle z,w\rangle\geq\sigma\|w\|^{2}$,
which gives us (5.7) and thus verifies the claimed implication (i)
$\Longrightarrow$(iii). The one in (iii)$\Longrightarrow$(ii) follows from the
inclusion in (2.9).

To complete the proof of the theorem, it remains to justify implication
(ii)$\Longrightarrow$(i). Suppose that $\varphi$ is prox-regular at $\bar{x}$
for $\bar{v}$ and then find neighborhoods $U$ of $\bar{x}$ and $V$ of
$\bar{v}$ such that (5.6) is satisfied. Our immediate goal is to check that
the function $\vartheta:=\varphi-\frac{\sigma}{2}\|\cdot-\bar{x}\|^{2}$ is
variationally convex at $\bar{x}$ for $\bar{v}$. To furnish this, consider
another affine transformation $L_{1}(x,y):=(x,y+\sigma(x-\bar{x}))$ on ${\rm
I\\!R}^{n}\times{\rm I\\!R}^{n}$ for which there are neighborhoods
$\widetilde{U}$ of $\bar{x}$ and $\widetilde{V}$ of $\bar{v}$ with
$L_{1}(\widetilde{U}\times\widetilde{V})\subset U\times V$. It follows from
(5.9) that

(5.12) $(x,y)\in\mbox{\rm
gph}\,\partial\vartheta\cap(\widetilde{U}\times\widetilde{V})\Longrightarrow\big{(}x,y+\sigma(x-\bar{x})\big{)}\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V).$

Take $(x,y)\in\mbox{\rm
gph}\,\partial\vartheta\cap(\widetilde{U}\times\widetilde{V})$, $w\in{\rm
I\\!R}^{n}$, and $z\in(\widehat{D}^{*}\partial\vartheta)(x,y)(w)$. By using
the regular coderivative sum rule from [30, Theorem 1.62(i)], we get

$(\widehat{D}^{*}\partial\vartheta)(x,y)(w)=\widehat{D}^{*}\partial\varphi\big{(}x,y+\sigma(x-\bar{x})\big{)}(w)-\sigma
w,$

which ensures that $z+\sigma
w\in(\widehat{D}^{*}\partial\varphi)(x,y+\sigma(x-\bar{x}))(w)$. It follows
from (5.6) and (5.12) that $\langle z+\sigma w,w\rangle\geq\sigma\|w\|^{2}$,
i.e., $\langle z,w\rangle\geq 0$. Applying the second-order subdifferential
characterization of variational convexity from Theorem 5.2(ii) tells us that
$\vartheta$ is variationally convex at $\bar{x}$ for $\bar{v}$. To deduce from
here the strong variational convexity of $\varphi$ at $\bar{x}$ for $\bar{v}$,
we just employ Lemma 4.2 and therefore complete the proof of the theorem.

Note that the obtained characterizations of variational convexity and
variational strong convexity expressed in terms of the limiting second-order
subdifferential (2.7) are more preferable in comparison with their
counterparts given via the combined second-order subdifferential (2.8). This
is due the robustness and well-developed calculus rules for the former
construction that is not the case for the latter one. Nevertheless, the
characterizations derived in Theorems 5.2 and 5.4 even in terms of (2.7)
involve neighborhoods of the reference point. It is definitely desired to
establish pointbased characterizations of these properties expressed via (2.7)
just at the point in question.

We now obtain such a pointbased characterization for the variational strong
convexity property of continuously prox-regular functions. Establishing
results of this type for (nonstrong) variational convexity is an open
question.

To proceed, recall the following lemma taken from [8, Proposition 4.6].

######  Lemma 5.5 (pointbased second-order sufficient condition for local
strong convexity of functions from class $\mathcal{C}^{1,1}$).

Let $\varphi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ be a function of class
$\mathcal{C}^{1,1}$ around $\bar{x}\in{\rm I\\!R}^{n}$. Then $\varphi$ is
locally strongly convex around $\bar{x}$ if we have the positive-definiteness
condition

$\langle z,w\rangle>0\;\text{ for all
}\;z\in({D}^{*}\nabla\varphi)(\bar{x})(w),\;w\in{\rm
I\\!R}^{n}\setminus\\{0\\}.$

Here is a pointbased characterization of variational strong convexity for
subdifferentially continuous functions.

######  Theorem 5.6 (pointbased second-order subdifferential characterization
of variational strong convexity).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be a subdifferentially
continuous function at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for
$\bar{v}\in\partial\varphi(\bar{x})$. Then the following assertions are
equivalent:

(i) $\varphi$ is variationally strongly convex at $\bar{x}$ for $\bar{v}$.

(ii) $\varphi$ is prox-regular at $\bar{x}$ for $\bar{v}$ and the second-order
subdifferential (2.7) is positive-definite in the sense that

(5.13) $\langle z,w\rangle>0\;\text{ whenever
}\;z\in\partial^{2}\varphi(\bar{x},\bar{v})(w),\;w\neq 0.$

[Proof.] Implication (i)$\Longrightarrow$(ii) follows from Theorem 5.4. To
verify the converse implication (ii)$\Longrightarrow$(i), observe as above
that the prox-regularity of $\varphi$ imposed in (ii) ensures without loss of
generality that $\varphi$ is prox-bounded. By the properties of Moreau
envelopes listed in Proposition 2.2, we find $\lambda_{0}>0$ such that for any
$\lambda\in(0,\lambda_{0})$ there exists a convex neighborhood $U_{\lambda}$
of $\bar{x}+\lambda\bar{v}$ on which

$\text{\rm the Moreau envelope $e_{\lambda}\varphi$ is $\mathcal{C}^{1,1}$ on
$U_{\lambda}$}\quad\text{and }\;\nabla e_{\lambda}\varphi(x)=\big{(}\lambda
I+(\partial\varphi)^{-1}\big{)}^{-1}(x)\quad\text{for all }\;x\in
U_{\lambda}.$

Fix any $\lambda\in(0,\lambda_{0})$ and show that $e_{\lambda}\varphi$ is
locally strongly convex around $\bar{x}+\lambda\bar{v}$. Indeed, take
$z\in({D}^{*}\nabla e_{\lambda}\varphi)(\bar{x}+\lambda\bar{v})(u)$ with
$u\neq 0$. It follows from [21, Lemma 6.4] that
$z\in\partial^{2}\varphi(\bar{x},\bar{v})(u-\lambda z)$. If $u-\lambda z\neq
0$, then we get from (5.13) that $\langle z,u-\lambda z\rangle>0$, i.e.,
$\langle z,u\rangle>\lambda\|z\|^{2}>0$. Otherwise, this tells us that
$u=\lambda z$, and thus

$\langle z,u\rangle=\frac{1}{\lambda}\langle
u,u\rangle=\frac{1}{\lambda}\|u\|^{2}>0.$

Therefore, we always have the coderivative positive-definiteness for the
${\cal C}^{1,1}$ Moreau envelope:

$\langle z,u\rangle>0\;\mbox{ for all }\;z\in({D}^{*}\nabla
e_{\lambda}\varphi)(\bar{x}+\lambda\bar{v})(u),\;u\neq 0.$

This ensures by Lemma 5.5 that $e_{\lambda}\varphi$ is locally strongly convex
around $\bar{x}+\lambda\bar{v}$. Employing the characterization of Theorem 4.5
concludes that $\varphi$ is variationally strongly convex at $\bar{x}$ for
$\bar{v}$, and thus we complete the proof.

As a consequence of the obtained results, we arrive to the following second-
order subdifferential characterizations of tilt-stable minimizers, with a
given modulus, for extended-real-valued continuously prox-regular functions.

######  Corollary 5.7 (second-order characterizations of tilt stability for
continuously prox-regular functions).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be continuously prox-
regular at $\bar{x}\in\mbox{\rm dom}\,\varphi$ for
$0\in\partial\varphi(\bar{x})$. Then we have the equivalences:

(i) $\bar{x}$ is a tilt-stable local minimizer with modulus $\kappa>0$.

(ii) There exist neighborhoods $U$ of $\bar{x}$ and $V$ of the origin in ${\rm
I\\!R}^{n}$ such that

$\langle z,w\rangle\geq\frac{1}{\kappa}\|w\|^{2}\;\text{ whenever
}\;z\in\breve{\partial}^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

(iii) There exist neighborhoods $U$ of $\bar{x}$ and $V$ of the origin in
${\rm I\\!R}^{n}$ such that

$\langle z,w\rangle\geq\frac{1}{\kappa}\|w\|^{2}\;\text{ whenever
}\;z\in\partial^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n}.$

Furthermore, the fulfillment of (i) with some modulus is equivalent to the
pointbased positive-definiteness condition

(5.14) $\langle z,w\rangle>0\;\text{ whenever
}\;z\in\partial^{2}\varphi(\bar{x},0)(w),\;w\neq 0.$

[Proof.] The given characterizations follow directly from Theorems 5.4, 5.6
and Proposition 2.9.

######  Remark 5.8 (discussions on characterizing tilt-stability via second-
order subdifferentials).

The first characterization of tilt-stable minimizers of continuously prox-
regular functions on ${\rm I\\!R}^{n}$ was obtained in the pointwise second-
order subdifferential form (5.14) by Poliquin and Rockafellar [46, Theorem
1.3] without involving moduli. The quantitative neighborhood characterization
of tilt stability in (ii) via the combined second-order subdifferential was
established by Mordukhovich and Nghia in [33, Theorem 4.3] in Hilbert spaces.
Here we recover the known results including the equivalence between (i) and
(ii) and the pointbased characterization of tilt stability by using the
obtained new characterizations of variational convexity. To the best of our
knowledge, the quantitative characterizations in (iii) via the limiting
second-order subdifferential has not been observed earlier in the literature.
Note that our proof of the second-order subdifferential characterizations of
tilt-stable minimizers in Corollary 5.7 via variational convexity is
significantly different from those previously used.

We conclude this section with the following remark on the novel SCD approach
to tilt stability and related issues developed of Gfrerer and Outrata in their
recent paper [16].

######  Remark 5.9 (strong variational convexity and tilt stability via SCD
mappings).

In [16], Gfrerer and Outrata introduced new generalized derivatives for set-
valued mappings called SCD mappings (subspace containing derivative mappings).
They derived for such mappings some calculus rules and revealed a number of
interesting connections in variational analysis. SCD mappings particularly
contain subdifferentials of prox-regular and subdifferentially continuous
functions [16, Proposition 3.26]. In particular, the SCD connection to
Rockafellar’s quadratic bundles (2.10) was established and a comparison with
the second-order subdifferentials was provided in [16, Example 3.29].
Characterizations of tilt stability and strong metric regularity were also
derived in Section 7 of [16]. The equivalent descriptions of variational
strong convexity given in Proposition 2.9 allow us to obtain the corresponding
characterizations of variational strong convexity via SCD mappings.

##  6 Variational Sufficiency in Composite Optimization

As discussed in Remark 2.8, variational convexity and variational strong
convexity of an l.s.c. function $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm
I\\!R}}$ imply the local optimality and tilt-stability of a local minimizer,
respectively. However, the reverse implications fail. The properties of
variational convexity and variational strong convexity of minimizing cost
functions at stationary points were labeled by Rockafellar [49] as variational
sufficiency and strong variational sufficiency, where the motivations came
from applications to proximal point algorithms. Further applications of these
notions and ideas to extended augmented Lagrangian methods in rather general
frameworks of optimization were given in the most recent papers [50, 51].

The main goal of this section is to investigate and characterize both of these
properties in structured frameworks of composite constrained optimization by
using the generalized differential characterizations of variational convexity
and variational strong convexity established in Sections 3 and 4 being married
to second-order calculus rules developed for the basic second-order
subdifferential (2.7).

We start with the definitions of variational sufficiency and strong
variational sufficiency in the general unconstrained format of minimizing
extended-real-valued functions.

######  Definition 6.1 (variational sufficiency and strong variational
sufficiency for local optimality).

Given an extended-real-valued function $\varphi:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$, consider the unconstrained optimization
problem:

(6.1) $\mbox{\rm minimize}\quad\varphi(x)\quad\text{subject to }\;x\in{\rm
I\\!R}^{n}.$

It is said that the variational sufficient condition for local optimality in
(6.1) holds at $\bar{x}$ if $\varphi$ is variationally convex at $\bar{x}$ for
$0\in\partial\varphi(\bar{x})$. If $\varphi$ is variationally strongly convex
at $\bar{x}$ for $0$ with modulus $\sigma>0$, then we say that the strong
variational sufficient condition for local optimality at $\bar{x}$ holds with
modulus $\sigma$.

Here we consider the class of composite optimization problems given by:

(6.2) $\mbox{\rm
minimize}\;\varphi(x):=\varphi_{0}(x)+\psi\big{(}g(x)\big{)}\quad\text{subject
to }\;x\in{\rm I\\!R}^{n},$

where $\psi:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ is an extended-real-
valued l.s.c. function, $\varphi_{0}:{\rm I\\!R}^{n}\to{\rm I\\!R}$ is a
$\mathcal{C}^{2}$-smooth function, and $g$ is a $\mathcal{C}^{2}$-smooth
mapping from ${\rm I\\!R}^{n}$ to ${\rm I\\!R}^{m}$. These are our standing
assumptions in this section unless otherwise stated. As mentioned, the
composite format (6.2) implicitly incorporates the constraint
$g(x)\in\mbox{\rm dom}\,\psi$. In what follows, we aim at deriving second-
order characterizations of variational sufficiency and strong variational
sufficiency for local optimality in (6.2) expressed in terms of the given data
of this problem.

To proceed, for each $(x,v)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{n}$ define the
set of multipliers

(6.3) $\Lambda(x,v):=\big{\\{}y\in{\rm
I\\!R}^{m}\;\big{|}\;v=\nabla\varphi_{0}(x)+\nabla
g(x)^{*}y,\;y\in\partial\psi\big{(}g(x)\big{)}\big{\\}}.$

The first theorem imposes the full rank assumption on the Jacobian matrix
$\nabla g(\bar{x})$ at the point in question.

######  Theorem 6.2 (variational and strong variational sufficiency for
composite problems with full ranks of Jacobians).

Let $\bar{x}\in{\rm I\\!R}^{n}$ be a stationary point of the composite
optimization problem (6.2) at which $\mbox{\rm rank}\,\nabla g(\bar{x})=m$ and
hence there exists a unique vector $\bar{y}\in{\rm I\\!R}^{m}$ with

(6.4) $\nabla\varphi_{0}(\bar{x})+\nabla g(\bar{x})^{*}\bar{y}=0\;\mbox{ and
}\;\bar{y}\in\partial\psi\big{(}g(\bar{x})\big{)}.$

Suppose in addition that $\psi$ is subdifferentially continuous at
$g(\bar{x})$ for $\bar{y}$. Then we have the following assertions:

(i) The variational sufficient condition for local optimality in (6.2) holds
at $\bar{x}$ if and only if $\psi$ is prox-regular at $g(\bar{x})$ for
$\bar{y}$ and there exist neighborhoods $U$ of $\bar{x}$ and $V$ of $0$ such
that

(6.5) $\langle\nabla^{2}\varphi_{0}(x)w,w\rangle+\langle\nabla^{2}\langle
y,g\rangle(x)w,w\rangle+\langle u,\nabla g(x)w\rangle\geq 0$

for all $x\in U$, $v\in V$, $y\in\Lambda(x,v)$,
$u\in\partial^{2}\psi(g(x),y)(\nabla g(x)w)$, $w\in{\rm I\\!R}^{n}$, where
$\Lambda(x,v)$ is a singleton in this case.

(ii) The strong variational sufficient condition for local optimality in (6.2)
holds at $\bar{x}$ with modulus $\sigma>0$ if and only if $\psi$ is prox-
regular at $g(\bar{x})$ for $\bar{y}$ and there exist neighborhoods $U$ of
$\bar{x}$ and $V$ of $0$ such that

(6.6) $\langle\nabla^{2}\varphi_{0}(x)w,w\rangle+\langle\nabla^{2}\langle
y,g\rangle(x)w,w\rangle+\langle u,\nabla g(x)w\rangle\geq\sigma\|w\|^{2}$

for all $x\in U$, $v\in V$, $y\in\Lambda(x,v)$,
$u\in\partial^{2}\psi(g(x),y)(\nabla g(x)w)$, $w\in{\rm I\\!R}^{n}$, where
$\Lambda(x,v)$ is a singleton in this case.

Furthermore, the strong variational sufficiency in (ii) with some modulus
$\sigma>0$ is equivalent to the prox-regularity of $\psi$ at $g(\bar{x})$ for
$\bar{y}$ together with the fulfillment of the pointbased condition

(6.7)
$\langle\nabla^{2}\varphi_{0}(\bar{x})w,w\rangle+\langle\nabla^{2}\langle\bar{y},g\rangle(\bar{x})w,w\rangle+\langle
u,\nabla g(\bar{x})w\rangle>0$

whenever $u\in\partial^{2}\psi\big{(}g(\bar{x}),\bar{y}\big{)}\big{(}\nabla
g(\bar{x})w\big{)}$ and $w\neq 0$.

[Proof.] Note that the full rank assumption $\mbox{\rm rank}\,\nabla
g(\bar{x})=m$ implies that there exists $\varepsilon>0$ such that $\mbox{\rm
rank}\,\nabla g(x)=m$ for all $x\in\mathbb{B}_{\varepsilon}(\bar{x})$. Thus it
follows from the first-order subdifferential sum and chain rules in [31,
Proposition 1.10 and Exercise 1.72] that we have the equivalences

(6.8) $v\in\partial\varphi(x)\iff v\in\nabla\varphi_{0}(x)+\nabla
g(x)^{*}\partial\psi\big{(}g(x)\big{)}\iff\Lambda(x,v)\;\text{ is a
singleton}$

for all $x\in\mathbb{B}_{\varepsilon}(\bar{x})$, which verifies the existence
of a unique $\bar{y}\in{\rm I\\!R}^{m}$ satisfying (6.4).

Next we observe that it follows from (6.8) and the definitions of prox-
regularity and subdifferential continuity in Section 2 that the prox-
regularity and subdifferential continuity properties of the function $\varphi$
an (6.2) at $\bar{x}$ for $0$ are equivalent to the corresponding properties
of $\psi$ at $g(\bar{x})$ for $\bar{y}$. Furthermore, Remark 2.4(iii) tells us
that the variational convexity of a function yields its prox-regularity at the
reference point. Therefore, we only need to verify that the variational
convexity as well as the variational strong convexity of $\varphi$ at
$\bar{x}$ for $0$ with and without modulus $\sigma>0$ hold if and only if the
corresponding conditions (6.5), (6.6), and (6.7) are satisfied.

To prove all of this, we employ the second-order subdifferential sum rule from
[30, Proposition 1.121] and the second-order subdifferential chain rule from
[30, Theorem 1.127] to the function $\varphi$ in (6.2), which tell us that

$\displaystyle\partial^{2}\varphi(x,v)(w)$
$\displaystyle=\nabla^{2}\varphi_{0}(x)w+\partial^{2}(\psi\circ
g)\big{(}x,v-\nabla\varphi_{0}(x)\big{)}(w)$
$\displaystyle=\nabla^{2}\varphi_{0}(x)w+\nabla^{2}\langle
y,g\rangle(x)w+\nabla
g(x)^{*}\partial^{2}\psi\big{(}g(x),y\big{)}\big{(}\nabla g(x)w\big{)}$

for each $x\in\mathbb{B}_{\varepsilon}(\bar{x})$, $v\in\partial\varphi(x)$,
$w\in{\rm I\\!R}^{n}$, and the unique vector $y$ from $\Lambda(x,v)$. By the
obtained representation of $\partial^{2}\varphi(x,v)$, it follows that the
conditions in (6.5) and (6.6) are equivalent to the existence of neighborhoods
$U$ of $\bar{x}$ and $V$ of $0$ such that we have the estimates

(6.9) $\langle z,w\rangle\geq 0\;\text{ for all
}\;z\in\partial^{2}\varphi(x,v)(w),\;(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n},$ (6.10) $\langle
z,w\rangle\geq\sigma\|w\|^{2}\;\text{ for all
}\;z\in\partial^{2}\varphi(x,v)(w),\;(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V),\;w\in{\rm I\\!R}^{n},$

respectively. In the same way, (6.7) reduces to the positive-definiteness
condition

(6.11) $\langle z,w\rangle>0\;\text{ for all
}\;z\in\partial^{2}\varphi(\bar{x},0)(w),\;w\neq 0.$

Finally, we deduce from the second-order subdifferential characterization in
Theorems 5.2, 5.4, and 5.6 that the conditions in (6.9), (6.10), and (6.11)
are equivalent to the variational convexity of $\varphi$ and the variational
strong convexity of $\varphi$ at $\bar{x}$ for $0$ with and without modulus
$\sigma$, respectively. This completes the proof of the theorem.

Our further goals are deriving effective conditions ensuring the fulfillment
of variational sufficiency and strong variational sufficiency for local
optimality in the composite model (6.2) and also characterizing these
properties without imposing the full rank assumption on the Jacobian $\nabla
g(\bar{x})$. To proceed in this direction requires dealing with particular
classes of compositions in (6.2), which cover a large territory in variational
analysis and optimization.

Following [52], recall that an l.s.c. function $\theta:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is strongly amenable at $\bar{x}$ if
there exists neighborhood $U$ of $\bar{x}$ on which $\theta$ can be
represented in the composition form $\theta=\psi\circ g$ with a
$\mathcal{C}^{2}$-smooth mapping $g\colon U\to{\rm I\\!R}^{m}$ and a proper
l.s.c. convex function $\psi:{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ such
that the following first-order qualification condition holds:

(6.12) $\partial^{\infty}\psi(\bar{z})\cap\mbox{\rm ker}\,\nabla
g(\bar{x})^{*}=\\{0\\}\;\mbox{ with }\;\bar{z}:=g(\bar{x})$

If in addition $\psi$ is piecewise linear-quadratic as in [52], then $\theta$
is called fully amenable at $\bar{x}$. Note that (6.12) is automatically
satisfied if either $\psi$ is locally Lipschitzian around $\bar{z}$, or
$\nabla g(\bar{x})$ is of full rank, while neither of these conditions is
required for the fulfillment of (6.12).

We are also going to use the second-order qualification condition (SOQC) from
[42] for problem (6.2) at $\bar{x}$, which is formulated as follows:

(6.13) $\partial^{2}\psi(\bar{z},\bar{y})(0)\cap\mbox{\rm ker}\,\nabla
g(\bar{x})^{*}=\\{0\\}\;\text{ with
}\;\bar{y}\in\partial\psi\big{(}\bar{z}\big{)}\;\text{ and
}\;\bar{z}:=g(\bar{x}).$

If $\psi$ is convex, then the following easy relationship between the
qualification conditions (6.12) and (6.13) holds.

######  Proposition 6.3 (relationships between the first- and second-order
qualification conditions).

Let $\psi\colon{\rm I\\!R}^{m}\to\overline{{\rm I\\!R}}$ be a convex function.
Then for each $\bar{z}\in{\rm I\\!R}^{m}$ and
$\bar{y}\in\partial\psi(\bar{z})$, we have the inclusions:

(6.14)
$\partial^{\infty}\psi(\bar{z})\subset\breve{\partial}^{2}\psi(\bar{z},\bar{y})(0)\subset{\partial}^{2}\psi(\bar{z},\bar{y})(0).$

Consequently, the second-order qualification condition (6.13) yields the
first-order qualification condition (6.12).

[Proof.] Pick $v\in\partial^{\infty}\psi(z)$ and deduced from the convexity of
$\psi$ and [52, Proposition 8.12] that

$\langle v,z-\bar{z}\rangle\leq 0\quad\text{for all }\;z\in\mbox{\rm
dom}\,\psi,$

which immediately implies that

$\underset{(z,y)\overset{\text{\rm
gph}\,\partial\psi}{\to}(\bar{z},\bar{y})}{\limsup}\frac{\langle(v,0),(z,y)-(\bar{z},\bar{y})\rangle}{\|z-\bar{z}\|+\|y-\bar{y}\|}\leq
0,$

and thus $(v,0)\in\widehat{N}_{\text{\rm
gph}\,\partial\psi}(\bar{z},\bar{y})$, i.e.,
$v\in\breve{\partial}^{2}\psi(\bar{z},\bar{y})(0)$. This justifies the first
inclusion in (6.14). The second inclusion therein is obvious, and so (6.14) is
verified. Implication (6.13)$\Longrightarrow$(6.12) clearly follows from
(6.14).

Next we verify the important robustness property of SOQC for strongly amenable
compositions.

######  Lemma 6.4 (robustness of the second-order qualification condition).

Let $\bar{x}\in{\rm I\\!R}^{n}$ be a stationary point of the composite
optimization problem (6.2) under the standing assumption on
$\varphi_{0},\psi$, and $g$. Suppose in addition that $\psi$ and $g$ be
mappings from the composite representation of a strongly amenable function at
$\bar{x}$ and that the second-order qualification condition (6.13) is
satisfied at $\bar{x}$. Then there are neighborhoods $\mathcal{X}$ of
$\bar{x}$ and $\mathcal{O}$ of $0$ with

(6.15) $\partial^{2}\psi\big{(}g(x),y\big{)}(0)\cap\mbox{\rm ker}\,\nabla
g(x)^{*}=\\{0\\}\;\text{ whenever
}\;x\in\mathcal{X},\;y\in\partial\psi\big{(}g(x)\big{)},\;\mbox{ and
}\;\nabla\varphi_{0}(x)+\nabla g(x)^{*}y\in\mathcal{O}.$

[Proof.] Suppose that (6.15) fails and then find sequences $x_{k}\to\bar{x}$,
$y_{k}\in\partial\psi(g(x_{k}))$ with

(6.16) $\lim_{k\to\infty}\big{[}\nabla\varphi_{0}(x_{k})+\nabla
g(x_{k})^{*}y_{k}\big{]}=0,$ (6.17) $0\neq
z_{k}\in\partial^{2}\psi\big{(}g(x^{k}),y^{k}\big{)}(0)\cap\mbox{\rm
ker}\,\nabla g(x^{k})^{*}\;\text{for all }\ k\in\\\ N.$

If $\\{y_{k}\\}$ bounded, suppose without loss of generality that
$y_{k}\to\bar{y}$ as $k\to\infty$. Put $\widetilde{z_{k}}:=z_{k}/\|z_{k}\|$
for all $k\in\\\ N$. Then $\|\widetilde{z_{k}}\|=1$, and we get without loss
of generality that $\widetilde{z_{k}}\to\widetilde{z}$ as $k\to\infty$ with
$\|\widetilde{z}\|=1$. It follows from (6.17) that

$\widetilde{z_{k}}=\displaystyle\frac{z_{k}}{\|z_{k}\|}\in\partial^{2}\psi\big{(}g(x^{k}),y^{k}\big{)}(0)\cap\mbox{\rm
ker}\,\nabla g(x^{k})^{*}\;\text{ for all }\;k\in\\\ N,$

and hence
$\widetilde{z}\in\partial^{2}\psi(g(\bar{x}),\bar{y})(0)\cap\mbox{\rm
ker}\,\nabla g(\bar{x})^{*}$. This yields $\widetilde{z}=0$ due to (6.13), a
contradiction.

If $\\{y_{k}\\}$ is not bounded, we suppose without loss of generality that
$\|y_{k}\|\to\infty$ as $k\to\infty$ and define
$\widetilde{y_{k}}:=y_{k}/\|y_{k}\|$ for all $k\in{\rm I\\!N}$. Then
$\|\widetilde{y_{k}}\|=1$, and thus get again without loss of generality that
$\widetilde{y_{k}}\to\widetilde{y}$ as $k\to\infty$ with
$\|\widetilde{y}\|=1$. It follows from (6.16) that $\nabla
g(\bar{x})^{*}\widetilde{y}=0$. To show next that
$\widetilde{y}\in\partial^{\infty}\psi(g(\bar{x}))$, we recall that
$y_{k}\in\partial\psi(g(x_{k}))$ and deduce from the convexity of $\psi$
together with [52, Proposition 8.12] that

$\psi(z)\geq\psi\big{(}g(x_{k})\big{)}+\langle y_{k},z-g(x_{k})\rangle\;\text{
for all }\;z\in{\rm I\\!R}^{m}\;\mbox{ and }\;k\in{\rm I\\!N},$

which implies in turn the estimate

$\langle\widetilde{y_{k}},z-g(x_{k})\rangle\leq\frac{\psi(z)-\psi\big{(}g(x_{k})\big{)}}{\|y_{k}\|}\;\mbox{
as }\;z\in{\rm I\\!R}^{m},\;k\in{\rm I\\!N}.$

Thus we have for each $z\in\mbox{\rm dom}\,\psi$ that

(6.18)
$\langle\widetilde{y},z-g(\bar{x})\rangle=\lim_{k\to\infty}\langle\widetilde{y_{k}},z-g(x_{k})\rangle\leq\limsup_{k\to\infty}\frac{\psi(z)-\psi\big{(}g(x_{k})\big{)}}{\|y_{k}\|}.$

Remembering that $\psi$ is l.s.c. leads us to the conditions

(6.19)
$\limsup_{k\to\infty}\big{(}-\psi(g(x_{k}))\big{)}=-\liminf_{k\to\infty}\psi\big{(}g(x_{k})\big{)}\leq-\psi\big{(}g(\bar{x})\big{)}.$

Combining (6.18) and (6.19) with $\psi(z)<\infty$ and $1/\|y_{k}\|\to 0$ as
$k\to\infty$, we conclude that $\langle\widetilde{y},z-g(\bar{x})\rangle\leq
0$ for all $z\in\mbox{\rm dom}\,\psi$. This tells us that
$\widetilde{y}\in\partial^{\infty}\psi(g(\bar{x}))$ and hence
$\widetilde{y}\in\partial^{\infty}\psi(g(\bar{x}))\cap\mbox{\rm ker}\,\nabla
g(\bar{x})^{*}$. By the strong amenability of $\psi\circ g$, the first-order
qualification condition (6.12) is satisfied, and thus $\widetilde{y}=0$. This
is a contradiction, which completes the proof of the lemma.

Now we are ready to obtain efficient conditions that ensure variational and
strong variational sufficiency for composite optimization problems (6.2)
without the full rank assumption. These conditions address the general class
of strongly amenable compositions in (6.2).

######  Theorem 6.5 (variational and strong variational sufficiency for local
optimality with strongly amenable compositions).

Let $\bar{x}\in{\rm I\\!R}^{n}$ be a stationary point of the composite
optimization problem (6.2) under the standing assumption on
$\varphi_{0},\psi$, and $g$. Suppose in addition that $\psi$ and $g$ be
mappings from the composite representation of a strongly amenable function at
$\bar{x}$ and that the second-order qualification condition (6.13) is
satisfied at $\bar{x}$. Then we have the following assertions:

(i) The variational sufficiency for local optimality in (6.2) holds at
$\bar{x}$ if there exist neighborhoods $U$ of $\bar{x}$ and $V$ of $0$ such
that (6.5) is satisfied for all $x\in U$, $v\in V$, $y\in\Lambda(x,v)$,
$u\in\partial^{2}\psi(g(x),y)(\nabla g(x)w)$, and $w\in{\rm I\\!R}^{n}$.

(ii) The strong variational sufficiency for local optimality in (6.2) holds at
$\bar{x}$ with modulus $\sigma>0$ if there exist neighborhoods $U$ of
$\bar{x}$ and $V$ of $0$ such that the neighborhood condition (6.6) is
satisfied for all $x\in U$, $v\in V$, $y\in\Lambda(x,v)$,
$u\in\partial^{2}\psi(g(x),y)(\nabla g(x)w)$, and $w\in{\rm I\\!R}^{n}$.

(iii) The strong variational sufficient condition for local optimality in
(6.2) holds at $\bar{x}$ if the pointbased condition (6.7) is satisfied for
any $\bar{y}\in\Lambda(\bar{x},0)$.

[Proof.] Note that the first-order qualification condition (6.12) is clearly
robust with respect of small perturbations of the reference point, which means
that there exists $\varepsilon>0$ such that

$\partial^{\infty}\psi\big{(}g(x)\big{)}\cap\mbox{\rm ker}\,\nabla
g(x)^{*}=\\{0\\}\;\text{ for all}\;x\in\mathbb{B}_{\varepsilon}(\bar{x}).$

Thus we can apply the aforementioned subdifferential sum rule and then the
chain rule from [31, Theorem 4.5] to the (lower regular) strongly amenable
composition $\psi\circ g$ and get for all
$x\in\mathbb{B}_{\varepsilon}(\bar{x})$ and $w\in{\rm I\\!R}^{n}$ the
equivalences

$v\in\partial\varphi(x)\iff v\in\nabla\varphi_{0}(x)+\nabla
g(x)^{*}\partial\psi\big{(}g(x)\big{)}\iff\Lambda(x,v)\neq\emptyset.$

Using Lemma 6.4, we find neighborhoods $\mathcal{X}$ of $\bar{x}$ and
$\mathcal{O}$ of $0$ such that (6.15) holds. Since the strong amenability
assumption on the composition $\psi\circ g$ yields its continuous prox-
regularity at any point $x$ near $\bar{x}$ by [52, Proposition 13.32], this
property also holds for the cost function $\varphi$ in (6.2). The second-order
subdifferential chain rule for strongly amenable functions taken from [30,
Corollary 3.76] tells us that for each $x$ near $\bar{x}$, each
$v\in\partial\varphi(x)\cap\mathcal{O}$, and each $w\in{\rm I\\!R}^{n}$ we
have

$\partial^{2}(\psi\circ
g)\big{(}x,v-\nabla\varphi_{0}(x)\big{)}(w)\subset\bigcup_{y\in\Lambda(x,v)}\left[\nabla^{2}\langle
y,g\rangle(x)w+\nabla
g(x)^{*}\partial^{2}\psi\big{(}g(x),y\big{)}\big{(}\nabla
g(x)w\big{)}\right].$

Combining this inclusion with the second-order subdifferential sum rule from
[30, Proposition 1.121] gives us

$\displaystyle\partial^{2}\varphi(x,v)(w)$
$\displaystyle=\nabla^{2}\varphi_{0}(x)w+\partial^{2}(\psi\circ
g)\big{(}x,v-\nabla\varphi_{0}(x)\big{)}(w)$ (6.20)
$\displaystyle\subset\bigcup_{y\in\Lambda(x,v)}\left[\nabla^{2}\varphi_{0}(x)w+\nabla^{2}\langle
y,g\rangle(x)w+\nabla
g(x)^{*}\partial^{2}\psi\big{(}g(x),y\big{)}\big{(}\nabla g(x)w\big{)}\right]$

for all $w\in{\rm I\\!R}^{n}$, $x$ near $\bar{x}$, and
$v\in\partial\varphi(x)\cap\mathcal{O}$. It follows from the upper estimates
in (6) that conditions (6.5) and (6.6) ensure the existence of neighborhoods
$U$ of $\bar{x}$ and $V$ of $0$ on which we have (6.9) and (6.10),
respectively. Likewise, the pointbased condition (6.7) yields (6.11). Applying
finally Theorems 5.2, 5.4 and 5.6 verifies, respectively, the fulfillment of
assertions (i), (ii), and (iii) of this theorem.

Note that the second-order conditions obtained in Theorem 6.5 imply the
variational sufficiency and strong variational sufficiency for local
optimality in (6.2) while not characterize them. The next theorem reveals
additional assumptions on the problem data that ensure complete
characterizations of these properties in composite optimization. We are
dealing below with two crucial subclasses of fully amenable compositions
$\psi\circ g$ in (6.2). The first subclass is generated by extended-real-
valued piecewise linear functions $\psi$ in the sense of [52, Definition
2.47]. The second subclass is formed by the functions $\psi\colon{\rm
I\\!R}^{m}\to\overline{{\rm I\\!R}}$ defined as

(6.21) $\psi(z):=\sup_{v\in P}\bigg{\\{}\langle
v,z\rangle-\frac{1}{2}\big{\langle}Qv,v\big{\rangle}\bigg{\\}},$

where $P\subset{\rm I\\!R}^{m}$ is a nonempty polyhedral set, and where
$Q\in{\rm I\\!R}^{m\times m}$ is a symmetric positive-semidefinite matrix.
Functions of this type appear in problems of extended linear-quadratic
programming; see [52]. To deal with class (6.21), recall that a mapping
$f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ is open around $\bar{x}$ if for any
neighborhood $U$ of $\bar{x}$ there exists a neighborhood $V$ of $f(\bar{x})$
such that $V\subset f(U)$. Here are the aforementioned characterizations of
variational and strong variational sufficiency for local optimality in (6.2),
which have the same form as in Theorem 6.2 (including the uniqueness of
multipliers) without imposing the full rank assumption.

######  Theorem 6.6 (characterizations of variational and strong variational
sufficiency in composite fully amenable optimization).

In addition to the assumptions of Theorem 6.5, suppose that

(a) either $\psi$ is piecewise linear,

(b) or $\psi$ is of class (6.21), $Q$ is positive-definite, and the inner
mapping $g$ is open around $\bar{x}$.
Then all the three characterizations (i)–(iii) of Theorem 6.2 hold.

[Proof.] We proceed as in the proof of Theorem 6.5 by observing that the
additional assumptions imposed either in (a), or in (b) of this theorem ensure
that the inclusion in (6) holds as equality with $\Lambda(x,w)$ being a
singleton. This is due to the second-order subdifferential chain rules of the
equality type derived under (a) and (b) in [42, Theorem 4.3] and [42, Theorem
4.5], respectively.

We now compare our second-order subdifferential approach to variational and
strong variational sufficiency for local optimality in composite optimization
(6.2) with Rockafellar’s developments in the very recent paper [50] to
characterize strong variational sufficiency in (6.2) via quadratic bundles
defined in (2.10).

######  Remark 6.7 (strong variational sufficiency via augmented Lagrangians
and quadratic bundles).

Rockafellar’s approach [50] to variational and strong variational sufficiency
for local optimality in (6.2) with the l.s.c. convex function $\psi$ is based
on exploring a certain “hidden convexity” (of a local convex-concave type) of
the corresponding augmented Lagrangian function. In this way, Rockafellar
established a criterion for strong variational sufficiency via Hessian bundles
of augmented Lagrangians; see [50, Theorem 3]. Moreover, using the other type
of generalized second-order derivatives called quadratic bundles, it is shown
in [50, Theorem 5] that the condition

(6.22) $q\in\text{\rm quad}\;\psi(g(\bar{x}),\bar{y}),\;w\neq
0\Longrightarrow\frac{1}{2}\big{\langle}\nabla^{2}_{xx}L(\bar{x},\bar{y}),w,w\big{\rangle}+q\big{(}\nabla
g(\bar{x})w\big{)}>0.$

via the standard Lagrangian of (6.2), characterizes the strong variational
sufficiency for local optimality in (6.2). In the case where $\psi$ is
nonconvex, it is possible to derive the characterization of strong variational
sufficiency via the connection to SCD mappings (cf, [16, Proposition 3.33]),
which is also discussed in Remark 5.9. To the best of our knowledge, the
characterization of the merely variational sufficiency for local optimality in
(6.2) via quadratic bundles has not been done. Our second-order
subdifferential approach is independent of the aforementioned approach of
Rockafellar. Let us emphasize that our second-order subdifferential results in
Theorems 6.2, 6.5, and 6.6 completely characterize both variational and strong
variational sufficiency in (6.2) with and without the convexity of the
function $\psi$ therein.

##  7 Applications to Nonlinear Programming

As an illustration of the general results of Section 6, we provide here their
direct applications to characterizing variational and strong variational
sufficiency for local optimality in classical problems on nonlinear
programming with ${\cal C}^{2}$-smooth data. The characterizations obtained
below are expressed entirely in terms the problem data meaning that the
second-order subdifferentials in the results of Section 6 are explicitly
calculated.

The conventional model of nonlinear programming (NLP) is formulated as
follows:

(7.1) $\mbox{\rm minimize}\quad\varphi_{0}(x)\;\text{ subject to
}\;\begin{cases}\varphi_{i}(x)\leq 0&\text{for }\;i=1,\ldots,s,\\\
\varphi_{i}(x)=0&\text{for }\;i=s+1,\ldots,m,\end{cases}$

where $\varphi_{i}$, $i=0,\ldots,m$, are $\mathcal{C}^{2}$-smooth functions
around the references points. Problem (7.1) can be obviously written in the
form of composite optimization (6.2) with $\psi=\delta_{\Omega}$, where
$\Omega$ is given by

(7.2) $\Omega:=\big{\\{}u\in{\rm I\\!R}^{m}\;\big{|}\;u_{i}\leq 0\;\text{ for
}\;i=1,\ldots,s\;\mbox{ and }\;u_{i}=0\;\text{ for
}\;i=s+1,\ldots,m\big{\\}},$

and where $g(x):=(\varphi_{1}(x),\ldots,\varphi_{m}(x))$. Define the
Lagrangian function $L:{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}\to{\rm I\\!R}$ by

(7.3) $L(x,y):=\varphi_{0}(x)+\langle
y,g(x)\rangle=\varphi_{0}(x)+y_{1}\varphi_{1}(x)+\ldots+y_{m}\varphi_{m}(x)\quad\text{for
all }\;x\in{\rm I\\!R}^{n},\;y\in{\rm I\\!R}^{m}$

and for each $(x,y)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}$ consider the
subspace

(7.4) $S(x,y):=\big{\\{}w\in{\rm
I\\!R}^{n}\;\big{|}\;\langle\nabla\varphi_{i}(x),w\rangle=0\;\text{ for
}\;i\in I_{+}(x,y)\cup\\{s+1,\ldots,m\\}\big{\\}}$

together with the index collections

(7.5) $I_{+}(x,y):=\big{\\{}i\in I(x)\;\big{|}\;y_{i}>0\big{\\}}\;\text{ and
}\;I(x):=\big{\\{}i\in\\{1,\ldots,s\\}\;\big{|}\;\varphi_{i}(x)=0\big{\\}}.$

First-order and second-order subdifferential calculations for the indicator
function of set (7.2) can be deduced from various sources and represented in
different forms. Here we present a simple direct derivation and present the
corresponding formulas in the explicit and convenient way used in what
follows.

######  Lemma 7.1 (explicit subdifferential calculations for NLP).

Let the set $\Omega$ be taken from (7.2). Then

(7.6)
$\partial\delta_{\Omega}(z)=\partial^{\infty}\delta_{\Omega}(z)=N_{\Omega}(z)=F_{1}(z_{1})\times\ldots\times
F_{m}(z_{m})\;{\text{ for all }\;z\in\Omega,}$

where each multifunction $F_{i}\colon{\rm I\\!R}\rightrightarrows{\rm I\\!R}$
is given by

$F_{i}(t):=\begin{cases}[0,\infty)&\text{if}\quad t=0,\;1\leq i\leq s,\\\
\\{0\\}&\text{if}\quad t<0,\;1\leq i\leq s,\\\ {\rm I\\!R}&\text{if}\quad
t=0,\;s+1\leq i\leq m,\\\ \emptyset&\text{otherwise}.\end{cases}$

Furthermore, for every $(z,y)\in\mbox{\rm gph}\,\partial\delta_{\Omega}$ we
have

(7.7) $\partial^{2}\delta_{\Omega}(z,y)(v)=\big{\\{}u\in{\rm
I\\!R}^{m}\;\big{|}\;(u_{i},-v_{i})\in
G_{i}(z_{i},y_{i}),\;i=1,\ldots,m\big{\\}}\;\mbox{ for all }\;v\in{\rm
I\\!R}^{m},$

where the multifunctions $G_{i}\colon{\rm I\\!R}^{2}\rightrightarrows{\rm
I\\!R}^{2}$, $i=1.\ldots,m$, are given by

$G_{i}(t,p):=\begin{cases}(\mathbb{R}_{+}\times\mathbb{R}_{-})\cup\big{(}\mathbb{R}\times\\{0\\}\big{)}\cup\big{(}\\{0\\}\times\mathbb{R}\big{)}&\text{if}\quad
t=0,\;p=0,\;1\leq i\leq s,\\\ \mathbb{R}\times\\{0\\}&\text{if}\quad
t=0,\;p>0,\;1\leq i\leq s,\\\ \\{0\\}\times\mathbb{R}&\text{if}\quad
t<0,\;p=0,\;1\leq i\leq s,\\\ \mathbb{R}\times\\{0\\}&\text{if}\quad
t=0,\;s+1\leq i\leq m,\\\ \emptyset&\text{otherwise}.\end{cases}$

[Proof.] Recall first by [30, Proposition 1.79] that

$\partial\delta_{\Omega}(z)=\partial^{\infty}\delta_{\Omega}(z)=N_{\Omega}(z)\quad\text{for
all }\;z\in\Omega.$

It follows from $\Omega=\Omega_{1}\times\ldots\times\Omega_{m}$ with

$\Omega_{i}:=\begin{cases}(-\infty,0]&\text{if }\quad i=1,\ldots,s,\\\
\\{0\\}&\text{if }\quad i=s+1,\ldots,m\end{cases}$

that we have the representation

$\delta_{\Omega}(z)=\delta_{\Omega_{1}}(z_{1})+\ldots+\delta_{\Omega_{m}}(z_{m})\quad\text{for
all }\;z=(z_{1},\ldots,z_{m})\in{\rm I\\!R}^{m}.$

This easily leads us to the subdifferential expression

(7.8)
$\partial\delta_{\Omega}(z)=\partial\delta_{\Omega_{1}}(z_{1})\times\ldots\times\partial\delta_{\Omega_{m}}(z_{m})\quad\text{for
all }\;z\in\Omega.$

Since $\Omega_{i}$ is convex for any $i\in\\{1,\ldots,m\\}$, it is not
difficult to check that

(7.9)
$\partial\delta_{\Omega_{i}}(t)=N_{\Omega_{i}}(t)=F_{i}(t)\quad\text{whenever
}\;t\in{\rm I\\!R},\;i=1,\ldots,m.$

Combining (7.8) and (7.9) justifies the first-order formulas in (7.6).

To verify finally the second-order subdifferential formula (7.7), observe that
$N_{{\rm\small gph}\,\partial\delta_{\Omega_{i}}}=G_{i}\quad\text{for all
}\;i=1,\ldots,m$. This allows us to deduce from [38, Theorem 4.3] the
representation

$\partial^{2}\delta_{\Omega}(z,y)(v)=\big{\\{}u\in{\rm
I\\!R}^{m}\;\big{|}\;\big{(}u_{i},-v_{i}\big{)}\in N_{{\rm\small
gph}\,\partial\delta_{\Omega_{i}}}(z_{i},y_{i}),\;i=1,\ldots,m\big{\\}},$

which therefore justifies the fulfillment of (7.7) and completes the proof of
the lemma.

Thanks to Lemma 7.1, we have the following explicit formula for the set of
multipliers (6.3) in problem (7.1):

(7.10) $\Lambda(x,v)=\big{\\{}y\in{\rm I\\!R}_{+}^{s}\times{\rm
I\\!R}^{m-s}\;\big{|}\;v=\nabla_{x}L(x,y),\;\langle y,g(x)\rangle=0\big{\\}}$

with $g=(\varphi_{1},\ldots,\varphi_{m})$ and the Lagrangian function $L$
defined in (7.3).

Next we recall the two well-known constraint qualification conditions in NLP.
Given a feasible solution $\bar{x}$ to (7.1), it is said that the linear
independent constraint qualification (LICQ) holds at $\bar{x}$ of (7.1) if the
vectors

(7.11) $\nabla\varphi_{i}(\bar{x})\;\mbox{ for }\;i\in I(\bar{x})\;\text{and
}\;\nabla\varphi_{i}(\bar{x})\;\mbox{ for }\;i=s+1,\ldots,m\;\text{ are
linearly independent},$

where $I(\bar{x})$ stands for the collection of active inequality constraint
indices at $\bar{x}$ taken from (7.5). We say that the positive linear
independence constraint qualification (PLICQ) is satisfied at $\bar{x}$ if

(7.12) ${\bigg{[}\displaystyle\sum_{i\in
I(\bar{x})\cup\\{s+1,\ldots,m\\}}\alpha_{i}\nabla\varphi_{i}(\bar{x})=0,\;\alpha_{i}\geq
0,\;i\in I(\bar{x})\bigg{]}\Longrightarrow\big{[}\alpha_{i}=0\;\mbox{ for all
}\;i\in I(\bar{x})\cup\\{s+1,\ldots,m\\}\big{]}.}$

Note that both of these constraint qualifications are robust with respect to
small perturbations of $\bar{x}$. In fact, (7.12) is a dual form of the
Mangasarian-Fromovitz constraint qualification (MFCQ) at $\bar{x}$.

By using Lemma 7.1, we show now that the first-order qualification condition
(6.12) and the second-order qualification condition (6.13) are equivalent to
PLICQ and LICQ at $\bar{x}$, respectively,

######  Lemma 7.2 (equivalent descriptions of first- and second-order
qualification conditions).

Let $\bar{x}$ be a feasible solution for NLP (7.1) written in the framework of
composite optimization (6.2) with

(7.13) $\psi:=\delta_{\Omega}\;\mbox{ and
}\;g:=(\varphi_{1},\ldots,\varphi_{m}),$

where $\Omega$ is taken from (7.2). Then the following assertions hold:

(i) We have the representation

(7.14) $\partial^{\infty}\psi\big{(}g(\bar{x})\big{)}\cap\mbox{\rm
ker}\,\nabla g(\bar{x})^{*}=\left\\{u\in{\rm I\\!R}^{m}\;\bigg{|}\;\sum_{i\in
J}u_{i}\nabla\varphi_{i}(\bar{x})=0,\;u_{i}\geq 0\;\forall{i\in
I(\bar{x})}\;\mbox{ and }\;u_{i}=0\;\forall i\notin J\right\\},$

where $J:=I(\bar{x})\cup\\{s+1,\ldots,m\\}$. Consequently, the first-order
qualification condition (6.12) at $\bar{x}$ is equivalent to the fulfillment
of PLICQ (7.12) at this point.

(ii) Whenever $\bar{y}\in\partial\psi(g(\bar{x}))$, we have the representation

(7.15) $\partial^{2}\psi\big{(}g(\bar{x}),\bar{y}\big{)}(0)\cap\mbox{\rm
ker}\,\nabla g(\bar{x})^{*}=\left\\{u\in{\rm I\\!R}^{m}\;\bigg{|}\;\sum_{i\in
J}u_{i}\nabla\varphi_{i}(\bar{x})=0,\;u_{i}=0\;\text{ for all }\;i\notin
J\right\\}$

with $J$ taken from (i). Consequently, the second-order qualification
condition (6.13) is equivalent to the fulfillment of LICQ (7.11) at this
point.

[Proof.] To verify assertion (i), deduce from Lemma 7.1 that

(7.16) $u\in\partial^{\infty}\psi\big{(}g(\bar{x})\big{)}\iff u_{i}\geq
0\quad\text{for all }\;{i\in I(\bar{x})}\quad\text{and
}\;u_{i}=0\quad\text{for all }\;i\notin J.$

Furthermore, it follows from the definitions that

(7.17) $u\in\mbox{\rm ker}\,\nabla g(\bar{x})^{*}\iff\nabla
g(\bar{x})^{*}u=0\iff{\sum_{i=1}^{m}u_{i}\nabla\varphi_{i}(\bar{x})=0.}$

Combining (7.16) and (7.17) justifies (7.14), which yields the claimed
equivalence between (6.12) and (7.12).

To proceed with the verification of (ii), pick
$\bar{y}\in\partial\psi(g(\bar{x}))$ and get from Lemma 7.1 that

$u\in\partial^{2}\psi\big{(}g(\bar{x}),\bar{y}\big{)}(0)\iff
u_{i}=0\quad\text{for all }\;i\notin J.$

Using this together with (7.17) gives us (7.15), which immediately implies the
claimed equivalence in (ii).

Reformulating the NLP problem (7.1) in the form of composite optimization
(6.2) with $\psi$ and $g$ taken from (7.13), observe that the stationary
condition $0\in\partial\varphi(\bar{x})$ can be equivalently written as the
KKT system

(7.18) $\nabla_{x}L(\bar{x},\bar{y})=0\quad\text{and
}\;\langle\bar{y},g(\bar{x})\rangle=0\quad\text{for some }\;\bar{y}\in{\rm
I\\!R}_{+}^{s}\times{\rm I\\!R}^{m-s}$

provided that the first-order qualification condition (6.12), i.e., PLICQ in
our case, holds. Indeed, it follows from the subdifferential sum and chain
rules taken from [30, Proposition 1.107(ii) and Theorem 3.41(ii)],
respectively, with the usage of Lemma 7.1 ensuring representation (7.10).

The next theorem establishes second-order characterizations of variational and
strong variational sufficiency for local optimality in nonlinear programming
entirely in terms of the given data of (7.1).

######  Theorem 7.3 (variational and strong variational sufficiency for local
optimality in NLP).

Let $\bar{x}$ be a feasible solution to the NLP problem (7.1) satisfying the
first-order optimality condition (7.18) under the fulfillment of LICQ at
$\bar{x}$, and let $S(x,y)$ be defined in (7.4). Then we have the following
assertions:

(i) The variational sufficiency for local optimality in (7.1) holds at
$\bar{x}$ if and only if there exist neighborhoods $U$ of $\bar{x}$, $V$ of
$0$ such that

(7.19) $\langle\nabla^{2}_{xx}L(x,y)w,w\rangle\geq 0\quad\text{whenever
}\;x\in U,\;v\in V,\;\mbox{ and }\;w\in S(x,y),$

where $y\in{\rm I\\!R}^{s}_{+}\times{\rm I\\!R}^{m-s}$ is a unique solution to
the system $\nabla_{x}L(x,y)=v$ and $\langle y,g(x)\rangle=0$ with $g$ from
(7.13).

(ii) The strong variational sufficiency for local optimality in (7.1) holds at
$\bar{x}$ with modulus $\sigma>0$ if and only if there exist neighborhoods $U$
of $\bar{x}$ and $V$ of $0$ such that

(7.20)
$\langle\nabla^{2}_{xx}L(x,y)w,w\rangle\geq\sigma\|w\|^{2}\quad\text{whenever
}\;x\in U,\;v\in V,\;\mbox{ and }\;w\in S(x,y)$

with the unique vector $y\in{\rm I\\!R}^{s}_{+}\times{\rm I\\!R}^{m-s}$
defined as in (i).

(iii) The strong variational sufficiency for local optimality in (7.1) holds
at $\bar{x}$ if and only if

(7.21)
$\langle\nabla^{2}_{xx}L(\bar{x},\bar{y})w,w\rangle>0\quad\text{whenever
}\;\bar{y}\in\Lambda(\bar{x},0)\;\mbox{ and }\;w\in
S(\bar{x},\bar{y})\setminus\\{0\\},$

where $\bar{y}$ is a unique solution to the KKT system (7.18).

[Proof.] By Lemma 7.2(ii), the fulfillment of LICQ at $\bar{x}$ is equivalent
to the second-order qualification condition (6.15), and thus (6.12) is
satisfied by Proposition 6.3 with $\psi=\delta_{\Omega}$. This also follows,
in the NLP case, from the PLICQ description of (6.12) in Lemma 7.2(i). As
discussed above, condition (7.18) is equivalent to the stationary
$0\in\partial\varphi(\bar{x})$ of $\bar{x}$ for
$\varphi=\varphi_{0}+\delta_{\Omega}\circ g$ with $\Omega$ from (7.2) and
$g=(\varphi_{1},\ldots,\varphi_{m})$.

It is easy to see that the imposed LICQ corresponds to the full rank
assumption for $g$ from Theorem 6.2, and thus we can apply the variational and
strong variational sufficiency characterizations of that theorem for the
composite problem (6.2) to the case of NLP (7.1). Note that the convex l.s.c.
function $\psi=\delta_{\Omega}$ for $\Omega$ from (7.2) is automatically
continuously prox-regular. Observe also that this function is even piecewise
linear, and thus we can equally apply Theorem 6.6(a) to the NLP setting (7.1).
It remains to express the general variational and strong variational
sufficiency characterization in composite optimization explicitly in terms of
the NLP data.

To proceed, we employ Lemma 7.1, which tells us that the inclusion
${u\in\partial^{2}\delta_{\Omega}(g(x),y)(\nabla g(x)w)}$ for each $u\in{\rm
I\\!R}^{m}$, $w\in{\rm I\\!R}^{n}$, $x\in{\rm I\\!R}^{n}$, and
$y\in\partial\delta_{\Omega}(g(x))$ amounts to saying that

(7.22) $\begin{cases}u_{i}=0&\text{if
}\;i\in\big{\\{}1,\ldots,s\big{\\}}\setminus I(x),\\\
\langle\nabla\varphi_{i}(x),w\rangle=0&\text{if
}\;i\in\big{\\{}s+1,\ldots,m\big{\\}}\cup I_{+}(x,y),\\\
\langle\nabla\varphi_{i}(x),w\rangle\geq 0,\;u_{i}\geq 0&\text{if }\;i\in
I(x)\setminus I_{+}(x,y).\end{cases}$

First we verify that the conditions in (7.19), (7.20), and (7.21) yield the
variational and strong variational sufficiency with and without modulus
$\sigma>0$ for local optimality in (7.1), respectively. To this end, suppose
that (7.19) holds and pick any $x\in U,\;v\in V,\;w\in{\rm I\\!R}^{n}$, and
$u\in\partial^{2}\psi(g(x),y)(\nabla g(x)w)$ in the setting of (7.13) with the
unique solution $y$ of the corresponding KKT system. We aim to show that

(7.23) $\langle\nabla^{2}\varphi_{0}(x)w,w\rangle+\langle\nabla^{2}\langle
y,g\rangle(x)w,w\rangle+\langle u,\nabla g(x)w\rangle\geq 0.$

Indeed, it follows from (7.22) that

(7.24) $u_{i}\langle\nabla\varphi_{i}(x),w\rangle\geq 0\quad\text{ for all
}\;i=1,\ldots,m\;\mbox{ and }\;w\in S(x,y),$

and thus we deduce from (7.19) that
$\langle\nabla_{xx}^{2}L(x,y)w,w\rangle\geq 0$. Combining the latter with
(7.24) gives us (7.23), and therefore the claimed variational sufficiency for
local optimality in (7.1) holds by Theorem 6.5. Arguing similarly to the
arguments above, we verify that the strong variational sufficiency for local
optimality in (7.1) with and without modulus $\sigma>0$ is also satisfied
under the conditions in (7.20) and (7.21), respectively.

Next we prove the converse, i.e., that the variational and strong variational
sufficient conditions with and without modulus $\sigma>0$ for local optimality
in (7.1) ensure the fulfillment of the conditions in (7.19), (7.20), and
(7.21), respectively. To proceed with the case of variational sufficiency in
(i), we get by this property for (7.1) at $\bar{x}$ that there exist
neighborhoods $U$ of $\bar{x}$ and $V$ of $0$ such that (6.5) holds due to
Theorem 6.6(a). Taking any $x\in U,\;v\in V$, and $w\in S(x,y)$ with the
unique solution $y$ of the corresponding KKT system, let us verify the
fulfillment of (7.19). Indeed, choose $u\in{\rm I\\!R}^{m}$ such that
$u_{i}=0$ for any $i\in\\{1,\ldots,s\\}\setminus I_{+}(x,y)$. It follows from
(7.22) that $u\in\partial^{2}\psi(g(x),y)(\nabla g(x)w)$ for $\psi$ and $g$ in
(7.13). Moreover, the choice of $u$ implies that

(7.25) $\sum_{i\in\\{1,\ldots,s\\}\setminus
I_{+}(x,y)}u_{i}\langle\nabla\varphi_{i}(x),w\rangle=0.$

Since $w\in S(x,y)$, we readily get that

(7.26) $\sum_{i\in\\{s+1,\ldots,m\\}\cup
I_{+}(x,y)}u_{i}\langle\nabla\varphi_{i}(x),w\rangle=0.$