remarkRemark hypothesisHypothesis claimClaim Composite nonsmooth
optimizationG. Bareilles, F. Iutzeler, and J. Malick

# Harnessing structure
in composite nonsmooth minimization††thanks: Submitted to the editors June 27,
2022.

Gilles Bareilles Univ. Grenoble Alpes, LJK, France (, ).
<EMAIL_ADDRESS><EMAIL_ADDRESS>Franck Iutzeler22footnotemark: 2 Jérôme Malick Univ. Grenoble Alpes, CNRS,
Grenoble INP, LJK<EMAIL_ADDRESS>
###### Abstract

We consider the problem of minimizing the composition of a nonsmooth function
with a smooth mapping in the case where the proximity operator of the
nonsmooth function can be explicitly computed. We first show that this
proximity operator can provide the exact smooth substructure of minimizers,
not only of the nonsmooth function, but also of the full composite function.
We then exploit this proximal identification by proposing an algorithm which
combines proximal steps with sequential quadratic programming steps. We show
that our method locally identifies the optimal smooth substructure and then
converges quadratically. We illustrate its behavior on two problems: the
minimization of a maximum of quadratic functions and the minimization of the
maximal eigenvalue of a parametrized matrix.

###### keywords:

Nonsmooth optimization, proximal operator, partial smoothness, manifold
identification, maximum eigenvalue minimization, sequential quadratic
programming.

65K10, 90C26, 49Q12, 90C55.

##  1 Introduction

###  1.1 Context: structured nonsmooth optimization

In this paper, we consider nonsmooth optimization problems of the form

(1) $\displaystyle\min_{x\in\mathbb{R}^{n}}~{}F(x)\;\triangleq\;g(c(x)),$

where the inner mapping $c:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is smooth and the
outer function $g:\mathbb{R}^{m}\to\mathbb{R}\cup\\{+\infty\\}$ is nonsmooth
and may be nonconvex, but admits an explicit proximity operator. Such
composite nonsmooth optimization problems appear in a variety of applications
in signal processing, machine learning, and control, such as robust nonlinear
regression, phase synchronization, nonsmooth penalty functions; see _e.g._
[21, 31] and the references therein.

Throughout the paper, we illustrate our developments on two classes of
functions: the pointwise maximum of $m$ smooth real-valued functions $c_{i}$

(2) $\displaystyle F(x)=\\!\\!\max_{i=1,\ldots,m}(c_{i}(x))$

and the maximum eigenvalue of a parametrized symmetric real matrix $c$

(3) $\displaystyle F(x)=\lambda_{\max{}}(c(x)).$

In these two examples and many others, subgradients of $F$ can be computed and
thus the composite function can be minimized using standard nonsmooth
optimization algorithms (_e.g._ subgradient methods, gradient sampling [7],
nonsmooth BFGS [20], or bundle methods [14]). Nevertheless, these methods do
not exploit the fact that $F$ is a composition of a smooth mapping $c$, which
can hinder their performance. In contrast, the so-called prox-linear methods
leverage this composite expression by introducing an extension of the
proximity operator where the nonlinear mapping $c$ is iteratively replaced by
a first-order Taylor approximation [21]. These methods benefit from
theoretical convergence guarantees, and nicely generalize to Taylor-like
approximations [9, 3]. However these methods are not always directly
implementable because the prox-linear step may be hard to compute, as in (3).

In this paper, we propose an optimization algorithm for solving (1) exploiting
that the nonsmooth objective function $F=g\circ c$ writes as a composition
between a smooth mapping $c$ and a simple nonsmooth function $g$ which
displays some smooth substructure, as discussed below.

###  1.2 Smooth substructure, identification, and existing algorithms

For many composite functions, including (2) and (3), the nondifferentiability
points _locally_ organize into _smooth manifolds over which $F$ evolves
smoothly_. We illustrate in Figure 1 such a smooth substructure for a maximum
of two functions.

(a) Level curves of $F$

(b) Level curves of $g$ and image of $c$

Figure 1:  Smooth substructure on a simple example $(n=m=2)$ with
$g(y)=\max(y_{1},y_{2})$ and
$c(x)=(2.6\,x_{1}^{2}+4\,(x_{2}-1)^{2}-4,x_{1}^{2}+4\,(x_{2}+1)^{2}-4)$. The
right-hand figure shows the level curves of $g$ (in the intermediate space),
and the left-hand figure shows the ones of $F$ (in the input space). The
manifolds of non-differentiability of $F$ and $g$ are in green. The right
figure also displays the image of $c$ as the red area.

The smooth substructure of $F$ can help in solving (1). Indeed, if the optimal
solution ${x}^{\star}$ belongs to a manifold ${\mathcal{M}}^{\star}$ that is
known beforehand, then minimizing the nonsmooth function $F$ over
$\mathbb{R}^{n}$ boils down to minimizing the smooth restriction
$F|_{{\mathcal{M}}^{\star}}$ over this smooth _optimal manifold_
${\mathcal{M}}^{\star}$. This would enable to solve (1) by smooth constrained
optimization algorithms, such as Sequential Quadratic Programming (SQP)
methods (see _e.g._ [25, 5]).111 Note that ${\mathcal{M}}^{\star}$ is an
arbitrary manifold and thus computing a feasible point is already a difficult
task in general. That is why we consider in this paper infeasible methods,
such as SQP, instead of feasible ones, like the Riemannian Newton algorithm.
The main difficulty in practice is that _we do not know
${\mathcal{M}}^{\star}$ in advance_.

Thus, the algorithms exploiting this smooth substructure require two
ingredients:

  * i)

a mechanism to identify the optimal manifold;

  * ii)

an efficient method to minimize $F$ restricted to this manifold.

For general convex functions, the algorithm of [23] mixes a proximal bundle
iteration (as a heuristic for identification) and a so-called
$\mathcal{U}$-Newton iteration (which interprets as an SQP step; see [24, Sec.
5]). The obtained superlinear rate hinges on the identification of the optimal
manifold.

For max-of-smooth functions (2), the paper [33] pioneered the idea of seeking
the optimal manifold and using it to make second-order steps. Their
identification heuristic uses the indices of the maximal function along a
descent direction. Recently, [18, 10] investigate a related setting and
propose bundle-like algorithms incorporating high-order information that
converge (super)linearly on max-of-smooth functions when the optimal manifold
is known.

For the maximum eigenvalue of a parametrized matrix (3), a specific version of
the $\mathcal{U}$-Newton method discussed above is studied by [26]. Again, the
identification mechanism is a heuristic determining the multiplicity of the
maximal eigenvalue and the optimization step is an SQP iteration.

None of these methods guarantee identification of the optimal manifold: they
either assume that the optimal manifold is known in advance, or rely on
heuristics for identification. Here, we aim at further harnessing the smooth
substructure of $F=g\circ c$ to have _guaranteed local identification_ of the
optimal manifold and then _guaranteed quadratic convergence_ when using SQP
iterations.

###  1.3 Contributions and outline

We propose a local second-order algorithm for solving the nonsmooth composite
problem (1) that identifies the optimal manifold of non-differentiability. The
two main ingredients of our algorithm are the following:

  * i)

we use the explicit proximal operator of $g$ with chosen stepsizes to provide
a guaranteed identification procedure;

  * ii)

for a candidate manifold $\mathcal{M}$, we make an SQP iteration minimizing a
smooth extension of $F|_{\mathcal{M}}$ subject to the constraint of belonging
to $\mathcal{M}$.

The fact that proximal-based operators have identification properties around
minimizers is well-known: the proximal operator [11, 8], the proximal gradient
operator [1], approximate variable-metric proximal gradient operators [15],
and prox-linear operators [21] locally identify the optimal manifold under
some natural geometrical assumptions. Here, we only have access to the
proximity operator of $g$, and in order to exploit the structure it provides,
we face the double challenge of, first, identifying the smooth structure
around a point which is not a minimizer for $g$, and, second, deducing the
corresponding structure of $F=g\circ c$. Thus, our main technical contribution
is to establish that $\mathbf{prox}_{\gamma g}$ maps a point $y$ close to
$c({x}^{\star})$ to $c({\mathcal{M}}^{\star})$. The step $\gamma$ should be
carefully chosen, in particular larger than the distance of $y$ to
$c({x}^{\star})$. Mathematically, we study the range of steps for which the
curve $\gamma\mapsto\mathbf{prox}_{\gamma g}(y)$ belongs to
$c({\mathcal{M}}^{\star})$. This analysis shows connections with recent works
in nonsmooth analysis, such as the modulus of identifiability appearing in
[17].

We combine this new identification result with standard SQP-steps to propose a
local algorithm for minimizing the composite function $F$. We pay a special
attention to prevent the quadratic convergence of SQP from jeopardizing
identification: we prove that, for a well-chosen stepsize policy, the method
identifies the optimal structure and converges quadratically. We illustrate
numerically these properties on problems of the form (2) and (3).

The outline of the remainder of the paper is as follows. First, in Section 2,
we introduce the technical tools to describe the manifold identification
brought by proximity operators (including prox-regularity and partial
smoothness). Furthermore, we lay out two technical properties needed for
proximal identification in the composite setting. In Section 3, we show our
main result consisting in a description of a stepsize range for which the
proximity operator of $g$ identifies the optimal manifold locally around a
minimizer. In Section 4 we detail the proposed method combining SQP-steps and
proximal identification steps. Finally, we present in Section 5 numerical
illustrations of our method and of the identification result.

###  1.4 Notations

Given a point $z$ in $\mathbb{R}^{p}$, we denote by $\mathcal{N}_{z}$ a
neighborhood of $z$ in $\mathbb{R}^{p}$. We reserve the names based on $x$ for
points in the input space $\mathbb{R}^{n}$, and on $y$ for points in the
intermediate space $\mathbb{R}^{m}$. We denote the differential of a smooth
mapping $c$ at point $x$ by $\operatorname{D}c(x)$, and its Jacobian matrix by
$\operatorname{Jac}_{c}(x)$. The conjugate of the linear operator $A$ is
denoted by $A^{*}$. The minimizer is denoted by ${x}^{\star}$.

##  2 Setting and assumptions

Let us start by representing schematically the type of functions we consider:

(4) $\displaystyle\mathbb{R}^{n}\xrightarrow[\text{smooth
mapping}]{c}\mathrm{Im}(c)\subset\mathbb{R}^{m}\xrightarrow[\text{nonsmooth
function}]{g}\mathbb{R}\cup\\{+\infty\\}.$

Throughout the paper, we denote by $x$ points in the _input space_
$\mathbb{R}^{n}$ and by $y$ points in the _intermediate space_
$\mathbb{R}^{m}$.

In all the results presented in this paper, we make the following assumption
that describes the minimal global properties on $g$ and $c$ to conduct our
reasoning.

######  Assumption .

The mapping $c:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is $\mathcal{C}^{2}$, the
function $g:\mathbb{R}^{m}\to\mathbb{R}\cup\\{+\infty\\}$ is proper and lower
semi-continuous.

We work with the set of _(general) subgradients_ (see [29, Def. 8.3]), defined
at a point $\bar{y}$ where $g(\bar{y})$ is finite as:

(5) $\displaystyle\partial
g(\bar{y})\triangleq\left\\{\lim_{r}v_{r}:v_{r}\in\widehat{\partial}g(y_{r}),y_{r}\to\bar{y},g(y_{r})\to
g(\bar{y})\right\\},$

where $\widehat{\partial}g(\bar{y})$ denotes the set of _regular (or Fréchet)
subgradients_ , defined as

(6) $\displaystyle\widehat{\partial}g(\bar{y})\triangleq\left\\{v:g(y)\geq
g(\bar{y})+\langle v,y-\bar{y}\rangle+o(\|y-\bar{y}\|)\text{ for all
}y\in\mathbb{R}^{m}\right\\}.$

These two subdifferentials match if (and only if) $g$ is (Clarke) regular at
$\bar{y}$. Closed convex functions are regular everywhere and these
subdifferentials match the usual convex subdifferential (see [29, Chap.
8.11-12] for details).

In the remainder of this section, we provide quick recalls and definitions
about the two important objects of our analysis: the proximity operator in
Section 2.1 and the structure manifolds in Section 2.2. We illustrate them on
our running examples (2) and (3).

###  2.1 Proximity operator

The proximity operator of a function $g$ with step $\gamma>0$ at
$y\in\mathbb{R}^{m}$ is defined as the set-valued mapping

(7) $\displaystyle\mathbf{prox}_{\gamma
g}(y)\triangleq\operatorname{argmin}_{u\in\mathbb{R}^{m}}\left\\{g(u)+\frac{1}{2\gamma}\|u-y\|^{2}\right\\}.$

This operator is well-defined when $g$ is prox-regular and prox-bounded; see
_e.g._ [29, 13.37]. We quickly introduce these two notions and recall a result
on the uniqueness and characterization of the prox operator, which is
important in our developments.

A function $g$ is _prox-regular_ at a point $\bar{y}$ for a subgradient
$\bar{v}\in\partial g(\bar{y})$ if $g$ is finite, locally lower semi-
continuous at $\bar{y}$, and there exists $r>0$ and $\epsilon>0$ such that

(8) $\displaystyle g(y^{\prime})\geq g(y)+\langle
v,y^{\prime}-y\rangle-\frac{r}{2}\|y^{\prime}-y\|^{2}$

whenever $v\in\partial g(y)$, $\|y-\bar{y}\|<\epsilon$,
$\|y^{\prime}-\bar{y}\|<\epsilon$, $\|v-\bar{v}\|<\epsilon$, and
$g(y)<g(\bar{y})+\epsilon$. When this holds for all $\bar{v}\in\partial
g(\bar{y})$, we say that $g$ is prox-regular at $\bar{y}$ [29, Def. 13.27].

A function $g$ is _prox-bounded_ if there exists $R\geq 0$ such that the
function $g+\frac{R}{2}\|\cdot\|^{2}$ is bounded below. The corresponding
_threshold_ (of prox-boundedness) is the smallest $r_{pb}\geq 0$ such that
$g+\frac{R}{2}\|\cdot\|^{2}$ is bounded below for all $R>r_{pb}$. In this
case, $g+\frac{R}{2}\|\cdot-\bar{y}\|^{2}$ is bounded below for any $\bar{y}$
and $R>r_{pb}$ [29, Def. 1.23, Th. 1.25].

We can now recall a relevant result on the characterization of proximal
points.

######  Proposition 2.1 ([12, Th. 1]).

Suppose that the function $g$ is prox-regular at for $\bar{v}\in\partial g($
with parameter $r_{pr}$, and prox-bounded with threshold $r_{pb}$. Then, for
any and all $y$ near , the proximal operator is:

  * •

single-valued and locally Lipschitz continuous;

  * •

uniquely determined by the relation

(9) $\displaystyle p=\mathbf{prox}(y)\Leftrightarrow y-p\in$

In addition to its existence and characterization provided by the result
above, the proximity operator has a closed-form expression in our running
examples.

######  Example 2.6 (Maximum).

The subdifferential of $g(y)=\max(y_{1},\ldots,y_{m})$ is

(10)
$\displaystyle\partial\max(y)=\operatorname{Conv}\left\\{e_{i}:y_{i}=\max(y)\right\\},$

where $e_{i}$ is the $i$-th element of the Cartesian basis of
$\mathbb{R}^{m}$. The $\max$ function is convex, thus globally prox-regular
and prox-bounded everywhere (with parameters $0$). Its proximity operator is
given (coordinate-wise) by

(11) $\displaystyle\left[\mathbf{prox}(y)\right]_{i}=\begin{cases}s&\text{if
}y_{i}>s\\\ y_{i}&\text{else}\end{cases}$

where $s$ is the unique real number such that
$\sum_{\\{i:y_{i}>s\\}}(y_{i}-s)=$.

######  Example 2.9 (Maximum eigenvalue).

Denote the eigenvalue decomposition of a point $y\in\mathbb{S}_{m}$ as
$y=E\operatorname{Diag}(\lambda)E^{\top}$, where $\lambda\in\mathbb{R}^{m}$ is
a vector with decreasing entries and $E\in\mathbb{R}^{m\times m}$ an
orthogonal matrix. The subdifferential of the maximum eigenvalue at $y$ writes
[19, Ex. 3.6]

(12)
$\displaystyle\partial\lambda_{\max{}}(y)=\\{E_{1:r}ZE_{1:r}^{\top},Z\in\mathbb{S}_{r},Z\succeq
0,\operatorname{trace}Z=1\\}$

where $r$ is the multiplicity of the maximum eigenvalue of $y$. The
$\lambda_{\max{}}$ function is convex, thus prox-regular and prox-bounded
(with parameters $0$). Its proximity operator can be expressed using the one
of the $\max$ function as

(13)
$\displaystyle\mathbf{prox}(y)=E\operatorname{Diag}(\mathbf{prox}(\lambda))E^{\top}.$

###  2.2 Structure manifolds

We now specify the notion of structure manifold in relation with a nonsmooth
function $g$.

A subset $\mathcal{M}$ of $\mathbb{R}^{n}$ is said to be a _$p$ -dimensional
$\mathcal{C}^{2}$-submanifold_ of $\mathbb{R}^{n}$ around if there exists a
$\mathcal{C}^{2}$ _manifold-defining map_
$h:\mathbb{R}^{n}\to\mathbb{R}^{n-p}$ with a surjective derivative at that
satisfies for all $x$ close enough to : $x\in\mathcal{M}\Leftrightarrow
h(x)=0$. We define the tangent and normal spaces at a point $x\in\mathcal{M}$
as follows:

(14) $\displaystyle T_{x}\mathcal{M}=\ker\operatorname{D}h(x)\qquad
N_{x}\mathcal{M}=\mathrm{Im}\;\operatorname{D}h(x)^{*}$

The important notion of _structure manifolds of $g$_ can be defined as a
manifold $\mathcal{M}^{g}$ where $g$ is nondifferentiable. More precisely, at
a point , we require $g$ to be prox-regular and _partly smooth_. This property
of ($\mathcal{C}^{2}$-)partial smoothness is verified at a point for a
function $g$ relatively to a set $\mathcal{M}^{g}$ containing if
$\mathcal{M}^{g}$ is a $\mathcal{C}^{2}$ manifold around and if

  * •

(smoothness) the restriction of $g$ to $\mathcal{M}^{g}$ is a
$\mathcal{C}^{2}$ function near ;

  * •

(regularity) $g$ is (Clarke) regular at all points $y\in\mathcal{M}^{g}$ near
, with $\partial g(y)\neq\emptyset$;

  * •

(sharpness) the affine span of $\partial g($ is a translate of
$N\mathcal{M}^{g}$;

  * •

(sub-continuity) the mapping $\partial g$ restricted to $\mathcal{M}^{g}$ is
continuous at .

The concept of partial smoothness, introduced in [19], captures (locally)
well-behaved nonsmoothness by requiring $g$ to be smooth along a manifold and
non-smooth across it. In addition, the prox-regularity of $g$ ensures
uniqueness of the structure manifold near [11, Corollary 4.2, Example 7.1]. To
highlight the relation between the manifold and the function $g$, we use the
notation $\mathcal{M}^{g}$ for the structure manifold related to $g$.

######  Example 2.12.

The structure manifolds of $\max$ are

(15)
$\displaystyle\mathcal{M}^{\max}_{I}=\\{y\in\mathbb{R}^{m}:y_{i}=\max(y)\text{
for }i\in I\\},$

where $I\subset\\{1,\ldots,m\\}$. A smooth manifold-defining map for
$\mathcal{M}^{\max}_{I}$ is $h:\mathbb{R}^{m}\to\mathbb{R}^{|I|-1}$ such that
$h(y)_{l}=y_{i_{l}}-y_{i_{|I|}}$, where $|I|$ denotes the size of $I$ and
$i_{l}$ the $l$-th element of $I$ (with some ordering). As required, this map
is surjective. At any point $y\in\mathbb{R}^{m}$, the maximum is partly smooth
relative to $\mathcal{M}^{\max}_{I}$, where $I=\\{i:y_{i}=\max(y)\\}$.

######  Example 2.13.

The structure manifolds of $\lambda_{\max{}}$ in $\mathbb{S}_{m}$ consist of
all matrices having a largest eigenvalue with fixed multiplicity $r$:

(16)
$\displaystyle\mathcal{M}^{\lambda_{\max}}_{r}=\\{y\in\mathbb{S}_{m}:\lambda_{1}(y)=\dots=\lambda_{r}(y)\\}.$

A manifold-defining map of $\mathcal{M}^{\lambda_{\max}}_{r}$ is described in
[32] and $\lambda_{\max{}}$ is partly smooth relative to
$\mathcal{M}^{\lambda_{\max}}_{r}$ at any point
$y\in\mathcal{M}^{\lambda_{\max}}_{r}$.

In view of the expression of the proximity operators in our examples, their
output naturally lie on the structure manifolds described above. More
precisely, $\mathbf{prox}(y)$ belongs to the structure manifold
$\mathcal{M}^{\max}_{I}$, where $I$ collects the indices of the $k$ largest
entries of $y$ and $k$ grows as increases. Similarly, $\mathbf{prox}(y)$
belongs to the structure manifold $\mathcal{M}^{\lambda_{\max}}_{r}$, where
$r$ increases as does. This observation is at the core of the ability of
proximal operators to identify neighboring structure manifolds.

###  2.3 Structure Identification

It is well-known that the proximity operator identifies structure locally
around critical points (see _e.g._ [8, Th. 28]): all points near a minimizer
are mapped to the manifold containing the minimizer. Furthermore, this
structure is revealed during the computation of the operator.222Computing
exactly the _structure_ of the output point of the operator, as can be done
for the prox, is opposed to merely observing the structure of the output after
its computation. This last option is not desirable in our opinion as it
entails delicate numerical questions such as testing equality between reals
for the maximum, or computing the multiplicity of the maximal eigenvalue of a
matrix.

In the situation we consider, the proximity operator of $F$ cannot be
explicitly computed. However, $\mathbf{prox}$ is available and can provide
some structure in the intermediate space $\mathbb{R}^{m}$ that we would like
to exploit. To do so, we introduce two properties (holding on our two running
examples), that will allow us to retrieve the structural information in the
intermediate space near points that are not minimizers of $g$.

The first property holds at point if the nonsmooth function $g$ strictly
increases on all directions on which it is nonsmooth.

######  Property 2.19 (Normal ascent).

A function $g$ satisfies the _normal ascent_ property at point if $0$ lies in
the relative interior of the projection of $\partial g($ on the normal space
at , that is:
$0\in\operatorname{ri}\operatorname{proj}_{N\mathcal{M}^{g}}\partial g($.

######  Remark 2.20 (Positive directional derivative).

In a “nice” setting where $g$ is Lipschitz continuous and regular at ,
Property 2.19 implies that the directional derivative of $g$ along any normal
direction $d\in N\mathcal{M}^{g}$ is positive. Indeed, in that case one-sided
directional derivatives are well-defined [29, p. 358, Th. 9.16], and the
derivative along direction $w$ equals $\max_{v\in\partial
g(\crit[\vxinter])}\langle v,w\rangle$. Along a normal direction $d\in
N\mathcal{M}^{g}$, by partial smoothness the directional derivative writes
$\max_{v_{n}\in\operatorname{proj}_{N\mathcal{M}^{g}}(\partial
g(\crit[\vxinter]))}\langle v_{n},d\rangle$. Property 2.19 ensures the
existence of $\alpha>0$ such that $\alpha
d\in\operatorname{proj}_{N\mathcal{M}^{g}}(\partial g($, making the derivative
positive.

Let us briefly discuss that, even if Property 2.19 may look strong, in
practice it is not. For a given nonsmooth function $F$ which can be decomposed
as $F=g\circ c$, Property 2.19 may not hold for $g$ at $c({x}^{\star})$ for a
minimizer ${x}^{\star}$. Nevertheless, the property often holds for a
different decomposition $F=\tilde{g}\circ\tilde{c}$. We give two examples
where changing the decomposition of $F$ ensures that Property 2.19 holds at
minimizers.

######  Example 2.21 (Normal ascent for regularized-type problem).

Consider the minimization of $F(x)=f(x)+r(x)$, where $f(x)=\frac{3}{2}x$ and
$r(x)=|x|-\frac{1}{2}x$, whose minimizer is ${x}^{\star}=0$. This writes as a
composite problem by setting $c(x)=(f(x),x)$ and $g(y)=y_{1}+r(y_{2})$. We
note first that Property 2.19 does not hold for $g$ at $c({x}^{\star})$, the
structure manifold of $g$ at $c({x}^{\star})$ being
$\mathcal{M}^{g}=\mathbb{R}\times\\{0\\}$. However the function also writes
$F(x)=\tilde{f}(x)+\tilde{r}(x)$, with $\tilde{f}(x)=x$ and
$\tilde{r}(x)=|x|$. Letting similarly $\tilde{c}(x)=(\tilde{f}(x),x)$ and
$\tilde{g}(y)=y_{1}+\tilde{r}(y_{2})$, we now get that Property 2.19 holds for
$\tilde{g}$ at $\tilde{c}({x}^{\star})$.

Figure 2:  Illustration of the level-curves of function $g$ in Example 2.22,
along with the image of $c$ and the tangent and normal spaces to
$\mathcal{M}^{g}$ at the minimizer.

######  Example 2.22 (Normal ascent property for composite problems).

Consider the minimization of $F=g\circ c$, with

(17) $\displaystyle g(y)=\begin{cases}y_{1}+y_{2}&\text{if }y_{1}>0\\\
y_{1}+0.25\,y_{2}&\text{else}\end{cases},\qquad c(x)=\begin{pmatrix}2-x\\\
2x\end{pmatrix}.$

The minimizer is ${x}^{\star}=0$, since $g$ is strictly increasing at all
$y\in\mathrm{Im}(c)$ near ${y}^{\star}=c({x}^{\star})$; see Fig. 2. However
the normal ascent property does not hold at ${x}^{\star}$: $g$ is decreasing
at ${y}^{\star}$ along the normal direction $(0;-1)$.

The composite function boils down to
$F(x)=2+\max(x,-0.5x)=\tilde{g}\circ\tilde{c}(x)$, where
$\tilde{g}(y)=2+\max(y)$ and $\tilde{c}(x)=(x,-0.5x)$. With this
decomposition, $\tilde{g}$ does satisfy the normal ascent property at
${x}^{\star}$.

The second property is more technical and controls the velocity of a curve on
the manifold $\mathcal{M}^{g}$.

######  Property 2.23 (Curve property).

A function $g$ partly smooth at relative to $\mathcal{M}^{g}$ satisfies the
_curve property_ at when there exists a neighborhood $\mathcal{N}$ of and
$T>0$ such that any smooth application
$e:\mathcal{N}\times[0,T]\to\mathcal{M}^{g}$ such that
$e(y,0)=\operatorname{proj}_{\mathcal{M}^{g}}(y)$,
$\frac{\mathrm{d}}{\mathrm{d}t}e(y,t)|_{t=0}=-\operatorname{grad}g(\operatorname{proj}_{\mathcal{M}^{g}}(y))$
satisfies

(18)
$\displaystyle\|\operatorname{proj}_{N_{e(y,t)}\mathcal{M}^{g}}(e(y,t)-y)\|\leq\operatorname{dist}_{\mathcal{M}^{g}}(y)+\tilde{L}\;t^{2}\quad\text{
for all }y\in\mathcal{N},t\in[0,T],$

where
$\operatorname{dist}_{\mathcal{M}^{g}}(y)\triangleq\|y-\operatorname{proj}_{\mathcal{M}^{g}}(y)\|$
is the distance between $\mathcal{M}^{g}$ and $y$, and
$\operatorname{grad}g(p)\in T_{p}\mathcal{M}^{g}$ denotes the Riemannian
gradient of $g$ obtained as
$\operatorname{proj}_{T_{p}\mathcal{M}^{g}}(\partial g(p))$.

The idea behind this property is to ensure that the differential of the (time
dependent) projection on the normal space is (uniformly) negligible at time
$0$. Note that for affine spaces, we trivially have
$\|\operatorname{proj}_{N_{e(y,t)}\mathcal{M}^{g}}(y-e(y,t))\|=\operatorname{dist}_{\mathcal{M}^{g}}(y)$
for all $t$ near $0$: the normal spaces are equal at all points of the
manifold.

These two properties are satisfied at any structured point for the two
nonsmooth functions $\max$ and $\lambda_{\max{}}$ of our running examples as
detailed in the following lemma. The proofs for the two functions are rather
direct but require precise technical descriptions; we defer them to Appendix
A.

######  Lemma 2.24.

Consider either:

  * •

$g=\max$, , and the structure manifold $\mathcal{M}^{\max}_{I}$ (of Example
2.12);

  * •

$g=\lambda_{\max{}}$, , and the structure manifold
$\mathcal{M}^{\lambda_{\max}}_{r}$ (of Example 2.13).

Then, Properties 2.19 and 2.23 hold at .

Finally, the structure provided by $\mathbf{prox}$ lies in the intermediate
space $\mathbb{R}^{m}$, while the optimization variable lives in
$\mathbb{R}^{n}$. In order to transfer the structure information to the input
space, we will also require the smooth map $c:\mathbb{R}^{n}\to\mathbb{R}^{m}$
to be transversal to $\mathcal{M}^{g}\subset\mathbb{R}^{m}$ at some point ,
which holds when $\mathcal{M}^{g}$ is a manifold around $c($ and the following
(equivalent) conditions hold:

(19) $\displaystyle N_{c(\crit)}\mathcal{M}^{g}\cap\ker(\operatorname{D}c($

In that case, the set $c^{-1}(\mathcal{M}^{g})$ is a submanifold of
$\mathbb{R}^{n}$ [16, Th. 6.30], whose normal space has the same dimension as
the one of $\mathcal{M}^{g}$. Furthermore, we have [16, Ex. 6-10]

(20) $\displaystyle
N_{x}c^{-1}(\mathcal{M}^{g})=\operatorname{D}c(x)^{*}N_{c(x)}\mathcal{M}^{g}~{}\text{
and
}~{}T_{x}c^{-1}(\mathcal{M}^{g})=\operatorname{D}c(x)^{-1}T_{c(x)}\mathcal{M}^{g}.$

##  3 Collecting structure with the proximity operator

We show in this section how to exactly detect the optimal structure manifold
of the composite function $F=g\circ c$ around a point using the proximity
operator of $g$.

In our nonconvex and nonsmooth setting, we seek only structured points which
satisfy certain assumptions summarized in our definition of a _qualified
point_.

######  Definition 3.1 (Qualified points).

A point is _qualified_ relative to a decomposition $(g,c)$ of $F$ and manifold
$\mathcal{M}^{g}$ if

  1. i)

$g$ is prox-bounded and prox-regular at $c($;

  2. ii)

$g$ is partly smooth at $c($ relative to $\mathcal{M}^{g}$;

  3. iii)

$c$ is transversal to $\mathcal{M}^{g}$ at ;

  4. iv)

$g$ satisfies Properties 2.19 and 2.23 at point $c($.

Three of these assumptions constrain only the nonsmooth function $g$ and are
easily verifiable in practice. Only the transversality condition limits the
range of acceptable smooth mappings; see _e.g._ [19, Sec. 4]. For such
_qualified_ points, we get two useful properties: first, $F$ is partly smooth
at relative to the manifold $\mathcal{M}$, locally defined as
$\mathcal{M}\triangleq c^{-1}(\mathcal{M}^{g})\ni$ by the chain rule of [19,
Th. 4.2], and second, the operator $\mathbf{prox}$ is single-valued, locally
Lipschitz, and defined by its optimality condition near $c($.

###  3.1 Main result: $\mathbf{prox}\circ c$ as a structure detector

We show in the following theorem that if $x$ is near a qualified point of $F$
with structure $\mathcal{M}$, then $\mathbf{prox}(c(x))$ will output a point
on $\mathcal{M}^{g}=c(\mathcal{M})$, the structure manifold of $g$
corresponding to $\mathcal{M}$ (in the intermediate space). Our theorem
provides precise conditions on $x$ and that guarantee this structure
identification and forms the main theoretical contribution of the paper. We
illustrate this behavior in Figures 4 and 3.

The position of this result with respect to the literature is discussed right
after in Remark 3.14, and the proof is given in the following Section 3.2, in
a succession of technical lemmas. We stress that we give guarantees on the
_structure_ to which the point $\mathbf{prox}(c(x))$ belongs, rather than on
the point itself.

######  Theorem 3.8.

Consider a function $F=g\circ c$ and a point . Assume that is _qualified_
relative to a manifold $\mathcal{M}^{g}\subset\mathbb{R}^{m}$. Then, there
exists a neighborhood $\mathcal{N}$ of and a constant $\Gamma$ such that, for
all $x\in\mathcal{N}$,

(21) $\displaystyle\mathbf{prox}(c(x))\in\mathcal{M}^{g}\text{ for all }$

where $\operatorname{dist}_{\mathcal{M}}(x)$ denotes the distance from $x$ to
the manifold $\mathcal{M}$ and $\varphi$ is defined as

(22)
$\displaystyle\varphi(t)=\frac{c_{\text{ri}}}{2\tilde{L}}\left(1-\sqrt{1-\frac{4\tilde{L}c_{\text{map}}t}{c_{\text{ri}}^{2}}}\right)=\frac{c_{\text{map}}}{c_{\text{ri}}}t+\frac{\tilde{L}c_{\text{map}}^{2}}{c_{\text{ri}}^{3}}t^{2}+o(t^{2}),$

with $c_{\text{ri}}$, $c_{\text{map}}$, and $\tilde{L}$ (of Property 2.23)
positive constants.

In particular, there exists $L>0$, $\epsilon>0$ such that

(23) $\displaystyle\|x-{x}^{\star}\|\leq\epsilon\text{ and
}L\|x-{x}^{\star}\|\leq$

Note that Property 2.23 is only used to compute explicitly an interval of
guaranteed to provide the correct structure; the existence of that interval
holds independently.

######  Remark 3.14 (Relation with existing results).

The difference between Theorem 3.8 and existing results lies in two aspects.
First, the identification properties of the proximal operator [8, Th. 28], the
proximal-gradient operator [1, Th. 3.1], or even approximate prox-gradient
operators [15] give structure information directly in the input space (even in
abstract algorithmic frameworks [11, Th. 4] or [22, Th. 4.10]). In the
composite case, the proximity operator reveals structure in the intermediate
space only, and extra work is required to bring it back to the input space.

Second, most existing results investigate identification properties near
minimizers, and not just arbitrary points (two notable exceptions give results
near arbitrary structured points: [22] for an abstract algorithmic framework,
and [1] for the proximal gradient). Here, we evaluate $\mathbf{prox}$ near
$c($, a point without any specific properties (even if is a local minimizer).
This is why we need Property 2.19 to guarantee identification in the
intermediate space, and bring the structure information to the input space.

Figure 3:  Illustration of the main result in the intermediate space, on the
function of Fig. 4. The structure manifolds of
$\max:\mathbb{R}^{3}\to\mathbb{R}$ are displayed as the three half-planes and
the line in green. The red line illustrates the curve
$\gamma\mapsto\mathbf{prox}(c(x))$. When , the curve does not lie on any
structure manifold. For , the curve lies on the optimal manifold
$\mathcal{M}_{{2,3}}^{\max}$. For , the curve lies on
$\mathcal{M}_{{1,2,3}}^{\max}$.

Figure 4:  Illustration of the main result on a maximum of three quadratic
functions, with and a point $x$ near . The three figures show the areas where
$\mathbf{prox}\circ c$ detects manifolds for three stepsizes: (upper left),
(upper right) and (lower left). We see on the upper left fig. that
$\mathbf{prox}\circ c$ detects no structure from $x$ because is too small, and
in contrast, on the lower fig., that it wrongly detects too much structure
($\mathcal{M}_{\\{1,2,3\\}}^{\max}$) because is too large. On the upper right
fig., the optimal manifold is detected with chosen in the right interval.

######  Remark 3.40 (About prox-linear methods).

Prox-linear methods are known to identify structure on composite problems
[21]. Specifically, [21, Th. 4.11] establishes that, after some finite time,
an intermediate quantity defined from the prox-linear subproblem _exact_
solution belongs to the optimal structure manifold
${\mathcal{M}^{g}}^{\star}$. In principle, this information could be used to
take efficient second-order steps to minimize $F$ along the identified
manifold ${\mathcal{M}}^{\star}$. However, for generic composite problems, it
may be difficult, first, to obtain an _exact_ solution of the prox-linear
subproblems, and, second, to check if the ensuing quantity belongs to
${\mathcal{M}^{g}}^{\star}$. In contrast, the approach presented here only
needs to compute an exact solution of the proximal operator of the simple
nonsmooth function $g$.

######  Remark 3.41 (Theorem 3.8 provides a structure identification tool).

In contrast with the identification of prox-linear methods, Theorem 3.8
provides a simple result for the detection of structure manifolds near any
point $x\in\mathbb{R}^{n}$. We also underline that the bounds on the range of
that provide correct identification are surprisingly simple: the upper bound
is constant and the lower bound is essentially proportional to the distance to
the manifold. These simple and explicit bounds allow us to build a simple
algorithm in the forthcoming Section 4.

###  3.2 Proof of Theorem 3.8

The main difficulty of the proof is to build a suitable identification result
for the nonsmooth function $g$. Theorem 3.8 (identification for $g\circ c$)
would then follow by taking into account the action of the smooth map $c$.

To derive an identification result on $g$, we have to give conditions on $y$
and so that $p=\mathbf{prox}(y)$ lies on the considered manifold
$\mathcal{M}^{g}$. Since $g$ is prox-regular and prox-bounded at point $c($,
Proposition 2.1 allows us to characterize this relation by its first-order
optimality condition:

(24) $\displaystyle y\in p+$

Whenever $p\in\mathcal{M}^{g}$ (which is what we want to show), this inclusion
decomposes along $T_{p}\mathcal{M}^{g}$ and $N_{p}\mathcal{M}^{g}$ as:

(25) $\displaystyle\operatorname{proj}_{T_{p}\mathcal{M}^{g}}(y-p)$
$\displaystyle=$ (26)
$\displaystyle\operatorname{proj}_{N_{p}\mathcal{M}^{g}}(y-p)$
$\displaystyle\in$

Thus we will show that for suitable $(y,$, there is a unique $p$ that
satisfies these two equations. We do so by considering the smooth tangent
component LABEL:eq:expltanpart first and then the nonsmooth normal component
LABEL:eq:explnormpart as follows:

  * •

We first show in Lemma 3.59 that for $y$ near and small, there exists a unique
point $p=e(y,$ on $\mathcal{M}^{g}$ that satisfies LABEL:eq:expltanpart, which
depends smoothly on $\gamma$ and $y$. This result is obtained by applying the
implicit function theorem.

  * •

Then, we prove in Lemma 3.95 that $e(y,$ also satisfies the second inclusion
LABEL:eq:explnormpart if belongs to the interval
$[\varphi^{g}(\operatorname{dist}_{\mathcal{M}^{g}}(y)),\Gamma^{g}]$. This
result is a consequence of the application of some variational analysis tools.

Putting these two results together, we obtain the existence and uniqueness of
a point $p=e(y,$ verifying both LABEL:eq:expltanpart and LABEL:eq:explnormpart
for all $y$ near and . By the first-order optimality condition presented
above, this point is necessarily $\mathbf{prox}(y)$.

Finally, this identification result in the intermediate space on $g$ is
transferred back to the input space using transversality.

####  3.2.1 Part 1: tangent optimality

We first show that, for $y$ near and small, there is a unique point $p$ _on
the manifold_ $\mathcal{M}^{g}$ that satisfies the tangent component of this
optimality condition:

(LABEL:eq:expltanpart)
$\displaystyle\operatorname{proj}_{T_{p}\mathcal{M}^{g}}(y-p)=$

where
$\operatorname{grad}g(p)\triangleq\operatorname{proj}_{T_{p}\mathcal{M}^{g}}\partial(g(p))$
is unique by the sharpness property of partial smoothness, and matches the
Riemannian gradient of $g$ on $\mathcal{M}^{g}$ (see [6, Sec. 7.7]). Such
points $p$ are given by a smooth manifold-valued application $e(y,$, the
existence of which is guaranteed by the following lemma.

######  Lemma 3.59.

Consider a function $g:\mathbb{R}^{m}\to{\mathbb{R}}\cup\\{+\infty\\}$, a
point , and a manifold $\mathcal{M}^{g}$ with $g$ partly smooth at relative to
$\mathcal{M}^{g}$. Then, there exists a smooth curve
$e:\mathcal{N}\times\mathcal{N}_{0}\to\mathcal{M}$ defined on a neighborhood
of $($ in $\mathbb{R}^{m}\times\mathbb{R}_{+}$ such that

  * •

for all $y\in\mathcal{N}$, $e(y,0)=\operatorname{proj}_{\mathcal{M}^{g}}(y)$
and $\frac{\mathrm{d}}{\mathrm{d}\step}e(y,$;

  * •

for all $y\in\mathcal{N}$, , Eq. ( ‣ 3.2.1) is satisfied for $p=e(y,$.

######  Proof 3.65.

We define the mapping
$\Phi:\mathbb{R}^{m}\times\mathbb{R}\times\mathcal{M}^{g}\to\cup_{x\in\mathcal{M}^{g}}T_{x}\mathcal{M}^{g}$
as

(27) $\displaystyle\Phi(y,$

and consider the equation $\Phi(y,$ near the point $($. Using the smoothness
of $g$ on $\mathcal{M}^{g}$ given by partial smoothness, we have that this
mapping is continuously differentiable on a neighborhood of $($. We see that
its differential with respect to $p$ is $\operatorname{D}_{p}\Phi($. Indeed,
for $\eta\in T_{p}\mathcal{M}^{g}$,

(28) $\displaystyle\operatorname{D}_{p}\Phi(y,$

At point $($, the first term vanishes, and the third term writes

(29)
$\displaystyle\operatorname{D}_{p^{\prime}}\left(p^{\prime}\mapsto\operatorname{proj}_{T_{p^{\prime}}\mathcal{M}^{g}}(0)\right)($

and vanishes as well as the differential of the null function
$p^{\prime}\mapsto\operatorname{proj}_{T_{p^{\prime}}\mathcal{M}^{g}}(0)$.
Thus $\operatorname{D}_{p}\Phi($ is invertible. The implicit functions theorem
thus grants the existence of neighborhoods $\mathcal{N}^{1}$,
$\mathcal{N}_{0}^{2}$, $\mathcal{N}^{3}$ of , $0$, in $\mathbb{R}^{m}$,
$\mathbb{R}$, $\mathcal{M}^{g}$ and a continuously differentiable function
$e:\mathcal{N}^{1}\times\mathcal{N}_{0}^{2}\to\mathcal{N}^{3}$ such that, for
any $(y,$, Equation is satisfied with $p=e(y,$. For $y\in\mathcal{N}^{1}$,
$e(y,0)$ satisfies $y-e(y,0)\in N_{e(y,0)}\mathcal{M}^{g}$, which is the
first-order optimality condition of
$e(y,0)=\operatorname{proj}_{\mathcal{M}^{g}}(y)$. Possibly reducing
$\mathcal{N}^{1}$ so that, for all $y\in\mathcal{N}$
$\operatorname{proj}_{\mathcal{M}^{g}}(y)$ is well-defined and unique, the
previous optimality condition is equivalent to
$e(y,0)=\operatorname{proj}_{\mathcal{M}^{g}}(y)$. Besides, differentiating
$\Phi(y,$ relative to at yields

(30) $\displaystyle\operatorname{D}e(y,0)$
$\displaystyle=-[\operatorname{D}_{p}\Phi(y,0,\operatorname{proj}_{\mathcal{M}^{g}}(y))]^{-1}\operatorname{D}\Phi(y,0,\operatorname{proj}_{\mathcal{M}^{g}}(y))$
(31)
$\displaystyle=-\operatorname{grad}g(\operatorname{proj}_{\mathcal{M}^{g}}(y)),$

which concludes the proof.

####  3.2.2 Part 2: normal optimality

The previous lemma shows that for every $(y,$ one can find a point $e(y,$ _on
the manifold_ $\mathcal{M}^{g}$ that solves the tangent part of the optimality
condition ( ‣ 3.2.1). The next lemma determines the values of $y$ and for
which the whole optimality condition

(32) $\displaystyle y\in e(y,$

holds, as illustrated in Figure 5(a).

(a) the curve on $\mathcal{M}$.

(b) the curve on $\mathcal{M}$
for .

Figure 5: Illustration of Lemma 3.95 and its consequences.

######  Lemma 3.95.

Consider a function $g$, a point and a manifold $\mathcal{M}^{g}$ such that
$g$ is partly smooth at relative to $\mathcal{M}^{g}$ and that $g$ satisfies
Property 2.19 at . Let $e$ denote a smooth $\mathcal{M}$-valued application
defined on a neighborhood of $($ provided by Lemma 3.59. Then, there exists
$C>0$ such that:

  1. i)

for all , $e($ verifies (32) with $y=$,

  2. ii)

for all , there exists a neighborhood $\mathcal{N}$ of  such that, for all
$y\in\mathcal{N}$, $e(y,$ verifies (32),

Further assume that $g$ satisfies Property 2.23 at with constant $\tilde{L}$,
then

  1. iii)

there exist $\Gamma^{g}>0$ and a neighborhood $\mathcal{N}$ of  such that for
all $y\in\mathcal{N}$

(33) $\displaystyle e(y,$

where $c_{\text{ri}}\geq 0$ and
$\varphi^{g}(t)=\frac{c_{\text{ri}}}{2\tilde{L}}\left(1-\sqrt{1-\frac{4\tilde{L}t}{c_{\text{ri}}^{2}}}\right)=\frac{1}{c_{\text{ri}}}t+\frac{\tilde{L}}{c_{\text{ri}}^{3}}t^{2}+o(t^{2})$.

The proof consists in finding the points $y,$ such that
$0\in\operatorname{ri}\Psi(y,$, where the mapping
$\Psi:\mathbb{R}^{m}\times\mathbb{R}\to\cup_{x\in\mathcal{M}^{g}}N_{x}\mathcal{M}^{g}$
is defined as

(34) $\displaystyle\Psi(y,$

Items _i)_ and _ii)_ are shown by extending the property $0\in\Psi($ to a
neighborhood of $($, using the inner-semicontinuity properties of $\Psi$. We
refer to [29, Def. 5.4] for an exposition of the notions of continuity of set-
valued mappings. We then derive explicit bounds on the interval of steps such
that $0\in\operatorname{ri}\Psi(y,$: for a fixed $y\in\mathcal{N}$, when
decreases past some value, say $\underaccent{\bar}{\step}(y)$, the condition
$0\in\operatorname{ri}\Psi(y,$ no longer holds. Precisely at
$\underaccent{\bar}{\step}(y)$, $0$ lies on the (relative) boundary of
$\Psi(y,\underaccent{\bar}{\step}(y))$: denoting
$\operatorname{rbd}S\triangleq S\setminus\operatorname{ri}S$ the relative
boundary of set $S$,

(35) $\displaystyle
0\in\operatorname{rbd}\operatorname{proj}_{N_{e(y,\underaccent{\bar}{\step}(y))}\mathcal{M}^{g}}\left(\frac{1}{\underaccent{\bar}{\step}(y)}\left(e(y,\underaccent{\bar}{\step}(y))-y\right)+\partial
g\left(e(y,\underaccent{\bar}{\step}(y))\right)\right).$

Denoting
$\partial^{N}g(p)\triangleq\operatorname{proj}_{N_{p}\mathcal{M}^{g}}(\partial
g(p))$ the projection of the subdifferential on the normal space of its
structure manifold and taking norms yields:

(36)
$\displaystyle\|\operatorname{proj}_{N_{e(y,\underaccent{\bar}{\step}(y))}\mathcal{M}^{g}}(y-e(y,\underaccent{\bar}{\step}(y)))\|$
$\displaystyle\geq\underaccent{\bar}{\step}(y)\inf_{v_{n}\in\operatorname{rbd}{\partial^{N}g(e(y,\underaccent{\bar}{\step}(y)))}}\|v_{n}\|$
(37)
$\displaystyle\geq\underaccent{\bar}{\step}(y)\underbrace{\inf_{p\in\mathcal{N}}\inf_{v_{n}\in\operatorname{rbd}{\partial^{N}g(p)}}\|v_{n}\|}_{\triangleq
c_{\text{ri}}}.$

We note that the constant $c_{\text{ri}}$ is positive. Indeed,
$y\mapsto\operatorname{grad}g(y)=\operatorname{proj}_{N_{y}\mathcal{M}^{g}}\partial
g(y)$ is a continuous selection of the affine hull of $\partial g$, and
$\operatorname{grad}g($ by property 2.19. Lemma 20 from [8] then guarantees
that $\operatorname{grad}g(y)\in\operatorname{ri}\partial g(y)$ for $y$ close
enough to . Projecting back on the normal space at $y$ provides the inclusion
$0\in\operatorname{ri}\operatorname{proj}_{N\mathcal{M}^{g}}\partial g($ a
neighborhood of on $\mathcal{M}^{g}$. This implies positivity of
$c_{\text{ri}}$, reducing the size of $\mathcal{N}$ if necessary. We note that
this kind of quantity also appears as the _modulus of identifiability_ in the
recent [17, Def. 2.3] where it has the same property: its positivity enables
the identification of the associated structure manifold.

Using Property 2.23, the left-hand side is upper bounded by a simpler
expression:

(38)
$\displaystyle\tilde{L}\underaccent{\bar}{\step}(y)^{2}+\operatorname{dist}_{\mathcal{M}^{g}}(y)\geq
c_{\text{ri}}\underaccent{\bar}{\step}(y),\quad\text{ that is
}\quad\underaccent{\bar}{\step}(y)\leq\frac{c_{\text{ri}}}{2\tilde{L}}\left(1-\sqrt{1-\frac{4\tilde{L}\operatorname{dist}_{\mathcal{M}^{g}}(y)}{c_{\text{ri}}^{2}}}\right),$

which provides the expression for $\varphi^{g}$ used in the lemma.

######  Proof 3.129.

_Item i)_ We first consider $\Psi(\cdot)=\Psi($. Since , Lemma 3.59 tells us
that $e($, and thus

(39)
$\displaystyle\Psi(0)=\operatorname{proj}_{N\mathcal{M}^{g}}\left(-\operatorname{grad}g(\right)=\operatorname{proj}_{N\mathcal{M}^{g}}(\partial
g($

where we used that $\operatorname{grad}g($ is orthogonal to
$N\mathcal{M}^{g}$. Property 2.19 provides that
$0\in\operatorname{ri}\Psi(0)$. We now turn to show that there exists
$C^{\prime}$ such that, for all , $0\in\operatorname{ri}\Psi($.

By contradiction, assume there exist a sequence such that
$0\notin\operatorname{ri}\Psi($. This means that there exists a sequence of
unit norm vectors $(s_{k})$ such that for all $k$,

(40) $\displaystyle\langle s_{k},z\rangle\leq 0\text{ for all }z\in\Psi($

As a bounded sequence, $s_{k}$ admits at least one limit point, say . Take .
The continuity of $\partial g$ (by partial smoothness, item iv), of (by
smoothness of $e$), and of (by smoothness of $\mathcal{M}^{g}$) yield the
continuity of $\Psi$ as a set-valued map. This mapping is thus inner-
semicontinuous [29, Def. 5.4], so there exists a sequence $z_{k}\in\Psi($ such
that $z_{k}$ converges to . Taking the correct subsequence and renaming
iterates, we can write $s_{k}\to$ and $z_{k}\to$. Equation (40) provides
$\langle s_{k},z_{k}\rangle\leq 0$ for all $k$, which gives at the limit
$\langle$. This actually holds for all : separates $0$ and $\Psi(0)$, which
contradicts $0\in\operatorname{ri}\Psi(0)$.

Finally, let us take the constant $C$ such that $[0,C]$ is included in both
$[0,C^{\prime}]$ and the neighborhood of $0$ provided by Lemma 3.59. Then, for
any , adding the two orthogonal inclusions $0\in\operatorname{ri}\Psi($ and
$0=\Phi(y,$, we obtain that $e($ verifies (32) with $y=$.

_Item ii)_ Let . We turn to show the existence of a neighborhood $\mathcal{N}$
of  such that, for all $y\in\mathcal{N}$, $e(y,$ verifies (32). By
contradiction, assume that there exists a sequence $(y_{k})$ that converges to
such that (32) fails for $(y_{k},$. Since the tangent component of (32) does
hold, necessarily $0\notin\operatorname{ri}\Psi(y_{k},$. However, the mapping
$y\mapsto\Psi(y,$ is inner-semicontinuous (from the same arguments as in the
proof of _item i)_ and there holds $0\in\operatorname{ri}\Psi($. A reasoning
similar to that of _item i)_ reveals the contradiction.

_Item iii)_ Define $\mathcal{N}$ a neighborhood of  and $\Gamma^{g}$ a
positive constant such that Property 2.23 applies over
$\mathcal{N}\times[0,\Gamma^{g}]$, and $0\in\operatorname{ri}\Psi(y,$ holds
for all $(y,$. The second condition can be met on a nontrivial neighborhood of
$($: it holds at that point, and $\Psi$ is inner-semicontinuous ($e(y,$ lies
on $\mathcal{M}^{g}$ and $\partial g$ is inner-semicontinuous by partial
smoothness of $g$).

Let $y\in\mathcal{N}$ and . We show that
$0\in\operatorname{ri}\Psi(y,\gamma)$, that is

(41) $\operatorname{proj}_{N_{e(y,\step)}\mathcal{M}^{g}}(y-e(y,$

Combining this with the orthogonal inclusion $0=\Phi(y,\gamma,e(y,\gamma))$
yields the claim.

The inequality $\varphi^{g}(\operatorname{dist}_{\mathcal{M}^{g}}(y))\leq$
implies $\tilde{L}$. We have successively by definition of $\mathcal{N}$ and
the above bound that

(42)
$\displaystyle\|\operatorname{proj}_{N_{e(y,\step)}\mathcal{M}^{g}}(y-e(y,$
$\displaystyle\leq$ (43) $\displaystyle\leq$

This means that $\operatorname{proj}_{N_{e(y,\step)}\mathcal{M}^{g}}(y-e(y,$
belongs to the ball of center $0$ and radius in
$N_{e(y,\step)}\mathcal{M}^{g}$. Besides, this ball is included in since
$0\in\partial^{N}g(e(y,$ by definition of $\mathcal{N}$. Therefore,
$0\in\operatorname{ri}\Psi(y,$ for all $y\in\mathcal{N}$ and .

####  3.2.3 Part 3: From the intermediate space to the input space

To conclude the proof of Theorem 3.8, we will first identify the curve $e(y,$
to $\mathbf{prox}(y)$ and thus prove that it belongs to the sought manifold,
as illustrated in Fig. 5(b). Then, this intermediate identification result is
brought back to the input space using transversality.

######  Proof 3.186.

The standing assumptions allow to call Lemma 3.95 at point $c($ with manifold
$\mathcal{M}^{g}$. This yields the neighborhood $\mathcal{N}_{c(\crit[\vx])}$,
constants $\Gamma^{g}$ and $C$, a function $\varphi^{g}$, and a smooth mapping
$e:\mathcal{N}_{c(\crit[\vx])}\times[0,C]\to\mathcal{M}^{g}$ such that, for
$y\in\mathcal{N}_{c(\crit[\vx])}$ and , $e(y,$ verifies the optimality
condition (32) of $e(y,$. Besides, since $g$ is prox-regular and prox-bounded
at point $c($, these properties also hold on a neighborhood of that point.
Under these conditions, Proposition 2.1 allows to recover the equality $e(y,$.
Take $\mathcal{N}=c^{-1}(\mathcal{N}_{c(\crit[\vx])})$, a neighborhood of as
the preimage of a neighborhood of $c($ by the continuous $c$. For all
$x\in\mathcal{N}$,

(44) $\displaystyle\mathbf{prox}(c(x))\in\mathcal{M}^{g}\text{ for all }$

We turn to show that, for some constant $c_{\text{map}}>0$, there holds
$\operatorname{dist}_{\mathcal{M}^{g}}(c(x))\leq
c_{\text{map}}\operatorname{dist}_{\mathcal{M}}(x)$ for all $x\in\mathcal{N}$.
Let $x\in\mathcal{N}$ and
$x^{\mathcal{M}}=\operatorname{proj}_{\mathcal{M}}(x)$, so that
$\operatorname{dist}_{\mathcal{M}}(x)=\|x^{\mathcal{M}}-x\|$. Using
successively that $c(x^{\mathcal{M}})\in\mathcal{M}^{g}$ and smoothness of
$c$, there holds for $x$ near

(45) $\displaystyle\operatorname{dist}_{\mathcal{M}^{g}}(c(x))$
$\displaystyle\leq\|c(x)-c(x^{\mathcal{M}})\|$ (46)
$\displaystyle\leq\|\operatorname{Jac}_{c}(x^{\mathcal{M}})\cdot(x-x^{\mathcal{M}})\|+\mathcal{O}(\|x-x^{\mathcal{M}}\|^{2})$
(47) $\displaystyle\leq\left(\sup_{v_{n}\in
N_{x^{\mathcal{M}}}\mathcal{M},\|v_{n}\|=1}\|\operatorname{Jac}_{c}(x^{\mathcal{M}})\cdot
v_{n}\|\right)\|x-x^{\mathcal{M}}\|+\mathcal{O}(\|x-x^{\mathcal{M}}\|^{2})$
(48) $\displaystyle\leq\underbrace{\left(\sup_{u\in\mathcal{N}}\sup_{v_{n}\in
N_{u}\mathcal{M},\|v_{n}\|=1}\|\operatorname{Jac}_{c}(u)\cdot
v_{n}\|\right)}_{C^{\prime\prime}}\|x-x^{\mathcal{M}}\|+\mathcal{O}(\|x-x^{\mathcal{M}}\|^{2}).$

We show by contradiction that the constant $C^{\prime\prime}$ is positive. If
$C^{\prime\prime}=0$, there exists $v_{n}\in N\mathcal{M}$ of unit norm such
that $\operatorname{D}c($. By Eq. 20, we have $v_{n}=\operatorname{D}c($ for
some $\hat{v}_{n}\in N_{c(\crit)}\mathcal{M}^{g}$, so that
$\operatorname{D}c($. Pre-multiplying by $\hat{v}_{n}^{*}$ yields
$\|\operatorname{D}c($: there holds
$\hat{v}_{n}\in\ker({\operatorname{D}c(\crit)}^{{*}})\cap
N_{c(\crit)}\mathcal{M}^{g}$. The transversality condition Eq. 19 implies
$\hat{v}_{n}=0$, and in turn $v_{n}=0$, which contradicts the fact that this
vector has unit length.

Therefore, for all $x\in\mathcal{N}$ and a constant
$c_{\text{map}}>C^{\prime\prime}$, there holds
$\operatorname{dist}_{\mathcal{M}^{g}}(c(x))\leq
c_{\text{map}}\operatorname{dist}_{\mathcal{M}}(x)$. Monotony of $\varphi^{g}$
implies that
$\varphi^{g}(\operatorname{dist}_{\mathcal{M}^{g}}(c(x)))\leq\varphi^{g}(c_{\text{map}}\operatorname{dist}_{\mathcal{M}}(x))$,
which yields the claimed bounds with

(49)
$\displaystyle\varphi(t)=\frac{c_{\text{ri}}}{2\tilde{L}}\left(1-\sqrt{1-\frac{4\tilde{L}c_{\text{map}}t}{c_{\text{ri}}^{2}}}\right)\quad\text{
and }\quad\Gamma=\Gamma^{g}.$

Finally, we show the existence of positive constants $\epsilon$, $L$ such that

(50) $\displaystyle\|x-$

Since , $\operatorname{dist}_{\mathcal{M}}(\cdot)\leq\|\cdot-$. By monotony
and smoothness of $\varphi$, there exists $L>0$ such that
$\varphi(\operatorname{dist}_{{\mathcal{M}}^{\star}}(\cdot))\leq
L\|\cdot-{x}^{\star}\|$ over $\mathcal{B}({x}^{\star},\epsilon)$. Reducing
$\epsilon$ if necessary so that $L\epsilon<\Gamma$ yields the result.

##  4 A local Newton algorithm for nonsmooth composite minimization

In this section, we use the results of Section 3 to propose an optimization
method that locally identifies the structure of a minimizer and converges
quadratically to this point.

Recall the basic idea: if the optimal manifold ${\mathcal{M}}^{\star}$
corresponding to a minimizer ${x}^{\star}$ is known, the _nonsmooth_
optimization problem turns into a _smooth constrained_ optimization problem.
In turn, this problem can be solved using algorithms from smooth constrained
optimization such as Sequential Quadratic Programming.

Using this idea and the structure identification mechanism developed in the
previous section, we propose a method which: i) uses the proximity operator of
$g$ to gather structure in the intermediate space, ii) brings back this
structure to the input space, and iii) optimizes smoothly along the identified
manifold. The resulting algorithm is precisely described in Section 4.1 and
then analyzed in Section 4.2.

###  4.1 Description of the algorithm

We proceed to describe the three steps exposed above. The full algorithm is
depicted in Algorithm 1.

_Gathering structure._ We showed in Theorem 3.8 that near a qualified point in
$\mathbb{R}^{n}$, the operator $\mathbf{prox}(c(\cdot))$ provides the optimal
structure ${\mathcal{M}^{g}}^{\star}$ (in the intermediate space
$\mathbb{R}^{m}$) for an explicit range of steps. We thus define from the
current iterate $x_{k}\in\mathbb{R}^{n}$ and stepsize the working manifold
$\mathcal{M}^{g}_{k}$ (in the intermediate space) as the structure of
$\mathbf{prox}(c(x_{k}))$. One technical point is to guarantee that, after
some time, so that the optimal manifold is identified; this is done by
decreasing linearly at each iteration.

_From the intermediate to the input space._ We now have a structure manifold
$\mathcal{M}^{g}_{k}$ in the intermediate space, and can define
$\tilde{g}_{k}$, a smooth extension of $g$ on $\mathcal{M}^{g}_{k}$ to
$\mathbb{R}^{m}$. Using a local equation $h^{g}_{k}$ of $\mathcal{M}^{g}_{k}$,
we define the smooth map $h_{k}=h^{g}_{k}\circ
c:\mathbb{R}^{n}\to\mathbb{R}^{p_{k}}$, which locally defines
$\mathcal{M}_{k}=c^{-1}(\mathcal{M}^{g}_{k})$. Similarly, a smooth extension
of $F$ on $\mathcal{M}_{k}$ is defined by $\tilde{F}_{k}=\tilde{g}_{k}\circ
c$.

_Optimizing in the input space._ We can now take steps to minimize the smooth
extension $\tilde{F}_{k}$ on the smooth set $\mathcal{M}_{k}$ characterized by
$h_{k}(x)=0$:

(51)
$\displaystyle\min_{x\in\mathbb{R}^{n}}\tilde{F}_{k}(x)\quad\text{s.t.}\quad
h_{k}(x)=0.$

We turn to an elementary version of the traditional second-order Sequential
Quadratic Programming methodology; see _e.g._ [5, Chap. 14]. At iteration $k$,
the SQP direction $d_{k}^{\mathrm{SQP}}(x_{k})$ at point $x_{k}$ is defined as
the solution of the following quadratic problem:

(52) $\displaystyle\begin{aligned}
d_{k}^{\mathrm{SQP}}(x_{k})=\operatorname{argmin}_{d\in\mathbb{R}^{n}}\quad&\langle\nabla\tilde{F}_{k}(x_{k}),d\rangle+\frac{1}{2}\langle\nabla^{2}_{xx}L_{k}(x_{k},\lambda_{k}(x_{k}))d,d\rangle\\\
\textrm{s.t.}\quad&h_{k}(x_{k})+\operatorname{D}h_{k}(x_{k})d=0\end{aligned}$

where $\nabla^{2}_{xx}L_{k}$ denotes the Hessian of the Lagrangian
$L_{k}(x,\lambda)=\tilde{F}_{k}(x)+\langle\lambda,h_{k}(x)\rangle$, and the
multiplier $\lambda_{k}(x_{k})$ defined from the following least-squares
problem:

(53)
$\displaystyle\lambda_{k}(x_{k})=\operatorname{argmin}_{\lambda\in\mathbb{R}^{p_{k}}}\left\|\nabla\tilde{F}_{k}(x_{k})+\sum_{i=1}^{p_{k}}\lambda_{i}\nabla
h_{k,i}(x_{k})\right\|^{2}.$

Finally, we check that $x_{k}+d_{k}^{\mathrm{SQP}}(x_{k})$ provides a
functional decrease in order to avoid degrading the iterate when the current
structure is suboptimal. If the test is not verified, $x_{k}$ is not updated
and is decreased until a satisfying structure is detected.

Algorithm 1 General structure exploiting algorithm

1:Pick $x_{0}$ near a minimizer, large enough.

2:repeat

3:

4: Compute $\mathbf{prox}(c(x_{k}))$ and obtain $\mathcal{M}^{g}_{k}$ locally
defined by $h^{g}_{k}$

5: $h_{k}=h^{g}_{k}\circ c$ (local equation of $\mathcal{M}_{k}$),
$\tilde{F}_{k}=\tilde{g}_{k}\circ c$ (smooth extension)

6: Compute $d_{k}^{\mathrm{SQP}}(x_{k})$ by solving (52)

7: if $F(x_{k}+d_{k}^{\mathrm{SQP}}(x_{k}))\leq F(x_{k})$ then

8: $x_{k+1}=x_{k}+d_{k}^{\mathrm{SQP}}(x_{k})$

9: else

10: $x_{k+1}=x_{k}$

11:until stopping criterion

######  Remark 4.11 (Complexity of one iteration).

The main computational cost of one iteration of Algorithm 1 consists in the
resolution of the quadratic program (52). Its plain resolution incurs a
$\mathcal{O}(n^{3})$ complexity. However, efficient approaches _reduce_ this
problem to a quadratic program on the subspace
$\ker\operatorname{D}h_{k}(x_{k})$, which has dimension
$\dim(\mathcal{M}_{k})$. We refer to [5, Chap. 14] for an in-depth exposition
of these techniques. The cost of an iteration is thus
$\mathcal{O}(\dim(\mathcal{M}_{k})^{3})$. In situations where minimizers are
highly structured (_i.e._ $\dim(\mathcal{M}^{\star})\ll n$) this complexity
may be comparable with the $\mathcal{O}(n^{2})$ iteration complexity of
classical nonsmooth optimization algorithms, such as nonsmooth BFGS [20].

###  4.2 Convergence of Algorithm 1

We proceed to give the result guaranteeing identification and local quadratic
convergence of Algorithm 1.

In order to benefit from the quadratic rate of SQP, the elements of (52)
should have the minimal regularity typically required by smooth constrained
Newton methods (see _e.g._ [5, Th. 14.5]); we thus make the following
assumption.

######  Assumption 4.12 (Regularity of functions).

The smooth extension and the manifold defining map are $\mathcal{C}^{2}$ with
Lipschitz second derivatives, and the Jacobian of the constraints is full rank
near the solution.

In order to focus on the algorithmic originality of the method, we slightly
simplify the situation and make the two following algorithmic assumptions.

######  Assumption 4.13 (Nonconvex stability).

The iterates of Algorithm 1 remain in the connected component of the sublevel
set $\\{x:F(x)\leq F(x_{0})\\}$ that contains ${x}^{\star}$.

This assumption ensures that an update that decreases the functional value
remains in the neighborhood of the minimizer ${x}^{\star}$. It is naturally
satisfied when $F$ is convex, or when ${x}^{\star}$ is a global minimizer of
$F$ and $x_{0}$ is close enough to ${x}^{\star}$.

######  Assumption 4.14 (No Maratos effect).

The iterates of Algorithm 1 are such that a step $d$ that makes $x+d$
quadratically closer to $x$ yields descent: $F(x+d)\leq F(x)$.

In smooth constrained optimization, getting closer (even at quadratic rate) to
a minimizer does not imply decrease of objective value and constraint
violation (measured by a merit function). This so-called Maratos effect (see
_e.g._ [5]) is one of the main difficulties in globalizing SQP schemes, which
is out of the scope of the current paper. We thus assume this effect does not
affect our algorithm in theory, and use in practice one of the successful
refinements, as discussed in Section 5.2.

We are now ready for the main convergence result of Algorithm 1, which
establish that, after some finite time, the iterates identify exactly the
optimal manifold and converge to the minimizer at a quadratic rate.

######  Theorem 4.15 (Exact identification and quadratic convergence).

Consider a function $F=g\circ c$ and ${x}^{\star}$ a strong minimizer,333There
exists $\eta>0$, $\epsilon>0$ such that $F(x)\geq
F({x}^{\star})+\eta\|x-{x}^{\star}\|^{2}$ for all
$x\in\mathcal{B}({x}^{\star},\epsilon)$. qualified relative to the optimal
manifold ${\mathcal{M}}^{\star}$. Assume that the smooth extension $\tilde{F}$
of $F$ relative to ${\mathcal{M}}^{\star}$ and the corresponding manifold
defining map $h$ satisfy Assumption 4.12.

If $x_{0}$ and $F(x_{0})$ are close enough to ${x}^{\star}$ and
$F({x}^{\star})$, is large enough and the simplifying algorithmic Assumptions
4.13 and 4.14 hold, then there exists $C>0$ such that the iterates
$(x_{k},\mathcal{M}_{k})$ generated by Algorithm 1 verify:

(54)
$\displaystyle\mathcal{M}_{k}={\mathcal{M}}^{\star}\quad\text{and}\quad\|x_{k+1}-{x}^{\star}\|\leq
C\|x_{k}-{x}^{\star}\|^{2}\quad\text{for all }k\text{ large enough. }$

The proof of this result consists in two steps. We first show the existence of
a neighborhood of initialization on which the proximity operator will
eventually identify the optimal manifold, once the stepsize has been
sufficiently decreased. From this point onward, we prove that the SQP step
provides a quadratic improvement and that the stepsize policy makes the
manifold identification stable.

######  Proof 4.17.

_Local identification of the optimal structure._ By Theorem 3.8, there exists
a ball centered around ${x}^{\star}$ of radius $\epsilon_{1}>0$ and two
positive constants $L$, $\Gamma$ such that, for all
$x\in\mathcal{B}({x}^{\star},\epsilon_{1})$ and , $\mathbf{prox}(c(x))$
belongs to the optimal manifold
${\mathcal{M}^{g}}^{\star}=c({\mathcal{M}}^{\star})$.

_Local quadratic convergence of SQP on the optimal structure._ Let us assume
that the optimal manifold has been identified. The least square multiplier
$\lambda$ is defined by the optimality condition of (53):

(55)
$\displaystyle\lambda(x)=-[\operatorname{Jac}_{h}(x)\operatorname{Jac}_{h}(x)^{\top}]^{-1}\operatorname{Jac}_{h}(x)\nabla\tilde{F}(x).$

and since $h$ is smooth and its Jacobian is full-rank near ${x}^{\star}$,
$\lambda$ is a Lipschitz continuous function near ${x}^{\star}$.

Since ${x}^{\star}$ is a strong minimizer of $F$, the Hessian of the
Lagrangian restricted to the tangent space is positive definite. Indeed, since
${x}^{\star}$ is a strong minimizer of $F$ on ${\mathcal{M}}^{\star}$, the
Riemannian Hessian relative to the optimal manifold is positive definite. With
the choice of multiplier (53), the Riemannian Hessian is exactly the Hessian
of the Lagrangian restricted to the tangent space to ${\mathcal{M}}^{\star}$
at ${x}^{\star}$ (see [6, Sec. 7.7]), which is thus itself positive definite.

Thus, using the local quadratic convergence of SQP [5, Th. 14.5], we get that
there exists a ball centered around ${x}^{\star}$ of radius $\epsilon_{2}>0$
such that the SQP step computed at a point $x$ in that neighborhood relative
to the optimal manifold provides a quadratic improvement towards
${x}^{\star}$. Reducing $\epsilon_{2}$ if necessary, we can in addition have
that the convergence is at least linear with rate $1/2$.

_Initialization, identification, and quadratic convergence._ Let
$\epsilon=\min(\epsilon_{1},\epsilon_{2},\Gamma/(2L))$. We will now show that
initializing with $x_{0}\in\\{x:F(x)\leq F({x}^{\star})+\eta\epsilon^{2}\\}$
and  provides the claimed behavior.

First, the functional decrease test of the algorithm and Assumption 4.14
guarantee that all iterates satisfy $F(x_{k})\leq F(x_{0})$. Using that
${x}^{\star}$ is a strong minimizer, we get that
$\eta\|x_{k}-{x}^{\star}\|^{2}\leq F(x_{k})-F({x}^{\star})\leq
F(x_{0})-F({x}^{\star})\leq\eta\epsilon^{2}$, and thus that the iterates
remain in $\mathcal{B}({x}^{\star},\epsilon)$.

Second, as $L\|x-{x}^{\star}\|\leq\Gamma/2$ for all
$x\in\mathcal{B}({x}^{\star},\epsilon)$ by construction, the fact that and $($
decreases with geometric rate $1/2$ implies that there exists $K$ such that
$L\|x_{K}-{x}^{\star}\|\leq$.

Now, assume that at iteration $k\geq K$, $L\|x_{k}-{x}^{\star}\|\leq$. Since
$x_{k}\in\mathcal{B}({x}^{\star},\epsilon_{1})$, we have from above that
${\mathcal{M}}^{\star}$ is identified. Thus, the SQP step is performed
relative to the optimal manifold and $x_{k}+d_{k}^{\mathrm{SQP}}(x_{k})$
brings a linear improvement of factor $1/2$ at least. Assumption 4.13 ensures
that $F(x_{k}+d_{k}^{\mathrm{SQP}}(x_{k}))\leq F(x_{k})$ so that
$x_{k+1}=x_{k}+d_{k}^{\mathrm{SQP}}(x_{k})$ and thus

(56) $\displaystyle
L\|x_{k+1}-{x}^{\star}\|\leq\frac{L}{2}\|x_{k}-{x}^{\star}\|\leq\frac{\step{}_{k}}{2}=$

This shows that $L\|x_{k+1}-{x}^{\star}\|\leq$, which completes the induction.
We get that for all $k\geq K$. Finally, we have that for all $k\geq K$,
$\mathcal{M}_{k}={\mathcal{M}}^{\star}$ and $x_{k+1}$ is quadratically closer
to ${x}^{\star}$ than $x_{k}$.

_Direct generalizations._ Theorem 4.15 actually holds for any decrease factor
of in $(0,1)$ with the presented SQP update, or actually any superlinearly
convergent update (_e.g._ a quasi-Newton type update). The above result is
also readily adapted to an update that converges merely linearly, as long as
its rate of convergence is faster than that of . This opens the possibility of
using SQP methods that rely only on first-order information (see _e.g._ [4]).

##  5 Numerical experiments

In this section, we provide numerical illustrations for our results. Our goal
here is twofold:

  1. i)

to illustrate the identification of the optimal manifold by the proximity
operator near a minimizer as provided by Theorem 3.8;

  2. ii)

to demonstrate the applicability of Algorithm 1 and observe the quadratic
rates predicted by Theorem 4.15 on our running examples.

###  5.1 Test problems

We first consider the minimization of a pointwise maximum of smooth functions
(2):

(57) $\displaystyle\min_{x\in\mathbb{R}^{n}}\max_{i=1,\ldots,m}(c_{i}(x)).$

We take the celebrated MaxQuad instance, where $n=10$, $m=5$ and each $c_{i}$
is quadratic convex, making the whole function $F$ convex [5, p. 153]. In this
instance, the optimal manifold is $\mathcal{M}^{\max}_{I}$ with
$I=\\{2,3,4,5\\}$.

Second, we consider the minimization of the maximum eigenvalue of an affine
mapping (3):

(58)
$\displaystyle\min_{x\in\mathbb{R}^{n}}~{}\lambda_{\max{}}\left(A_{0}+\sum_{i=1}^{n}x_{i}A_{i}\right).$

We take $n=25$ and we generate randomly $n+1$ symmetric matrices of size $50$.
In this instance, the multiplicity of the maximum eigenvalue at the minimizer
is $r=3$.

###  5.2 Numerical setup

All the algorithms are implemented in Julia [2]; experiments may be reproduced
using the code available online444 See
https://github.com/GillesBareilles/LocalCompositeNewton.jl for Algorithm 1 and
https://github.com/GillesBareilles/NonSmoothSolvers.jl for the baselines. .

_Algorithm._ For the initialization of Algorithm 1, we set as the smallest
such that $\mathbf{prox}(c(x_{0}))$ has the most structure (_e.g._ if
$g=\max$, we increase until the output of the proximity operator sets all
coordinates to the same value, and if $g=\lambda_{\max{}}$, we increase until
the multiplicity of the maximal eigenvalue of the output of the proximity
operator is maximal). We solve the quadratic subproblem (52) providing the SQP
step by the reduced system approach presented in [5, p. 133]. Tangent vectors
are expressed in an orthonormal basis of the nullspace of the Jacobian of the
constraints at the current iterate. At iterate $x_{k}$, a second-order
correction step $d^{\mathrm{corr}}(x_{k})$ is added to the SQP step
$d^{\mathrm{SQP}}(x_{k})$. It is obtained as
$d^{\mathrm{corr}}(x_{k})=\operatorname{argmin}_{d\in\mathbb{R}^{n}}\\{\|h(x_{k})+\operatorname{Jac}_{h}(x_{k})\;d\|,\text{
s.t. }d\in\mathrm{Im}\;\operatorname{Jac}_{h}(x_{k})^{\top}\\}$. The full-step
is thus $x_{k}+d^{\mathrm{SQP}}(x_{k})+d^{\mathrm{corr}}(x_{k})$.

##### Baselines

For the two nonsmooth problems, we compare with the nonsmooth BFGS algorithm
of [20] (nsBFGS) and the gradient sampling algorithm [7]. The nsBFGS method is
not covered by any theoretical guarantees; it is known to perform relatively
well in practice, often displaying a linear rate of convergence. In contrast,
the Gradient Sampling algorithm generates with probability one a sequence of
iterates for which all cluster points are Clarke stationary for $F$ [7, Th.
3.1].555This holds when $F$ is locally Lipschitz over $\mathbb{R}^{n}$ and
lower bounded, the algorithm iterates indefinitely and the sampling radius
decreases to $0$.

Other methods could be considered as relevant baselines. In particular, the
minimization of convex composite functions can be tackled with dedicated
bundle methods [30]. Alternatively, some approaches try to estimate and use
the optimal structure ${\mathcal{M}}^{\star}$, leading to potential
superlinear convergence: [33] for the maximum of smooth functions, [27, 13]
for the maximum eigenvalue, and [23] for general convex functions. However,
the superlinear speed of these methods hinges on the correct identification of
the optimal manifold ${\mathcal{M}}^{\star}$, which is done only
heuristically. We do not include these methods in our numerical comparison
since they are rather advanced, and thus difficult to implement and tune
efficiently.

##### Oracles

Traditional methods for nonsmooth optimization, and notably bundle methods,
require a first-order oracle:

(59) $\displaystyle x\mapsto(F(x),v)\quad\text{ where }v\in\partial F(x)$

while Gradient Sampling and nsBFGS require additionally to know if $F$ is
differentiable at point $x$. Algorithm 1 requires rather different information
oracles:

(60) $\displaystyle x$ $\displaystyle\mapsto F(x)$ (61) $\displaystyle x$
$\displaystyle\mapsto\mathcal{M}^{g}\ni\mathbf{prox}(c(x))$ (62)
$\displaystyle\mathcal{M},x$ $\displaystyle\mapsto
h(x),\operatorname{Jac}_{h}(x),\nabla\tilde{F}(x),\nabla^{2}L(x,\lambda).$

The second part of the oracle provides the candidate structure at point $x$.
The last part of the oracle, which requires a point _and a candidate
structure_ , provides the second-order information of $F$ required by the SQP
step.

###  5.3 Experiments

Figure 6 reports the suboptimality of the considered methods in terms of CPU
time and each marker corresponds to one iteration. All algorithms are
initialized at a point $x_{0}$ obtained by running nsBFGS for several
iterations.

Our algorithm compares favorably to nsBFGS and Gradient Sampling: it converges
in a handful of iterations and less time. Note that this happens even though
the iteration cost of our algorithm is higher than that of the other methods.
Indeed, the oracles of our method are more complex and a quadratic problem
needs to be solved, while the iteration cost of nsBFGS and Gradient Sampling
is dominated by the computation of function values and subgradients at each
trials of the linesearch.

In terms of identification, our method finds the correct manifold at the first
iteration for MaxQuad, and at the third iteration for Eigmax. From that point,
the iterates of Algorithm 1 reach machine precision in 3 iterations. This
illustrates the quadratic convergence, and supports the idea that, for
nondifferentiable problems as well, it is worth computing higher-order
information to get fast local methods.

Figure 7 allows to observe the identification of the algorithm and the quality
of the bounds of Theorem 3.8. For each iterate $x_{k}$ of Algorithm 1, we
report the current step along with the minimal and maximal steps
$\underaccent{\bar}{\step}(x_{k}),\bar{}(x_{k})$ such that
$\mathbf{prox}(c(x_{k}))$ belongs to the optimal manifold.666To better
illustrate the local behavior of our method, we also ran the algorithms with a
high precision floating type. Details and corresponding experiments can be
found in Appendix B. A first remark is that, as predicted by Theorem 4.15, the
pair $x_{k},$ satisfies the identification condition after a few iterations.
We also observe that $\bar{}(x_{k})$ is near constant and that
$\underaccent{\bar}{\step}(x_{k})$ converges to zero linearly with
$\|x_{k}-{x}^{\star}\|$, as predicted by our result. Finally, we note that
even though the initial point is not structured and away from the minimizer
($\|x_{0}-{x}^{\star}\|\approx 10^{-2}$), the initialization of ensures a
quick identification.

(a) MaxQuad

(b) Eigmax affine

Figure 6: Suboptimality vs time (s)

(a) MaxQuad

(b) Eigmax affine

Figure 7: Stepsize vs iteration

##  6 Conclusions

This paper studies the local structure of functions that write as a
composition of a nonsmooth function with a smooth mapping. When the proximity
operator of the nonsmooth function is explicitly available, we show that the
structure of the minimizer can be detected. We further use this information to
propose a local Newton method to minimize the objective harnessing the
detected structure. This method is guaranteed to identify the structure of the
minimizer and to converge quadratically. We illustrate this behavior on two
standard nonsmooth problems.

##  Appendix A The maximum and maximum eigenvalue satisfy the normal ascent
and curve properties

We show here that the maximum and the maximum eigenvalue meet the normal
ascent Property 2.19 and curve properties Property 2.23. We begin with a lemma
that simplifies verification of Property 2.23.

######  Lemma A.1.

Consider a function $g$, partly smooth at a point relative to a manifold
$\mathcal{M}^{g}$, and a smooth application
$e:\mathcal{N}\times[0,T]\to\mathcal{M}^{g}$ defined for a neighborhood
$\mathcal{N}$ of and $T>0$ such that
$e(y,0)=\operatorname{proj}_{\mathcal{M}^{g}}(y)$,
$\frac{\mathrm{d}}{\mathrm{d}t}e(y,t)|_{t=0}=-\operatorname{grad}g(\operatorname{proj}_{\mathcal{M}^{g}}(y))$.

If
$\operatorname{D}\left(t\mapsto\operatorname{proj}_{N_{e(y,t)}\mathcal{M}^{g}}(\operatorname{proj}_{\mathcal{M}}(y)-y)\right)=0$
for all $y\in\mathcal{N}$, then $g$ satisfies Property 2.23 at point .

######  Proof A.2.

We denote
$\theta(y,t)=\operatorname{proj}_{N_{e(y,t)}\mathcal{M}^{g}}(e(y,t)-y)$.
First,

(63) $\displaystyle\frac{\mathrm{d}}{\mathrm{d}t}\theta(y,t)|_{t=0}=$
$\displaystyle\operatorname{D}\left(t\mapsto\operatorname{proj}_{N_{e(y,t)}\mathcal{M}^{g}}(\operatorname{proj}_{\mathcal{M}^{g}}(y)-y)\right)$
(64)
$\displaystyle~{}~{}+\operatorname{proj}_{N_{\operatorname{proj}_{\mathcal{M}}(y)}\mathcal{M}^{g}}\left(\operatorname{D}(t\mapsto(e(y,t)-y))(0)\right),$

where the first term is null by assumption and the second is also null since
it is the normal projection of the tangent vector
$\operatorname{grad}g(\operatorname{proj}_{\mathcal{M}^{g}}(y))$. Thus,
$\frac{\mathrm{d}}{\mathrm{d}t}\theta(y,t)|_{t=0}=0$. Using this fact and
smoothness of $\theta$, Taylor’s theorem with Lagrange remainder yields, for
all $y\in\mathcal{N}$, the existence of $\bar{t}\in[0,T]$ such that, for all
$t\in[0,T]$,

(65)
$\displaystyle\theta(y,t)=\theta(y,0)+\frac{t^{2}}{2}\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\theta(y,\bar{t}).$

Therefore, for all $y\in\mathcal{N}$ and $t\in[0,T]$,

(66)
$\displaystyle\|\theta(y,t)\|\leq\|\theta(y,0)\|+\frac{t^{2}}{2}\sup_{\bar{t}\in[0,T]}\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\theta(y,\bar{t})\leq\|\theta(y,0)\|+t^{2}\tilde{L},$

where
$\tilde{L}=\sup_{y\in\mathcal{N}}\sup_{\bar{t}\in[0,T]}\frac{\mathrm{d}^{2}}{\mathrm{d}t^{2}}\theta(y,\bar{t})$.

We can now proceed with the proof of Lemma 2.24, divided into two parts
corresponding to the two cases of the result. The case $g=\max$ comes easily,
due to the polyhedral nature of the function.

######  Lemma A.3.

Consider $g=\max$, a point and the corresponding structure manifold
$\mathcal{M}^{\max}_{I}$ (of Example 2.12). Then Properties 2.19 and 2.23 hold
at .

######  Proof A.4.

_Normal ascent_ Take $y\in\mathcal{M}^{\max}_{I}$ for some active indices
$I\subset\\{1,\ldots,m\\}$. A normal direction $d\in
N_{y}\mathcal{M}^{\max}_{I}$ is such that $d_{i}=0$ for $i\notin I$ and
$\sum_{i\in I}d_{i}=0$. Thus $\max(y+td)=y_{i}+td_{i}$ with
$i=\operatorname{argmax}_{i}d_{i}$, and
$\operatorname{D}\max(y)[d]=\lim_{t\searrow 0}(\max(y+td)-\max(y))/t=d_{i}>0$
for all $d\neq 0$.

_Curve assumption_ Since the structure manifold of $\max$ are affine
subspaces, the normal spaces are equal at all points of the manifold.
Therefore the derivative of the projection at a parametrized point is null and
Lemma A.1 provides the result.

The case $g=\lambda_{\max{}}$ is not difficult _per se_ , but requires a
precise description of the geometry of the maximum eigenvalue function and its
structure manifolds; we refer to [32, 28] for the derivation of these tools.

######  Lemma A.5.

Consider $g=\lambda_{\max{}}$, a point and the corresponding structure
manifold $\mathcal{M}^{\lambda_{\max}}_{r}$ (of Example 2.13). Then Properties
2.19 and 2.23 hold at .

######  Proof A.6.

_Normal ascent_ Take $y\in\mathcal{M}^{\lambda_{\max}}_{r}$, let
$U\in\mathbb{R}^{m\times r}$ denote a basis of the first eigenspace of matrix
$y$ and $d\in N_{y}\mathcal{M}^{\lambda_{\max}}_{r}$. The normal space at
$y\in\mathcal{M}^{\lambda_{\max}}_{r}$ writes ([28, Th. 4.3, Cor. 4.8])

(67) $\displaystyle
N_{y}\mathcal{M}^{\lambda_{\max}}_{r}=\\{U(y)ZU(y)^{\top},Z\in\mathbb{S}_{r},\operatorname{trace}(Z)=0\\}.$

Therefore, $d=UZU^{\top}$ for some $Z\in\mathbb{S}_{r}$ such that
$\operatorname{trace}(Z)=0$. Let $s=U(I/r+\alpha Z)U^{\top}$ where $\alpha>0$
is small enough so that $s$ is positive definite. Since $s$ has also unit
trace, it is a subgradient of $\lambda_{\max{}}$ at $y$ [28, Th. 4.1]. Thus
$\lambda_{\max{}}^{\prime}(y;d)=\sup_{v\in\partial\lambda_{\max{}}(y)}\langle
v,d\rangle\geq\langle s,d\rangle=\langle I/r+\alpha
Z,Z\rangle=\alpha\|Z\|^{2}$, which yields $\lambda_{\max{}}^{\prime}(y;d)>0$
for any $d\in N_{y}\mathcal{M}^{\lambda_{\max}}_{r}\setminus\\{0\\}$.

_Curve assumption_ Let . For any $y\in\mathbb{S}_{m}$, we denote by $P(y)$ the
orthogonal projection on the eigenspace corresponding to the $r$ largest
eigenvalues of $y$ (counting multiplicities). This operator is smooth. We can
define a mapping $U:\mathbb{S}_{m}\to\mathbb{R}^{m\times r}$ such that:
$U(y)^{\top}U(y)=I_{r}$, $P(y)=U(y)U(y)^{\top}$, $U$ is smooth near our
reference point and its derivative at satisfies $\operatorname{D}U($. The
mapping $U$ defines a smooth orthonormal basis of the eigenspace corresponding
to the $r$ largest eigenvalues [32, p. 557]. Finally, for a point
$y^{\prime}\in\mathcal{M}^{\lambda_{\max}}_{r}$, the projection of
$d\in\mathbb{S}_{m}$ on $N_{y^{\prime}}\mathcal{M}^{\lambda_{\max}}_{r}$
writes

(68)
$\displaystyle\operatorname{proj}_{N_{y^{\prime}}\mathcal{M}^{\lambda_{\max}}_{r}}\left(d\right)=U(y^{\prime})\left\\{U(y^{\prime})^{\top}dU(y^{\prime})-\frac{1}{r}\operatorname{trace}(U(y^{\prime})^{\top}dU(y^{\prime}))I_{r}\right\\}U(y^{\prime})^{\top}.$

Now, fix $y$ near , consider the eigenbasis $U$ with reference point
$e(y,0)=\operatorname{proj}_{\mathcal{M}^{\lambda_{\max}}_{r}}(y)$. Following
Lemma A.1, let
$\nu:t\mapsto\operatorname{proj}_{N_{e(y,t)}\mathcal{M}^{\lambda_{\max}}_{r}}(d)$
with $d=\operatorname{proj}_{\mathcal{M}^{\lambda_{\max}}_{r}}(y)-y$. We can
now give an explicit expression of $\nu(t)$ and show that
$\frac{\mathrm{d}}{\mathrm{d}t}\nu(0)$ is null. Denoting $U(t)=U(e(y,t))$, we
have

(69)
$\displaystyle\nu(t)=U(t)\underbrace{\left\\{U(t)^{\top}dU(t)-\frac{1}{r}\operatorname{trace}(U(t)^{\top}dU(t))I_{r}\right\\}}_{\triangleq\chi(t)}U(t)^{\top}.$

First, as $d$ is a normal vector to $\mathcal{M}^{\lambda_{\max}}_{r}$ at
point $\operatorname{proj}_{\mathcal{M}^{\lambda_{\max}}_{r}}(y)$, there
exists $Z\in\mathbb{S}_{r}$ such that $d=U(0)ZU(0)^{\top}$. Using that
$\operatorname{D}U(0)^{\top}U(0)=0$ yields

(70)
$\displaystyle\operatorname{D}U(0)^{\top}dU(0)=\operatorname{D}U(0)^{\top}U(0)ZU(0)^{\top}U(0)=0.$

Then, one readily checks that $U(0)\operatorname{D}\chi(0)U(0)=0$.

We turn to the term $\operatorname{D}U(0)\chi(0)U(0)^{\top}$. A quick
computation from the eigen decomposition of $y$ shows that $d$ writes
$U(0)ZU(0)^{\top}$, where $Z$ is actually diagonal. Therefore,
$\chi(0)=Z-(1/r)\operatorname{trace}(Z)I_{r}$ is a diagonal matrix, so that

(71)
$\displaystyle\operatorname{D}U(0)\chi(0)U(0)^{\top}=\sum_{i=1}^{r}\chi(0)_{ii}\operatorname{D}U_{i}(0)U_{i}(0)^{\top}.$

Following [32], the differential of $t\mapsto U(e(y,t))$ at $t=0$ writes

(72)
$\displaystyle\operatorname{D}U_{i}(0)=\sum_{k=r+1}^{m}\frac{1}{\lambda_{1}-\lambda_{k}}U_{k}(0)U_{k}(0)^{\top}\eta
U_{i}(0),$

with
$\eta=\operatorname{grad}\lambda_{\max{}}(\operatorname{proj}_{\mathcal{M}^{\lambda_{\max}}_{r}}(y))$.
Using that $\lambda_{\max{}}(y)=(1/r)\sum_{i=1}^{r}U_{i}(y)^{\top}yU_{i}(y)$,
we compute the Riemannian gradient (see [6, Sec. 7.7]):

(73)
$\operatorname{grad}\lambda_{\max{}}(y)=\frac{1}{r}\sum_{i=1}^{r}U_{i}(y)^{\top}U_{i}(y).$

By orthogonality of the smooth basis of eigenvectors, the terms
$U_{k}(0)^{\top}U_{i}(0)$ vanish for all $i\in\\{1,\ldots,r\\}$ and
$k\in\\{r+1,\ldots,m\\}$. We get that
$\operatorname{D}U(0)\chi(0)U(0)^{\top}=0$, and thus that
$\operatorname{D}\nu(0)=0$. Thus, Lemma A.1 applies and yields the result.

##  Appendix B Numerical experiments in high precision

We report in Figure 8 the evolution of suboptimality versus computing time,
for the same problems and algorithms as in Section 5, but with a high
precision floating type. Indeed, the flexibility of the Julia language allows
to use the same implementation with the high precision BigFloat type, which
precision is $1.73\cdot 10^{-72}$, or the usual Float64 type, which precision
is $2.22\cdot 10^{-16}$.

(a) MaxQuad

(b) Eigmax affine

Figure 8: Suboptimality vs time (s)

## Acknowledgments

This work is funded by the ANR JCJC project STROLL (ANR-19-CE23-0008) and
MIAI@Grenoble Alpes (ANR-19-P3IA-0003). We thank the three anonymous referees
and the associate editor for their improvement suggestions that lead to a
better readability and exposition of the paper.

## References

  * [1] G. Bareilles, F. Iutzeler, and J. Malick, Newton acceleration on manifolds identified by proximal gradient methods, Mathematical Programming, (2022), https://doi.org/10.1007/s10107-022-01873-w.
  * [2] J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah, Julia: A fresh approach to numerical computing, SIAM review, 59 (2017), pp. 65–98.
  * [3] J. Bolte, Z. Chen, and E. Pauwels, The multiproximal linearization method for convex composite problems, Mathematical Programming, 182 (2020), pp. 1–36, https://doi.org/10.1007/s10107-019-01382-3.
  * [4] J. Bolte and E. Pauwels, Majorization-Minimization Procedures and Convergence of SQP Methods for Semi-Algebraic and Tame Programs, Mathematics of Operations Research, 41 (2016), pp. 442–465, https://doi.org/10.1287/moor.2015.0735.
  * [5] J.-F. Bonnans, J. C. Gilbert, C. Lemaréchal, and C. A. Sagastizábal, Numerical optimization: theoretical and practical aspects, Springer Science & Business Media, 2006.
  * [6] N. Boumal, An introduction to optimization on smooth manifolds.  To appear with Cambridge University Press, Jun 2022, https://www.nicolasboumal.net/book.
  * [7] J. V. Burke, F. E. Curtis, A. S. Lewis, M. L. Overton, and L. E. Simões, Gradient sampling methods for nonsmooth optimization, in Numerical Nonsmooth Optimization, Springer, 2020, pp. 201–225.
  * [8] A. Daniilidis, W. Hare, and J. Malick, Geometrical interpretation of the predictor-corrector type algorithms in structured optimization problems, Optimization, 55 (2006), pp. 481–503.
  * [9] D. Drusvyatskiy, A. D. Ioffe, and A. S. Lewis, Nonsmooth optimization using Taylor-like models: Error bounds, convergence, and termination criteria, Mathematical Programming, 185 (2021), pp. 357–383, https://doi.org/10.1007/s10107-019-01432-w.
  * [10] X. Y. Han and A. S. Lewis, Survey Descent: A Multipoint Generalization of Gradient Descent for Nonsmooth Optimization, (2021), p. 29.
  * [11] W. Hare and A. S. Lewis, Identifying active constraints via partial smoothness and prox-regularity, Journal of Convex Analysis, 11 (2004), pp. 251–266.
  * [12] W. Hare and C. Sagastizábal, Computing proximal points of nonconvex functions, Mathematical Programming, 116 (2009), pp. 221–258.
  * [13] C. Helmberg, M. Overton, and F. Rendl, The spectral bundle method with second-order information, Optimization Methods and Software, 29 (2014), pp. 855–876, https://doi.org/10.1080/10556788.2013.858155.
  * [14] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms, Springer Verlag, Heidelberg, 1993.  Two volumes.
  * [15] C.-p. Lee, Accelerating Inexact Successive Quadratic Approximation for Regularized Optimization Through Manifold Identification, arXiv:2012.02522 [math], (2021), https://arxiv.org/abs/2012.02522.
  * [16] J. M. Lee, Introduction to Smooth Manifolds, Graduate Texts in Mathematics, Springer-Verlag, New York, 2003, https://doi.org/10.1007/978-0-387-21752-9.
  * [17] A. Lewis and T. Tian, Identifiability, the kl property in metric spaces, and subgradient curves, arXiv preprint arXiv:2205.02868, (2022).
  * [18] A. Lewis and C. Wylie, A simple Newton method for local nonsmooth optimization, arXiv:1907.11742 [cs, math], (2019), https://arxiv.org/abs/1907.11742.
  * [19] A. S. Lewis, Active sets, nonsmoothness, and sensitivity, SIAM Journal on Optimization, 13 (2002), pp. 702–725.
  * [20] A. S. Lewis and M. L. Overton, Nonsmooth optimization via quasi-Newton methods, Mathematical Programming, 141 (2013), pp. 135–163, https://doi.org/10.1007/s10107-012-0514-2.
  * [21] A. S. Lewis and S. J. Wright, A proximal method for composite minimization, Mathematical Programming, 158 (2016), pp. 501–546.
  * [22] A. S. Lewis and S. Zhang, Partial Smoothness, Tilt Stability, and Generalized Hessians, SIAM Journal on Optimization, 23 (2013), pp. 74–94, https://doi.org/10.1137/110852103.
  * [23] R. Mifflin and C. Sagastizábal, A $\mathcal{VU}$-algorithm for convex minimization, Mathematical programming, 104 (2005), pp. 583–608.
  * [24] S. A. Miller and J. Malick, Newton methods for nonsmooth convex minimization: connections among-lagrangian, riemannian newton and sqp methods, Mathematical programming, 104 (2005), pp. 609–633.
  * [25] J. Nocedal and S. Wright, Numerical optimization, Springer Science & Business Media, 2006.
  * [26] D. Noll and P. Apkarian, Spectral bundle methods for non-convex maximum eigenvalue functions: second-order methods, Mathematical Programming, 104 (2005), pp. 729–747.
  * [27] D. Noll and P. Apkarian, Spectral bundle methods for non-convex maximum eigenvalue functions: Second-order methods, Mathematical Programming, 104 (2005), pp. 729–747, https://doi.org/10.1007/s10107-005-0635-y.
  * [28] F. Oustry, The $\mathcal{U}$-Lagrangian of the Maximum Eigenvalue Function, SIAM Journal on Optimization, 9 (1999), pp. 526–549, https://doi.org/10.1137/S1052623496311776.
  * [29] R. T. Rockafellar and R. J.-B. Wets, Variational analysis, vol. 317, Springer Science & Business Media, 2009.
  * [30] C. Sagastizábal, Composite proximal bundle method, Mathematical Programming, 140 (2013), pp. 189–233, https://doi.org/10.1007/s10107-012-0600-5.
  * [31] A. Shapiro, On a Class of Nonsmooth Composite Functions, Mathematics of Operations Research, 28 (2003), pp. 677–692, https://doi.org/10.1287/moor.28.4.677.20512.
  * [32] A. Shapiro and M. K. H. Fan, On Eigenvalue Optimization, SIAM Journal on Optimization, 5 (1995), pp. 552–569, https://doi.org/10.1137/0805028.
  * [33] R. S. Womersley and R. Fletcher, An algorithm for composite nonsmooth optimization problems, Journal of Optimization Theory and Applications, 48 (1986), pp. 493–523, https://doi.org/10.1007/BF00940574.