#  Convergence Properties of Monotone and Nonmonotone Proximal Gradient
Methods Revisited

Christian Kanzow University of Würzburg, Institute of Mathematics, 97074
Würzburg, Germany<EMAIL_ADDRESS>ORCID:
0000-0003-2897-2509 Patrick Mehlitz Brandenburgische Technische Universität
Cottbus-Senftenberg, Institute of Mathematics, 03046 Cottbus, Germany,
<EMAIL_ADDRESS>ORCID: 0000-0002-9355-850X, University of Mannheim, School of
Business Informatics and Mathematics, 68159 Mannheim, Germany

(August 27, 2024)

Abstract. Composite optimization problems, where the sum of a smooth and a
merely lower semicontinuous function has to be minimized, are often tackled
numerically by means of proximal gradient methods as soon as the lower
semicontinuous part of the objective function is of simple enough structure.
The available convergence theory associated with these methods (mostly)
requires the derivative of the smooth part of the objective function to be
(globally) Lipschitz continuous, and this might be a restrictive assumption in
some practically relevant scenarios. In this paper, we readdress this
classical topic and provide convergence results for the classical (monotone)
proximal gradient method and one of its nonmonotone extensions which are
applicable in the absence of (strong) Lipschitz assumptions. This is possible
since, for the price of forgoing convergence rates, we omit the use of
descent-type lemmas in our analysis.

Keywords. Non-Lipschitz Optimization, Nonsmooth Optimization, Proximal
Gradient Method

AMS subject classifications. 49J52, 90C30

##  1 Introduction

In this paper, we address the classical problem of minimizing the sum of a
smooth function $f$ and a nonsmooth function $\phi$, also known under the name
_composite optimization_. This setting received much attention throughout the
last years due to its inherent practical relevance in, e.g., machine learning,
data compression, matrix completion, and image processing, see e.g. [6, 13,
14, 20, 27, 28].

A standard technique for the solution of composite optimization problems is
the proximal gradient method, introduced by Fukushima and Mine [21] and
popularized e.g. by Combettes and Wajs in [18]. A particular instance of this
method is the celebrated iterative shrinkage/threshold algorithm (ISTA), see,
e.g. [5]. A summary of existing results for the case where the nonsmooth term
$\phi$ is defined by a convex function is given in the monograph by Beck [4].

The proximal gradient method can also be interpreted as a forward-backward
splitting method, see [12, 31] for its origins and [3] for a modern view, and
is able to handle problems where the nonsmooth term $\phi$ is given by a
merely lower semicontinuous function, see, e.g. the seminal works [1, 8].
These references also provide convergence and rate-of-convergence results by
using the popular _descent lemma_ together with the celebrated
_Kurdyka–Łojasiewicz property_.

To the best of our knowledge, however, the majority of available convergence
results for proximal gradient methods assume that the smooth term $f$ is
continuously differentiable with a globally Lipschitz continuous gradient (or
they require local Lipschitzness together with a bounded level set which,
again, implies the global Lipschitz continuity on this level set). This
requirement, which is the essential ingredient for the classical descent
lemma, is often satisfied for standard applications of the proximal gradient
method in data science and image processing, where $f$ appears to be a
quadratic function.

In this paper, we aim to get rid of this global Lipschitz condition. This is
motivated by the fact that the algorithmic application we have in mind does
not satisfy this Lipschitz property since the smooth term $f$ corresponds to
the augmented Lagrangian function of a general nonlinear constrained
optimization problem, which rarely has a globally Lipschitz continuous
gradient or a bounded level set. The proximal gradient method will be used to
solve the resulting subproblems which forces us to generalize the convergence
theory up to reasonable assumptions which are likely to hold in our framework.
We refer the interested reader to [15, 23, 25, 19] where such augmented
Lagrangian _proximal_ methods are investigated.

Numerically, a nonmonotone version of the proximal gradient method is often
preferred. Based on ideas by Grippo et al. [22] in the context of smooth
unconstrained optimization problems, Wright et al. [34] developed a
nonmonotone proximal gradient method for composite optimization problems known
under the name SpaRSA. In their paper, the authors assume that the nonsmooth
part $\phi$ of the objective function is convex. Almost simultaneously, the
authors of [7] presented a nonmonotone projected gradient method for the
minimization of a differentiable function over a convex set. Their findings
can be interpreted as a special case of the results from [34] where $\phi$
equals the indicator of a convex set. The ideas from [7, 34] were subsequently
generalized in the papers [15, 16] where the proximal gradient method is used
as a subproblem solver within an augmented Lagrangian and penalization scheme,
respectively. However, the authors did not address the aforementioned
problematic lack of Lipschitzness in these papers which causes their
convergence theory to be barely applicable in their algorithmic framework. In
[26, 33], the authors present nonmonotone extensions of ISTA which can handle
merely lower semicontinuous terms in the objective function. Again, for the
convergence analysis, global Lipschitzness of the smooth term’s derivative is
assumed. Due to its practical importance, we therefore aim to provide a
convergence theory for the nonmonotone proximal gradient method without using
any Lipschitz assumption.

In the seminal paper [2], the authors consider the composite optimization
problem with both terms being convex, but without a global Lipschitz
assumption for the gradient of the smooth part $f$. They get suitable rate-of-
convergence results for the iterates generated by a Bregman-type proximal
gradient method using only a local Lipschitz condition. In addition, however,
they require that there is a constant $L>0$ such that $Lh-f$ is convex, where
$h$ is a convex function which defines the Bregman distance (in our setting,
$h$ equals the squared norm). Some examples indicate that this convexity-type
condition is satisfied in many practically relevant situations. Subsequently,
this approach was generalized to the nonconvex setting in [9] using, once
again, a local Lipschitz assumption only, as well as the slighty stronger
assumption (in order to deal with the nonconvexity) that there exist $L>0$ and
a convex function $h$ such that both $Lh-f$ and $Lh+f$ are convex. Note that
the constant $L$ plays a central role in the design of the corresponding
proximal-type methods. Particularly, it is used explicitly for the choice of
stepsizes. Finally, the very recent paper [17] proves global convergence
results under a local Lipschitz assumption (without the additional convexity-
type condition), but assumes that the iterates and stepsizes of the underlying
proximal gradient method remain bounded.

To the best of our knowledge, this is the current state-of-the-art regarding
the convergence properties of proximal gradient methods. The aim of this paper
is slightly different, since we do not provide rate-of-convergence results,
but conditions which guarantee accumulation points to be suitable stationary
points of the composite optimization problem. This is the essential feature of
the proximal gradient method which, for example, is exploited in [15, 25, 19]
to develop augmented Lagrangian proximal methods. We also stress that, in this
particular situation, the above assumption that $Lh\pm f$ is convex for some
$L>0$ is often violated unless we are dealing with linear constraints only.

Our analysis does not require a global Lipschitz assumption and is not based
on the crucial descent lemma, contrasting [2, 9] mentioned above. The results
show that we can get stationary accumulation points only under a local
Lipschitz assumption and, depending on the properties of $\phi$, sometimes
even without any Lipschitz condition. In any case, a convexity-type condition
like $Lh\pm f$ being convex for some constant $L$ is not required at all.
Moreover, the implementation of our proximal gradient method does not need any
knowledge of the size of any Lipschitz-type constant.

Since the aim of this paper is to get a better understanding of the
theoretical convergence properties of both monotone and nonmonotone proximal
gradient methods, and since these methods have already been applied
numerically to a large variety of problems, we do not include any numerical
results in this paper.

Let us recall that we are mainly interested in conditions ensuring that
accumulation points of sequences produced by the proximal gradient method are
stationary. The main contributions of this paper show that this property holds
(neglecting a few technical conditions) for the monotone proximal gradient
method if either the smooth function $f$ is continuously differentiable and
the nonsmooth function $\phi$ is continuous on its domain (e.g., this
assumption holds for a constrained optimization problem where $\phi$
corresponds to the indicator function of a nonempty and closed set), or if $f$
is differentiable with a locally Lipschitz continuous derivative and $\phi$ is
an arbitrary lower semicontinuous function. Corresponding statements for the
nonmonotone proximal gradient method require stronger assumptions, basically
the uniform continuity of the objective function on a level set. That,
however, is a standard assumption in the literature dealing with nonmonotone
stepsize rules.

The paper is organized as follows: In Section 2, we give a detailed statement
of the composite optimization problem and provide some necessary background
material from variational analysis. The convergence properties of the monotone
and nonmonotone proximal gradient method are then discussed in Sections 3 and
4, respectively. We close with some final remarks in Section 5.

##  2 Problem Setting and Preliminaries

We consider the _composite_ optimization problem

$\min_{x}\ \psi(x):=f(x)+\phi(x),\quad\quad x\in\mathbb{X},$ (P)

where $f\colon\mathbb{X}\to\mathbb{R}$ is continuously differentiable,
$\phi\colon\mathbb{X}\to\overline{\mathbb{R}}:=\mathbb{R}\cup\\{\infty\\}$ is
lower semicontinuous (possibly infinite-valued and nondifferentiable), and
$\mathbb{X}$ denotes a Euclidean space, i.e., a real and finite-dimensional
Hilbert space. We assume that the domain
$\operatorname{dom}\phi:=\\{x\in\mathbb{X}\,|\,\phi(x)<\infty\\}$ of $\phi$ is
nonempty to rule out trivial situations. In order to minimize the function
$\psi\colon\mathbb{X}\to\overline{\mathbb{R}}$ in (P), it seems reasonable to
exploit the composite structure of $\psi$, i.e., to rely on the
differentiability of $f$ on the one hand, and on some beneficial structural
properties of $\phi$ on the other one. This is the idea behind splitting
methods.

Throughout the paper, the Euclidean space $\mathbb{X}$ will be equipped with
the inner product
$\langle\cdot,\cdot\rangle\colon\mathbb{X}\times\mathbb{X}\to\mathbb{R}$ and
the associated norm $\left\|\cdot\right\|$. For some set $A\subset\mathbb{X}$
and some point $x\in\mathbb{X}$, we make use of $A+x=x+A:=\\{x+a\,|\,a\in
A\\}$ for the purpose of simplicity. For some sequence
$\\{x^{k}\\}\subset\mathbb{X}$ and $x\in\mathbb{X}$, $x^{k}\to_{\phi}x$ means
that $x^{k}\to x$ and $\phi(x^{k})\to\phi(x)$. The continuous linear operator
$f^{\prime}(x)\colon\mathbb{X}\to\mathbb{R}$ denotes the derivative of $f$ at
$x\in\mathbb{X}$, and we will make use of $\nabla f(x):=f^{\prime}(x)^{*}1$
where $f^{\prime}(x)^{*}\colon\mathbb{R}\to\mathbb{X}$ is the adjoint of
$f^{\prime}(x)$. This way, $\nabla f$ is a mapping from $\mathbb{X}$ to
$\mathbb{X}$. Furthermore, we find $f^{\prime}(x)d=\langle\nabla
f(x),d\rangle$ for each $d\in\mathbb{X}$.

The following concepts are standard in variational analysis, see e.g. [29,
32]. Let us fix some point $x\in\operatorname{dom}\phi$. Then

$\widehat{\partial}\phi(x):=\left\\{\eta\in\mathbb{X}\,\middle|\,\liminf\limits_{y\to
x}\frac{\phi(y)-\phi(x)-\langle\eta,y-x\rangle}{\left\|y-x\right\|}\geq
0\right\\}$

is called the regular (or Fréchet) subdifferential of $\phi$ at $x$.
Furthermore, the set

$\partial\phi(x):=\left\\{\eta\in\mathbb{X}\,\middle|\,\exists\\{x^{k}\\},\\{\eta^{k}\\}\subset\mathbb{X}\colon
x^{k}\to_{\phi}x,\,\eta^{k}\to\eta,\,\eta^{k}\in\widehat{\partial}\phi(x^{k})\,\forall
k\in\mathbb{N}\right\\}$

is well known as the limiting (or Mordukhovich) subdifferential of $\phi$ at
$x$. Clearly, we always have $\widehat{\partial}\phi(x)\subset\partial\phi(x)$
by construction. Whenever $\phi$ is convex, equality holds, and both
subdifferentials coincide with the subdifferential of convex analysis, i.e.,

$\widehat{\partial}\phi(x)=\partial\phi(x)=\\{\eta\in\mathbb{X}\,|\,\forall
y\in\mathbb{X}\colon\,\phi(y)\geq\phi(x)+\langle\eta,y-x\rangle\\}$

holds in this situation. It can be seen right from the definition that
whenever $x^{*}\in\operatorname{dom}\phi$ is a local minimizer of $\phi$, then
$0\in\widehat{\partial}\phi(x^{*})$, which is referred to as Fermat’s rule,
see [29, Proposition 1.30(i)].

Given $x\in\operatorname{dom}\phi$, the limiting subdifferential has the
important robustness property

$\left\\{\eta\in\mathbb{X}\,\middle|\,\exists\\{x^{k}\\},\\{\eta^{k}\\}\subset\mathbb{X}\colon\,x^{k}\to_{\phi}x,\,\eta^{k}\to\eta,\,\eta^{k}\in\partial\phi(x^{k})\,\forall
k\in\mathbb{N}\right\\}\subset\partial\phi(x),$ (2.1)

see [29, Proposition 1.20]. Clearly, the converse inclusion $\supset$ is also
valid by definition of the limiting subdifferential. Note that in situations
where $\phi$ is discontinuous at $x$, the requirement $x^{k}\to_{\phi}x$ in
the definition of the set on the left-hand side in (2.1) is strictly
necessary. In fact, the usual outer semicontinuity in the sense of set-valued
mappings, given by

$\left\\{\eta\in\mathbb{X}\,\middle|\,\exists\\{x^{k}\\},\\{\eta^{k}\\}\subset\mathbb{X}\colon\,x^{k}\to
x,\,\eta^{k}\to\eta,\,\eta^{k}\in\partial\phi(x^{k})\,\forall
k\in\mathbb{N}\right\\}\subset\partial\phi(x),$ (2.2)

would be a much stronger condition in this situation and does not hold in
general.

Whenever $x\in\operatorname{dom}\phi$ is fixed, the sum rule

$\widehat{\partial}(f+\phi)(x)=\nabla f(x)+\widehat{\partial}\phi(x)$ (2.3)

holds, see [29, Proposition 1.30(ii)]. Thus, due to Fermat’s rule, whenever
$x^{*}\in\operatorname{dom}\phi$ is a local minimizer of $f+\phi$, we have
$0\in\nabla f(x^{*})+\widehat{\partial}\phi(x^{*})$. This condition is
potentially more restrictive than $0\in\nabla f(x^{*})+\partial\phi(x^{*})$
which, naturally, also serves as a necessary optimality condition for (P).
However, the latter is more interesting from an algorithmic point of view as
it is well known from the literature on splitting methods comprising nonconvex
functions $\phi$. If $\phi$ is convex, there is no difference between those
stationarity conditions.

Throughout the paper, a point $x^{*}\in\operatorname{dom}\phi$ satisfying
$0\in\nabla f(x^{*})+\partial\phi(x^{*})$ will be called a Mordukhovich-
stationary (M-stationary for short) point of (P) due to the appearance of the
limiting subdifferential. In the literature, the name _limiting critical
point_ is used as well. We close this section with two special instances of
problem (P) and comment on the corresponding M-stationary conditions.

###### Remark 2.1.

Consider the constrained optimization problem

$\min_{x}\ f(x)\quad\text{subject to}\quad x\in C$

for a continuously differentiable function $f\colon\mathbb{X}\to\mathbb{R}$
and a nonempty and closed (not necessarily convex) set $C\subset\mathbb{X}$.
This problem is equivalent to the unconstrained problem (P) by setting
$\phi:=\delta_{C}$, where $\delta_{C}\colon\mathbb{X}\to\overline{\mathbb{R}}$
denotes the indicator function of the set $C$, vanishing on $C$ and taking the
value $\infty$ on $\mathbb{X}\setminus C$, which is lower semicontinuous due
to the assumptions regarding $C$. The corresponding M-stationarity condition
is given by

$0\in\nabla f(x^{*})+\partial\delta_{C}(x^{*})=\nabla
f(x^{*})+\mathcal{N}_{C}(x^{*}),$

where $\mathcal{N}_{C}(x^{*})$ denotes the _limiting_ (or _Mordukhovich_)
_normal cone_ , see [29, Proposition 1.19].

###### Remark 2.2.

Consider the more general constrained optimization problem

$\min_{x}\ f(x)+\varphi(x)\quad\text{subject to}\quad x\in C$

with $f\colon\mathbb{X}\to\mathbb{R}$ and $C\subset\mathbb{X}$ as in Remark
2.1, and $\varphi\colon\mathbb{X}\to\overline{\mathbb{R}}$ being another lower
semicontinuous function (which might represent a regularization, penalty, or
sparsity-promoting term, for example). Setting $\phi:=\varphi+\delta_{C}$, we
obtain once again an optimization problem of the form (P). The corresponding
M-stationarity condition is given by

$0\in\nabla f(x^{*})+\partial\phi(x^{*})=\nabla
f(x^{*})+\partial(\varphi+\delta_{C})(x^{*}).$

Unfortunately, the sum rule

$\partial(\varphi+\delta_{C})(x^{*})\subset\partial\varphi(x^{*})+\partial\delta_{C}(x^{*})=\partial\varphi(x^{*})+\mathcal{N}_{C}(x^{*})$

does not hold in general. However, for locally Lipschitz functions $\varphi$,
for example, it applies, see [29, Theorems 1.22, 2.19]. Note that the
resulting stationarity condition

$0\in\nabla f(x^{*})+\partial\varphi(x^{*})+\mathcal{N}_{C}(x^{*})$

might be slightly weaker than M-stationarity as introduced above. Related
discussions can be found in [24, Section 3].

##  3 Monotone Proximal Gradient Method

We first investigate a monotone version of the proximal gradient method
applied to the composite optimization problem (P) with $f$ being continuously
differentiable and $\phi$ being lower semicontinuous. Recall that the
corresponding M-stationarity condition is given by

$0\in\nabla f(x)+\partial\phi(x).$

Our aim is to find, at least approximately, an M-stationary point of (P). The
following algorithm is the classical proximal gradient method for this class
of problems. Since we will also consider a nonmonotone variant of this
algorithm in the following section, we call this the monotone proximal
gradient method.

###### Algorithm 3.1 (Monotone Proximal Gradient Method).

0:
$\tau>1,0<\gamma_{\min}\leq\gamma_{\max}<\infty,\delta\in(0,1),x^{0}\in\operatorname{dom}\phi$

1: Set $k:=0$.

2: while A suitable termination criterion is violated at iteration $k$ do

3: Choose $\gamma_{k}^{0}\in[\gamma_{\min},\gamma_{\max}]$.

4: For $i=0,1,2,\ldots$, compute a solution $x^{k,i}$ of  $\min_{x}\
f(x^{k})+\langle\nabla
f(x^{k}),x-x^{k}\rangle+\frac{\gamma_{k,i}}{2}\|x-x^{k}\|^{2}+\phi(x),\quad
x\in\mathbb{X}$ (3.1) with $\gamma_{k,i}:=\tau^{i}\gamma_{k}^{0}$, until the
acceptance criterion
$\psi(x^{k,i})\leq\psi(x^{k})-\delta\frac{\gamma_{k,i}}{2}\|x^{k,i}-x^{k}\|^{2}$
(3.2) holds.

5: Denote by $i_{k}:=i$ the terminal value, and set
$\gamma_{k}:=\gamma_{k,i_{k}}$ and $x^{k+1}:=x^{k,i_{k}}$.

6: Set $k\leftarrow k+1$.

7: end while

8: return $x^{k}$

The convergence theory requires some technical assumptions.

###### Assumption 3.2.

  1. (a)

The function $\psi$ is bounded from below on $\operatorname{dom}\phi$.

  2. (b)

The function $\phi$ is bounded from below by an affine function.

Assumption 3.2 (a) is a reasonable condition regarding the given composite
optimization problem, whereas Assumption 3.2 (b) is essentially a statement
relevant for the subproblems from (3.1). In particular, Assumption 3.2 (b)
implies that the quadratic objective function of the subproblems (3.1) are,
for fixed $k,i\in\mathbb{N}$, coercive, and therefore always attain a solution
$x^{k,i}$ (which, however, may not be unique).

The subsequent convergence theory assumes implicitly that Algorithm 3.1
generates an infinite sequence.

We first establish that the stepsize rule in 4 of Algorithm 3.1 is always
finite.

###### Lemma 3.3.

Consider a fixed iteration $k$ of Algorithm 3.1, assume that $x^{k}$ is not an
M-stationary point of (P), and suppose that Assumption 3.2 (b) holds. Then the
inner loop in 4 of Algorithm 3.1 is finite, i.e., we have
$\gamma_{k}=\gamma_{k,i_{k}}$ for some finite index
$i_{k}\in\\{0,1,2,\ldots\\}$.

###### Proof.

Suppose that the inner loop of Algorithm 3.1 does not terminate after a finite
number of steps in iteration $k$. Recall that $x^{k,i}$ is a solution of
(3.1). Therefore, we get

$\langle\nabla
f(x^{k}),x^{k,i}-x^{k}\rangle+\frac{\gamma_{k,i}}{2}\|x^{k,i}-x^{k}\|^{2}+\phi(x^{k,i})\leq\phi(x^{k}).$
(3.3)

Noting that $\gamma_{k,i}\to\infty$ for $i\to\infty$ and using Assumption 3.2
(b), we obtain $x^{k,i}\to x^{k}$ for $i\to\infty$. Taking the limit
$i\to\infty$ therefore yields

$\phi(x^{k})\leq\liminf_{i\to\infty}\phi(x^{k,i})\leq\limsup_{i\to\infty}\phi(x^{k,i})\leq\phi(x^{k}),$

where the first estimate follows from the lower semicontinuity of $\phi$ and
the final inequality is a consequence of (3.3). Therefore, we have

$\phi(x^{k,i})\to\phi(x^{k})\quad\text{for }i\to\infty.$ (3.4)

We claim that

$\liminf_{i\to\infty}\gamma_{k,i}\|x^{k,i}-x^{k}\|>0.$ (3.5)

Assume, by contradiction, that there is a subsequence $i_{l}\to\infty$ such
that

$\liminf_{l\to\infty}\gamma_{k,i_{l}}\|x^{k,i_{l}}-x^{k}\|=0.$ (3.6)

Since $x^{k,i_{l}}$ is optimal for (3.1), Fermat’s rule and the sum rule (2.3)
yield

$0\in\nabla
f(x^{k})+\gamma_{k,i_{l}}(x^{k,i_{l}}-x^{k})+\widehat{\partial}\phi(x^{k,i_{l}})$
(3.7)

for all $l\in\mathbb{N}$. Taking the limit $l\to\infty$ while using (3.4) and
(3.6), we obtain

$0\in\nabla f(x^{k})+\partial\phi(x^{k}),$

which means that $x^{k}$ is already an M-stationary point of (P). This
contradiction shows that (3.5) holds. Hence, there is a constant $c>0$ such
that

$\gamma_{k,i}\|x^{k,i}-x^{k}\|\geq c$

holds for all large enough $i\in\mathbb{N}$. In particular, this implies

$(1-\delta)\frac{\gamma_{k,i}}{2}\|x^{k,i}-x^{k}\|^{2}\geq\frac{1-\delta}{2}c\|x^{k,i}-x^{k}\|\geq
o\big{(}\|x^{k,i}-x^{k}\|\big{)}$ (3.8)

for all sufficiently large $i\in\mathbb{N}$. Furthermore, (3.3) shows that

$\langle\nabla
f(x^{k}),x^{k,i}-x^{k}\rangle+\phi\big{(}x^{k,i}\big{)}-\phi(x^{k})\leq-\frac{\gamma_{k,i}}{2}\|x^{k,i}-x^{k}\|^{2}.$
(3.9)

Using a Taylor expansion of the function $f$ and exploiting (3.8), (3.9), we
obtain

$\displaystyle\psi(x^{k,i})-\psi(x^{k})$
$\displaystyle=f(x^{k,i})+\phi(x^{k,i})-f(x^{k})-\phi(x^{k})$
$\displaystyle=\langle\nabla
f(x^{k}),x^{k,i}-x^{k}\rangle+\phi(x^{k,i})-\phi(x^{k})+o\big{(}\|x^{k,i}-x^{k}\|\big{)}$
$\displaystyle\leq-\frac{\gamma_{k,i}}{2}\|x^{k,i}-x^{k}\|^{2}+o\big{(}\|x^{k,i}-x^{k}\|\big{)}$
$\displaystyle\leq-\delta\frac{\gamma_{k,i}}{2}\|x^{k,i}-x^{k}\|^{2}$

for all $i\in\mathbb{N}$ sufficiently large. This, however, means that the
acceptance criterion (3.2) is valid for sufficiently large $i\in\mathbb{N}$,
contradicting our assumption. This completes the proof. ∎

Let us note that the above proof actually shows that the inner loop from 4 of
Algorithm 3.1 is either finite, or we have
$\gamma_{k,i_{l}}\|x^{k,i_{l}}-x^{k}\|\to 0$ along a subsequence
$i_{l}\to\infty$. Rewriting (3.7) by means of

$\nabla f(x^{k,i_{l}})-\nabla
f(x^{k})+\gamma_{k,i_{l}}(x^{k}-x^{k,i_{l}})\in\nabla
f(x^{k,i_{l}})+\widehat{\partial}\phi(x^{k,i_{l}})$ (3.10)

and recalling that $\nabla f\colon\mathbb{X}\to\mathbb{X}$ is continuous
motivates to also use

$\|\nabla f(x^{k,i})-\nabla
f(x^{k})+\gamma_{k,i}(x^{k}-x^{k,i})\|\leq\tau_{\textup{abs}}$

for some $\tau_{\textup{abs}}>0$ as a termination criterion of the inner loop
since this encodes, in some sense, approximate M-stationarity of $x^{k,i}$ for
(P) (note that taking the limit $l\to\infty$ in (3.10) would recover the
limiting subdifferential of $\phi$ at $x^{k}$ since we have
$x^{k,i_{l}}\to_{\phi}x^{k}$ by (3.4)).

A critical step for the convergence theory of Algorithm 3.1 is provided by the
following result.

###### Proposition 3.4.

Let Assumption 3.2 hold. Then each sequence $\\{x^{k}\\}$ generated by
Algorithm 3.1 satisfies $\|x^{k+1}-x^{k}\|\to 0$.

###### Proof.

First recall that the sequence $\\{x^{k}\\}$ is well-defined by Lemma 3.3.
Using the acceptance criterion (3.2), we get

$\psi(x^{k+1})\leq\psi(x^{k})-\delta\frac{\gamma_{k}}{2}\|x^{k+1}-x^{k}\|^{2}\leq\psi(x^{k})$
(3.11)

for all $k\in\mathbb{{N}}$. Hence, the sequence $\\{\psi(x^{k})\\}$ is
monotonically decreasing. Since $\psi$ is bounded from below on
$\operatorname{dom}\phi$ by Assumption 3.2 (a) and
$\\{x^{k}\\}\subset\operatorname{dom}\phi$, it follows that this sequence is
convergent. Therefore, (3.11) implies

$\gamma_{k}\|x^{k+1}-x^{k}\|^{2}\to 0\quad\text{for }k\to\infty.$

Hence the assertion follows from the fact that, by construction, we have
$\gamma_{k}\geq\gamma_{\min}>0$ for all $k\in\mathbb{N}$. ∎

A refined analysis gives the following result.

###### Proposition 3.5.

Let Assumption 3.2 hold, let $\\{x^{k}\\}$ be a sequence generated by
Algorithm 3.1, and let $\\{x^{k}\\}_{K}$ be a subsequence converging to some
point $x^{*}$. Then $\gamma_{k}\|x^{k+1}-x^{k}\|\to_{K}0$ holds.

###### Proof.

If the subsequence $\\{\gamma_{k}\\}_{K}$ is bounded, the statement follows
immediately from Proposition 3.4. The remaining part of this proof therefore
assumes that this subsequence is unbounded. Without loss of generality, we may
assume that $\gamma_{k}\to_{K}\infty$ and that the acceptance criterion (3.2)
is violated in the first iteration of the inner loop for each $k\in K$. Then,
for $\hat{\gamma}_{k}:=\gamma_{k}/\tau$, $k\in K$, we also have
$\hat{\gamma}_{k}\to_{K}\infty$, but the corresponding vector
$\hat{x}^{k}:=x^{k,i_{k}-1}$ does not satisfy the stepsize condition from
(3.2), i.e., we have

$\psi(\hat{x}^{k})>\psi(x^{k})-\delta\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}\quad\forall
k\in K.$ (3.12)

On the other hand, since $\hat{x}^{k}$ solves the corresponding subproblem
(3.1) with $\hat{\gamma}_{k}=\gamma_{k,i_{k}-1}$, we have

$\langle\nabla
f(x^{k}),\hat{x}^{k}-x^{k}\rangle+\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}+\phi(\hat{x}^{k})-\phi(x^{k})\leq
0.$ (3.13)

We claim that this, in particular, implies $\hat{x}^{k}\to_{K}x^{*}$. In fact,
using (3.13), the Cauchy-Schwarz inequality, and the monotonicity of
$\\{\psi(x^{k})\\}$, we obtain

$\displaystyle\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}$
$\displaystyle\leq\|\nabla
f(x^{k})\|\|\hat{x}^{k}-x^{k}\|+\phi(x^{k})-\phi(\hat{x}^{k})$
$\displaystyle=\|\nabla
f(x^{k})\|\|\hat{x}^{k}-x^{k}\|+\psi(x^{k})-f(x^{k})-\phi(\hat{x}^{k})$
$\displaystyle\leq\|\nabla
f(x^{k})\|\|\hat{x}^{k}-x^{k}\|+\psi(x^{0})-f(x^{k})-\phi(\hat{x}^{k}).$

Since $f$ is continuously differentiable and $-\phi$ is bounded from above by
an affine function in view of Assumption 3.2 (b), this implies
$\|\hat{x}^{k}-x^{k}\|\to_{K}0$. In fact, if $\\{\|\hat{x}^{k}-x^{k}\|\\}_{K}$
would be unbounded, then the left-hand side would grow more rapidly than the
right-hand side, and if $\\{\|\hat{x}^{k}-x^{k}\|\\}_{K}$ would be bounded,
but staying away, at least on a subsequence, from zero by a positive number,
the right-hand side would be bounded, whereas the left-hand side would be
unbounded on the corresponding subsequence.

Now, by the mean-value theorem, there exists $\xi^{k}$ on the line segment
connecting $x^{k}$ with $\hat{x}^{k}$ such that

$\displaystyle\psi(\hat{x}^{k})-\psi(x^{k})$
$\displaystyle=f(\hat{x}^{k})+\phi(\hat{x}^{k})-f(x^{k})-\phi(x^{k})$ (3.14)
$\displaystyle=\langle\nabla
f(\xi^{k}),\hat{x}^{k}-x^{k}\rangle+\phi(\hat{x}^{k})-\phi(x^{k}).$

Substituting the expression $\phi(\hat{x}^{k})-\phi(x^{k})$ from (3.14) into
(3.13) yields

$\langle\nabla f(x^{k})-\nabla
f(\xi^{k}),\hat{x}^{k}-x^{k}\rangle+\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}+\psi(\hat{x}^{k})-\psi(x^{k})\leq
0.$

Exploiting (3.12), we therefore obtain

$\displaystyle\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}$
$\displaystyle\leq-\langle\nabla f(x^{k})-\nabla
f(\xi^{k}),\hat{x}^{k}-x^{k}\rangle+\psi(x^{k})-\psi(\hat{x}^{k})$
$\displaystyle\leq\|\nabla f(x^{k})-\nabla
f(\xi^{k})\|\|\hat{x}^{k}-x^{k}\|+\delta\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2},$

which can be rewritten as

$(1-\delta)\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|\leq\|\nabla
f(x^{k})-\nabla f(\xi^{k})\|$ (3.15)

(note that $\hat{x}^{k}\neq x^{k}$ in view of (3.12)). Since
$x^{k}\to_{K}x^{*}$ (by assumption) and $\hat{x}^{k}\to_{K}x^{*}$ (by the
previous part of this proof), we also get $\xi^{k}\to_{K}x^{*}$. Using
$\delta\in(0,1)$ and the continuous differentiability of $f$, it follows from
(3.15) that $\hat{\gamma}_{k}\|\hat{x}^{k}-x^{k}\|\to_{K}0$.

Finally, exploiting the fact that $x^{k+1}$ and $\hat{x}^{k}$ are solutions of
the subproblems (3.1) with parameters $\gamma_{k}$ and $\hat{\gamma}_{k}$,
respectively, we find

$\displaystyle\langle\nabla f(x^{k}),x^{k+1}-x^{k}\rangle$
$\displaystyle+\frac{\gamma_{k}}{2}\|x^{k+1}-x^{k}\|^{2}+\phi(x^{k+1})$
$\displaystyle\leq\langle\nabla
f(x^{k}),\hat{x}^{k}-x^{k}\rangle+\frac{\gamma_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}+\phi(\hat{x}^{k}),$
$\displaystyle\langle\nabla f(x^{k}),\hat{x}^{k}-x^{k}\rangle$
$\displaystyle+\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}+\phi(\hat{x}^{k})$
$\displaystyle\leq\langle\nabla
f(x^{k}),x^{k+1}-x^{k}\rangle+\frac{\hat{\gamma}_{k}}{2}\|x^{k+1}-x^{k}\|^{2}+\phi(x^{k+1}).$

Adding these two inequalities and noting that
$\gamma_{k}=\tau\hat{\gamma}_{k}>\hat{\gamma}_{k}$ yields
$\|x^{k+1}-x^{k}\|\leq\|\hat{x}^{k}-x^{k}\|$ and, therefore,

$\gamma_{k}\|x^{k+1}-x^{k}\|=\tau\hat{\gamma}_{k}\|x^{k+1}-x^{k}\|\leq\tau\hat{\gamma}_{k}\|\hat{x}^{k}-x^{k}\|\to_{K}0.$

This completes the proof. ∎

The above technique of proof implies a boundedness result for the sequence
$\\{\gamma_{k}\\}_{K}$ if $\nabla f$ satisfies a local Lipschitz property
around the associated accumulation point of iterates. This observation is
stated explicitly in the following result.

###### Corollary 3.6.

Let Assumption 3.2 hold, let $\\{x^{k}\\}$ be a sequence generated by
Algorithm 3.1, let $\\{x^{k}\\}_{K}$ be a subsequence converging to some point
$x^{*}$, and assume that $\nabla f\colon\mathbb{X}\to\mathbb{X}$ is locally
Lipschitz continuous around $x^{*}$. Then the corresponding subsequence
$\\{\gamma_{k}\\}_{K}$ is bounded.

###### Proof.

We may argue as in the proof of Proposition 3.5. Hence, on the contrary,
assume that $\gamma_{k}\to_{K}\infty$. For each $k\in K$, define
$\hat{\gamma}_{k}$ and $\hat{x}^{k}$ as in that proof, and let $L>0$ denote
the local Lipschitz constant of $\nabla f$ around $x^{*}$. Recall that
$x^{k}\to_{K}x^{*}$ (by assumption) and $\hat{x}^{k}\to_{K}x^{*}$ (from the
proof of Proposition 3.5). Exploiting (3.15), we therefore obtain

$(1-\delta)\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|\leq
L\|\hat{x}^{k}-\xi^{k}\|\leq L\|\hat{x}^{k}-x^{k}\|$

for all $k\in K$ sufficiently large, using the fact that $\xi^{k}$ is on the
line segment between $x^{k}$ and $\hat{x}^{k}$. Since
$\hat{\gamma}_{k}\to_{K}\infty$ and $\hat{x}^{k}\neq x^{k}$, see once again
(3.12), this gives a contradiction. Hence, $\\{\gamma_{k}\\}_{K}$ stays
bounded. ∎

The following is the main convergence result for Algorithm 3.1 which requires
a slightly stronger smoothness assumption on either $f$ or $\phi$.

###### Theorem 3.7.

Assume that Assumption 3.2 holds while either $\phi$ is continuous on
$\operatorname{dom}\phi$ or $\nabla f\colon\mathbb{X}\to\mathbb{X}$ is locally
Lipschitz continuous. Then each accumulation point $x^{*}$ of a sequence
$\\{x^{k}\\}$ generated by Algorithm 3.1 is an M-stationary point of (P).

###### Proof.

Let $\\{x^{k}\\}_{K}$ be a subsequence converging to $x^{*}$. In view of
Proposition 3.4, it follows that also the subsequence $\\{x^{k+1}\\}_{K}$
converges to $x^{*}$. Furthermore, Proposition 3.5 yields
$\gamma_{k}\|x^{k+1}-x^{k}\|\to_{K}0$. The minimizing property of $x^{k+1}$,
Fermat’s rule, and the sum rule (2.3) imply that

$0\in\nabla
f(x^{k})+\gamma_{k}(x^{k+1}-x^{k})+\widehat{\partial}\phi(x^{k+1})$ (3.16)

holds for each $k\in K$. Hence, if we can show
$\phi(x^{k+1})\to_{K}\phi(x^{*})$, we can take the limit $k\to_{K}\infty$ in
(3.16) to obtain the desired statement $0\in\nabla
f(x^{*})+\partial\phi(x^{*})$.

Due to (3.11), we find $\psi(x^{k+1})\leq\psi(x^{0})$ for each $k\in K$.
Taking the limit $k\to_{K}\infty$ while respecting the lower semicontinuity of
$\phi$ gives $\psi(x^{*})\leq\psi(x^{0})$, and due to
$x^{0}\in\operatorname{dom}\phi$, we find $x^{*}\in\operatorname{dom}\phi$.
Thus, the condition $\phi(x^{k+1})\to_{K}\phi(x^{*})$ obviously holds if
$\phi$ is continuous on its domain since all iterates $x^{k}$ generated by
Algorithm 3.1 as well as $x^{*}$ belong to $\operatorname{dom}\phi$.

Hence, it remains to consider the situation where $\phi$ is only lower
semicontinuous, but $\nabla f$ is locally Lipschitz continuous. From
$x^{k+1}\to_{K}x^{*}$ and the lower semicontinuity of $\phi$, we find

$\phi(x^{*})\leq\liminf_{k\in K}\phi(x^{k+1})\leq\limsup_{k\in
K}\phi(x^{k+1}).$

It therefore suffices to show that $\limsup_{k\in
K}\phi(x^{k+1})\leq\phi(x^{*})$ holds. Since $x^{k+1}$ solves the subproblem
(3.1) with parameter $\gamma_{k}$, we obtain

$\displaystyle\langle\nabla f(x^{k}),x^{k+1}-x^{k}\rangle$
$\displaystyle+\frac{\gamma_{k}}{2}\|x^{k+1}-x^{k}\|^{2}+\phi(x^{k+1})$
$\displaystyle\leq\langle\nabla
f(x^{k}),x^{*}-x^{k}\rangle+\frac{\gamma_{k}}{2}\|x^{*}-x^{k}\|^{2}+\phi(x^{*})$

for each $k\in K$. We now take the upper limit over $K$ on both sides. Using
the continuity of $\nabla f$, the convergences $x^{k+1}-x^{k}\to_{K}0$ as well
as $\gamma_{k}\|x^{k+1}-x^{k}\|^{2}\to_{K}0$ (see Propositions 3.4 and 3.5),
and taking into account that $\gamma_{k}\|x^{k}-x^{*}\|^{2}\to_{K}0$ due to
the boundedness of the subsequence $\\{\gamma_{k}\\}_{K}$ in this situation,
see Corollary 3.6, we obtain $\limsup_{k\in K}\phi(x^{k+1})\leq\phi(x^{*})$.
Altogether, we therefore get $\phi(x^{k+1})\to_{K}\phi(x^{*})$, and this
completes the proof. ∎

Note that $\phi$ being continuous on $\operatorname{dom}\phi$ is an assumption
which holds, e.g., if $\phi$ is the indicator function of a closed set, see
Remark 2.1. Therefore, Theorem 3.7 provides a global convergence result for
constrained optimization problems with an arbitrary continuously
differentiable objective function over any closed (not necessarily convex)
feasible set. Moreover, the previous convergence result also holds for a
general lower semicontinuous function $\phi$ provided that $\nabla f$ is
locally Lipschitz continuous. This includes, for example, sparse optimization
problems in $\mathbb{X}\in\\{\mathbb{R}^{n},\mathbb{R}^{n\times m}\\}$
involving the so-called $\ell_{0}$-quasi-norm, which counts the number of
nonzero entries of the input vector, as a penalty term or optimization
problems in $\mathbb{X}:=\mathbb{R}^{n\times m}$ comprising rank penalties.
Note that we still do not require the global Lipschitz continuity of $\nabla
f$. However, it is an open question whether the previous convergence result
also holds for the general setting where $f$ is only continuously
differentiable and $\phi$ is just lower semicontinuous.

###### Remark 3.8.

Let $\\{x^{k}\\}$ be a sequence generated by Algorithm 3.1. In iteration
$k\in\mathbb{N}$, $x^{k+1}$ satisfies the necessary optimality condition
(3.16) of the subproblem (3.1). Hence, from the next iteration’s point of
view, we obtain

$\gamma_{k-1}(x^{k-1}-x^{k})+\nabla f(x^{k})-\nabla f(x^{k-1})\in\nabla
f(x^{k})+\widehat{\partial}\phi(x^{k})$

for each $k\in\mathbb{N}$ with $k\geq 1$. This justifies evaluation of the
termination criterion

$\left\|\gamma_{k-1}(x^{k-1}-x^{k})+\nabla f(x^{k})-\nabla
f(x^{k-1})\right\|\leq\tau_{\textup{abs}}$ (3.17)

for some $\tau_{\textup{abs}}>0$ since this means that $x^{k}$ is, in some
sense, approximately M-stationary for (P). Observe that, along a subsequence
$\\{x^{k}\\}_{K}$ satisfying $x^{k-1}\to_{K}x^{*}$ for some $x^{*}$,
Propositions 3.4 and 3.5 yield $x^{k}\to_{K}x^{*}$ and
$\gamma_{k-1}(x^{k}-x^{k-1})\to_{K}0$ under appropriate assumptions, which
means that (3.17) is satisfied for large enough $k\in K$ due to continuity of
$\nabla f\colon\mathbb{X}\to\mathbb{X}$, see the discussion after Lemma 3.3 as
well.

Recall that the existence of accumulation points is guaranteed by the
coercivity of the function $\psi$. A simple criterion for the convergence of
the entire sequence $\\{x^{k}\\}$ is provided by the following comment.

###### Remark 3.9.

Let $\\{x^{k}\\}$ be any sequence generated by Algorithm 3.1 such that $x^{*}$
is an isolated accumulation point of this sequence. Then the entire sequence
converges to $x^{*}$. This follows immediately from [30, Lemma 4.10] and the
property of the proximal gradient method stated in Proposition 3.4. The
accumulation point $x^{*}$ is isolated, in particular, if $f$ is twice
continuously differentiable with $\nabla^{2}f(x^{*})$ being positive definite
and $\phi$ is convex. In this situation, $x^{*}$ is a strict local minimum of
$\psi$ and therefore the only stationary point of $\psi$ is a neighborhood of
$x^{*}$. Since, by Theorem 3.7, every accumulation point is stationary, it
follows that $x^{*}$ is necessarily an isolated stationary point in this
situation and, thus, convergence of the whole sequence $\\{x^{k}\\}$ to
$x^{*}$ follows.

##  4 Nonmonotone Proximal Gradient Method

The method to be presented here is a nonmonotone version of the proximal
gradient method from the previous section. The kind of nonmonotonicity used
here was introduced by Grippo et al. [22] for a class of smooth unconstrained
optimization problems and then discussed, in the framework of composite
optimization problems, by Wright et al. [34] as well as in some subsequent
papers. We first state the precise algorithm and investigate its convergence
properties. The relation to the existing convergence results is postponed
until the end of this section.

###### Algorithm 4.1 (Nonmonotone Proximal Gradient Method).

0: $\tau>0$, $0<\gamma_{\min}\leq\gamma_{\max}<\infty$, $m\in\mathbb{N}$,
$\delta\in(0,1)$, $x^{0}\in\operatorname{dom}\phi$

1: Set $k:=0$.

2: while A suitable termination criterion is violated at iteration $k$ do

3: Set $m_{k}:=\min\\{k,m\\}$ and choose
$\gamma_{k}^{0}\in[\gamma_{\min},\gamma_{\max}]$.

4: For $i=0,1,2,\ldots$, compute a solution $x^{k,i}$ of  $\min_{x}\
f(x^{k})+\langle\nabla
f(x^{k}),x-x^{k}\rangle+\frac{\gamma_{k,i}}{2}\|x-x^{k}\|^{2}+\phi(x),\quad
x\in\mathbb{X}$ (4.1) with $\gamma_{k,i}:=\tau^{i}\gamma_{k}^{0}$, until the
acceptance criterion
$\psi(x^{k,i})\leq\max_{j=0,1,\ldots,m_{k}}\psi(x^{k-j})-\delta\frac{\gamma_{k,i}}{2}\|x^{k,i}-x^{k}\|^{2}$
(4.2) holds.

5: Denote by $i_{k}:=i$ the terminal value, and set
$\gamma_{k}:=\gamma_{k,i_{k}}$ and $x^{k+1}:=x^{k,i_{k}}$.

6: Set $k\leftarrow k+1$.

7: end while

8: return $x^{k}$

The only difference between Algorithm 3.1 and Algorithm 4.1 is in the stepsize
rule. More precisely, Algorithm 4.1 may be viewed as a generalization of
Algorithm 3.1 since the particular choice $m=0$ recovers Algorithm 3.1.
Numerically, in many examples, the choice $m>0$ leads to better results and is
therefore preferred in practice. On the other hand, for $m>0$, we usually get
a nonmonotone behavior of the function values $\\{\psi(x^{k})\\}$ which
complicates the theory significantly. In addition, the nonmontone proximal
gradient method also requires stronger assumptions in order to prove a
suitable convergence result.

In particular, in addition to the requirements from Assumption 3.2, we need
the following additional conditions on the data functions in order to proceed.

###### Assumption 4.2.

  1. (a)

The function $\psi$ is uniformly continuous on the sublevel set
$\mathcal{L}_{\psi}(x^{0}):=\\{x\in\mathbb{X}\,|\,\psi(x)\leq\psi(x^{0})\\}$.

  2. (b)

The function $\phi$ is continuous on $\operatorname{dom}\phi$.

Note that we always have
$\mathcal{L}_{\psi}(x^{0})\subset\operatorname{dom}\phi$ by the continuity of
$f$. Furthermore, whenever $\psi$ is coercive, Assumption 4.2 (b) already
implies Assumption 4.2 (a) since $\mathcal{L}_{\psi}(x^{0})$ would be a
compact subset of $\operatorname{dom}\phi$ in this situation, and continuous
functions are uniformly continuous on compact sets. Observe that coercivity of
$\psi$ is an inherent property in many practically relevant settings. We
further note that, in general, Assumption 4.2 (a) does not imply Assumption
4.2 (b), and the latter is a necessary requirement since, in our convergence
theory, we will also evaluate the function $\phi$ in some points resulting
from an auxiliary sequence $\\{\hat{x}^{k}\\}$ which may not belong to the
level set $\mathcal{L}_{\psi}(x^{0})$.

For the convergence theory, we assume implicitly that Algorithm 4.1 generates
an infinite sequence $\\{x^{k}\\}$. We first note that the stepsize rule in
the inner loop of Algorithm 4.1 is always finite. Since

$\psi(x^{k})\leq\max\limits_{j=0,1,\ldots,m_{k}}\psi(x^{k-j})$

this observation follows immediately from Lemma 3.3.

Throughout the section, for each $k\in\mathbb{N}$, let
$l(k)\in\\{k-m_{k},\ldots,k\\}$ be an index such that

$\psi(x^{l(k)})=\max\limits_{j=0,1,\ldots,m_{k}}\psi(x^{k-j})$

is valid. We already mentioned that $\\{\psi(x^{k})\\}$ may possess a
nonmonotone behavior. However, as the following lemma shows,
$\\{\psi(x^{l(k)})\\}$ is monotonically decreasing.

###### Lemma 4.3.

Let Assumption 3.2 (b) hold and let $\\{x^{k}\\}$ be a sequence generated by
Algorithm 4.1. Then $\\{\psi(x^{l(k)})\\}$ is monotonically decreasing.

###### Proof.

The nonmonotone stepsize rule from (4.2) can be rewritten as

$\psi(x^{k+1})\leq\psi(x^{l(k)})-\delta\frac{\gamma_{k}}{2}\|x^{k+1}-x^{k}\|^{2}.$
(4.3)

Using $m_{k+1}\leq m_{k}+1$, we find

$\displaystyle\psi(x^{l(k+1)})$
$\displaystyle=\max_{j=0,1,\ldots,m_{k+1}}\psi(x^{k+1-j})$
$\displaystyle\leq\max_{j=0,1,\ldots,m_{k}+1}\psi(x^{k+1-j})$
$\displaystyle=\max\left\\{\max_{j=0,1,\ldots,m_{k}}\psi(x^{k-j}),\psi(x^{k+1})\right\\}$
$\displaystyle=\max\left\\{\psi(x^{l(k)}),\psi(x^{k+1})\right\\}$
$\displaystyle=\psi(x^{l(k)}),$

where the last equality follows from (4.3). This shows the claim. ∎

As a corollary of the above result, we obtain that the iterates of Algorithm
4.1 belong to the level set $\mathcal{L}_{\psi}(x^{0})$.

###### Corollary 4.4.

Let Assumption 3.2 (b) hold and let $\\{x^{k}\\}$ be a sequence generated by
Algorithm 4.1. Then
$\\{x^{k}\\},\\{x^{l(k)}\\}\subset\mathcal{L}_{\psi}(x^{0})$ holds.

###### Proof.

Noting that $l(0)=0$ holds by construction, Lemma 4.3 and (4.3) yield the
estimate $\psi(x^{k+1})\leq\psi(x^{l(k)})\leq\psi(x^{l(0)})=\psi(x^{0})$ for
each $k\in\mathbb{N}$ which shows the claim. ∎

The counterpart of Proposition 3.4 is significantly more difficult to prove in
the nonmonotone setting. In fact, it is this central result which requires the
uniform continuity of the objective function $\psi$ from Assumption 4.2 (a).
Though its proof is essentially the one from [34], we present all details
since they turn out to be of some importance for the discussion at the end of
this section.

###### Proposition 4.5.

Let Assumption 3.2 and Assumption 4.2 (a) hold. Then each sequence
$\\{x^{k}\\}$ generated by Algorithm 4.1 satisfies $\|x^{k+1}-x^{k}\|\to 0$.

###### Proof.

Since $\psi$ is bounded from below due to Assumption 3.2 (a), Lemma 4.3
implies

$\lim_{k\to\infty}\psi(x^{l(k)})=\psi^{*}$ (4.4)

for some finite $\psi^{*}\in\mathbb{R}$. From Corollary 4.4, we find
$\\{x^{l(k)}\\}\subset\mathcal{L}_{\psi}(x^{0})$. Applying (4.3) with $k$
replaced by $l(k)-n-1$ for some $n\in\mathbb{N}$ gives
$\psi(x^{l(k)-n})\leq\psi(x^{l(l(k)-n-1)})\leq\psi(x^{0})$, i.e.,
$\\{x^{l(k)-n}\\}\subset\mathcal{L}_{\psi}(x^{0})$ (here, we assume implicitly
that $k$ is large enough such that no negative indices $l(k)-n-1$ occur). More
precisely, for $n=0$, we have

$\psi(x^{l(k)})-\psi(x^{l(l(k)-1)})\leq-\delta\frac{\gamma_{l(k)-1}}{2}\|x^{l(k)}-x^{l(k)-1}\|^{2}\leq
0.$

Taking the limit $k\to\infty$ in the previous inequality and using (4.4), we
therefore obtain

$\lim_{k\to\infty}\gamma_{l(k)-1}\|x^{l(k)}-x^{l(k)-1}\|^{2}=0.$

Since $\gamma_{k}\geq\gamma_{\min}>0$ for all $k\in\mathbb{N}$, we get

$\lim_{k\to\infty}d^{l(k)-1}=0,$ (4.5)

where $d^{k}:=x^{k+1}-x^{k}$ for all $k\in\mathbb{N}$. Using (4.4) and (4.5),
it follows that

$\psi^{*}=\lim_{k\to\infty}\psi(x^{l(k)})=\lim_{k\to\infty}\psi\big{(}x^{l(k)-1}+d^{l(k)-1}\big{)}=\lim_{k\to\infty}\psi(x^{l(k)-1}),$
(4.6)

where the last equality takes into account the uniform continuity of $\psi$
from Assumption 4.2 (a) and (4.5).

We will now prove, by induction, that the limits

$\lim_{k\to\infty}d^{l(k)-j}=0,\qquad\lim_{k\to\infty}\psi(x^{l(k)-j})=\psi^{*}$
(4.7)

hold for all $j\in\mathbb{N}$ with $j\geq 1$. We already know from (4.5) and
(4.6) that (4.7) holds for $j=1$. Suppose that (4.7) holds for some $j\geq 1$.
We need to show that it holds for $j+1$. Using (4.3) with $k$ replaced by
$l(k)-j-1$, we have

$\psi(x^{l(k)-j})\leq\psi(x^{l(l(k)-j-1)})-\delta\frac{\gamma_{l(k)-j-1}}{2}\|d^{l(k)-j-1}\|^{2}$

(again, we assume implicitly that $k$ is large enough such that $l(k)-j-1$ is
nonnegative). Rearranging this expression and using
$\gamma_{k}\geq\gamma_{\min}$ for all $k$ yields

$\|d^{l(k)-j-1}\|^{2}\leq\frac{2}{\gamma_{\min}\delta}\big{(}\psi(x^{l(l(k)-j-1)})-\psi(x^{l(k)-j})\big{)}.$

Taking $k\to\infty$, using (4.4), as well as the induction hypothesis, it
follows that

$\lim_{k\to\infty}d^{l(k)-j-1}=0,$ (4.8)

which proves the induction step for the first limit in (4.7). The second limit
then follows from

$\lim_{k\to\infty}\psi\big{(}x^{l(k)-(j+1)}\big{)}=\lim_{k\to\infty}\psi\big{(}x^{l(k)-(j+1)}+d^{l(k)-j-1)}\big{)}=\lim_{k\to\infty}\psi\big{(}x^{l(k)-j}\big{)}=\psi^{*},$

where the first equation exploits (4.8) together with the uniform continuity
of $\psi$ from Assumption 4.2 (a) and
$\\{x^{l(k)-j}\\},\\{x^{l(k)-(j+1)}\\}\subset\mathcal{L}_{\psi}(x^{0})$,
whereas the final equation is the induction hypothesis.

In the last step of our proof, we now show that $\lim_{k\to\infty}d^{k}=0$
holds. Suppose that this is not true. Then there is a (suitably shifted, for
notational simplicity) subsequence $\\{d^{k-m-1}\\}_{k\in K}$ and a constant
$c>0$ such that

$\|d^{k-m-1}\|\geq c\quad\forall k\in K.$ (4.9)

Now, for each $k\in K$, the corresponding index $l(k)$ is one of the indices
$k-m,k-m+1,\ldots,k$. Hence, we can write $k-m-1=l(k)-j_{k}$ for some index
$j_{k}\in\\{1,2,\ldots,m+1\\}$. Since there are only finitely many possible
indices $j_{k}$, we may assume without loss of generality that $j_{k}=j$ holds
for some fixed index $j\in\\{1,\ldots,m+1\\}$. Then (4.7) implies

$\lim_{k\to_{K}\infty}d^{k-m-1}=\lim_{k\to_{K}\infty}d^{l(k)-j}=0.$

This contradicts (4.9) and therefore completes the proof. ∎

###### Theorem 4.6.

Assume that Assumptions 3.2 and 4.2 hold and let $\\{x^{k}\\}$ be a sequence
generated by Algorithm 4.1. Suppose that $x^{*}$ is an accumulation point of
$\\{x^{k}\\}$ such that $x^{k}\to_{K}x^{*}$ holds along a subsequence
$k\to_{K}\infty$. Then $x^{*}$ is an M-stationary point of (P), and
$\gamma_{k}(x^{k+1}-x^{k})\to_{K}0$ is valid.

###### Proof.

Since $\\{x^{k}\\}_{K}$ is a subsequence converging to $x^{*}$, it follows
from Proposition 4.5 that also the subsequence $\\{x^{k+1}\\}_{K}$ converges
to $x^{*}$. We note that $x^{*}\in\operatorname{dom}\phi$ follows from
Corollary 4.4 by closedness of $\mathcal{L}_{\psi}(x^{0})$. The minimizing
property of $x^{k+1}$ for (4.1) together with Fermat’s rule and the sum rule
from (2.3) imply that the necessary optimality condition (3.16) holds for each
$k\in K$. We claim that the subsequence $\\{\gamma_{k}\\}_{K}$ is bounded.
Assume, by contradiction, that this is not true. Without loss of generality,
let us assume that $\gamma_{k}\to_{K}\infty$ and that the acceptance criterion
(4.2) is violated in the first iteration of the inner loop for each $k\in K$.
Setting $\hat{\gamma}_{k}:=\gamma_{k}/\tau$ for each $k\in K$,
$\\{\hat{\gamma}^{k}\\}_{K}$ also tends to infinity, but the corresponding
vectors $\hat{x}^{k}:=x^{k,i_{k}-1}$, $k\in K$, do not satisfy the stepsize
condition from (4.2), i.e., we have

$\psi(\hat{x}^{k})>\max_{j=0,1,\ldots,m_{k}}\psi(x^{k-j})-\delta\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}\qquad\forall
k\in K.$ (4.10)

On the other hand, since $\hat{x}^{k}=x^{k,i_{k}-1}$ solves the corresponding
subproblem (3.1) with $\hat{\gamma}_{k}=\gamma_{k,i_{k}-1}$, we have

$\langle\nabla
f(x^{k}),\hat{x}^{k}-x^{k}\rangle+\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}+\phi(\hat{x}^{k})\leq\phi(x^{k})$
(4.11)

for each $k\in K$. Due to $\hat{\gamma}_{k}\to_{K}\infty$ and since $\phi$ is
bounded from below by an affine function due to Assumption 3.2 (b) while
$\phi$ is continuous on its domain by Assumption 4.2 (b) (which yields
boundedness of the right-hand side of (4.11)), this implies
$\hat{x}^{k}-x^{k}\to_{K}0$. Consequently, we have $\hat{x}^{k}\to_{K}x^{*}$
as well.

Now, if $\hat{\gamma}_{k}\|\hat{x}^{k}-x^{k}\|\to_{K^{\prime}}0$ holds along a
subsequence $k\to_{K^{\prime}}\infty$ such that $K^{\prime}\subset K$, then,
due to

$0\in\nabla
f(x^{k})+\hat{\gamma}_{k}(\hat{x}^{k}-x^{k})+\widehat{\partial}\phi(\hat{x}^{k}),$

which holds for each $k\in K^{\prime}$ by means of Fermat’s rule and the sum
rule (2.3), we immediately see that $x^{*}$ is an M-stationary point of (P) by
taking the limit $k\to_{K^{\prime}}\infty$ and exploiting the continuity of
$\phi$ on $\operatorname{dom}\phi$ from Assumption 4.2 (b). Thus, for the
remainder of the proof, we may assume that there is a constant $c>0$ such that

$\hat{\gamma}_{k}\|\hat{x}^{k}-x^{k}\|\geq c$

holds for each $k\in K$. Further, we then also get

$(1-\delta)\frac{\hat{\gamma}_{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}\geq\frac{1-\delta}{2}c\|\hat{x}^{k}-x^{k}\|\geq
o\big{(}\|\hat{x}^{k}-x^{k}\|\big{)}$

for all $k\in K$ sufficiently large. Rearranging (4.11) gives us

$\langle\nabla
f(x^{k}),\hat{x}^{k}-x^{k}\rangle+\phi(\hat{x}^{k})-\phi(x^{k})\leq-\frac{\hat{\gamma}^{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}$

for each $k\in K$. From the mean-value theorem, we obtain some $\xi^{k}$ on
the line segment between $\hat{x}^{k}$ and $x^{k}$ such that

$\displaystyle\psi(\hat{x}^{k})-\max_{j=0,1,\ldots,m_{k}}\psi(x^{k-j})$
$\displaystyle\qquad\leq\psi(\hat{x}^{k})-\psi(x^{k})$
$\displaystyle\qquad=\langle\nabla
f(\xi^{k}),\hat{x}^{k}-x^{k}\rangle+\phi(\hat{x}^{k})-\phi(x^{k})$
$\displaystyle\qquad=\langle\nabla
f(x^{k}),\hat{x}^{k}-x^{k}\rangle+\phi(\hat{x}^{k})-\phi(x^{k})+\langle\nabla
f(\xi^{k})-\nabla f(x^{k}),\hat{x}^{k}-x^{k}\rangle$
$\displaystyle\qquad\leq-\frac{\hat{\gamma}^{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}+o(\|\hat{x}^{k}-x^{k}\|)$
$\displaystyle\qquad\leq-\delta\frac{\hat{\gamma}^{k}}{2}\|\hat{x}^{k}-x^{k}\|^{2}$

for all $k\in K$ sufficiently large. This contradiction to (4.10) shows that
the sequence $\\{\gamma_{k}\\}_{K}$ is bounded.

Finally, the continuity of $\phi$ from Assumption 4.2 (b) gives
$\phi(x^{k+1})\to_{K}\phi(x^{*})$ due to $x^{k+1}\to_{K}x^{*}$. Thus,
recalling $x^{k}\to_{K}x^{*}$ and the boundedness of $\\{\gamma_{k}\\}_{K}$,
we find $\gamma_{k}(x^{k+1}-x^{k})\to_{K}0$, and taking the limit
$k\to_{K}\infty$ in (3.16) gives us M-stationarity of $x^{*}$ for (P). ∎

###### Remark 4.7.

  1. (a)

Note that Assumptions 3.2 and 4.2 do not comprise any Lipschitz conditions on
$\nabla f$.

  2. (b)

The results in this section recover the findings from [23, Section 4] and [25,
Section 3] which were obtained in the special situation where $\phi$ is the
indicator function associated with a closed set, see Remark 2.1 as well.

  3. (c)

Based on Theorem 4.6, (3.17) also provides a reasonable termination criterion
for Algorithm 4.1, see Remark 3.8 as well.

  4. (d)

In view of Proposition 4.5, it follows in the same way as in Remark 3.9 that
the entire sequence $\\{x^{k}\\}$ generated by Algorithm 4.1 converges if
there exists an isolated accumulation point.

The uniform continuity of $\psi$ which is demanded in Assumption 4.2 (a) is
obviously a much stronger assumption than the one used in the previous section
for the monotone proximal gradient method. In particular, this assumption
rules out applications where $\phi$ is given by the $\ell_{0}$-quasi-norm.
Nevertheless, the theory still covers the situation where the role of $\phi$
is played by an $\ell_{p}$-type penalty function for $p\in(0,1)$ over
$\mathbb{X}\in\\{\mathbb{R}^{n},\mathbb{R}^{n\times m}\\}$ which is known to
promote sparse solutions. More precisely, this choice is popular in sparse
optimization if the more common $\ell_{1}$-norm does not provide satisfactory
sparsity results, and the application of the $\ell_{0}$-quasi-norm seems too
difficult, see [6, 14, 15, 19, 27, 28] for some applications and numerical
results based on the $\ell_{p}$-quasi-norm or closely related expressions. We
would like to note that uniform continuity is a standard assumption in the
context of nonmonotone stepsize rules involving acceptance criteria of type
(4.2), see [22, page 710].

We close this section with a discussion on existing convergence results for
nonmonotone proximal gradient methods. To the best of our knowledge, the first
one can be found in [34]. The authors prove convergence under the assumptions
that $f$ is differentiable with a globally Lipschitz continuous gradient and
$\phi$ being real-valued and convex, see [34, Section II.G]. Implicitly,
however, they also exploit the uniform continuity of $\psi=f+\phi$ in their
proof of [34, Lemma 4], a result like Proposition 4.5, without stating this
assumption explicitly. Taking this into account, our Assumption 4.2 (a) is
actually weaker than the requirements used in [34], so that the results of
this section can be viewed as a generalization of the convergence theory from
[34].

Furthermore, [15, Section 3.1] and [16, Appendix A] consider a nonmonotone
proximal gradient method which is slightly different from Algorithm 4.1 since
the acceptance criterion (4.2) is replaced by the slightly simpler condition

$\psi(x^{k,i})\leq\max_{j=0,1,\ldots,m_{k}}\psi(x^{k-j})-\frac{\delta}{2}\|x^{k,i}-x^{k}\|^{2}.$

In [16, Theorem 4.1], the authors obtain convergence to M-stationary points
whenever $\psi$ is bounded from below as well as uniformly continuous on the
level set $\mathcal{L}_{\psi}(x^{0})$, $f$ possesses a Lipschitzian derivative
on some enlargement of $\mathcal{L}_{\psi}(x^{0})$, and $\phi$ is continuous.
Clearly, our convergence analysis of Algorithm 4.1 does not exploit any
Lipschitzianity of $\nabla f$, so our assumptions are weaker than those ones
used in [16]. In [15, Theorem 3.3], the authors claim that the results from
[16] even hold when the continuity assumption on $\phi$ is dropped. The proof
of [15, Theorem 3.3], however, relies on the outer semicontinuity property
(2.2) of the limiting subdifferential, which does not hold for general
discontinuous functions $\phi$, so this result is not reliable.

Finally, let us mention that the two references [26, 33] also consider
nonmonotone (and accelerated) proximal gradient methods. These methods are not
directly comparable to our algorithm since they are based on a different kind
of nonmonotonicity. In any case, although the analysis in both papers works
for merely lower semicontinuous functions $\phi$, the provided convergence
theory requires $\nabla f$ to be globally Lipschitz continuous.

##  5 Conclusions

In this paper, we demonstrated how the convergence analysis for monotone and
nonmonotone proximal gradient methods can be carried out in the absence of
(global) Lipschitz continuity of the derivative associated with the smooth
function. Our results, thus, open up these algorithms to be reasonable
candidates for subproblem solvers within an augmented Lagrangian framework for
the numerical treatment of constrained optimization problems with lower
semicontinuous objective functions, see e.g. [15] where this approach has been
suggested but suffers from an incomplete analysis, and [23, 19, 25] where this
approach has been corrected and extended.

Let us mention some remaining open problems regarding the investigated
proximal gradient methods. First, it might be interesting to find minimum
requirements which ensure global convergence of Algorithms 3.1 and 4.1. We
already mentioned in Section 3 that it is an open question whether the
convergence analysis for Algorithm 3.1 can be generalized to the setting where
$f$ is only continuously differentiable while $\phi$ is just lower
semicontinuous. Second, we did not investigate if the _Kurdyka–Łojasiewicz_
property could be efficiently incorporated into the convergence analysis in
order to get stronger results even in the absence of strong Lipschitz
assumptions on the derivative of $f$. Third, our analysis has shown that
Algorithms 3.1 and 4.1 compute M-stationary points of (P) in general. In the
setting of Remark 2.2, i.e., where constrained programs with a merely lower
semicontinuous objective function are considered, the introduced concept of
M-stationarity is, to some extent, _implicit_ since it comprises an unknown
subdifferential. In general, the latter can be approximated from above in
terms of initial problem data only in situations where a qualification
condition is valid. The resulting stationarity condition may be referred to as
_explicit_ M-stationarity. It seems to be a relevant topic of future research
to investigate whether Algorithms 3.1 and 4.1 can be modified such that they
compute explicitly M-stationary points in this rather general setting. Fourth,
it might be interesting to investigate whether other types of nonmonotonicity,
different from the one used in Algorithm 4.1, can be exploited in order to get
rid of the uniform continuity requirement from Assumption 4.2 (a).

Finally, we note that there exist several generalizations of proximal gradient
methods using, e.g., inertial terms and Bregman distances, see e.g. [2, 9, 10,
11] and the references therein. The corresponding convergence theory is also
based on a global Lipschitz assumption for the gradient of the smooth term or
additional convexity assumptions which allow the application of a descent-type
lemma. It might be interesting to see whether our technique of proof can be
adapted to these generalized proximal gradient methods in order to weaken the
postulated assumptions.

## References

  * [1] H. Attouch, J. Bolte, and B. F. Svaiter.  Convergence of descent methods for semi-algebraic and tame problems, proximal algorithms, forward-backward splitting, and regularized Gauss–Seidel methods.  Mathematical Programming, 137:91 – 129, 2013.  doi:10.1007/s10107-011-0484-9.
  * [2] H. H. Bauschke, J. Bolte, and M. Teboulle.  A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications.  Mathematics of Operations Research, 42(2):330–348, 2017.  doi:10.1287/moor.2016.0817.
  * [3] H. H. Bauschke and P. L. Combettes.  Convex Analysis and Monotone Operator Theory in Hilbert Spaces.  Springer, 2011.  doi:10.1007/978-1-4419-9467-7.
  * [4] A. Beck.  First-Order Methods in Optimization.  SIAM, 2017.  doi:10.1137/1.9781611974997.
  * [5] A. Beck and M. Teboulle.  A fast iterative shrinkage-thresholding algorithm for linear inverse problems.  SIAM Journal on Imaging Sciences, 2(1):183–202, 2009.  doi:10.1137/080716542.
  * [6] W. Bian and X. Chen.  Linearly constrained non-Lipschitz optimization for image restoration.  SIAM Journal on Imaging Sciences, 8(4):2294–2322, 2015.  doi:10.1137/140985639.
  * [7] E. G. Birgin, J. M. Martínez, and M. Raydan.  Nonmonotone spectral projected gradient methods on convex sets.  SIAM Journal on Optimization, 10(4):1196–1211, 2000.  doi:10.1137/s1052623497330963.
  * [8] J. Bolte, S. Sabach, and M. Teboulle.  Proximal alternating linearized minimization for nonconvex and nonsmooth problems.  Mathematical Programming, 146:459 – 494, 2014.  doi:10.1007/s10107-013-0701-9.
  * [9] J. Bolte, S. Sabach, M. Teboulle, and Y. Vaisbourd.  First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems.  SIAM Journal on Optimization, 28(3):2131–2151, 2018.  doi:10.1137/17M1138558.
  * [10] R. I. Boţ and E. R. Csetnek.  An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems.  Journal of Optimization Theory and Applications, 171(2):600–616, 2016.  doi:10.1007/s10957-015-0730-z.
  * [11] R. I. Boţ, E. R. Csetnek, and S. C. László.  An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions.  EURO Journal on Computational Optimization, 4(1):3–25, 2016.  doi:10.1007/s13675-015-0045-8.
  * [12] R. E. Bruck.  On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space.  Journal of Mathematical Analysis and Applications, 61(1):159–164, 1977.  doi:10.1016/0022-247X(77)90152-4.
  * [13] A. M. Bruckstein, D. L. Donoho, and M. Elad.  From sparse solutions of systems of equations to sparse modeling of signals and images.  SIAM Review, 51(1):34–81, 2009.  doi:10.1137/060657704.
  * [14] R. Chartrand.  Exact reconstruction of sparse signals via nonconvex minimization.  IEEE Signal Processing Letters, 14(10):707–710, 2007.  doi:10.1109/LSP.2007.898300.
  * [15] X. Chen, L. Guo, Z. Lu, and J. J. Ye.  An augmented Lagrangian method for non-Lipschitz nonconvex programming.  SIAM Journal on Numerical Analysis, 55(1):168–193, 2017.  doi:10.1137/15M1052834.
  * [16] X. Chen, Z. Lu, and T.-K. Pong.  Penalty methods for a class of non-Lipschitz optimization problems.  SIAM Journal on Optimization, 26(3):1465–1492, 2016.  doi:10.1137/15M1028054.
  * [17] E. Cohen, N. Hallak, and M. Teboulle.  Dynamic alternating direction of multipliers for nonconvex minimization with nonlinear functional equality constraints.  Journal of Optimization Theory and Applications, 193:324–353, 2022\.  doi:10.1007/s10957-021-01929-5.
  * [18] P. L. Combettes and V. R. Wajs.  Signal recovery by proximal forward-backward splitting.  Multiscale Modeling & Simulation, 4(4):1168–1200, 2005.  doi:10.1137/050626090.
  * [19] A. De Marchi, X. Jia, C. Kanzow, and P. Mehlitz.  Constrained structured optimization and augmented Lagrangian proximal methods.  Technical report, preprint arXiv, 2022.  URL https://arxiv.org/abs/2203.05276.
  * [20] D. Di Lorenzo, G. Liuzzi, F. Rinaldi, F. Schoen, and M. Sciandrone.  A concave optimization-based approach for sparse portfolio selection.  Optimization Methods and Software, 27(6):983–1000, 2012.  doi:10.1080/10556788.2011.577773.
  * [21] M. Fukushima and H. Mine.  A generalized proximal point algorithm for certain non-convex minimization problems.  International Journal of Systems Science, 12(8):989–1000, 1981\.  doi:10.1080/00207728108963798.
  * [22] L. Grippo, F. Lampariello, and S. Lucidi.  A nonmonotone line search technique for Newton’s method.  SIAM Journal on Numerical Analysis, 23(4):707–716, 1986.  doi:10.1137/0723046.
  * [23] L. Guo and Z. Deng.  A new augmented Lagrangian method for MPCCs - theoretical and numerical comparison with existing augmented Lagrangian methods.  Mathematics of Operations Research, 2021.  doi:10.1287/moor.2021.1165.
  * [24] L. Guo and J. J. Ye.  Necessary optimality conditions and exact penalization for non-Lipschitz nonlinear programs.  Mathematical Programming, 168:571–598, 2018.  doi:10.1007/s10107-017-1112-0.
  * [25] X. Jia, C. Kanzow, P. Mehlitz, and G. Wachsmuth.  An augmented Lagrangian method for optimization problems with structured geometric constraints.  Technical report, preprint arXiv, 2021.  URL https://arxiv.org/abs/2105.08317.
  * [26] H. Li and Z. Lin.  Accelerated proximal gradient methods for nonconvex programming.  In Proceedings of the 28th International Conference on Neural Information Processing Systems, volume 1, pages 379–387, 2015.  doi:10.5555/2969239.2969282.
  * [27] Y.-F. Liu, Y.-H. Dai, and S. Ma.  Joint power and admission control: non-convex $\ell_{q}$ approximation and an effective polynomial time deflation approach.  IEEE Transactions on Signal Processing, 63(14):3641–3656, 2015\.  doi:10.1109/TSP.2015.2428224.
  * [28] G. Marjanovic and V. Solo.  On $\ell_{q}$ optimization and matrix completion.  IEEE Transactions on Signal Processing, 60(11):5714–5724, 2012\.  doi:10.1109/TSP.2012.2212015.
  * [29] B. S. Mordukhovich.  Variational Analysis and Applications.  Springer, 2018.  doi:10.1007/978-3-319-92775-6.
  * [30] J. J. Moré and D. C. Sorensen.  Computing a trust region step.  SIAM Journal on scientific and statistical computing, 4(3):553–572, 1983.  doi:10.1137/0904038.
  * [31] G. B. Passty.  Ergodic convergence to a zero of the sum of monotone operators in Hilbert space.  Journal of Mathematical Analysis and Applications, 72(2):383–390, 1979.  doi:10.1016/0022-247X(79)90234-8.
  * [32] R. T. Rockafellar and R. J.-B. Wets.  Variational Analysis.  Springer, 2009.  doi:10.1007/978-3-642-02431-3.
  * [33] T. Wang and H. Liu.  A nonmonotone accelerated proximal gradient method with variable stepsize strategy for nonsmooth and nonconvex minimization problems.  Technical report, preprint Optimization-Online, 2021.  URL http://www.optimization-online.org/DB_HTML/2021/04/8365.html.
  * [34] S. J. Wright, R. D. Nowak, and M. A. T. Figueiredo.  Sparse reconstruction by separable approximation.  IEEE Transactions on Signal Processing, 57(7):2479–2493, 2009.  doi:10.1109/tsp.2009.2016892.