Generalized Damped Newton Algorithms in Nonsmooth Optimization via Second-
Order Subdifferentials
Pham Duy Khanh***Department of Mathematics, HCMC University of Education, Ho
Chi Minh City, Vietnam., Boris S. Mordukhovich†††Department of Mathematics,
Wayne State University, Detroit, Michigan, USA. E-mail<EMAIL_ADDRESS>Research of this author was partly supported by the US National Science
Foundation under grants DMS-1512846 and DMS-1808978, by the US Air Force
Office of Scientific Research under grant #15RT0462, and by the Australian
Research Council under Discovery Project DP-190100555., Vo Thanh Phat
‡‡‡Department of Mathematics, HCMC University of Education, Ho Chi Minh City,
Vietnam and Department of Mathematics, Wayne State University, Detroit,
Michigan, USA. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>Research of
this author was partly supported by the US National Science Foundation under
grants DMS-1512846 and DMS-1808978, and by the US Air Force Office of
Scientific Research under grant #15RT0462., Dat Ba Tran §§§Department of
Mathematics, Wayne State University, Detroit, Michigan, USA. E-mails:
<EMAIL_ADDRESS>Research of this author was partly supported by the US
National Science Foundation under grant DMS-1808978..

Abstract. The paper proposes and develops new globally convergent algorithms
of the generalized damped Newton type for solving important classes of
nonsmooth optimization problems. These algorithms are based on the theory and
calculations of second-order subdifferentials of nonsmooth functions with
employing the machinery of second-order variational analysis and generalized
differentiation. First we develop a globally superlinearly convergent damped
Newton-type algorithm for the class of continuously differentiable functions
with Lipschitzian gradients, which are nonsmooth of second order. Then we
design such a globally convergent algorithm to solve a structured class of
nonsmooth quadratic composite problems with extended-real-valued cost
functions, which typically arise in machine learning and statistics. Finally,
we present the results of numerical experiments and compare the performance of
our main algorithm applied to an important class of Lasso problems with those
achieved by other first-order and second-order optimization algorithms.
Keywords. Variational analysis and nonsmooth optimization, damped Newton
methods, global convergence, tilt stability of minimizers, superlinear
convergence, Lasso problems.

##  1 Introduction

This paper is mainly devoted to the design, justification, and applications of
globally convergent Newton-type algorithms to solve nonsmooth (of the first or
second order) optimization problems in finite-dimensional spaces. Considering
the unconstrained optimization problem

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

with a continuously differentiable (${\cal C}^{1}$-smooth) cost function
$\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$, recall that one of the most
natural and efficient approaches to solve (1.1) globally is by using line
search methods; see, e.g., [20, 33, 53] and the references therein. Given a
starting point $x^{0}\in\mathbb{R}^{n}$, such methods construct an iterative
procedure of the form

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

where $\tau_{k}\geq 0$ is a step size at iteration $k$, and where $d^{k}\neq
0$ is a search direction. The precise choice of $d^{k}$ and $\tau_{k}$ at each
iteration in (1.2) distinguishes one algorithm from another. The main goal of
line search methods is to construct a sequence of iterates $\\{x^{k}\\}$ such
that the corresponding sequence $\\{\varphi(x^{k})\\}$ is decreasing. Recall
also that the condition $\langle\nabla\varphi(x^{k}),d^{k}\rangle<0$ on
$d^{k}$ ensures that it is a descent direction at $x^{k}$, i.e., there exists
$\bar{\tau}_{k}\in(0,1]$ such that $\varphi(x^{k}+\tau d^{k})<\varphi(x^{k})$
for all $\tau\in[0,\bar{\tau}_{k}]$. There are many choices of the direction
$d^{k}$ that satisfies this condition. For instance, a classical choice for
the search direction is $d^{k}:=-\nabla\varphi(x^{k})$ when the resulting
algorithm is known as the gradient algorithm or steepest descent method; see
[2, 8, 20, 33, 52, 57] for more details and impressive further developments of
gradient and subgradient methods.

If $\varphi$ is twice continuously differentiable (${\cal C}^{2}$-smooth) and
the Hessian matrix $\nabla^{2}\varphi(x^{k})$ is positive-definite for each
$k\in{\rm I\\!N}$, then another choice of search directions in (1.2) is
provided by solving the linear equation

$-\nabla\varphi(x^{k})=\nabla^{2}\varphi(x^{k})d^{k},$ (1.3)

where $d^{k}$ is known as a Newton direction. In this case, algorithm (1.2)
with the backtracking line search is called the damped/guarded Newton method
[2, 8] to distinguish it from the pure Newton method, which uses a fixed step
size $\tau=1$; see, e.g., the books [16, 20, 33, 35] with the comprehensive
commentaries and references therein. It has been well recognized that the
latter method exhibits a local convergence with quadratic rate.

There exist various extensions of the pure Newton method to solve
unconstrained optimization problems (1.1), where the cost functions $\varphi$
are not ${\cal C}^{2}$-smooth but belong merely to the class ${\cal C}^{1,1}$
of continuously differentiable functions with Lipschitz continuous gradients,
i.e., being nonsmooth of second order. We refer the reader to [6, 16, 20, 33,
34, 35, 49, 59, 66] and the vast bibliographies therein for a variety of
results in this direction, where mostly a local superlinear convergence rate
was achieved, while in some publications certain globalization procedures were
also suggested and investigated.

The first goal of this paper is to develop a globally convergent damped Newton
method of type (1.2), (1.3) to solve problems (1.1) with cost functions
$\varphi$ of class ${\cal C}^{1,1}$. Our approach is based on replacing the
classical Hessian matrix $\nabla^{2}\varphi$ in equation (1.3) by the
inclusion

$-\nabla\varphi(x^{k})\in\partial^{2}\varphi(x^{k})(d^{k}),\quad
k=0,1,\ldots,$ (1.4)

where $\partial^{2}\varphi$ stands for second-order
subdifferential/generalized Hessian of $\varphi$ in the sense of Mordukhovich
[43]. This construction has been largely used in variational analysis and its
applications with deriving comprehensive calculus rules and complete
computations of $\partial^{2}\varphi$ for broad classes of composite functions
that often appeared in important problems of optimization, optimal control,
stability, applied sciences, etc.; see, e.g., [12, 14, 15, 17, 18, 30, 44, 45,
46, 47, 48, 54, 56, 61, 67] with further references therein. The second-order
subdifferentials have been recently employed in [49] and [34] for the design
and justifications of generalized algorithms of the pure Newton type to find
stable local minimizers of (1.1) as well as solutions of gradient equations
and subgradient inclusions associated with ${\cal C}^{1,1}$ and prox-regular
functions, respectively.

In this paper we obtain efficient conditions ensuring that the iterative
sequence generated by the damped Newton-type algorithm in (1.2), (1.3) is
well-defined (i.e., the algorithm solvability), and that the iterative
sequence global converges to a tilt-stable local minimizer of (1.1) in the
sense of Poliquin and Rockafellar [56]. It is shown that the rate of
convergence of our algorithm is at least linear, while the superlinear
convergence of the algorithm is achieved under the additional semismooth∗
assumption on $\nabla\varphi$ in the sense of Gfrerer and Outrata [26].

The next major goal of the paper is to design, for the first time in the
literature, a globally convergent damped Newton algorithm of solving nonsmooth
problems of convex composite optimization given in the form:

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

where $f$ is a convex quadratic function defined by $f(x):=\frac{1}{2}\langle
Ax,x\rangle+\langle b,x\rangle+\alpha$ with $b\in\mathbb{R}^{n}$,
$\alpha\in\mathbb{R}$, and $A\in\mathbb{R}^{n\times n}$ being a positive-
semidefinite matrix, and where
$g\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}:=(-\infty,\infty]$ is a lower
semicontinuous (l.s.c.) extended-real-valued convex function. Problems in this
format frequently arise in many applied areas such as machine learning,
compressed sensing, and image processing. Since $g$ is generally extended-
real-valued, the unconstrained format (1.5) encompasses problems of
constrained optimization. If, in particular, $g$ is the indicator function of
a closed and convex set, then (1.5) becomes a constrained quadratic
optimization problems studied, e.g., in the book [53] with numerous
applications. Problems of this type are important in their own sake, while
they also appear as subproblems in various numerical algorithms including
sequential quadratic programming (SQP) methods, augmented Lagrangian methods,
proximal Newton methods, etc. One of the most well-known algorithms to solve
(1.5) is the forward-backward splitting (FBS) or proximal splitting method
[13, 39]. Since this method is of first order, its rate of convergence is at
most linear. Another approach to solve (1.5) is to use second-order methods
such as proximal Newton methods, proximal quasi-Newton methods, etc.; see,
e.g., [5, 36, 50]. Although the latter approach has several benefits over
first-order methods (as rapid convergence and high accuracy), a severe
limitation of these methods is the cost of solving subproblems.

In this paper we offer a different approach to solve problems (1.5) globally
by developing a generalized damped Newton algorithm based on the second-order
subdifferential scheme (1.4), advanced machinery of second-order variational
analysis with the usage of the proximal mapping for $g$. As revealed below,
the latter mapping can be constructively computed for many particular classes
of problems arising in machine learning, statistics, etc. Proceeding in this
way, we justify the well-posedness and global linear convergence of the
proposed algorithm for (1.5) with presenting efficient conditions for its
superlinear convergence.

The last topic of this paper concerns applications of the our generalized
damped Newton method (GDNM) to solving an important class of Lasso problems,
which appear in many areas of applied sciences and are discussed in detail in
what follows. Problems of this class can be written in form (1.5) with a
quadratic loss function $f$ and a nonsmooth regularizer function $g$ given in
special norm-type forms. For such problems, all the parameters of GDNM and its
justification (first- and second-order subdifferentials, proximal mappings,
conditions for convergence and convergence rates) can be computed and
expressed entirely in terms of the problem data, which thus leads us the
constructive globally superlinearly convergent realization of GDNM. Finally,
we conduct MATLAB numerical experiments of solving the basic version of the
Lasso problem described by Tibshirani [64] and then compare the obtained
numerical results with those achieved by using well-recognized first-order and
second-order methods. They include: Alternating Direction Methods of
Multipliers (ADMM) [22, 23], Nesterov’s Accelerated Proximal Gradient with
Backtracking (APG) [51, 52], Fast Iterative Shrinkage-Thresholding Algorithm
with constant step size (FISTA) [4], and a highly efficient Semismooth Newton
Augmented Lagrangian Method (SSNAL) from [37].

The rest of the paper is organized as follows. Section 2 presents and
discusses some basic notions of variational analysis and generalized
differentiation, which are broadly used in the formulations and proofs of the
main results. Section 3 is devoted to the development and justification of the
globally convergent GDNM to solve unconstrained optimization problems (1.1)
with ${\cal C}^{1,1}$ cost functions. In Section 4 we present results on the
linear and superlinear convergence of GDNM for problems of ${\cal C}^{1,1}$
optimization. Section 5 addresses developing GDNM for nonsmooth problems of
convex composite optimization with cost functions given as sums of convex
quadratic and convex extended-real-valued ones. In Section 6 we specify the
obtained results for the basic class of Lasso problems under consideration and
present the results of numerical experiments and their comparison with other
first-order and second-order methods for solving Lasso problems. The
concluding Section 7 summarizes the major contributions of the paper and
discusses topics of future research.

##  2 Preliminaries from Variational Analysis

In this section we review the needed background from variational analysis and
generalized differentiation by following the books [44, 45, 62], where the
reader can find more details and references. Our notation is standard in
variational analysis and optimization and can be found in the aforementioned
books.

Given a set $\Omega\subset\mathbb{R}^{s}$ with $\bar{z}\in\Omega$, the
(Fréchet) regular normal cone to $\Omega$ at $\bar{z}\in\Omega$ is

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

where the symbol $z\overset{\Omega}{\rightarrow}\bar{z}$ stands for
$z\to\bar{z}$ with $z\in\Omega$. The (Mordukhovich) limiting normal cone to
$\Omega$ at $\bar{z}\in\Omega$ is defined by

$N_{\Omega}(\bar{z}):=\big{\\{}v\in\mathbb{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.6)

Given further a set-valued mapping
$F\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ with the graph

$\mbox{\rm
gph}\,F:=\big{\\{}(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}\;\big{|}\;y\in
F(x)\big{\\}},$

the (basic/limiting) coderivative of $F$ at $(\bar{x},\bar{y})\in\mbox{\rm
gph}\,F$ is defined via the limiting normal cone (2.6) to the graph of $F$ at
the reference point $(\bar{x},\bar{y})$ as

$D^{*}F(\bar{x},\bar{y})(v):=\big{\\{}u\in\mathbb{R}^{n}\;\big{|}\;(u,-v)\in
N_{{\rm gph}\,F}(\bar{x},\bar{y})\big{\\}},\quad v\in\mathbb{R}^{m},$ (2.7)

where $\bar{y}$ is omitted in the coderivative notation if
$F(\bar{x})=\\{\bar{y}\\}$. Note that if
$F\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ is a (single-valued) ${\cal
C}^{1}$-smooth mapping around $\bar{x}$, then we have

$D^{*}F(\bar{x})(v)=\big{\\{}\nabla F(\bar{x})^{*}v\big{\\}}\;\mbox{ for all
}\;v\in\mathbb{R}^{m}$

in terms of the transpose matrix (adjoint operator) $\nabla F(\bar{x})^{*}$ of
the Jacobian $\nabla F(\bar{x})$. Recall further that a set-valued mapping
$F:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is metrically regular around
$(\bar{x},\bar{y})\in\text{\rm gph}F$ with modulus $\mu>0$ if there exist
neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{y}$ such that

${\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,$

where $F^{-1}(y):=\\{x\in\mathbb{R}^{n}\;|\;y\in F(x)\\}$ is the inverse
mapping of $F$. If in addition $F^{-1}$ has a single-valued localization
around $(\bar{y},\bar{x})$, i.e., there exist some neighborhoods $U$ of
$\bar{x}$ and $V$ of $\bar{y}$ together with a single-valued mapping
$\vartheta:V\to U$ such that $\text{\rm gph}F^{-1}\cap(V\times U)=\text{\rm
gph}\vartheta$, then $F$ is strongly metrically regular around
$(\bar{x},\bar{y})$ with modulus $\mu>0$. A set-valued mapping
$T:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is locally strongly monotone
with modulus $\tau>0$ around $(\bar{x},\bar{y})\in\text{\rm gph}T$ if there
exist neighborhoods $U$ of $\bar{x}$ and $V$ of $\bar{y}$ such that

$\langle x-u,v-w\rangle\geq\tau\|x-u\|^{2}\quad\text{for all
}\;(x,v),(u,w)\in\text{\rm gph}T\cap(U\times V).$

If in addition $\text{\rm gph}T\cap(U\times V)=\text{\rm gph}S\cap(U\times V)$
for any monotone operator $S:\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$
satisfying the inclusion $\text{\rm gph}T\cap(U\times V)\subset\text{\rm
gph}S$, $T$ is called locally strongly maximally monotone with modulus
$\tau>0$ around $(\bar{x},\bar{y})$.
Let $\varphi\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be an extended-real-
valued function with the domain and epigraph

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

The (basic/limiting) subdifferential of $\varphi$ at $\bar{x}\in\mbox{\rm
dom}\,\varphi$ is defined geometrically

$\partial\varphi(\bar{x}):=\big{\\{}v\in\mathbb{R}^{n}\;\big{|}\;(v,-1)\in
N_{{\rm\small epi}\,\varphi}\big{(}\bar{x},\varphi(\bar{x})\big{)}\big{\\}}$
(2.8)

via the limiting normal cone (2.6), while admitting various analytic
representations. This subdifferential is an extension of the classical
gradient for smooth functions and of the classical subdifferential of convex
ones. If $F\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ is locally Lipschitzian
around $\bar{x}$, then we have the useful relationships between the
coderivative (2.7) of $F$ and the subdifferential (2.8) of the scalarized
function $\langle v,F\rangle(x):=\langle v,F(x)\rangle$ formulated as

$D^{*}F(\bar{x})(v)=\partial\langle v,F\rangle(\bar{x})\;\mbox{ for all
}\;v\in\mathbb{R}^{m}.$ (2.9)

Following [43], we now define the second-order subdifferential
$\partial^{2}\varphi(\bar{x},\bar{v})\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$
of $\varphi\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ at
$\bar{x}\in\mbox{\rm dom}\,\varphi$ for $\bar{v}\in\partial\varphi(\bar{x})$
as the coderivative (2.7) of the subgradient mapping (2.8), i.e., by

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

If $\varphi$ is ${\cal C}^{2}$-smooth around $\bar{x}$, then we have the
representation of the second-order subdifferential via the classical
(symmetric) Hessian matrix

$\partial^{2}\varphi(\bar{x})(u)=\big{\\{}\nabla^{2}\varphi(\bar{x})u\big{\\}}\;\mbox{
for all }\;u\in\mathbb{R}^{n},$ (2.11)

which allows us to also label (2.10) as the generalized Hessian. In the case
of ${\cal C}^{1,1}$ functions $\varphi$, the second-order subdifferential
(2.10) is computed by the scalarization formula (2.9) via the coderivative of
the gradient mapping $\nabla\varphi$. In Section 1, the reader can find the
references to many publications where the second-order subdifferential is
computed entirely via the given data for major classes of systems appeared in
variational analysis and optimization. It is important to mention that our
basic constructions (2.6)–(2.8) and (2.10), enjoy comprehensive calculus rules
in general settings, despite being intrinsically nonconvex. This is due to
variational/extremal principles of variational analysis; see the books [44,
45, 62] for the first-order constructions and [44, 45] for the second-order
subdifferential (2.10).

In what follows we are going to broadly employ the fundamental notion of tilt
stability of local minimizers for extended-real-valued functions, which was
introduced by Poliquin and Rockafellar [56] and characterized therein in terms
of the second-order subdifferential (2.10).

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

Given $\varphi\colon\mathbb{R}^{n}\to\overline{\mathbb{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 a neighborhood of
$0\in\mathbb{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.

Besides the seminal paper [56], the notion of tilt stability has been largely
investigated, characterized, and widely applied in many publications to
various classes of unconstrained and constrained optimization problems; see,
e.g., [11, 17, 18, 25, 45, 46, 48] and the references therein.

##  3 Globally Convergent GDNM in $\mathcal{C}^{1,1}$ Optimization

In this section we concentrate on the unconstrained optimization problem
(1.1), where the cost function $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ is
of class $\mathcal{C}^{1,1}$ around the reference points. The corresponding
gradient equation associated with (1.1), which gives us, in particular, a
necessary condition for local minimizers, is written in the form

$\nabla\varphi(x)=0.$ (3.12)

The following generalization of the pure Newton algorithm to solve (1.1)
locally was first suggested and investigated in [49] under the major
assumption that a given point $\bar{x}$ is a tilt-stable local minimizer of
(1.1). Then it was extended in [34] to solve directly the gradient equation
(3.12) under certain assumptions on a given solution $\bar{x}$ to (3.12)
ensuring the well-posedness and local superlinear convergence of the
algorithm.

######  Algorithm 3.1 (generalized pure Newton-type algorithm for ${\cal
C}^{1,1}$ functions).

Step 0: Choose a starting point $x^{0}\in\mathbb{R}^{n}$ and set $k=0$.
Step 1: If $\nabla\varphi(x^{k})=0$, stop the algorithm. Otherwise move to
Step 2.
Step 2: Choose $d^{k}\in\mathbb{R}^{n}$ satisfying

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

Step 3: Set $x^{k+1}$ given by

$x^{k+1}:=x^{k}+d^{k}\;\mbox{ for all }\;k=0,1,\ldots.$

Step 4: Increase $k$ by $1$ and go to Step 1.

One of the serious disadvantages of the pure Newton method and its
generalizations is that the corresponding sequence of iterates may not
converges if the stating point is not sufficiently close to the solution. This
motivates us to design and justify the globally convergent damped Newton
counterpart of Algorithm 3.1 with backtracking line search to solve the
gradient equation (3.12) that is formalized as follows.

######  Algorithm 3.2 (generalized damped Newton algorithm for
$\mathcal{C}^{1,1}$ functions).

Let $\sigma\in\left(0,\frac{1}{2}\right)$ and $\beta\in\left(0,1\right)$ be
given real numbers. Then do the following:
Step 0: Choose an arbitrary staring point $x^{0}\in\mathbb{R}^{n}$ and set
$k=0$.
Step 1: If $\nabla\varphi(x^{k})=0$, stop the algorithm. Otherwise move to
Step 2.
Step 2: Choose $d^{k}\in\mathbb{R}^{n}$ such that

$-\nabla\varphi(x^{k})\in\partial^{2}\varphi(x^{k})(d^{k}).$ (3.13)

Step 3: Set $\tau_{k}=1$. Until Armijo’s inequality

$\varphi(x^{k}+\tau_{k}d^{k})\leq\varphi(x^{k})+\sigma\tau_{k}\langle\nabla\varphi(x^{k}),d^{k}\rangle.$

is satisfied, set $\tau_{k}:=\beta\tau_{k}$.
Step 4: Set $x^{k}$ given by

$x^{k+1}:=x^{k}+\tau_{k}d^{k}\;\mbox{ for all }\;k=0,1,\ldots.$

Step 5: Increase $k$ by $1$ and go to Step 1.

Due to (2.11), Algorithm 3.2 reduces to the standard damped Newton method (as,
e.g., in [2, 8]) if $\varphi$ is $\mathcal{C}^{2}$-smooth. Note also that by
(2.7) the direction $d^{k}$ in (3.13) can be explicitly found from

$\big{(}-\nabla\varphi(x^{k}),-d^{k}\big{)}\in
N\big{(}(x^{k},\nabla\varphi(x^{k}));\mbox{\rm gph}\,\nabla\varphi\big{)}.$

To proceed with the study of Algorithm 3.2, first we clarify the existence of
descent Newton directions. It is done in the next proposition under the
positive-definiteness of the second-order subdifferential mapping
$\partial^{2}\varphi(x)$.

######  Proposition 3.3 (existence of descent Newton directions).

Let $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ be of class $\mathcal{C}^{1,1}$
around $x\in\mathbb{R}^{n}$. Suppose that $\nabla\varphi(x)\neq 0$ and that
$\partial^{2}\varphi(x)$ is positive-definite, i.e.,

$\langle z,u\rangle>0\;\mbox{ for all }\;z\in\partial^{2}\varphi(x)(u)\;\mbox{
and }\;u\neq 0.$ (3.14)

Then there exists a nonzero direction $d\in\mathbb{R}^{n}$ such that

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

Moreover, every such direction satisfies the inequality
$\langle\nabla\varphi(x),d\rangle<0$. Consequently, for each $\sigma\in(0,1)$
and $d\in\mathbb{R}^{n}$ satisfying (3.15) we have $\delta>0$ such that

$\varphi(x+\tau
d)\leq\varphi(x)+\sigma\tau\langle\nabla\varphi(x),d\rangle\;\mbox{ whenever
}\;\tau\in(0,\delta).$ (3.16)

[Proof.] It follows from [45, Theorem 5.16] that $\nabla\varphi$ is strongly
locally maximal monotone around $(x,\nabla\varphi(x))$. Thus $\nabla\varphi$
is strongly metrically regular around $(x,\nabla\varphi(x))$ by [45, Theorem
5.13]. Using [34, Theorem 4.2] yields the existence of $d\in\mathbb{R}^{n}$
with $-\nabla\varphi(x)\in\partial^{2}\varphi(x)(d)$. To verify that $d\neq
0$, suppose on the contrary that $d=0$. Since $\nabla\varphi$ is locally
Lipschitz around $x$, it follows from [44, Theorem 1.44] that

$\partial^{2}\varphi(x)(d)=\big{(}D^{*}\nabla\varphi\big{)}(x)(d)=\big{(}D^{*}\nabla\varphi\big{)}(x)(0)=\\{0\\}.$

Therefore, we have that $\nabla\varphi(x)=0$ due to the inclusion
$-\nabla\varphi(x)\in\partial^{2}\varphi(x)(d)$, which contradicts the
assumption that $\nabla\varphi(x)\neq 0$. Employing the imposed positive-
definiteness of the mapping $\partial^{2}\varphi(x)$ tells us that
$\langle\nabla\varphi(x),d\rangle<0$. Using finally [33, Lemmas 2.18 and
2.19], we arrive at (3.16) and thus complete the proof of the proposition.

Now we formulate and discuss our major assumption to establish the desired
global behavior of Algorithm 3.2 for $\mathcal{C}^{1,1}$ functions $\varphi$.
Fix an arbitrary point $x^{0}\in\mathbb{R}^{n}$ and consider the level set

$\Omega:=\big{\\{}x\in\mathbb{R}^{n}\;\big{|}\;\varphi(x)\leq\varphi(x^{0})\big{\\}}.$
(3.17)

######  Assumption 1.

The mapping
$\partial^{2}\varphi(x)\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{n}$ is
positive-definite (3.14) for all $x\in\Omega$.

Observe that Assumption 1 cannot be removed or even replaced by the positive-
semidefiniteness of $\partial^{2}\varphi(x)$ to ensure the existence of
descent Newton direction for Algorithm 3.2 as in Proposition 3.3. Indeed,
consider the simplest linear function $\varphi(x):=x$ on $\mathbb{R}$. Then we
obviously have that $\nabla^{2}\varphi(x)\geq 0$ for all $x\in\mathbb{R}$,
while there is no Newtonian direction $d\in\mathbb{R}$ satisfying the
backtracking line search condition (3.16).

The next theorem shows that Assumption 1 not only ensures the well-posedness
of Algorithm 3.2, but also allows us to conclude that all the limiting points
of the iterative sequence $\\{x^{k}\\}$ are tilt-stable minimizers of the cost
function $\varphi$.

######  Theorem 3.4 (well-posedness and limiting points of the generalized
damped Newton algorithm).

Let $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ be of class
$\mathcal{C}^{1,1}$, and let $x^{0}\in\mathbb{R}^{n}$ be an arbitrary point
such that Assumption 1 is satisfied. Then we have the following assertions:

  * (i)

Any sequence $\\{x^{k}\\}$ generated by Algorithm 3.2 is well-defined with
$x^{k}\in\Omega$ for all $k\in{\rm I\\!N}$.

  * (ii)

All the limiting points of $\\{x^{k}\\}$ are tilt-stable local minimizers of
$\varphi$.

[Proof.] First we check that a sequence $\\{x^{k}\\}$ generated by Algorithm
3.2 with any starting point $x^{0}$ is well-defined. Indeed, there is nothing
to prove if $\nabla\varphi(x^{0})=0$. Otherwise, it follows from Proposition
3.3 due to the positive-definiteness of $\partial^{2}\varphi(x^{0})$ that
there exist $d^{0}$ and $\tau_{0}$ satisfying
$-\nabla\varphi(x^{0})\in\partial^{2}\varphi(x^{0})(d^{0})$ and the
inequalities

$\varphi(x^{1})\leq\varphi(x^{0})+\sigma\tau_{0}\langle\nabla\varphi(x^{0}),d^{0}\rangle<\varphi(x^{0}),$

which clearly ensure that $x^{1}\in\Omega$. Then we get by induction that
either $x^{k}\in\Omega$, or $\nabla\varphi(x^{k})=0$ whenever $k\in{\rm
I\\!N}$. Thus assertion (i) is verified.

Next we prove assertion (ii). To proceed, suppose that $\\{x^{k}\\}$ has a
limiting point $\bar{x}\in\mathbb{R}^{n}$, i.e., there exists a subsequence
$\\{x^{k_{j}}\\}_{j\in{\rm I\\!N}}$ of $\\{x^{k}\\}$ such that
$x^{k_{j}}\to\bar{x}$ as $j\to\infty$. Since $\Omega$ is closed and since
$x^{k_{j}}\in\Omega$ for all $j\in{\rm I\\!N}$, we get $\bar{x}\in\Omega$. By
Assumption 1, the mapping $\partial^{2}\varphi(\bar{x})$ is positive-definite.
Then [10, Proposition 4.6] gives us positive numbers $\kappa$ and $\delta$
such that

$\langle z,w\rangle\geq\kappa\|w\|^{2}\quad\text{for all
}\;z\in\partial^{2}\varphi(x)(w),\;x\in\mathbb{B}_{\delta}(\bar{x}),\;\mbox{
and }\;w\in\mathbb{R}^{n}.$ (3.18)

Since $\varphi$ is of class ${\cal C}^{1,1}$ around $\bar{x}$, we get without
loss of generality that $\nabla\varphi$ is Lipschitz continuous on
$\mathbb{B}_{\delta}(\bar{x})$ with some constant $\ell>0$. The rest of the
proof is split into the following two claims.
Claim 1: The sequence $\\{\tau_{k_{j}}\\}_{j\in{\rm I\\!N}}$ in Algorithm 3.2
is bounded from below by a positive number $\gamma>0$. Indeed, suppose on the
contrary that the statement does not hold. Combining this with $\tau_{k}\geq
0$ gives us a subsequence of $\\{\tau_{k_{j}}\\}$ that converges to $0$.
Suppose without loss of generality that $\tau_{k_{j}}\to 0$ as $j\to\infty$.
Since $-\nabla\varphi(x^{k_{j}})\in\partial^{2}\varphi(x^{k_{j}})(d^{k_{j}})$
for all $j\in{\rm I\\!N}$, we deduce from (3.18) and the Cauchy-Schwarz
inequality that

$\|\nabla\varphi(x^{k_{j}})\|\geq\kappa\|d^{k_{j}}\|\;\mbox{ whenever
}\;j\in{\rm I\\!N},$

which verifies the boundedness of $\\{d^{k_{j}}\\}$. Thus
$x^{k_{j}}+\beta^{-1}\tau_{k_{j}}d^{k_{j}}\to\bar{x}$ as $j\to\infty$, and
hence

$x^{k_{j}}+\beta^{-1}\tau_{k_{j}}d^{k_{j}}\in\mathbb{B}_{\delta}(\bar{x})$

for all $j\in{\rm I\\!N}$ sufficiently large. Since $\varphi$ is of class
${\cal C}^{1,1}$ around $\bar{x}$, we suppose without loss of generality that
$\nabla\varphi$ is Lipschitz continuous on $\mathbb{B}_{\delta}(\bar{x})$. It
follows then from [33, Lemma A.11] that

$\varphi(x^{k_{j}}+\beta^{-1}\tau_{k_{j}}d^{k_{j}})\leq\varphi(x^{k_{j}})+\beta^{-1}\tau_{k_{j}}\langle\nabla\varphi(x^{k_{j}}),d^{k_{j}}\rangle+\frac{\ell\beta^{-2}\tau_{k_{j}}^{2}}{2}\|d^{k_{j}}\|^{2}$
(3.19)

whenever indices $j\in{\rm I\\!N}$ are sufficiently large. Due to the exit
condition of the backtracking line search in Step 3 of Algorithm 3.2, we have
the strict inequality

$\varphi(x^{k_{j}}+\beta^{-1}\tau_{k_{j}}d^{k_{j}})>\varphi(x^{k_{j}})+\sigma\beta^{-1}\tau_{k_{j}}\langle\nabla\varphi(x^{k_{j}}),d^{k_{j}}\rangle$
(3.20)

for large $j\in{\rm I\\!N}$. Now combining (3.18), (3.19), and (3.20) for such
$j$ yields the estimates

$\displaystyle\sigma\beta^{-1}\tau_{k_{j}}\langle\nabla\varphi(x^{k_{j}}),d^{k_{j}}\rangle$
$\displaystyle<$
$\displaystyle\beta^{-1}\tau_{k_{j}}\langle\nabla\varphi(x^{k_{j}}),d^{k_{j}}\rangle+\frac{\ell\beta^{-2}\tau_{k_{j}}^{2}}{2}\|d^{k_{j}}\|^{2}$
$\displaystyle\leq$
$\displaystyle\beta^{-1}\tau_{k_{j}}\langle\nabla\varphi(x^{k_{j}}),d^{k_{j}}\rangle+\frac{\ell\beta^{-2}\tau_{k_{j}}^{2}}{2\kappa}\langle\nabla\varphi(x^{k_{j}}),-d^{k_{j}}\rangle,$

which imply in turn that $\sigma\beta>\beta-\frac{\ell}{2\kappa}\tau_{k_{j}}$
for all large $j\in{\rm I\\!N}$. Letting $j\to\infty$ gives us
$\sigma\beta\geq\beta$, a contradiction due to $\sigma<1$ and $\beta>0$. This
justifies the claimed boundedness of $\\{\tau_{k_{j}}\\}_{j\in{\rm I\\!N}}$.
Claim 2: Any limiting point $\bar{x}$ of $\\{x^{k}\\}$ is a tilt-stable local
minimizer of $\varphi$. Indeed, it follows from the continuity of the gradient
$\nabla\varphi$ and the convergence $x^{k_{j}}\to\bar{x}$ that
$\nabla\varphi(x^{k_{j}})\to\nabla\varphi(\bar{x})$ as $j\to\infty$. Since the
sequence $\\{\varphi(x^{k})\\}$ is nonincreasing, we get that
$\varphi(\bar{x})$ is a lower bound for $\\{\varphi(x^{k})\\}$. Thus the
sequence $\\{\varphi(x^{k})\\}$ must converge to $\varphi(\bar{x})$ as
$k\to\infty$. It follows from [44, Theorem 1.44] due to
$-\nabla\varphi(x^{k_{j}})\in\partial^{2}\varphi(x^{k_{j}})(d^{k_{j}})$ and
the Lipschitz continuity of $\nabla\varphi$ on $\mathbb{B}_{\delta}(\bar{x})$
with constant $\ell$ that

$\|\nabla\varphi(x^{k_{j}})\|\leq\ell\|d^{k_{j}}\|\;\text{ for sufficiently
large }\;j\in{\rm I\\!N}.$ (3.21)

Combining Claim 1 with the estimates in (3.18) and (3.21), we find
$j_{0}\in{\rm I\\!N}$ such that

$\varphi(x^{k_{j}})-\varphi(x^{k_{j}+1})\geq\sigma\tau_{k_{j}}\langle-\nabla\varphi(x^{k_{j}}),d^{k_{j}}\rangle\geq\sigma\gamma\kappa\|d^{k_{j}}\|^{2}\geq\sigma\gamma\kappa\ell^{-2}\|\nabla\varphi(x^{k_{j}})\|^{2},\;j\geq
j_{0}.$ (3.22)

Since $\\{\varphi(x^{k})\\}$ is convergent, it follows that the sequence
$\\{\varphi(x^{k_{j}})-\varphi(x^{k_{j}+1})\\}_{j\in{\rm I\\!N}}$ converges to
$0$ as $j\to\infty$. Furthermore, we deduce from $\eqref{ineq}$ that
$\\{\|\nabla\varphi(x^{k_{j}})\|\\}$ also converges to $0$, and therefore
$\nabla\varphi(\bar{x})=0$. Combining the latter with the positive-
definiteness of $\partial^{2}\varphi(\bar{x})$ tells us by [56, Theorem 1.3]
that $\bar{x}$ is a tilt-stable local minimizer of $\varphi$. This completes
the proof.

######  Remark 3.5 (iterative sequences may diverge).

Note that Theorem 3.4 does not claim anything about the convergence of the
iterative sequence $\\{x^{k}\\}$. In fact, the divergence of such a sequence
can be observe in simple situations under the fulfillment of all the
assumptions of Theorem 3.4. To illustrate it, consider the function
$\varphi(x):=e^{x}$ on $\mathbb{R}$ with the positive second derivative
$\varphi^{\prime\prime}(x)=e^{x}>0$ for all $x\in\mathbb{R}$. Running
Algorithm 3.2 with the starting point $x^{0}=1$, it is not hard to check that
$\tau_{k}=1$ and $d^{k}=-1$ for all $k\in{\rm I\\!N}$. Thus the sequence of
$x^{k}=1-k$ as $k\in{\rm I\\!N}$ generated by Algorithm 3.2 is obviously
divergent.

We conclude this section by giving a simple additional condition to Assumption
1 that ensures the global convergence of any sequence of iterates in Algorithm
3.2.

######  Assumption 2.

The level set $\Omega$ from (3.17) is bounded.

To establish the global convergence of Algorithm 3.2, we first present the
following useful lemma of its own interest.

######  Lemma 3.6 (uniformly positive-definiteness of second-order
subdifferentials).

Let $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ be a function of class
$\mathcal{C}^{1,1}$, and let $x^{0}$ be arbitrary vector for which Assumptions
1 and 2 are satisfied. Then there exists $\kappa>0$ such that for each
$x\in\Omega$ we have

$\langle z,w\rangle\geq\kappa\|w\|^{2}\;\mbox{ whenever
}\;z\in\partial^{2}\varphi(x)(w)\;\mbox{ and }\;w\in\mathbb{R}^{n}.$ (3.23)

[Proof.] Since the mapping $\partial^{2}\varphi(x)$ is positive-definite for
each $x\in\Omega$ by Assumption 1, we deduce from [10, Proposition 4.6] that
there exist $\kappa_{x}>0$ and a neighborhood $U_{x}$ of $x$ such that

$\langle z,w\rangle\geq\kappa_{x}\|w\|^{2}\;\text{ for all
}\;z\in\partial^{2}\varphi(y)(w),\;y\in U_{x},\;\mbox{ and
}\;w\in\mathbb{R}^{n}.$ (3.24)

Note that the neighborhood system $\\{U_{x}\;|\;x\in\Omega\\}$ provides an
open cover of $\Omega$. Using the compactness of the set $\Omega$ due its
closedness and Assumption 2, we find finitely many points
$x_{1},\ldots,x_{p}\in\Omega$ such that
$\Omega\subset\bigcup_{j=1}^{p}U_{x_{j}}$. Denoting

$\kappa:={\rm min}\big{\\{}\kappa_{x_{1}},\ldots,\kappa_{x_{p}}\big{\\}}>0,$

we arrive at the fulfillment of the claimed condition (3.23) for each
$x\in\Omega$.

Now we are ready to justify the global convergence of Algorithm 3.2.

######  Theorem 3.7 (global convergence of the damped Newton algorithm for
${\cal C}^{1,1}$ functions).

In the setting of Theorem 3.4, suppose in addition that Assumption 2 is
satisfied. Then the sequence $\\{x^{k}\\}$ is convergent, and its limit is a
tilt-stable local minimizer of $\varphi$.

[Proof.] The well-definiteness of the sequence $\\{x^{k}\\}$ and the inclusion
$\\{x^{k}\\}\subset\Omega$ follow from Theorem 3.4. Furthermore, employing
Assumptions 1 and 2, the inclusion
$-\nabla\varphi(x^{k})\in\partial^{2}\varphi(x^{k})(d^{k})$ for all $k\in{\rm
I\\!N}$, and Proposition 3.6 ensures the existence of $\kappa>0$ such that

$\langle-\nabla\varphi(x^{k}),d^{k}\rangle\geq\kappa\|d^{k}\|^{2}\quad\text{for
all }\;k\in{\rm I\\!N}.$ (3.25)

Assumption 2 tells us that the sequence $\\{x^{k}\\}$ is bounded, and so it
has a limiting point $\bar{x}\in\Omega$. Hence the value $\varphi(\bar{x})$ is
a limiting point of the numerical sequence $\\{\varphi(x^{k})\\}$. Combining
this with the nonincreasing property of $\\{\varphi(x^{k})\\}$ yields the
convergence of $\\{\varphi(x^{k})\\}$ to $\varphi(\bar{x})$ as $k\to\infty$.
It follows from (3.25) that

$\varphi(x^{k})-\varphi(x^{k+1})\geq\sigma\tau_{k}\langle-\nabla\varphi(x^{k}),d^{k}\rangle\geq\sigma\tau_{k}\kappa\|d^{k}\|^{2}\;\text{
for all }\;k\in{\rm I\\!N}.$ (3.26)

The above convergence of $\\{\varphi(x^{k})\\}$ implies that the sequence
$\\{\varphi(x^{k})-\varphi(x^{k+1})\\}_{k\in{\rm I\\!N}}$ converges to $0$ as
$k\to\infty$. It follows from $\eqref{ineq1}$ that

$\lim_{k\to\infty}\tau_{k}\|d^{k}\|^{2}=0.$ (3.27)

Now let us show that the sequence $\\{x^{k}\\}$ converges to $\bar{x}$ as
$k\to\infty$ by using Ostrowski’s condition from [20, Proposition 8.3.10]. To
accomplish this, we verify that there is a neighborhood of $\bar{x}$ within
which no other limiting point of $\\{x^{k}\\}$ exists, and the following
condition holds:

$\lim_{k\to\infty}\|x^{k+1}-x^{k}\|=0.$ (3.28)

Indeed, tilt stability of the local minimizer $\bar{x}$ of $\varphi$ ensures
the existence of $\delta>0$ for which $\varphi$ is strongly convex on
$\mathbb{B}_{\delta}(\bar{x})$ due to [10, Theorem 4.7]. Arguing by
contraposition, suppose that there is
$\widetilde{x}\in\mathbb{B}_{\delta}(\bar{x})$ such that
$\widetilde{x}\neq\bar{x}$ and $\widetilde{x}$ is a limiting point of
$\\{x^{k}\\}$. Theorem 3.4 tells us that $\widetilde{x}$ is also a tilt-stable
local minimizer of $\varphi$, a contradiction with the strong convexity of
$\varphi$ on $\mathbb{B}_{\delta}(\bar{x})$. Moreover, the construction of
$\\{x^{k}\\}$ and the condition $\tau_{k}\in(0,1]$ imply the estimate

$\|x^{k+1}-x^{k}\|^{2}=\tau_{k}^{2}\|d^{k}\|^{2}\leq\tau_{k}\|d^{k}\|^{2}\;\mbox{
for all }\;k\in{\rm I\\!N}.$

Passing there to the limit as $k\to\infty$ and using (3.27), we verify (3.28).
Finally, it follows from [20, Proposition 8.3.10] that $\\{x^{k}\\}$ converges
to $\bar{x}$, which thus completes the proof.

##  4 Rates of Convergence of GDNM for ${\cal C}^{1,1}$ Optimization

This section is devoted to the study of convergence rates of the globally
convergent Algorithm 3.2 for minimizing ${\cal C}^{1,1}$ functions. First we
recall the standard notions of convergence rates used in what follows; see
[20, Definition 7.2.1].

######  Definition 4.1 (rates of convergence).

Let $\\{x^{k}\\}\subset\mathbb{R}^{n}$ be a sequence of vectors converging to
$\bar{x}$ as $k\to\infty$ with $\bar{x}\neq x^{k}$ for all $k\in{\rm I\\!N}$.
The convergence rate is said to be (at least):

  * (i)

R-linear if

$0<\limsup_{k\to\infty}\left(\|x^{k}-\bar{x}\|\right)^{1/k}<1,$

i.e., there exist $\mu\in(0,1)$, $c>0$, and $k_{0}\in{\rm I\\!N}$ such that

$\|x^{k}-\bar{x}\|\leq c\mu^{k}\quad\text{for all }\;k\geq k_{0}.$

  * (ii)

Q-linear if

$\limsup_{k\to\infty}\frac{\|x^{k+1}-\bar{x}\|}{\|x^{k}-\bar{x}\|}<1,$

i.e., there exist $\mu\in(0,1)$ and $k_{0}\in{\rm I\\!N}$ such that

$\|x^{k+1}-\bar{x}\|\leq\mu\|x^{k}-\bar{x}\|\quad\text{for all }\;k\geq
k_{0}.$

  * (iii)

Q-superlinear if

$\lim_{k\to\infty}\frac{\|x^{k+1}-\bar{x}\|}{\|x^{k}-\bar{x}\|}=0.$

Our first result here establishes the linear convergence of Algorithm 3.2
under the general assumptions formulated in the preceding section.

######  Theorem 4.2 (linear convergence of generalized damped Newton algorithm
for ${\cal C}^{1,1}$ functions).

In the setting of Theorem 3.4, suppose in addition that the sequence
$\\{x^{k}\\}$ converges to some vector $\bar{x}$ being such that
$x^{k}\neq\bar{x}$ for all $k\in{\rm I\\!N}$. Then we have the following
assertions:

  * (i)

The sequence $\\{\varphi(x^{k})\\}$ converges to $\varphi(\bar{x})$ at least
Q-linearly.

  * (ii)

The sequences $\\{x^{k}\\}$ and $\\{\|\nabla\varphi(x^{k})\|\\}$ converge to
$\bar{x}$ and $0$, respectively at least R-linearly.

[Proof.] Suppose that $\\{x^{k}\\}$ converges to $\bar{x}$. It follows from
Theorem 3.4 that $\bar{x}$ is a tilt-stable local minimizer of $\varphi$.
Using now the characterizations of tilt-stable local minimizers taken from
[10, Theorem 4.7], we deduce that there exist $\kappa>0$ and $\delta>0$ such
that $\varphi$ is strongly convex on $\mathbb{B}_{\delta}(\bar{x})$ with
modulus $\kappa$ while satisfying

$\langle z,w\rangle\geq\kappa\|w\|^{2}\quad\text{for all
}\;z\in\partial^{2}\varphi(x)(w),\;x\in\mathbb{B}_{\delta}(\bar{x}),\;\mbox{
and }\;w\in\mathbb{R}^{n}.$ (4.29)

Furthermore, due to the locally Lipschitz continuity around $\bar{x}$ of
$\nabla\varphi$, we suppose without loss of generality that $\nabla\varphi$ is
Lipschitz continuous on $\mathbb{B}_{\delta}(\bar{x})$ with some constant
$\ell>0$. The strong convexity of $\varphi$ on $\mathbb{B}_{\delta}(\bar{x})$
tells us that

$\varphi(x)\geq\varphi(u)+\langle\nabla\varphi(u),x-u\rangle+\frac{\kappa}{2}\|x-u\|^{2}\;\mbox{
and}$ (4.30)
$\langle\nabla\varphi(x)-\nabla\varphi(u),x-u\rangle\geq\kappa\|x-u\|^{2}\;\mbox{
for all }\;x,u\in\mathbb{B}_{\delta}(\bar{x}).$ (4.31)

Since $x^{k}\to\bar{x}$ as $k\to\infty$, we have that $x^{k}\in U$ for all
$k\in{\rm I\\!N}$ sufficiently large. Substituting $x:=x^{k}$ and $u:=\bar{x}$
into (4.30) and (4.31), and then using the Cauchy-Schwarz inequality together
with $\nabla\varphi(\bar{x})=0$ yield the estimates

$\varphi(x^{k})\geq\varphi(\bar{x})+\frac{\kappa}{2}\|x^{k}-\bar{x}\|^{2}\;\mbox{
and}$ (4.32) $\|\nabla\varphi(x^{k})\|\geq\kappa\|x^{k}-\bar{x}\|$ (4.33)

for all large $k\in{\rm I\\!N}$. The local Lipschitz continuity of
$\nabla\varphi$ around $\bar{x}$ and the result of [33, Lemma A.11] ensure the
existence of $\ell>0$ such that

$\varphi(x^{k})-\varphi(\bar{x})=|\varphi(x^{k})-\varphi(\bar{x})-\langle\nabla\varphi(\bar{x}),x^{k}-\bar{x}\rangle|\leq\frac{\ell}{2}\|x^{k}-\bar{x}\|^{2}\quad\text{for
large }\;k\in{\rm I\\!N}.$ (4.34)

Furthermore, the Lipschitz continuity of $\nabla\varphi$ on
$\mathbb{B}_{\delta}(\bar{x})$ together with the inclusion
$-\nabla\varphi(x^{k})\in\partial^{2}\varphi(x^{k})(d^{k})$ implies by [44,
Theorem 1.44] that

$\|\nabla\varphi(x^{k})\|\leq\ell\|d^{k}\|\quad\text{for large }\;k\in{\rm
I\\!N}.$ (4.35)

Proceeding similarly to the proof of Theorem 3.4 tells us that the sequence
$\\{\tau_{k}\\}$ is bounded from below by some constant $\gamma>0$. Combining
the latter with (4.29) and (4.35) yields

$\varphi(x^{k})-\varphi(x^{k+1})\geq\sigma\tau_{k}\langle-\nabla\varphi(x^{k}),d^{k}\rangle\geq\sigma\gamma\kappa\|d^{k}\|^{2}\geq\sigma\gamma\kappa\ell^{-2}\|\nabla\varphi(x^{k})\|^{2}$
(4.36)

for all large $k\in{\rm I\\!N}$. Therefore, for such $k$ we deduce from
(4.33), (4.34), and (4.36) that

$\varphi(x^{k+1})-\varphi(x^{k})\leq-\sigma\gamma\kappa\ell^{-2}\|\nabla\varphi(x^{k})\|^{2}\leq-\sigma\gamma\kappa^{3}\ell^{-2}\|x^{k}-\bar{x}\|^{2}\leq-2\sigma\gamma\kappa^{3}\ell^{-3}\big{(}\varphi(x^{k})-\varphi(\bar{x})\big{)}.$

This allows us to find $k_{0}\in{\rm I\\!N}$ such that

$\varphi(x^{k+1})-\varphi(\bar{x})\leq\mu\big{(}\varphi(x^{k})-\varphi(\bar{x})\big{)}\quad\text{whenever
}\;k\geq k_{0},$

which verifies (i) with $\mu:=1-2\sigma\gamma\kappa^{3}\ell^{-3}\in(0,1)$. It
readily follows from (4.32) that

$\sqrt{\frac{2}{\kappa}\big{(}\varphi(x^{k})-\varphi(\bar{x})\big{)}}\leq\sqrt{\frac{2\mu}{\kappa}\big{(}\varphi(x^{k-1})-\varphi(\bar{x})\big{)}}\leq\ldots\leq\sqrt{\frac{2\mu^{k-k_{0}}}{\kappa}\big{(}\varphi(x^{k_{0}})-\varphi(\bar{x})\big{)}}$

whenever $k\geq k_{0}$. Thus we get $\|x^{k}-\bar{x}\|\leq M\lambda^{k}$ for
such $k$, where

$M:=\sqrt{\frac{2}{\kappa}\mu^{-k_{0}}\big{(}\varphi(x^{k_{0}})-\varphi(\bar{x})\big{)}}\quad\text{and}\quad\lambda:=\sqrt{\mu}.$

Since $\lambda\in(0,1)$, it follows that
$\displaystyle\lim_{k\to\infty}\lambda^{k}=0$, which implies that the sequence
$\\{x^{k}\\}$ converges at least R-linearly to $\bar{x}$ as $k\to\infty$.
Employing again the Lipschitz continuity of $\nabla\varphi$ around $\bar{x}$
with constant $\ell>0$, we arrive at

$\|\nabla\varphi(x^{k})\|=\|\nabla\varphi(x^{k})-\nabla\varphi(\bar{x})\|\leq\ell\|x^{k}-\bar{x}\|\leq\ell
M\lambda^{k}\quad\text{for all }\;k\geq k_{0},$

which verifies assertion (ii) and thus completes the proof of the theorem.

To proceed further with deriving verifiable conditions ensuring the
Q-superlinear convergence of Algorithm 3.2, we need to recall some important
notions from variational analysis. A crucial role in the theory and
applications of nonsmooth Newton-type methods is played by a remarkable
subclass of single-valued locally Lipschitzian mappings defined as follows;
see the books [20, 33, 35] with the commentaries and references therein. A
mapping $f\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ is semismooth at $\bar{x}$ if
it is locally Lipschitzian around this point and the limit

$\lim_{A\in\text{\rm co}\overline{\nabla}f(\bar{x}+tu^{\prime})\atop
u^{\prime}\to u,t\downarrow 0}Au^{\prime}$ (4.37)

exists for all $u\in\mathbb{R}^{n}$, where ‘co’ stands for the convex hull of
a set, and where $\overline{\nabla}f$ is given by

$\overline{\nabla}f(x):=\big{\\{}A\in\mathbb{R}^{m\times n}\big{|}\;\exists\
x_{k}\overset{\Omega_{f}}{\to}x\;\text{ such that }\;\nabla f(x_{k})\to
A\big{\\}},\quad x\in\mathbb{R}^{n},$

with $\Omega_{f}:=\\{x\in\mathbb{R}^{n}\;|\;f\;\text{ is differentiable at
}\;x\\}$. Quite recently [26], the concept of semismoothness has been improved
and extended to set-valued mappings. To formulate the latter notion, recall
first the construction of the directional limiting normal cone to a set
$\Omega\subset\mathbb{R}^{s}$ at $\bar{z}\in\Omega$ in the direction
$d\in\mathbb{R}^{s}$ introduced in [27] by

$N_{\Omega}(\bar{z};d):=\big{\\{}v\in\mathbb{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{\\}}.$ (4.38)

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

$D^{*}F\big{(}(\bar{x},\bar{y});(u,v)\big{)}(v^{*}):=\big{\\{}u^{*}\in\mathbb{R}^{n}\;\big{|}\;(u^{*},-v^{*})\in
N_{\text{gph}\,F}\big{(}(\bar{x},\bar{y});(u,v)\big{)}\big{\\}},\;v^{*}\in\mathbb{R}^{m}.$
(4.39)

Using (4.39), we come to the aforementioned property of set-valued mappings
introduced in [26].

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

A mapping $F\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is
semismooth∗ at $(\bar{x},\bar{y})\in\mbox{\rm gph}\,F$ if whenever
$(u,v)\in\mathbb{R}^{n}\times\mathbb{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 [26] that the semismoothness∗ holds if the graph of
$F\colon\mathbb{R}^{n}\rightrightarrows\mathbb{R}^{m}$ is represented as a
union of finitely many closed and convex sets as well as for normal cone
mappings generated by convex polyhedral sets. Note also that the semismooth∗
property of single-valued locally Lipschitzian mappings
$f\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ around $\bar{x}$ agrees with the
semismooth property (4.37) at this point provided that $f$ directionally
differentiable at $\bar{x}$.

Prior to deriving a major theorem on the $Q$-superlinear convergence of
Algorithm 3.2, we present an important property of $\mathcal{C}^{1,1}$
functions with semismooth∗ derivatives.

######  Proposition 4.4 (directional estimate for functions with semismooth∗
derivatives).

Let $\varphi\colon\mathbb{R}^{n}\to\mathbb{R}$ be continuously differentiable
around $\bar{x}\in\mathbb{R}^{n}$ with $\nabla\varphi(\bar{x})=0$. Suppose
that $\nabla\varphi$ is locally Lipschitzian around this point with modulus
$\ell>0$, and that $\nabla\varphi$ is semismooth∗ at this point. Assume
further that a sequence $\\{x^{k}\\}$ converges to $\bar{x}$ with
$x^{k}\neq\bar{x}$ as $k\in{\rm I\\!N}$, and that a sequence $\\{d^{k}\\}$ is
superlinearly convergent with respect to $\\{x^{k}\\}$, i.e.,
$\|x^{k}+d^{k}-\bar{x}\|=o(\|x^{k}-\bar{x}\|)$. Consider the following
statements:

  * (i)

$\nabla\varphi$ is directionally differentiable at $\bar{x}$, and there exists
$\kappa>0$ such that
$\langle\nabla\varphi(x^{k}),d^{k}\rangle\leq-\frac{1}{\kappa}\|d^{k}\|^{2}$
for all sufficiently large $k\in{\rm I\\!N}$.

  * (ii)

There exists $\kappa>0$ such that

$\varphi(x^{k}+d^{k})-\varphi(x^{k})\leq\langle\nabla\varphi(x^{k}+d^{k}),d^{k}\rangle-\frac{1}{2\kappa}\|d^{k}\|^{2}$
(4.40)

for all sufficiently large $k\in{\rm I\\!N}$.

Then we have the estimate

$\varphi(x^{k}+d^{k})\leq\varphi(x^{k})+\sigma\langle\nabla\varphi(x^{k}),d^{k}\rangle\;\mbox{
for all large }\;k\in{\rm I\\!N}$ (4.41)

provided that either (i) holds and $\sigma\in(0,1/2)$, or (ii) holds and
$\sigma\in\left(0,1/(2\ell\kappa)\right)$

[Proof.] Suppose that (i) holds. The directional differentiability and
semismoothness∗ of $\nabla\varphi$ at $\bar{x}$ ensures by [26, Corollary 3.8]
that $\nabla\varphi$ is semismooth at $\bar{x}$. Using now [20, Proposition
8.3.18], we immediately get (4.41). Suppose next that (ii) is satisfied and
$\sigma\in\left(0,1/(2\ell\kappa)\right)$. Since $\\{d^{k}\\}$ is
superlinearly convergent with respect to $\\{x^{k}\\}$, by employing [20,
Lemma 7.5.7] we have

$\lim_{k\to\infty}\|x^{k}-\bar{x}\|/\|d^{k}\|=1,$ (4.42)

which ensures in turn that

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

Then the statement in (ii) leads us to the inequalities

$\displaystyle\varphi(x^{k}+d^{k})-\varphi(x^{k})-\sigma\langle\nabla\varphi(x^{k}),d^{k}\rangle$
$\displaystyle\leq$
$\displaystyle\langle\nabla\varphi(x^{k}+d^{k}),d^{k}\rangle-\frac{1}{2\kappa}\|d^{k}\|^{2}-\sigma\langle\nabla\varphi(x^{k}),d^{k}\rangle$
$\displaystyle\leq$
$\displaystyle\|\nabla\varphi(x^{k}+d^{k})\|\cdot\|d^{k}\|-\frac{1}{2\kappa}\|d^{k}\|^{2}+\sigma\|\nabla\varphi(x^{k})\|\cdot\|d^{k}\|$
$\displaystyle\leq$
$\displaystyle\ell\|x^{k}+d^{k}-\bar{x}\|\cdot\|d^{k}\|-\frac{1}{2\kappa}\|d^{k}\|^{2}+\sigma\ell\|x^{k}-\bar{x}\|\cdot\|d^{k}\|$
$\displaystyle\leq$
$\displaystyle\|d^{k}\|^{2}\left(\ell\frac{\|x^{k}+d^{k}-\bar{x}\|}{\|d^{k}\|}-\frac{1}{2\kappa}+\sigma\ell\frac{\|x^{k}-\bar{x}\|}{\|d^{k}\|}\right)$

for all large $k\in{\rm I\\!N}$. Finally, it follows from the inequality
$\sigma<1/(2\ell\kappa)$, (4.42), and (4.43) that

$\varphi(x^{k}+d^{k})-\varphi(x^{k})-\sigma\langle\nabla\varphi(x^{k}),d^{k}\rangle\leq
0\quad\text{whenever }\;k\in{\rm I\\!N}\;\text{ is sufficiently large},$

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

Now we are ready to derive the main result of this section that establishes
the Q-superlinear convergence of Algorithm 3.2 under the imposed assumptions.

######  Theorem 4.5 (superlinear convergence of the generalized damped Newton
algorithm for ${\cal C}^{1,1}$ functions).

In the setting of Theorem 3.4, suppose that $\\{x^{k}\\}$ converges $\bar{x}$
as $k\to\infty$ with $x^{k}\neq\bar{x}$ for all $k\in{\rm I\\!N}$, and that
$\nabla\varphi$ is locally Lipschitzian around $\bar{x}$ with some constant
$\ell>0$ being also semismooth∗ at this point. Then the convergence rate of
$\\{x^{k}\\}$ is at least Q-superlinear if either one of the following two
conditions holds:

  * (i)

$\nabla\varphi$ is directionally differentiable at $\bar{x}$.

  * (ii)

$\sigma\in\left(0,1/(2\ell\kappa)\right)$, where $\kappa>0$ is a modulus of
tilt stability of $\varphi$ at $\bar{x}$.

Furthermore, in both cases (i) and (ii) the sequence $\\{\varphi(x^{k})\\}$
converges Q-superlinearly to $\varphi(\bar{x})$, and the sequence
$\\{\nabla\varphi(x^{k})\\}$ converges Q-superlinearly to $0$ as $k\to\infty$.

[Proof.] Suppose that the sequence $\\{x^{k}\\}$ converges as $k\to\infty$ to
a point $\bar{x}\in\mathbb{R}^{n}$. We split the proof of the theorem into the
following three claims.
Claim 1: The sequence $\\{d^{k}\\}$ is superlinearly convergent with respect
to $\\{x^{k}\\}$. Indeed, it follows from Theorem 3.4 that $\bar{x}$ is tilt-
stable local minimizer of $\varphi$ with some modulus $\kappa>0$. By using the
characterization of tilt-stable minimizers via the combined second-order
subdifferential taken from [46, Theorem 3.5] and [10, Proposition 4.6], we
find a positive number $\delta$ such that

$\langle z,w\rangle\geq\frac{1}{\kappa}\|w\|^{2}\quad\text{for all
}\;z\in\partial^{2}\varphi(x)(w),\;x\in\mathbb{B}_{\delta}(\bar{x}),\;\mbox{
and }\;w\in\mathbb{R}^{n}.$ (4.44)

Using the subadditivity property of coderivatives obtained in [34, Lemma 5.6],
we have

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

Since $-\nabla\varphi(x^{k})\in\partial^{2}\varphi(x^{k})(d^{k})$, for all
$k\in{\rm I\\!N}$ there exists
$v^{k}\in\partial^{2}\varphi(x^{k})(-x^{k}+\bar{x})$ such that

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

Employing (4.44) and the Cauchy-Schwarz inequality, we have

$\|x^{k}+d^{k}-\bar{x}\|\leq\kappa\|\nabla\varphi(x^{k})+v^{k}\|\quad\text{for
sufficiently large }\;k\in{\rm I\\!N}.$ (4.45)

By the semismoothness∗ of $\nabla\varphi$ at $\bar{x}$ together with
$\nabla\varphi(\bar{x})=0$ and [34, Lemma 5.5], we have

$\|\nabla\varphi(x^{k})+v^{k}\|=\|\nabla\varphi(x^{k})-\nabla\varphi(\bar{x})+v^{k}\|=o(\|x^{k}-\bar{x}\|).$
(4.46)

Combining (4.45) and (4.46) tells us that
$\|x^{k}+d^{k}-\bar{x}\|=o(\|x^{k}-\bar{x}\|)$ as $k\to\infty$, which thus
completes the proof of this claim.
Claim 2: We have $\tau_{k}=1$ for all $k\in{\rm I\\!N}$ sufficiently large
provided that either condition (i) or (ii) of this theorem holds. To proceed,
we need to show that for all $k\in{\rm I\\!N}$ sufficiently large, we get the
inequality (4.41). Assume first that (i) holds. Due to the inclusion
$-\nabla\varphi(x^{k})\in\partial^{2}\varphi(x^{k})(d^{k})$ for all $k\in{\rm
I\\!N}$ and the estimate (4.44), we have
$\langle\nabla\varphi(x^{k}),d^{k}\rangle\leq-\frac{1}{\kappa}\|d^{k}\|^{2}$
whenever $k\in{\rm I\\!N}$ is sufficiently large. Then by Proposition 4.4 we
get (4.41), which readily verifies the claimed assertion in case (i). Assuming
now the conditions in (ii) and using Claim 1, we easily get that the sequence
$\\{d^{k}\\}$ converges to $0$ as $k\to\infty$, and that
$x^{k}+d^{k}\to\bar{x}$ as $k\to\infty$. Employing the uniform second-order
growth condition for tilt-stable minimizers from [46, Theorem 3.2] gives us a
neighborhood $U$ of $\bar{x}$ such that

$\varphi(x)\geq\varphi(u)+\langle\nabla\varphi(u),x-u\rangle+\frac{1}{2\kappa}\|x-u\|^{2}\quad\text{for
all }\;x,u\in U,$

which implies the inequality (4.40). Then by Proposition 4.4 we get (4.41),
and hence complete verifying the the claimed assertion in this case.
Claim 3: The conclusions of the theorem about the Q-superlinear convergence of
the sequences $\\{x^{k}\\}$, $\\{\varphi(x^{k})\\}$, and
$\\{\nabla\varphi(x^{k})\\}$ hold provided that either condition (i) or (ii)
of this theorem holds. To justify this assertion, we get from Claim 2 that
$\tau_{k}=1$ for all sufficiently large $k\in{\rm I\\!N}$, and thus Algorithm
3.2 eventually becomes Algorithm 3.1. Hence the claimed convergence results
follow from [34, Theorems 5.7 and 5.12]. This verifies the assertions of Claim
3 and completes the proof of the theorem.

##  5  GDNM for Problems of Quadratic Composite Optimization

In this section we study a special class of constrained optimization problem
given in the form

$\displaystyle\text{minimize }\;\varphi(x):=f(x)+g(x),\quad
x\in\mathbb{R}^{n},$ (5.47)

where $f\colon\mathbb{R}^{n}\to\mathbb{R}$ is a convex and smooth function,
while $g\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ is a convex and
extended-real-valued one. This class is known as problems of convex composite
optimization. Observe that, although (5.47) is written in the unconstrained
format, it includes constrained optimization problems with the effective
constraints $x\in\mbox{\rm dom}\,g$.

In what follows we pay the main attention to a subclass of (5.47) described by

$\displaystyle\text{minimize }\;\varphi(x):=\frac{1}{2}\langle
Ax,x\rangle+\langle b,x\rangle+\alpha+g(x),\quad x\in\mathbb{R}^{n},$ (5.48)

where $A\in\mathbb{R}^{n\times n}$ is a positive-semidefinite matrix,
$b\in\mathbb{R}^{n}$, and $\alpha\in\mathbb{R}$. That is, (5.48) is a subclass
of (5.47) with $f$ being a quadratic function. This allows us to label (5.48)
as problems of quadratic composite optimization.

Note that problems of type (5.48) frequently appear, e.g., in practical models
of machine learning and statistics. In particular, various Lasso problems
considered in Section 6 can be written in form (5.48). Here are some other
important classes of problems arising in practical modeling, which are reduced
to (5.48).

######  Example 5.1 (support vector machine problems).

Given the training data $(x_{i},y_{i})$, $i=1,\ldots,m$, where
$x_{i}\in\mathbb{R}^{n}$ are the observations and $y_{i}\in\\{-1,1\\}$ are the
labels, the support vector classification is a problem of finding a hyperplane
$y=\langle w,x\rangle+b$ such that the data with different labels can be
separated by the hyperplane. One of the most popular support vector machine
models [32] is the regularized penalty model

$\displaystyle\text{minimize
}\;\varphi(w,b):=\frac{1}{2}\|w\|^{2}+C\sum_{i=1}^{m}\xi(w,x_{i},y_{i},b)\;\mbox{
with }\;w\in\mathbb{R}^{n}\;\mbox{ and }\;b\in\mathbb{R},$ (5.49)

where $C>0$ is a penalty parameter, and where
$\xi\colon\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}\times\mathbb{R}\to\mathbb{R}$
is called a loss function. Typical loss functions are given as follows:

  * (i)

L1-loss, or $\ell_{1}$ hinge loss:
$\xi(w,x_{i},y_{i},b)=\max\\{1-y_{i}(\langle w,x_{i}\rangle+b),0\\}$.

  * (ii)

L2-loss, or squared hinge loss: $\xi(w,x_{i},y_{i},b)=\max\\{1-y_{i}(\langle
w,x_{i}\rangle+b),0\\}^{2}$.

  * (iii)

Logistic loss: $\xi(w,x_{i},y_{i},b)=\log(1+e^{-y_{i}(\langle
w,x_{i}\rangle+b)})$.

######  Example 5.2 (convex clustering problems).

Let $A:=[a_{1},\ldots,a_{n}]\in\mathbb{R}^{d\times n}$ be a given matrix with
$n$ observations and $d$ features. The convex clustering model [55] is
described in the form of quadratic composite optimization (5.48) by:

$\displaystyle\text{minimize
}\;\frac{1}{2}\sum_{i=1}^{n}\|x_{i}-a_{i}\|^{2}+\gamma\sum_{i<j}\|x_{i}-x_{j}\|_{p},\quad
X\in\mathbb{R}^{d\times n},$ (5.50)

where $\gamma>0$ is a tuning parameter, and where $\|\cdot\|_{p}$ denotes the
$p$-norm. Typically the norm parameter $p$ is chosen as $1,2,\infty$.

######  Example 5.3 (constrained quadratic optimization).

Consider problem (5.48), where $g$ is the indicator function of a nonempty,
closed, and convex set $\Omega$. Then (5.48) is known as a constrained
quadratic optimization problem. Some of the typical constraints are given by:

  * (i)

Box constrained set:
$\Omega=\text{Box}[l,u]:=\big{\\{}x\in\mathbb{R}^{n}\;\big{|}\;l\leq x_{i}\leq
u,\;i=1,\ldots,n\big{\\}}$.

  * (ii)

Half-space: $\Omega=\big{\\{}x\in\mathbb{R}^{n}\;\big{|}\;\langle
a,x\rangle\leq\alpha\big{\\}}$, where $a\in\mathbb{R}^{n}\setminus\\{0\\}$ and
$\alpha\in\mathbb{R}$.

  * (iii)

Affine set: $\Omega=\big{\\{}x\in\mathbb{R}^{n}\;\big{|}\;Ax=b\big{\\}}$,
where $A$ is an $m\times n$ matrix and $b\in\mathbb{R}^{m}$.

######  Remark 5.4 (subproblems for other methods).

Quadratic composite optimization problems of type (5.48) not only cover
optimization models in machine learning, statistics, and other applied areas,
but also arise as subproblems for some efficient algorithms including
sequential quadratic programming methods (SQP) [6, 33], augmented Lagrangian
methods [28, 31, 37, 58, 60, 61], proximal Newton methods [36, 50], etc.

To develop now a globally convergent damped Newton method for solving
quadratic composite optimization problems of type (5.48), we employ the basic
machinery of variational analysis, which allows us to reduce (5.48) to
unconstrained problems with ${\cal C}^{1,1}$ objectives. Following [62],
recall the corresponding notions used in our subsequent developments.

######  Definition 5.5 (Moreau envelopes and proximal mappings).

Given an extended-real-valued, proper, l.s.c. function
$\varphi\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ and given a parameter
value $\gamma>0$, the Moreau envelope $e_{\gamma}\varphi$ and the proximal
mapping $\textit{\rm Prox}_{\gamma\varphi}$ are defined by

$e_{\gamma}\varphi(x):=\inf\left\\{\varphi(y)+\frac{1}{2\gamma}\|y-x\|^{2}\;\Big{|}\;y\in\mathbb{R}^{n}\right\\},$
(5.51) $\textit{\rm Prox}_{\gamma\varphi}(x):={\rm
argmin}\left\\{\varphi(y)+\frac{1}{2\gamma}\|y-x\|^{2}\;\Big{|}\;y\in\mathbb{R}^{n}\right\\}.$
(5.52)

If $\gamma=1$, we use the notation $e\varphi(x)$ and $\text{\rm
Prox}_{\varphi}(x)$ in (5.51) and (5.52), respectively.

Both Moreau envelopes and proximal mappings have been well recognized in
variational analysis and optimization as efficient tools of regularization and
approximation of nonsmooth functions. Prior to establishing the main
convergence results of this section, we present several lemmas of their own
interest. The first one, taken from [1, Proposition 12.30], lists those
properties of Moreau envelopes and proximal mappings for convex extended-real-
valued functions that are needed to derive the main results obtained below.

######  Lemma 5.6 (Moreau envelopes and proximal mappings for convex
functions).

Let $\varphi\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ be a proper, l.s.c.,
convex function. Then the following assertions hold for all $\gamma>0$:

  * (i)

The Moreau envelope $e_{\gamma}\varphi$ is of class of continuously
differentiable functions, and its gradient is Lipschitz continuous with
modulus $1/\gamma$ on $\mathbb{R}^{n}$.

  * (ii)

The proximal mapping $\text{\rm Prox}_{\gamma\varphi}$ is single-valued,
monotone, and nonexpansive, i.e., it is Lipschitz continuous with modulus $1$
on $\mathbb{R}^{n}$.

  * (iii)

The gradient of $e_{\gamma}\varphi$ is calculated by

$\nabla e_{\gamma}\varphi(x)=\frac{1}{\gamma}\Big{(}x-\text{\rm
Prox}_{\gamma\varphi}(x)\Big{)}=\big{(}\gamma
I+(\partial\varphi)^{-1}\big{)}^{-1}(x)\;\mbox{ for all
}\;x\in\mathbb{R}^{n}.$ (5.53)

The results of Lemma 5.6 allow us to pass from nonsmooth convex optimization
problems of type (5.48) with extended-valued objectives (i.e., including
constraints) to an unconstrained ${\cal C}^{1,1}$ problem given in form (1.1).
Note that such an approach has been used in [34, 49] to design locally
convergent pure Newton algorithms for optimization problems and subgradient
inclusions associated with prox-regular functions [62]. However, now we go
further from the numerical viewpoint. Exploiting the quadratic composite
structure of problems (5.48) and their specifications leads us to the design
and justification of a new globally convergent algorithm with constructive
calculations of its parameters via the problem data.

To proceed, let $\gamma>0$ be such that the matrix $I-\gamma A$ is positive-
definite. Denoting $Q:=(I-\gamma A)^{-1}$, $c:=\gamma Qb$, and $P:=Q-I$,
define the unconstrained optimization problem by

minimize $\displaystyle\psi(u):=\frac{1}{2}\langle Pu,u\rangle+\langle
c,u\rangle+\gamma e_{\gamma}g(u)\;\mbox{ subject to }\;u\in\mathbb{R}^{n}.$
(5.54)

The following lemma reveals some important properties of the optimization
problem (5.54).

######  Lemma 5.7 (quadratic composite problems via proximal mappings).

Let $\psi$ be given in (5.54). Then $\psi$ is a continuously differentiable
function represented by

$\psi(u):=\frac{1}{2}\langle Pu,u\rangle+\langle c,u\rangle+\gamma
g\big{(}\text{\rm Prox}_{\gamma g}(u)\big{)}+\frac{1}{2}\|u-\text{\rm
Prox}_{\gamma g}(u)\|^{2}.$ (5.55)

Moreover, the mapping $\nabla\psi$ is Lipschitz continuous on $\mathbb{R}^{n}$
with modulus $\ell:=1+\|Q\|$, and

$\nabla\psi(u)=Qu-\text{\rm Prox}_{\gamma g}(u)+c.$ (5.56)

If in addition $A$ is positive-definite, then $\psi$ is strongly convex with
modulus $\lambda_{\text{\rm min}}(P)>0$.

[Proof.] Due to the convexity of $g$ and Lemma 5.6, the Moreau envelope
$e_{\gamma}g$ is continuously differentiable and the proximal mapping
$\text{\rm Prox}_{\gamma g}$ is nonexpansive on $\mathbb{R}^{n}$. Thus the
function $\psi$ is continuously differentiable as well. The representations in
(5.55) and (5.56) follow from the definition of $\psi$ and formula (5.53).
Furthermore, for any $u_{1},u_{2}\in\mathbb{R}^{n}$ we have

$\|\nabla\psi(u_{1})-\nabla\psi(u_{2})\|=\|Qu_{1}-Qu_{2}-\text{\rm
Prox}_{\gamma g}(u_{1})+\text{\rm Prox}_{\gamma
g}(u_{2})\|\leq(1+\|Q\|)\|u_{1}-u_{2}\|=\ell\|u_{1}-u_{2}\|,$

which justifies the global Lipschitz continuity of $\psi$ on $\mathbb{R}^{n}$
with the uniform constant $\ell$ defined above. Suppose further that $A$ is
positive-definite. Combining this with the positive-definiteness of
$I-~{}\gamma A$ readily yields the positive-definiteness of $P$. Thus $\psi$
in (5.54) is strongly convex on $\mathbb{R}^{n}$ with modulus
$\lambda_{\text{\rm min}}(P)>~{}0$.

Next we establishes the relationship between the optimization problems (5.48)
and (5.54).

######  Lemma 5.8 (reduction of quadratic composite problems to ${\cal
C}^{1,1}$ optimization).

Consider the optimization problems (5.48) and (5.54). The following are
equivalent:

  * (i)

The vector $\bar{x}$ is an optimal solution to (5.48).

  * (ii)

The vector $\bar{x}=Q\bar{u}+c$, where $\bar{u}$ is an optimal solution to
(5.54).

[Proof.] Using [1, Theorem 26.2] and the expression $\nabla f(x):=Ax+b$ for
all $x\in\mathbb{R}^{n}$ tells us that the optimal solution to (5.48) is fully
characterized by the equation

$x-\text{\rm Prox}_{\gamma g}\big{(}x-\gamma(Ax+b)\big{)}=0.$ (5.57)

For each $x\in\mathbb{R}^{n}$ denote $u:=x-\gamma(Ax+b)=(I-\gamma A)x-\gamma
b$ and observe by the positive-definiteness of the matrix $I-\gamma A$ that
(5.57) is equivalent to

$\begin{cases}Qu-\text{\rm Prox}_{\gamma g}(u)+c=0,\\\ x=Qu+c,\end{cases}$
(5.58)

where $Q:=(I-\gamma A)^{-1}$ and $c:=\gamma Qb$. The positive-definiteness of
$I-\gamma A$ and the positive-semidefiniteness of $A$ imply that $P=Q-I$ is
positive-semidefinite. Furthermore, the convexity of $g$ and Lemma 5.7 ensure
that $e_{\gamma}g$ is continuously differentiable on $\mathbb{R}^{n}$, and
that $\bar{u}$ is a solution to (5.54) if and only if we have

$0=\nabla\psi(\bar{u})=P\bar{u}+c+\gamma\nabla
e_{\gamma}g(\bar{u})=Q\bar{u}-\text{\rm Prox}_{\gamma g}(\bar{u})+c.$

This verifies the equivalence between (i) and (ii) as stated in the lemma.

The last lemma of this section provides the representation of the second-order
subdifferential of the cost function $\psi$ in the reduced problem (5.54) via
the second-order subdifferential of the given regularizer $g$ in the original
one (5.48).

######  Lemma 5.9 (second-order subdifferentials of reduced cost functions).

Let $\psi\colon\mathbb{R}^{n}\to\mathbb{R}$ be taken from (5.54). Then for
each $u\in\mathbb{R}^{n}$ and $w\in\mathbb{R}^{n}$ we have the relationship

$z\in\partial^{2}\psi(u)(w)\iff\frac{1}{\gamma}(z-Pw)\in\partial^{2}g\Big{(}\text{\rm
Prox}_{\gamma g}(u),\frac{1}{\gamma}\big{(}u-\text{\rm Prox}_{\gamma
g}(u)\big{)}\Big{)}\big{(}Qw-z\big{)}.$

[Proof.] Using the second-order subdifferential sum rule from [44, Proposition
1.121] gives us

$\partial^{2}\psi(u)(w)=Pw+\gamma\partial^{2}e_{\gamma}g\Big{(}u,\frac{1}{\gamma}\big{(}\nabla\psi(u)-Pu-c\big{)}\Big{)}(w).$

This we have that $z\in\partial^{2}\psi(u)(w)$ if and only if

$\frac{1}{\gamma}(z-Pw)\in\partial^{2}e_{\gamma}g\Big{(}u,\frac{1}{\gamma}\big{(}\nabla\psi(u)-Pu-c\big{)}\Big{)}(w).$

Due to [34, Lemma 6.4], the latter is equivalent to

$\frac{1}{\gamma}(z-Pw)\in\partial^{2}g\Big{(}u-\nabla\psi(u)+Pu+c,\frac{1}{\gamma}\big{(}\nabla\psi(u)-Pu-c\big{)}\Big{)}(w-z+Pw).$
(5.59)

Furthermore, we have the equalities

${u-\nabla\psi(u)+Pu+c=u-\gamma\nabla e_{\gamma}g(u)=\text{\rm Prox}_{\gamma
g}(u),}$ (5.60)
$\frac{1}{\gamma}(\nabla\psi(u)-Pu-c)=\frac{1}{\gamma}\big{(}u-\text{\rm
Prox}_{\gamma g}(u)\big{)}.$ (5.61)

Combining (5.59) with (5.60) and (5.61) completes the proof of the lemma.

Now we are in a position to design the aforementioned generalized damped
Newton-type algorithm to solve problems (5.48) of quadratic composite
optimization.

######  Algorithm 5.10 (generalized damped Newton algorithm for problems of
quadratic composite optimization).

Input: $A\in\mathbb{R}^{n\times n}$, $b\in\mathbb{R}^{n}$, $g$,
$\sigma\in\left(0,\frac{1}{2}\right)$, and $\beta\in(0,1)$. Do the following:
Step 0: Choose $\gamma>0$ such that $I-\gamma A$ is positive-definite,
calculate $Q:=(I-\gamma A)^{-1}$, $c:=\gamma Qb$, $P:=Q-I$, define the
function $\psi$ as in (5.55), choose a starting point
$u^{0}\in\mathbb{R}^{n}$, and set $k:=0$.
Step 1: If $\nabla\psi(u^{k})=0$, then stop. Otherwise, set $v^{k}:=\text{\rm
Prox}_{\gamma}g(u^{k})$.
Step 2: Find $d^{k}\in\mathbb{R}^{n}$ such that

$\frac{1}{\gamma}\big{(}-\nabla\psi(u^{k})-Pd^{k}\big{)}\in\partial^{2}g\Big{(}v^{k},\frac{1}{\gamma}(u^{k}-v^{k})\Big{)}\big{(}Qd^{k}+\nabla\psi(u^{k})\big{)}.$
(5.62)

Step 3: Set $\tau_{k}=1$. Until  Armijo’s inequality

$\psi(u^{k}+\tau_{k}d^{k})\leq\psi(u^{k})+\sigma\tau_{k}\langle\nabla\psi(u^{k}),d^{k}\rangle$

is satisfied, set $\tau_{k}:=\beta\tau_{k}$.
Step 4: Compute $u^{k+1}$ by

$u^{k+1}:=u^{k}+\tau_{k}d^{k},\quad k=0,1,\ldots.$

Step 5: Increase $k$ by $1$ and go to Step 1.
Output: $x^{k}:=Qu^{k}+c$.

Note that the definitions of the second-order subdifferential (2.10) and the
limiting coderivative (2.7) allow us to rewrite the implicit inclusion (5.62)
for $d^{k}$ in the explicit form

$\Big{(}\frac{1}{\gamma}\big{(}-\nabla\psi(u^{k})-Pd^{k}\big{)},-Qd^{k}-\nabla\psi(x^{k})\Big{)}\in
N_{\text{gph}\,\partial g}\Big{(}v^{k},\frac{1}{\gamma}(u^{k}-v^{k})\Big{)}.$
(5.63)

Explicit expressions for the sequences $\\{v^{k}\\}$ and $\\{d^{k}\\}$ in
Algorithm 5.10 depend on given structures of the regularizers $g$, which are
efficiently specified in applied models of machine learning and statistics;
see, e.g., the above discussions and those presented in Section 6.

######  Remark 5.11 (stopping criterion).

Note that $\bar{x}$ is a solution to (5.48) if and only if this point
satisfies the stationary equation (5.57). In order to approximate the solution
$\bar{x}$, we choose the termination/stopping criterion

$\big{\|}x-\text{\rm Prox}_{\gamma
g}\big{(}x-\gamma(Ax+b)\big{)}\big{\|}\leq\varepsilon$ (5.64)

with a given tolerance parameter $\varepsilon>0$. The stopping criterion
(5.64) is clearly equivalent to the condition
$\|\nabla\psi(u)\|\leq\varepsilon$, where $u:=x-\gamma(Ax+b)=Q^{-1}(x-c)$, and
where $\psi$ is defined in (5.55). Therefore, in practice the stopping
criterion of Step 2 of Algorithm 5.10 can be replaced by the simpler one
$\|\nabla\psi(u^{k})\|\leq~{}\varepsilon$.

To proceed with establishing conditions for global convergence of Algorithm
5.10, we need to employ yet another notion of generalized second-order
differentiability taken from [62, Chapter 13]. First recall that a mapping
$h\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ is semidifferentiable at $\bar{x}$ if
there exists a continuous and positively homogeneous operator
$H\colon\mathbb{R}^{n}\to\mathbb{R}^{m}$ such that

$h(x)=h(\bar{x})+H\big{(}x-\bar{x}\big{)}+o(\|x-\bar{x}\|)\quad\text{for all
}\;x\;\text{ near }\;\bar{x}.$

Given $\varphi\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ with
$\bar{x}\in\mbox{\rm dom}\,\varphi$, consider the family of second-order
finite differences

$\Delta^{2}_{\tau}\varphi(\bar{x},v)(u):=\frac{\varphi(\bar{x}+\tau
u)-\varphi(\bar{x})-\tau\langle v,u\rangle}{\frac{1}{2}\tau^{2}}$

and define the second subderivative of $\varphi$ at $\bar{x}$ for
$v\in\mathbb{R}^{n}$ and $w\in\mathbb{R}^{n}$ by

$d^{2}\varphi(\bar{x},v)(w):=\liminf_{\tau\downarrow 0\atop u\to
w}\Delta^{2}_{\tau}\varphi(\bar{x},v)(u).$

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

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

Twice epi-differentiability has been recognized as an important property in
second-order variational analysis with numerous applications to optimization;
see the aforementioned monograph by Rockafellar and Wets and the recent papers
[40, 41, 42] developing a systematic approach to verify epi-differentiability
via parabolic regularity, which is a major second-order property of sets and
extended-real-valued functions.

The next theorem provides verifiable conditions on the matrix $A$ and the
function $g$ to run the GDNM Algorithm 5.10 for solving quadratic composite
optimization problems (5.48).

######  Theorem 5.12 (convergence rate of GDNM for problems of quadratic
composite optimization).

Considering the optimization problem (5.48), suppose that $A$ is positive-
definite. Then the following assertions hold:

  * (i)

Algorithm 5.10 is well-defined, and the sequence of its iterates $\\{u^{k}\\}$
globally R-linearly converges to some $\bar{u}$ as $k\to\infty$.

  * (ii)

The vector $\bar{x}:=Q\bar{u}+c$ is a tilt-stable local minimizer of the cost
function $\varphi$ in (5.48), and $\bar{x}$ is the unique solution to (5.48).

Furthermore, the rate of convergence of $\\{u^{k}\\}$ is at least
Q-superlinear if the mapping $\partial g$ is semismooth∗ at
$(\bar{x},\bar{v})$ with $\bar{v}:=-A\bar{x}-b$, and if one of two following
conditions fulfills:

  * (a)

$\sigma\in\left(0,1/(2\ell\kappa)\right)$, where $\ell:=1+\|Q\|$ and
$\kappa:=1/\lambda_{\text{\rm min}}(P)$.

  * (b)

$g$ is twice epi-differentiable at $\bar{x}$ for $\bar{v}$.

[Proof.] Lemma 5.7 and Lemma 5.9 tell us that applying Algorithm 5.10 to solve
the quadratic composite optimization problem (5.48) is equivalent to applying
Algorithm 3.2 to solving the ${\cal C}^{1,1}$ optimization problem (5.54). We
split the proof of the theorem into the following claims:
Claim 1: The function $\psi$ from (5.54) satisfies Assumptions 1 and 2.
Indeed, Lemma 5.7 ensures that $\psi$ is strongly convex with modulus
$\lambda_{\text{\rm min}}(P)>0$, and thus Assumption 1 holds due to [9,
Theorem 5.1]. Moreover, the strong convexity of $\psi$ clearly implies that
for an arbitrary vector $u^{0}\in\mathbb{R}^{n}$ the level set

$\Omega:=\big{\\{}u\in\mathbb{R}^{n}\;\big{|}\;\psi(u)\leq\psi(u^{0})\big{\\}}$

is bounded, and so Assumption 2 holds for the function $\psi$.
Claim 2: Both statements (i) and (ii) of the theorem are satisfied. To
proceed, we employ Claim 1 together with Theorems 3.7 and 4.2 to conclude that
Algorithm 5.10 is well-defined, and that the sequence of its iterates
$\\{u^{k}\\}$ globally R-linearly converges to some $\bar{u}$ as $k\to\infty$.
Then Lemma 5.8 tells us that the vector $\bar{x}=Q\bar{u}+c$ is a solution to
(5.48). The uniqueness and tilt stability of $\bar{x}$ follow immediately from
the strong convexity of $\varphi$.
Claim 3: The convergence rate of the sequence $\\{u^{k}\\}$ is at least
Q-superlinear provided that $\partial g$ is semismooth∗ at all the points on
its graph and that either one of the two conditions (a) and (b) is satisfied.
Indeed, suppose that $\partial g$ is semismooth∗ at $(\bar{x},\bar{v})$. Then
we deduce from [21, Proposition 6] that $\text{\rm Prox}_{\gamma g}$ is
semismooth∗ at $\bar{x}-\gamma(A\bar{x}+b)$. Thus we obtain that the mapping
$\nabla\psi(u)=Qu-\text{\rm Prox}_{\gamma g}(u)+c$ is semismooth∗ at $\bar{u}$
by employing [26, Proposition 3.6].

Assume now that condition (a) is satisfied. Then Lemma 5.7 tells us that
$\ell$ is a Lipschitz constant of $\nabla\psi$ around $\bar{u}$, and that
$\bar{u}$ is a tilt-stable local minimizer of $\psi$ with modulus $\kappa$.
Thus the claimed assertion follows in case (a) directly from Theorem 4.5.

Assuming by (b) that $g$ is twice epi-differentiable at $\bar{x}$ for
$\bar{v}$, we deduce from [62, Theorem 13.40] that the subgradient mapping
$\partial g$ is proto-differentiable of at $(\bar{x},\bar{v})$. Using [21,
Corollary 8], we conclude that $\text{\rm Prox}_{\gamma g}$ is directionally
differentiable at $\bar{x}-\gamma(A\bar{x}+b)$, which yields in turn the
directional differentiability of $\nabla\psi$ at $\bar{u}$. Finally, Theorem
4.5 allows us to conclude that the sequence $\\{u^{k}\\}$ Q-superlinearly
converges to $\bar{u}$ as $k\to\infty$.

It is highly desired to obtain a counterpart of Theorem 5.12 on global
convergence of Algorithm 5.10 under merely positive-semidefiniteness of the
matrix $A$. However, we cannot do it at this stage of developments since the
function $\psi$ from (5.54) may not satisfy Assumption 1. A natural idea to
overcome such a challenge is to regularize the original problem via
approximating it by a sequence of well-behaved problems. Perhaps the simplest
way to realize this idea is to employ the classical Tikhonov regularization.
To this end, consider in the setting of Lemma 5.8 the following family of
optimization problem depending on the parameter $\varepsilon>0$:

minimize $\displaystyle\psi_{\varepsilon}(u):=\frac{1}{2}\langle
P_{\varepsilon}u,u\rangle+\langle c,u\rangle+\gamma e_{\gamma}g(u)\;\mbox{
subject to }\;u\in\mathbb{R}^{n},$ (5.65)

where $P_{\varepsilon}:=P+\varepsilon I$. The next proposition discusses the
relationship between (5.65) and (5.48).

######  Proposition 5.13 (Tikhonov regularization).

Assume that (5.48) has a solution, and for each $\varepsilon>0$ consider the
optimization problem (5.65). If $\bar{u}(\varepsilon)$ is a solution to
(5.65), then we have the following assertions:

  * (i)

The limit $\displaystyle\bar{u}:=\lim_{\varepsilon\to 0}\bar{u}(\varepsilon)$
exists being a solution to (5.54).

  * (ii)

The vector $\bar{x}:=Q\bar{u}+c$ is a solution to (5.48).

[Proof.] Observe that the optimization problem (5.54) is equivalent to the
variational inequality problem VI($\mathbb{R}^{n},F$) written as: find a
vector $u\in\mathbb{R}^{n}$ such that

${\langle F(u),z-u\rangle\geq 0\;\mbox{ for all }\;z\in\mathbb{R}^{n},}$

where $F:=\nabla\psi$. Since $\bar{u}(\varepsilon)$ is a solution to (5.65),
we get that the family of approximate solutions
$\\{\bar{u}(\varepsilon)\;|\;\varepsilon>0\\}$ is the Tikhonov trajectory of
VI($\mathbb{R}^{n},F$); see, e.g., [20, Equation (12.2.2)]. It follows from
the convexity of $\psi$ that $\nabla\psi\colon\mathbb{R}^{n}\to\mathbb{R}^{n}$
is a monotone operator. Since the optimization problem (5.48) has a solution,
the set of solutions for VI($\mathbb{R}^{n},F$) is nonempty by Lemma 5.8.
Using [20, Theorem 12.2.3], we have that the limit
$\displaystyle\bar{u}=\lim_{\varepsilon\to 0}u(\varepsilon)$ exists and solves
(5.54). Finally, assertion (ii) follows immediately from Lemma 5.8.

######  Remark 5.14 (generalized Newton algorithm based on Tikhonov
regularization).

Proposition 5.13 provides a precise relationship between solutions to (5.48)
and solutions to (5.65). This plays a crucial role in solving (5.48) without
assuming the positive-definiteness of $A$. Moreover, Proposition 5.13
motivates us to develop a generalized Newton-type algorithm based on the
Tikhonov regularization to solve the class of optimization problems (5.48),
where $A$ is merely positive-semidefinite. We will pursue this issue in our
future research.

##  6  Solving Lasso Problems and Numerical Experiments

This section is devoted to specifying our generalized damped Newton method
(GDNM) developed in Section 5 for the basic class of Lasso problems, where
Lasso stands for the Least Absolute Shrinkage and Selection Operator. Using on
the obtained specification of GDNM to solve Lasso problems, we conduct
numerical experiments by using our algorithm and the compare the computations
with the performances of some major first-order and second-order algorithms
applied to solving this class of problems of composite quadratic optimization.

The basic Lasso problem, known also as the $\ell^{1}$-regularized least square
optimization problem, was introduced by Tibshirani [64] and then has been
largely investigated and applied to various issues in statistics, machine
learning, image processing, etc. This problem is formulated as:

$\displaystyle\text{minimize
}\;\varphi(x):=\frac{1}{2}\|Ax-b\|_{2}^{2}+\mu\|x\|_{1}\quad\text{ subject to
}\;x\in\mathbb{R}^{n},$ (6.66)

where $A$ is an $m\times n$ matrix, $\mu>0$, $b\in\mathbb{R}^{m}$, and where

$\|x\|_{1}:=\sum_{i=1}^{n}|x_{i}|,\quad\|x\|_{2}:=\left(\sum_{i=1}^{n}|x_{i}|^{2}\right)^{1/2}\quad\text{for
all }\;x=(x_{1},x_{2},\ldots,x_{n}).$

There are other classes of Lasso problems modeled in the quadratic composite
form

$\displaystyle\text{minimize
}\;\varphi(x):=\frac{1}{2}\|Ax-b\|_{2}^{2}+g(x),\quad x\in\mathbb{R}^{n},$
(6.67)

where $A$ is an $m\times n$ matrix, $b\in\mathbb{R}^{m}$ and
$g\colon\mathbb{R}^{n}\to\overline{\mathbb{R}}$ is a given regularizer. More
specifically, let us list several well-recognized versions of (6.67) in
addition to (6.66):

  * (i)

The elastic net regularized problem, or the Lasso elastic net problem [29]
with

$g(x):=\mu_{1}\|x\|_{1}+\mu_{2}\|x\|_{2}^{2},$

where $\mu_{1}$ and $\mu_{2}$ are given positive parameters.

  * (ii)

The clustered Lasso problem [63] with

$g(x):=\mu_{1}\|x\|_{1}+\mu_{2}\sum_{1\leq i\leq j\leq n}|x_{i}-x_{j}|,$

where $\mu_{1}$ and $\mu_{2}$ are given positive parameters.

  * (iii)

The fused regularized problem, or the fused Lasso problem [65] with

$g(x):=\mu_{1}\|x\|_{1}+\mu_{2}\|Bx\|_{1},$

where $\mu_{1}$ and $\mu_{2}$ are given positive numbers, and where $B$ is the
$(n-1)\times n$ matrix

$Bx:=[x_{1}-x_{2},x_{2}-x_{3},\ldots,x_{n-1}-x_{n}]\quad\text{for all
}\;x\in\mathbb{R}^{n}.$

Although the developed Algorithm 5.10 allows us to efficiently solve all these
Lasso problems, we concentrate here on numerical results for the basic one
(6.66). It is easy to see that the Lasso problem (6.66) belongs to the
quadratic composite class (5.48). Indeed, we represent (6.66) as minimizing
the nonsmooth convex function $\varphi(x):=f(x)+g(x)$, where

$f(x):=\frac{1}{2}\langle\bar{A}x,x\rangle+\langle\bar{b},x\rangle+\bar{\alpha}\quad\text{and
}\;g(x):=\mu\|x\|_{1}$ (6.68)

with $\bar{A}:=A^{*}A$, $\bar{b}:=-A^{*}b$, and
$\bar{\alpha}:=\frac{1}{2}\|b\|^{2}$, and where the matrix $\bar{A}=A^{*}A$ is
positive-semidefinite. Observe further that the Lasso problem (6.66) always
admits an optimal solution; see [64]. In order to apply Algorithm 5.10 to
solving problem (6.66), we begin with providing explicit calculations of the
first-order and second-order subdifferentials of the regularizer
$g(x)=\mu\|x\|_{1}$ together with the proximal mapping associated with this
function.

Using definition (5.52), it is not hard to compute the proximal mapping of
$g(x)=\mu\|x\|_{1}$ by

$\big{(}\text{\rm Prox}_{\gamma
g}(x)\big{)}_{i}=\begin{cases}x_{i}-\mu\gamma&\text{if}\quad
x_{i}>\mu\gamma,\\\ 0&\text{if}\quad-\mu\gamma\leq x_{i}\leq\mu\gamma,\\\
x_{i}+\mu\gamma&\text{if}\quad x_{i}<-\mu\gamma.\end{cases}$ (6.69)

Now we compute the first-order and second-order subdifferentials of this
function.

######  Proposition 6.1 (subdifferential calculations).

For the regularizer $g(\cdot)=\mu\|\cdot\|_{1}$ in (6.66) we have the
subgradient mapping

$\partial
g(x)=\left\\{v\in\mathbb{R}^{n}\;\bigg{|}\;\begin{array}[]{@{}cc@{}}v_{j}=\text{\rm
sgn}(x_{j}),\;x_{j}\neq 0,\\\
v_{j}\in[-\mu,\mu],\;x_{j}=0\end{array}\right\\}\quad\text{whenever
}\;x\in\mathbb{R}^{n}.$ (6.70)

Further, for each $(x,y)\in\text{\rm gph}\,\partial g$ and
$v=(v_{1},\ldots,v_{n})\in\mathbb{R}^{n}$, the second-order subdifferential of
$g$ is computed by the formula

$\partial^{2}g(x,y)(v)=\Big{\\{}w\in\mathbb{R}^{n}\;\Big{|}\;\Big{(}\frac{1}{\mu}w_{i},-v_{i}\Big{)}\in
G\Big{(}x_{i},\frac{1}{\mu}y_{i}\Big{)},\;i=1,\ldots,n\Big{\\}},$ (6.71)

where the mapping $G\colon\mathbb{R}^{2}\rightrightarrows\mathbb{R}^{2}$ is
defined by

$G(t,p):=\begin{cases}\\{0\\}\times\mathbb{R}&\text{\rm if}\quad t\neq
0,\;p\in\\{-1,1\\},\\\ \mathbb{R}\times\\{0\\}&\text{\rm if}\quad
t=0,\;p\in(-1,1),\\\
(\mathbb{R}_{+}\times\mathbb{R}_{-})\cup(\\{0\\}\times\mathbb{R})\cup(\mathbb{R}\times\\{0\\})&\text{\rm
if}\quad t=0,\;p=-1,\\\
(\mathbb{R}_{-}\times\mathbb{R}_{+})\cup(\\{0\\}\times\mathbb{R})\cup(\mathbb{R}\times\\{0\\})&\text{\rm
if}\quad t=0,\;p=1,\\\ \emptyset&\text{\rm otherwise}.\end{cases}$ (6.72)

[Proof.] These computations follow from [34, Proposition 8.1].

The next theorem provides an efficient condition on (6.66) expressed entirely
in terms of its given data to ensure a global superlinear convergence of
Algorithm 5.10 for solving (6.66).

######  Theorem 6.2 (solving Lasso).

Considering the Lasso problem (6.66), suppose that the matrix $A^{*}A$ is
positive-definite. Then we have:

  * (i)

Algorithm 5.10 is well-defined, and the sequence of its iterates $\\{y^{k}\\}$
globally converges at least Q-superlinearly to $\bar{y}$ as $k\to\infty$.

  * (ii)

The vector $\bar{x}:=Q\bar{y}+c$ is a unique solution to (6.66) being a tilt-
stable local minimizer of the cost function $\varphi$.

[Proof.] It follows from (6.70) that the graph of $\partial g$ is the union of
finitely many closed convex sets, and hence $\partial g$ is semismooth∗ on its
graph. Furthermore, $g$ is proper, convex, and piecewise linear-quadratic on
$\mathbb{R}^{n}$. Then [62, Proposition 13.9] ensures that $g$ is twice epi-
differentiable on $\mathbb{R}^{n}$. Applying Theorem 5.12, we arrive at all
the conclusions of Theorem 6.2.

To run Algorithm 5.10, we need to explicitly determine the sequences
$\\{v^{k}\\}$ and $\\{d^{k}\\}$ generated by this algorithm. Using (6.69),
(6.70), and (6.71) gives us the following expressions for all the components
$i=1,\ldots,n$ of these vectors:

$\left(v^{k}\right)_{i}=\begin{cases}y_{i}-\mu\gamma&\text{if}\quad
y_{i}>\mu\gamma,\\\ 0&\text{if}\quad-\mu\gamma\leq y_{i}\leq\mu\gamma,\\\
y_{i}+\mu\gamma&\text{if}\quad y_{i}<-\mu\gamma,\end{cases}$
$\begin{cases}\big{(}Pd^{k}+\nabla\psi(y^{k})\big{)}_{i}=0&\text{if}\quad\left(v^{k}\right)_{i}\neq
0,\\\
\big{(}Qd^{k}+\nabla\psi(y^{k})\big{)}_{i}=0&\text{if}\quad\left(v^{k}\right)_{i}=0.\end{cases}$

######  Remark 6.3 (Newton descent directions for Lasso).

Let us emphasize that the algorithm directions $d^{k}$ can be computed through
solving a system of linear equations for each $k\in{\rm I\\!N}$. Indeed, for
the sequence $\\{d^{k}\\}$ generated by Algorithm 5.10, denote by $P_{i}$ and
$Q_{i}$ are the $i$-th rows of the matrices $P$ and $Q$, respectively. Define

$(X^{k})_{i}:=\begin{cases}P_{i}&\text{if}\quad v_{i}\neq 0,\\\
Q_{i}&\text{if}\quad v_{i}=0.\end{cases}$

Then $d^{k}$ is a solution to the system of linear equations
$X^{k}d=-\nabla\psi(y^{k})$.

Now we are in a position to conduct numerical experiments for solving the
Lasso problem (6.66) by using our generalized damped Newton method (GDNM) via
Algorithm 5.10. The obtained calculations are compared with those obtained by
implementing the following highly recognized first-order and second-order
algorithms:

  * (i)

The Alternating Direction Methods of Multipliers¶¶¶https://web.stanford.edu/
boyd/papers/admm/lasso/lasso.html (ADMM); see [7, 22, 23].

  * (ii)

The Accelerated Proximal Gradient Method∥∥∥https://github.com/bodono/apg
(APG); see [51, 52].

  * (iii)

The Fast Iterative Shrinkage-Thresholing
Algorithm******https://github.com/he9180/FISTA-lasso (FISTA); see [4].

  * (iv)

The Semismooth Newton Augmented Lagrangian
Method††††††https://www.polyu.edu.hk/ama/profile/dfsun/ (SSNAL) developed in
[37].

All the numerical experiments are conducted on a desktop with 10th Gen
Intel(R) Core(TM) i5-10400 processor (6-Core, 12M Cache, 2.9GHz to 4.3GHz) and
16GB memory. All the codes are written in MATLAB 2016a. Our numerical
experiments are conducted with the test instances $(A,b)$ in (6.66) generated
randomly following the Matlab commands

$\displaystyle A={\rm randn}(m,n);\quad b={\rm randn}(n,1).$

In order to run Algorithm 5.10 for solving Lasso problems, the matrix $A^{*}A$
needs to be positive-definite due to Theorem 6.2. Since $\text{\rm
rank}(A^{*}A)=\text{\rm rank}A$, the matrix $A^{*}A$ is singular if $m<n$.
Therefore, a necessary condition for the positive-definite of $A^{*}A$ is that
$m\geq n$, and thus we only test datasets in which the matrix $A$ has more
rows than columns, or its rows and columns are equal. Note that the modes with
$m\geq n$ appear in practical applications; see, e.g., [19] with applications
to diabetes studies and [4] with applications to image processing. The GDNM
code is publicly available on the
website‡‡‡‡‡‡https://github.com/he9180/GDNM/.

The initial points in all the experiments are set to be the zero vector. The
following relative KKT residual $\eta_{k}$ in (6.73) suggested in [37] is used
to measure the accuracy of an approximate optimal solution $x^{k}$ for (6.66):

$\eta_{k}:=\frac{\|x^{k}-\text{\rm
Prox}_{\mu\|\cdot\|_{1}}(x^{k}-A^{*}(Ax^{k}-b))\|}{1+\|x^{k}\|+\|Ax^{k}-b\|}.$
(6.73)

We stop the algorithms in our experiments when either the condition
$\eta_{k}<10^{-6}$ is satisfied, or they reach the maximum computation time of
$6000$ seconds. For testing purpose, the regularization parameter $\mu$ in the
Lasso problem (6.66) is chosen as $10^{-3}$ or as in [37], i.e.

$\mu=10^{-3}\|A^{*}b\|_{\infty},\quad\text{where
}\;\|x\|_{\infty}:=\max\\{|x_{1}|,|x_{2}|,\ldots,|x_{n}|\\},x=(x_{1},x_{2},\ldots,x_{n}).$
(6.74)

The achieved numerical results are presented in Table 2 and Table 2. In these
tables, “CPU time” stands for the time needed to achieve the prescribed
accuracy of approximate solutions (the smaller the better). As we can see from
the results presented in Tables 2 and 2, GDNM is more efficient in the cases
where $m>>n$ and $n$ is not large, which confirms the need of positive
definiteness of the matrix $A^{*}A$ for the superlinear convergence. On the
other hand, ADMM performs well in all tests while SSNAL is more efficient for
large-scale datasets.

Table 1: $\mu=10^{-3}$

Problem size |  | Number of iterations |  | CPU time
---|---|---|---|---
m | n |  | SSNAL | GDNM | ADMM | APG | FISTA |  | SSNAL | GDNM | ADMM | APG | FISTA
1024 | 256 |  | 4 | 4 | 9 | 42 | 133 |  | 0.13 | 0.09 | 0.02 | 0.04 | 0.25
1024 | 1024 |  | 30 | 22 | 12192 | 172326 | 190461 |  | 10.68 | 1.23 | 35.71 | 485.51 | 2046.34
4096 | 256 |  | 4 | 4 | 9 | 24 | 44 |  | 0.14 | 0.11 | 0.03 | 0.05 | 0.34
4096 | 4096 |  | 1306 | 281 | 12571 | 114879 | 38912 |  | 4163.54 | 6000.00 | 775.59 | 6000.00 | 6000.00

Table 2: $\mu=10^{-3}\left\|A^{*}b\right\|_{\infty}$

Problem size |  | Number of iterations |  | CPU time
---|---|---|---|---
m | n |  | SSNAL | GDNM | ADMM | APG | FISTA |  | SSNAL | GDNM | ADMM | APG | FISTA
1024 | 256 |  | 4 | 5 | 123 | 45 | 133 |  | 0.62 | 0.11 | 0.03 | 0.03 | 0.24
1024 | 1024 |  | 17 | 172 | 174 | 2638 | 26431 |  | 2.38 | 10.72 | 0.56 | 7.41 | 273.84
4096 | 256 |  | 4 | 4 | 248 | 26 | 44 |  | 0.22 | 0.12 | 0.15 | 0.05 | 0.32
4096 | 4096 |  | 18 | 355 | 343 | 1797 | 32412 |  | 149.57 | 668.32 | 23.68 | 95.60 | 5121.51

##  7 Concluding Remarks and Further Research

This paper proposes and develops new globally convergent algorithms of the
damped Newton type to solve some classes of nonsmooth optimization problems
addressing minimization of ${\cal C}^{1,1}$ objectives and problems of
quadratic composite optimization with extended-real-valued regularizers, which
include nonsmooth problems of constrained optimization. We verify well-
posedness of the proposed algorithms and their linear and superlinear
convergence under rather nonrestrictive assumptions. Our approach is based on
advanced machinery of second-order variational analysis and generalized
differentiation. The obtained results are applied to some classes of
optimization problems that arise in machine learning, statistics, and related
areas with the efficient implementation to solving the well-recognized Lasso
problems. The numerical experiments conducted to solve an important class of
nonsmooth Lasso problems by using the suggested algorithm are compared in
detail with the corresponding calculations by using some other first-order and
second-order algorithms.

Our future research includes efficient calculations of second-order
subdifferentials and proximal mappings used in this paper for broader classes
of convex and nonconvex problems with further applications to practically
important models of machine learning, statistics, etc. We also intend to
establish a global superlinear convergence of our damped generalized Newton
algorithms for problems of quadratic composite optimization with extended-
real-valued regularizers without the positive-definiteness requirement on the
quadratic term.

## Acknowledgments

The authors are grateful to two anonymous referees for their helpful remarks
and comments that allowed us to significantly improve the original manuscript.
Our thanks also go to Alexey Izmailov for his useful remarks on the algorithm
developed in Section 3 and to Michal Kočvara and Defeng Sun for helpful
discussions on numerical experiments to solve Lasso problems.

## References

  * [1] Bauschke H.H, Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edition. Springer, New York (2017)
  * [2] Beck, A.: Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. SIAM, Philadelphia, PA (2014)
  * [3] Beck, A.: First-Order Methods in Optimization. SIAM, Philadelphia, PA (2017)
  * [4] Beck, A., Teboulle, M.: (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)
  * [5] Becker, S., Fadili, M.J.: A quasi-Newton proximal splitting method. Adv. Neural Inform. Process. Syst. 25, 2618–2626 (2012)
  * [6] Bonnans, J.F.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161–186 (1994)
  * [7] Boyd, S., Parikh, N,, Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learning, 3, 1–122 (2010)
  * [8] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, UK (2004)
  * [9] Chieu, N.H., Chuong, T.D., Yao, J.-C., Yen, N.D.: Characterizing convexity of a function by its Fréchet and limiting second-order subdifferentials. Set-Valued Var. Anal. 19, 75–96 (2011)
  * [10] Chieu, N.H., Lee, G.M., Yen, N.D.: Second-order subdifferentials and optimality conditions for ${\cal C}^{1}$-smooth optimization problems. Appl. Anal. Optim. 1, 461–476 (2017)
  * [11] Chieu, N.M., Hien, L.V., Nghia, T.T.A.: Characterization of tilt stability via subgradient graphical derivative with applications to nonlinear programming. SIAM J. Optim. 28, 2246–2273 (2018)
  * [12] Colombo, G., Henrion, R., Hoang, N.D., Mordukhovich, B.S.: Optimal control of the sweeping process over polyhedral controlled sets. J. Diff. Eqs. 260, 3397–3447 (2016)
  * [13] Combettes, P.L., Pesquet, J.-C.: Proximal splitting methods in signal processing. In: Bauschke, H.H. et al. (eds) Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185–212. Springer, New York (2011)
  * [14] Ding, C., Sun, D., Ye, J.J.: First-order optimality conditions for mathematical programs with semidefinite cone complementarity constraints. Math. Program. 147, 539–379 (2014)
  * [15] Dontchev, A.L., Rockafellar, R.T.: Characterizations of strong regularity for variational inequalities over polyhedral convex sets. SIAM J. Optim. 6, 1087–1105 (1996)
  * [16] Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings: A View from Variational Analysis, 2nd edition. Springer, New York (2014)
  * [17] Drusvyatskiy, D., Lewis, A.S.: Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential. SIAM J. Optim. 23, 256–267 (2013)
  * [18] Drusvyatskiy, D., Mordukhovich, B.S., Nghia, T.T.A.: Second-order growth, tilt stability, and metric regularity of the subdifferential. J. Convex Anal. 21, 1165–1192 (2014)
  * [19] Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Statist. 32, 407–499 (2004)
  * [20] Facchinei, F., Pang, J.-C.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. II. Springer, New York (2003)
  * [21] Friedlander, M.P., Goodwin, A., Hoheisel, T.: From perspective maps to epigraphical projections. arXiv:2102.06809 (2021)
  * [22] Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17–40 (1976)
  * [23] Glowinski, R., Marroco, A.: Sur lapproximation, par elements finis dordre un, et la resolution, par penalisation-dualite, dune classe de problemes de Dirichlet non lineares. Revue Francaise d’Automatique, Informatique et Recherche Operationelle 9, 41–76 (1975)
  * [24] Gfrerer, H.: On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs. Set-Valued Var. Anal. 21, 151–176 (2013)
  * [25] Gfrerer, H., Mordukhovich, B.S.: Complete characterization of tilt stability in nonlinear programming under weakest qualification conditions. SIAM J. Optim. 25, 2081–2119 (2015)
  * [26] Gfrerer, H., Outrata, J.V.: (2019) On a semismooth∗ Newton method for solving generalized equations. SIAM J. Optim. 31, 489–517 (2021)
  * [27] Ginchev, I., Mordukhovich, B.S.: On directionally dependent subdifferentials. C. R. Acad. Bulg. Sci. 64, 497–508 (2011)
  * [28] Hang, N.T.V,, Mordukhovich, B.S., Sarabi, M.E.: Augmented Lagrangian method for second-order conic programs under second-order sufficiency. J. Global Optim. 82, 51–81 (2022)
  * [29] Hastie, T., Zou, H.: Regularization and variable selection via the elastic net. J. Roy. Statist. Soc. Ser. B 67, 301–320 (2005)
  * [30] Henrion, R., Mordukhovich, B.S., Nam, N.M.: Second-order analysis of polyhedral systems in finite and infinite dimensions with applications to robust stability of variational inequalities. SIAM J. Optim. 20, 2199–2227 (2010)
  * [31] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)
  * [32] Hsieh, C.J., Chang, K.W., Lin, C.J.: A dual coordinate descent method for large-scale linear SVM. Proceedings 25th International Conference on Machine Learning, pp. 408–415. Helsinki, Finland (2008)
  * [33] Izmailov, A.F., Solodov, M.V.: Newton-Type Methods for Optimization and Variational Problems. Springer, New York (2014)
  * [34] Khanh, P.D., Mordukhovich, B.S., Phat, V.T.: A generalized Newton method for subgradient systems. arXiv:2009.10551 (2020)
  * [35] Klatte, D., Kummer, B.: Nonsmooth Equations in Optimization. Regularity, Calculus, Methods and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002)
  * [36] Lee, J.D., Sun, Y., Saunders, M.A.: Proximal Newton-type methods for minimizing composite functions. SIAM J. Optim. 24, 1420–1443 (2014)
  * [37] Li, X., Sun, D., Toh, K.-C.: A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems. SIAM J. Optim. 28, 433–458 (2018)
  * [38] Lichman, M.: UCI Machine Learning Repository. University of California, School of Information and Computer Science, Irvine, CA (2013)
  * [39] Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)
  * [40] Mohammadi, A., Mordukhovich, B.S., Sarabi, M.E.: Variational analysis of composite models with applications to continuous optimization. Math. Oper. Res. DOI: 10.1287/moor.2020.1074 (2020)
  * [41] Mohammadi, A., Mordukhovich, B.S., Sarabi, M.E.: Parabolic regularity in geometric variational analysis. Trans. Amer. Math. Soc. 374, 1711–1763 (2021)
  * [42] Mohammadi, A., Sarabi, M.E.: Twice epi-differentiability of extended-real-valued functions with applications in composite optimization. SIAM J. Optim. 30, 2379–2409 (2020)
  * [43] Mordukhovich, B.S.: Sensitivity analysis in nonsmooth optimization. In: Field, D.A., Komkov, V.(eds) Theoretical Aspects of Industrial Design, pp. 32–46. SIAM Proc. Appl. Math. 58. Philadelphia, PA (1992)
  * [44] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications. Springer, Berlin (2006)
  * [45] Mordukhovich, B.S.: Variational Analysis and Applications. Springer, Cham, Switzerland (2018)
  * [46] Mordukhovich, B.S., Nghia, T.T.A.: Second-order characterizations of tilt stability with applications to nonlinear programming. Math. Program. 149, 83–104 (2015)
  * [47] Mordukhovich, B.S., Outrata, J.V.: On second-order subdifferentials and their applications. SIAM J. Optim. 12, 139–169 (2001)
  * [48] Mordukhovich, B.S., Rockafellar, R.T.: Second-order subdifferential calculus with applications to tilt stability in optimization. SIAM J. Optim. 22, 953–986 (2012)
  * [49] Mordukhovich, B.S., Sarabi, M.E.: Generalized Newton algorithms for tilt-stable minimizers in nonsmooth optimization. SIAM J. Optim. 31, 1184–1214 (2021)
  * [50] Mordukhovich, B.S., Yuan, X., Zheng, S., Zhang. J.: A globally convergent proximal Newton-type method in nonsmooth convex optimization. arXiv:2011.08166 (2020)
  * [51] Nesterov, Yu.: A method of solving a convex programming problem with convergence rate $\mathcal{O}(1/k^{2})$. Soviet Math. Dokl. 27, 372–376 (1983)
  * [52] Nesterov, Yu.: Lectures on Convex Optimization, 2nd edition. Springer, Cham, Switzerland (2018)
  * [53] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2006)
  * [54] Outrata, J.V., Sun, D.: On the coderivative of the projection operator onto the second-order cone. Set-Valued Anal. 16, 999–1014 (2008)
  * [55] Pelckmans, K., De Brabanter, J., De Moor, B., Suykens, J.A.K.: Convex clustering shrinkage. In: PASCAL Workshop on Statistics and Optimization of Clustering, pp. 1–6. London, UK (2005)
  * [56] Poliquin, R.A., Rockafellar, R.T.: Tilt stability of a local minimum. SIAM J. Optim. 8, 287–299 (1998)
  * [57] Polyak, B.T.: Introduction to Optimization. Optimization Software, New York (1987)
  * [58] Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed) Optimization, pp. 283–298. Academic Press, New York (1969)
  * [59] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367(1993)
  * [60] Rockafellar, R.T.: Augmented Lagrangian multiplier functions and duality in nonconvex programming. SIAM J. Control 12, 268–285 (1974)
  * [61] Rockafellar, R.T.: Augmented Lagrangians and hidden convexity in sufficient conditions for local optimality. http://sites.math.washington.edu/ rtr/papers/rtr256-HiddenConvexity.pdf (2020)
  * [62] Rockafellar, R.T., Wets R.J-B.: Variational Analysis. Springer, Berlin (1998)
  * [63] She, Y.: Sparse regression with exact clustering. Electron. J. Stat. 4, 1055–1096 (2010)
  * [64] Tibshirani, R.: Regression shrinkage and selection via the Lasso. J. R. Stat. Soc. 58, 267–288 (1996)
  * [65] Tibshirani, R., Saunders, M., Rosset, S., Zhu, J., Knight, K.: Sparsity and smoothness via the fused Lasso. J. R. Stat. Soc. Ser. B Stat. Methodol. 67, 91–108 (2005)
  * [66] Ulbrich, M.: Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces. SIAM, Philadelphia, PA (2011)
  * [67] Yao, J.-C., Yen, N.D.: Coderivative calculation related to a parametric affine variational inequality. Part 1: Basic calculation. Acta Math. Vietnam. 34, 157–172 (2009)