# Coderivative-Based Newton Methods in Structured Nonconvex and Nonsmooth
Optimization

Pham Duy Khanh111Department of Mathematics, Ho Chi Minh City University of
Education, Ho Chi Minh City, Vietnam. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>Boris S. Mordukhovich222Department of Mathematics, Wayne
State University, Detroit, Michigan, USA. E-mail<EMAIL_ADDRESS> Vo Thanh
Phat333Department of Mathematics, Wayne State University, Detroit, Michigan,
USA. E-mail<EMAIL_ADDRESS>
Abstract. This paper proposes and develops new Newton-type methods to solve
structured nonconvex and nonsmooth optimization problems with justifying their
fast local and global convergence by means of advanced tools of variational
analysis and generalized differentiation. The objective functions belong to a
broad class of prox-regular functions with specification to constrained
optimization of nonconvex structured sums. We also develop a novel line search
method, which is an extension of the proximal gradient algorithm while
allowing us to globalize the proposed coderivative-based Newton methods by
incorporating the machinery of forward-backward envelopes. Further
applications and numerical experiments are conducted for the
$\ell_{0}$-$\ell_{2}$ regularized least-square model appearing in statistics
and machine learning.
Key words. Nonsmooth optimization, variational analysis, generalized Newton
methods, local convergence, global convergence, nonconvex structured
optimization, regularized least-square, machine learning
Mathematics Subject Classification (2010) 90C26, 49J52, 49J53

##  1 Introduction

For a function $\varphi:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$, which is twice
continuously differentiable (${\cal C}^{2}$-smooth) around a certain point
$\bar{x}$, the classical Newton method to solve the unconstrained optimization
problem

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

starts with a given initial point $x^{0}\in{\rm I\\!R}^{n}$ and constructs the
iterative procedure

$x^{k+1}:=x^{k}+d^{k}\;\mbox{ for all }\;k\in{\rm
I\\!N}:=\big{\\{}1,2,\ldots\big{\\}},$ (1.2)

where $d^{k}$ is a solution to the linear system

$-\nabla\varphi(x^{k})=\nabla^{2}\varphi(x^{k})d^{k},\quad k\in{\rm I\\!N},$
(1.3)

expressed via the Hessian matrix $\nabla^{2}\varphi(x^{k})$ of $\varphi$ at
$x^{k}$. In classical optimization, Newton’s algorithm in (1.2) and (1.3) is
well-defined, meaning that the equations in (1.3) are solvable for $d^{k}$ and
the sequence of its iterations ${x^{k}}$ quadratically converges to the
solution $\bar{x}$ of (1.1) if $x^{0}$ is chosen sufficiently close to
$\bar{x}$ and if the Hessian matrix $\nabla^{2}\varphi(\bar{x})$ is positive-
definite. However, this method necessitates information on Hessian matrices,
which are unavailable in many practical optimization problems where the cost
function may not be $\mathcal{C}^{2}$-smooth. Therefore, the development of
generalized Newton methods is required with replacing the Hessian matrix by a
certain generalized second-order derivative.

Over the years, various generalized Newton methods have been developed in
nonsmooth optimization; we refer the reader to the books [7, 13, 22] and the
bibliographies therein for more details.

Our approach in this paper is different from the majority of developments on
generalized Newton methods in nonsmooth optimization and related areas. It is
based on the machinery of variational analysis and generalized differentiation
that is revolved around the second-order subdifferentials/generalized Hessians
introduced by Mordukhovich [23] in the dual “derivative-of-derivative” scheme
by taking a coderivative of a subgradient mapping; see Section 2. The
importance and benefits of such constructions have been well recognized in
variational analysis, optimization, and numerous applications (see, e.g., the
books [25, 27] with the vast bibliographies therein), while their usage in the
design and justification of numerical algorithms, as well as in practical
applications to machine learning and other disciplines, has been revealed
quite recently in [1, 9, 18, 20, 21, 27, 29].

The main goals of this paper include developing novel coderivative-based
generalized Newton methods to solve broad classes of optimization-related
problems that are different from the known achievements in this direction by
the methodology, design, imposed assumptions, obtained results, and
applications. Let us discuss some major issues and their placements in the
paper .

$\bullet$ In Section 3 (after the basic definitions and preliminary results
given in Section 2), we address solving subgradient inclusions of the type
$0\in\partial\varphi(x)$, where $\partial\varphi$ stands for the limiting
subdifferential of an extended-real-valued, lower semicontinuous (l.s.c.), and
prox-bounded function $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm
I\\!R}}:=(-\infty,\infty]$. Using the aforementioned second-order
subdifferential $\partial^{2}\varphi$, we design a generalized Newton
algorithm to solve such problems that doesn’t require, in contrast to [18],
the nonemptiness of the limiting subdifferential $\partial\varphi(x^{k})$
along the iterative sequence. The well-posedness and local superlinear
convergence of the new algorithm to find stationary points are justified under
natural assumptions.

$\bullet$ Section 4 develops a novel Newton-type algorithm to solve structured
optimization problems

$\mbox{\rm minimize}\quad\varphi(x):=f(x)+g(x)\quad\text{subject to
}\;x\in{\rm I\\!R}^{n},$ (1.4)

where $f:{\rm I\\!R}^{n}\to{\rm I\\!R}$ is a $\mathcal{C}^{2}$-smooth function
while the regularizer $g:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is l.s.c.
and prox-bounded. Note that both $f$ and $g$ are generally nonconvex. This
makes (1.4) appropriate for applications to signal and image processing,
machine learning, statistics, control, system identification, etc.. The newly
proposed algorithm to solve (1.4) uses, in contrast to the previous
developments in [20, 21], the proximal mapping only for the regularizer $g$,
while not for the cost function $\varphi$. This is often easy to compute (as
in many models of machine learning) and enables us to address broader classes
in constrained optimization and applications. To proceed efficiently, we
explore a new notion of normal maps for (1.4) and establish the local
superlinear convergence of iterates in the proposed algorithm.

$\bullet$ Sections 5 and 6 are devoted to the globalization of developed
algorithms to solve nonconvex structured optimization problems (1.4). In
Section 5, we propose and justify a novel line search method, which can be
viewed as a generalized proximal gradient line search. To proceed, we exploit
the machinery of forward-backward envelopes (FBE) introduced in [30]. The
newly proposed line search algorithm doesn’t involved any generalized second-
order constructions and ensures the global linear convergence of iterates.
Involving further the second-order information in Section 6 allows us to
design the globalized coderivative-based Newton method (GCNM), which exhibits
the global superlinear convergence under the assumptions, which are much less
restrictive in comparison with the previous developments in [20, 21]. In
particular, we don’t impose the positive-definiteness of the generalized
Hessian on the entire space ${\rm I\\!R}^{n}$ (while only at the solution
point in some settings) and don’t restrict ourselves to quadratic convex
functions $f$ in (1.4). This dramatically extend the scope of applications.

$\bullet$ As an example of practical applications, we present in Section 7 the
usage of GCNM to the complete solving of the nonconvex $\ell_{0}-\ell_{2}$
regularized least square regression problem, which typically arises in models
of machine learning and statistics. For this class of nonsmooth and nonconvex
problems, we compute all the constructions and parameters of our algorithm
entirely in terms of the problem data and conduct numerical experiments for
randomly generated entries.

##  2 Preliminaries from Variational Analysis

This section overviews some notions and results of first-order and second-
order variational analysis and generalized differentiation broadly used in the
paper. We refer the reader to the monographs [25, 27, 35] and the more recent
papers mentioned below.

Given a set-valued mapping/multifunction $F\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ between finite-dimensional spaces,
its (Painlevé-Kuratowski) outer limit at $\bar{x}$ is defined by

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

Using the notation $z\stackrel{{\scriptstyle\Omega}}{{\to}}\bar{z}$ meaning
that $z\to\bar{z}$ with $z\in\Omega$ for a given nonempty set
$\Omega\subset{\rm I\\!R}^{s}$, the (Fréchet) regular normal cone to $\Omega$
at $\bar{z}\in\Omega$ is

$\widehat{N}_{\Omega}(\bar{z}):=\Big{\\{}v\in{\rm
I\\!R}^{s}\;\Big{|}\;\limsup_{z\overset{\Omega}{\rightarrow}\bar{z}}\frac{\langle
v,z-\bar{z}\rangle}{\|z-\bar{z}\|}\leq 0\Big{\\}},$ (2.1)

while the (Mordukhovich) limiting normal cone to $\Omega$ at
$\bar{z}\in\Omega$ is defined by

$N_{\Omega}(\bar{z}):=\underset{z\overset{\Omega}{\to}\bar{z}}{\mathop{{\rm
Lim}\,{\rm sup}}}\;\widehat{N}_{\Omega}(z)=\big{\\{}v\in{\rm
I\\!R}^{s}\;\big{|}\;\exists\,z_{k}\stackrel{{\scriptstyle\Omega}}{{\to}}\bar{z},\;v_{k}\to
v\;\text{ as }\;k\to\infty\;\text{ with
}\;v_{k}\in\widehat{N}_{\Omega}(z_{k})\big{\\}}.$ (2.2)

The (Bouligand-Severi) tangent/contingent cone to $\Omega$ at $\bar{z}$ is

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

Note the duality relation between the regular normal and tangent cones

$\widehat{N}_{\Omega}(\bar{z})=\left[T_{\Omega}(\bar{z})\right]^{*}=\big{\\{}v\in{\rm
I\\!R}^{s}\;\big{|}\;\langle v,w\rangle\leq 0\;\mbox{ for all }\;w\in
T_{\Omega}(\bar{z})\big{\\}}$ (2.4)

and observe that the limiting normal cone (2.2) cannot be dual, in view its
intrinsic nonconvexity, to any tangential approximation of the set in
question.

For a set-valued mapping $F\colon{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{m}$, we define its graph, domain, kernel, and range by

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

respectively. The inverse mapping of $F$ is the set-valued mapping
$F^{-1}:{\rm I\\!R}^{m}\rightrightarrows{\rm I\\!R}^{n}$ given by

$F^{-1}(y):=\big{\\{}x\in{\rm I\\!R}^{n}\;\big{|}\;y\in F(x)\big{\\}},\quad
y\in{\rm I\\!R}^{m}.$

Based on the normal cones (2.1) and (2.2) to the graphs, we define the regular
coderivative and the limiting coderivative of $F$ at
$(\bar{x},\bar{y})\in\mbox{\rm gph}\,$ by, respectively,

$\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.5)
$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}.$ (2.6)

The graphical derivative of $F$ at $(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$ is
defined via the tangent cone (2.3) by

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

Due to the regular normal-tangent cone duality (2.4), we have the duality
correspondence between (2.5) and (2.7), while the nonconvex-valued limiting
coderivative (2.6) is not tangentially generated. In the case where
$F(\bar{x})$ is the singleton $\\{\bar{y}\\}$, we omit $\bar{y}$ in the
notation of (2.5)–(2.7). Note that if $F\colon{\rm I\\!R}^{n}\to{\rm
I\\!R}^{m}$ is ${\cal C}^{1}$-smooth around $\bar{x}$ (in fact, just strictly
differentiable at this point), then

$DF(\bar{x})=\nabla F(\bar{x})\;\mbox{ and
}\;\widehat{D}^{*}F(\bar{x})=D^{*}F(\bar{x})=\nabla F(\bar{x})^{*},$

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

To proceed further, recall that the distance function associated with a set
$\Omega\subset{\rm I\\!R}^{s}$ is

${\rm
dist}(x;\Omega):=\inf\big{\\{}\|w-x\|\;\big{|}\;w\in\Omega\big{\\}},\quad
x\in{\rm I\\!R}^{s},$

and define the Euclidean projector of $x\in{\rm I\\!R}^{s}$ to $\Omega$ by

$\Pi_{\Omega}(x):=\big{\\{}w\in\Omega\;\big{|}\;\|x-w\|={\rm
dist}(x;\Omega)\big{\\}}.$

A mapping $\widehat{F}\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$
is a localization of $F\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$
at $\bar{x}$ for $\bar{y}\in F(\bar{x})$ if there exist neighborhoods $U$ of
$\bar{x}$ and $V$ of $\bar{y}$ such that we have $\mbox{\rm
gph}\,\widehat{F}=\mbox{\rm gph}\,F\cap(U\times V)$. Here are the important
well-posedness properties of set-valued mappings used in what follows.

######  Definition 2.1 (metric regularity and subregularity of mappings).

Let $F\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ be a set-valued
mapping, and let $(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$. We say that:

(i) $F$ is metrically regular around $(\bar{x},\bar{y})$ with modulus $\mu>0$
if there exist neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{y}$ providing
the estimate

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

If in addition $F^{-1}$ has a single-valued localization around
$(\bar{y},\bar{x})$, then $F$ is strongly metrically regular around
$(\bar{x},\bar{y})$ with modulus $\mu>0$.

(ii) $F$ is metrically subregular at $(\bar{x},\bar{y})$ with modulus $\mu>0$
if there exists a neighborhood $U$ of $\bar{x}$ such that we have the estimate

${\rm dist}\big{(}x;F^{-1}(\bar{y})\big{)}\leq\mu\,{\rm
dist}\big{(}\bar{y};F(x)\big{)}\;\text{ for all }\;x\in U.$

If $F^{-1}(\bar{y})\cap U=\\{\bar{x}\\}$, then $F$ is strongly metrically
subregular at $(\bar{x},\bar{y})$ with modulus $\mu>0$. We say that $F$ is
strongly metrically subregular around $(\bar{x},\bar{y})$ if there exist
neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{y}$ such that $F$ is strongly
metrically subregular at every point $(x,y)\in\mbox{\rm gph}\,F\cap(U\times
V)$.

Observe that the metric regularity properties in Definition 2.1(i) are
preserved in a neighborhood of the point $(\bar{x},\bar{y})$, i.e., they are
robust with respect to small perturbations of the reference point, which is
not always the case for metric subregularity from Definition 2.1(ii). Recall
that a mapping $F\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$, which
graph is closed around $(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$, is metrically
regular around this point if and only if we have the kernel coderivative
condition

$\mbox{\rm ker}\,D^{*}F(\bar{x},\bar{y}):=\big{\\{}v\in{\rm
I\\!R}^{m}\;\big{|}\;0\in D^{*}F(\bar{x},\bar{y})(v)\big{\\}}=\\{0\\}$ (2.8)

established by Mordukhovich [24, Theorem 3.6] via his limiting coderivative
(2.6) and then labeled as the Mordukhovich criterion in Rockafellar and Wets
[35, Theorems 7.40 and 7.43]. Broad applications of this result are based on
the robustness and full calculus available for the limiting coderivative; see
[25, 26, 35] for more details and references. A parallel characterization of
the (nonrobust) strong metric subregularity property of a closed-graph mapping
$F\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ at
$(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$ is given by $\mbox{\rm
ker}\,DF(\bar{x},\bar{y})=\\{0\\}$ via the (nonrobust) graphical derivative
(2.7) of $F$ at $(\bar{x},\bar{y})$ and is known as the Levy-Rockafellar
criterion; see [5, Theorem 4E.1] for more discussions.

Next we consider an extended-real-valued function $\varphi\colon{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ with the domain and epigraph

$\mbox{\rm dom}\,\varphi:=\big{\\{}x\in{\rm
I\\!R}^{n}\;\big{|}\;\varphi(x)<\infty\big{\\}},\quad\mbox{\rm
epi}\,\varphi:=\big{\\{}(x,\alpha)\in{\rm
I\\!R}^{n+1}\;\big{|}\;\alpha\geq\varphi(x)\big{\\}}.$

The regular subdifferential and limiting subdifferential of $\varphi$ at
$\bar{x}\in\mbox{\rm dom}\,\varphi$ are defined geometrically via the
corresponding normal cones to the epigraph by, respectively,

$\widehat{\partial}\varphi(\bar{x}):=\big{\\{}v\in{\rm
I\\!R}^{n}\;\big{|}\;(v,-1)\in\widehat{N}_{{\rm\small
epi}\,\varphi}\big{(}\bar{x},\varphi(\bar{x})\big{)}\big{\\}},$ (2.9)
$\partial\varphi(\bar{x}):=\big{\\{}v\in{\rm I\\!R}^{n}\;\big{|}\;(v,-1)\in
N_{{\rm\small epi}\,\varphi}\big{(}\bar{x},\varphi(\bar{x})\big{)}\big{\\}}$
(2.10)

Note that the limiting subdifferential (2.10) admits various analytic
representations and satisfies comprehensive calculus rules that can be found
in [25, 26, 35]. Observe the useful scalarization formula

$D^{*}F(\bar{x})(v)=\partial\langle v,F\rangle(\bar{x})\;\mbox{ for all
}\;v\in{\rm I\\!R}^{m}$ (2.11)

connecting the coderivative (2.6) of a locally Lipschitzian mapping
$F\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{m}$ and the subdifferential (2.10) of
the scalarized function $x\mapsto\langle v,F\rangle(x)$ whenever $v\in{\rm
I\\!R}^{m}$.

Following [23], we define the second-order subdifferential, or generalized
Hessian, $\partial^{2}\varphi(\bar{x},\bar{v})\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ of $\varphi\colon{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ at $\bar{x}\in\mbox{\rm dom}\,\varphi$
for $\bar{v}\in\partial\varphi(\bar{x})$ as the coderivative of the
subgradient mapping

$\partial^{2}\varphi(\bar{x},\bar{v})(u):=\big{(}D^{*}\partial\varphi\big{)}(\bar{x},\bar{y})(u)\;\mbox{
for all }\;u\in{\rm I\\!R}^{n}.$ (2.12)

If $\varphi$ is ${\cal C}^{2}$-smooth around $\bar{x}$, then we have (no
Hessian transposition is needed) that

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

If $\varphi$ is of class $\mathcal{C}^{1,1}$ around $\bar{x}$ (i.e., it is
${\cal C}^{1}$-smooth and its gradient is Lipschitz continuous around this
point), then we get by (2.11) that

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

In general, (2.12) is a positively homogeneous multifunction, which possesses
well-developed calculus rules and variety of applications while being
explicitly computed in terms of the initial data for large classes of
extended-real-valued functions that overweeningly appear in variational
analysis, optimization, and numerous applications. We refer the reader to the
recent book [27] for a rather comprehensive account on (2.12); see also
Section 7 for new applications to models of machine learning and statistics.

Let us now review some classes of extended-real-valued functions
$\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ broadly used in the
paper. 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$, which is equivalent to

${\varphi((1-\lambda)x+\lambda
y)\leq(1-\lambda)\varphi(x)+\lambda\varphi(y)-\frac{\kappa}{2}\lambda(1-\lambda)\|x-y\|^{2}\;\mbox{
for any }\;x,y\in\Omega,\;\lambda\in[0,1].}$ (2.15)

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
$r,\varepsilon>0$ such that

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

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\in{\rm
I\\!R}^{n}$ with radius $\varepsilon$. 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}))$.
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.,
convex and $C^{1,1}$ functions, amenable functions, etc.; see [35, Chapter
13].

Given a function $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and a
parameter value $\lambda>0$, we always assume that $\varphi$ is proper (i.e.,
$\mbox{\rm dom}\,\varphi\neq\emptyset$) and define the Moreau envelope
$e_{\lambda}\varphi$ and proximal mapping $\textit{\rm Prox}_{\lambda\varphi}$
by, respectively,

$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.17)
$\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}.$ (2.18)

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}$. The
supremum of the set of all such $\lambda$ is the threshold $\lambda_{\varphi}$
of prox-boundedness for $\varphi$. This property admits various equivalent
descriptions and ensures a favorable behavior of Moreau envelopes and proximal
mappings. We recall the following results from [35, Theorem 1.25 and Example
10.32].

######  Proposition 2.2.

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be l.s.c. and prox-
bounded with threshold $\lambda_{\varphi}$. Then for all
$\lambda\in(0,\lambda_{\varphi})$, we have the assertions:

(i) $e_{\lambda}\varphi$ is locally Lipschitzian on ${\rm I\\!R}^{n}$.

(ii) $\operatorname{Prox}_{\lambda\varphi}(x)\neq\emptyset$ for any $x\in{\rm
I\\!R}^{n}$.

(iii) If $w^{k}\in\operatorname{Prox}_{\lambda\varphi}(x^{k})$ for $k\in{\rm
I\\!N}$ such that $x^{k}\rightarrow\bar{x}$ as $k\to\infty$, then the sequence
$\left\\{w^{k}\right\\}_{k\in{\rm I\\!N}}$ is bounded and all its accumulation
points lie in $\operatorname{Prox}_{\lambda\varphi}(\bar{x})$.

Next we present important properties of Moreau envelopes and proximal mappings
that are taken from [35, 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

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

If $\varphi$ is an l.s.c. function, a localization can be taken with just
$\varphi(x)<\varphi(\bar{x})+\varepsilon$ in (2.19).

######  Proposition 2.3 (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 that 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$ we find 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.17) is of class ${\cal
C}^{1,1}$ on the set $U_{\lambda}$.

(ii) The proximal mapping $\text{\rm Prox}_{\lambda\varphi}$ from (2.18) is
single-valued, monotone, and Lipschitz continuous on $U_{\lambda}$ while
satisfying the condition ${\rm
Prox}_{\lambda\varphi}(\bar{x}+\lambda\bar{v})=\bar{x}$.

(iii) The gradient of $e_{\lambda}\varphi$ is calculated by:

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

If in addition $\varphi$ is subdifferentially continuous at $\bar{x}$ for
$\bar{v}$, then $T$ in (2.20) can be replaced by $\partial\varphi$. The
parameter $\lambda$ can be chosen arbitrarily from $(0,\infty)$ with
$U_{\lambda}={\rm I\\!R}^{n}$ if $\varphi$ is convex.

The fundamental notion of tilt-stable local minimizers introduced in [32] is
formulated as follows.

######  Definition 2.4 (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

$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}\\}$. By a modulus of tilt stability
of $\varphi$ at $\bar{x}$, we understand a Lipschitz constant of $M_{\gamma}$
around the origin.

Finally in this section, we revisit the notion of variational convexity for
extended-real-valued functions recently introduced in [36] and then further
examined in [15, 16, 17, 19, 27, 37].

######  Definition 2.5 (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

$(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),$ (2.21)

where $U_{\varepsilon}:=\\{x\in
U\;|\;\varphi(x)<\varphi(\bar{x})+\varepsilon\\}$. We say that $\varphi$ is
strongly variationally convex at $\bar{x}$ for $\bar{v}$ with modulus
$\sigma>0$ if (2.21) holds with $\psi$ being strongly convex on $U$ with this
modulus. The term variational $\sigma$-convexity is used for $\varphi$ to
unify both cases of variational convexity ($\sigma=0$) and strong variational
convexity with modulus $\sigma>0$.

The next proposition taken from [36, Theorems 1 and 2] lists the
characterizations of variationally convex functions via some properties of
their limiting subdifferentials.

######  Proposition 2.6 (subgradient characterizations of variational
convexity).

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

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

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

$\langle
v_{1}-v_{2},u_{1}-u_{2}\rangle\geq\sigma\|u_{1}-u_{2}\|^{2}\quad\text{for all
}\;(u_{1},v_{1}),(u_{2},v_{2})\in\text{\rm
gph}\partial\varphi\cap(U_{\varepsilon}\times V),$ (2.22)

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

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

$\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).$
(2.23)

The last two propositions taken from [19] provide second-order subdifferential
characterizations of variational convexity and a precise relationship between
its strong version and tilt stability.

######  Proposition 2.7 (second-order 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})$, and let $\sigma\geq 0$, the following
are equivalent:

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

(ii) $\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

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

######  Proposition 2.8 (strong variational convexity and tilt stability).

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})$. The following assertions are equivalent:

(i) $\varphi$ is strongly variationally 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}$.

##  3 Coderivative-Based Newton Method for Subgradient Systems

In this section, we design and justify a novel generalized Newton method to
solve subgradient inclusions

$0\in\partial\varphi(x),\quad x\in{\rm I\\!R}^{n},$ (3.1)

where $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is an l.s.c. and
prox-bounded function, and where $\partial$ stands for the limiting
subdifferential (2.10). Recall that in the case of a $\mathcal{C}^{2}$-smooth
function $\varphi$, the classical Newton method constructs the iterative
procedure given in (1.2) and (1.3). A natural idea, which we explored in our
previous publications, is to replace $\nabla\varphi(x^{k})$ and
$\nabla^{2}\varphi(x^{k})$ with a vector $v^{k}\in\partial\varphi(x^{k})$ and
$\partial^{2}\varphi(x^{k},v^{k})$, respectively. In this way, the iterative
sequence $\\{x^{k}\\}\subset{\rm I\\!R}^{n}$ is constructed by

${x^{k+1}=x^{k}+d^{k}}\quad\text{with
}{-v^{k}\in\partial^{2}\varphi(x^{k},v^{k})(d^{k}),\;v^{k}\in\partial\varphi(x^{k}),\quad
k\in{\rm I\\!N}}.$ (3.2)

However, to proceed as in (3.2) is not possible if the subgradient sets
$\partial\varphi(x^{k})$ are empty for some $k\in{\rm I\\!N}$, which is not
generally excluded. We now propose to replace $x^{k}$ with another approximate
vector $\widehat{x}^{k}$ that ensures that the limiting subdifferential
$\partial\varphi(\widehat{x}^{k})$ is nonempty and that $\widehat{x}^{k}$ is
not far from $x^{k}$. This leads us to the iterative sequence
$\\{x^{k}\\}\subset{\rm I\\!R}^{n}$ constructed by

${x^{k+1}=\widehat{x}^{k}+d^{k}}\quad\text{with
}{-\widehat{v}^{k}\in\partial^{2}\varphi(\widehat{x}^{k},\widehat{v}^{k})(d^{k}),\quad
k\in{\rm I\\!N}},$ (3.3)

where $(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm gph}\,\partial\varphi$.
This general framework plays a crucial role in designing and justifying our
new coderivative-based Newton-type algorithms for solving nonsmooth and
nonconvex optimization problems in Sections 4 and 6. To proceed, suppose that
$\bar{x}$ is a solution to (3.1), i.e., $0\in\partial\varphi(\bar{x})$, and
formulate the following standing assumption for our convergence analysis in
this section.

######  Assumption 1.

There exists a neighborhood $U\times V$ of $(\bar{x},0)$ such that for each
$(x,v)\in\mbox{\rm gph}\,\partial\varphi\cap(U\times V)$ the generalized
Newton system

$-v\in\partial^{2}\varphi(x,v)(d)$ (3.4)

is solvable, i.e., there exists $d\in{\rm I\\!R}^{n}$ satisfying (3.4).

Before designing our algorithm to find a solution of (3.1), we recall
efficient conditions for solvability of the generalized Newton system (3.4)
that follow from [18, Theorems 3.1 and 3.2]. These conditions ensure that the
proposed algorithm is well-defined. Note that the local closedness assumption
on the limiting subdifferential graph imposed in the lemma holds in very
general settings; in particular, when $\varphi\colon{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is subdifferentially continuous; see
Section 2.

######  Lemma 3.1 (solvability of generalized Newton systems).

Let $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be such that
$\mbox{\rm gph}\,\partial\varphi$ is locally closed around
$(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial\varphi$. The following
assertions hold:

(i) If the mapping $\partial\varphi\colon{\rm I\\!R}^{n}\rightrightarrows{\rm
I\\!R}^{n}$ is strongly metrically subregular at $(\bar{x},\bar{v})$, then
there exists $d\in{\rm I\\!R}^{n}$ satisfying the second-order subdifferential
inclusion (3.4) for $(x,v):=(\bar{x},\bar{v})$.

(ii) If the subgradient mapping $\partial\varphi$ is strongly metrically
regular around $(\bar{x},\bar{v})$, then there exists a neighborhood $U\times
V$ of $(\bar{x},\bar{v})$ such that for each $(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V)$ we find a direction $d\in{\rm
I\\!R}^{n}$ satisfying the second-order subdifferential inclusion (3.4).

Under Assumption 1, we propose the generalized coderivative-based Newton
method for solving the subgradient system (3.1) designed as follows.

Algorithm 1 (general framework for coderivative-based Newton-type methods)

1:$x^{0}\in{\rm I\\!R}^{n}$, $\eta>0$

2:for $k=0,1,\ldots$ do

3: If $0\in\partial\varphi(x^{k})$, stop; otherwise go to the next step

4: Approximate step: Find $(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm
gph}\,\partial\varphi$ satisfying
$\|(\widehat{x}^{k},\widehat{v}^{k})-(\bar{x},0)\|\leq\eta\|x^{k}-\bar{x}\|$
(3.5)

5: Newton step: Choose $d^{k}\in{\rm I\\!R}^{n}$ satisfying
$-\widehat{v}^{k}\in\partial^{2}\varphi(\widehat{x}^{k},\widehat{v}^{k})(d^{k}).$
(3.6)

6: Set $x^{k+1}:=\widehat{x}^{k}+d^{k}$

7:end for

######  Remark 3.2 (implementation of the approximate step in Algorithm 1).

The idea in the approximate step of Algorithm 1 comes from the semismooth∗
Newton method suggested in [9]. We will compare our approach with the latter
method at the end of this section. Note that formally the approximate step in
Algorithm 1 is always well-defined since $(\widehat{x}^{k},\widehat{v}^{k})$
can be chosen as $(\bar{x},0)$. However, in practice the solution $\bar{x}$ is
unknown. Depending on the structure of $\varphi$, we will adopt below a
specific approach to selecting $\widehat{x}^{k}$ and $\widehat{v}^{k}$ that
facilitates the implementation of the algorithm.

It follows from [25, Corollary 2.29] that the collection of points
$(x,v)\in\mbox{\rm gph}\,\partial\varphi$ with
$\partial\varphi(x)\neq\emptyset$ is dense in the subdifferential graph, and
thus we can always select $(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm
gph}\,\partial\varphi$ arbitrarily close to $(\bar{x},0)$. The issue is about
fulfillment of estimate (3.5). Let us show how to do it in the following major
settings without knowing the solution $\bar{x}$.

(i) When $\varphi$ is of class $\mathcal{C}^{1,1}$ around $\bar{x}$, there
exist a neighborhood $U$ of $\bar{x}$ and $\ell>0$ such that

$\|\nabla\varphi(x)-\nabla\varphi(\bar{x})\|\leq\ell\|x-\bar{x}\|\quad\text{for
all }\;x\in U.$

Supposing that $x^{k}\in U$ at the $k^{\text{th}}$ iteration, take
$\widehat{x}^{k}:=x^{k}$ and $\widehat{v}^{k}:=\nabla\varphi(x^{k})$, which
gives us

$\|(\widehat{x}^{k},\widehat{v}^{k})-(\bar{x},0)\|\leq\|\widehat{x}^{k}-\bar{x}\|+\|\widehat{v}^{k}\|=\|x^{k}-\bar{x}\|+\|\nabla\varphi(x^{k})\|\leq(1+\ell)\|x^{k}-\bar{x}\|$

and thus justifies the required condition (3.5).

(ii) If $\varphi\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is
continuously prox-regular at $\bar{x}$ for $0$ with modulus $r>0$, then it
follows from Proposition 2.3 that for each $\lambda\in(0,r^{-1})$, there
exists a neighborhood $U_{\lambda}$ of $\bar{x}$ such that $\text{\rm
Prox}_{\lambda\varphi}$ is single-valued and Lipschitz continuous with some
modulus $L_{\lambda}>0$ on $U_{\lambda}$. Having $x^{k}\in U_{\lambda}$ at the
$k^{\text{th}}$ iteration, choose $\widehat{x}^{k}$ and $\widehat{v}^{k}$ in
the forms

$\widehat{x}^{k}:=\text{\rm Prox}_{\lambda\varphi}(x^{k})\quad\text{and
}\;\widehat{v}^{k}:=\frac{1}{\lambda}\left(x^{k}-\text{\rm
Prox}_{\lambda\varphi}(x^{k})\right).$ (3.7)

Therefore, we get the estimates

$\displaystyle\|(\widehat{x}^{k},\widehat{v}^{k})-(x^{k},0)\|\leq\left(1+\lambda^{-1}\right)\|x^{k}-\text{\rm
Prox}_{\lambda\varphi}(x^{k})\|$
$\displaystyle\leq\left(1+\lambda^{-1}\right)(\|x^{k}-\bar{x}\|+\|\text{\rm
Prox}_{\lambda\varphi}(x^{k})-\bar{x}\|)$
$\displaystyle=\left(1+\lambda^{-1}\right)(\|x^{k}-\bar{x}\|+\|\text{\rm
Prox}_{\lambda\varphi}(x^{k})-\text{\rm Prox}_{\lambda\varphi}(\bar{x})\|)$
$\displaystyle\leq\left(1+\lambda^{-1}\right)\left(\|x^{k}-\bar{x}\|+L_{\lambda}\|x^{k}-\bar{x}\|\right)=M\|x^{k}-\bar{x}\|$

with $M:=(1+\lambda^{-1})(1+L_{\lambda})$, which yields (3.5). In Section 4,
we present a choice of $(\widehat{x}^{k},\widehat{v}^{k})$ in the approximate
step of the version of Algorithm 1 for minimizing sums of two nonconvex
functions.

To justify the superlinear local convergence of our generalized Newton method,
we need the concept of semismoothness∗, which has been recently introduced by
Gfrerer and Outrata in [9]. To formulate this notion, recall first the
construction of the directional limiting normal cone to a set
$\Omega\subset{\rm I\\!R}^{s}$ at $\bar{z}\in\Omega$ in the direction
$d\in{\rm I\\!R}^{s}$ defined in [11] by

$N_{\Omega}(\bar{z};d):=\big{\\{}v\in{\rm
I\\!R}^{s}\;\big{|}\;\exists\,t_{k}\downarrow 0,\;d_{k}\to d,\;v_{k}\to
v\;\mbox{ with }\;v_{k}\in\widehat{N}_{\Omega}(\bar{z}+t_{k}d_{k})\big{\\}}.$
(3.8)

It is obvious that (3.8) agrees with the limiting normal cone (2.2) for $d=0$.
The directional limiting coderivative of $F\colon{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ at $(\bar{x},\bar{y})\in\mbox{\rm
gph}\,F$ in the direction $(u,v)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}$ is
defined in [8] by

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

while being instrumental to describe the aforementioned property from [9].

######  Definition 3.3 (semismooth∗ property of set-valued mappings).

A mapping $F\colon{\rm I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{m}$ is
semismooth∗ at $(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$ if whenever
$(u,v)\in{\rm I\\!R}^{n}\times{\rm I\\!R}^{m}$ we have

$\langle u^{*},u\rangle=\langle v^{*},v\rangle\;\mbox{ for all
}\;(v^{*},u^{*})\in\mbox{\rm
gph}\,D^{*}F\big{(}(\bar{x},\bar{y});(u,v)\big{)}.$

Recall from [29, Proposition 2.4] that for $F:=\nabla\varphi$, where
$\varphi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ is of class $\mathcal{C}^{1,1}$ around
$\bar{x}$, the semismoothness∗ of $F$ at $(\bar{x},\nabla\varphi(\bar{x}))$ is
equivalent to

$\|\nabla\varphi(x)-\nabla\varphi(\bar{x})+v_{x}\|=o(\|x-\bar{x}\|)$ (3.9)

whenever $x\to\bar{x}$ and $v_{x}\in\partial^{2}\varphi(x)(\bar{x}-x)$. This
is essential for the next lemma and subsequent results.

######  Lemma 3.4 (estimates for ${\cal C}^{1,1}$ functions).

Let $\varphi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ be of class $\mathcal{C}^{1,1}$
around $\bar{x}\in{\rm I\\!R}^{n}$. If $\nabla\varphi$ is metrically regular
around $(\bar{x},\nabla\varphi(\bar{x}))$, then there exist $c>0$ and a
neighborhood $U$ of $\bar{x}$ such that for any $x\in U$ and $d\in{\rm
I\\!R}^{n}$ satisfying $-\nabla\varphi(x)\in\partial^{2}\varphi(x)(d)$, we
find $v_{x}\in\partial^{2}\varphi(x)(\bar{x}-x)$ with

$\|x+d-\bar{x}\|\leq c\|\nabla\varphi(x)+v_{x}\|.$ (3.10)

If in addition $\nabla\varphi(\bar{x})=0$ and $\nabla\varphi$ is semismooth∗
at $(\bar{x},0)$, then for every $\varepsilon>0$ there exists a neighborhood
$U$ of $\bar{x}$ such that

$\|x+d-\bar{x}\|\leq\varepsilon\|x-\bar{x}\|\quad\text{whenever }\;x\in
U\;\mbox{ and }\;-\nabla\varphi(x)\in\partial^{2}\varphi(x)(d).$ (3.11)

[Proof.] By the metric regularity of $\nabla\varphi$ around
$(\bar{x},\nabla\varphi(\bar{x}))$ and its characterization from [18, Lemma
5.1], we find $c>0$ and a neighborhood $U$ of $\bar{x}$ satisfying

$\|v\|\geq c^{-1}\|u\|\quad\text{for all
}\;v\in\partial^{2}\varphi(x)(u),\;x\in U,\;u\in{\rm I\\!R}^{n}.$ (3.12)

Using the subadditivity of coderivatives from [18, Lemma 5.3] tells us that

$\partial^{2}\varphi(x)(d)=\partial^{2}\varphi(x)(x+d-\bar{x}+\bar{x}-x)\subset\partial^{2}\varphi(x)(x+d-\bar{x})+\partial^{2}\varphi(x)(\bar{x}-x).$

Hence for any $x\in U$ and $d\in{\rm I\\!R}^{n}$ satisfying
$-\nabla\varphi(x)\in\partial^{2}\varphi(x)(d)$, we find
$v_{x}\in\partial^{2}\varphi(x)(\bar{x}-x)$ with

$-\nabla\varphi(x)-v_{x}\in\partial^{2}\varphi(x)(x+d-\bar{x}).$

Furthermore, it follows from (3.12) that

$\|x+d-\bar{x}\|\leq c\|\nabla\varphi(x)+v_{x}\|$

verifying (3.10). Under the additional assumptions of the lemma, we deduce
from (3.9) that

$\|\nabla\varphi(x)+v_{x}\|=\|\nabla\varphi(x)-\nabla\varphi(\bar{x})+v_{x}\|=o(\|x-\bar{x}\|)\quad\text{as
}\;x\to\bar{x},$

which justifies (3.11) and thus completes the proof.

Estimate (3.10) was proved in [29] under the assumption that $\bar{x}$ is a
tilt-stable local minimizer of $\varphi$, which is stronger than the metric
regularity of $\partial\varphi$ around $(\bar{x},0)$ assumed in Lemma 3.4.
Moreover, our proof of (3.10) is fully independent from the proof of [29]. The
following technical lemma on second-order subdifferential behavior under
Moreau envelopes is borrowed from [18, Lemma 6.1].

######  Lemma 3.5 (second-order subdifferential of Moreau envelopes).

In the setting of Proposition 2.3, we have the equivalence

$x^{*}\in\partial^{2}e_{\lambda}\varphi(x,v)(v^{*})\iff
x^{*}\in\partial^{2}\varphi(x-\lambda v,v)(v^{*}-\lambda x^{*})$

for all $\lambda>0$ sufficiently small, all $x\in U_{\lambda}$, and all
$v=\nabla e_{\lambda}\varphi(x)$,

Our next theorem provides a crucial estimate, which is significant for the
subsequent justification of the coderivative-based generalized Newton
algorithm.

######  Theorem 3.6 (estimates of Newton iterations via coderivatives).

Let $\bar{x}$ solve (3.1), where $\partial\varphi$ is metrically regular
around $(\bar{x},0)$ and semismooth∗ at this point. Assume further that
$\varphi$ is continuously prox-regular at $\bar{x}$ for $0$. Then for any
$\varepsilon>0$, there exists a neighborhood $W$ of $(\bar{x},0)$ such that

$\|x+d-\bar{x}\|\leq\varepsilon\|(x,v)-(\bar{x},0)\|$ (3.13)

whenever $(x,v)\in\text{\rm gph}\partial\varphi\cap W$ and $d\in{\rm
I\\!R}^{n}$ satisfy $-v\in\partial^{2}\varphi(x,v)(d)$.

[Proof.] Proposition 2.3 tells us that the assumed prox-boundedness and
continuous prox-regularity properties of $\varphi$ guarantee the existence of
$\lambda\in(0,1)$ such that there is a neighborhood $U_{\lambda}$ of $\bar{x}$
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})=\bar{x}$, and that the gradient expression for
the Moreau envelope (2.20) holds. Since $\partial\varphi$ is semismooth∗ at
$(\bar{x},0)$, it follows from [29, Theorem 6.2, Claim 2] that $\nabla
e_{\lambda}\varphi$ is semismooth∗ at $(\bar{x},0)$. Given $\varepsilon>0$, we
find a neighborhood $U$ of $\bar{x}$ such that, by Lemma 3.4,

$\|x^{\prime}+d^{\prime}-\bar{x}\|\leq\frac{\varepsilon}{2}\|x^{\prime}-\bar{x}\|\;\text{
if }\;x^{\prime}\in U\;\mbox{ and }\;d^{\prime}\in{\rm I\\!R}^{n}\;\text{
satisfy }\;-\nabla
e_{\lambda}\varphi(x^{\prime})\in\partial^{2}e_{\lambda}\varphi(x^{\prime})(d^{\prime}).$
(3.14)

Choose further a neighborhood $W$ of $(\bar{x},0)$ such that

$x+\lambda v\in U\cap U_{\lambda}\;\mbox{ whenever }\;(x,v)\in W$ (3.15)

and suppose that $(x,v)\in\mbox{\rm gph}\,\partial\varphi\cap W$ and that
$d\in{\rm I\\!R}^{n}$ satisfies

$-v\in\partial^{2}\varphi(x,v)(d)=\partial^{2}\varphi((x+\lambda v)-\lambda
v,v)(d).$ (3.16)

Then it follows from (2.20) and (3.15) that $\nabla
e_{\lambda}\varphi(x+\lambda v)=v$. Combining the latter equality with (3.15),
(3.16), and Lemma 3.5 yields

$-\nabla e_{\lambda}\varphi(x+\lambda
v)=-v\in\partial^{2}e_{\lambda}\varphi(x+\lambda v,v)(d-\lambda v).$

This implies in turn due to (3.14) and (3.15) that

$\|(x+\lambda v)+(d-\lambda v)-\bar{x}\|\leq\frac{\varepsilon}{2}\|x+\lambda
v-\bar{x}\|.$

Therefore, we arrive at the estimates

$\|x+d-\bar{x}\|\leq\frac{\varepsilon}{2}\left(\|x-\bar{x}\|+\lambda\|v\|\right)\leq\varepsilon\|(x,v)-(\bar{x},0)\|,$

which complete the proof of theorem.

Now we are ready to establish the main result of this section justifying the
local superlinear convergence of the Newtonian coderivative-based Algorithm 1.

######  Theorem 3.7 (local superlinear convergence of the generalized Newton
algorithms).

Let $\bar{x}$ solve inclusion (3.1), where $\partial\varphi$ is metrically
regular around $(\bar{x},0)$ and semismooth∗ at this point. Suppose further
that Assumption 1 is satisfied and that $\varphi$ is continuously prox-regular
at $\bar{x}$ for $0$. Then there exists a neighborhood $U$ of $\bar{x}$ such
that, whenever $x^{0}\in U$, Algorithm 1 either stops after finitely many
iterations, or produces a sequence $\\{x^{k}\\}$ that $Q$-superlinearly
converges to $\bar{x}$ as $k\to\infty$.

[Proof.] Assumption 1 and Theorem 3.6 allow us to find such $\delta>0$ that
for any $x\in\mathbb{B}_{\delta}(\bar{x})$ there exists
$(\widehat{x},\widehat{v})\in\mbox{\rm gph}\,\partial\varphi$ satisfying the
estimate

$\|(\widehat{x},\widehat{v})-(\bar{x},0)\|\leq\eta\|x-\bar{x}\|,$ (3.17)

and that for any $(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap\mathbb{B}_{\delta}(\bar{x},0)$ we get $d\in{\rm
I\\!R}^{n}$ with

$-v\in\partial^{2}\varphi(x,v)(d)\;\text{and
}\|x+d-\bar{x}\|\leq\frac{1}{2\eta}\|(x,v)-(\bar{x},0)\|.$ (3.18)

Fix $x^{0}\in
U:=\mathbb{B}_{\delta/\eta}(\bar{x})\cap\mathbb{B}_{\delta}(\bar{x})$ and
deduce from (3.17) the existence of
$\left(\widehat{x}^{0},\widehat{v}^{0}\right)\in\mbox{\rm
gph}\,\partial\varphi$ such that

$\left\|\left(\widehat{x}^{0},\widehat{v}^{0}\right)-(\bar{x},0)\right\|\leq\eta\|x^{0}-\bar{x}\|\leq\delta,$

which readily implies that
$\left(\widehat{x}^{0},\widehat{v}^{0}\right)\in\mbox{\rm
gph}\,\partial\varphi\cap\mathbb{B}_{\delta}(\bar{x},0)$. Furthermore, by
(3.18) we find $d^{0}\in{\rm I\\!R}^{n}$ satisfying
$-\widehat{v}^{0}\in\partial^{2}\varphi(\widehat{x}^{0},\widehat{v}^{0})(d^{0})$,
and hence

$\|x^{1}-\bar{x}\|=\|\widehat{x}^{0}+d^{0}-\bar{x}\|\leq\frac{1}{2\eta}\|(\widehat{x}^{0},\widehat{v}^{0})-(\bar{x},0)\|\leq\frac{1}{2}\|x^{0}-\bar{x}\|.$

The latter ensures, in particular, that $x^{1}\in U$. Employing the standard
induction arguments allows us to conclude that Algorithm 1 either stops after
finitely many iterations, or produces sequences $\\{x^{k}\\}$,
$\\{\widehat{x}^{k}\\}$, and $\\{\widehat{v}^{k}\\}$ so that the pairs
$(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm
gph}\,\partial\varphi\cap\mathbb{B}_{\delta}(\bar{x},0)$ satisfy the estimates

$\|(\widehat{x}^{k},\widehat{v}^{k})-(\bar{x},0)\|\leq\eta\|x^{k}-\bar{x}\|,$
$\|x^{k+1}-\bar{x}\|\leq\frac{1}{2}\|x^{k}-\bar{x}\|\quad\text{for all
}\;k=0,1,\ldots.$

This clearly implies that both sequences $\\{x^{k}\\}$ and
$\\{\widehat{x}^{k}\\}$ converge to the solution $\bar{x}$ of (3.1) while the
sequence $\\{\widehat{v}^{k}\\}$ converges to $0$ as $k\to\infty$. To verify
finally the $Q$-superlinear convergence of the iterative sequence
$\\{x^{k}\\}$, pick any $\varepsilon>0$ and deduce from Theorem 3.6 that

$\|x^{k+1}-\bar{x}\|=\|\widehat{x}^{k}+d^{k}-\bar{x}\|\leq\frac{\varepsilon}{\eta}\|(\widehat{x}^{k},\widehat{v}^{k})-(\bar{x},0)\|\leq\varepsilon\|x^{k}-\bar{x}\|$

when $k$ is sufficiently large. This means that the quotient
$\|x^{k+1}-\bar{x}\|/\|x^{k}-\bar{x}\|$ converges to $0$ as $k\to\infty$,
which completes the proof of the theorem.

We conclude this section with the brief discussion on the semismooth∗ Newton
method developed by Gfrerer and Outrata in [9] to solve set-valued inclusions
involving the subgradient systems (3.1).

######  Remark 3.8 (comparison with the semismooth∗ Newton method and its
variants).

The method in [9] addresses solving the inclusion $0\in F(x)$, where $F:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ is a set-valued mapping of closed
graph. When $F:=\partial\varphi$ with $\varphi:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ being an l.s.c. function, the latter
inclusion reduces to (3.1). The underlying difference between our approach and
the semismooth∗ Newton method in [9] is in finding the generalized Newton
directions. To be more specific, the directions $d^{k}$ in the semismooth∗
Newton-type method is given by

$d^{k}:=-A^{-1}B\widehat{v}^{k},\quad k=0,1,\ldots,$ (3.19)

where $(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm gph}\,\partial\varphi$ is
selected for each $k$ from (3.5), and where the matrices $A,B\in{\rm
I\\!R}^{n\times n}$ are generated as follows. Choose
$(v_{i}^{*},u_{i}^{*})\in\mbox{\rm
gph}\,D^{*}\partial\varphi(\widehat{x}^{k},\widehat{v}^{k})$ such that the
$i$th rows of $A$ and $B$ are $u_{i}^{*}$ and $v_{i}^{*}$, respectively, and
that $A$ is nonsingular. It is known that the computation cost to generate the
matrices $A$ and $B$ in (3.19) and solve the system of linear equations
$Ad=-B\widehat{v}^{k}$ to find $d^{k}$ in (3.19) is expensive. This is not
required in finding directions in Algorithm 1. Moreover, in [9] the
semismooth∗ Newton method was only guaranteed to converge under the assumption
of strong metric regularity, while Theorem 3.7 shows that the local
superlinear convergence of Algorithm 1 holds under merely metric regularity,
which is a less restrictive condition. To overcome this disadvantage of the
semismooth∗ Newton method, one of the possible ideas developed by Gfrerer and
Outrata in the recent paper [10] is to generate generalized Newton directions
via using SCD (subspace containing derivative) mappings instead of
coderivatives. This adaption requires a certain SCD regularity, which is
weaker than the metric regularity of the subgradient mapping
$\partial\varphi$. However, calculus rules for SCD mappings are more limited
in comparison with the extensive calculus available for coderivatives.

##  4 Local Convergence Analysis of Coderivative-Based Newton Method for
Structured Nonconvex Optimization

As discussed in Section 3, Algorithm 1 offers a variety of possibilities to
implement the approximate step. In this section, we present a way to choose
the pair $(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm gph}\,\partial\varphi$
in the approximate step of Algorithm 1 for solving the class of nonsmooth
nonconvex optimization problems of the type

$\mbox{\rm minimize}\quad\varphi(x):=f(x)+g(x)\quad\text{subject to
}\;x\in{\rm I\\!R}^{n},$ (4.1)

where $f:{\rm I\\!R}^{n}\to{\rm I\\!R}$ is a $\mathcal{C}^{2}$-smooth
function, and where $g:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is a proper
extended-real-valued l.s.c. and prox-bounded function with threshold
$\lambda_{g}\in(0,\infty]$. We start with the corresponding definitions needed
in what follows.

######  Definition 4.1 (prox-gradient and normal maps).

Let $\varphi$ be given in (4.1). For each $\lambda\in(0,\lambda_{g})$, define
the following multifunctions:

(i) The prox-gradient map $\mathcal{G}_{\lambda}:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ associated with (4.1) is given by

$\mathcal{G}_{\lambda}(x):=\text{\rm Prox}_{\lambda g}\big{(}x-\lambda\nabla
f(x)\big{)},\quad x\in{\rm I\\!R}^{n}.$ (4.2)

(ii) The normal map $\mathcal{F}_{\lambda}^{\text{\rm nor}}:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ associated with (4.1) is given by

$\mathcal{F}_{\lambda}^{\text{\rm nor}}(x):=\Big{\\{}\nabla
f(\widehat{x})+\frac{1}{\lambda}(x-\widehat{x})\;\Big{|}\;\widehat{x}\in\text{\rm
Prox}_{\lambda g}(x)\Big{\\}},\quad x\in{\rm I\\!R}^{n}.$ (4.3)

When the proximal mapping $\text{\rm Prox}_{\lambda g}$ is single-valued, the
normal map (4.3) can be written as

$\mathcal{F}_{\lambda}^{\text{\rm nor}}(x)=\nabla f\big{(}\text{\rm
Prox}_{\lambda g}(x)\big{)}+\frac{1}{\lambda}\big{(}x-\text{\rm Prox}_{\lambda
g}(x)\big{)},\quad x\in{\rm I\\!R}^{n}.$ (4.4)

The terminology “normal map” goes back to variational inequalities being
useful there for characterizing solution sets; see, e.g., [7]. In the setting
of variational inequalities

$\text{find }\bar{x}\in\Omega\;\text{ such that }\;\langle
F(\bar{x}),x-\bar{x}\rangle\geq 0\;\mbox{ for all }\;x\in\Omega,$ (4.5)

where $F:{\rm I\\!R}^{n}\to{\rm I\\!R}^{n}$ is a single-valued operator, and
where $\Omega$ is a closed and convex set, the normal map associated with
(4.5) is defined by

$\mathcal{F}^{\text{\rm
nor}}(x):=F\big{(}\Pi_{\Omega}(x)\big{)}+x-\Pi_{\Omega}(x),\quad x\in{\rm
I\\!R}^{n}.$ (4.6)

Note that both normal maps in (4.3) and (4.6) agree when $F:=\nabla f$,
$g:=\delta_{\Omega}$, and $\lambda=1$. Various error bounds for variational
inequalities based on the normal map (4.6) can be found in the book [7] and
the references therein, while new ones by using this normal map have been
recently derived in [14] for the class of strongly pseudomonotone variational
inequalities. To the best of our knowledge, the concept of normal maps defined
in (4.3) for the structured nonconvex optimization problems (4.1) is firstly
introduced in this paper. We’ll see that the normal map (4.3) plays a crucial
role in designing and justifying our new generalized Newton and line-search
methods in this section and in the subsequent Sections 5 and 6 as well.

Observe further that the stationarity condition
$0\in\partial\varphi(\bar{x})$, where $\varphi$ is given in form (4.1), is
only a necessary condition for the optimality of $\bar{x}$, and it is
sufficient if $\varphi$ is convex. In what follows, we define different
concepts of stationary and critical points for the function $\varphi$ of type
(4.1) along the lines of general optimization theory.

######  Definition 4.2 (stationary and critical points).

Let $\bar{x}\in\mbox{\rm dom}\,\varphi$ for $\varphi$ given in (4.1). Then
$\bar{x}$ is:

(i) F$($réchet$)$-stationary point if
$0\in\widehat{\partial}\varphi(\bar{x})$.

(ii) M$($ordukhovich$)$-stationary point if $0\in{\partial}\varphi(\bar{x})$.

(iii) Critical point if $\bar{x}\in\mathcal{G}_{\lambda}(\bar{x})$ for some
$\lambda\in(0,\lambda_{g})$.

######  Remark 4.3.

If $\bar{x}$ is a critical point of (4.1), then $\bar{x}$ is a F-stationary
(and hence M-stationary) point. Indeed, we have from the critical point
definition that

$\bar{x}\in\text{\rm
argmin}\Big{\\{}g(x)+\frac{1}{2\lambda}\|x-\bar{x}+\lambda\nabla
f(\bar{x})\|^{2}\;\Big{|}\;x\in{\rm I\\!R}^{n}\Big{\\}}.$

It then follows from [25, Proposition 1.114] that

$0\in\widehat{\partial}g(\bar{x})+\frac{1}{\lambda}\big{(}\bar{x}-\bar{x}+\lambda\nabla
f(\bar{x})\big{)}=\nabla
f(\bar{x})+\widehat{\partial}g(\bar{x})=\widehat{\partial}\varphi(\bar{x})\subset\partial\varphi(\bar{x}).$

If $f$ and $g$ are convex and $\bar{x}$ is a critical point of (4.1), then
$\bar{x}$ is an optimal solution to (4.1). The proof of this statement can be
found in [3, Corollary 27.3].

Next we show that the criticality of $\bar{x}$ is a necessary optimality
condition for the structured nonconvex optimization problem (4.1). Looking for
local minimizers of (4.1), our attention can be restricted to points nearby
the optimal solution.

######  Proposition 4.4 (necessary optimality condition for nonconvex
optimization problems).

Let $\varphi$ be given in (4.1), and let $\bar{x}$ be a global optimal
solution to problem (4.1). Suppose further that $\nabla f$ is Lipschitz
continuous around $\bar{x}$ with modulus $L_{f}>0$. Then $\bar{x}$ is a
critical point of (4.1), and $\mathcal{G}_{\lambda}$ is single-valued at
$\bar{x}$ for any $\lambda\in(0,\text{\rm min}\\{1/L_{f},\lambda_{g}\\})$.

[Proof.] Fix $\lambda\in(0,\lambda_{g})$. Since $g$ is prox-bounded with
threshold $\lambda_{g}$, we have that $\text{\rm Prox}_{\lambda
g}(\bar{x}-\lambda\nabla f(\bar{x}))$ is a nonempty set by Proposition 2.2.
Supposing without loss of generality that $\bar{x}$ is a global solution to
(4.1) and picking an arbitrary element of $\widehat{x}$ of this set, we intend
to show that $\widehat{x}=\bar{x}$. Indeed, the Lipschitz continuity of
$\nabla f$ ensures by the descent lemma in [13, Lemma A.11] that

$f(\widehat{x})\leq f(\bar{x})+\langle\nabla
f(\bar{x}),\widehat{x}-\bar{x}\rangle+\frac{L_{f}}{2}\|\widehat{x}-\bar{x}\|^{2}.$
(4.7)

Taking into account that $\widehat{x}\in\text{\rm Prox}_{\lambda
g}(\bar{x}-\lambda\nabla f(\bar{x}))$, we have the estimate

$g(\widehat{x})+\frac{1}{2\lambda}\|\widehat{x}-(\bar{x}-\lambda\nabla
f(\bar{x}))\|^{2}\leq
g(\bar{x})+\frac{1}{2\lambda}\|\bar{x}-(\bar{x}-\lambda\nabla
f(\bar{x}))\|^{2}=g(\bar{x})+\frac{\lambda}{2}\|\nabla f(\bar{x})\|^{2}.$
(4.8)

Since $\bar{x}$ is an optimal solution to (4.1) and $g$ is proper, it tells us
that $g(\bar{x})$ is finite, and so is $g(\widehat{x})$ by (4.8). Combining
(4.7) and (4.8) provides the conditions

$\displaystyle f(\widehat{x})+g(\widehat{x})$ $\displaystyle\leq
f(\bar{x})+\langle\nabla
f(\bar{x}),\widehat{x}-\bar{x}\rangle+\frac{L_{f}}{2}\|\widehat{x}-\bar{x}\|^{2}+g(\widehat{x})$
$\displaystyle=f(\bar{x})+g(\widehat{x})+\frac{1}{2\lambda}\|\widehat{x}-(\bar{x}-\lambda\nabla
f(\bar{x}))\|^{2}-\frac{\lambda}{2}\|\nabla
f(\bar{x})\|^{2}+\left(\frac{L_{f}}{2}-\frac{1}{2\lambda}\right)\|\widehat{x}-\bar{x}\|^{2}$
$\displaystyle\leq
f(\bar{x})+g(\bar{x})+\left(\frac{L_{f}}{2}-\frac{1}{2\lambda}\right)\|\widehat{x}-\bar{x}\|^{2}\leq
f(\widehat{x})+g(\widehat{x})+\left(\frac{L_{f}}{2}-\frac{1}{2\lambda}\right)\|\widehat{x}-\bar{x}\|^{2},$

which ensure that $\|\widehat{x}-\bar{x}\|^{2}\leq 0$, and thus
$\widehat{x}=\bar{x}$. Since $\widehat{x}$ was chosen arbitrarily, the set
$\text{\rm Prox}_{\lambda g}(\bar{x}-\lambda\nabla f(\bar{x}))$ is a
singleton, and $\bar{x}$ is its unique element as claimed.

Unifying Remark 4.3 and Proposition 4.4, we have the relationships

$\text{optimal solution}\Longrightarrow\text{critical
point}\Longrightarrow\text{F-stationary
point}\Longrightarrow\text{M-stationary point}.$

To proceed further, we involve the normal maps (4.3) to characterize critical
points.

######  Proposition 4.5 (characterization of critical points via normal maps).

Let $\varphi$ be given in (4.1). Then for each $\lambda\in(0,\lambda_{g})$,
the following assertions hold:

(i) If $\bar{x}$ is a critical point of (4.1), then
$0\in\mathcal{F}_{\lambda}^{\text{\rm nor}}(\bar{x}-\lambda\nabla
f(\bar{x}))$.

(ii) If $\nabla f$ is Lipschitz continuous around $\bar{x}$ with modulus
$L_{f}>0$ and if $0\in\mathcal{F}_{\lambda}^{\text{\rm
nor}}(\bar{x}-\lambda\nabla f(\bar{x}))$ with $\lambda\in(0,1/L_{f})$, then
$\bar{x}$ is a critical point of (4.1).

[Proof.] To verify (i), we have by the criticality $\bar{x}$ in (4.1) that
$\bar{x}\in\mathcal{G}_{\lambda}(\bar{x})$, which yields

$0=\nabla f(\bar{x})+\frac{1}{\lambda}\big{(}\bar{x}-\lambda\nabla
f(\bar{x})-\bar{x}\big{)}\in\mathcal{F}_{\lambda}^{\text{\rm
nor}}\big{(}\bar{x}-\lambda\nabla f(\bar{x})\big{)}.$

To prove (ii), deduce from $0\in F_{\lambda}^{\text{\rm
nor}}(\bar{x}-\lambda\nabla f(\bar{x}))$ that there exists
$\widehat{x}\in\mathcal{G}_{\lambda}(\bar{x})$ satisfying

$0=\nabla f(\widehat{x})+\frac{1}{\lambda}\big{(}\bar{x}-\lambda\nabla
f(\bar{x})-\widehat{x}\big{)}=\nabla f(\widehat{x})-\nabla
f(\bar{x})+\frac{1}{\lambda}(\bar{x}-\widehat{x}).$ (4.9)

Due to the Lipschitz continuity of $\nabla f$ with modulus $L_{f}>0$ around
$\bar{x}$, it follows from (4.9) that

$\frac{1}{\lambda}\|\widehat{x}-\bar{x}\|=\|\nabla f(\widehat{x})-\nabla
f(\bar{x})\|\leq L_{f}\|\widehat{x}-\bar{x}\|,$ (4.10)

which tells us by $0<\lambda<1/L_{f}$ that $\|\widehat{x}-\bar{x}\|=0$, i.e.,
$\widehat{x}=\bar{x}$. Thus we get $\bar{x}\in\mathcal{G}_{\lambda}(\bar{x})$.

The next proposition allows us to generate a point in the graph of the
subgradient mapping for $\varphi$ in (4.1) directly from the prox-gradient
(4.2) and normal (4.3) maps. It plays a crucial role in designing and
justifying our new algorithm below in this section.

######  Proposition 4.6 (generating elements of subgradient graphs).

Let $\varphi$ be given in (4.1). For each $\lambda\in(0,\lambda_{g})$ and
$x\in{\rm I\\!R}^{n}$, take $\widehat{x}\in\mathcal{G}_{\lambda}(x)$ and
denote

$\widehat{v}:=\nabla f(\widehat{x})-\nabla
f(x)+\frac{1}{\lambda}(x-\widehat{x}).$

Then we have $\widehat{v}\in\mathcal{F}_{\lambda}^{\text{\rm
nor}}(x-\lambda\nabla f(x))$ and $(\widehat{x},\widehat{v})\in\mbox{\rm
gph}\,\widehat{\partial}\varphi$.

[Proof.] The first inclusion follows immediately from the definition of the
prox-gradient and normal maps. To verify the second one, deduce from
$\widehat{x}\in\mathcal{G}_{\lambda}(x)$ that

$\widehat{x}\in\text{\rm
argmin}\Big{\\{}g(u)+\frac{1}{2\lambda}\|u-x+\lambda\nabla
f(x)\|^{2}\;\Big{|}\;u\in{\rm I\\!R}^{n}\Big{\\}}.$

It follows from the elementary calculus rules for regular subgradients [26,
Proposition 1.30] that

$0\in\widehat{\partial}g(\widehat{x})+\frac{1}{\lambda}\big{(}\widehat{x}-x+\lambda\nabla
f(x)\big{)}=\nabla
f(x)+\widehat{\partial}g(\widehat{x})+\frac{1}{\lambda}(\widehat{x}-x),$

which implies in turn that

$\widehat{v}=\nabla f(\widehat{x})-\nabla
f(x)+\frac{1}{\lambda}(x-\widehat{x})\in\nabla
f(\widehat{x})+\widehat{\partial}g(\widehat{x})=\widehat{\partial}\varphi(\widehat{x}),$

and thus completes the proof of the proposition.

Now we involve the prox-regularity of the regularizer in (4.1), which allows
us to justify the single-valuedness of the prox-gradient and normal maps.

######  Proposition 4.7 (single-valuedness of prox-gradient and normal maps).

Let $\bar{x}$ be a critical point of (4.1), and let $g$ be prox-regular with
modulus $r>0$ at $\bar{x}$ for $-\nabla f(\bar{x})$. Then for each
$\lambda\in(0,r^{-1})$, there exists a neighborhood $U$ of $\bar{x}$ on which
the maps $x\mapsto\mathcal{G}_{\lambda}(x)$ and
$x\mapsto\mathcal{F}_{\lambda}^{\text{\rm nor}}(x-\lambda\nabla f(x))$ are
single-valued and Lipschitz continuous on $U$. Moreover, we find
$\eta_{1},\eta_{2}>0$ such that

$\|\mathcal{G}_{\lambda}(x)-\bar{x}\|\leq\eta_{1}\|x-\bar{x}\|\;\text{ and
}\;\|\mathcal{F}_{\lambda}^{\text{\rm nor}}(x-\lambda\nabla
f(x))\|\leq\eta_{2}\|x-\bar{x}\|\;\text{ for all }\;x\in U.$ (4.11)

[Proof.] Since $f$ is a $\mathcal{C}^{2}$-smooth function, there exists a
neighborhood $\widetilde{U}$ of $\bar{x}$ such that $\nabla f$ is Lipschitz
continuous on $\widetilde{U}$. It follows from Lemma 2.3 that the proximal
mapping $\text{\rm Prox}_{\lambda g}$ is single-valued and locally
Lipschitzian on a neighborhood $U_{\lambda}$ of $\bar{x}-\lambda\nabla
f(\bar{x})$ and that $\text{\rm Prox}_{\lambda g}(\bar{x}-\lambda\nabla
f(\bar{x}))=\bar{x}$. Choose further a neighborhood $U\subset\widetilde{U}$ of
$\bar{x}$ so that

$(I-\lambda\nabla f)(U)\subset U_{\lambda}\;\text{and }\;\text{\rm
Prox}_{\lambda g}\big{(}(I-\lambda\nabla f)(U)\big{)}\subset\widetilde{U},$
(4.12)

which implies that the prox-gradient map $\mathcal{G}_{\lambda}$ is single-
valued and Lipschitz continuous on $U$. By (4.4) and (4.12), the normal map
$x\mapsto\mathcal{F}_{\lambda}^{\text{\rm nor}}(x-\lambda\nabla f(x))$ is
single-valued satisfying the equality

$\mathcal{F}_{\lambda}^{\text{\rm nor}}\big{(}x-\lambda\nabla
f(x)\big{)}=\nabla f\big{(}\mathcal{G}_{\lambda}(x)\big{)}-\nabla
f(x)+\frac{1}{\lambda}\big{(}x-\mathcal{G}_{\lambda}(x)\big{)}\;\mbox{ for all
}\;x\in U,$ (4.13)

which also implies that this map is Lipschitz continuous on $U$.

To verify further (4.11), let $\ell>0$ and $L>0$ be Lipschitz moduli of
$\mathcal{G}_{\lambda}$ and $\nabla f$ on $U$ and $\widetilde{U}$,
respectively. Since $\mathcal{G}_{\lambda}(\bar{x})=\bar{x}$, for each $x\in
U$ we have

$\|\mathcal{G}_{\lambda}(x)-\bar{x}\|=\|\mathcal{G}_{\lambda}(x)-\mathcal{G}_{\lambda}(\bar{x})\|\leq\ell\|x-\bar{x}\|,$

which gives us the first estimate in (4.11) with $\eta_{1}:=\ell$. To verify
the second estimate therein, for each $x\in U$ we deduce from (4.12) that
$\mathcal{G}_{\lambda}(x)\in\widetilde{U}$. The Lipschitz continuity of
$\nabla f$ with modulus $L>0$ on $\widetilde{U}$ leads us to the relationships

$\displaystyle\big{\|}\mathcal{F}_{\lambda}^{\text{\rm
nor}}\big{(}x-\lambda\nabla f(x)\big{)}\big{\|}$ $\displaystyle=\big{\|}\nabla
f\big{(}\mathcal{G}_{\lambda}(x)\big{)}-\nabla
f(x)+\frac{1}{\lambda}\big{(}x-\mathcal{G}_{\lambda}(x)\big{)}\big{\|}$
$\displaystyle\leq\big{\|}\nabla
f\big{(}\mathcal{G}_{\lambda}(x)\big{)}-\nabla
f(x)\big{\|}+\frac{1}{\lambda}\big{\|}x-\mathcal{G}_{\lambda}(x)\big{\|}\leq\big{(}L+\frac{1}{\lambda}\big{)}\|\mathcal{G}_{\lambda}(x)-x\|$
$\displaystyle\leq\big{(}L+\frac{1}{\lambda}\big{)}\big{(}\|\mathcal{G}_{\lambda}(x)-\bar{x}\|+\|x-\bar{x}\|\big{)}\leq\big{(}L+\frac{1}{\lambda}\big{)}(1+\ell)\|x-\bar{x}\|,$

which justify the second estimate in (4.11) with
$\eta_{2}:=(L+\lambda^{-1})(1+\ell)$.

The obtained Proposition 4.7 immediately provides the justification of the
approximate step in the version of Algorithm 1 for the structured optimization
model (4.1).

######  Corollary 4.8 (approximate step in structured nonconvex optimization).

In the setting of Proposition 4.7, for each $\lambda\in(0,r^{-1})$ there exist
$\eta>0$ and a neighborhood $U$ of $\bar{x}$ such that whenever $x\in U$, we
get $(\widehat{x},\widehat{v})\in\mbox{\rm gph}\,\partial\varphi$ satisfying

$\|(\widehat{x},\widehat{v})-(\bar{x},0)\|\leq\eta\|x-\bar{x}\|,$

where the approximation vectors $\widehat{x}$ and $\widehat{v}$ are selected
by

$\widehat{x}:=\mathcal{G}_{\lambda}(x)\;\text{ and
}\;\widehat{v}:=\mathcal{F}_{\lambda}^{\text{\rm nor}}(x-\lambda\nabla f(x)).$

Let us now discuss how to implement the approximate step in Algorithm 1 for
solving the structured optimization problem (4.1). The simplest way to choose
$(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm gph}\,\partial\varphi$ in
Algorithm 1 is

$\widehat{x}^{k}:=x^{k}\;\text{ and
}\;\widehat{v}^{k}\in\partial\varphi(x^{k}).$

The difficulty in the above choice is that we cannot guarantee that
$\partial\varphi(x)$ is nonempty for an arbitrary $x\in{\rm I\\!R}^{n}$. The
alternative way is choosing $\widehat{x}^{k}$ and $\widehat{v}^{k}$ as in
(3.7). However, one of the difficulties here is to compute exactly the
proximal mapping of $\varphi$, which is the sum of two nonconvex functions.
Thanks to Proposition 4.6 and Corollary 4.8, we can choose $\widehat{x}^{k}$
and $\widehat{v}^{k}$ as follows:

$\widehat{x}^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla
f(x^{k})),\text{ and }\widehat{v}^{k}:=\nabla f(\widehat{x}^{k})-\nabla
f(x^{k})+\frac{1}{\lambda}(x^{k}-\widehat{x}^{k}).$ (4.14)

Note that $\widehat{x}^{k}$ and $\widehat{v}^{k}$ in (4.14) are always well-
defined since $\text{\rm Prox}_{\lambda g}(x)$ is nonempty for any $x\in{\rm
I\\!R}^{n}$ due to the prox-boundedness of $g$. Moreover, (4.14) requires to
know the proximal mapping only for the regularizer $g$ (not for the whole
function $\varphi$ in (4.1)), which is often easy to compute. The
corresponding Newton algorithm using the choice (4.14) is formulated as
follows.

Algorithm 2 (coderivative-based pure Newton algorithm for structured
optimization)

1:$x^{0}\in{\rm I\\!R}^{n}$, $\lambda>0$

2:for $k=0,1,\ldots$ do

3: If $x^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla f(x^{k}))$,
stop; otherwise go to the next step

4: Define $\widehat{x}^{k}$ and $\widehat{v}^{k}$ by
$\widehat{x}^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla
f(x^{k})),\quad\widehat{v}^{k}:=\nabla f(\widehat{x}^{k})-\nabla
f(x^{k})+\frac{1}{\lambda}(x^{k}-\widehat{x}^{k})$ (4.15)

5: Newton step: Choose $d^{k}\in{\rm I\\!R}^{n}$ satisfying
$-\widehat{v}^{k}-\nabla^{2}f(\widehat{x}^{k})d^{k}\in\partial^{2}g(\widehat{x}^{k},\widehat{v}^{k}-\nabla
f(\widehat{x}^{k})(d^{k})$ (4.16)

6: Set $x^{k+1}:=\widehat{x}^{k}+d^{k}$

7:end for

######  Remark 4.9 (on the iterative sequence generated by Algorithm 2).

Proposition 4.6 and Corollary 4.8 allow us to show that Algorithm 2 is a
special case of the general scheme proposed in Algorithm 1. Indeed, Remark 4.3
tells us that the condition in Step 2 of Algorithm 2 implies that
$0\in\partial\varphi(x^{k})$. Moreover, by Proposition 4.6 and the
constructions of $\\{\widehat{x}^{k}\\}$ and $\\{\widehat{v}^{k}\\}$ in
Algorithm 2, we have that $(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm
gph}\,\partial\varphi$. Then Corollary 4.8 ensures that

$\|(\widehat{x}^{k},\widehat{v}^{k})-(\bar{x},0)\|\leq\eta\|x^{k}-\bar{x}\|$

whenever $x^{k}$ is near $\bar{x}$. This means that the choice of
$(\widehat{x}^{k},\widehat{v}^{k})$ in Algorithm 2 satisfies the approximate
step of Algorithm 1. The Newton step of Algorithm 2 can be written as

$-\widehat{v}^{k}\in\nabla^{2}f(\widehat{x}^{k})d^{k}+\partial^{2}g\big{(}\widehat{x}^{k},\widehat{v}^{k}-\nabla
f(\widehat{x}^{k})\big{)}(d^{k}),$

which is equivalent to
$-\widehat{v}^{k}\in\partial^{2}\varphi(\widehat{x}^{k},\widehat{v}^{k})(d^{k})$
by the second-order sum rule from [25, Proposition 1.121]. Therefore,
Algorithm 2 can be viewed as a specification of Algorithm 1 with
$\varphi=f+g$.

The next theorem establishes the well-posedness and local superlinear
convergence of iterates in Algorithm 2 under fairly general assumptions.

######  Theorem 4.10 (local superlinear convergence of the coderivative-based
pure Newton algorithm).

Let $\bar{x}$ be a critical point of (4.1) for which $\nabla f+\partial g$ is
metrically regular around $(\bar{x},0)$ and $\partial g$ is semismooth∗ at
$(\bar{x},-\nabla f(\bar{x}))$. Suppose further that Assumption 1 is satisfied
and that $g$ is continuously prox-regular at $\bar{x}$ for $-\nabla
f(\bar{x})$ with modulus $r>0$. Then for $\lambda\in(0,r^{-1})$, there exists
a neighborhood $U$ of $\bar{x}$ such that for all $x^{0}\in U$ we have that
Algorithm 2 either stops after finitely many iterations, or produces a
sequence $\\{x^{k}\\}$ that converges $Q$-superlinearly to $\bar{x}$.

[Proof.] The limiting subdifferential sum rule from [25, Proposition 1.107]
tells us that

$\partial\varphi(x)=\nabla f(x)+\partial g(x)\;\text{ for all }\;x\in{\rm
I\\!R}^{n},$

which ensures by the assumptions made that $\partial\varphi$ is metrically
regular around $(\bar{x},0)$, and semismooth∗ at this point due to [9,
Proposition 3.6]. It follows from Remark 4.9 that Algorithm 2 reduces to
Algorithm 1 with $\varphi=f+g$. Therefore, all the assumptions of Theorem 3.7
are satisfied, and thus we are done with the proof of this theorem.

######  Remark 4.11.

In our previous paper [18], we proposed and justified the local superlinear
convergence of the coderivative-based Newton algorithm in [18, Algorithm 7.1])
to solve (4.1) in the case where $f$ is a quadratic function and $g$ is
continuously prox-regular around the reference point. The aforementioned
algorithm in [18] is a special case of the new Algorithm 2. Let us emphasize
that now we don’t require as that $f$ is quadratic, which was a serious
restriction in [18] essential in the proof therein.

##  5 Generalized Line Search Proximal Gradient Method

In the line of the classical pure Newton method, the generalized one from
Section 4 provides fast convergence when the iterative sequence is near the
solution point. To get its globalization that converges for any starting point
in ${\rm I\\!R}^{n}$ in the nonconvex composite optimization problem (4.1), a
natural approach is to replace Step 5 in Algorithm 2 by a damped step of the
form

$x^{k+1}:=\widehat{x}^{k}+\tau_{k}d^{k}$ (5.1)

with an appropriate stepsize selection $\tau_{k}\in(0,1]$. To accomplish this,
we develop in this section a new line search method based on the forward-
backward envelope (FBE) $\varphi_{\lambda}$ of the function $\varphi$ from
(4.1), which is defined below to guarantee the descent property at each
iteration, i.e.,

$\varphi_{\lambda}(\widehat{x}^{k}+\tau_{k}d^{k})<\varphi_{\lambda}(x^{k}),\quad
k=0,1,\ldots.$ (5.2)

To be more specific, we employ the construction of FBE introduced by Patrinos
and Bemporad [30] for convex composite functions and then largely used to
design numerical methods in various composite frameworks of optimization as,
e.g., in [21, 27, 33, 34] with the references therein. In general, the FBE
$\varphi_{\lambda}$ approximates $\varphi$ from below while linearizing the
smooth part of the function $\varphi$ in (4.1); see (5.3)). This construction
plays a crucial role in developing our new line search method to guarantee the
global convergence of our generalized coderivative-based Newton method
presented in Section 6.

######  Definition 5.1 (forward-backward envelopes).

Let $\varphi$ be given in (4.1). The forward-backward envelope $($FBE$)$ of
$\varphi$ with the parameter value $\lambda>0$ is given by

$\varphi_{\lambda}(x):=\inf_{y\in{\rm I\\!R}^{n}}\Big{\\{}f(x)+\langle\nabla
f(x),y-x\rangle+g(y)+\frac{1}{2\lambda}\|y-x\|^{2}\Big{\\}}.$ (5.3)

The following properties are clearly implied by the definition.

(i) $\varphi_{\lambda}(x)\leq\varphi(x)$ for all $x\in{\rm I\\!R}^{n}$.

(ii) For each $x\in{\rm I\\!R}^{n}$, $\lambda\in(0,\lambda_{g})$, and
$\widehat{x}\in\mathcal{G}_{\lambda}(x)$ we have

$\varphi_{\lambda}(x)=f(x)+\langle\nabla
f(x),\widehat{x}-x\rangle+g(\widehat{x})+\frac{1}{2\lambda}\|\widehat{x}-x\|^{2},$
(5.4)

where $\mathcal{G}_{\lambda}$ is defined in (4.2). Furthermore, FBE (5.3) can
be equivalently written as

$\varphi_{\lambda}(x)=f(x)-\frac{\lambda}{2}\|\nabla
f(x)\|^{2}+e_{\lambda}g\big{(}x-\lambda\nabla f(x)\big{)}.$ (5.5)

Recall from [18, Proposition 7.1] that the fairly mild assumptions ensure that
the FBE $\varphi_{\lambda}$ is ${\cal C}^{1}$-smooth with the explicit
calculation of its gradient and the preservation of stationary points of
$\varphi$

######  Proposition 5.2 (smoothness of FBE and stationary points).

Let $f$ be of class $\mathcal{C}^{2}$ around $\bar{x}$ where
$0\in\partial\varphi(\bar{x})$, and let $g$ be prox-bounded and continuously
prox-regular at $\bar{x}$ for $-\nabla f(\bar{x})$ with modulus $r>0$. Then
for all $\lambda\in(0,r^{-1})$ there exists a neighborhood $U$ of $\bar{x}$ on
which the FBE $\varphi_{\lambda}$ is continuously differentiable and its
gradient mapping is calculated by

$\nabla\varphi_{\lambda}(x)=\lambda^{-1}\big{(}I-\lambda\nabla^{2}f(x)\big{)}\big{(}x-\text{\rm
Prox}_{\lambda g}(x-\lambda\nabla f(x))\big{)}.$ (5.6)

Moreover, if $I-\lambda\nabla^{2}f(x)$, with the identity matrix $I$, is
nonsingular for $x\in U$, we have the equivalence

$\nabla\varphi_{\lambda}(x)=0\iff 0\in\partial\varphi(x).$ (5.7)

If in addition $g$ is convex, then $\lambda$ above can be chosen arbitrarily
in $(0,\infty)$.

######  Remark 5.3 (on nonsingularity of the shifted matrix and
$\mathcal{C}^{1,1}$-smoothness of FBE).

(i) We can guarantee the nonsingularity of the shifted matrix
$I-\lambda\nabla^{2}f(x)$ in Proposition 5.2 if assume in addition that
$\nabla f$ is Lipschitz continuous on ${\rm I\\!R}^{n}$ with modulus $L_{f}>0$
and that $\lambda\in(0,1/L_{f})$. Indeed, the Lipschitz continuity of $\nabla
f$ with modulus $L_{f}>0$ implies that the matrix $L_{f}I-\nabla^{2}f(x)$ is
positive-semidefinite for all $x\in{\rm I\\!R}^{n}$. Therefore, the matrix
$I-\lambda\nabla^{2}f(x)$ is positive-definite for all $x\in{\rm I\\!R}^{n}$
by the choice of $\lambda\in(0,1/L_{f})$. In this case, it follows from (5.6)
that

$\nabla\varphi_{\lambda}(x)=0\iff x=\text{\rm Prox}_{\lambda
g}\big{(}x-\lambda\nabla f(x)\big{)}.$ (5.8)

(ii) Thev FBE $\varphi_{\lambda}$ is of class $\mathcal{C}^{1,1}$ around
$\bar{x}$ if the mapping $\nabla^{2}f$ is locally Lipschitzian around
$\bar{x}$. Indeed, Lemma 2.3 tells us that the Moreau envelope $e_{\lambda}g$
is of class $\mathcal{C}^{1,1}$ around $\bar{x}-\lambda\nabla f(\bar{x})$.
Combining this with the formulation of FBE in form (5.5) verifies the claim.

Prior to the design and verification of our new line-search method, we
establish some related auxiliary results, which are certainly of their own
interest. The first lemma provides a precise formula for representing the
generalized Hessian (2.12) of FBE (5.3) at critical points.

######  Lemma 5.4 (second-order subdifferential of FBE at critical points).

Let $\bar{x}\in{\rm I\\!R}^{n}$ be a critical point of $\varphi=f+g$ in (4.1).
Assume that $\nabla^{2}f$ is strictly differentiable at $\bar{x}$ and that
$g\colon{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ is prox-regular at $\bar{x}$
for $-\nabla f(\bar{x})$ with modulus $r>0$. For any $\lambda\in(0,r^{-1})$
such that $Q(\bar{x}):=I-\lambda\nabla^{2}f(\bar{x})$ is nonsingular, we have
the FBE generalized Hessian representation

$\partial^{2}\varphi_{\lambda}(\bar{x})(w)=Q(\bar{x})\nabla^{2}f(\bar{x})w+Q(\bar{x})\partial^{2}e_{\lambda}g\big{(}\bar{z},-\nabla
f(\bar{x})\big{)}\big{(}Q(\bar{x})w\big{)}\;\text{ whenever }\;w\in{\rm
I\\!R}^{n},$ (5.9)

where $\bar{z}:=\bar{x}-\lambda\nabla f(\bar{x})$. Consequently, we get the
equivalence

$z\in\partial^{2}\varphi_{\lambda}(\bar{x})(w)\iff
z\in\partial^{2}\varphi(\bar{x},0)\big{(}w-\lambda
Q(\bar{x})^{-1}z\big{)}\;\text{ for any }\;w\in{\rm I\\!R}^{n}$ (5.10)

provided that $g$ is subdifferentially continuous at $\bar{x}$ for $-\nabla
f(\bar{x})$.

[Proof.] To verify representation (5.9), fix $\bar{x},\bar{z},w,\lambda$ as
above and define the functions $\psi:{\rm I\\!R}^{n}\to{\rm I\\!R}$, $h:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ and the mapping $F:{\rm I\\!R}^{n}\to{\rm
I\\!R}^{n}$ by

$\psi(x):=f(x)-\frac{\lambda}{2}\|\nabla
f(x)\|^{2},\;h(x):=e_{\lambda}g\big{(}F(x)\big{)}\;\text{
with}\;F(x):=x-\lambda\nabla f(x),\quad x\in{\rm I\\!R}^{n}.$

It follows from the differentiability of $\nabla^{2}f$ at $\bar{x}$ that
$\psi$ is twice differentiable at this point. We have by (5.5) that
$\varphi_{\lambda}=\psi+h$, which allows us to apply to this sum the second-
order sum from [25, Proposition 1.121] and thus get

$\partial^{2}\varphi_{\lambda}(\bar{x})(w)=\nabla^{2}\psi(\bar{x})w+\partial^{2}h(\bar{x})(w),\quad
w\in{\rm I\\!R}^{n}.$ (5.11)

The Hessian matrix of $\psi$ is clearly calculated by

$\begin{array}[]{ll}\nabla^{2}\psi(\bar{x})&=\nabla^{2}f(\bar{x})-\lambda\nabla^{2}f(\bar{x})\nabla^{2}f(\bar{x})-\lambda\nabla^{2}\langle\nabla
f(\bar{x}),\nabla f\rangle(\bar{x})\\\
&=Q(\bar{x})\nabla^{2}f(\bar{x})-\lambda\nabla^{2}\langle\nabla
f(\bar{x}),\nabla f\rangle(\bar{x}).\end{array}$ (5.12)

It follows from Proposition 2.3 that $h$ is continuously differentiable at
$\bar{x}$. By using the second-order chain rule from [25, Theorem 1.127], we
have

$\partial^{2}h(\bar{x})(w)=\nabla^{2}\langle\nabla
e_{\lambda}g(\bar{z}),F\rangle(\bar{x})w+Q(\bar{x})\partial^{2}e_{\lambda}g(\bar{z},\nabla
e_{\lambda}g(\bar{z}))(Q(\bar{x})w).$ (5.13)

Since $\bar{x}$ is a critical point of $\varphi$, it follows from (2.20) that

$\nabla e_{\lambda}g(\bar{z})=\frac{1}{\lambda}\big{(}\bar{z}-\text{\rm
Prox}_{\lambda
g}(\bar{z})\big{)}=\frac{1}{\lambda}\big{(}\bar{x}-\lambda\nabla
f(\bar{x})-\text{\rm Prox}_{\lambda g}\big{(}\bar{x}-\lambda\nabla
f(\bar{x})\big{)}\big{)}=-\nabla f(\bar{x}).$ (5.14)

Combining (5.13) and (5.14) gives us the equality

$\partial^{2}h(\bar{x})(w)=\lambda\nabla^{2}\langle\nabla f(\bar{x}),\nabla
f\rangle(\bar{x})w+Q(\bar{x})\partial^{2}e_{\lambda}g\big{(}\bar{z},-\nabla
f(\bar{x})\big{)}\big{(}Q(\bar{x})w\big{)},$ (5.15)

which being combined with (5.11), (5.12), and (5.15) justifies representation
(5.9).

It remains to verify the equivalence in (5.10). To this end, observe from
(5.9) that $z\in\partial^{2}\varphi_{\lambda}(\bar{x})(w)$ if and only if we
have the inclusion

$Q(\bar{x})^{-1}z-\nabla^{2}f(\bar{x})w\in\partial^{2}e_{\lambda}g\big{(}\bar{z},-\nabla
f(\bar{x})\big{)}\big{(}Q(\bar{x})w\big{)}.$

By Lemma 3.5, the above inclusion is equivalent to

$Q(\bar{x})^{-1}z-\nabla^{2}f(\bar{x})w\in\partial^{2}g\big{(}\bar{x},-\nabla
f(\bar{x})\big{)}\big{(}Q(\bar{x})w-\lambda
Q(\bar{x})^{-1}z+\lambda\nabla^{2}f(\bar{x})w\big{)},$

which results in the following one

$Q(\bar{x})^{-1}z-\nabla^{2}f(\bar{x})w\in\partial^{2}g\big{(}\bar{x},-\nabla
f(\bar{x})\big{)}\big{(}w-\lambda Q(\bar{x})^{-1}z\big{)}.$ (5.16)

Applying now the second-order subdifferential sum rule from [25, Proposition
1.121] gives us

$\partial^{2}\varphi(\bar{x},0)\big{(}w-\lambda
Q(\bar{x})^{-1}z\big{)}=\nabla^{2}f(\bar{x})\big{(}w-\lambda
Q(\bar{x})^{-1}z\big{)}+\partial^{2}g\big{(}\bar{x},-\nabla
f(\bar{x})\big{)}\big{(}w-\lambda Q(\bar{x})^{-1}z\big{)}.$ (5.17)

Due to (5.17), the inclusion in (5.16) is equivalent to

$Q(\bar{x})^{-1}z-\nabla^{2}f(\bar{x})w+\nabla^{2}f(\bar{x})\big{(}w-\lambda
Q(\bar{x})^{-1}z\big{)}\in\partial^{2}\varphi(\bar{x},0)\big{(}w-\lambda
Q(\bar{x})^{-1}z\big{)},$

which readily reduces to $z\in\partial^{2}\varphi(\bar{x},0)(w-\lambda
Q(\bar{x})^{-1}z)$ and thus completes the proof.

In the next result, we show that when the cost function in the structured form
(4.1) exhibits the tilt stability at a stationary point, it yields the strong
convexity in its forward-backward envelope around this point. To proceed
further, recall that a set-valued mapping $T:{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ is positive-semidefinite if
$\langle z,u\rangle\geq 0$ for any $u\in{\rm I\\!R}^{n}$ and $z\in T(u)$. If
$\langle z,u\rangle>0$ whenever $u\in{\rm I\\!R}^{n}\setminus\\{0\\}$ and
$z\in T(u)$, then $T$ is said to be positive-definite.

######  Lemma 5.5 (tilt-stable minimizers and strong convexity of FBE).

In the setting of Lemma 5.4, suppose that $g$ is subdifferentially continuous
at $\bar{x}$ for $-\nabla f(\bar{x})$, and let $\lambda\in(0,r^{-1})$ be such
that $Q(\bar{x})=I-\lambda\nabla^{2}f(\bar{x})$ is positive-definite. If
$\bar{x}$ is a tilt-stable local minimizer of the function $\varphi$ in (4.1),
then FBE (5.3) is strongly convex around $\bar{x}$.

[Proof.] It immediately follows from the imposed assumptions that $\varphi$ is
continuously prox-regular at $\bar{x}$ for $0$. Combining this with the
pointbased second-order characterization of tilt stability from [32, Theorem
1.3] gives us the positive-definiteness of $\partial^{2}\varphi(\bar{x},0)$.
Note that the strict differentiability of $\nabla^{2}f$ yields the local
Lipschitz continuity of $\nabla^{2}f$ around $\bar{x}$. Therefore,
$\varphi_{\lambda}$ is of class $\mathcal{C}^{1,1}$ around $\bar{x}$ due to
Remark 5.3(ii). By [4, Proposition 4.6], we verify the strong convexity of
$\varphi_{\lambda}$ around $\bar{x}$ by showing that
$\partial^{2}\varphi_{\lambda}(\bar{x})$ is positive-definite. To furnish
this, pick $w\in{\rm I\\!R}^{n}\setminus\\{0\\}$ and
$z\in\partial^{2}\varphi_{\lambda}(\bar{x})(w)$. Then we deduce from (5.10)
that $z\in\partial^{2}\varphi(\bar{x},0)(w-\lambda Q(\bar{x})^{-1}z)$, which
ensures that $z\neq 0$ by the positive-definiteness of
$\partial^{2}\varphi(\bar{x},0)$. This also implies that $\langle z,w-\lambda
Q(\bar{x})^{-1}z\rangle\geq 0$, and hence

$\langle z,w\rangle\geq\lambda\langle Q(\bar{x})^{-1}z,z\rangle>0$ (5.18)

due to the positive-definiteness of $Q(\bar{x})^{-1}$. In this way, we verify
the positive-definiteness of $\partial^{2}\varphi_{\lambda}(\bar{x})$ and thus
complete the proof of the lemma.

To design and justify our next algorithm for solving the structured
optimization model (4.1), we need the following global Lipschitzian property
of the gradient of $f$ in (4.1).

######  Assumption 2.

$\nabla f$ is Lipschitz continuous on ${\rm I\\!R}^{n}$ with modulus
$L_{f}>0$.

Having this property allows us to design the new line-search method for
solving (4.1) that involves forward-backward envelopes. We label this
algorithm as the generalized line-search proximal gradient method because it
extends the proximal gradient method as explained below in Remark 5.7.

Algorithm 3 (generalized line search proximal gradient method)

1:$x^{0}\in{\rm I\\!R}^{n}$, $\lambda\in(0,\text{\rm
min}\\{1/L_{f},\lambda_{g}\\})$, $\sigma\in\left(0,\frac{\lambda(1-\lambda
L_{f})}{2(1+\lambda L_{f})^{2}}\right)$, $\beta\in(0,1)$

2:for $k=0,1,\ldots$ do

3: If $x^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla f(x^{k}))$,
stop; otherwise go to the next step

4: Define $\widehat{x}^{k}$ and $\widehat{v}^{k}$ by
$\widehat{x}^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla
f(x^{k})),\;\widehat{v}^{k}:=\nabla f(\widehat{x}^{k})-\nabla
f(x^{k})+\frac{1}{\lambda}(x^{k}-\widehat{x}^{k})$

5: Abstract direction step: Select some direction $d^{k}\in{\rm I\\!R}^{n}$
(see specifications below)

6: Set $\tau_{k}=1$

7: while
$\varphi_{\lambda}(\widehat{x}^{k}+\tau_{k}d^{k})>\varphi_{\lambda}(x^{k})-\sigma\left\|\widehat{v}^{k}\right\|^{2}$
do

8: set $\tau_{k}:=\beta\tau_{k}$

9: end while

10: Set $x^{k+1}:=\widehat{x}^{k}+\tau_{k}d^{k}$

11:end for

In the rest of this section, we analyze the well-posedness of Algorithm 3 and
the convergence of its iterates. Our achievements can be summarized as
follows:

$\bullet$ Algorithm 3 is always well-defined (Lemma 5.6), and the proximal
gradient algorithm is a special case of this algorithm (Remark 5.7). That is
the reason why we label Algorithm 3 as a generalized line search proximal
gradient algorithm.

$\bullet$ Every accumulation point of $\\{x^{k}\\}$ generated by Algorithm 3
solves (4.1) (Proposition 5.8).

$\bullet$ If the accumulation point is isolated and directions satisfy an
additional property, the convergence is achieved (Proposition 5.9).

$\bullet$ If the accumulation point satisfies additional assumptions, global
and linear convergence are achieved (Theorem 5.11).

To show that the stepsize $\tau_{k}$ in Algorithm 3 is well-defined, we need
the following lemma.

######  Lemma 5.6 (stepsize in Algorithm 3).

Let Assumption 2 be satisfied in (4.1). For each $\lambda\in(0,\text{\rm
min}\\{1/L_{f},\lambda_{g}\\})$, ${\sigma\in\left(0,\frac{\lambda(1-\lambda
L_{f})}{2(1+\lambda L_{f})^{2}}\right)}$, $d\in{\rm I\\!R}^{n}$, and $x\in{\rm
I\\!R}^{n}$, we define $\widehat{x}$ and $\widehat{v}$ by

$\widehat{x}\in\text{\rm Prox}_{\lambda g}(x-\lambda\nabla f(x))\;\mbox{ and
}\>\widehat{v}:=\nabla f(\widehat{x})-\nabla
f(x)+\frac{1}{\lambda}(x-\widehat{x}).$ (5.19)

If $\widehat{x}\neq x$, then $\widehat{v}\neq 0$ ensuring the estimate

$\varphi_{\lambda}(\widehat{x})<\varphi_{\lambda}(x)-\sigma\|\widehat{v}\|^{2}.$
(5.20)

Consequently, there exists $\bar{\tau}>0$ for which

$\varphi_{\lambda}(\widehat{x}+\tau
d)\leq\varphi_{\lambda}(x)-\sigma\|\widehat{v}\|^{2}\;\text{ whenever
}\;\tau\in(0,\bar{\tau}).$ (5.21)

[Proof.] By Assumption 2, we have the relationships

$\|\widehat{v}\|=\Big{\|}\nabla f(\widehat{x})-\nabla
f(x)+\frac{1}{\lambda}(x-\widehat{x})\Big{\|}\geq\frac{1}{\lambda}\|x-\widehat{x}\|-\|\nabla
f(\widehat{x})-\nabla
f(x)\|\geq\Big{(}\frac{1}{\lambda}-L_{f}\Big{)}\|\widehat{x}-x\|,$ (5.22)
$\|\widehat{v}\|=\Big{\|}\nabla f(\widehat{x})-\nabla
f(x)+\frac{1}{\lambda}(x-\widehat{x})\Big{\|}\leq\|\nabla
f(\widehat{x})-\nabla
f(x)\|+\frac{1}{\lambda}\|x-\widehat{x}\|\leq\Big{(}\frac{1}{\lambda}+L_{f}\Big{)}\|\widehat{x}-x\|.$
(5.23)

It follows from (5.22) that $\widehat{v}\neq 0$ since $x\neq\widehat{x}$. To
verify (5.20), we deduce from (5.4), the Lipschitz continuity of $\nabla f$,
and [13, Lemma A.11] that

$\varphi_{\lambda}(x)=f(x)+\langle\nabla
f(x),\widehat{x}-x\rangle+g(\widehat{x})+\frac{1}{2\lambda}\|\widehat{x}-x\|^{2}\geq
f(\widehat{x})-\frac{L_{f}}{2}\|\widehat{x}-x\|^{2}+g(\widehat{x})+\frac{1}{2\lambda}\|\widehat{x}-x\|^{2},$

which implies in turn that

$\varphi_{\lambda}(x)\geq\varphi(\widehat{x})+\frac{1-\lambda
L_{f}}{2\lambda}\|x-\widehat{x}\|^{2}.$ (5.24)

Combining (5.23) and (5.24) tells us that

$\varphi_{\lambda}(x)\geq\varphi(\widehat{x})+\frac{\lambda(1-\lambda
L_{f})}{2(1+\lambda L_{f})^{2}}\|\widehat{v}\|^{2},$ (5.25)

which being combined with $\widehat{v}\neq 0$ and (5.25) yields

$\varphi_{\lambda}(\widehat{x})\leq\varphi(\widehat{x})\leq\varphi_{\lambda}(x)-\frac{\lambda(1-\lambda
L_{f})}{2(1+\lambda
L_{f})^{2}}\|\widehat{v}\|^{2}<\varphi_{\lambda}(x)-\sigma\|\widehat{v}\|^{2}$

and thus justifies (5.20). It follows from Proposition 2.2 that the prox-
boundedness of $g$ with threshold $\lambda_{g}$ implies the continuity of the
Moreau envelope $e_{\lambda}g$ on ${\rm I\\!R}^{n}$, and hence
$\varphi_{\lambda}$ is also continuous on ${\rm I\\!R}^{n}$ due to (5.5).
Using the latter together with (5.20) verifies (5.21) and completes the proof.

######  Remark 5.7 (relationship with the proximal gradient algorithm).

Note that when $d^{k}:=0$ for all $k\in{\rm I\\!N}$ in Algorithm 3, this
algorithm reduces to the proximal gradient method in which

$x^{k+1}:=\widehat{x}^{k}\in\text{\rm Prox}_{\lambda
g}\big{(}x^{k}-\lambda\nabla f(x^{k})\big{)},\quad k=0,1,\ldots$ (5.26)

Indeed, it follows from $d^{k}=0$ and Lemma 5.6 that

$\varphi_{\lambda}(\widehat{x}^{k}+1\cdot
d^{k})=\varphi_{\lambda}(\widehat{x}^{k})\leq\varphi_{\lambda}(x^{k})-\sigma\|\widehat{v}^{k}\|^{2},$

which implies that $\tau_{k}=1$ for all $k\in{\rm I\\!N}$, and thus we arrive
at (5.26).

Next we show that Algorithm 3 is well-defined and its accumulation points are
critical for (4.1).

######  Proposition 5.8 (well-posedness of Algorithm 3).

Let Assumption 2 hold in (4.1). Then the sequence $\\{x^{k}\\}$ generated by
Algorithm 3 is well-defined, and we have the estimates

$\Big{(}\frac{1}{\lambda}-L_{f}\Big{)}\|\widehat{x}^{k}-x^{k}\|\leq\|\widehat{v}^{k}\|\leq\Big{(}\frac{1}{\lambda}+L_{f}\Big{)}\|\widehat{x}^{k}-x^{k}\|\;\text{
for all }\;k\in{\rm I\\!N}.$ (5.27)

If $\inf\varphi>-\infty$, then the sequence $\\{\varphi_{\lambda}(x^{k})\\}$
is convergent and

$\sum_{k=0}^{\infty}\|\widehat{v}^{k}\|^{2}<\infty,\quad\sum_{k=0}^{\infty}\|\widehat{x}^{k}-x^{k}\|^{2}<\infty.$
(5.28)

Consequently, both sequences $\\{\widehat{v}^{k}\\}$ and
$\\{\widehat{x}^{k}-x^{k}\\}$ converge to $0$ as $k\to\infty$. Finally, any
accumulation point of $\\{x^{k}\\}$ is a critical point of (4.1).

[Proof.] It follows from Lemma 5.6 that Algorithm 3 is well-defined and
exhibits the descent property
$\varphi_{\lambda}(x^{k+1})<\varphi_{\lambda}(x^{k})$. Arguing similarly to
the proof of inequalities (5.22) and (5.23) brings us to (5.27). By [34,
Theorem 4.4], we have $\inf\varphi_{\lambda}=\inf\varphi>-\infty$. Remembering
that the sequence $\\{\varphi_{\lambda}(x^{k})\\}$ is monotonically decreasing
tells us that that $\varphi_{\lambda}(x^{k})\to\inf\varphi_{\lambda}$ as
$k\to\infty$. Moreover,

$\sigma\sum_{i=0}^{k}\|\widehat{v}^{i}\|^{2}\leq\sum_{i=0}^{k}\left[\varphi_{\lambda}(x^{i})-\varphi_{\lambda}(x^{i+1})\right]=\varphi_{\lambda}(x^{0})-\varphi_{\lambda}(x^{k+1})\leq\varphi_{\lambda}(x^{0})-\inf\varphi_{\lambda},$
$\Big{(}\frac{1}{\lambda}-L_{f}\Big{)}^{2}\sum_{i=0}^{k}\|\widehat{x}^{i}-x^{i}\|^{2}\leq\sum_{i=0}^{k}\|\widehat{v}^{i}\|^{2}\leq\frac{1}{\sigma}(\varphi_{\lambda}(x^{0})-\inf\varphi_{\lambda}),$

which justifies (5.28) and ensures that both sequences $\\{\widehat{v}^{k}\\}$
and $\\{\widehat{x}^{k}-x^{k}\\}$ converge to $0$ as $k\to\infty$.

Suppose further that $\bar{x}$ is an accumulation point of $\\{x^{k}\\}$ and
thus find an infinite set $J\subset{\rm I\\!N}$ such that
$x^{k}\overset{J}{\rightarrow}\bar{x}$. By Proposition 2.2, we deduce from the
inclusion $\widehat{x}^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla
f(x^{k}))$ that the sequence $\\{\widehat{x}^{k}\\}_{k\in J}$ is bounded and
that all its accumulation points lie in $\text{\rm Prox}_{\lambda
g}(\bar{x}-\lambda\nabla f(\bar{x}))$. Without loss of generality, assume that
$\widehat{x}^{k}\overset{J}{\rightarrow}\widehat{x}\in\text{\rm Prox}_{\lambda
g}(\bar{x}-\lambda\nabla f(\bar{x}))$. By $\widehat{v}^{k}\to 0$, it yields

$0=\lim_{k\to\infty,k\in J}\|\widehat{v}^{k}\|=\|\nabla
f(\widehat{x})+\lambda^{-1}(\bar{x}-\lambda\nabla f(\bar{x})-\widehat{x})\|,$

which implies in turn that $0\in F_{\lambda}^{\text{\rm
nor}}(\bar{x}-\lambda\nabla f(\bar{x}))$. Using Proposition 4.5, we conclude
that $\bar{x}$ is a critical point of (4.1) and thus complete the proof of the
proposition.

The following proposition verifies the global convergence of the iterates in
Algorithm 3 to an isolated accumulation point under a particular direction
choice.

######  Proposition 5.9 (global convergence to isolated accumulation points).

In the setting of Proposition 5.8, assume that $\bar{x}$ is an isolated
accumulation point of $\\{x^{k}\\}$ in Algorithm 3 with

$\|d^{k}\|\leq\zeta\|\widehat{v}^{k}\|\;\text{ for all large }\;k\in J,$
(5.29)

where $\zeta>0$ is fixed. Then the sequence $\\{x^{k}\\}$ converges to
$\bar{x}$ as $k\to\infty$.

[Proof.] It follows from Proposition 5.8 that $\bar{x}$ is a critical point of
(4.1) with $\widehat{v}^{k}\to 0$ and $\widehat{x}^{k}-x^{k}\to 0$ as
$k\to\infty$. Let a subsequence $\\{x^{k}\\}_{k\in J}$ converge to $\bar{x}$.
For all large $k$, we get from (5.29) that

$\|x^{k+1}-x^{k}\|\leq\|x^{k+1}-\widehat{x}^{k}\|+\|\widehat{x}^{k}-x^{k}\|=\tau_{k}\|d^{k}\|+\|\widehat{x}^{k}-x^{k}\|\leq\zeta\|\widehat{v}^{k}\|+\|\widehat{x}^{k}-x^{k}\|,$

which implies that $\|x^{k+1}-x^{k}\|\overset{J}{\rightarrow}0$. Then we
deduce from the Ostrowski’s condition [7, Proposition 8.3.10] that the entire
sequence $\\{x^{k}\\}$ converges to $\bar{x}$ as $k\to\infty$.

Next we establish convergence rates for Algorithm 3. This requires the
following sufficient conditions, which ensures at least linear convergence
rates.

######  Assumption 3.

Let $\bar{x}$ be a critical point of (4.1). Suppose that:

(i) $\bar{x}$ is a tilt-stable local minimizer of $\varphi$.

(ii) $\nabla^{2}f$ is strictly differentiable at $\bar{x}$.

(iii) $g$ is continuously prox-regular at $\bar{x}$ for $-\nabla f(\bar{x})$
with some modulus $r>0$.

The next lemma taken from [21, Lemma 4] provides conditions for the $R$-linear
and $Q$-linear convergence rates of the iterative sequences.

######  Lemma 5.10 (estimating convergence rates).

Let $\\{\alpha_{k}\\},\;\\{\beta_{k}\\}$, and $\\{\gamma_{k}\\}$ be sequences
of positive numbers. Assume that there are $c_{i}>0$, $i=1,2,3$, and
$k_{0}\in{\rm I\\!N}$ such that for all $k\geq k_{0}$ we have

(i) $\alpha_{k}-\alpha_{k+1}\geq c_{1}\beta_{k}^{2}$.

(ii) $\beta_{k}\geq c_{2}\gamma_{k}$.

(iii) $c_{3}\gamma_{k}^{2}\geq\alpha_{k}$.
Then the sequence $\\{\alpha_{k}\\}$ Q-linearly converges to zero, and the
sequences $\\{\beta_{k}\\}$ and $\\{\gamma_{k}\\}$ R-linearly converge to zero
as $k\to\infty$.

Now we are ready to verify the global convergence rates for Algorithm 3.

######  Theorem 5.11.

In the setting of Proposition 5.9, suppose that the accumulation point
$\bar{x}$ satisfies all the conditions in Assumption 3. In Algorithm 3, choose
$\lambda\in(0,r^{-1})$ such that $Q(\bar{x})=I-\lambda\nabla^{2}f(\bar{x})$ is
positive-definite. Then we have the assertions:

(i) The convergence rate of $\\{\varphi_{\lambda}(x^{k})\\}$ is at least
Q-linear.

(ii) The convergence rates of $\\{x^{k}\\}$ and
$\\{\|\nabla\varphi_{\lambda}(x^{k})\|\\}$ are at least R-linear.

[Proof.] It follows from Proposition 5.8 that $\widehat{v}^{k}\to 0$ as
$k\to\infty$ with the estimates in (5.27). Invoking Proposition 5.9 ensures
the convergence of the sequence $\\{x^{k}\\}$ to $\bar{x}$. By the prox-
regularity of $g$ at $\bar{x}$ for $-\nabla f(\bar{x})$, Proposition 4.7 tells
us that the mapping $x\mapsto\text{\rm Prox}_{\lambda g}(x-\lambda\nabla
f(x))$ is single-valued around $\bar{x}$. Then we deduce from Remark 5.3(i),
the criticality of $\bar{x}$, and (5.8) that
$\nabla\varphi_{\lambda}(\bar{x})=0$. It follows from Remark 5.3(ii) that
$\varphi_{\lambda}$ is of class $\mathcal{C}^{1,1}$ around $\bar{x}$, and thus
we get that $\varphi_{\lambda}(x^{k})\to\varphi_{\lambda}(\bar{x})$ and
$\|\nabla\varphi_{\lambda}(x^{k})\|\to 0$ as $k\to\infty$. Moreover, Lemma 5.5
implies that $\varphi_{\lambda}$ is strongly convex around $\bar{x}$. By the
descriptions of strongly convex functions, we find $\kappa>0$ such that

$\varphi_{\lambda}(x)\geq\varphi_{\lambda}(\bar{x})+\langle\nabla\varphi_{\lambda}(\bar{x}),x-\bar{x}\rangle+\frac{\kappa}{2}\|x-\bar{x}\|^{2}=\varphi_{\lambda}(\bar{x})+\frac{\kappa}{2}\|x-\bar{x}\|^{2},$
(5.30)
$\langle\nabla\varphi_{\lambda}(x),x-\bar{x}\rangle=\langle\nabla\varphi_{\lambda}(x)-\nabla\varphi_{\lambda}(\bar{x}),x-\bar{x}\rangle\geq\kappa\|x-\bar{x}\|^{2}$
(5.31)

for all $x$ near $\bar{x}$. By using the descent lemma [13, Lemma A.11], we
find $\ell>0$ such that

$\varphi_{\lambda}(x)\leq\varphi_{\lambda}(\bar{x})+\langle\nabla\varphi_{\lambda}(\bar{x}),x-\bar{x}\rangle+\frac{\ell}{2}\|x-\bar{x}\|^{2}=\varphi_{\lambda}(\bar{x})+\frac{\ell}{2}\|x-\bar{x}\|^{2}$
(5.32)

for all $x$ near $\bar{x}$. Combining the latter with (5.27) tells us that

$\|\widehat{v}^{k}\|\geq\Big{(}\frac{1}{\lambda}-L_{f}\Big{)}\|\widehat{x}^{k}-x^{k}\|=\Big{(}\frac{1}{\lambda}-L_{f}\Big{)}\|x^{k}-\text{\rm
Prox}_{\lambda g}(x^{k}-\lambda\nabla f(x^{k}))\|,$

which implies by Algorithm 3 the estimates

$\varphi_{\lambda}(x^{k})-\varphi_{\lambda}(x^{k+1})\geq\sigma\|\widehat{v}^{k}\|^{2}\geq\sigma\Big{(}\frac{1}{\lambda}-L_{f}\Big{)}^{2}\|x^{k}-\text{\rm
Prox}_{\lambda g}(x^{k}-\lambda\nabla f(x^{k}))\|^{2},$ (5.33)

for sufficiently large $k\in{\rm I\\!N}$. The Lipschitz continuity of $\nabla
f$ on ${\rm I\\!R}^{n}$ ensures that the gradient of function
$x\mapsto\frac{\|x\|^{2}}{2}-\lambda f(x)$ is also global Lipschitz continuous
on ${\rm I\\!R}^{n}$. Then there is $M>0$ such that
$\|I-\lambda\nabla^{2}f(x)\|\leq M$. Due to (5.6), we have

$\|\nabla\varphi_{\lambda}(x)\|=\left\|\lambda^{-1}\big{(}I-\lambda\nabla^{2}f(x)\big{)}\big{(}x-\text{\rm
Prox}_{\lambda g}(x-\lambda\nabla
f(x))\big{)}\right\|\leq\frac{M}{\lambda}\big{\|}x-\text{\rm Prox}_{\lambda
g}(x-\lambda\nabla f(x))\big{\|}$ (5.34)

for all $x$ near $\bar{x}$. Combining (5.33) and (5.34), we have

$\displaystyle[\varphi_{\lambda}(x^{k})-\varphi_{\lambda}(\bar{x})]-[\varphi_{\lambda}(x^{k+1}-\varphi_{\lambda}(\bar{x})]$
$\displaystyle=\varphi_{\lambda}(x^{k})-\varphi_{\lambda}(x^{k+1})$
$\displaystyle\geq\frac{\sigma\lambda^{2}}{M^{2}}\Big{(}\frac{1}{\lambda}-L_{f}\Big{)}^{2}\|\nabla\varphi_{\lambda}(x^{k})\|^{2}$
(5.35)

for all sufficiently large $k\in{\rm I\\!N}$. Then (5.31) and the Cauchy-
Schwarz inequality ensure that

$\|\nabla\varphi_{\lambda}(x^{k})\|\geq\kappa\|x^{k}-\bar{x}\|\;\text{ for
large }\;k\in{\rm I\\!N}.$ (5.36)

The estimate in (5.32) tells us that

$\frac{\ell}{2}\|x^{k}-\bar{x}\|^{2}\geq\varphi_{\lambda}(x^{k})-\varphi_{\lambda}(\bar{x})\;\text{
whenever $k$ is large enough}.$ (5.37)

Using (5), (5.36), and (5.37) and then applying Lemma 5.10 to the sequences

$\alpha_{k}:=\varphi_{\lambda}(x^{k})-\varphi_{\lambda}(\bar{x}),\;\beta_{k}:=\|\nabla\varphi_{\lambda}(x^{k})\|,\;\gamma_{k}:=\|x^{k}-\bar{x}\|,\quad
k=0,1,\ldots,$

we complete the proof of this theorem.

##  6 Globalization of Coderivative-Based Newton Method in Structured
Nonconvex Optimization

In this section, we design a new generalized coderivative-based Newton method
to solve (4.1) and justify its fast global convergence. With the Lipschitz
constant $L_{f}$ from Assumption 2, our globalized coderivative-based Newton
method (GCNM) of solving (4.1) is formulated as follows.

Algorithm 4 (coderivative-based Newtonian algorithm in nonconvex optimization)

1:$x^{0}\in{\rm I\\!R}^{n}$, $\lambda\in(0,\text{\rm
min}\\{1/L_{f},\lambda_{g}\\})$, ${\sigma\in\left(0,\frac{\lambda(1-\lambda
L_{f})}{2(1+\lambda L_{f})^{2}}\right)}$, $\beta\in(0,1)$

2:for $k=0,1,\ldots$ do

3: If $x^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla f(x^{k}))$,
stop; otherwise go to the next step

4: Define $\widehat{x}^{k}$ and $\widehat{v}^{k}$ by
$\widehat{x}^{k}\in\text{\rm Prox}_{\lambda g}(x^{k}-\lambda\nabla
f(x^{k}))\;\mbox{ and }\;\widehat{v}^{k}:=\nabla f(\widehat{x}^{k})-\nabla
f(x^{k})+\frac{1}{\lambda}(x^{k}-\widehat{x}^{k})$

5: Newton step: Choose $d^{k}\in{\rm I\\!R}^{n}$ satisfying
$-\widehat{v}^{k}-\nabla^{2}f(\widehat{x}^{k})d^{k}\in\partial^{2}g(\widehat{x}^{k},\widehat{v}^{k}-\nabla
f(\widehat{x}^{k}))(d^{k})$ (6.1) If such $d^{k}$ doesn’t exist, select an
arbitrary $d^{k}\in{\rm I\\!R}^{n}$

6: Set $\tau_{k}=1$

7: while
$\varphi_{\lambda}(\widehat{x}^{k}+\tau_{k}d^{k})>\varphi_{\lambda}(x^{k})-\sigma\left\|\widehat{v}^{k}\right\|^{2}$
do

8: set $\tau_{k}:=\beta\tau_{k}$

9: end while

10: Set $x^{k+1}:=\widehat{x}^{k}+\tau_{k}d^{k}$

11:end for

Note that Algorithm 4 is a special case of Algorithm 3 in which the direction
$d^{k}$ is now chosen based on second-order information. Under some additional
assumptions, the unit stepsize is eventually accepted, and therefore Algorithm
4 eventually becomes the generalized pure Newton algorithm from Algorithm 2.
Thus its Q-superlinear convergence is guaranteed. The following theorem
explains the aforementioned observations in more detail.

######  Theorem 6.1 (Q-superlinear convergence of globalized coderivative-
based damped Newton algorithm).

Given $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ in (4.1) under
Assumption 2, suppose that $\inf\varphi>-\infty$. If $\bar{x}$ is an
accumulation point of the sequence $\\{x^{k}\\}$ generated by Algorithm 4,
then $\bar{x}$ is a critical point of (4.1). Assuming further that the
subgradient mapping $\partial g$ is semismooth∗ at $(\bar{x},-\nabla
f(\bar{x}))$ and the $\bar{x}$ satisfies all the conditions in Assumption 3,
choose in Algorithm 4 the parameter $\lambda\in(0,r^{-1})$ such that
$Q(\bar{x})=I-\lambda\nabla^{2}f(\bar{x})$ is positive-definite. Then
Algorithm 4 generates the sequences $\\{x^{k}\\}$,
$\|\nabla\varphi_{\lambda}(\bar{x})\|$, and $\\{\varphi_{\lambda}(x^{k})\\}$
converging respectively to $\bar{x}$, $0$, and $\varphi_{\lambda}(\bar{x})$
with the Q-superlinear convergence rates.

[Proof.] It follows from Proposition 5.8 that Algorithm 4 produces sequences
$\\{x^{k}\\}$, $\\{\widehat{x}^{k}\\}$, and $\\{\widehat{v}^{k}\\}$ such that
both $\\{\widehat{v}^{k}\\}$ and $\\{\widehat{x}^{k}-x^{k}\\}$ converge to $0$
as $k\to\infty$, and that $\bar{x}$ is a critical point of (4.1). Let us
verify the Q-superlinear convergence of $\\{x^{k}\\}$ and
$\\{\varphi_{\lambda}(x^{k})\\}$ under all the conditions in Assumption 3 and
the semismoothness∗ of $\partial g$ at $(\bar{x},-\nabla f(\bar{x}))$. To
proceed, we split the proof into the three claims.
Claim 1: Both sequences $\\{x^{k}\\}$ and $\\{\widehat{x}^{k}\\}$ converge to
$\bar{x}$, and the sequence $\\{d^{k}\\}$ converges to $0$ as $k\to\infty$. To
furnish this, we first show that $\bar{x}$ is an isolated accumulation point
of $\\{x^{k}\\}$. Indeed, since $\bar{x}$ is a tilt-stable local minimizer of
$\varphi$, it follows from [6, Proposition 3.1] that $\partial\varphi$ is
strongly metrically regular around $(\bar{x},0)$. Thus there exists a
neighborhood $U$ of $\bar{x}$ such that $\partial\varphi^{-1}(0)\cap
U=\\{\bar{x}\\}$. Suppose that there is an accumulation point $\widehat{x}$ of
the sequence $\\{x^{k}\\}$ for which $\widehat{x}\in U$ and
$\widehat{x}\neq\bar{x}$. Proposition 5.8 ensures that $\widehat{x}$ is a
critical point, and hence $0\in\partial\varphi(\widehat{x})$. Then we get that
$\widehat{x}\in\partial\varphi^{-1}(0)\cap U$ and thus $\widehat{x}=\bar{x}$,
a contradiction meaning that $\bar{x}$ is an isolated accumulation point of
$\\{x^{k}\\}$. As follows from Lemma 3.1, the strong metric regularity of
$\partial\varphi$ around $(\bar{x},0)$ yields the existence of a neighborhood
$W$ of $(\bar{x},0)$ such that for each $(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap W$ we find $d\in{\rm I\\!R}^{n}$ with

$-v\in\partial^{2}\varphi(x,v)(d)=\nabla^{2}f(x)d+\partial^{2}g(x,v-\nabla
f(x))(d),$ (6.2)

where the equality follows from the second-order subdifferential sum rule in
[25, Proposition 1.121]. This allows us to employ Theorem 5.11 for clarifying
the convergence of $\\{x^{k}\\}$ to $\bar{x}$. Picking now an arbitrary
subsequence $\\{x^{k}\\}_{k\in J}$ of $\\{x^{k}\\}$ converging to $\bar{x}$,
we intend to show that

$\|d^{k}\|\leq\kappa\|\widehat{v}^{k}\|\;\text{ for all large }\;k\in J,$
(6.3)

where $\kappa>0$ is a modulus of tilt stability of $\bar{x}$. Since $f$ is
$\mathcal{C}^{2}$-smooth around $\bar{x}$ and $g$ is continuously prox-regular
at $\bar{x}$ for $-\nabla f(\bar{x})$, it follows that $\varphi$ is
continuously prox-regular at $\bar{x}$ for $0$. By Proposition 2.8, the tilt
stability of $\bar{x}$ implies that $\varphi$ is variationally strongly convex
at $\bar{x}$ for $0$ with modulus $\kappa^{-1}$. Due to Proposition 2.7, the
strong variational convexity of $\varphi$ at $\bar{x}$ for $0$ with modulus
$\kappa>0$ guarantees the existence of a positive number $\delta$ such that

$\langle z,w\rangle\geq\kappa^{-1}\|w\|^{2}\;\text{ for all
}\;z\in\partial^{2}\varphi(x,v)(w),\;(x,v)\in\mbox{\rm
gph}\,\partial\varphi\cap\mathbb{B}_{\delta}(\bar{x},0),\;w\in{\rm
I\\!R}^{n}.$ (6.4)

Since $\\{x^{k}-\widehat{x}^{k}\\}$ converges to $0$, we have that
$\widehat{x}^{k}\overset{J}{\rightarrow}\bar{x}$ as $k\to\infty$. Combining
the latter with (6.2) gives us directions $d^{k}\in{\rm I\\!R}^{n}$ satisfying
the second-order inclusions

$-\widehat{v}^{k}\in\partial^{2}\varphi(\widehat{x}^{k},\widehat{v}^{k})(d^{k})=\nabla^{2}f(\widehat{x}^{k})d^{k}+\partial^{2}g(\widehat{x}^{k},\widehat{v}^{k}-\nabla
f(\widehat{x}^{k})(d^{k})$

for all large $k\in J$. Moreover, the inclusions
$-\widehat{v}^{k}\in\partial^{2}\varphi(\widehat{x}^{k},\widehat{v}^{k})(d^{k})$
for all $k\in J$ with the convergence
$\widehat{x}^{k}\overset{J}{\rightarrow}\bar{x}$ and
$\widehat{v}^{k}\overset{J}{\rightarrow}0$ lead us by using (6.4) to
$\langle-\widehat{v}^{k},d^{k}\rangle\geq\kappa^{-1}\|d^{k}\|^{2}$ for large
$k\in J$. Then the Cauchy-Schwarz inequality yields (6.3), and thus
$x^{k}\to\bar{x}$ as $k\to\infty$ due to Theorem 5.11. Combining this with
(6.3) and the convergence $\widehat{v}^{k}\to 0$, $\widehat{x}^{k}-x^{k}\to 0$
as $k\to\infty$ tells us that $d^{k}\to 0$ and $\widehat{x}^{k}\to\bar{x}$ as
$k\to\infty$, which verifies all the conclusions of this claim.
Claim 2: Whenever $k\in{\rm I\\!N}$ is large enough, we get the unit stepsize
$\tau_{k}=1$. Indeed, the prox-regularity of $g$ at $\bar{x}$ for $-\nabla
f(\bar{x})$ and Proposition 4.7 tell us that the mapping $x\mapsto\text{\rm
Prox}_{\lambda g}(x-\lambda\nabla f(x))$ is single-valued around $\bar{x}$.
Due to Remark 5.3, the FBE $\varphi_{\lambda}$ is of class $\mathcal{C}^{1,1}$
around $\bar{x}$, and the criticality of $\bar{x}$ yields
$\nabla\varphi_{\lambda}(\bar{x})=0$. By Lemma 5.5, the tilt stability of
$\bar{x}$ implies that $\varphi_{\lambda}$ is strongly convex around
$\bar{x}$. Thus we find $\mu>0$ ensuring the estimates

$\varphi_{\lambda}(x)\geq\varphi_{\lambda}(u)+\langle\nabla\varphi_{\lambda}(u),x-u\rangle+\frac{\mu}{2}\|x-u\|^{2},$
(6.5)
$\langle\nabla\varphi_{\lambda}(x)-\nabla\varphi_{\lambda}(u),x-u\rangle\geq\mu\|x-u\|^{2}$
(6.6)

for all $x,u$ near $\bar{x}$. The Lipschitz continuity of
$\nabla\varphi_{\lambda}$ around $\bar{x}$ with modulus $\ell$ implies that

$\varphi_{\lambda}(x)\leq\varphi_{\lambda}(u)+\langle\nabla\varphi_{\lambda}(u),x-u\rangle+\frac{\ell}{2}\|x-u\|^{2},$
(6.7)
$\|\nabla\varphi_{\lambda}(x)-\nabla\varphi_{\lambda}(u)\|\leq\ell\|x-u\|$
(6.8)

for all $x,u$ near $\bar{x}$. By Claim 1, we have
$\widehat{x}^{k}+d^{k}\to\bar{x}$ and $\widehat{x}^{k}\to\bar{x}$ as
$k\to\infty$. Combining this with (6.3), (6.5), and (6.8) brings us to the
conditions

$\displaystyle\begin{array}[]{ll}\displaystyle\varphi_{\lambda}(\widehat{x}^{k}+d^{k})-\varphi_{\lambda}(\widehat{x}^{k})\displaystyle\leq\langle\nabla\varphi_{\lambda}(\widehat{x}^{k}+d^{k}),d^{k}\rangle-\frac{\mu}{2}\|d^{k}\|^{2}\\\
\displaystyle\leq\|\nabla\varphi_{\lambda}(\widehat{x}^{k}+d^{k})\|\cdot\|d^{k}\|\displaystyle\leq\|\nabla\varphi_{\lambda}(\widehat{x}^{k}+d^{k})-\nabla\varphi_{\lambda}(\bar{x})\|\cdot\|d^{k}\|\\\
\displaystyle\leq\frac{\ell}{\kappa}\|\widehat{x}^{k}+d^{k}-\bar{x}\|\cdot\|\widehat{v}^{k}\|\;\mbox{
for large }\;k\in{\rm I\\!N}.\end{array}$ (6.12)

It follows from [9, Proposition 3.6] that the semismoothness∗ of $\partial g$
at $(\bar{x},-\nabla f(\bar{x}))$ yields the semismoothness∗ of
$\partial\varphi$ at $(\bar{x},0)$. By [6, Proposition 3.1], the imposed tilt
stability of the local minimizer $\bar{x}$ implies that the subgradient
mapping $\partial\varphi$ is strongly metrically regular around $(\bar{x},0)$.
Combining the latter statements and using Theorem 3.6, we have

$\|\widehat{x}^{k}+d^{k}-\bar{x}\|=o(\|(\widehat{x}^{k},\widehat{v}^{k})-(\bar{x},0)\|)\;\text{
as }\;k\to\infty$ (6.13)

due to $\widehat{x}^{k}\to\bar{x}$, $\widehat{v}^{k}\to 0$, and
$-\widehat{v}^{k}\in\partial^{2}\varphi(\widehat{x}^{k},\widehat{v}^{k})(d^{k})$
for large $k$. By Proposition 2.6, the strong variational convexity of
$\varphi$ at $\bar{x}$ for $0$ with some modulus $\kappa>0$ guarantees the
existence of neighborhoods $U$ of $\bar{x}$ and $V$ of the origin such that

$\langle v_{1}-v_{2},x_{1}-x_{2}\rangle\geq\kappa\|x_{1}-x_{2}\|^{2}\;\text{
for all }\;(x_{1},v_{1}),(x_{2},v_{2})\in\mbox{\rm
gph}\,\partial\varphi\cap(U\times V).$ (6.14)

Note that $(\widehat{x}^{k},\widehat{v}^{k})\in\mbox{\rm
gph}\,\partial\varphi$ by Corollary 4.8, and therefore it follows from (6.14)
that

$\langle\widehat{v}^{k}-0,\widehat{x}^{k}-\bar{x}\rangle\geq\kappa\|\widehat{x}^{k}-\bar{x}\|^{2}\;\mbox{
for large }\;k\in{\rm I\\!N}.$

Employing again the Cauchy-Schwarz inequality yields
$\|\widehat{v}^{k}\|\geq\kappa\|\widehat{x}^{k}-\bar{x}\|$ for such $k$, which
being combined with (6.13) leads us to

$\|\widehat{x}^{k}+d^{k}-\bar{x}\|=o(\|\widehat{v}^{k}\|)\;\text{ as
}\;k\to\infty.$ (6.15)

Unifying further (6.12) and (6.15) results in

$\limsup_{k\to\infty}\frac{\varphi_{\lambda}(\widehat{x}^{k}+d^{k})-\varphi_{\lambda}(\widehat{x}^{k})}{\|\widehat{v}^{k}\|^{2}}\leq
0.$ (6.16)

Choose $\varepsilon:=\frac{\lambda(1-\lambda L_{f})}{2(1+\lambda
L_{f})^{2}}-\sigma>0$ and deduce from (6.16) the existence of $k_{0}\in{\rm
I\\!N}$ with

$\varphi_{\lambda}(\widehat{x}^{k}+d^{k})-\varphi_{\lambda}(\widehat{x}^{k})\leq\varepsilon\|\widehat{v}^{k}\|^{2}\;\text{
for all }\;k\geq k_{0}.$ (6.17)

Moreover, it follows from (5.27) that

$\|\widehat{v}^{k}\
\leq\Big{(}\frac{1}{\lambda}+L_{f}\Big{)}\|\widehat{x}^{k}-x^{k}\|.$ (6.18)

By (5.4) and the Lipschitz continuity of $\nabla f$, we deduce from [13, Lemma
A.11] that

$\displaystyle\varphi_{\lambda}(x^{k})$ $\displaystyle=f(x^{k})+\langle\nabla
f(x^{k}),\widehat{x}^{k}-x^{k}\rangle+g(\widehat{x}^{k})+\frac{1}{2\lambda}\|\widehat{x}^{k}-x^{k}\|^{2}$
$\displaystyle\geq
f(\widehat{x}^{k})-\frac{L_{f}}{2}\|\widehat{x}^{k}-x^{k}\|^{2}+g(\widehat{x}^{k})+\frac{1}{2\lambda}\|\widehat{x}^{k}-x^{k}\|^{2}=\varphi(\widehat{x}^{k})+\frac{1-\lambda
L_{f}}{2\lambda}\|\widehat{x}^{k}-x^{k}\|^{2}.$ (6.19)

Combining finally (6.17), (6.18), and (6) brings us to the estimates

$\displaystyle\varphi_{\lambda}(\widehat{x}^{k}+d^{k})\leq\varphi_{\lambda}(\widehat{x}^{k})+\varepsilon\|\widehat{v}^{k}\|^{2}\leq\varphi(\widehat{x}^{k})+\varepsilon\|\widehat{v}^{k}\|^{2}$
$\displaystyle\leq\varphi_{\lambda}(x^{k})+\varepsilon\|\widehat{v}^{k}\|^{2}-\frac{1-\lambda
L_{f}}{2\lambda}\|x^{k}-\widehat{x}^{k}\|^{2}$
$\displaystyle\leq\varphi_{\lambda}(x^{k})+\varepsilon\|\widehat{v}^{k}\|^{2}-\frac{\lambda(1-\lambda
L_{f})}{2(1+\lambda
L_{f})^{2}}\|\widehat{v}^{k}\|^{2}=\varphi_{\lambda}(x^{k})-\sigma\|\widehat{v}^{k}\|^{2}$

for all $k\geq k_{0}$, which tells us that $\tau_{k}=1$ whenever $k\geq k_{0}$
and thus completes the proof of the claim.
Claim 3: The convergence rates of $\\{x^{k}\\}$,
$\\{\|\nabla\varphi_{\lambda}(x^{k})\|\\}$ and
$\\{\varphi_{\lambda}(x^{k})\\}$ are at least Q-superlinear. Indeed, it
follows from Claim 2 that the iterative sequence $\\{x^{k}\\}$ generated by
Algorithm 4 eventually becomes the iterative sequence $\\{x^{k}\\}$ generated
by Algorithm 2 of the pure Newton type. Hence the claimed $Q$-superlinear
convergence of $\\{x^{k}\\}$ follows from Theorem 4.10.

Next we verify the $Q$-superlinear convergence of
$\\{\|\nabla\varphi_{\lambda}(x^{k})\|\\}$ and
$\\{\varphi_{\lambda}(x^{k})\\}$. To furnish this for the sequence
$\\{\varphi_{\lambda}(x^{k})\\}$, deduce from (6.5) and
$\nabla\varphi_{\lambda}(\bar{x})=0$ that

$\varphi_{\lambda}(x^{k})-\varphi_{\lambda}(\bar{x})\geq\frac{\mu}{2}\|x^{k}-\bar{x}\|^{2}\;\mbox{
for large }\;k\in{\rm I\\!N}.$

Furthermore, we get from (6.7) whenever $k\in{\rm I\\!N}$ is large that

$0<\varphi_{\lambda}(x^{k+1})-\varphi_{\lambda}(\bar{x})\leq\frac{\ell}{2}\|x^{k+1}-\bar{x}\|^{2},$

and thus combining the two estimates above gives us

$\frac{|\varphi_{\lambda}(x^{k+1})-\varphi_{\lambda}(\bar{x})|}{|\varphi_{\lambda}(x^{k})-\varphi_{\lambda}(\bar{x})|}\leq\frac{\ell}{\mu}\frac{\|x^{k+1}-\bar{x}\|^{2}}{\|x^{k}-\bar{x}\|^{2}}.$

This justifies the claimed Q-superlinear convergence of
$\\{\varphi_{\lambda}(\bar{x})\\}$ by the one established for $\\{x^{k}\\}$.

To finish the proof of the theorem, it remains to show that the sequence
$\\{\nabla\varphi_{\lambda}(x^{k})\\}$ converges to $0$ with the Q-superlinear
rate. Indeed, it follows from (6.8) that

$\|\nabla\varphi_{\lambda}(x^{k+1})\|=\|\nabla\varphi_{\lambda}(x^{k+1})-\nabla\varphi_{\lambda}(\bar{x})\|\leq\ell\|x^{k+1}-\bar{x}\|\;\mbox{
for large }\;k\in{\rm I\\!N}.$

Therefore, for such $k$ we get from (6.6) that

$\langle\nabla\varphi_{\lambda}(x^{k})-\nabla\varphi_{\lambda}(\bar{x}),x^{k}-\bar{x}\rangle\geq\mu\|x^{k}-\bar{x}\|^{2},$

which implies in turn that
$\|\nabla\varphi_{\lambda}(x^{k})\|\geq\kappa\|x^{k}-\bar{x}\|$ and brings us
to the estimate

$\frac{\|\nabla\varphi_{\lambda}(x^{k+1})\|}{\|\nabla\varphi_{\lambda}(x^{k})\|}\leq\frac{\ell}{\mu}\frac{\|x^{k+1}-\bar{x}\|}{\|x^{k}-\bar{x}\|}.$

This shows that the gradient sequence $\\{\nabla\varphi_{\lambda}(x^{k})\\}$
converges to 0 with the Q-superlinear rate $k\to\infty$ due to the established
convergence of $x^{k}\to\bar{x}$, which thus completes the proof of the
theorem.

######  Remark 6.2 (comparison with other globalized coderivative-based Newton
methods).

Recently, several globally convergent coderivative-based Newton methods have
been developed in [20, 21] to solve (4.1) in the case where $f$ is a convex
quadratic function and $g$ is l.s.c. and convex. Besides, the generalized
damped Newton methods in [20, 21] require the positive-definiteness of
$\partial^{2}\varphi$ on the whole space, which is a restrictive assumption
for many practical models. In contrast, our new coderivative-based Newton
method in Algorithm 4 doesn’t assume that $f$ is convex quadratic and $g$ is
convex and doesn’t impose the global assumption on $\partial^{2}\varphi$.
Recall to this end that the tilt stability requirement in Assumption 3 is
equivalent for continuously prox-regular functions to the positive-
definiteness of the generalized Hessian only at one solution point, not on the
entire space.

##  7 Solving Nonconvex Least Square Regression Models

In this section, we provide explicit implementations of our new generalized
coderivative-based Newton method (abbr. GCNM), developed above for nonsmooth
nonconvex optimization models of type (4.1) via Algorithm 4, to solve the
$\ell_{0}$-$\ell_{2}$ regularized least square regression problem whose
importance has been well recognized in applications to practical models of
statistics, machine learning, etc.; see e.g., [12] and the references therein.
All the numerical experiments were conducted on a desktop with a 12th Gen
Intel(R) Core(TM) i5-1235U processor (10 cores, 12M Cache, up to 4.4 GHz) and
16GB of memory. The codes were written in Python and executed in Google Colab.

Given an $m\times n$ matrix $A$ and a vector $b\in{\rm I\\!R}^{m}$, the
$\ell_{0}$-$\ell_{2}$ regularized least square problem is

$\text{minimize
}\quad\varphi(x):=\frac{1}{2}\|Ax-b\|^{2}+\mu_{0}\|x\|_{0}+\mu_{2}\|x\|_{2}^{2}\quad\text{subject
to}\quad x\in{\rm I\\!R}^{n},$ (7.1)

where $\mu_{0}$ and $\mu_{2}$ are positive parameters, and where $\|x\|_{0}$
is the $\ell_{0}$ norm of $x$ counting the number of nonzero elements of $x$,
i.e., being expressed as

$\|x\|_{0}:=\sum_{i=1}^{n}I(x_{i})\;\text{ for
}\;x=(x_{1},\ldots,x_{n})\in{\rm I\\!R}^{n}\;\mbox{ with
}\;I(t):=\begin{cases}1&\text{if}\quad t\neq 0,\\\
0&\text{otherwise}.\end{cases}$ (7.2)

Note that problem (7.1) is nonconvex and nonsmooth, and it is a particular
case of the structured optimization model in (4.1) with the data

$f(x):=\frac{1}{2}\|Ax-b\|^{2}+\mu_{2}\|x\|^{2}\;\text{ and
}\;g(x):=\mu_{0}\|x\|_{0}.$ (7.3)

We immediately calculate the gradient and Hessian of $f$ by

$\nabla f(x)=A^{*}(Ax-b)+2\mu_{2}x\quad\text{and
}\;\nabla^{2}f(x)=A^{*}A+2\mu_{2}I,\quad x\in{\rm I\\!R}^{n}.$ (7.4)

It follows from [2, Page 121] that the proximal mapping of
$g(x)=\mu_{0}\|x\|_{0}$ is given by

$\big{(}\text{\rm Prox}_{\lambda
g}(x)\big{)}_{i}=\begin{cases}x_{i}&\text{if}\quad|x_{i}|>\sqrt{2\lambda\mu_{0}},\\\
\\{0,x_{i}\\}&\text{if}\quad|x_{i}|=\sqrt{2\lambda\mu_{0}},\\\
0&\text{if}\quad|x_{i}|<\sqrt{2\lambda\mu_{0}}.\end{cases}$ (7.5)

To run Algorithm 4, we need to explicitly determine the direction sequence
$\\{d^{k}\\}$ in the Newton step, which requires the formula for the second-
order subdifferential of $g(x)=\mu_{0}\|x\|_{0}$. This is done in the next
proposition together with calculating the subgradient graphical derivative
used below.

######  Proposition 7.1 (second-order subdifferentials and subgradient
graphical derivative of the $\ell_{0}$ norm).

The limiting subdifferential of the function $g(x)=\mu_{0}\|x\|_{0}$ at any
$x\in{\rm I\\!R}^{n}$ is given by

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

The second-order subdifferential and the subgradient graphical derivative of
$g$ are

$\partial^{2}g(x,y)(v)=\Big{\\{}w\in{\rm
I\\!R}^{n}\;\Big{|}\;\left(w_{i},-v_{i}\right)\in
F\left(x_{i},y_{i}\right),\;i=1,\ldots,n\Big{\\}},$ (7.7) $(D\partial
g)(x,y)(v)=\big{\\{}u\in{\rm I\\!R}^{n}\;\big{|}\;\left(u_{i},v_{i}\right)\in
F\left(x_{i},v_{i}\right),\;i=1,\ldots,n\big{\\}}$ (7.8)

for each $(x,y)\in\text{\rm gph}\,\partial g$ and
$v=(v_{1},\ldots,v_{n})\in{\rm I\\!R}^{n}$, where the mapping $F\colon{\rm
I\\!R}^{2}\rightrightarrows{\rm I\\!R}^{2}$ is defined by

$F(t,p):=\begin{cases}\\{0\\}\times{\rm I\\!R}&\text{if }\;t\neq 0,p=0,\\\
(\\{0\\}\times{\rm I\\!R})\cup({\rm I\\!R}\times\\{0\\})&\text{if
}\;t=0,p=0,\\\ {\rm I\\!R}\times\\{0\\}&\text{if }\;t=0,p\neq 0,\\\
\emptyset&\text{otherwise}.\end{cases}$ (7.9)

[Proof.] Let $I:{\rm I\\!R}\to{\rm I\\!R}$ be given in (7.2). By simple
computations, it is not hard to get

$\partial I(t)=\begin{cases}\\{0\\}&\text{if }\;t\neq 0,\\\ {\rm
I\\!R}&\text{if }\;t=0,\end{cases}$ $N_{{\rm\small gph}\,\partial
I}(t,p)=\begin{cases}\\{0\\}\times{\rm I\\!R}&\text{if }\;t\neq 0,p=0,\\\
(\\{0\\}\times{\rm I\\!R})\cup({\rm I\\!R}\times\\{0\\})&\text{if
}\;t=0,p=0,\\\ {\rm I\\!R}\times\\{0\\}&\text{if }\;t=0,p\neq 0,\end{cases}$
$T_{{\rm\small gph}\,\partial I}(t,p)=\begin{cases}{\rm
I\\!R}\times\\{0\\}&\text{if }\;t\neq 0,p=0,\\\ (\\{0\\}\times{\rm
I\\!R})\cup({\rm I\\!R}\times\\{0\\})&\text{if }\;t=0,p=0,\\\
\\{0\\}\times{\rm I\\!R}&\text{if }\;t=0,p\neq 0,\end{cases}$

which clearly imply the formulas

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

This allows us to deduce from [28, Theorem 4.3] the representation

$\partial^{2}g(x,y)(v)=\Big{\\{}w\in{\rm
I\\!R}^{n}\;\Big{|}\;\Big{(}\frac{1}{\mu_{0}}w_{i},-v_{i}\Big{)}\in
N_{{\rm\small gph}\,\partial
I}\Big{(}x_{i},\frac{1}{\mu_{0}}y_{i}\Big{)},\;i=1,\ldots,n\Big{\\}}$

verifying (7.7). Furthermore, it follows from (2.7) and [35, Proposition 6.41]
that

$\begin{array}[]{ll}(D\partial g)(x,y)(v)=\big{\\{}u\in{\rm
I\\!R}^{n}\;\big{|}\;\left(v,u\right)\in T_{{\rm\small gph}\,\partial
g}\left(x,y\right)\big{\\}}\\\ =\big{\\{}u\in{\rm
I\\!R}^{n}\;\big{|}\;\big{(}v_{i},u_{i}\big{)}\in T_{{\rm\small gph}\,\partial
I}(x_{i},y_{i}),\;i=1,\ldots,n\big{\\}}=\big{\\{}w\in{\rm
I\\!R}^{n}\;\big{|}\;\big{(}u_{i},v_{i}\big{)}\in
F(x_{i},y_{i}),\;i=1,\ldots,n\big{\\}},\end{array}$

which readily justifies (7.8) and thus completes the proof of the proposition.

As a consequence of the above calculations, we get the following corollary
ensuring the positive-definiteness of the cost function in (7.1).

######  Corollary 7.2 (positive-definiteness of the cost in
$\ell_{0}$-$\ell_{2}$ model).

Let $\varphi:{\rm I\\!R}^{n}\to{\rm I\\!R}$ be given in (7.1). Then both
mappings $\partial^{2}\varphi(x,y)$ and $(D\partial\varphi)(x,y)$ are
positive-definite with the uniform modulus $\kappa:=\lambda_{\text{\rm
min}}(A^{*}A)+2\mu_{2}$ for all $(x,y)\in\mbox{\rm gph}\,\partial\varphi$,
i.e., we have

$\langle z,w\rangle\geq\kappa\|w\|^{2}\;\text{ whenever
}\;z\in\partial^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi,\;w\in{\rm I\\!R}^{n},$ (7.10) $\langle
z,w\rangle\geq\kappa\|w\|^{2}\;\text{ whenever
}\;z\in(D\partial\varphi)(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi,\;w\in{\rm I\\!R}^{n}.$ (7.11)

[Proof.] It follows directly from Proposition 7.1 that $\partial^{2}g(x,v)$
and $(D\partial g)(x,v)$ is positive-semidefinite for all $(x,v)\in\mbox{\rm
gph}\,\partial g$. Since $f$ in (7.3) is strongly convex with modulus
$\kappa$, the Hessian matrix $\nabla^{2}f(x)$ is positive-definite with the
uniform modulus $\kappa$ for all $x\in{\rm I\\!R}^{n}$. By using the
subdifferential sum rule from [25, Proposition 1.107], the second-order sum
rule from [25, Proposition 1.121], and the graphical derivative sum rule from
[35, Exercise 10.43], we justify the claimed conclusions.

Next we establish some additional variational properties of the $\ell_{0}$
norm, which are of their own interest and help us to solve the
$\ell_{0}$-$\ell_{2}$ problem by employing the developed GCNM algorithm.

######  Theorem 7.3 (variational convexity and subdifferential continuity of
the $\ell_{0}$ norm).

Let $g:{\rm I\\!R}^{n}\to{\rm I\\!R}$ be given by $g(x)=\|x\|_{0}$ on ${\rm
I\\!R}^{n}$. Then $g$ is variationally convex at every $x\in{\rm I\\!R}^{n}$
for any $v\in\partial g(x)$. If furthermore we have

$\bar{v}_{i}\neq 0\quad\text{whenever }\;\bar{x}_{i}=0,\;\bar{v}\in\partial
g(\bar{x}),\;\mbox{ and }\;\bar{x}\in{\rm I\\!R}^{n},$ (7.12)

then $g$ is subdifferentially continuous at $\bar{x}$ for $\bar{v}$.

[Proof.] It is not difficult to check that $g$ is l.s.c. on ${\rm I\\!R}^{n}$.
Picking $(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial g$, we now verify via
Proposition 2.6 the variational convexity of $g$ at $\bar{x}$ for $\bar{v}$ by
checking that $\partial g$ is $g$-locally monotone around $(\bar{x},\bar{v})$
as in (2.22). To furnish this, define
$J(\bar{x}):=\big{\\{}j\in\\{1,2,\ldots,n\\}\;\big{|}\;\bar{x}_{j}\neq
0\big{\\}}$ and observe that $\bar{x}_{j}\neq 0$ for each $j\in J(\bar{x})$.
Thus there is $\delta_{j}>0$ such that
$0\notin(\bar{x}_{j}-\delta_{j},\bar{x}_{j}+\delta_{j})$. Denoting

$U:=\big{\\{}x=(x_{1},\ldots,x_{n})\in{\rm
I\\!R}^{n}\;\big{|}\;x_{j}\in(\bar{x}_{j}-\delta_{j},\bar{x}_{j}+\delta_{j})\;\text{
if }\;j\in J(\bar{x})\big{\\}}\;\mbox{ and }\;V:={\rm I\\!R}^{n}$

we see that $U\times V$ is a convex neighborhood of $(\bar{x},\bar{v})$ and
that

$\sum_{j\in J(\bar{x})}I(x_{j})=\sum_{j\in
J(\bar{x})}I(\bar{x}_{j}),\quad\sum_{j\in\\{1,\ldots,n\\}\setminus
J(\bar{x})}I(\bar{x}_{j})=0$

for all $x\in U$, where $I$ is taken from (7.2). This readily implies that

$g(x)-g(\bar{x})=\sum_{j\in
J(\bar{x})}I(x_{j})+\sum_{j\in\\{1,\ldots,n\\}\setminus
J(\bar{x})}I(x_{j})-\sum_{j\in
J(\bar{x})}I(\bar{x}_{j})-\sum_{j\in\\{1,\ldots,n\\}\setminus
J(\bar{x})}I(\bar{x}_{j})=\sum_{j\in\\{1,\ldots,n\\}\setminus
J(\bar{x})}I(x_{j}).$

Fix $\varepsilon\in(0,1)$ and show that $\partial g$ is monotone relative to
the set

$\displaystyle W:=\big{\\{}(x,v)\in U\times
V\;\big{|}\;g(x)<g(\bar{x})+\varepsilon\big{\\}}=\Big{\\{}(x,v)\in U\times
V\;\Big{|}\;\sum_{j\in\\{1,\ldots,n\\}\setminus
J(\bar{x})}I(x_{j})<\varepsilon\Big{\\}}$ $\displaystyle=\big{\\{}(x,v)\in
U\times V\;\big{|}\;x_{j}=0\;\text{for all }j\in\\{1,\ldots,n\\}\setminus
J(\bar{x})\big{\\}}.$

Indeed, for $(x,v),(u,w)\in\mbox{\rm gph}\,\partial g\cap W$ we have

$\begin{cases}x_{j}=u_{j}=0&\text{whenever }j\in\\{1,\ldots,n\\}\setminus
J(\bar{x}),\\\
x_{j},u_{j}\in(\bar{x}_{j}-\delta_{j},\bar{x}_{j}+\delta_{j})&\text{whenever
}\;j\in J(\bar{x}).\end{cases}$ (7.13)

Observe that $x_{j},u_{j}\neq 0$ for any $j\in J(\bar{x})$ by
$0\notin(\bar{x}_{j}-\delta_{j},\bar{x}_{j}+\delta_{j})$. Therefore, it
follows from (7.6) that

$v_{j}=w_{j}=0\quad\text{whenever }\;j\in J(\bar{x}).$ (7.14)

Combining (7.13) and (7.14), we get the equality

$\langle x-u,v-w\rangle=\sum_{j\in
J(\bar{x})}(x_{j}-u_{j})(v_{j}-w_{j})+\sum_{j\in\\{1,2,\ldots,n\\}\setminus
J(\bar{x})}(x_{j}-u_{j})(v_{j}-w_{j})=0,$

which tells us tha the subdifferential mapping $\partial g$ is $g$-locally
monotone around $(\bar{x},\bar{v})$. Therefore, $g$ is variationally convex at
$\bar{x}$ for $\bar{v}$ due to Proposition 2.6.

Next we pick $(\bar{x},\bar{v})\in\mbox{\rm gph}\,\partial g$ satisfying
(7.12) and show that $g$ is subdifferentially continuous at $\bar{x}$ for
$\bar{v}$. Indeed, take $(x^{k},v^{k})\to(\bar{x},\bar{v})$, $v^{k}\in\partial
g(x^{k})$, and then check that $g(x^{k})\to g(\bar{x})$ as $k\to\infty$. For
$j\in J(\bar{x})$, we have $\bar{x}_{j}\neq 0$ ensuring that $I$ is continuous
at $\bar{x}_{j}$, which implies that

$I\big{(}(x^{k})_{j}\big{)}\to I(\bar{x}_{j})\;\text{ as }\;k\to\infty\;\text{
whenever }\;j\in J(\bar{x}).$ (7.15)

Fixing $j\in\\{1,\ldots,n\\}\setminus J(\bar{x})$ gives us $\bar{x}_{j}=0$,
and thus $\bar{v}_{j}\neq 0$ by (7.12). Since $(v^{k})_{j}\to\bar{v}_{j}$ as
$k\to\infty$, we have $(v^{k})_{j}\neq 0$ for all large $k$. By
$v^{k}\in\partial g(x^{k})$, it follows from (7.6) that $(x^{k})_{j}=0$ for
large $k$, which yields the convergence

$I\big{(}(x^{k})_{j}\big{)}\to 0=I(\bar{x}_{j})\;\text{ as
}\;k\to\infty\;\text{ whenever }\;j\in\\{1,\ldots,n\\}\setminus J(\bar{x}).$
(7.16)

Combining (7.15) and (7.16) brings us to

$g(x^{k})=\sum_{j=1}^{n}I\big{(}(x^{k})_{j}\big{)}\to\sum_{j=1}^{n}I(\bar{x}_{j})=g(\bar{x})\;\text{
as }\;k\to\infty,$

which justifies the claimed subdifferential continuity and thus completes the
proof of theorem.

Now we are ready to reveal the explicit conditions for solving (7.1) by
Algorithm 4. Observe that Proposition 7.1 allows us to calculate the
directions $d^{k}$ in this algorithm for (7.1) via the relationships

$\begin{cases}\big{(}-\widehat{v}^{k}-\nabla^{2}f(x^{k})d^{k}\big{)}_{i}=0&\text{if}\quad\left(\widehat{x}^{k}\right)_{i}\neq
0,\\\
\big{(}d^{k}\big{)}_{i}=0&\text{if}\quad\left(\widehat{x}^{k}\right)_{i}=0\end{cases}$
(7.17)

in which the approximate vectors $\widehat{x}^{k}$ and $\widehat{v}^{k}$ are
determined by

$\widehat{x}^{k}\in\text{\rm