processing, etc. This problem is formulated as follows:

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

where $A$ is an $m\times n$ matrix, $\mu>0$, and $b\in{\rm I\\!R}^{m}$, and
where $\|\cdot\|_{1}$ and $\|\cdot\|_{2}$ stand for the standard $p$-norms on
${\rm I\\!R}^{n}$. It is easy to see that the Lasso problem (6.14) belongs to
the class of convex composite optimization problems (5.8). Indeed, we can
represent (6.14) as minimizing the nonsmooth convex function
$\varphi(x):=f(x)+g(x)$, where

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

with $\widetilde{A}:=A^{*}A$, $\widetilde{b}:=-A^{*}b$, and
$\widetilde{\alpha}:=\frac{1}{2}\|b\|^{2}$, and where the matrix
$\widetilde{A}=A^{*}A$ is symmetric and positive-semidefinite. Observe that
the Lasso problem (6.14) always admits an optimal solution [92].

We start implementing Algorithms 3 and 4 to solve (6.14) with the explicit
computation of their ingredients (proximal and subgradient mappings,
generalized Hessian of $g$) given entirely via the problem data.

######  Proposition 6.4 (explicit computations for the Lasso problem).

Let $g(x)=\mu\|x\|_{1}$ be the regularizer in the Lasso problem (6.14). Then
we have the calculation formulas:

$\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.16) $\partial
g(x)=\left\\{v\in{\rm
I\\!R}^{n}\;\bigg{|}\;\begin{array}[]{<EMAIL_ADDRESS>sgn}(x_{i}),\;x_{i}\neq 0,\\\
v_{i}\in[-\mu,\mu],\;x_{i}=0\end{array}\right\\}\quad\text{whenever
}\;x\in{\rm I\\!R}^{n}.$ (6.17)

The generalized Hessian of $g$ is calculated by

$\partial^{2}g(x,y)(v)=\Big{\\{}w\in{\rm
I\\!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.18)

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

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

[Proof.] The formula for the proximal mapping (6.16) follows from definition
(5.3) and the form of $g(\cdot)=\|\cdot\|_{1}$. The calculations of $\partial
g$ and $\partial^{2}g$ are taken from [46, Propositions 7.1 and 7.2],
respectively.

Let us present specifications of Algorithms 3 and 4 as well as Theorems 5.6
and 5.7 on their performances, respectively, for the Lasso problem (6.14).

######  Theorem 6.5 (solving Lasso).

Considering the Lasso problem (6.14), we have the following:

(i) Algorithm 3, with all its ingredients calculated in Proposition 6.4,
either stops after finitely many iterations, or produces a sequence
$\\{x^{k}\\}$ such that it globally Q-superlinearly converges to $\bar{x}$,
which is the unique solution to (6.14) and a tilt-stable local minimizer of
$\varphi$ with modulus $\kappa:=1/\lambda_{\text{\rm min}(A^{*}A)}$, provided
that the matrix $A^{*}A$ is positive-definite.

(ii) Algorithm 4, with the positive-semidefinite matrix $A^{*}A$ and the
ingredients calculated in Proposition 6.4, either stops after finitely many
steps, or produces a sequence $\\{x^{k}\\}$ such that any accumulation point
$\bar{x}$ of it is a solution to (6.14). If in addition $\partial\varphi$ is
metrically regular around $(\bar{x},0)$ with modulus $\kappa>0$, then the
sequence $\\{x^{k}\\}$ globally Q-superlinearly converges to $\bar{x}$, which
is a tilt-stable local minimizer of $\varphi$ with the same modulus.

[Proof.] Observe by (6.17) that the graph of $\partial g$ is the union of
finitely many closed convex sets, and hence $\partial g$ is semismooth∗ on its
graph; see [32]. Furthermore, $g$ is a proper, convex, and piecewise linear
function on ${\rm I\\!R}^{n}$. Then it follows from [88, Proposition 13.9]
that $g$ is twice epi-differentiable on ${\rm I\\!R}^{n}$. Applying Theorems
5.6 and 5.7, we arrive at all the conclusions in (i) and (ii) of this theorem,
respectively.

To run Algorithms 3 and 4, we need to explicitly determine the sequences
$\\{v^{k}\\}$ and $\\{d^{k}\\}$ generated by these algorithms. The expressions
for $v^{k}$ follows directly from formula (6.16) telling us that

$\left(v^{k}\right)_{i}=\begin{cases}(u^{k})_{i}-\mu\gamma&\text{if}\quad(u^{k})_{i}>\mu\gamma,\\\
0&\text{if}\quad-\mu\gamma\leq(u^{k})_{i}\leq\mu\gamma,\\\
(u^{k})_{i}+\mu\gamma&\text{if}\quad(u^{k})_{i}<-\mu\gamma,\end{cases}\quad\text{where
}\;u^{k}=x^{k}-\gamma(A^{*}Ax^{k}+b).$

Using further the formulas in (6.17)–(6.19), we express $d^{k}$ in Algorithm 3
via the conditions

$\begin{cases}\big{(}-\frac{1}{\gamma}(x^{k}-v^{k})-A^{*}Ad^{k}\big{)}_{i}=0&\text{if}\quad\left(v^{k}\right)_{i}\neq
0,\\\
\big{(}x^{k}-v^{k}+d^{k}\big{)}_{i}=0&\text{if}\quad\left(v^{k}\right)_{i}=0.\end{cases}$

Thus $d^{k}$ can be computed for each $k\in{\rm I\\!N}$ by solving the linear
equation $X^{k}d=v^{k}-x^{k}$, where

$(X^{k})_{i}:=\begin{cases}\gamma(A^{*}A)_{i}&\text{if}\quad(v^{k})_{i}\neq
0,\\\ I_{i}&\text{if}\quad(v^{k})_{i}=0.\end{cases}$ (6.20)

Similarly, by employing the calculations of Proposition 6.4 in the framework
of Algorithm 4 and by performing elementary transformations, we get the linear
equation

$(BX^{k}+\gamma\mu_{k}I)d^{k}=B(v^{k}-x^{k})$

to find the direction $d^{k}$, where $X^{k}$ is computed in (6.20), and
$B:=I-\gamma A^{*}A$.

Now we are ready to conduct numerical experiments for solving the Lasso
problem (6.14) by using our globally convergent coderivative-based Generalized
Damped Newton Method (GDNM) via Algorithm 3 and globally convergent
coderivative-based Generalized Regularized Newton Method (GRNM) via Algorithm
4. 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 555https://web.stanford.edu/
boyd/papers/admm/lasso/lasso.html (ADMM); see [8, 28, 29].

  * (ii)

The Fast Iterative Shrinkage-Thresholing
Algorithm666https://github.com/he9180/FISTA-lasso (FISTA) with the code
presented in [4].

  * (iii)

The Semismooth Newton Augmented Lagrangian
Method777https://www.polyu.edu.hk/ama/profile/dfsun/ (SSNAL) recently
developed in [51].

All the numerical experiments are conducted in the same desktop and software
described in Section 6.1. All the codes are written in MATLAB 2016a. In our
numerical experiment, $A$ is generated randomly with i.i.d. (identically and
independent distributed) standard Gaussian entries, where $b$ is generated
randomly with values of components are from $0$ to $1$. In some particular
tests, we normalize each column of $A$ so that $A^{*}A$ is close to singular
and mark them with symbol ∗ for identification. In summary, $A^{*}A$ is
nonsingular in Tests 3, 4, 7, 8, and it is singular or close to singular in
all the other tests. Table 1 contains 2 tests where $n>m$ and the matrix
$A^{*}A$ is nonsingular, 2 tests where $n>m$ and the matrix $A^{*}A$ is
singular, 2 tests where $n=m$ and the matrix $A^{*}A$ is nonsingular, 2 tests
where $n=m$ and the matrix $A^{*}A$ is singular, and 2 tests when $m>n$. To
simplify the numerical implementations for solving the Lasso problem (6.14),
we set $\mu:=10^{-3}$ as the tuning parameter for all the tests. If an
algorithm cannot start iterating in the first step, it is marked by “Error”
word; this concerns only some cases of GDNM when the matrix $A^{*}A$ is not
positive-definite. In our numerical experiments, $x^{0}:=0$ is the starting
point for each algorithm, and the following relative KKT residual $\eta_{k}$
in (6.21) suggested in [51] is used to measure the accuracy of an approximate
optimal solution $x^{k}$ for (6.14):

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

We stop the algorithms when either the condition $\eta_{k}<10^{-6}$ is
satisfied, or the maximum computation time of $10000$ seconds is reached. The
results of computations for this part are displayed in Table 1. There ‘TN’
stands for the test number, ‘iter’ indicates the number of performed
iterations, and ‘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 Table 1, our algorithms GDNM and
GRNM are highly efficient when $A^{*}A$ is nonsingular, where the
$Q$-superlinear convergence is guaranteed by Theorem 6.5. They may behave even
better than the other compared algorithms when $m\geq n$, which is the setting
of various practically important models; see, e.g., [24] for Lasso
applications to diabetes studies where $m$ is much large than $n$, and [4] for
$m=n$ with applications to image processing.

When the matrix $A^{*}A$ is singular (or close to be singular), our
theoretical results do not guarantee the fast convergence of GDNM and GRNM,
while the conducted numerical experiments show that GRNM performs better that
GDNM and better than FISTA and ADMM in Table 1, while usually worse than
SSNAL. A partial explanation for this is that SSNAL is actually a hybrid
algorithm, which combines the first-order augmented Lagrangian method to solve
dual subproblems, which are strongly convex and of lower dimensions, with the
subsequent applications of the second-order semismooth Newton method. Such a
combination exhibits a high efficiency in solving Lasso problems in the
singular case.

Table 1: Solving (6.14) on random instances  Problem size and TN |  | iter |  | CPU time
---|---|---|---|---
TN | m | n |  | SSNAL | FISTA | ADMM | GRNM | GDNM |  | SSNAL | FISTA | ADMM | GRNM | GDNM
1 | 400 | 800 |  | 25 | 37742 | 22873 | 1813 | Error |  | 0.45 | 145.52 | 10.89 | 45.62 | Error
2 | 4000 | 8000 |  | 153 | 19173 | 19173 | 2499 | Error |  | 847.87 | 10000 | 2359.36 | 10000 | Error
3 | 2000 | 2000 |  | 43 | 239701 | 12785 | 59 | 12 |  | 78.38 | 8138.94 | 158.12 | 11.07 | 2.24
4 | 4000 | 4000 |  | 246 | 73374 | 5970 | 59 | 218 |  | 1253.45 | 10000 | 320.81 | 48.16 | 178.91
5* | 2000 | 2000 |  | 22 | 3619 | 90501 | 394 | 292 |  | 18.11 | 123.38 | 1141.64 | 65.60 | 58.80
6* | 4000 | 4000 |  | 24 | 3629 | 103868 | 520 | 555 |  | 231.40 | 462.53 | 5166.16 | 369.27 | 474.74
7 | 800 | 400 |  | 4 | 430 | 10 | 6 | 3 |  | 0.14 | 0.86 | 0.02 | 0.11 | 0.08
8 | 8000 | 4000 |  | 13 | 487 | 11 | 7 | 3 |  | 18.80 | 117.92 | 3.67 | 8.46 | 4.39
9* | 800 | 400 |  | 11 | 245 | 426 | 31 | 7 |  | 0.18 | 0.53 | 0.12 | 0.23 | 0.11
10* | 8000 | 4000 |  | 11 | 238 | 411 | 72 | 9 |  | 8.37 | 59.18 | 32.17 | 56.37 | 8.88

###  6.3 Box Constrained Quadratic Programming

This subsection is devoted to specifying Algorithms 3 and 4 for quadratic
programming problems of the form

minimize $\displaystyle\;\varphi(x):=\dfrac{1}{2}\langle Ax,x\rangle+\langle
b,x\rangle\quad$ (6.22) subject to $\displaystyle\;l_{i}\leq x_{i}\leq
L_{i}\text{ for all }i=1,\ldots,n$

where $A$ is an $n\times n$ positive-semidefinite matrix, and where
$b,l,L\in{\rm I\\!R}^{n}$ are such that $l_{i}\leq L_{i}$ as $i=1,\ldots,n$.

######  Proposition 6.6.

Considering the indicator function $\delta_{\Omega}:{\rm
I\\!R}^{n}\to\overline{{\rm I\\!R}}$ of the set

$\Omega:=\big{\\{}x\in{\rm I\\!R}^{n}\;\big{|}\;\ell\leq x\leq L\big{\\}},$
(6.23)

we have the precise calculation formulas

$\text{\rm Prox}_{\gamma g}(x)=P_{\Omega}(x)=\big{(}\text{\rm min}\\{\text{\rm
max}\big{\\{}x_{i},\ell_{i}\big{\\}},L_{i}\big{\\}}\big{)}_{i=1}^{n}\quad\text{for
}\;x\in{\rm I\\!R}^{n},\;\gamma>0,$ (6.24)
$\partial\delta_{\Omega}(x)=N_{\Omega}(x)=F_{1}(x_{1})\times\ldots\times
F_{n}(x_{n})\quad\text{for }\;x\in\Omega,\;\mbox{ where}$ (6.25)
$F_{i}(t)=\begin{cases}(-\infty,0]&\text{if }\quad t=\ell_{i},\\\
[0,\infty)&\text{if }\quad t=L_{i},\\\ \\{0\\}&\text{if }\quad
t\in(\ell_{i},L_{i}).\end{cases}$

The generalized Hessian of $\delta_{\Omega}$ is calculated by

$\partial^{2}\delta_{\Omega}(x,y)(v)=\big{\\{}w\in{\rm
I\\!R}^{n}\;\big{|}\;\big{(}w_{i},-v_{i}\big{)}\in
G_{i}\big{(}x_{i},y_{i}\big{)},\;i=1,\ldots,n\big{\\}},$ (6.26)

where the mappings $G_{i}\colon{\rm I\\!R}^{2}\rightrightarrows{\rm
I\\!R}^{2}$, $i=1,\ldots,n$, are defined by

$G_{i}(t,p):=\begin{cases}{\rm I\\!R}\times\\{0\\}&\text{\rm if}\quad
t=\ell_{i},p<0,\\\ ({\rm I\\!R}_{-}\times{\rm I\\!R}_{+})\cup({\rm
I\\!R}\times\\{0\\})\cup(\\{0\\}\times{\rm I\\!R})&\text{\rm if}\quad
t=\ell_{i},\;p=0,\\\ \\{0\\}\times{\rm I\\!R}&\text{\rm if}\quad
t\in(\ell_{i},L_{i}),\;p=0,\\\ ({\rm I\\!R}_{+}\times{\rm
I\\!R}_{-})\cup(\\{0\\}\times{\rm I\\!R})\cup({\rm
I\\!R}\times\\{0\\})&\text{\rm if}\quad t=L_{i},\;p=0,\\\ {\rm
I\\!R}\times\\{0\\}&\text{\rm if}\quad t=L_{i},\;p>0,\\\ \emptyset&\text{\rm
otherwise}.\end{cases}$ (6.27)

[Proof.] The formula for the proximal mapping (6.24) follows from [3, Lemma
6.26]. Note that

$\delta_{\Omega}(x)=\delta_{\Omega_{1}}(x_{1})+\ldots+\delta_{\Omega_{n}}(x_{n})\quad\text{for
all }\;x=(x_{1},\ldots,x_{n})\in{\rm I\\!R}^{n},$

where $\Omega_{i}:=[\ell_{i},L_{i}]=\\{t\in{\rm I\\!R}\;|\;\ell_{i}\leq t\leq
L_{i}\\}$, $i=1,\ldots,n$. Using [88, Exercise 8.14 and Example 6.10], we
obtain (6.25). It remains to verify the second-order subdifferential formula
(6.26) for $\delta_{\Omega}$ at $(x,y)\in\mbox{\rm
gph}\,\partial\delta_{\Omega}$. Observe that $N_{{\rm\small
gph}\,\partial\delta_{\Omega_{i}}}=G_{i}\quad\text{for all }\;i=1,\ldots,n$.
This allows us to deduce from [63, Theorem 4.3] the representation

$\partial^{2}\delta_{\Omega}(x,y)(v)=\big{\\{}w\in{\rm
I\\!R}^{n}\;\big{|}\;\big{(}w_{i},-v_{i}\big{)}\in N_{{\rm\small
gph}\,\partial\delta_{\Omega_{i}}}(x_{i},y_{i}),\;i=1,\ldots,n\big{\\}},$

which therefore justifies the fulfillment of (6.26) and completes the proof of
the proposition.

Next we obtain specifications of Algorithms 3 and 4 together with Theorem 5.6
and 5.7 on their performances, respectively, for the case of box constrained
quadratic programming in (6.22).

######  Theorem 6.7 (solving box constrained quadratic programs).

Considering the quadratic programming problem (6.22), we have the following
assertions:

(i) Assume that the matrix $A$ is positive-definite. Then Algorithm 3, with
all its ingredients calculated in Proposition 6.6, either stops after finitely
many iterations, or produces a sequence $\\{x^{k}\\}$ such that it globally
Q-superlinearly converges to $\bar{x}$, which is the unique solution to (6.22)
and a tilt-stable local minimizer of $\varphi$ with modulus
$\kappa:=1/\lambda_{\text{\rm min}(A^{*}A)}$.

(ii) Assume that the matrix $A$ is positive-semidefinite. Then Algorithm 4,
with all its ingredients calculated in Proposition 6.6, either stops after
finitely many iterations, or produces a sequence $\\{x^{k}\\}$ such that any
accumulation point $\bar{x}$ of it is a solution to (6.22). If in addition
$\partial\varphi$ is metrically regular around $(\bar{x},0)$ with some modulus
$\kappa>0$, then the sequence $\\{x^{k}\\}$ globally Q-superlinearly converges
to $\bar{x}$, which is a tilt-stable local minimizer of $\varphi$ with the
same modulus.

[Proof.] Reduce (6.22) to the equivalent form of convex composite
optimization:

$\mbox{\rm minimize}\quad f(x)+g(x)\quad\text{subject to }\;x\in{\rm
I\\!R}^{n},\;\mbox{ where}$ $f(x):=\frac{1}{2}\langle Ax,x\rangle+\langle
b,x\rangle,\quad g(x):=\delta_{\Omega}(x),\quad\Omega:=\big{\\{}x\in{\rm
I\\!R}^{n}\;\big{|}\;\ell\leq x\leq L\big{\\}}.$

Observe by (6.25) that the graph of $\partial g$ is the union of finitely many
closed convex sets, and hence $\partial g$ is semismooth∗ on its graph by
[32]. Since $\Omega$ is polyhedral, it follows from [88, Example 10.24] that
$g$ is fully amenable on ${\rm I\\!R}^{n}$ in the sense of [88]. Then using
[88, Corollary 13.15] tells us that $g$ is twice epi-differentiable on ${\rm
I\\!R}^{n}$. Applying now Theorems 5.6 and 5.7, we verify both assertions of
this theorem.

To run Algorithms 3 and 4, we need to explicitly determine the sequences
$\\{v^{k}\\}$ and $\\{d^{k}\\}$ generated by these algorithms. The expressions
for $v^{k}$ follows directly from (6.24), which tells us that

$v^{k}=\big{(}\text{\rm min}\big{\\{}\text{\rm
max}\\{u_{i},\ell_{i}\big{\\}},L_{i}\big{\\}}\big{)}_{i=1}^{n}.$

Using further the formulas in (6.25)–(6.27), we express $d^{k}$ in Algorithm 3
via the conditions

$\begin{cases}\big{(}-\frac{1}{\gamma}(x^{k}-v^{k})-Ad^{k}\big{)}_{i}=0&\text{if}\quad\left(u^{k}-v^{k}\right)_{i}=0,\\\
\big{(}-x^{k}-v^{k}+d^{k}\big{)}_{i}=0&\text{if}\quad\left(u^{k}-v^{k}\right)_{i}\neq
0.\end{cases}$

Thus $d^{k}$ can be computed for each $k\in{\rm I\\!N}$ by solving the linear
equation $X^{k}d=v^{k}-x^{k}$, where

$(X^{k})_{i}:=\begin{cases}\gamma A_{i}&\text{if}\quad(u^{k}-v^{k})_{i}=0,\\\
I_{i}&\text{if}\quad(u^{k}-v^{k})_{i}\neq 0.\end{cases}$ (6.28)

Similarly, by employing the calculations of Proposition 6.6 in the framework
of Algorithm 4 and by performing elementary transformations, we get the linear
equation

$(BX^{k}+\gamma\mu_{k}I)d^{k}=B(v^{k}-x^{k})$

to find the direction $d^{k}$, where $X^{k}$ is computed in (6.28), and
$B:=I-\gamma A$. Now we are ready to conduct numerical experiments for solving
quadratic programming problems with box constraints by using our GDNM via
Algorithm 3 and GRNM via Algorithm 4. Our methods are compared with the trust
region reflective algorithm in MATLAB’s quadratic programming solver. All the
numerical experiments are conducted in the same desktop and software described
in Section 6.1.

To get the positive-semidefinite matrix $A$, we generate a random $n\times n$
matrix $C$ with i.i.d. standard uniform entries and then define $A:=C^{*}C$.
In some particular tests, we put $A:=C^{*}C/10^{7}$ so that $A$ is close to be
singular and mark these tests by $*$. Then the vectors $b$ and $l$ are
generated randomly with i.i.d. standard uniform entries. To get the vector
$L\in{\rm I\\!R}^{n}$ such that $l_{i}\leq L_{i}$ for all $i=1,\ldots,n$,
entries of $L$ are generated independently with uniform distribution on the
interval $(1,2)$. The initial points are all ones vector for all the tests and
all the algorithms. As suggested in the MATLAB built in quadratic programming
solver, the stopping criterion used is the function tolerance one, i.e.,

$\displaystyle\dfrac{|f(x^{k})-f(x^{k+1})|}{1+|f(x^{k})|}\leq\varepsilon.$

The tolerance $\varepsilon$ is chosen to be $10^{-9}$ for all the tests and
all the algorithms. The results of numerical experiments in this part are
shown in Table 2. In this table, ‘TR’ refers to the trust region reflective
method while other information is the same as in Subsection 6.2.

TN and size |  | Iter |  | CPU time
---|---|---|---|---
TN | size |  | TR | GDNM | GRNM |  | TR | GDNM | GRNM
1 | 200 |  | 6 | 4 | 6 |  | 0.16 | 0.07 | 0.02
2 | 500 |  | 7 | 7 | 6 |  | 0.08 | 0.05 | 0.04
3 | 2000 |  | 7 | 7 | 6 |  | 1.38 | 1.30 | 2.40
4 | 5000 |  | 9 | 8 | 6 |  | 8.03 | 9.06 | 18.33
5* | 200 |  | 7 | 2 | 5 |  | 0.61 | 0.08 | 0.02
6* | 500 |  | 9 | 3 | 5 |  | 0.11 | 0.03 | 0.04
7* | 2000 |  | 10 | 10 | 8 |  | 1.61 | 2.00 | 2.97
8* | 5000 |  | 15 | 39 | 6 |  | 14.58 | 54.89 | 21.54
Table 2: Solving box constrained quadratic programming on random instances

The obtained results show that our algorithms GDNM and GRNM are more efficient
when the size of the problem is rather small; see, e.g., Tests 1, 2, 3 and 5,
6. It can also be seen that GRNM is more stable than GDNM when the size of the
problems is increasing. Tests 4, 7 and 8 indicate that our methods should be
further improved to solve problems in high-dimensional spaces.

##  7 Conclusions and Future Research

In this paper we propose and develop two globally convergent generalized
Newton methods to solve problems of ${\cal C}^{1,1}$ optimization and of
convex composite optimization with extended-real-valued regularizers, which
include nonsmooth problems of constrained optimization. The developed
algorithms are far-going extensions of the classical damped Newton method and
of the regularized Newton algorithm with the replacement of the standard
Hessian by its generalized version applied to nonsmooth (of the second order)
functions. The latter construction is coderivative generated, which coins the
names of our generalized Newton methods. The obtained results demonstrate the
efficiently of both algorithms, their global superlinear convergence under
appropriate assumptions, and their applications to the solution of Lasso
problems and of box constrained problem of quadratic programming with
conducting numerical experiments.

Our future research includes developing hybrid generalized Newton methods,
which contain subproblems that can be efficiently solved by using first-order
algorithms, and then combining them with the advanced second-order Newton-type
techniques. We intend to establish the global superlinear convergence of
iterates under relaxed assumptions that do not involve the positive-
definiteness of the generalized Hessian in ${\cal C}^{1,1}$ optimization as
well as the strong convexity requirement for problems of convex composite
optimization, which will go beyond those with quadratic smooth parts. The
obtained results would allow us to develop new applications to Lasso problems
as well as to other important classes of models in machine learning,
statistic, and related disciplines.

## Appendix: Some Technical Lemmas

This section contains four technical lemmas used in the text.

The first lemma is a local version of [44, Lemma 2.20]. The proof of this
result is similar to the original one, and thus it is omitted.

######  Lemma 7.1.

Let $\Omega\subset{\rm I\\!R}^{n}$ be an open set, and let
$\varphi:\Omega\to{\rm I\\!R}$ be a continuously differentiable function such
that $\nabla\varphi$ is Lipschitz continuous with modulus $L>0$. Then for any
$\sigma>0$, $x\in\Omega$, and $d\in{\rm I\\!R}^{n}$ satisfying
$\langle\nabla\varphi(x),d\rangle<0$, the following inequality

$\varphi(x+\tau d)\leq\varphi(x)+\sigma\tau\langle\nabla\varphi(x),d\rangle$
(7.1)

holds whenever $\tau\in(0,\overline{\tau}]$ and $x+\tau d\in\Omega$, where

$\overline{\tau}:=\frac{2(\sigma-1)\langle\nabla\varphi(x),d\rangle}{L\|d\|^{2}}>0.$

The next lemma provides conditions for the $R$-linear and $Q$-linear
convergence of sequences.

######  Lemma 7.2 (estimates for convergence rates).

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

  * (i)

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

  * (ii)

$\beta_{k}\geq c_{2}\gamma_{k}$.

  * (iii)

$c_{3}\gamma_{k}^{2}\geq\alpha_{k}$.

Then the sequence $\\{\alpha_{k}\\}$ Q-linearly converges to zero, and the
sequences $\\{\beta_{k}\\}$ and $\\{\gamma_{k}\\}$ R-linearly converge to zero
as $k\to\infty$.

[Proof.] Combining (i), (ii), and (iii) yields the inequalities

$\alpha_{k}-\alpha_{k+1}\geq c_{1}\beta_{k}^{2}\geq
c_{1}c_{2}^{2}\gamma_{k}^{2}\geq\frac{c_{1}c_{2}^{2}}{c_{3}}\alpha_{k}\quad\text{for
all }\;k\geq k_{0},$

which imply that $\alpha_{k+1}\leq q\alpha_{k}$, where
$q:=1-(c_{1}c_{2}^{2})/c_{3}\in(0,1)$. This verifies that the sequence
$\\{\alpha_{k}\\}$ Q-linearly converges to zero. Using the latter and the
assumed condition (i) ensures that

$\beta_{k}^{2}\leq\frac{1}{c_{1}}(\alpha_{k}-\alpha_{k+1})\leq\frac{1}{c_{1}}\alpha_{k}\leq\frac{1}{c_{1}}q\alpha_{k-1}\leq\ldots\leq\frac{1}{c_{1}}q^{k}\alpha_{0}\quad\text{for
all }\;k\geq k_{0},$

which tells us that $\beta_{k}\leq c\mu^{k}$, where
$c:=\sqrt{\alpha_{0}/c_{1}}$ and $\mu:=\sqrt{q}$. This justifies the
$R$-linear convergence of the sequence $\\{\beta_{k}\\}$ to zero. Furthermore,
it easily follows from (ii) that the sequence $\\{\gamma_{k}\\}$ $R$-linearly
converge to zero, and thus we are done with the proof.

Now we obtain a useful result on the semismooth∗ property of compositions.

######  Lemma 7.3 (semismooth∗ property of composition mappings).

Let $A\in{\rm I\\!R}^{n\times n}$ be a symmetric nonsingular matrix, $b\in{\rm
I\\!R}^{n}$, $\bar{x}\in{\rm I\\!R}^{n}$, and $f:{\rm I\\!R}^{n}\to{\rm
I\\!R}^{n}$ be continuous and semismooth∗ at $\bar{y}:=A\bar{x}+b$. Then the
mapping $g:{\rm I\\!R}^{n}\to{\rm I\\!R}^{n}$ defined by $g(x):=f(Ax+b)$ is
semismooth∗ at $\bar{x}$.

[Proof.] Using the coderivative chain rule from [59, Theorem 1.66], we get

$D^{*}g(x)(w)=A^{*}D^{*}f(Ax+b)(w)\quad\text{for all }\;w\in{\rm I\\!R}^{n}.$
(7.2)

Denote $\mu:=\sqrt{\text{\rm max}\\{1,\|A\|^{2}\\}\cdot\text{\rm
max}\\{1,\|A^{-1}\|^{2}\\}}>0$. Picking any $\varepsilon>0$ and employing the
semismooth∗ property of $f$ at $\bar{y}$, we find $\delta>0$ such that

$|\langle x^{*},y-\bar{y}\rangle-\langle
y^{*},f(y)-f(\bar{y})\rangle|\leq\frac{\varepsilon}{\mu}\big{\|}(y-\bar{y},f(y)-f(\bar{y}))\big{\|}\cdot\|(x^{*},y^{*})\|$
(7.3)

for all $y\in\mathbb{B}_{\delta}(\bar{y})$ and all $(x^{*},y^{*})\in\mbox{\rm
gph}\,D^{*}f(y)$. Denoting $r:=\delta/\|A\|>0$ gives us
$y:=Ax+b\in\mathbb{B}_{\delta}(\bar{y})$ whenever
$x\in\mathbb{B}_{r}(\bar{x})$. Picking now $x\in\mathbb{B}_{r}(\bar{x})$ and
$(z^{*},w^{*})\in\mbox{\rm gph}\,D^{*}g(x)$, we get
$(A^{-1}z^{*},w^{*})\in\mbox{\rm gph}\,D^{*}f(Ax+b)$ due to (7.2). It follows
from (7.3) that

$\displaystyle|\langle z^{*},x-\bar{x}\rangle-\langle
w^{*},g(x)-g(\bar{x})\rangle|$ $\displaystyle=$ $\displaystyle|\langle
A^{-1}z^{*},y-\bar{y}\rangle-\langle w^{*},f(y)-f(\bar{y})\rangle|$
$\displaystyle\leq$
$\displaystyle\frac{\varepsilon}{\mu}\big{\|}(y-\bar{y},f(y)-f(\bar{y}))\|\cdot\big{\|}(A^{-1}z^{*},w^{*})\big{\|}$
$\displaystyle=$
$\displaystyle\frac{\varepsilon}{\mu}\big{\|}(Ax-A\bar{x},g(x)-g(\bar{x}))\big{\|}\cdot\big{\|}(A^{-1}z^{*},w^{*})\big{\|}$
$\displaystyle\leq$
$\displaystyle\varepsilon\|(x-\bar{x},g(x)-g(\bar{x}))\|\cdot\|(z^{*},w^{*})\|,$

which verifies the semismooth∗ property of $g$ at $\bar{x}$.

The final lemma establishes tilt stability of strongly convex functions at
stationary points.

######  Lemma 7.4 (strong convexity and tilt-stability).

Let $\varphi:{\rm I\\!R}^{n}\to\overline{{\rm I\\!R}}$ be an l.s.c. and
strongly convex function with modulus $\kappa>0$, and let $\bar{x}\in\mbox{\rm
dom}\,\varphi$ such that $0\in\partial\varphi(\bar{x})$. Then $\bar{x}$ is a
tilt-stable local minimizer of $\varphi$ with modulus $\kappa^{-1}$.

[Proof.] By the second-order characterization of strongly convex functions
[10, Theorem 5.1], we have

$\langle z,w\rangle\geq\kappa\|w\|^{2}\quad\text{for all
}\;z\in\partial^{2}\varphi(x,y)(w),\;(x,y)\in\mbox{\rm
gph}\,\partial\varphi,\;\mbox{and }\;w\in{\rm I\\!R}^{n}.$

This implies in turn that $\bar{x}$ is a tilt-stable local minimizer with
modulus $\kappa^{-1}$ by second-order characterization of tilt stability taken
from [61, Theorem 3.5].

## Funding and Conflicts of Interests

Research of Pham Duy Khanh is funded by the Ministry of Education and Training
Research Funding under grant B2023-SPS-02. Research of Boris S. Mordukhovich
was partly supported by the US National Science Foundation under grants
DMS-1808978 and DMS-2204519, by the US Air Force Office of Scientific Research
under grant #15RT0462, and by the Australian Research Council under Discovery
Project DP-190100555. Research of Vo Thanh Phat was partly supported by the US
National Science Foundation under grants DMS-1808978 and DMS-2204519, and by
the US Air Force Office of Scientific Research under grant #15RT0462. Research
of Dat Ba Tran was partly supported by the US National Science Foundation
under grant DMS-1808978 and DMS-2204519. The authors declare that the
presented results are new, and there is no any conflict of interest.

## Acknowledgements

The authors are very grateful to three anonymous referees for their helpful
remarks and suggestions, which allowed us to significantly improve the
original presentation.

## 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.: 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] Bertsekas, D.P.: Nonlinear Programming, 3rd edition. Athena Scientific, Belmont, MA (2016)
  * [7] Bonnans, J.F.: Local analysis of Newton-type methods for variational inequalities and nonlinear programming. Appl. Math. Optim. 29, 161–186 (1994)
  * [8] 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)
  * [9] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge, UK (2004)
  * [10] 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)
  * [11] 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)
  * [12] 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)
  * [13] 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)
  * [14] 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)
  * [15] Dan, H., Yamashita, N., Fukushima, M.: Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions. Optim. Meth. Softw. 17, 605–626 (2002)
  * [16] Dennis, J.E., Moré, J.J.: Quasi-Newton methods, motivation and theory. SIAM Rev. 19, 46–89 (1977)
  * [17] 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)
  * [18] Dias, S., Smirnov, G.: On the Newton method for set-valued maps. Nonlinear Anal. TMA, 75, 1219–1230 (2012)
  * [19] Dontchev, A.L., Rockafellar, R.T.: Characterizations of strong regularity for variational inequalities over polyhedral convex sets. SIAM J. Optim. 6, 1087–1105 (1996)
  * [20] Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings: A View from Variational Analysis, 2nd edition. Springer, New York (2014)
  * [21] Drusvyatskiy, D., Lewis, A.S.: Tilt stability, uniform quadratic growth, and strong metric regularity of the subdifferential. SIAM J. Optim. 23, 256–267 (2013)
  * [22] 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)
  * [23] Emich, K., Henrion, R.: A simple formula for the second-order subdifferential of maximum functions. Vietnam J. Math. 42, 467–478 (2014)
  * [24] Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Statist. 32, 407–499 (2004)
  * [25] Facchinei, F.: Minimization of SC1 functions and the Maratos effect. Oper. Res. Lett. 17, 131–137 (1995)
  * [26] Facchinei, F., Pang, J.-C.: Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. II. Springer, New York (2003)
  * [27] Friedlander, M.P., Goodwin, A., Hoheisel, T: From perspective maps to epigraphical projections. Math. Oper. Res. (2022). https://doi.org/10.1287/moor.2022.1317
  * [28] 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)
  * [29] Glowinski, R., Marroco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problémes de Dirichlet non linéares. Revue Francaise d’Automatique, Informatique et Recherche Operationelle 9, 41–76 (1975)
  * [30] Gfrerer, H.: On directional metric regularity, subregularity and optimality conditions for nonsmooth mathematical programs. Set-Valued Var. Anal. 21, 151–176 (2013)
  * [31] Gfrerer, H., Mordukhovich, B.S.: Complete characterization of tilt stability in nonlinear programming under weakest qualification conditions. SIAM J. Optim. 25, 2081–2119 (2015)
  * [32] Gfrerer, H., Outrata, J.V.: On a semismooth∗ Newton method for solving generalized equations. SIAM J. Optim. 31, 489–517 (2021)
  * [33] Ginchev, I., Mordukhovich, B.S.: On directionally dependent subdifferentials. C. R. Acad. Bulg. Sci. 64, 497–508 (2011)
  * [34] 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)
  * [35] 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)
  * [36] Henrion, R., Römisch, W.: On $M$-stationary points for a stochastic equilibrium problem under equilibrium constraints in electricity spot market modeling. Appl. Math. 52, 473–494 (2007)
  * [37] Henrion, R., Outrata, J., Surowiec, T.: On the co-derivative of normal cone mappings to inequality systems. Nonlinear Anal. 71, 1213–1226 (2009)
  * [38] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)
  * [39] Hintermüller, M., Ito, K., Kunisch, K.: The primal-dual active set strategy as a semismooth Newton method, SIAM J. Optim. 13, 865–888 (2002)
  * [40] Hiriart-Urruty, J.-B., Strodiot, J.-J., Nguyen, V.H.: Generalized Hessian matrix and second-order optimality conditions for problems with $\mathcal{C}^{1,1}$ data. Appl. Math. Optim. 11, 43–56 (1984)
  * [41] Ho, C. H., Lin, C. J.: Large-scale linear support vector regression. J. Machine Learning Res. 13, 3323–3348 (2012)
  * [42] Hoheisel, T., Kanzow, C., Mordukhovich, B.S., Phan, H.M.: Generalized Newton’s methods for nonsmooth equations based on graphical derivatives, Nonlinear Anal. 75, 1324–1340 (2012); Erratum in Nonlinear Anal. 86, 157–158 (2013)
  * [43] 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)
  * [44] Izmailov, A.F., Solodov, M.V.: Newton-Type Methods for Optimization and Variational Problems. Springer, New York (2014)
  * [45] Izmailov, A.F., Solodov, M.V., Uskov, E.T.: Globalizing stabilized sequential quadratic programming method by smooth primal-dual exact penalty function. J. Optim. Theor. Appl. 169, 1–31 (2016)
  * [46] Khanh, P.D., Mordukhovich, B.S., Phat, V.T.: A generalized Newton method for subgradient systems. Math. Oper. Res. DOI: 10.1287/moor.2022.1320 (2022)
  * [47] Klatte, D., Kummer, B.: Nonsmooth Equations in Optimization. Regularity, Calculus, Methods and Applications. Kluwer Academic Publishers, Dordrecht, The Netherlands (2002)
  * [48] Kummer, B.: Newton’s method for non-differentiable functions. In: Guddat et al. (eds) Advances in Mathematical Optimization, pp. 114–124. Akademie-Verlag, Berlin (1988)
  * [49] Lee, J.D., Sun, Y., Saunders, M.A.: Proximal Newton-type methods for minimizing composite functions. SIAM J. Optim. 24, 1420–1443 (2014)
  * [50] Li, D. H., Fukushima, M., Qi, L., Yamashita, N.: Regularized Newton methods for convex minimization problems with singular solutions. Comput. Optim. Appl. 28, 131–147 (2004)
  * [51] 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)
  * [52] Lions, P.-L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)
  * [53] Meng, F., Sun, D., Zhao Z.: Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization. Math. Program. 104, 561–581 (2005)
  * [54] Mohammadi, A., Mordukhovich, B.S., Sarabi, M.E.: Variational analysis of composite models with applications to continuous optimization. Math. Oper. Res. 47, 397–426 (2022)
  * [55] Mohammadi, A., Mordukhovich, B.S., Sarabi, M.E.: Parabolic regularity in geometric variational analysis. Trans. Amer. Math. Soc. 374, 1711–1763 (2021)
  * [56] 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)
  * [57] 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)
  * [58] Mordukhovich, B.S.: Complete characterizations of openness, metric regularity, and Lipschitzian properties of multifunctions. Trans. Amer. Math. Soc. 340, 1–35 (1993)
  * [59] Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications. Springer, Berlin (2006)
  * [60] Mordukhovich, B.S.: Variational Analysis and Applications. Springer, Cham, Switzerland (2018)
  * [61] Mordukhovich, B.S., Nghia, T.T.A.: Second-order characterizations of tilt stability with applications to nonlinear programming. Math. Program. 149, 83–104 (2015)
  * [62] Mordukhovich, B.S., Nghia, T.T.A.: Local monotonicity and full stability of parametric variational systems. SIAM J. Optim. 26, 1032–1059 (2016)
  * [63] Mordukhovich, B.S., Outrata, J.V.: On second-order subdifferentials and their applications. SIAM J. Optim. 12, 139–169 (2001)
  * [64] Mordukhovich, B.S., Outrata, J.V., Sarabi, M.E.: Full stability of local optimal solutions in second-order cone programming. SIAM J. Optim. 14, 1581–1613 (2014)
  * [65] Mordukhovich, B.S., Rockafellar, R.T.: Second-order subdifferential calculus with applications to tilt stability in optimization. SIAM J. Optim. 22, 953–986 (2012)
  * [66] Mordukhovich, B.S., Rockafellar, R.T., Sarabi, M.E.: Characterizations of full stability in constrained optimization. SIAM J. Optim. 23, 1810–1849 (2013)
  * [67] Mordukhovich, B.S., Sarabi, M.E.: Generalized differentiation of piecewise linear functions in second-order variational analysis. Nonlinear Anal. 132, 240–273 (2016)
  * [68] Mordukhovich, B.S., Sarabi, M.E.: Generalized Newton algorithms for tilt-stable minimizers in nonsmooth optimization. SIAM J. Optim. 31, 1184–1214 (2021)
  * [69] Mordukhovich, B.S., Yuan, X., Zheng, S., Zhang. J.: A globally convergent proximal Newton-type method in nonsmooth convex optimization. Math. Program. 198, 899–936 (2023)
  * [70] Nam, N.M.: Coderivatives of normal cone mappings and Lipschitzian stability of parametric variational inequalities. Nonlinear Anal. 73, 2271–2282 (2010)
  * [71] Nesterov, Yu.: Lectures on Convex Optimization, 2nd edition. Springer, Cham, Switzerland (2018)
  * [72] Nocedal, J., Wright, S.: Numerical Optimization. Springer, New York (2006)
  * [73] Outrata, J.V.; Sun, D.: On the coderivative of the projection operator onto the second-order cone. Set-Valued Anal. 16 (999-1014 (2008)
  * [74] Pang, J.S.: Newton’s method for B-differentiable equations. Math. Oper. Res. 15, 311–341 (1990)
  * [75] Pang, J.S., Qi, L.: A globally convergent Newton method for convex SC1 minimization problems. J. Optim. Theory Appl. 85, 633–648 (1995)
  * [76] Patrinos, P., Bemporad, A.: Proximal Newton methods for convex composite optimization. In: IEEE Conference on Decision and Control, 2358–2363 (2013)
  * [77] Patrinos, P., Stella, L., Bemporad, A..: Forward–backward truncated Newton methods for convex composite optimization. http://arxiv.org/abs/1402.6655, 02 (2014)
  * [78] 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)
  * [79] Poliquin, R.A., Rockafellar, R.T.: Tilt stability of a local minimum. SIAM J. Optim. 8, 287–299 (1998)
  * [80] Polyak, B.T.: Introduction to Optimization. Optimization Software, New York (1987)
  * [81] 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)
  * [82] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18, 227–244 (1993)
  * [83] Qi, L., Sun, J.: A nonsmooth version of Newton’s method. Math. Program. 58, 353–367 (1993)
  * [84] Qui, N.T.: Generalized differentiation of a class of normal cone operators, J. Optim. Theory Appl. 161, 398–429 (2014)
  * [85] Robinson, S.M.: Newton’s method for a class of nonsmooth functions. Set-Valued Anal. 2, 291–305 (1994)
  * [86] Rockafellar, R.T.: Augmented Lagrangian multiplier functions and duality in nonconvex programming. SIAM J. Control 12, 268–285 (1974)
  * [87] Rockafellar, R.T.: Augmented Lagrangians and hidden convexity in sufficient conditions for local optimality. Math. Program. 198, 159–194 (2023)
  * [88] Rockafellar, R.T., Wets R.J-B.: Variational Analysis. Springer, Berlin (1998)
  * [89] She, Y.: Sparse regression with exact clustering. Elect. J. Stat. 4, 1055–1096 (2010)
  * [90] Stella, L., Themelis, A., Patrinos, P.: Forward–backward quasi-Newton methods for nonsmooth optimization problems. Comput. Optim. Appl. 67, 443–487 (2017)
  * [91] Stella, L., Themelis, A., Patrinos, P.: Forward-backward envelope for the sum of two nonconvex functions: further properties and nonmonotone linesearch algorithms. SIAM J. Optim. 28, 2274–2303 (2018)
  * [92] Tibshirani, R.: Regression shrinkage and selection via the Lasso. J. R. Stat. Soc. 58, 267–288 (1996)
  * [93] Ulbrich, M.: Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces. SIAM, Philadelphia, PA (2011)
  * [94] Yamashita, N., Fukushima, M.: On the rate of convergence of the Levenberg-Marquardt method. In: G. Alefeld, X. Chen (eds) Topics in Numerical Analysis. 15, 239–249. Springer, Vienna (2001)
  * [95] 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)