# Inexact reduced gradient methods
in nonconvex optimization

Pham Duy Khanh111Department of Mathematics, Ho Chi Minh City University of
Education, Ho Chi Minh City, Vietnam. E-mail<EMAIL_ADDRESS>Boris S.
Mordukhovich222Department of Mathematics, Wayne State University, Detroit,
Michigan, USA. E-mail<EMAIL_ADDRESS>Research of this author was partly
supported by the US National Science Foundation under grants DMS-1808978 and
DMS-2204519, by the Australian Research Council under grant DP-190100555, and
by Project 111 of China under grant D21024. Dat Ba Tran333Department of
Mathematics, Wayne State University, Detroit, Michigan, USA. E-mail:
<EMAIL_ADDRESS>Research of this author was partly supported by the US
National Science Foundation under grant DMS-1808978.

Abstract. This paper proposes and develops new linesearch methods with inexact
gradient information for finding stationary points of nonconvex continuously
differentiable functions on finite-dimensional spaces. Some abstract
convergence results for a broad class of linesearch methods are established. A
general scheme for inexact reduced gradient (IRG) methods is proposed, where
the errors in the gradient approximation automatically adapt with the
magnitudes of the exact gradients. The sequences of iterations are shown to
obtain stationary accumulation points when different stepsize selections are
employed. Convergence results with constructive convergence rates for the
developed IRG methods are established under the Kurdyka-Łojasiewicz property.
The obtained results for the IRG methods are confirmed by encouraging
numerical experiments, which demonstrate advantages of automatically
controlled errors in IRG methods over other frequently used error selections.
Key words: Nonconvex optimization, inexact reduced gradient methods,
linesearch methods, Kurdyka-Łojasiewicz property, convergence rates
Mathematics Subject Classification (2020) 90C30, 90C52, 49M05

##  1 Introduction

Consider the unconstrained optimization problem formulated as follows:

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

with a continuously differentiable ($\mathcal{C}^{1}$-smooth) objective
function $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$. One of the most natural
and classical approaches to solve (1.1) is by using linesearch methods; see,
e.g., [8, 10, 27, 42, 44, 47]. Given a starting point $x^{1}\in{\rm
I\\!R}^{n}$, such methods construct the iterative procedure

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

where $t_{k}\geq 0$ is a stepsize at the $k^{\rm th}$ iteration, and where the
direction $d^{k}$ satisfies the condition

$\displaystyle\big{\langle}d^{k},\nabla f(x^{k})\big{\rangle}<0.$

The classical choice for the direction is $d^{k}=-\nabla f(x^{k})$ when the
resulting algorithm is known as the gradient descent method; see the
aforementioned books and the references therein. If $f$ is twice continuously
differentiable ($\mathcal{C}^{2}$-smooth) and the Hessian matrix
$\nabla^{2}f(x^{k})$ is positive-definite, then $d^{k}$ is chosen by solving
the linear equation

$\displaystyle-\nabla f(x^{k})=\nabla^{2}f(x^{k})d^{k},$

and it is known as a Newton direction [10, 24, 27]. Additionally, more general
choices of descent directions widely used are the gradient related directions
[10, Page 41], directions satisfying an angle condition [1, Page 541], etc.
Together with the descent directions, stepsizes are usually chosen to ensure
the decreasing property of the entire sequence $\left\\{f(x^{k})\right\\}$ or
sometimes only its tail. Well-known stepsize selections are constant stepsize,
diminishing stepsize (not summable), stepsizes following Armijo rule, and
Wolfe conditions; see, e.g., [1, 8, 10, 27, 42, 44, 47].

The stationarity of accumulation points generated by linesearch methods with
gradient related directions and stepsizes following the Armijo rule is
established in [10, Proposition 1.2.1]. When the Lipschitz continuity of the
gradient is additionally assumed, the same type of convergence is achieved if
either the stepsize is constant and directions are gradient related, or the
stepsize is diminishing and directions satisfy more involved conditions [10,
Proposition 1.2.3]. The global convergence of some linesearch methods to an
isolated stationary point relies on the Ostrowski condition; see [45] and [24,
Theorem 8.3.9]. If there is no guarantee on the isolation of stationary
points, algebraic geometry tools introduced by Łojasiewicz [37] and Kurdyka
[34] are used for linesearch methods with directions satisfying the angle
conditions and the stepsize following the Wolfe conditions; see [1, Theorem
4.1]. While rates of convergence of general linesearch methods are not
considered, some specific methods achieve certain convergence rates for
particular classes of functions. For instance, the gradient descent method
achieves a local linear rate of convergence if the objective function is twice
differentiable with Lipschitz continuous Hessian as in [42, Theorem 1.2.4],
and the (generalized) damped Newton method attains a superlinear convergence
rate of under the positive-definiteness of the (generalized) Hessian and some
additional assumptions; [30, Theorem 4.5]. Furthermore, a linear rate of
convergence for the gradient descent method is achieved under either the
Polyak-Łojasiewicz condition as in [46] and [29], or under the weak convexity
of the objective function as in [50].

Due to its simplicity, the gradient descent method is broadly used to solve
various optimization problems; see, e.g., [14, 19, 20, 43, 51]. However,
errors in gradient calculations may appear in many situations, which can be
found in practical problems arising, e.g., in the design of space trajectories
[2] and computer-aided design of microwave devices [25]. Moreover, many
nonsmooth optimization problems can be transformed into its smoothed versions
by using Moreau envelopes [49] and forward-backward envelopes [52].
Nevertheless, gradients of smoothed functions cannot be usually computed
precisely, and therefore various gradient methods with inexact gradient
information have been suggested. We mention the following major developments
in this vein:

  * •

Devolder et al. [22] introduce the notion of inexact oracle and analyze
behavior of several first-order methods of smooth convex optimization employed
such an oracle. Nesterov [41] develops new methods of this type for nonsmooth
convex optimization in the framework of inexact oracle.

  * •

Gilmore and Kelley [25] propose an implicit filtering algorithm to deal with
certain box constrained optimization problems, where the objective function is
a sum of a $\mathcal{C}^{1}$-smooth function with Lipschitz continuous
gradient and a noise function.

  * •

Bertsekas shows in [10, pp. 44–45] that if the objective function is
$\mathcal{C}^{1}$-smooth with a Lipschitz continuous gradient and if the error
of inexact gradient is either small relative to the norm of the exact
gradient, or proportional to the stepsize, then convergence behavior of
gradient methods is similar to the case where there are no errors.

All the convergence results for inexact gradient methods mentioned above
assume that the objective function is either $\mathcal{C}^{1}$-smooth with a
Lipschitz continuous gradient, or convex. To the best of our knowledge,
general methods of solving nonconvex $\mathcal{C}^{1}$-smooth optimization
problems with inexact information on non-Lipschitzian gradients are not
available in the literature. One of the reasons for this is that verifying the
descent property of the sequence of function values without the Lipschitz
continuity of $\nabla f$ via the Armijo linesearch requires exact information
on gradients. To deal with inexactness, we need a descent direction that
allows us to replace the Armijo linesearch procedure by another one not
demanding exact gradients. In addition, a practical inexact gradient method
that uses constant stepsize for a general nonconvex $\mathcal{C}^{1}$-smooth
function with the Lipschitz gradient is also not established. Although an
inexact gradient method with constant stepsize is proposed in [10, pp. 44–45]
by using an error smaller than the norm of the exact gradient, the problem of
how to control this error while the exact gradient is unknown is still
questionable.

Having in mind the above discussion, we introduce new inexact reduced gradient
(IRG) methods to find stationary points for a general class of nonconvex
$\mathcal{C}^{1}$-smooth functions. Although our proposed methods address
smooth problems, some motivations for them partly come from a certain
nonsmooth algorithm and generalized differential tools of variational
analysis. Specifically, to find a Clarke stationary point of a nonsmooth
locally Lipschitzian function, the gradient sampling (GS) method, introduced
by Burke et al. [16] and modified by Kiwiel [32], approximates at each
iteration the $\varepsilon$-generalized gradient by the convex hull of nearby
gradients. In the GS method, the negative projection of the origin onto this
convex hull is chosen as the descent direction and the stepsizes are chosen
from the backtracking linesearch as in [32, Section 4.1]. Although the GS
method work well for nonsmooth problems, using them for smooth functions seems
to be challenging due to, in particular, the necessity to solve subproblems of
finding projections onto convex hulls. However, replacing the
$\varepsilon$-generalized gradient by the Fréchet-type
$\varepsilon$-subdifferential makes our methods much simpler and suitable for
smooth problems. Indeed, the latter construction for a
$\mathcal{C}^{1}$-smooth function at the point in question is just the closed
ball centered at its gradient with radius $\varepsilon$. Thus the projection
of the origin onto this ball has an explicit and simple form. The descent
direction chosen by this projection also allows us to replace the exact
gradient by its approximation and to use a linesearch procedure that does not
require exact gradients. Developing this idea, we design our inexact reduced
gradient methods with non-normalized directions together with some stepsize
selections such as backtracking stepsize, constant stepsize, and diminishing
stepsize. To the best of our knowledge, the IRG methods that we propose and
develop in this paper are completely new even in the exact case. It should
also be emphasized that the proposed IRG methods are not special versions of
the GS one since the latter needs exact gradients at multiple points in each
iteration, while the IRG methods need only one inexact gradient. Moreover, the
iterative sequence of the GS method is chosen randomly while IRG iterations
are designed deterministically. Our main results include the following:

  * •

Designing a general framework for the IRG methods and revealing their basic
properties.

  * •

Finding stationary accumulation points of iterations in the IRG methods with
backtracking stepsizes as well as with either constant stepsizes, or
diminishing ones under an additional descent condition on the objective
functions.

  * •

Obtaining the global convergence of iterations in the IRG methods with
constructive convergence rates depending on the exponent of the imposed
Kurdyka-Łojasiewicz $(KL)$ property of the objective functions.

These results are achieved by using our newly developed scheme for general
linesearch methods described in the following way. To begin with, some
conditions are proposed to ensure the stationary of accumulation points in
general linesearch methods. If the KL property is additionally assumed, then
the global convergence of the iterative sequence to a stationary point is
guaranteed. Moreover, the rates of convergence are established if the stepsize
is bounded away from zero.

From a practical viewpoint, our IRG methods automatically adjust the errors
required for finding approximate gradients, which will be shown to have
numerical advantages over decreasing errors, e.g., $\varepsilon_{k}=k^{-p}$ as
$p\geq 1$, that are frequently used in the existing methods [10, 22, 25]. To
elaborate more on this issue, observe that since the magnitude of the exact
gradient is small near the stationary points and is larger elsewhere,
decreasing errors that do not take the information of the exact or inexact
gradients into consideration may encounter the following phenomena:

  * •

Over approximation, which happens when the magnitude of the exact gradient is
large but the error is too small. In this case, the procedures of finding
approximate gradient may execute longer than needed to obtain a good
approximation of the exact gradient.

  * •

Under approximation, which happens when the magnitude of the exact gradient is
small but the error is too large, which may lead us to an approximate gradient
that is not good enough. As a consequence of using such an approximate
gradient, the next iterative element can be worse instead of being better than
the current one.

In contrast to methods using decreasing errors, our IRG methods, by performing
a low cost checking step in each iteration to determine whether the error for
the approximation procedure should be decrease or stay the same in the next
iteration, use errors which automatically adapt with the magnitudes of the
exact gradients to avoid the aforementioned phenomena and exhibit a better
performance.

The rest of the paper is organized as follows. Section 2 discusses basic
notions related to methods. Some abstract convergence results for linesearch
methods are established in Section 3. In Section 4, we introduce a general
form of the IRG methods and investigate their principal properties. Our main
results about the convergence behavior of the IRG methods with different
stepsize selections are given in Section 5. The numerical experiments
conducted in Section 6 support the theoretical results obtained in Section 5
and show that the IRG methods with the new type of automatically controlled
errors have a better performance in comparison with the inexact proximal point
method in the Least Absolute Deviations Curve-Fitting problem taken from [11].
In Section 6, we also compare numerically the performance of our IRG methods
with those of the reduced gradient method and the gradient decent method
employing the exact gradient calculations for two well-known benchmark
functions in global optimization. The last Section 7 discusses some directions
of our future research.

##  2 Linesearch Methods and Related Properties

First we recall some notions and notation frequently used in what follows. All
our considerations are given in the space ${\rm I\\!R}^{n}$ with the Euclidean
norm $\|\cdot\|$ and scalar/inner product
$\left\langle\cdot,\cdot\right\rangle$. We use ${\rm
I\\!N}:=\\{1,2,\ldots\\}$, ${\rm I\\!R}_{+}$, and $\overline{{\rm
I\\!R}}:={\rm I\\!R}\cup\left\\{\infty\right\\}$ to denote the collections of
natural numbers, positive numbers, and the extended real line, respectively.
The symbol $x^{k}\stackrel{{\scriptstyle J}}{{\to}}\bar{x}$ means that
$x^{k}\to\bar{x}$ as $k\to\infty$ with $k\in J\subset{\rm I\\!N}$. For a
$\mathcal{C}^{1}$-smooth function $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$,
$\bar{x}$ is a stationary point of $f$ if $\nabla f(\bar{x})=0$. The function
$f$ is said to satisfy the $L$-descent condition with some $L>0$ if

$\displaystyle f(y)\leq f(x)+\left\langle\nabla
f(x),y-x\right\rangle+\dfrac{L}{2}\left\|y-x\right\|^{2}\;\text{ for all
}\;x,y\in{\rm I\\!R}^{n}.$ (2.1)

We see that $L$-descent condition (2.1) means that the graphs o the quadratic
functions $f_{L,x}(y):=f(x)+\left\langle\nabla
f(x),y-x\right\rangle+\frac{L}{2}\left\|y-x\right\|^{2}$ lie above that of $f$
for all $x\in{\rm I\\!R}^{n}.$ This condition is equivalent to the convexity
of $\dfrac{L}{2}\left\|x\right\|^{2}-f(x)$ [53, Lemma 4], while being a direct
consequence of the $L$-Lipschitz continuity of $\nabla f$, i.e., the Lipschitz
continuity of $\nabla f$ with constant $L$; see, e.g., [10, Proposition A.24]
and [27, Lemma A.11]. The converse implication holds when $f$ is convex [6,
53] but fails otherwise. A major class of real-valued functions satisfying the
$L$-descent condition but not having the Lipschitz continuous gradient is
given by

$\displaystyle f(x):=\dfrac{1}{2}\left\langle Ax,x\right\rangle+\left\langle
b,x\right\rangle+c-h(x),$

where $A$ is an $n\times n$ matrix, $b\in{\rm I\\!R}^{n}$, $c\in{\rm I\\!R}$
and $h:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ is a smooth convex function
whose gradient is not Lipschitz continuous, e.g.,
$h(x):=\left\|Cx-d\right\|^{4}$, where $C$ is an $m\times n$ matrix and
$d\in{\rm I\\!R}^{m}.$ Indeed, we can find some $L>0$ such that the matrix
$LI-A$ is positive-semidefinite, where $I$ is the $n\times n$ identity matrix.
It follows from the second-order characterization of convex functions that

$\displaystyle\dfrac{L}{2}\left\|x\right\|^{2}-\Big{(}\dfrac{1}{2}\left\langle
Ax,x\right\rangle+\left\langle
b,x\right\rangle+c\Big{)}=\dfrac{1}{2}\big{\langle}(LI-A)x,x\big{\rangle}-\left\langle
b,x\right\rangle-c\;\text{ is convex}.$

Combining this with the convexity of $h$, we get the convexity of
$\dfrac{L}{2}\left\|x\right\|^{2}-f(x),$ which means that $f$ satisfies the
$L-$descent property (2.1).

Even when $\nabla f$ is Lipschitz continuous with constant $L>0$, $f$ can
satisfy the $\widetilde{L}-$descent condition with $\widetilde{L}<L$. E.g.,
consider the univariate function $f$ together with its gradient $\nabla f$
given by

$\displaystyle f(x)=\begin{cases}\frac{3}{4}x^{2}&\text{\rm if
}|x|<\frac{2}{3},\\\ -\frac{3}{2}x^{2}+3x-1&\text{\rm if }\frac{2}{3}\leq
x\leq 1,\\\ -\frac{3}{2}x^{2}-3x-1&\text{\rm if }-1\leq x\leq-\frac{2}{3},\\\
|x|-\frac{x^{2}}{2}&\text{\rm if }|x|>1\end{cases}\quad\text{ and }\quad\nabla
f(x)=\begin{cases}\frac{3}{2}x&\text{\rm if }|x|<\frac{2}{3},\\\
-3x+3&\text{\rm if }\frac{2}{3}\leq x\leq 1,\\\ 3x-3&\text{\rm if }-1\leq
x\leq-\frac{2}{3},\\\ 1-x&\text{\rm if }x>1,\\\ -1-x&\text{\rm if
}x<1.\end{cases}$

The latter representation implies that $L=3$ is the smallest constant for the
Lipschitz continuity of $\nabla f$. Meanwhile, we see on Figure 1 that $f$
satisfies the $\widetilde{L}$-descent property with $\widetilde{L}=3/2.$

Figure 1: An illustration for $f$ and $f_{3/2,x}$.

Next we recall by following [10, Section 1.2] some basic stepsize selections
for the iterative procedure (1.2). The stepsize sequence
$\left\\{t_{k}\right\\}$ satisfies the Armijo rule if there exist a scalar
$\beta$ and a reduction factor $\gamma\in(0,1)$ such that for all $k\in{\rm
I\\!N}$ we have the representation

$\displaystyle t_{k}=\max\big{\\{}t\;\big{|}\;f(x^{k}+td^{k})\leq
f(x^{k})+\beta t\big{\langle}\nabla
f(x^{k}),d^{k}\big{\rangle},\;t=1,\gamma,\gamma^{2},\ldots\big{\\}}.$ (2.2)

This stepsize selection ensures the nonincreasing property of the entire
sequence $\left\\{f(x^{k})\right\\}$. However, Armijo stepsizes may be small
and thus require a large number of stepsize reducing steps in order to make
just small changes of the iterative sequence.

To significantly simplify the iterative sequence design, it is possible to
consider a constant stepsize, i.e., $t_{k}:=\alpha$ for all $k\in{\rm I\\!N}$.
For this rule, the nonincreasing property of $\left\\{f(x^{k})\right\\}$ is
not ensured in general but holds under the $L$-descent condition (2.1)
whenever $\alpha$ is chosen to be sufficiently small with respect to $1/L$,
see, e.g., [10, 44]. However, even when the $L$-descent condition is satisfied
for $f$ while an approximate value of $L$ is unknown, using constant stepsizes
becomes inefficient. In such a case, it is possible to use the diminishing
stepsize selection, i.e.,

$\displaystyle t_{k}\downarrow 0\;\;\mbox{ as }\;k\to\infty\;\text{ and
}\;\sum_{k=1}^{\infty}t_{k}=\infty.$ (2.3)

Drawbacks of the latter selection are the eventual slow convergence due to its
small stepsizes and the absence of the descent property for the iterative
sequence $\left\\{f(x^{k})\right\\}$.

Now we formulate a general type of directions that plays a crucial role in our
subsequent analysis of various linesearch methods.

######  Definition 2.1.

Let $\left\\{x^{k}\right\\}$ be a sequence in ${\rm I\\!R}^{n}$. The direction
sequence $\left\\{d^{k}\right\\}$ is called gradient associated with
$\left\\{x^{k}\right\\}$ if we have the implication

$\displaystyle\text{ whenever }\;d^{k}\overset{J}{\rightarrow}0\;\text{ for
some infinite set }\;J\subset{\rm I\\!N},\;\text{ it holds that }\;\nabla
f(x^{k})\overset{J}{\rightarrow}0.$ (2.4)

It can be easily checked that if either

$\displaystyle\lim_{k\rightarrow\infty}\left\|d^{k}-\nabla
f(x^{k})\right\|=0,$ (2.5)

or there exists some constant $c>0$ such that

$\displaystyle\left\|\nabla f(x^{k})\right\|\leq c\left\|d^{k}\right\|\;\text{
for all sufficiently large }\;k\in{\rm I\\!N},$ (2.6)

then $\left\\{d^{k}\right\\}$ is gradient associated with
$\left\\{x^{k}\right\\}$. Many methods such as the gradient descent, the
generalized damped Newton method [30, 31], and the methods appeared in [10,
Proposition 1.2.3] satisfy (2.6), while (2.5) can be considered as a standard
condition for inexact gradient directions. It should be also mentioned that
the notion of gradient associated directions is different from the notion of
gradient related directions proposed by Bertsekas in [10].

Finally in this section, we discuss two versions of the fundamental KL
property playing plays a crucial role in the results on global convergence and
convergence rates established in what follows. The first version, which is
mainly used in the paper, is due to Absil et al. [1, Theorem 3.4].

######  Definition 2.2.

Let $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ be a differentiable function. We
say that $f$ satisfies the KL property at $\bar{x}\in{\rm I\\!R}^{n}$ if there
exist a number $\eta>0$, a neighborhood $U$ of $\bar{x}$, and a nondecreasing
function $\psi:(0,\eta)\rightarrow(0,\infty)$ such that the function $1/\psi$
is integrable over $(0,\eta)$ and we have

$\displaystyle\left\|\nabla f(x)\right\|\geq\psi\big{(}f(x)-f(\bar{x})\big{)}$
(2.7)

for all $x\in U$ with $f(\bar{x})<f(x)<f(\bar{x})+\eta$.

######  Remark 2.3.

For smooth functions $f$, the KL property from Definition 2.2 is weaker than
the KL property of $f$ at $\bar{x}$ introduced by Attouch et al. in [5]
meaning that there exist a number $\eta>0$, a neighborhood $U$ of $\bar{x}$,
and a continuous concave function $\varphi:[0,\eta]\rightarrow[0,\infty)$ such
that

  * (i)

$\varphi(0)=0$;

  * (ii)

$\varphi$ is $\mathcal{C}^{1}$-smooth on $(0,\eta)$;

  * (iii)

$\varphi^{\prime}>0$ on $(0,\eta)$;

  * (iv)

for all $x\in U$ with $f(\bar{x})<f(x)<f(\bar{x})+\eta$, we have

$\displaystyle\varphi^{\prime}\big{(}f(x)-f(\bar{x})\big{)}\left\|\nabla
f(x)\right\|\geq 1.$ (2.8)

Supposing that $f$ satisfies the KL property at $\bar{x}$ in the sense of
Attouch et al., we now show that it satisfies the KL property from Definition
2.2. Indeed, take $\eta,\ U$, and the function $\varphi$ satisfying conditions
(i)-(iv) in Remark 2.3. By (iii), the function
$\psi:(0,\eta)\rightarrow[0,\infty)$ given by

$\displaystyle\psi(x):=1/\varphi^{\prime}(x)\;\text{ for all }\;x\in(0,\eta)$

is well-defined. Since $\varphi$ is concave, $\varphi^{\prime}$ is
nonincreasing. Therefore, $1/\psi=\varphi^{\prime}$ is a nondecreasing
positive function that is integrable on $(0,\eta)$. Moreover, by
$1/\psi=\varphi^{\prime}$ we get that (2.8) and (2.7) are equivalent. Thus $f$
satisfies the KL property at $\bar{x}$ in the sense of Definition 2.2.

It has been realized that KL property in the sense of Attouch et al., and
hence the one from Definition 2.2, is satisfied in broad settings. In
particular, it holds at every nonstationary point of $f$; see [5, Lemma 2.1
and Remark 3.2(b)]. Furthermore, it is proved at the original paper by
Łojasiewicz [37] that any analytic function $f:{\rm I\\!R}^{n}\rightarrow{\rm
I\\!R}$ satisfies the KL property at every point $\bar{x}$ with
$\varphi(t)\leavevmode\nobreak\ =\leavevmode\nobreak\ Mt^{1-q}$ for some
$q\in[0,1)$. Typical smooth functions satisfying this property are
semialgebraic functions and also those from the more general class of
functions definable in o-minimal structures; see [12, 34]. For other examples
of functions satisfying the KL property, we refer the reader to [5, 35] and
the bibliographies therein.

##  3 Abstract Convergence Results for Linesearch Methods

In this section, we establish properties for a general class of linesearch
methods of type (1.2), which provide major tools for convergence analysis of
IRG methods in Section 5. One of the most important results desired for
linesearch methods is as follows:

$\displaystyle\text{ every accumulation point of }\;\\{x^{k}\\}\;\text{ is a
stationary point of }\;f.$ (3.1)

By the continuity of the gradient mapping, the desired property (3.1)
automatically holds if for each accumulation point $\bar{x}$ of
$\left\\{x^{k}\right\\}$ we can find an infinite set $J\subset{\rm I\\!N}$
such that $x^{k}\overset{J}{\rightarrow}\bar{x}$ and $\nabla
f(x^{k})\overset{J}{\rightarrow}0$. If the exact information on the gradient
is unknown while $\left\\{d^{k}\right\\}$ is gradient associated with
$\left\\{x^{k}\right\\}$, i.e., (2.4) is satisfied, then property (3.1) is
satisfied when

$\displaystyle x^{k}\overset{J}{\rightarrow}\bar{x}\;\text{ and
}\;d^{k}\overset{J}{\rightarrow}0\;\text{ for some infinite set
}\;J\subset{\rm I\\!N}.$ (3.2)

We are going to show that (3.2) holds whenever $0$ is an accumulation point of
$\left\\{d^{k}\right\\}$ and

$\displaystyle\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|\cdot\left\|d^{k}\right\|<\infty.$
(3.3)

The following lemma is new and is crucial in the convergence analysis for many
linesearch methods.

######  Lemma 3.1.

Let $\left\\{x^{k}\right\\}$ and $\left\\{d^{k}\right\\}$ be sequences
satisfying (3.3). If $\bar{x}$ is an accumulation point of
$\left\\{x^{k}\right\\}$ and if $0$ is an accumulation point of
$\left\\{d^{k}\right\\}$, then there exists an infinite set $J\subset{\rm
I\\!N}$ such that

$\displaystyle x^{k}\overset{J}{\rightarrow}\bar{x}\;\mbox{ and
}\;d^{k}\overset{J}{\rightarrow}0.$ (3.4)

[Proof.] If $x^{k}\rightarrow\bar{x}$ as $k\to\infty$, the conclusion
obviously holds, so suppose that $x^{k}\not\rightarrow\bar{x}$. It suffices to
show that for any $\delta>0$ sufficiently small and any $N\in{\rm I\\!N}$
there is a number $k_{N}\geq N$ such that

$\displaystyle\|x^{k_{N}}-\bar{x}\|<\delta\;\text{ and
}\;\|d^{k_{N}}\|<\delta.$

Fix such $\delta>0$ and $N\in{\rm I\\!N}$. Since $\delta$ is sufficiently
small and $x^{k}\not\rightarrow\bar{x}$, suppose that the set

$\displaystyle A_{1}:=\big{\\{}k\geq
N\;\big{|}\;\|x^{k}-\bar{x}\|\geq\delta\big{\\}}\;\text{ is infinite}.$

As $\bar{x}$ is an accumulation point of $\left\\{x^{k}\right\\}$ and $0$ is
an accumulation point of $\left\\{d^{k}\right\\}$, we get that

$\displaystyle A_{2}:$ $\displaystyle=\big{\\{}k\geq
N\;\big{|}\;\|x^{k}-\bar{x}\|<\delta\big{\\}}\;\text{ is infinite},$
$\displaystyle A_{3}:$ $\displaystyle=\big{\\{}k\geq
N\;\big{|}\;\|x^{k}-\bar{x}\|<\delta/2\big{\\}}\;\text{ is infinite},$
$\displaystyle A_{4}:$ $\displaystyle=\big{\\{}k\geq
N\;\big{|}\;\|d^{k}\|<\delta\big{\\}}\;\text{ is infinite}.$

It suffices to verify that $A_{2}\cap A_{4}\neq\emptyset.$ Suppose on the
contrary that $A_{2}\cap A_{4}=\emptyset$, i.e.,

$\displaystyle\|d^{k}\|\geq\delta\;\text{ for all }\;k\in A_{2}.$

By (3.3), we have the estimates

$\displaystyle\infty>\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|\cdot\left\|d^{k}\right\|$
$\displaystyle\geq\sum_{k\in
A_{2}}\left\|x^{k+1}-x^{k}\right\|\cdot\left\|d^{k}\right\|$
$\displaystyle\geq\delta\sum_{k\in A_{2}}\left\|x^{k+1}-x^{k}\right\|,$

which ensure the series convergence

$\displaystyle\sum_{k\in A_{2}}\left\|x^{k+1}-x^{k}\right\|<\infty.$ (3.5)

Taking any number $K\in A_{3}$, we also have $K\in A_{2}.$ Since $A_{1}$ is
infinite and $A_{1},A_{2}$ form a partition of the set
$\left\\{N,N+1,\ldots\right\\}$ including $K$, there exists a number
$\widehat{K}\in A_{1}$ with $\widehat{K}>K$ such that
$K,K+1,\ldots,\widehat{K}-1\in A_{2}$. Then we have the estimates

$\displaystyle\left\|x^{\widehat{K}}-x^{K}\right\|\geq\left\|x^{\widehat{K}}-\bar{x}\right\|-\left\|x^{K}-\bar{x}\right\|\geq\delta-\delta/2=\delta/2.$

Using the triangle inequality and (3.5) gives us

$\displaystyle\delta/2\leq\left\|x^{\widehat{K}}-x^{K}\right\|\leq\sum_{i=K}^{\widehat{K}-1}\left\|x^{i+1}-x^{i}\right\|\leq\sum_{i\geq
K,\;i\in A_{2}}\left\|x^{i+1}-x^{i}\right\|\xrightarrow[K\in
A_{3}]{K\rightarrow\infty}0,$

which brings us to a contradiction that completes the proof of the lemma.

######  Remark 3.2.

Our proof of Lemma 3.1 is inspired by the proofs of Kiwiel in [32, Theorem
3.3(iii)], [33, Theorem 3.8(iii)] and of Burke and Lin in [17, Theorem 5]. If
$0$ is not an accumulation point of $\\{d^{k}\\}$, then (3.3) implies that
$\\{x^{k}\\}$ is convergent. Indeed, the negation of the statement that $0$ is
an accumulation point of $\\{d^{k}\\}$ yields the existence of $\tau>0$ and
$K\in{\rm I\\!N}$ such that

$\|d^{k}\|\geq\;\tau\text{ for all }\;k\geq K.$

It follows from (3.3) that

$\tau\sum_{k=K}^{\infty}\left\|x^{k+1}-x^{k}\right\|\leq\sum_{k=K}^{\infty}\left\|x^{k+1}-x^{k}\right\|\cdot\left\|d^{k}\right\|<\infty,$

which implies that $\\{x^{k}\\}$ is a Cauchy sequence, and thus it converges.

Next we recall classical results that describe important properties of the set
of accumulation points generated by a sequence satisfying a limit condition
introduced by Ostrowski; see (3.6) below. The result from Lemma 3.3(i) was
first established in [45, Theorem 28.1], while assertion (ii) of this lemma
appeared in [23]. These results are also stated as Theorem 8.3.9 and Theorem
8.3.10 in the book of Facchinei and Pang [24]. More recent usage of the of the
Ostrowski condition in the framework of linesearch methods can be found in
[13, Lemma 5(iii)].

######  Lemma 3.3.

Let $\left\\{x^{k}\right\\}$ be a sequence satisfying the Ostrowski condition

$\displaystyle\lim_{k\rightarrow\infty}\|x^{k+1}-x^{k}\|=0.$ (3.6)

Then the following assertions hold:

  * (i)

If $\left\\{x^{k}\right\\}$ is bounded, then the set of accumulation points of
$\left\\{x^{k}\right\\}$ is nonempty, compact, and connected in ${\rm
I\\!R}^{n}$.

  * (ii)

If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then this
sequence converges to it.

Now we are ready to establish the main result of this section revealing major
convergence properties of a general class of linesearch methods.

######  Theorem 3.4.

Let $\left\\{x^{k}\right\\}$ be a sequence generated by a linesearch method
(1.2) such that:

  * (a)

$\left\\{d^{k}\right\\}$ is gradient associated with $\left\\{x^{k}\right\\}$;

  * (b)

$0$ is an accumulation point of $\left\\{d^{k}\right\\};$

  * (c)

$\displaystyle{\sum_{k=1}^{\infty}}t_{k}\|d^{k}\|^{2}<\infty.$

Then every accumulation point of $\left\\{x^{k}\right\\}$ is a stationary
point of $f$. Moreover, if $\left\\{t_{k}\right\\}$ is bounded from above,
then the following assertions hold:

  * (i)

If $\left\\{x^{k}\right\\}$ is bounded, then the set of accumulation points of
$\left\\{x^{k}\right\\}$ is nonempty, compact, and connected.

  * (ii)

If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then this
sequence converges to it.

[Proof.] Let $\bar{x}$ be an accumulation point of $\left\\{x^{k}\right\\}$.
Note that (c) is equivalent to (3.3) under the linesearch relationship
$x^{k+1}=x^{k}+t_{k}d^{k}$ in (1.2). Applying Lemma 3.1 with taking into
account (b) and (c), we can find an infinite set $J\subset{\rm I\\!N}$ such
that $x^{k}\overset{J}{\rightarrow}\bar{x}$ and
$d^{k}\overset{J}{\rightarrow}0$. Then (a) implies that $\nabla
f(x^{k})\overset{J}{\rightarrow}0$. Employing the continuity of $\nabla f$, we
have

$\displaystyle\nabla f(\bar{x})=\lim_{k\overset{J}{\rightarrow}\infty}\nabla
f(x^{k})=0,$

which tells us that $\bar{x}$ is a stationary point of $f$. Suppose now that
$\left\\{t_{k}\right\\}$ is bounded from above by some $\tau>0$. Using (c), we
immediately get

$\displaystyle\sum_{k=1}^{\infty}\|x^{k+1}-x^{k}\|^{2}=\sum_{k=1}^{\infty}t_{k}^{2}\|d^{k}\|^{2}\leq\tau\sum_{k=1}^{\infty}t_{k}\|d^{k}\|^{2}<\infty.$

This leads us to $\left\|x^{k+1}-x^{k}\right\|\rightarrow 0$ and verifies
assertions (i) and (ii) by applying Lemma 3.3.

Theorem 3.4 also allows us to ensure the stationarity of accumulation points
generated by linesearch methods (1.2) applied to functions satisfying the
$L$-descent condition (2.1), where the stepsize is either constant or
diminishing, and where the direction is gradient associated while satisfying
the following sufficient descent condition

$\displaystyle\langle\nabla
f(x^{k}),d^{k}\rangle\leq-\kappa\|d^{k}\|^{2}\;\text{ for all }\;k\in{\rm
I\\!N}$ (3.7)

with some constant $\kappa>0$. Note that condition (3.7) is different from the
gradient associated condition from Definition 2.1, since from (3.7) we only
have that $\nabla f(x^{k})\overset{J}{\rightarrow}0$ yields
$d^{k}\overset{J}{\rightarrow}0$ but the reverse implication may not hold. In
addition to the gradient descent and generalized Newton methods discussed
above, there exist many other linesearch methods using direction (3.7); e.g.,
the boosted difference of convex functions algorithm as in [3, Proposition
4]), the inexact Levenberg-Marquardt method as in [21, Algorithm 3.1]), and
the GS method for nonsmooth functions with non-normalized direction given in
[32, Section 4.1].

We have the following effective consequence of Theorem 3.4.

######  Corollary 3.5.

Let $\left\\{x^{k}\right\\}$ be a sequence generated by a linesearch method
(1.2). Suppose that $\inf f(x^{k})>-\infty$, and that we have the conditions:

  * (a)

$f$ satisfies the $L$-descent condition (2.1) for some $L>0$;

  * (b)

the sequence $\left\\{d^{k}\right\\}$ is gradient associated with
$\left\\{x^{k}\right\\}$ and satisfies (3.7) for some $\kappa>0;$

  * (c)

the sequence $\left\\{t_{k}\right\\}$ is not summable, i.e.,

$\displaystyle\displaystyle{\sum_{k=1}^{\infty}}t_{k}=\infty,$ (3.8)

and there are numbers $\delta>0$ and $N\in{\rm I\\!N}$ such that

$\displaystyle t_{k}\leq\dfrac{2\kappa-\delta}{L}\;\text{ for all }\;k\geq N.$
(3.9)

Then every accumulation point of $\left\\{x^{k}\right\\}$ is stationary for
$f$, and the following assertions hold:

  * (i)

If the sequence $\left\\{x^{k}\right\\}$ is bounded, then the collection of
accumulation points of $\left\\{x^{k}\right\\}$ is nonempty, compact, and
connected.

  * (ii)

If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then the
entire sequence $\left\\{x^{k}\right\\}$ converges to it.

Moreover, if $\left\\{t_{k}\right\\}$ is bounded away from $0,$ then $\nabla
f(x^{k})\rightarrow 0$ as $k\to\infty$.

[Proof.] It follows from (3.9) in condition (c) that

$\displaystyle\kappa-\dfrac{Lt_{k}}{2}\geq\dfrac{\delta}{2}\;\text{ for all
}\;k\geq N.$

Since $f$ satisfies $L$-descent condition (2.1), we deduce from (3.7) and the
latter inequality that

$\displaystyle f(x^{k+1})$ $\displaystyle\leq f(x^{k})+t_{k}\left\langle\nabla
f(x^{k}),d^{k}\right\rangle+\dfrac{Lt_{k}^{2}}{2}\left\|d^{k}\right\|^{2}$
$\displaystyle\leq
f(x^{k})-t_{k}\kappa\left\|d^{k}\right\|^{2}+\dfrac{Lt_{k}^{2}}{2}\left\|d^{k}\right\|^{2}$
$\displaystyle=f(x^{k})-t_{k}\left\|d^{k}\right\|^{2}\Big{(}\kappa-\dfrac{Lt_{k}}{2}\Big{)}$
$\displaystyle\leq
f(x^{k})-\dfrac{\delta}{2}t_{k}\left\|d^{k}\right\|^{2}\;\text{ for all
}\;k\geq N.$ (3.10)

Then summing up the relationships
$\dfrac{\delta}{2}t_{k}\left\|d^{k}\right\|^{2}\leq f(x^{k})-f(x^{k+1})$ over
$k=N,N+1,\ldots$ and using the assumption $\inf f(x^{k})>-\infty$ give us

$\displaystyle\sum_{k=N}^{\infty}t_{k}\left\|d^{k}\right\|^{2}<\infty.$ (3.11)

Now we show that $0$ is an accumulation point of $\left\\{d^{k}\right\\}$.
Suppose on the contrary that there exist a positive number $u$ and a natural
number $K\geq N$ such that

$\displaystyle\left\|d^{k}\right\|\geq u\;\text{ for all }\;k\geq K.$

Using this together with (3.11) imply that $\sum_{k=K}^{\infty}t_{k}<\infty$,
which contradicts (3.8). Therefore, $0$ is an accumulation point of
$\left\\{d^{k}\right\\}$. Combining the latter with (b), (3.11), and (3.9)
allows us to confirm that all the assumptions of Theorem 3.4 are satisfied.
Thus every accumulation point of $\\{x_{k}\\}$ is a stationary point of $f$,
and both assertions in (i) and (ii) hold.

If finally $\left\\{t_{k}\right\\}$ is bounded away from $0,$ it follows from
(3.11) that $d^{k}\rightarrow 0$ as $k\to\infty$. Since the sequence
$\left\\{d^{k}\right\\}$ is gradient associated with $\left\\{x^{k}\right\\}$
by (b), we get $\nabla f(x^{k})\rightarrow 0$.

######  Remark 3.6.

Let us compare Corollary 3.5 with two well-known results by Bertsekas [10]
about the convergence of linesearch methods. First we compare the result of
Corollary 3.5 in the case where $\left\\{t_{k}\right\\}$ is bounded away from
$0$ with Bertsekas’s result for the constant stepsize.

######  Proposition 3.7.

[10, Proposition 1.2.2] Let $\left\\{x^{k}\right\\}$ be a sequence generated
by a linesearch method $x^{k+1}=x^{k}+t_{k}d^{k}$, where the sequence
$\left\\{d^{k}\right\\}$ is gradient related. Assume that

$\displaystyle\left\|\nabla f(x)-\nabla f(y)\right\|\leq
L\left\|x-y\right\|\;\text{ for all }\;x,y\in{\rm I\\!R}^{n}$ (3.12)

with some constant $L>0$, and that for all $k\in{\rm I\\!N}$ we have
$d^{k}\neq 0$ and

$\displaystyle\varepsilon\leq t_{k}\leq(2-\varepsilon)\bar{t}_{k},$ (3.13)

where $\varepsilon$ is a fixed positive scalar, and where

$\displaystyle\bar{t}_{k}:=\dfrac{\left|\left\langle\nabla
f(x^{k}),d^{k}\right\rangle\right|}{L\left\|d^{k}\right\|^{2}}.$

Then every limit point of $\left\\{x^{k}\right\\}$ is a stationary point of
$f$.

Our comparison with this result are as follows:

  1. 1.

Observe first that the result of [10, Proposition 1.2.2] assumes the Lipschitz
continuity of $\nabla f$, while the proof works under the $L$-descent
condition (2.1). Thus there is no difference between the class of functions
considered in [10, Proposition 1.2.2] and Corollary 3.5.

  2. 2.

Regarding the stepsize selection, our choice is much simpler than the one used
in [10, Proposition 1.2.2]. Observe that in the direction selection, we use
$\left\\{d^{k}\right\\}$ as gradient associated with $\left\\{x^{k}\right\\}$
and satisfying the sufficient descent condition, while [10, Proposition 1.2.2]
used the gradient related direction. It is commented in the note after [10,
Proposition 1.2.2] that if the direction is chosen better, i.e., there are two
numbers $c_{1},c_{2}>0$ satisfying

$\displaystyle c_{1}\left\|\nabla f(x^{k})\right\|^{2}\leq-\left\langle\nabla
f(x^{k}),d^{k}\right\rangle,\quad\left\|d^{k}\right\|^{2}\leq
c_{2}\left\|\nabla f(x^{k})\right\|^{2},\quad k\in{\rm I\\!N},$ (3.14)

then the stepsize selection can be reduced to the one chosen above. It can be
seen that (3.14) yields the estimates

$\displaystyle\left\langle\nabla f(x^{k}),d^{k}\right\rangle\leq-
c_{1}\left\|\nabla
f(x^{k})\right\|^{2}\leq-\dfrac{c_{1}}{c_{2}}\left\|d^{k}\right\|^{2}\;\text{
for all }\;k\in{\rm I\\!N},$

and for any infinite set $J$ we have $d^{k}\overset{J}{\rightarrow}0$ if and
only if $\nabla f(x^{k})\overset{J}{\rightarrow}0$. Therefore, condition (b)
in Corollary 3.5 and the gradient related condition share the common direction
(3.14).

  3. 3.

Comparing the conclusions of Corollary 3.5 and of [10, Proposition 1.2.2],
observe that our result establishes the convergence to $0$ of the entire
sequence $\left\\{\nabla f(x^{k})\right\\}$, which is stronger than the
stationarity of accumulation points obtained by [10, Proposition 1.2.2].
Moreover, our results about the set of accumulation points and convergence to
an isolated accumulation point by using the Ostrowski condition are not given
in [10, Proposition 1.2.2].

Next we compare the usage of the diminishing stepsize in Corollary 3.5 with
the the corresponding result by Bertsekas [10].

######  Proposition 3.8.

[10, Proposition 1.2.3] Let $\left\\{x^{k}\right\\}$ be a sequence generated
by a linesearch method $x^{k+1}=x^{k}+t_{k}d^{k}$. Assume that $\nabla f$ is
$L$-Lipschitzian, and that there exist positive scalars $c_{1},c_{2}$ such
that (3.14) holds for all $k\in{\rm I\\!N}$. Suppose also that

$\displaystyle t_{k}\rightarrow 0\;\mbox{ and
}\;\sum_{k=0}^{\infty}t_{k}=\infty.$ (3.15)

Then either $f(x^{k})\rightarrow-\infty$, or $\left\\{f(x^{k})\right\\}$
converges to a finite value with $\nabla f(x^{k})\rightarrow 0$ as
$k\to\infty$. Furthermore, every accumulation point of
$\left\\{x^{k}\right\\}$ is a stationary point of $f$.

Here are our comparison with the latter proposition.

  1. 1.

The $L$-Lipschitz continuity of $\nabla f$ yields $L$-descent condition while
the converse implication fails; see the commentaries in Section 2. The
convergence of $\left\\{\nabla f(x^{k})\right\\}$ to $0$ is the main result of
[10, Proposition 1.2.3], and technically it cannot be derived without the
$L$-Lipschitz continuity of $\nabla f$ or its small modifications. Relaxing
the Lipschitz continuity of the gradient to the descent condition may allow us
to work with broader classes of functions by replacing the usual Euclidean
distance by the Bregman distance; see, e.g., [6, 15, 38].

  2. 2.

The diminishing stepsize (3.15) satisfies both conditions in Corollary 3.5(c),
while the converse implication may not hold.

  3. 3.

As already mentioned above, condition (3.14) yields (b) in Corollary 3.5.

  4. 4.

The conclusions of Corollary 3.5 provides the convergence to an isolated
stationary point, while [10, Proposition 1.2.3] does not establish this.

To summarize, if considering the stationarity of accumulation points only,
Corollary 3.5 covers [10, Proposition 1.2.3] with a larger class of objective
functions as well as descent directions. On the other hand, the convergence of
$\left\\{\nabla f(x^{k})\right\\}$ to $0$ is not obtained in Corollary 3.5
since the $L$-Lipschitz continuity is relaxed therein.

Next we present the convergence result for linesearch methods under the
fulfillment of the KL property, which is taken from [1, Theorem 3.4].

######  Proposition 3.9.

Let $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ be a $\mathcal{C}^{1}$-smooth
function, and let the sequence of iterations
$\left\\{x^{k}\right\\}\subset{\rm I\\!R}^{n}$ satisfy the following
conditions:

  * (H1)

(primary descent condition). There exists $\sigma>0$ such that for
sufficiently large $k\in{\rm I\\!N}$ we have

$\displaystyle f(x^{k})-f(x^{k+1})\geq\sigma\left\|\nabla
f(x^{k})\right\|\cdot\left\|x^{k+1}-x^{k}\right\|.$

  * (H2)

(complementary descent condition). For sufficiently large $k\in{\rm I\\!N}$,
we have

$\displaystyle\big{[}f(x^{k+1})=f(x^{k})\big{]}\Longrightarrow[x^{k+1}=x^{k}].$

If $\bar{x}$ is an accumulation point of $\left\\{x^{k}\right\\}$ and $f$
satisfies the KL property at $\bar{x}$, then $x^{k}\rightarrow\bar{x}$ as
$k\to\infty$.

Note that [1, Theorem 3.2] provides a detailed proof for Proposition 3.9 when
$f$ satisfies the KL property at $\bar{x}$ with $\psi(t)=Mt^{q}$ for some
$M>0$ and $q\in[0,1)$. The key ingredient of the proof is the existence of
some $k_{1}\in\mathbb{N}$ such that

$\displaystyle\left\|x^{k+1}-x^{k}\right\|$ $\displaystyle\leq\dfrac{1}{\sigma
M(1-q)}\left[(f(x^{k})-f(\bar{x}))^{1-q}-(f(x^{k+1})-f(\bar{x}))^{1-q}\right]\text{
for all }k\geq k_{1}.$ (3.16)

Using this, we can deduce that

$\displaystyle\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|<\infty,$ (3.17)

and so the sequence $\left\\{x^{k}\right\\}$ is convergent.

Next we address rates of convergence of linesearch methods of type (1.2).
Finding convergence rates for the gradient descent method in nonconvex
settings is an important issue that has received an increasing attention
recently; see, e.g., [29, 50] and the references therein. Our results in
Theorem 3.11 establish the rate of convergence of general linesearch methods
under the KL property and the boundedness of stepsizes away from $0$. The
proof below employs the technique developed in the proof of [4, Theorem 2] for
the proximal point method. This technique is also used in the proofs of
convergence rates for the difference of convex algorithm [36] and its boosted
version in [3, Theorem 1]. The next technical lemma taken from [3, Lemma 1] is
needed in what follows.

######  Lemma 3.10.

Let $\left\\{s_{k}\right\\}$ be a nonnegative sequence in ${\rm I\\!R}$, and
let $\alpha,\beta$ be some positive constants. Suppose that $s_{k}\rightarrow
0$ as $k\to\infty$ and that this sequence satisfies the condition

$\displaystyle s_{k}^{\alpha}\leq\beta(s_{k}-s_{k-1})\;\text{ for all
}\;k\in{\rm I\\!N}\;\text{ sufficiently large}.$

The following assertions hold:

  1. (i)

If $\alpha\in(0,1]$, then $s_{k+1}\leq\left(1-\dfrac{1}{\beta}\right)s_{k}$
for all $k\in{\rm I\\!N}$ sufficiently large, i.e., $\left\\{s_{k}\right\\}$
converges linearly to $0$ with rank $1-\dfrac{1}{\beta}.$

  2. (ii)

If $\alpha>1$, then there exists a number $\varrho>0$ such that

$\displaystyle s_{k}\leq\varrho k^{-\frac{1}{\alpha-1}}\;\text{ for all
}\;k\in{\rm I\\!N}\;\text{ sufficiently large}.$

Here is the aforementioned theorem about the convergence rates.

######  Theorem 3.11.

Let the sequences $\left\\{x^{k}\right\\}\subset{\rm I\\!R}^{n}$,
$\left\\{t_{k}\right\\}\subset{\rm I\\!R}_{+}$ and the numbers $\beta>0,\;c>0$
be such that $x^{k+1}\neq x^{k}$ for all $k\in{\rm I\\!N}$, and that we have

$\displaystyle
f(x^{k})-f(x^{k+1})\geq\dfrac{\beta}{t_{k}}\left\|x^{k+1}-x^{k}\right\|^{2}\;\text{
and }\;\left\|\nabla
f(x^{k})\right\|\leq\dfrac{c}{t_{k}}\left\|x^{k+1}-x^{k}\right\|$ (3.18)

for sufficiently large $k\in{\rm I\\!N}$. Suppose that the sequence
$\left\\{t_{k}\right\\}$ is bounded away from $0$, that $\bar{x}$ is an
accumulation point of $\left\\{x^{k}\right\\}$, and that $f$ satisfies the KL
property at $\bar{x}$ with $\psi(t)=Mt^{q}$ for some $M>0$ and $q\in(0,1)$.
The following convergence rates are guaranteed:

  * (i)

If $q\in(0,1/2]$, then the sequence $\left\\{x^{k}\right\\}$ converges
linearly to $\bar{x}$.

  * (ii)

If $q\in(1/2,1)$, then there exists a positive constant $\varrho$ such that

$\displaystyle\left\|x^{k}-\bar{x}\right\|\leq\varrho
k^{-\frac{1-q}{2q-1}}\;\text{ for sufficiently large }\;k\in{\rm I\\!N}.$

[Proof.] The conditions imposed in (3.18) imply that

$\displaystyle f(x^{k})-f(x^{k+1})\geq\dfrac{\beta}{c}\left\|\nabla
f(x^{k})\right\|\cdot\left\|x^{k+1}-x^{k}\right\|\;\text{ for sufficiently
large }\;k\in{\rm I\\!N},$

which ensures that assumption (H1) in Proposition 3.9 holds with
$\sigma:=\dfrac{\beta}{c}$. By $t_{k}>0$ for all $k\in{\rm I\\!N}$, the first
condition in (3.18) yields also assumption (H2) of this proposition. Let
$k_{1}\in{\rm I\\!N}$ be such that (3.16) is satisfied for all $k\geq k_{1}$,
which implies in turn inequality (3.17) and thus the convergence of
$\left\\{x^{k}\right\\}$ to $\bar{x}$. Moreover, the first condition in (3.18)
together with $x^{k+1}\neq x^{k}$ as $k\in{\rm I\\!N}$ implies that

$\displaystyle f(x^{k})\downarrow f(\bar{x}):=\bar{f}\;\text{ and
}\;f(x^{k})>\bar{f}\;\text{ for all }\;k\in{\rm I\\!N}.$ (3.19)

It follows from (3.17) and the triangle inequality that

$\displaystyle\left\|x^{i}-\bar{x}\right\|\leq\sum_{k=i}^{\infty}\left\|x^{k+1}-x^{k}\right\|=:s_{i}<\infty\;\text{
whenever }\;i\in{\rm I\\!N}.$

Therefore, the convergence rate of $x^{i}$ to $\bar{x}$ can be deduced from
the convergence rate of $s_{i}$ to $0$. Let $k_{1}$ be defined in (3.16) and
pick $i\geq k_{1}$. Summing up (3.16) from $i$ to any $p>i$ gives us

$\displaystyle\sum_{k=i}^{p}\left\|x^{k+1}-x^{k}\right\|\leq\dfrac{1}{\sigma
M(1-q)}\big{(}f(x^{i})-\bar{f}\big{)}^{1-q}.$

Letting $p\rightarrow\infty$, we get the estimate

$\displaystyle s_{i}\leq\dfrac{1}{\sigma
M(1-q)}\big{(}f(x^{i})-\bar{f}\big{)}^{1-q}\;\text{ for all }\;i\geq k_{1}.$
(3.20)

The KL property of $f$ at $\bar{x}$ with $\psi(t)=Mt^{q}$ allows us to find a
positive number $\eta$ and a neighborhood $U$ of $\bar{x}$ ensuring the
condition

$\displaystyle\left\|\nabla f(x)\right\|\geq
M\big{(}f(x)-\bar{f}\big{)}^{q}\;\mbox{ whenever }\;x\in
U,\;\bar{f}<f(x)<\bar{f}+\eta.$ (3.21)

Using (3.21), $x^{k}\rightarrow\bar{x}$, and (3.19) gives us a natural number
$k_{2}>k_{1}$ such that

$\displaystyle\left\|\nabla f(x^{i})\right\|\geq
M\big{(}f(x^{i})-\bar{f}\big{)}^{q}\;\text{ for all }\;i\geq k_{2}.$ (3.22)

Let $\bar{t}>0$ be a lower bound of $\left\\{t_{k}\right\\}$. Combining this
with (3.22) and the second inequality in (3.18), we have the estimates

$\displaystyle\big{(}f(x^{i})-\bar{f}\big{)}^{q}$
$\displaystyle\leq\dfrac{1}{M}\left\|\nabla
f(x^{i})\right\|\leq\dfrac{c}{Mt_{i}}\left\|x^{i+1}-x^{i}\right\|$
$\displaystyle\leq\dfrac{c}{M\bar{t}}\left\|x^{i+1}-x^{i}\right\|\;\text{ for
all }\;i\geq k_{2}.$ (3.23)

Involving further (3.20) and (3.23) ensures that

$\displaystyle s_{i}^{\frac{q}{1-q}}$ $\displaystyle\leq\left(\dfrac{1}{\sigma
M(1-q)}\right)^{\frac{q}{1-q}}\big{(}f(x^{i})-\bar{f}\big{)}^{q}$
$\displaystyle\leq\left(\dfrac{1}{\sigma
M(1-q)}\right)^{\frac{q}{1-q}}\dfrac{c}{M\bar{t}}\left\|x^{i+1}-x^{i}\right\|.$

Define $\alpha:=\dfrac{q}{1-q}$ and $\beta:=\left(\dfrac{1}{\sigma
M(1-q)}\right)^{\frac{q}{1-q}}\dfrac{c}{M\bar{t}}$, and then rewrite the
latter estimate as

$\displaystyle s_{i}^{\alpha}\leq\beta(s_{i}-s_{i-1})\;\text{ for all }\;i\geq
k_{2}.$

Applying finally Lemma 3.10, we verify the convergence rates in (i), (ii), and
(iii).

By employing the iterative procedure $x^{k+1}=x^{k}+t_{k}d^{k},$ the
conditions in (3.18) can be rewritten as the following estimates:

$\displaystyle f(x^{k})-f(x^{k+1})\geq\beta
t_{k}\left\|d^{k}\right\|^{2}\;\text{ and }\;\left\|\nabla
f(x^{k})\right\|\leq c\left\|d^{k}\right\|.$

Note that, in addition to the IRG methods as shown in Section 5, these
conditions are also satisfied for the generalized damped Newton method as
proved in [30, Theorem 4.2].

##  4 General Scheme for Inexact Reduced Gradient Methods

In this section, we design a general framework for our novel IRG methods and
establish their basic properties prior to constructing particular methods of
this type with various stepsize selections. As mentioned in Section 1, the
motivation to design the IRG methods comes from the gradient sampling (GS)
method by Burke et al. [16] and further developments in Kiwiel [32, Section
4.1] for unconstrained problems of nonsmooth optimization.

Although the focus of this paper is on smooth optimization problems, we first
recall the perturbed notions of generalized differentiation for nonsmooth
functions and their smooth specifications employed in [16, 32] as well as
different ones used in our algorithms. In what follows, the notation
$\mathbb{B}(\bar{x},\varepsilon)$ stands for the closed ball centered at
$\bar{x}\in{\rm I\\!R}^{n}$ with radius $\varepsilon>0$, by ${\rm co}\,\Omega$
we understand the convex hull of a set $\Omega\subset{\rm I\\!R}^{n}$, and the
symbol $x\stackrel{{\scriptstyle\Omega}}{{\to}}\bar{x}$ indicates that
$x\to\bar{x}$ with $x\in\Omega$.

Let $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}$ be a real-valued function locally
Lipschitzian around some point $\bar{x}\in{\rm I\\!R}^{n}$. The generalized
differential notion employed in [16, 32] is introduced by Goldstein [26] under
the name of the $\varepsilon$-generalized gradient of $f$ at $\bar{x}$. It is
defined by

$\overline{\partial}_{\varepsilon}f(\bar{x}):={\rm
co}\,\overline{\partial}f(\mathbb{B}\big{(}\bar{x},\varepsilon)\big{)},\quad\varepsilon>0,$
(4.1)

via the convex hull of the (Clarke) generalized gradient

$\overline{\partial}f(\bar{x}):={\rm
co}\Big{\\{}\lim_{x\overset{\Omega}{\rightarrow}\bar{x}}\nabla f(x)\Big{\\}},$
(4.2)

where $\Omega$ denotes the set of full measure on which $f$ is differentiable;
see [18, 49] for more details. If $f$ is ${\cal C}^{1}$-smooth around
$\bar{x}$, then $\overline{\partial}f(\bar{x})$ in (4.2) reduces to the
gradient $\\{\nabla f(\bar{x})\\}$, and hence the $\varepsilon$-generalized
gradient (4.1) is represented by

$\overline{\partial}_{\varepsilon}f(\bar{x})={\rm co}\,\nabla
f\big{(}\mathbb{B}(\bar{x},\varepsilon)\big{)},\quad\varepsilon>0.$ (4.3)

Prior to introducing our IRG methods, let us briefly describe the GS scheme
based on the $\varepsilon$-generalized gradient in the smooth case (4.3).
Recall that the projection ${\rm Proj}(x,\Omega)$ of $x\in{\rm I\\!R}^{n}$
onto a closed and convex set $\Omega\subset{\rm I\\!R}^{n}$ is a singleton
that is characterized by

$\displaystyle u={\rm Proj}(x,\Omega)\;\text{ if and only if $u\in\Omega$ and
}\;\left\langle y-u,x-u\right\rangle\leq 0\;\text{ for all }\;y\in\Omega.$
(4.4)

Given a ${\cal C}^{1}$-smooth function $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}$,
an initial point $x^{1}$, initial radii $\varepsilon_{1},r_{1}$, and a natural
number $m\geq n+1$, the GS method approximately calculates the
$\varepsilon_{k}$-generalized gradient of $f$ at the $k^{\rm th}$ iteration
$x^{k}$ by taking the convex hull of the gradients

$\displaystyle\partial_{\varepsilon_{k}}f(x^{k})\approx{\rm co}\left\\{\nabla
f(x^{k}),\nabla f(x^{k,1}),\nabla f(x^{k,2}),\ldots,\nabla
f(x^{k,m})\right\\}=:\mathcal{G}_{k},$ (4.5)

where the points $x^{k,i}$ with $i=1,\ldots,m$ are chosen uniformly in
$\mathbb{B}(x^{k},\varepsilon_{k})$. If
$\mathcal{G}_{k}\cap\mathbb{B}(0,r_{k})\neq\emptyset$, then both
$\varepsilon_{k}$ and $r_{k}$ are reduced in the sense that
$\varepsilon_{k+1}=\mu\varepsilon_{k}$ and $r_{k+1}=\theta r_{k}$ for some
$\mu,\theta\in(0,1)$, while the reference point $x^{k}$ stays the same.
Otherwise, the new iterative point $x^{k+1}$ is updated by the procedure
$x^{k+1}=x^{k}+t_{k}d^{k}$, where $-d^{k}={\rm Proj}(0,\mathcal{G}_{k})$, and
where $t_{k}$ is given by the backtracking linesearch. This procedure is
illustrated on Figure 2 for the case where $n=2$ and $m=3$.

Figure 2: Illustration for the GS method when $x^{k}$ is updated

In contrast to [16, 32], in our IRG methods proposed in this paper, we use
another subdifferential construction for locally Lipschitzian functions $f$ at
$\bar{x}$ defined as follows

$\widehat{\partial}_{\varepsilon}f(\bar{x}):=\left\\{v\in{\rm
I\\!R}^{n}\;\Big{|}\;\liminf_{x\rightarrow\bar{x}}\dfrac{f(x)-f(\bar{x})-\langle
v,x-\bar{x}\rangle}{\left\|x-\bar{x}\right\|}\geq-\varepsilon\right\\},\quad\varepsilon\geq
0.$ (4.6)

This construction is known in variational analysis and optimization as the
(Fréchet) $\varepsilon$-subdifferential of $f$ at $\bar{x}$. When
$\varepsilon=0$, (4.6) reduces to the regular subdifferential
$\widehat{\partial}f(\bar{x})$; see, e.g., [39, 40, 49] and the references
therein. For $\varepsilon>0$, the $\varepsilon$-subdifferential goes back to
the early work by Kruger and Mordukhovich, where it was used via a limiting
procedure to adequately extend the notion of the (Mordukhovich) limiting
subdifferential $\partial f(\bar{x})$ from ${\rm I\\!R}^{n}$ to Banach spaces;
see [39, 40] with more discussions and references. In this paper, we show that
(4.6) for $\varepsilon>0$ is useful to design and justify numerical algorithms
for smooth problems in finite dimensions.

The next proposition gives us the expression of (4.6) for differentiable
functions.

######  Proposition 4.1.

Let $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ be differentiable at
$\bar{x}\in{\rm I\\!R}^{n}$, and let $\varepsilon>0$. Then we have

$\widehat{\partial}_{\varepsilon}f(\bar{x})=\mathbb{B}\big{(}\nabla
f(\bar{x}),\varepsilon\big{)}.$ (4.7)

[Proof.] Since $f$ is differentiable at $\bar{x}$, we have

$\displaystyle\lim_{x\rightarrow\bar{x}}\dfrac{f(x)-f(\bar{x})-\left\langle\nabla
f(\bar{x}),x-\bar{x}\right\rangle}{\left\|x-\bar{x}\right\|}=0.$ (4.8)

Take any $v\in\mathbb{B}(\nabla f(\bar{x}),\varepsilon)$ and write $v=\nabla
f(\bar{x})+h$ with $\left\|h\right\|\leq\varepsilon$. It follows from (4.8)
that

$\displaystyle\liminf_{x\rightarrow\bar{x}}\dfrac{f(x)-f(\bar{x})-\left\langle\nabla
f(\bar{x})+h,x-\bar{x}\right\rangle}{\left\|x-\bar{x}\right\|}$
$\displaystyle=\liminf_{x\rightarrow\bar{x}}\dfrac{-\left\langle
h,x-\bar{x}\right\rangle}{\left\|x-\bar{x}\right\|}$
$\displaystyle\geq\liminf_{x\rightarrow\bar{x}}\dfrac{-\left\|h\right\|\cdot\left\|x-\bar{x}\right\|}{\left\|x-\bar{x}\right\|}$
$\displaystyle=-\left\|h\right\|\geq-\varepsilon.$

This means that $v\in\widehat{\partial}_{\varepsilon}f(\bar{x})$, and so
$\widehat{\partial}_{\varepsilon}f(\bar{x})\supset\mathbb{B}(\nabla
f(\bar{x}),\varepsilon)$. To verify the converse implication, pick any
$v\in\widehat{\partial}_{\varepsilon}f(\bar{x})$ meaning that

$\displaystyle\liminf_{x\rightarrow\bar{x}}\dfrac{f(x)-f(\bar{x})-\left\langle
v,x-\bar{x}\right\rangle}{\left\|x-\bar{x}\right\|}\geq-\varepsilon$

and deduce from the latter and (4.8) that

$\displaystyle\liminf_{x\rightarrow\bar{x}}\dfrac{\left\langle\nabla
f(\bar{x})-v,x-\bar{x}\right\rangle}{\left\|x-\bar{x}\right\|}\geq-\varepsilon.$
(4.9)

Then for any $e\in\mathbb{B}(0,1)$ we get from (4.9) and
$\bar{x}\pm\frac{1}{k}e\rightarrow\bar{x}$ as $k\rightarrow\infty$ that

$\displaystyle\lim_{k\rightarrow\infty}\dfrac{\left\langle\nabla
f(\bar{x})-v,\frac{1}{k}e\right\rangle}{\left\|\frac{1}{k}e\right\|}\geq-\varepsilon\quad\text{
and }\quad\lim_{k\rightarrow\infty}\dfrac{\left\langle\nabla
f(\bar{x})-v,-\frac{1}{k}e\right\rangle}{\left\|-\frac{1}{k}e\right\|}\geq-\varepsilon,$

which implies in turn that $\left|\left\langle\nabla
f(\bar{x})-v,e\right\rangle\right|\leq\varepsilon$. Since this holds for all
$e\in\mathbb{B}(0,1)$, it follows that $\left\|\nabla
f(\bar{x})-v\right\|\leq\varepsilon$, i.e., $v\in\mathbb{B}(\nabla
f(\bar{x}),\varepsilon)$, which verifies the claimed representation (4.7).

The following table summarizes the main differences between the
$\varepsilon$-generalized gradient in (4.3) and $\varepsilon$-subdifferential
in (4.7) for smooth functions.

| $\overline{\partial}_{\varepsilon}f(\bar{x})={\rm co}\,\nabla f\big{(}\mathbb{B}(\bar{x},\varepsilon)\big{)}$ | $\widehat{\partial}_{\varepsilon}f(\bar{x})=\mathbb{B}\big{(}\nabla f(\bar{x}),\varepsilon\big{)}$
---|---|---
How to calculate? | $\approx{\rm co}\left\\{\nabla f(x^{k})\;\big{|}\;x^{k}\in\mathbb{B}(\bar{x},\varepsilon),\;k\in\\{1,\ldots,m\\},\;m\geq n+1\right\\}$ | has explicit form
How to find projection? |  $\approx$ projection onto the convex hull above | has explicit form
Table 1: Comparison between the $\varepsilon$-generalized gradient and the
$\varepsilon$-subdifferential for smooth functions

We can see from Table 1 that the numerical implementation of algorithms
involving $\widehat{\partial}_{\varepsilon}f$ is much easier in comparison
with the GS method using $\overline{\partial}_{\varepsilon}f$ for smooth
functions. One more advantage of algorithms implementing the
$\varepsilon$-subdifferential (4.6) in comparison with the usage of
$\varepsilon$-generalized gradient (4.1) is that, for nonsmooth functions,
algorithms based on (4.1) lead us to Clarke stationary points satisfying
$0\in\overline{\partial}f(\bar{x})$ in terms of the generalized gradient
(4.2). On the other hand, the usage of (4.6) brings us to the more subtle
Mordukhovich stationary $0\in\partial f(\bar{x})$ due to the representation

$\partial f(\bar{x})=\big{\\{}v\in{\rm
I\\!R}^{n}\;\big{|}\;\exists\,\varepsilon_{k}\downarrow
0,\;x_{k}\to\bar{x},\;v_{k}\to v\;\mbox{ with
}\;v_{k}\in\widehat{\partial}_{\varepsilon_{k}}f(x_{k})\big{\\}}$

of the limiting subdifferential, which works even in Banach spaces with the
appropriate convergence of $v_{k}\to v$; cf. [40, Theorem 1.28] and [39,
Theorem 1.89]. Since we have

$\overline{\partial}f(\bar{x})={\rm co}\,\partial f(\bar{x})$

when $f\colon{\rm I\\!R}^{n}\to{\rm I\\!R}$ is locally Lipschitzian around
$\bar{x}$, the condition $0\in\partial f(\bar{x})$ is more selective than that
of $0\in\overline{\partial}f(\bar{x})$ to find stationary points and
minimizers of Lipschitzian functions and will be investigated in our future
development of IRG algorithms for nonsmooth optimization problems.

Now we are ready to formulate our general algorithmic framework (the Master
Algorithm) for IRG methods with the usage of the $\varepsilon$-subdifferential
representation (4.7) for smooth functions while without considering yet
particular stepsize selections.

######  Algorithm 1 (general framework for IRG methods).

######  Step 0 (initialization).

Select an initial point $x^{1}\in{\rm I\\!R}^{n}$, initial radii
$\varepsilon_{1},r_{1}>0$, radius reduction factors $\mu,\theta\in(0,1)$, a
sequence of manually controlled errors $\left\\{\rho_{k}\right\\}\subset{\rm
I\\!R}_{+}.$

######  Step 1 (inexact gradient and stopping criterion).

Choose $g^{k}$ such that

$\displaystyle\left\|g^{k}-\nabla
f(x^{k})\right\|\leq\min\left\\{\varepsilon_{k},\rho_{k}\right\\}.$ (4.10)

######  Step 2 (radius update).

If $\left\|g^{k}\right\|\leq r_{k}+\varepsilon_{k}$, then set $r_{k+1}:=\mu
r_{k},\;\varepsilon_{k+1}:=\theta\varepsilon_{k}$, $d^{k}:=0$, and go to Step
3. Otherwise, set $r_{k+1}:=r_{k}$, $\varepsilon_{k+1}:=\varepsilon_{k}$, and

$\displaystyle
d^{k}:=-\dfrac{\left\|g^{k}\right\|-\varepsilon_{k}}{\left\|g^{k}\right\|}g^{k}.$
(4.11)

######  Step 3 (stepsize).

Choose $t_{k}>0$ by a specific rule.

######  Step 4 (iteration update).

Set $x^{k+1}:=x^{k}+t_{k}d^{k}$.

######  Step 5.

Increase $k$ by $1$ and go back to Step $1.$

Let us make some comments on the constructions of Algorithm 1. The first
remark concerns the novelty in the choice of errors and directions.

######  Remark 4.2.

We have the following observations:

  1. (i)

The selection of $\left\\{\rho_{k}\right\\}$ satisfying $\rho_{k}\rightarrow
0$ as $k\rightarrow\infty$ plays a vital role in the convergence analysis of
the IRG method with backtracking stepsize as shown later. In the remaining
cases, since the presence of $\rho_{k}$ is not necessary, we specify
$\rho_{k}:=\varepsilon_{k}$ for all $k\in{\rm I\\!N}$, which leads us to a
simplified form of the condition (4.10) as follows:

$\displaystyle\left\|g^{k}-\nabla f(x^{k})\right\|\leq\varepsilon_{k}.$ (4.12)

  2. (ii)

From (4.10), the radius $\varepsilon_{k}$ can be considered as an
automatically controlled error for the calculation of $\nabla f(x^{k})$, which
does not need to decrease after each iteration. This is different than the
choice $\varepsilon_{k}=ck^{-p}$ for $p\geq 1,c>0$ frequently used in the
well-known methods [10, 22, 25]. Moreover, Steps 1 and 2 also show that
$\left\|\nabla f(x^{k})\right\|\leq r_{k}+2\varepsilon_{k}$ when
$\varepsilon_{k}$ is reduced. Therefore, we can conclude intuitively that
$\left\|\nabla f(x^{k})\right\|$ is decreasing when $\varepsilon_{k}$ is
decreasing.

  3. (iii)

In the exact case when $g^{k}=\nabla f(x^{k})$ for all $k\in{\rm I\\!N}$, we
label our methods as the reduced gradient (RG) ones, which are different from
the standard gradient descent method. Indeed, it follows from Step 2 that
$d^{k}$ is either $0$, or is given by

$\displaystyle d^{k}=-\Big{(}\dfrac{\|\nabla
f(x^{k})\|-\varepsilon_{k}}{\|\nabla f(x^{k})\|}\Big{)}\nabla f(x^{k}).$
(4.13)

Therefore, the vector $d^{k}$ in (4.13) has the same direction as $-\nabla
f(x^{k})$ but its length is $\left\|\nabla f(x^{k})\right\|$ reduced by
$\varepsilon_{k}$ for each $k\in{\rm I\\!N}$.

Further we discuss and illustrate behavior of Algorithm 1 at the major steps
of iterations.

######  Remark 4.3.

Notice first that:

  * (i)

If $d^{k}\neq 0$, it follows from (4.11) and the definition of projections
that $d^{k}=-{\rm Proj}(0,\mathbb{B}(g^{k},\varepsilon_{k}))$.

  * (ii)

An illustration for Algorithm 1 can be seen in Figure 3.

Let $g^{1}$ be an approximate gradient of $\nabla f(x^{1})$ at the $1$st
iteration. Then Figure 3 shows that the two balls
$\mathbb{B}(g^{1},\varepsilon_{1})$ and $\mathbb{B}(0,r_{1})$ do not
intersect. This means by Step 2 that $r_{2}=r_{1}$,
$\varepsilon_{2}=\varepsilon_{1}$, and $d^{1}=-{\rm
Proj}(0,\mathbb{B}(g^{1},\varepsilon_{1}))$. Then we have a new point
$x^{2}=x^{1}+t_{1}d^{1}$ after choosing the stepsize $t_{1}>0$ as in Step 3
and Step 4.

At the $2$nd iteration, it can be seen in Figure 3 that the two balls
$\mathbb{B}(g^{2},\varepsilon_{2})$ and $\mathbb{B}(0,r_{2})$ intersect each
other. Thus by Step 2 of Algorithm 1, the radii $r_{2},\varepsilon_{2}$ are
reduced to $r_{3}=\mu r_{2}$ and $\varepsilon_{3}=\theta\varepsilon_{2}$,
while the direction $d^{2}$ is zero. The latter means that the iterative point
$x^{2}$ stays the same, i.e., $x^{3}=x^{2}$ from Step 4.

At the $3$rd iteration, although $\nabla f(x^{3})=\nabla f(x^{2})$, we still
need to recalculate an approximate gradient $g^{3}$ with a new error
$\min\left\\{\varepsilon_{3},\rho_{3}\right\\}$. In this iteration, the two
balls $\mathbb{B}(g^{3},\varepsilon_{3})$ and $\mathbb{B}(0,r_{3})$ do not
intersect, and hence the procedure is similar to that at the first iteration.

Figure 3: An illustration for IRG methods

  * (iii)

For each $k\in{\rm I\\!N}$, we have from Step 2 and Step 3 the equivalences

$\displaystyle x^{k+1}=x^{k}\Longleftrightarrow d^{k}=0\Longleftrightarrow
r_{k+1}=\mu
r_{k}\Longleftrightarrow\varepsilon_{k+1}=\theta\varepsilon_{k}\Longleftrightarrow\left\|g^{k}\right\|\leq
r_{k}+\varepsilon_{k}.$ (4.14)

The next proposition verifies the decent property of Algorithm 1.

######  Proposition 4.4.

In Algorithm 1, $\left\\{d^{k}\right\\}$ satisfies the sufficient descent
condition with constant $1,$ i.e.,

$\displaystyle\left\langle\nabla
f(x^{k}),d^{k}\right\rangle\leq-\left\|d^{k}\right\|^{2}\;\text{ for all
}\;k\in{\rm I\\!N}.$ (4.15)

[Proof.] Note that (4.15) automatically holds if $d^{k}=0$. Supposing that
$d^{k}\neq 0$ and using the construction of $d^{k}$ in Step 2, we have the
expression

$\displaystyle-d^{k}={\rm
Proj}\big{(}0,\mathbb{B}(g^{k},\varepsilon_{k})\big{)}.$

It follows from (4.10) that $\left\|g^{k}-\nabla
f(x^{k})\right\|\leq\varepsilon_{k}$, which means that $\nabla
f(x^{k})\in\mathbb{B}(g^{k},\varepsilon_{k})$. Invoking the projection
description for convex sets (4.4) yields

$\displaystyle\left\langle 0+d^{k},\nabla f(x^{k})+d^{k}\right\rangle\leq 0,$

which is in turn equivalent to

$\displaystyle\left\langle\nabla
f(x^{k}),d^{k}\right\rangle\leq-\left\|d^{k}\right\|^{2}$

and thus verifies the claim in (4.15).

Now we introduce the notion of null iterations and establish some properties
of such iterations related to the IRG methods.

######  Definition 4.5.

The $k^{\rm th}$ iteration of Algorithm 1 is called a null iteration if
$x^{k+1}=x^{k}$. The set of all null iterations is denoted by

$\mathcal{N}:=\big{\\{}k\in{\rm I\\!N}\;\big{|}\;x^{k+1}=x^{k}\big{\\}}.$

The next proposition collects important properties of null iterations.

######  Proposition 4.6.

Let
$\left\\{x^{k}\right\\},\left\\{g^{k}\right\\},\left\\{d^{k}\right\\},\left\\{\varepsilon_{k}\right\\}$,
and $\left\\{r_{k}\right\\}$ be sequences generated by Algorithm 1. The
following assertions hold:

  * (i)

$k\in\mathcal{N}$ if and only if either one of the equivalent conditions in
(4.14) holds.

  * (ii)

$\varepsilon_{k}\downarrow 0$ if and only if $r_{k}\downarrow 0$, which is
equivalent to the set $\mathcal{N}$ being infinite.

  * (iii)

If $\mathcal{N}$ is finite, then we have

$\displaystyle\left\|g^{k}\right\|>r_{N}+\varepsilon_{N}\;\text{ and
}\;\left\|d^{k}\right\|>r_{N}$

for all $k\geq N$, where $N:=\max\mathcal{N}+1$.

  * (iv)

If ${\rm I\\!N}\setminus\mathcal{N}$ is finite, then $\nabla f(x^{K})=0$ and
$\left\\{x^{k}\right\\}_{k\geq K}$ is a constant sequence, where we denote
$K:=\max\\{{\rm I\\!N}\setminus\mathcal{N}\\}+1$. Otherwise, $\bar{x}$ is an
accumulation point of $\left\\{x^{k}\right\\}$ if and only if it is an
accumulation point of $\left\\{x^{k}\right\\}_{k\in{\rm
I\\!N}\setminus\mathcal{N}}$, and therefore $x^{k}\rightarrow\bar{x}$ if and
only if $x^{k}\overset{{\rm
I\\!N}\setminus\mathcal{N}}{\longrightarrow}\bar{x}$.

[Proof.] Assertions (i) and (ii) follow directly from Definition 4.5. To
verify (iii), observe that for any natural number $k\geq N$, the $k^{\rm th}$
iteration is not a null one and then deduce from (i) that

$\displaystyle\varepsilon_{k+1}=\varepsilon_{k}=\varepsilon_{N},\quad
r_{k+1}=r_{k}=r_{N},\;\mbox{ and
}\;\left\|g^{k}\right\|>r_{k}+\varepsilon_{k}=r_{N}+\varepsilon_{N}.$

Together with Step 2 in Algorithm 1, this ensures that

$\displaystyle\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}>r_{k}=r_{N}.$

which readily justifies assertion (i).

The proof of (iv) is a bit more involved. Supposing that the set ${\rm
I\\!N}\setminus\mathcal{N}$ is finite, we have that $k\in\mathcal{N}$ for all
$k\geq K$. This means by (i) that

$\displaystyle
x^{k+1}=x^{k},\;\varepsilon_{k+1}=\theta\varepsilon_{k},\;r_{k+1}=\mu
r_{k},\;\text{ and }\;\left\|g^{k}\right\|\leq r_{k}+\varepsilon_{k}\;\text{
whenever }\;k\geq K.$

This tells us that $x^{k}=x^{K}$ for all $k\geq K$, and that
$\varepsilon_{k}\downarrow 0,\;r_{k}\downarrow 0$, and $g^{k}\rightarrow 0$ as
$k\to\infty$. Taking the limit as $k\rightarrow\infty$ in $\left\|g^{k}-\nabla
f(x^{k})\right\|\leq\varepsilon_{k}$ gives us $\nabla f(x^{k})\rightarrow 0$,
which yields $\nabla f(x^{K})=0$.

Supposing otherwise that the set ${\rm I\\!N}\setminus\mathcal{N}$ is
infinite, we obviously get that every accumulation point of
$\left\\{x^{k}\right\\}_{k\in{\rm I\\!N}\setminus\mathcal{N}}$ is an
accumulation point of $\left\\{x^{k}\right\\}$. Conversely, taking any
accumulation point $\bar{x}$ of $\left\\{x^{k}\right\\}$, it suffices to show
that

$\displaystyle\mbox{for any }\;\delta>0,\;N\in{\rm I\\!N}\;\mbox{ there exists
}\;k_{N}\in{\rm I\\!N}\setminus\mathcal{N},\;k_{N}\geq N\;\mbox{ with
}\;\left\|x^{k_{N}}-\bar{x}\right\|<\delta.$

To verify this, fixing $\delta>0$ and $N\in{\rm I\\!N}$ and remembering that
$\bar{x}$ is an accumulation point of $\left\\{x^{k}\right\\}$, we find $K\geq
N$ such that $\left\|x^{K}-\bar{x}\right\|<\delta$. If $K\in{\rm
I\\!N}\setminus\mathcal{N}$, choose $k_{N}:=K$. Otherwise, using that ${\rm
I\\!N}\setminus\mathcal{N}$ is infinite allows us to find $\widehat{K}\in{\rm
I\\!N}\setminus\mathcal{N}$ for which
$K,K+1,\ldots,\widehat{K}-1\in\mathcal{N}$. This ensures that

$\displaystyle{x^{\widehat{K}}}={x^{\widehat{K}-1}}=\ldots=x^{K+1}=x^{K},$

and therefore, with $k_{N}:=\widehat{K}$, we get that
$\left\|x^{k_{N}}-\bar{x}\right\|<\delta$. Since $\delta$ was chosen
arbitrarily, this clearly shows that $\bar{x}$ is an accumulation point of
$\left\\{x^{k}\right\\}_{k\in{\rm I\\!N}\setminus\mathcal{N}}$ and thus
completes the proof.

The last proposition here establishes relationships between convergence
properties of the sequences $\left\\{g^{k}\right\\}$ and
$\left\\{d^{k}\right\\}$ in Algorithm 1.

######  Proposition 4.7.

Let
$\left\\{g^{k}\right\\},\left\\{d^{k}\right\\},\;\left\\{\varepsilon_{k}\right\\}$,
and $\left\\{r_{k}\right\\}$ be sequences generated by Algorithm 1. Then for
any $k\in{\rm I\\!N}$ we have the estimates

$\displaystyle\left\|d^{k}\right\|\leq\left\|g^{k}\right\|\leq\left\|d^{k}\right\|+\varepsilon_{k}+r_{k}.$
(4.16)

Consequently, the following assertions hold:

  * (i)

$\varepsilon_{k}\downarrow 0$ if and only if there is an infinite set
$J\subset{\rm I\\!N}$ such that $g^{k}\overset{J}{\rightarrow}0$.

  * (ii)

For any infinite set $J\subset{\rm I\\!N}$, we have the equivalence

$\displaystyle g^{k}\overset{J}{\rightarrow}0\Longleftrightarrow
d^{k}\overset{J}{\rightarrow}0.$

[Proof.] Fix any $k\in{\rm I\\!N}$. If $k\in\mathcal{N}$, then we get by
Proposition 4.6(i) that $d^{k}=0$ and
$\left\|g^{k}\right\|\leq\varepsilon_{k}+r_{k}$. Otherwise, Step 2 in
Algorithm 1 yields
$\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}\leq\left\|g^{k}\right\|$.
In both cases, (4.16) holds.

To deduce (i) from (4.16), suppose that $\varepsilon_{k}\downarrow 0$ as
$k\to\infty$. By Proposition 4.6(ii) we have that $r_{k}\downarrow 0$ and the
set $\mathcal{N}$ is infinite. Then for any $\delta>0$ and $N\in{\rm I\\!N}$
there is $k\geq N$ with $k\in\mathcal{N}$ such that

$\displaystyle\left\|g^{k}\right\|\leq r_{k}+\varepsilon_{k}<\delta,$

where the first inequality follows from (4.14). Thus we can construct an
infinite set $J\subset{\rm I\\!N}$ such that
$g^{k}\overset{J}{\longrightarrow}0$. If conversely the sequence
$\left\\{\varepsilon_{k}\right\\}$ does not converge to $0$, then the set
$\mathcal{N}$ is finite by Proposition 4.6(ii). Using Proposition 4.6(iii)
confirms that $\left\\{g^{k}\right\\}$ is bounded away from $0$, which tells
us that such an index set $J$ does not exist.

To verify now assertion (ii), observe that assuming
$g^{k}\overset{J}{\rightarrow}0$, implies by the first inequality in (4.16)
that $d^{k}\overset{J}{\rightarrow}0$. Conversely, suppose that
$d^{k}\overset{J}{\rightarrow}0$ and deduce from Proposition 4.6(i) that the
set $\mathcal{N}$ is infinite. Then it follows from Proposition 4.6(ii) that
$\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow 0$ as $k\to\infty$. Using
the second inequality in (4.16), we arrive at $g^{k}\overset{J}{\rightarrow}0$
and thus complete the proof of the proposition.

Finally in this section, we deduce from the obtained results the following
desired property of the direction sequence $\left\\{d^{k}\right\\}$ in
Algorithms 1.

######  Corollary 4.8.

The sequence $\left\\{d^{k}\right\\}$ in Algorithms 1 is gradient associated
with $\left\\{x^{k}\right\\}$.

[Proof.] It follows from Proposition 4.7 that the convergence
$d^{k}\overset{J}{\rightarrow}0$ yields $g^{k}\overset{J}{\rightarrow}0$ and
$\varepsilon_{k}\downarrow 0.$ Thus we get $\nabla
f(x^{k})\overset{J}{\rightarrow}0$ by taking into account $\left\|g^{k}-\nabla
f(x^{k})\right\|\leq\varepsilon_{k}$ from (4.10). This shows therefore that
the sequence $\left\\{d^{k}\right\\}$ is gradient associated with
$\left\\{x^{k}\right\\}$.

##  5 Inexact Reduced Gradient Methods with Stepsize Selections

In this section, we develop novel IRG methods with the following selections of
stepsize rules: backtracking stepsize, constant stepsize, and diminishing
stepsize. Address first an IRG method with the backtracking line search.
Choose a line search scalar $\beta\in(0,1)$, a reduction factor
$\gamma\in(0,1)$, and an artificial stepsize of null iterations
$\tau\in(0,1)$. Consider the Master Algorithm 1 with the stepsize sequence
$\left\\{t_{k}\right\\}$ in Step 3 calculated as follows. If $d^{k}=0$, then
put $t_{k}:=\tau$. Otherwise, we set

$\displaystyle t_{k}:=\max\big{\\{}t\;\big{|}\;f(x^{k}+td^{k})\leq
f(x^{k})-\beta
t\big{\|}d^{k}\big{\|}^{2},\;t=1,\;\gamma,\;\gamma^{2},\ldots\big{\\}}.$ (5.1)

The next proposition shows that the stepsize sequence $\left\\{t_{k}\right\\}$
is well-defined.

######  Proposition 5.1.

If $d^{k}\neq 0$, then there exists a positive number $\bar{t}$ such that

$\displaystyle f(x^{k}+td^{k})\leq f(x^{k})-\beta
t\big{\|}d^{k}\big{\|}^{2}\;\text{ for all }\;t\in[0,\bar{t}],$

which ensures the existence of the stepsize sequence $\\{t_{k}\\}$ in (5.1).

[Proof.] Suppose that $d^{k}\neq 0$ and get by Proposition 4.4 that
$\left\langle\nabla f(x^{k}),d^{k}\right\rangle\leq-\left\|d^{k}\right\|^{2}$.
By the differentiability of $f$ at $x^{k}$, for each $t>0$ sufficiently small
we have

$\displaystyle f(x^{k}+td^{k})-f(x^{k})$ $\displaystyle=t\left\langle\nabla
f(x^{k}),d^{k}\right\rangle+o(t)\leq-t\left\|d^{k}\right\|^{2}+o(t)$
$\displaystyle=-\beta
t\left\|d^{k}\right\|^{2}+t\left((\beta-1)\left\|d^{k}\right\|^{2}+\dfrac{o(t)}{t}\right).$

Since $o(t)/t\rightarrow 0$ as $t\downarrow 0$ and since
$(\beta-1)\left\|d^{k}\right\|^{2}<0$, there exists $\bar{t}>0$ such that

$\displaystyle f(x^{k}+td^{k})\leq f(x^{k})-\beta
t\left\|d^{k}\right\|^{2}\;\text{ for all }\;t\in(0,\bar{t}].$

Therefore, all the numbers $t_{k}$ introduced in (5.1) are well-defined.

Now we are ready to establish a major result about the stationarity of
accumulation points of the iterative sequence generated by Algorithm 1 with
the backtracking line search.

######  Theorem 5.2.

Let $\left\\{x^{k}\right\\}$ be the sequence of iterations generated by
Algorithm 1 with the stepsize sequences $t_{k}$ from (5.1) of the backtracking
line search. Assume that $\inf f(x^{k})>-\infty$ and that $\rho_{k}\rightarrow
0$ as $k\rightarrow\infty$. Then the following assertions hold:

  * (i)

$\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow 0$ as $k\to\infty$.

  * (ii)

Every accumulation point of $\left\\{x^{k}\right\\}$ is a stationary point of
$f$.

  * (iii)

If the sequence $\left\\{x^{k}\right\\}$ is bounded, then the set of
accumulation points of $\left\\{x^{k}\right\\}$ is nonempty, compact, and
connected.

  * (iv)

If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then the
entire sequence $\left\\{x^{k}\right\\}$ converges to this point.

[Proof.] From the choice of $\left\\{t_{k}\right\\}$ and Step 4 in Algorithm
1, for every $k\in{\rm I\\!N}$ we have

$\displaystyle\beta t_{k}\left\|d^{k}\right\|^{2}\leq f(x^{k})-f(x^{k+1}).$
(5.2)

Since $\inf f(x^{k})>-\infty$, summing up on both sides of (5.2) over
$k=1,2,\ldots$ and using the relation $x^{k+1}=x^{k}+t_{k}d^{k}$, we get that

$\displaystyle\sum_{k=1}^{\infty}t_{k}\left\|d^{k}\right\|^{2}<\infty\quad\text{
and
}\quad\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|\cdot\left\|d^{k}\right\|<\infty.$
(5.3)

To verify assertion (i), recall by Proposition 4.6(ii) that the convergence
$\varepsilon_{k}\downarrow 0$ is equivalent to $r_{k}\downarrow 0$ and to the
fact that the set of null iterations $\mathcal{N}$ is infinite. Assume on the
contrary that $\mathcal{N}$ is finite. By Proposition 4.6(iii) with
$N=\max\mathcal{N}+1$, we have

$\displaystyle\left\|g^{k}\right\|>r_{N}+\varepsilon_{N}\;\text{ and
}\;\left\|d^{k}\right\|>r_{N}\;\text{ for all }\;k\geq N.$ (5.4)

Then (5.3) gives us $\sum_{k=1}^{\infty}t_{k}<\infty$ and thus
$t_{k}\downarrow 0$ as $k\to\infty$. Choosing a larger number $N$ if
necessary, we get that $t_{k}<1$ for all $k\geq N$. For such $k$, it follows
from the exit condition of the algorithm that

$\displaystyle-\gamma^{-1}\beta
t_{k}\left\|d^{k}\right\|^{2}<f(x^{k}+\gamma^{-1}t_{k}d^{k})-f(x^{k}).$ (5.5)

By the classical mean value theorem, there exists some
$\widetilde{x}^{k}\in[x^{k},x^{k}+\gamma^{-1}t_{k}d^{k}]$ such that

$\displaystyle
f(x^{k}+\gamma^{-1}t_{k}d^{k})-f(x^{k})=\gamma^{-1}t_{k}\left\langle
d^{k},\nabla f(\widetilde{x}^{k})\right\rangle.$

Combining the latter with (5.5) tells us that

$\displaystyle\left\langle-d^{k},\nabla
f(\widetilde{x}^{k})\right\rangle\leq\beta\left\|d^{k}\right\|^{2}\;\text{ for
all }\;k\geq N.$ (5.6)

Using (5.3) and (5.4), we have
$\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|<\infty$, and thus
$\left\\{x^{k}\right\\}$ converges to some $\bar{x}\in{\rm I\\!R}^{n}$. The
continuity of $\nabla f$ ensures that $\nabla f(x^{k})\rightarrow\nabla
f(\bar{x})$. Then employing $\left\|g^{k}-\nabla
f(x^{k})\right\|\leq\rho_{k}\rightarrow 0$ yields $g^{k}\rightarrow\nabla
f(\bar{x})$ as $k\rightarrow\infty$. It follows from Step 2 that

$\displaystyle-d^{k}$
$\displaystyle=\dfrac{\left\|g^{k}\right\|-\varepsilon_{k}}{\left\|g^{k}\right\|}g^{k}=\dfrac{\left\|g^{k}\right\|-\varepsilon_{N}}{\left\|g^{k}\right\|}g^{k}\;\text{
for all \;}k\geq N.$

Letting $k\rightarrow\infty$ leads us to the equalities

$\displaystyle-d^{k}\rightarrow\bar{g}:=\dfrac{\left\|\nabla
f(\bar{x})\right\|-\varepsilon_{N}}{\left\|\nabla f(\bar{x})\right\|}\nabla
f(\bar{x})={\rm Proj}\big{(}0,\mathbb{B}(\nabla
f(\bar{x}),\varepsilon_{N})\big{)}.$ (5.7)

Using $t_{k}\downarrow 0$, we get that $\widetilde{x}^{k}\rightarrow\bar{x}$,
and thus $\nabla f(\widetilde{x}^{k})\rightarrow\nabla f(\bar{x})$ as
$k\to\infty$. Combining the latter with (5.6), (5.7), and the projection
characterization in (4.4) verifies the estimates

$\displaystyle\left\|\bar{g}\right\|^{2}\leq\left\langle\bar{g},\nabla
f(\bar{x})\right\rangle\leq\beta\left\|\bar{g}\right\|^{2}.$ (5.8)

This tells us that $\bar{g}=0$, which contradicts the condition
$\left\|\bar{g}\right\|\geq r_{N}$ by (5.4). Therefore, we arrive at
$\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow 0$ as $k\to\infty$, which
completes the proof of assertion (i).

To justify assertions (ii)–(iv), recall from Corollary 4.8 that
$\left\\{d^{k}\right\\}$ is gradient associated with $\left\\{x^{k}\right\\}$.
Since $\varepsilon_{k}\downarrow 0$, we deduce from Proposition 4.7 that $0$
is an accumulation point of $\left\\{d^{k}\right\\}$. Combining these facts
with (5.3) and $t_{k}\leq 1$ whenever $k\in{\rm I\\!N}$ ensures that all the
assumptions of Theorem 3.4 are satisfied. Therefore, we verify assertions
(ii)–(iv) and finish the proof of the theorem.

Next we consider problem (1.1) with the objective function $f$ satisfying the
$L$-descent condition for some $L>0$. The following result establishes
convergence properties of IRG method, which use either diminishing or constant
stepsizes.

######  Theorem 5.3.

Let $\left\\{x^{k}\right\\}$ be the sequence generated by Algorithm 1, where

  * (a)

$f$ satisfies the $L$-descent condition;

  * (b)

either $\left\\{t_{k}\right\\}$ is diminishing, i.e.,

$\displaystyle t_{k}\downarrow 0\;\mbox{ as }\;k\to\infty\;\text{ and
}\quad\sum_{k=1}^{\infty}t_{k}=\infty,$ (5.9)

or there exist $\delta,\delta^{\prime}>0$ such that
$\delta^{\prime}\leq\dfrac{2-\delta}{L}$ and

$\displaystyle
t_{k}\in\left[\delta^{\prime},\dfrac{2-\delta}{L}\right]\;\text{ for all
}\;k\in{\rm I\\!N}.$ (5.10)

Assume that $\rho_{k}=\varepsilon_{k}$ for all $k\in{\rm I\\!N}$ and that
$\inf f(x^{k})>-\infty$. Then all the conclusions of Theorem 5.2 hold.
Moreover, if $\left\\{t_{k}\right\\}$ is chosen as (5.10), then $\nabla
f(x^{k})\rightarrow 0$ as $k\to\infty$.

[Proof.] We know from Remark 4.8 that the direction sequence
$\left\\{d^{k}\right\\}$ is gradient associated with $\left\\{x^{k}\right\\}$.
Furthermore, Proposition 4.4 tells us that $\left\\{d^{k}\right\\}$ satisfies
the sufficient descent condition (3.7) with the constant $\kappa=1$. Note that
if $\left\\{t_{k}\right\\}$ is chosen as either (5.9) or (5.10), then we
always get that

$\displaystyle\displaystyle{\sum_{k=1}^{\infty}}t_{k}=\infty\quad\text{and}\quad
t_{k}\leq\dfrac{2-\delta}{L}\;\text{ for sufficiently large }\;k\in{\rm
I\\!N}.$

Combining these facts with the imposed $L$-descent condition on $f$ yields the
fulfillment of assumptions (a), (b), (c) in Corollary 3.5. Therefore,
conclusions (ii)–(iv) of Theorem 5.2 hold. The proof of Corollary 3.5 also
ensures that $0$ is an accumulation point of $\left\\{d^{k}\right\\}$. Thus it
follows from Proposition 4.7 that $\varepsilon_{k}\downarrow 0$. Using
Proposition 4.6(ii), we have $r_{k}\downarrow 0$, which verifies conclusion
(i) of Theorem 5.2. If $\left\\{t_{k}\right\\}$ is chosen as (5.10), its
boundedness away from $0$ is guaranteed, and so Corollary 3.5 yields $\nabla
f(x^{k})\rightarrow 0$ as $k\to\infty$ and thus completes the proof of the
theorem.

The final part of our convergence analysis of the proposed IRG methods applies
the KL property to establishing the global convergence of the entire sequence
of iterations to a stationary point with deriving convergence rates. We start
with the following simple albeit useful lemma.

######  Lemma 5.4.

Let $\left\\{x^{k}\right\\}$ be the sequence generated by Algorithm 1 with
$\theta<\mu$. Assume that $\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow
0$ as $k\to\infty$. Then there exists some $N\in{\rm I\\!N}$ such that

$\displaystyle\left\|\nabla f(x^{k})\right\|\leq 3\left\|d^{k}\right\|\;\text{
for all }\;k\notin\mathcal{N},\;k\geq N,$ (5.11)

where the set $\mathcal{N}$ is taken from Definition 4.5.

[Proof.] It follows directly from the assumptions of the lemma that there
exists a natural number $N$ such that $\varepsilon_{k}\leq r_{k}$ for all
$k\geq N$. By Step 2 of the algorithm, for any $k\geq N$ with
$k\notin\mathcal{N}$ we have $\left\|g^{k}\right\|>r_{k}+\varepsilon_{k}$ with
the direction $d^{k}$ calculated in (4.11). Thus for such $k$ we get the
estimates

$\displaystyle\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}>r_{k}+\varepsilon_{k}-\varepsilon_{k}=r_{k}\geq\varepsilon_{k}.$
(5.12)

It follows from (4.10) in Step 1 and from (5.12) that

$\displaystyle\left\|\nabla
f(x^{k})\right\|\leq\left\|g^{k}\right\|+\varepsilon_{k}=\left\|d^{k}\right\|+2\varepsilon_{k}\leq
3\left\|d^{k}\right\|,$

which verifies the conclusion of the lemma.

The following two theorems provide conditions ensuring the global convergence
of iterative sequences generated by Algorithm 1 with different stepsize
selections to a stationary point of $f$. The first theorem concerns the IRG
methods with the backtracking stepsize.

######  Theorem 5.5.

Let $\left\\{x^{k}\right\\}$ be the iterative sequence generated by Algorithm
1 with the backtracking linesearch such that $\theta<\mu$. Assume that
$\rho_{k}\rightarrow 0$ as $k\rightarrow\infty$, $\left\\{x^{k}\right\\}$ has
an accumulation point $\bar{x}$, and $f$ satisfies the KL property at
$\bar{x}$. Then $\bar{x}$ is a stationary point of $f$, and we have
$x^{k}\rightarrow\bar{x}$ as $k\to\infty$.

[Proof.] Since $\bar{x}$ is an accumulation point of $\left\\{x^{k}\right\\}$,
we can find some infinite set $J\subset{\rm I\\!N}$ such that
$x^{k}\overset{J}{\rightarrow}\bar{x}$. It follows from the choice of
$\left\\{t_{k}\right\\}$ in (5.1) that $\left\\{f(x^{k})\right\\}$ is
nonincreasing, which implies that

$\displaystyle\inf_{k\in{\rm I\\!N}}f(x^{k})=\inf_{k\in
J}f(x^{k})=f(\bar{x})>-\infty.$

Therefore, the results of Theorem 5.2 tell us that $\bar{x}$ is a stationary
point of $f$ and that $\varepsilon_{k}\downarrow 0$, $r_{k}\downarrow 0$ as
$k\to\infty$. We employ Proposition 3.9 to verify that
$x^{k}\rightarrow\bar{x}$ along the entire sequence of iterations. Indeed, the
imposed assumptions and the convergence $\varepsilon_{k}\downarrow 0$,
$r_{k}\downarrow 0$ as $k\to\infty$ guarantee that all the requirements of
Lemma 5.4 are satisfied. Pick $N\in{\rm I\\!N}$ such that (5.11) holds. The
choice of $\left\\{t_{k}\right\\}$ in (5.1) ensures the lower estimate

$\displaystyle f(x^{k})-f(x^{k+1})$ $\displaystyle\geq\beta
t_{k}\big{\|}d^{k}\big{\|}^{2}\;\text{ for all }\;k\in{\rm I\\!N}.$ (5.13)

Combining this with (5.11) and the relation $x^{k+1}=x^{k}+t_{k}d^{k}$ yields

$\displaystyle f(x^{k})-f(x^{k+1})\geq\dfrac{\beta}{3}\left\|\nabla
f(x^{k})\right\|\cdot\left\|x^{k+1}-x^{k}\right\|\;\text{ for all
}\;k\notin\mathcal{N},\;k\geq N.$ (5.14)

Observe that when $k\in\mathcal{N}$, both sides of (5.14) reduce to zero, and
so (5.14) is satisfied. Therefore, assumption (H1) in Proposition 3.9 holds.
Moreover, for $k\geq N$ the conditions $f(x^{k+1})=f(x^{k})$ and (5.13) imply
that $d^{k}=0$, and hence $x^{k+1}=x^{k}$. Thus assumption (H2) in Proposition
3.9 is satisfied as well. Applying the latter proposition, we arrive at
$x^{k}\rightarrow\bar{x}$ as $k\to\infty$ and complete the proof.

The second theorem of the above type addresses the IRG methods with
diminishing and constant selections of the stepsize sequence
$\left\\{t_{k}\right\\}$.

######  Theorem 5.6.

Let the objective function $f$ satisfy the $L$-descent condition (2.1) for
some $L>0$, and let $\left\\{x^{k}\right\\}$ be the sequence generated by
Algorithm 1 with $\theta<\mu$, $\rho_{k}=\varepsilon_{k}$ for all $k\in{\rm
I\\!N}$, and either diminishing (5.9) or constant stepsizes (5.10). Assume in
addition that $\bar{x}$ is an accumulation point of the sequence
$\left\\{x^{k}\right\\}$ and that $f$ satisfies the KL property at $\bar{x}$.
Then $\bar{x}$ is a stationary point of $f$, and we have the convergence
$x^{k}\rightarrow\bar{x}$ as $k\to\infty$.

[Proof.] Observe first that the assumptions imposed here yield those in
Theorem 5.3 and Corollary 3.5 but $\inf f(x^{k})>-\infty$. Similarly to the
proof of Corollary 3.5, we can show that $\left\\{f(x^{k})\right\\}_{k\geq K}$
is nonincreasing for some $K\in{\rm I\\!N}.$ Since $\bar{x}$ is an
accumulation point of $\left\\{x^{k}\right\\}$, similarly to the proof of
Theorem 5.5, we deduce that $\inf f(x^{k})=f(\bar{x})>-\infty$, which verifies
the remaining assumption. Therefore, $\bar{x}$ is a stationary point of $f$
and $\varepsilon_{k}\downarrow 0$, $r_{k}\downarrow 0$ as $k\to\infty$. The
latter convergence together with the imposed assumptions guarantee the
fulfillment of all the conditions of Lemma 5.4. Let $N\in{\rm I\\!N}$ be such
that (5.11) holds. Let $\delta>0$ be the constant given in (5.10). From the
proof of Corollary 3.5, we find some $N_{1}\geq N$ such that

$\displaystyle f(x^{k})-f(x^{k+1})$
$\displaystyle\geq\dfrac{\delta}{2}t_{k}\left\|d^{k}\right\|^{2}\;\text{ for
all }\;k\geq N_{1}.$ (5.15)

The relation $x^{k+1}=x^{k}+t_{k}d^{k}$ and (5.11), (5.15) tell us that

$\displaystyle f(x^{k})-f(x^{k+1})$
$\displaystyle\geq\dfrac{\delta}{6}\left\|\nabla
f(x^{k})\right\|\left\|x^{k+1}-x^{k}\right\|\;\text{ whenever
}\;k\notin\mathcal{N},\;k\geq N_{1}.$ (5.16)

Similarly to the proof of Theorem 5.5, we get $x^{k}\rightarrow\bar{x}$ as
$k\to\infty$ and thus complete the proof.

We’ll see below that the boundedness of stepsizes away from $0$ plays a
crucial role in establishing the rate of convergence of the IRG methods. This
property automatically holds for constant stepsizes while may fail for
diminishing ones. The next proposition shows that the boundedness from below
is satisfied for the backtracking stepsize selection provided that the
gradient of the objective function is locally Lipschitzian around accumulation
points of iterative sequence. Observe that this property is strictly weaker
than the (global) Lipschitz continuous of $\nabla f$. Indeed,
$\mathcal{C}^{2}$-smooth functions have locally Lipschitzian gradients but do
not need to have a globally Lipschitzian one as, e.g., for $f(x):=x^{4}$.

######  Proposition 5.7.

Let $\left\\{x^{k}\right\\}$ be a sequence generated by Algorithm 1 with the
backtracking stepsize. Suppose that $\rho_{k}\rightarrow 0$ as
$k\rightarrow\infty$ and that there exists an infinite set $J\subset{\rm
I\\!N}$ such that $\left\\{x^{k}\right\\}_{k\in J}$ converges to some
$\bar{x}$. Assume further that $\nabla f$ is locally Lipschitzian around
$\bar{x}$. Then the stepsize sequence $\left\\{t_{k}\right\\}_{k\in J}$ is
bounded away from zero.

[Proof.] Assume on the contrary that $\left\\{t_{k}\right\\}_{k\in J}$ is not
bounded away from zero. Then we find an infinite set $\bar{J}\subset J$ such
that $t_{k}\overset{\bar{J}}{\longrightarrow}0$. Let $\tau\in(0,1)$ be an
artificial stepsize of null iterations. Since
$t_{k}\overset{\bar{J}}{\longrightarrow}0$, there exists a number $N\in{\rm
I\\!N}$ such that

$\displaystyle t_{k}<\tau<1\;\text{ for all }\;k\geq N,\;k\in\bar{J}.$ (5.17)

This means that $k\notin\mathcal{N}$ whenever $k\geq N,\;k\in\bar{J}$. By
Proposition 4.6(i), we have $d^{k}\neq 0$ for all $k\geq N,\;k\in\bar{J}$.
Then condition (4.11) in Step 2 leads us to

$\displaystyle\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}\leq\left\|g^{k}\right\|\;\mbox{
for all }\;k\geq N,\;k\in\bar{J}.$ (5.18)

Since $x^{k}\overset{\bar{J}}{\rightarrow}\bar{x}$, the continuity of $\nabla
f$ and the estimate $\left\|\nabla
f(x^{k})-g^{k}\right\|\leq\rho_{k}\rightarrow 0$ yield that
$g^{k}\overset{\bar{J}}{\rightarrow}\nabla f(\bar{x})$. Using (5.18), we get
that the sequence $\left\\{d^{k}\right\\}_{k\in\bar{J}}$ is bounded, and thus

$\displaystyle x^{k}+\gamma^{-1}t_{k}d^{k}\rightarrow\bar{x}\;\mbox{ as
}\;k\overset{\bar{J}}{\rightarrow}\infty.$ (5.19)

Since $\nabla f$ is locally Lipschitzian around $\bar{x}$, there exists a
positive number $\delta$ such that $\nabla f$ is Lipschitz continuous on
$\mathbb{B}(\bar{x},\delta)$ with some modulus $L>0$. By (5.19) and
$x^{k}\overset{\bar{J}}{\rightarrow}\bar{x}$, we find $N_{1}\geq N$ with
$x^{k},x^{k}+\gamma^{-1}t_{k}d^{k}\in\mathbb{B}(\bar{x},\delta)$ for all
$k\geq N_{1},\;k\in\bar{J}$. The Lipschitz continuity of $\nabla f$ on
$\mathbb{B}(\bar{x},\delta)$ with modulus $L$ yields by [10, Proposition A.24]
the $L$-descent condition, i.e.,

$\displaystyle f(x)-f(y)\leq\left\langle\nabla
f(y),x-y\right\rangle+\dfrac{L}{2}\left\|x-y\right\|^{2}\;\text{ for all
}\;x,y\in\mathbb{B}(\bar{x},\delta).$ (5.20)

Fixing $k\in\bar{J},\;k\geq N_{1}$, we deduce from the above that $d^{k}\neq
0$, and $t_{k}<1$. The exit condition for the backtracking line search implies
that

$\displaystyle-\gamma^{-1}\beta
t_{k}\left\|d^{k}\right\|^{2}<f(x^{k}+\gamma^{-1}t_{k}d^{k})-f(x^{k}).$ (5.21)

Applying (5.20) for $x=x^{k}+\gamma^{-1}t_{k}d^{k}$ and $y=x^{k}$ we have that

$\displaystyle
f(x^{k}+\gamma^{-1}t_{k}d^{k})-f(x^{k})\leq\gamma^{-1}t_{k}\left\langle\nabla
f(x^{k}),d^{k}\right\rangle+\dfrac{L\gamma^{-2}t_{k}^{2}}{2}\left\|d^{k}\right\|^{2}.$

Combining this with (5.21) leads us to

$\displaystyle-\gamma^{-1}\beta
t_{k}\left\|d^{k}\right\|^{2}<\gamma^{-1}t_{k}\left\langle\nabla
f(x^{k}),d^{k}\right\rangle+\dfrac{L\gamma^{-2}t_{k}^{2}}{2}\left\|d^{k}\right\|^{2},$

or equivalently to the inequality

$\displaystyle 0<\gamma^{-1}\beta
t_{k}\left\|d^{k}\right\|^{2}+\gamma^{-1}t_{k}\left\langle\nabla
f(x^{k}),d^{k}\right\rangle+\dfrac{L\gamma^{-2}t_{k}^{2}}{2}\left\|d^{k}\right\|^{2}.$
(5.22)

Proposition 4.4 and $d^{k}\neq 0$ tell us that
$0<\left\|d^{k}\right\|^{2}\leq\left\langle\nabla
f(x^{k}),-d^{k}\right\rangle$. Then we deduce from (5.22) the fulfillment of
the estimate

$\displaystyle 0<\gamma^{-1}\beta t_{k}\left\langle\nabla
f(x^{k}),-d^{k}\right\rangle+\gamma^{-1}t_{k}\left\langle\nabla
f(x^{k}),d^{k}\right\rangle+\dfrac{L\gamma^{-2}t_{k}^{2}}{2}\left\langle\nabla
f(x^{k}),-d^{k}\right\rangle.$

Dividing both sides above by $\gamma^{-1}t_{k}\left\langle\nabla
f(x^{k}),-d^{k}\right\rangle>0$, we get
$0<\beta-1+\dfrac{L\gamma^{-1}t_{k}}{2}$. Letting
$k\overset{\bar{J}}{\longrightarrow}\infty$ yields $\beta\geq 1$, which
contradicts the choice of $\beta\in(0,1)$. Thus we verify that the sequence
$\left\\{t_{k}\right\\}_{k\in J}$ is bounded away from zero, which completes
the proof of the proposition.

The last two theorems establish efficient conditions ensuring the convergence
rates in Algorithm 1 under different stepsize selections. Having the sequence
of iterations $\left\\{x^{k}\right\\}$ generated by this algorithm, we obtain
first from Proposition 4.6(iii) that if ${\rm I\\!N}\setminus\mathcal{N}$ is
finite, then $\left\\{x^{k}\right\\}$ stops after a finite number of
iterations. Thus we consider the case where the set ${\rm
I\\!N}\setminus\mathcal{N}$ is infinite and can be numerated as
$\left\\{j_{1},j_{2},\ldots\right\\}$. Construct the sequence
$\left\\{z^{k}\right\\}$ by

$\displaystyle z^{k}:=x^{j_{k}}\;\text{ for all }\;k\in{\rm I\\!N}.$ (5.23)

We have $j_{k+1}\geq j_{k}+1$ whenever $k\in{\rm I\\!N}$. If the equality
holds therein, then $z^{k+1}=z^{j_{k}+1}$. Otherwise, by taking into account
that the indices $j_{k}+1,\ldots,j_{k+1}-1$ correspond to null iterations, we
get that

$\displaystyle
x^{j_{k}+1}=x^{j_{k}+2}=\ldots=x^{j_{k+1}-1}=x^{j_{k+1}}=z^{k+1}.$ (5.24)

Therefore, it follows from $j_{k}\notin\mathcal{N}$ that

$\displaystyle z^{k+1}=x^{j_{k}+1}\neq x^{j_{k}}=z^{k}\;\text{ for all
}\;k\in{\rm I\\!N}.$ (5.25)

Furthermore, Proposition 4.6(iv) tells us that $\bar{x}$ is an accumulation
point of $\left\\{z^{k}\right\\}$ if and only if $\bar{x}$ is also an
accumulation point of $\left\\{x^{k}\right\\}$.

The first theorem about the convergence rates concerns Algorithm 1 with the
backtracking stepsize.

######  Theorem 5.8.

Consider Algorithm 1 with the backtracking stepsize selections under the
condition $\theta<\mu$. Let $\left\\{x^{k}\right\\}$ be the iterative sequence
generated by this algorithm. Suppose that $\rho_{k}\rightarrow 0$ as
$k\rightarrow\infty$. Assume further that $\left\\{x^{k}\right\\}$ has an
accumulation point $\bar{x}$, that $f$ satisfies the KL property at $\bar{x}$
with $\psi(t)=Mt^{q}$ for some $M>0$ and $q\in(0,1)$, and that $\nabla f$ is
locally Lipschitzian around $\bar{x}$. The following convergence rates are
guaranteed for the sequence $\left\\{z^{k}\right\\}$ defined in (5.23):

  * (i)

If $q\in(0,1/2]$, then the sequence $\left\\{z^{k}\right\\}$ converges
linearly to $\bar{x}$.

  * (ii)

If $q\in(1/2,1)$, then there exists a positive constant $\varrho$ such that

$\displaystyle\left\|z^{k}-\bar{x}\right\|\leq\varrho
k^{-\frac{1-q}{2q-1}}\;\text{ for all large }\;k\in{\rm I\\!N}.$

[Proof.] The imposed assumptions yield the fulfillment of those in Theorem
5.5, and so lead us to the convergence $x^{k}\rightarrow\bar{x}$ as
$k\to\infty$. Then the local Lipschitz continuity of $\nabla f$ around
$\bar{x}$ and Proposition 5.7 ensure that the sequence
$\left\\{t_{k}\right\\}$ is bounded away from zero.

To deduce now the claimed convergence rates in (i)–(iii) from Theorem 3.11,
define $\tau_{k}:=t_{j_{k}}$ for all $k\in{\rm I\\!N}$. Then
$\left\\{\tau_{k}\right\\}$ is also bounded away from zero as a subsequence of
$\left\\{t_{k}\right\\}$. Furthermore, using (5.24) and the line search
conditions, we have

$\displaystyle f(z^{k})-f(z^{k+1})$
$\displaystyle=f(x^{j_{k}})-f(x^{j_{k}+1})\geq\beta
t_{j_{k}}\left\|d^{j_{k}}\right\|^{2}$
$\displaystyle=\dfrac{\beta}{t_{j_{k}}}\left\|x^{j_{k}+1}-x^{j_{k}}\right\|^{2}=\dfrac{\beta}{\tau_{k}}\left\|z^{k+1}-z^{k}\right\|^{2}$
(5.26)

for all $k\in{\rm I\\!N}$. Note that all the assumptions of Theorem 5.2 are
satisfied, and so Lemma 5.4 holds. Pick any $N\in{\rm I\\!N}$ from (5.11) and
fix $k\geq N$. Then using (5.24) and (5.11) with taking into account that
$j_{k}\notin\mathcal{N}$ for $j_{k}\geq k$ leads us to

$\displaystyle\left\|\nabla f(z^{k})\right\|=\left\|\nabla
f(x^{j_{k}})\right\|$
$\displaystyle\leq\dfrac{3}{t_{j_{k}}}\left\|x^{j_{k}+1}-x^{j_{k}}\right\|=\dfrac{3}{\tau_{k}}\left\|z^{k+1}-z^{k}\right\|.$

Apply finally Theorem 3.11 to $\left\\{z^{k}\right\\}$ and
$\left\\{\tau_{k}\right\\}$ while remembering that $z^{k+1}\neq z^{k}$ for all
$k\in{\rm I\\!N}$ from (5.25). This verifies the convergence rates (i)–(iii)
claimed in the theorem.

The next theorem on the convergence rates addresses Algorithm 1 with the
constant stepsizes.

######  Theorem 5.9.

Let $f$ satisfy the $L$-descent condition for some $L>0$, and let
$\left\\{x^{k}\right\\}$ be the iterative sequence generated by Algorithm 1
with the constant stepsizes (5.10) under the condition $\theta<\mu$ and the
selection $\rho_{k}=\varepsilon_{k}$ for all $k\in{\rm I\\!N}$. Suppose that
$\left\\{x^{k}\right\\}$ has an accumulation point $\bar{x}$ and that $f$
satisfies the KL property at $\bar{x}$ with $\psi(t)=Mt^{q}$ for some $M>0$
and $q\in(0,1)$. Then the following convergence rates are guaranteed for the
iterative sequence $\left\\{z^{k}\right\\}$ defined in (5.23):

  * (i)

If $q\in(0,1/2]$, then the sequence $\left\\{z^{k}\right\\}$ converges
linearly to $\bar{x}$.

  * (ii)

If $q\in(1/2,1)$, then there exists a positive constant $\varrho$ such that

$\displaystyle\left\|z^{k}-\bar{x}\right\|\leq\varrho
k^{-\frac{1-q}{2q-1}}\;\text{ for all large }\;k\in{\rm I\\!N}.$

[Proof.] Note that our assumptions yield the fulfillment of those in Theorem
5.6, and thus we have that $x^{k}\rightarrow\bar{x}$ as $k\to\infty$. Defining
$\tau_{k}:=t_{j_{k}}$ for all $k\in{\rm I\\!N}$ ensures that the stepsize
sequence $\left\\{\tau_{k}\right\\}$ is bounded away from zero. Note that all
the assumptions in Corollary 3.5 hold, and let $\delta>0$ be the constant
taken from in (5.10). By the $L$-descent property of $f$ and the constant
stepsize selection, we find by arguing similarly to the proof of Corollary 3.5
a number $N\in{\rm I\\!N}$ such that

$\displaystyle f(x^{k})-f(x^{k+1})$
$\displaystyle\geq\dfrac{\delta}{2}t_{k}\left\|d^{k}\right\|^{2}\;\text{
whenever }\;k\geq N.$ (5.27)

Since $j_{k}\geq k\geq N$ for such $k$, it follows that

$\displaystyle f(z^{k})-f(z^{k+1})$
$\displaystyle=f(x^{j_{k}})-f(x^{j_{k}+1})\geq\dfrac{\delta}{2}t_{j_{k}}\left\|d^{j_{k}}\right\|^{2}$
$\displaystyle=\dfrac{\delta}{2t_{j_{k}}}\left\|x^{j_{k}+1}-x^{j_{k}}\right\|^{2}=\dfrac{\delta}{2\tau_{k}}\left\|z^{k+1}-z^{k}\right\|^{2}.$

Note that all the assumptions of Theorem 5.3 are satisfied. Using this result
together with Lemma 5.4 and then arguing as in the proof of Theorem 5.8, we
complete the proof of this theorem.

##  6 Applications and Numerical Experiments

In this section, we present efficient implementations of the developed IRG
methods to solving particular classes of optimization problems that appear in
practical modeling. We conduct numerical experiments and compare the results
of computations by using our algorithms with those obtained by applying some
other well-known methods. This section is split into two subsections
addressing different classes of problems with the usage of different
algorithms.

###  6.1 Comparison with classical inexact proximal point method

This subsection addresses the Least Absolute Deviations $($LAD$)$ Curve-
Fitting problem which is formulated as follows:

$\mbox{minimize }\;g(x):=\left\|Ax-b\right\|_{1}\;\mbox{ over }\;x\in{\rm
I\\!R}^{n},$ (6.1)

where $A$ is an $m\times n$ matrix, $b$ is a vector in ${\rm I\\!R}^{m}$, and
$\left\|u\right\|_{1}:=\sum_{k=1}^{m}|u_{k}|$ for any
$u=(u_{1},\ldots,u_{m})\in{\rm I\\!R}^{m}$. Problem (6.1) exhibits robustness
in outliers resistance and appears in many applied areas; see, e.g., [11] for
more discussions. Observe that (6.1) is a problem of nonsmooth convex
optimization, but we can reduce it to a smooth problem by using a
regularization procedure. In this way, we solve (6.1) by using our IRG method
with constant stepsize and compare our approach with the usage of the inexact
proximal point method (IPPM) proposed by Rockafellar in [48].

To proceed, recall that the Moreau envelope and the proximal mapping of $g$
are defined by

$e_{g}(x):=\inf_{y\in{\rm I\\!R}^{n}}\varphi_{x}(y)\;\mbox{ and }\;\mbox{\rm
Prox}_{g}(x):=\mathop{\rm argmin}_{y\in{\rm I\\!R}^{n}}\varphi_{x}(y),\quad
x\in{\rm I\\!R}^{n},$ (6.2)

where the minimization mapping $\varphi_{x}:{\rm I\\!R}^{n}\rightarrow{\rm
I\\!R}$ is given by

$\displaystyle\varphi_{x}(y):=g(y)+\dfrac{1}{2}\left\|y-x\right\|^{2},\quad
y\in{\rm I\\!R}^{n}.$ (6.3)

Since $g$ is convex, it follows from [7, Propositions 12.28 and 12.30] that
$e_{g}$ is $\mathcal{C}^{1}$-smooth and that its gradient is Lipschitz
continuous with constant $1$ being represented by

$\nabla e_{g}(x)=x-\text{\rm Prox}_{g}(x)\;\mbox{ for all }\;x\in{\rm
I\\!R}^{n}.$ (6.4)

Moreover, the set of minimizers of $g$ coincides with the set of zeros of the
gradient mapping $\nabla e_{g}$.

This tells us that problem (6.1) can be equivalently transformed into the
problem of finding stationary points of the smooth function $f:=e_{g}$.
Therefore, it is possible to solve (6.1) by using Algorithm 1 with constant
stepsize, where an inexact gradient $g^{k}$ of $\nabla f(x^{k})$ in Step 1
satisfying the simplified condition (4.12) can be chosen from the conditions

$\displaystyle g^{k}:=x^{k}-p^{k}\;\text{ with }\left\|p^{k}-\mbox{\rm
Prox}_{g}(x^{k})\right\|\leq\varepsilon_{k}.$ (6.5)

Meanwhile, the iterative procedure of IPPM in [48, page 878] for solving (6.1)
is given by

$\displaystyle x^{k+1}=p^{k}\text{ with }\left\|p^{k}-\mbox{\rm
Prox}_{g}(x^{k})\right\|\leq\delta_{k},\text{ where
}\sum_{k=1}^{\infty}\delta_{k}<\infty.$ (6.6)

Since the function $\varphi_{x^{k}}$ in (6.3) is strongly convex with constant
$1$ [42, Definition 2.1.3], the error bound for the distance between the
inexact proximal point $p^{k}$ and the exact one $\mbox{\rm Prox}_{g}(x^{k})$
in (6.5) and (6.6) is satisfied if

$\displaystyle\varphi_{x^{k}}(p^{k})\leq\inf\varphi_{x^{k}}+\omega_{k},$ (6.7)

where $\omega_{k}:=\dfrac{\varepsilon_{k}^{2}}{2}$ for (6.5) and
$\omega_{k}:=\dfrac{\delta_{k}^{2}}{2}$ for (6.6) by using [42, Theorem
2.1.8]. In this numerical experiment, we run the Fast Iterative Shrinkage-
Thresholding Algorithm (FISTA) of Beck and Teboulle [9] for the dual function
of $\varphi_{x^{k}}$ until the duality gap is below $\omega_{k}$, which
therefore ensures (6.7).

The initial points are chosen as $x^{1}:=0_{{\rm I\\!R}^{n}}$ for both
algorithms, while the detailed settings of each algorithm are given as
follows:

  * •

IRG: $\varepsilon_{1}=10,\theta=\mu=0.5$. Two selections of the initial radius
$r_{1}$ are $20$ and $5$, which correspond to versions IRG-20 and IRG-5,
respectively. To simplify the iterative sequence of Algorithm 1 when
$\left\|g^{k}\right\|\leq r_{k}+\varepsilon_{k}$, we put $x^{k+1}:=p^{k}$,
which corresponds to the choice of stepsize
$t_{k}=\frac{\left\|g^{k}\right\|}{\left\|g^{k}\right\|-\varepsilon_{k}}$.

  * •

IPPM: $\omega_{k}=\dfrac{1}{k^{p}}$ for all $k\in{\rm I\\!N}$, where $p=4$ or
$p=2.1.$ These selections together with the definition of $\omega_{k}$ in
(6.7) ensure that $\sum_{k=1}^{\infty}\delta_{k}<\infty$ as required for IPPM
in (6.6). We also use the labels IPPM-4 and IPPM-2.1 for these versions of
IPPM, respectively.

In this numerical experiment, we let IPPM-2.1 run for 200 iterations and
record the function value obtained by this method. Then other methods run
until their function values are lower than the recorded one of IPPM-2.1. We
stop the methods when the time reaches the limit of $4000$ seconds. The data
$A,b$ are generated randomly with i.i.d. (identically and independent
distributed) standard Gaussian entries. To avoid algorithms from reaching the
solution promptly, we consider only the cases where $m\leq n$ in (6.1).

The numerical experiment is conducted on a computer with 10th Gen Intel(R)
Core(TM) i5-10400 (6-Core 12M Cache, 2.9GHz to 4.3GHz) and 16GB RAM memory.
The codes are written in MATLAB R2021a. The detail information for the results
are presented in Table 2, where ’Test #’, ’iter’, ’fval’, ’time’ mean Test
number, the number of iterations, value of the objective function at the last
iteration and the computational time, respectively. The errors $\omega_{k}$ in
the inexact proximal point calculations (6.7) and the function values obtained
by the algorithms over the duration of time are also graphically illustrated
in Figure 4 and Figure 5.

Test # | m | n | IPPM-2.1 | IPPM-4 | IRG-5 | IRG-20
---|---|---|---|---|---|---
iter | fval | time | iter | fval | time | iter | fval | time | iter | fval | time
1 | 300 | 300 | 200 | 3.44 | 11.79 | 200 | 3.44 | 100.63 | 209 | 3.44 | 5.51 | 210 | 3.43 | 7.91
2 | 300 | 600 | 200 | 0.00 | 1.56 | 17 | 0.00 | 0.38 | 16 | 0.00 | 0.33 | 19 | 0.00 | 0.44
3 | 600 | 600 | 200 | 0.44 | 140.35 | 201 | 0.44 | 863.39 | 210 | 0.44 | 78.09 | 211 | 0.44 | 119.78
4 | 600 | 1200 | 200 | 0.00 | 5.26 | 16 | 0.00 | 1.72 | 17 | 0.00 | 1.42 | 20 | 0.00 | 1.77
5 | 1200 | 1200 | 67 | 8.00 | 4000 | 14 | 14.76 | 4000 | 75 | 7.98 | 949.46 | 75 | 8.00 | 1672.52
Table 2: Results for LAD Curve-Fitting problem

Figure 4: Errors in proximal points calculation in iterations

Figure 5: Value of the objective function with respect to the computational
time

It can be seen from Table 2 that IRG-5 has the best performance in this
numerical experiment. IRG-20 is the second fastest algorithm in Tests 1, 3, 5
while it is slightly slower than IPPM-4 in Tests 2, 4. In Test 5 with the
largest dimensions $m=n=1200,$ IRG-5 is around 4 times faster than IPPM-2.1
while IPPM-4 even cannot reach the value obtained by IPPM-2.1 within the time
limit. In this test, IRG-20 is also around 2.5 times faster than IPPM-2.1.

The graphs in Figure 4 and Figure 5 show that the errors (in inexact proximal
point calculations) of IRG are automatically adjusted to be suitable for
different problems:

  * •

In Tests 1, 3, 5 with $m=n$, it can be seen from Figure 5 that IPPM-2.1 is
faster than IPPM-4, which means that the use of larger errors is preferred in
this case. Then Figure 4 shows that the errors used in IRG stagnate at most of
the iterations. As a result, the IRG methods use the errors larger than that
of the IPPM methods and thus achieve better performances.

  * •

In Tests 2, 4 with $m<n$, IPPM-4 with smaller errors performs better than
IPPM-2.1. In this cases, the IRG methods decrease in almost every iteration
and achieve smaller errors in comparison with IPPM-4.

###  6.2 Comparison with the exact gradient descent methods

In the numerical experiments presented in this subsection, we show that our
IRG method with backtracking stepsize, based on the usage of inexact
gradients, performs well compared with the famous methods employing the exact
gradient calculation, which are the reduced gradient (RG) method method and
gradient descent (GD) method in the following setting:

  1. 1.

The accuracy of the inexact gradient $g^{k}$ is low, i.e.,
$\left\|g^{k}-\nabla f(x^{k})\right\|\leq\delta_{k}$, where $\delta_{k}$ is
not too small relative to $\left\|\nabla f(x^{k})\right\|$.

  2. 2.

The accuracy required for the solution is increasing.

To demonstrate this, we choose the following two well-known smooth benchmark
functions in global optimization taken from the survey paper [28].

  * •

The Dixon $\&$ Price function defined by

$\displaystyle f_{\rm
dixon}(\mathbf{x}):=\left(x_{1}-1\right)^{2}+\sum_{i=2}^{n}i\left(2x_{i}^{2}-x_{i-1}\right)^{2},\quad
x\in{\rm I\\!R}^{n}.$

The global minimum of this function is $\bar{f}_{\rm dixon}=0$, and the two
solutions $x^{*},y^{*}\in{\rm I\\!R}^{n}$ are

$\displaystyle\begin{cases}x^{*}_{1}=1,&\\\
x^{*}_{k}=\sqrt{\dfrac{x_{k-1}}{2}}&\text{ for }\;k=2,\ldots,n\end{cases}$

and by $y^{*}_{k}=x^{*}_{k}$ for all $k=1,\ldots,n-1,$ $y^{*}_{n}=-x^{*}_{n}$.

  * •

The Rosenbrock 1 function defined by

$\displaystyle f_{\rm
rosen}(\mathbf{x}):=\sum_{i=1}^{n-1}\left[100\left(x_{i+1}-x_{i}^{2}\right)^{2}+\left(x_{i}-1\right)^{2}\right],\quad
x\in{\rm I\\!R}^{n}.$

The global minimum of this function is $\bar{f}_{\rm rosen}=0$, and the unique
solution is $(1,\ldots,1)\in{\rm I\\!R}^{n}$.

Since the information about the convexity and the Lipschitz continuity of
gradients of the chosen objective functions is unknown, our experiments are
conducted by algorithms, where stepsizes are obtained from the corresponding
line searches. We use the following abbreviations:

  * •

GD: Gradient descent method with the backtracking linesearch.

  * •

RGB & IRGB: Reduced gradient method with the backtracking linesearch $\&$
Inexact reduced gradient method with the backtracking linesearch; see (5.1).

To generate the inexactness for testing purposes, given the gradient error
$\delta_{k}:=\min\left\\{\varepsilon_{k},\rho_{k}\right\\}$ as in (4.10), we
create an inexact gradient $g^{k}$ by adding a random vector with the norm
$0.5\delta_{k}$ to the exact gradient $\nabla f(x^{k})$. To ensure manually
controlled errors between the exact gradients and inexact ones that do not
decrease so fast, we choose $\rho_{k}:=1/\log(k+1)$. For all the methods in
our experiments, the linesearch parameters are chosen as $\beta=0.7$ and
$\gamma=0.5$. The initial radii $\varepsilon_{1}=r_{1}=5$ and the radius
reduction factors $\theta=0.7,\;\mu=0.7$ are also used for the RG and IRG
methods. To avoid the initial points from being identical with the solutions,
we choose $x^{1}:=0_{{\rm I\\!R}^{n}}$ on tests using the Rosenbrock 1
function. In the tests using the Dixon & Price functions, we choose
$x^{1}:=1_{{\rm I\\!R}^{n}}$ to avoid the algorithms from going to different
solutions. The condition

$\displaystyle\left\|\nabla f(x)\right\|\leq\nu,\;\text{ where either
}\;\nu=0.01\text{ or }\nu=0.001.$

is used as the stopping criterion for all the tests. The detailed information
of the numerical experiments and the achieved numerical results are presented
in Table 3. The problem names are given in the forms Dn and Rn, where D stands
for Dixon & Price, R stands for Rosenbrock 1, and $n$ is the dimension of the
tested problem. In these tables, “Iter”, “fval” stand for the number of
iterations and the function value at the last iteration.

Name | $\nu$ | GD | IRGB | RGB
---|---|---|---|---
Iter | fval | Iter | fval | $\varepsilon_{k}$ | $\delta_{k}$ | Iter | fval | $\varepsilon_{k}$
D200 | 0.01 | 1928 | 2.8E-05 | 1110 | 2.6E-05 | 4.0E-03 | 2.0E-03 | 998 | 2.76E-05 | 4.0E-03
D500 | 0.01 | 3831 | 2.8E-05 | 4782 | 2.7E-05 | 4.0E-03 | 2.0E-03 | 5012 | 2.43E-05 | 4.0E-03
D1000 | 0.01 | 7655 | 2.8E-05 | 9347 | 2.6E-05 | 4.0E-03 | 2.0E-03 | 9271 | 2.58E-05 | 4.0E-03
R200 | 0.01 | 20357 | 9.5E-05 | 24966 | 9.2E-05 | 4.0E-03 | 2.0E-03 | 25162 | 8.65E-05 | 4.0E-03
R500 | 0.01 | 46135 | 9.3E-05 | 59768 | 7.3E-05 | 4.0E-03 | 2.0E-03 | 59604 | 9.20E-05 | 4.0E-03
R1000 | 0.01 | 89130 | 9.4E-05 | 117754 | 8.8E-05 | 4.0E-03 | 2.0E-03 | 117845 | 9.09E-05 | 4.0E-03
D200 | 0.001 | 3294 | 2.7E-07 | 1870 | 2.7E-07 | 4.7E-04 | 2.3E-04 | 1704 | 2.8E-07 | 4.7E-04
D500 | 0.001 | 6543 | 2.8E-07 | 8151 | 2.4E-07 | 4.7E-04 | 2.3E-04 | 7933 | 2.2E-07 | 4.7E-04
D1000 | 0.001 | 13078 | 2.8E-07 | 15946 | 2.7E-07 | 4.7E-04 | 2.3E-04 | 15598 | 2.3E-07 | 4.7E-04
R200 | 0.001 | 22664 | 9.6E-07 | 26958 | 8.9E-07 | 4.7E-04 | 2.3E-04 | 27395 | 9.7E-07 | 4.7E-04
R500 | 0.001 | 48442 | 9.5E-07 | 61998 | 7.8E-07 | 4.7E-04 | 2.3E-04 | 61875 | 9.6E-07 | 4.7E-04
R1000 | 0.001 | 91431 | 9.6E-07 | 119687 | 9.0E-07 | 4.7E-04 | 2.3E-04 | 120321 | 9.6E-07 | 4.7E-04
Table 3: Comparison with Dixon & Price and Rosenbrock 1

It can be seen that the performance of the IRG and RG methods in Tests D200
with $\nu=0.01$ and $\nu=0.001$ is better than that of the GD method, while
the latter is more efficient in the other tests. It is reasonable that GD
usually performs better since it uses the exact gradient while RGB uses the
reduced gradient and IRGB uses even the inexact one. In the worst case in Test
R1000 with $\nu=0.01,$ the number of iterations of IRGB is equal around 1.3
times that of GD. It shows that IRGB does not suffer much from the use of
inexact gradient compared with the performance of GD using the exact gradient.
Table 3 also shows that the decrease of $\nu$ in $10$ times results in the
increase of the number of iterations in IRGB with the rate at most $1.7$,
where the worst case corresponds with the tests D500. This rate is similar to
the rate obtained by the GD method in these tests, which confirms that our IRG
method with the backtracking stepsize does not suffer from error accumulation.

The graphs below show that the errors $\delta_{k}$ of the inexact gradient
used in IRGB is automatically adjusted to be not too small or too large
compared with $\left\|\nabla f(x^{k})\right\|$. This confirms the intuitive
conclusion on the IRG methods discussed in Remark 4.2(ii). Figure 6 shows that
the selections of errors $\delta_{k}=k^{-p},p\geq 1$ in the existing methods
[10, 22, 25] do not fit the unexpected fluctuations in the norm of the exact
gradient given in the tests using the Rosenbrock function, which may lead to
the over approximation and under approximation issues discussed in Section 1.

Figure 6: Errors of IRGB compared with the norm of exact gradient

##  7  Conclusions and Further Research

In this paper, we propose and develop the inexact reduced gradient methods
with different stepsize selections to solve problems of nonconvex
optimization. These methods achieve stationary accumulation points and, under
additional assumptions on the KL property of the objective functions, the
global linear convergence. The convergence analysis of the developed
algorithms is based on novel convergence results established for general
linesearch methods. The theoretical and numerical comparisons show that our
methods do not suffer much from the error accumulation and are able to
automatically adjust the errors in the exact gradient approximations to get a
better performance than the existing methods using common selections of
errors.

In our future research, we aim at developing the IRG methods in different
directions, which include designing zeroth-order algorithms by using practical
methods for approximating gradients, designing inexact versions of methods
frequently used in nonconvex nonsmooth optimization, e.g., the proximal point
and proximal gradient methods, and also designing appropriate IRG methods for
problems of constrained optimization. The obtained results would allow us to
develop new applications to important classes of models in machine learning,
statistics, and related disciplines.

## References

  * [1] P.-A. Absil, R. Mahony and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim. 16 (2005), 531–547.
  * [2] A. Addis, A. Cassioli, M. Locatelli and F. Schoen, A global optimization method for the design of space trajectories, Comput. Optim. Appl. 48 (2011), 635–652.
  * [3] F. J. Aragón Artacho, R. M. T. Fleming and P. T. Vuong, Accelerating the DC algorithm for smooth functions, Math. Program. 169 (2018), 95–118.
  * [4] H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program. 116 (2009), 5–16.
  * [5] H. Attouch, J. Bolte, P. Redont and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka-Łojasiewicz property, Math. Oper. Res. 35 (2010), 438–457.
  * [6] H. H. Bauschke, J. Bolte and M. Teboulle, A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications, Math. Oper. Res. 42 (2017), 330–348.
  * [7] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edition, Springer. Cham, Switzerland, 2017.
  * [8] A. Beck, First-Order Methods in Optimization, SIAM, Philadelphia, PA, 2017.
  * [9] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), 183–202.
  * [10] D. P. Bertsekas, Nonlinear Programming, 3rd edition, Athena Scientific, Belmont, MA, 2016.
  * [11] P. Bloomfield and W. Steiger, Least absolute deviations curve fitting, SIAM J. Sci. Stat. Comput. 1 (1980), 290–301.
  * [12] J. Bolte, A. Daniilidis and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim. 17 (2006), 1205–1223.
  * [13] J. Bolte, S. Sabach and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program. 146 (2014), 459–494.
  * [14] L. Bottou, F. E. Curtis and J. Nocedal, Optimization methods for large-scale machine learning, SIAM Rev. 60 (2018), 223–311.
  * [15] L. M. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. & Math. Phys. 7 (1967), 200–217.
  * [16] J. V. Burke, A. S. Lewis and M. L. Overton, Two numerical methods for optimizing matrix stability, Linear Algebra Appl. 351–352 (2002), 147–184.
  * [17] J. V. Burke and Q. Lin, Convergence of the gradient sampling algorithm on directionally Lipschitz functions, Set-Valued Var. Anal. 29 (2021), 949–966.
  * [18] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.
  * [19] J. B. Crockett and H. Chernoff, Gradient methods of maximization, Pac. J. Math. 5 (1955), 33–50.
  * [20] H. B. Curry, The method of steepest descent for non-linear minimization problems, Q. Appl. Math. 2 (1944), 258–261.
  * [21] H. Dan, N. Yamashita and M. Fukushima, Convergence properties of the inexact Levenberg-Marquardt method under local error bound conditions, Optim. Meth. Softw. 17 (2002), 605–626
  * [22] O. Devolder, F. Glineur and Yu. Nesterov, First-order methods of smooth convex optimization with inexact oracle, Math. Program. 146 (2014), 37–75.
  * [23] F. Facchinei, On the convergence to a unique point of minimization algorithms, Technical Report 06-95, Dipartimento di Informacica e Sisemistica, Università di Roma ”La Sapienza”, Rome, Italy, 1995.
  * [24] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. II, Springer, New York, 2003.
  * [25] P. Gilmore and C. T. Kelley, An implicit filtering algorithm for optimization of functions with many local minima, SIAM J. Optim. 5 (1995), 269–285.
  * [26] A. A. Goldstein, Optimization of Lipschitz continuous functions, Math. Program. 13 (1977), 14–22.
  * [27] A. F. Izmailov and M. V. Solodov, Newton-Type Methods for Optimization and Variational Problems, Springer, New York, 2014.
  * [28] M. Jamil, A literature survey of benchmark functions for global optimization problems, Int. J. Math. Model. Numer. Optim. 4 (2013), 150–194.
  * [29] H. Karimi, J. Nutini and M. Schmidt, Linear convergence of gradient and proximal-gradient methods under the Polyak-Łojasiewicz condition, in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Lecture Notes in Computer Science, Part 1 (P. Frasconi et al., eds.), Springer, Cham, Switzerland, 2016, pp. 795–811.
  * [30] P. D. Khanh, B. S. Mordukhovich, V. T. Phat and D. B. Tran, Generalized damped Newton algorithms in nonsmooth optimization via second-order subdifferentials, J. Global Optim. (2022), https://doi.org/10.1007/s10898-022-01248-7.
  * [31] P. D. Khanh, B. S. Mordukhovich, V. T. Phat and D. B. Tran, Globally convergent coderivative-based generalized Newton methods in nonsmooth optimizations, DOI:10.48550/arXiv.2109.02093.
  * [32] K. C. Kiwiel, Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim. 18 (2007), 379–388.
  * [33] K. C. Kiwiel, A nonderivative version of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM J. Optim. 20(4), 1983–1994 (2010)
  * [34] K. Kurdyka, On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier 48 (1998), 769–783.
  * [35] A. S. Lewis, D. R. Luke and J. Malick, Local linear convergence for alternating and averaged nonconvex projections, Found. Comput. Math. 9 (2009), 485-–513.
  * [36] H. A. Le Thi, V. N. Huynh and D. T. Pham, Convergence analysis of DC algorithm for DC programming with subanalytic data, J. Optim. Theory Appl. 179 (2018), 103–126.
  * [37] S. Łojasiewicz, Ensembles semi-analytiques, Institut des Hautes Etudes Scientifiques, Bures-sur-Yvette (Seine-et-Oise), France, 1965.
  * [38] H. Lu, R. M. Freund and Yu. Nesterov, Relatively smooth convex optimization by first-order methods, and applications, SIAM J. Optim. 28 (2018), 333–-354.
  * [39] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications, Springer, Berlin, 2006.
  * [40] B. S. Mordukhovich, Variational Analysis and Applications, Springer, Cham, Switzerland, 2018.
  * [41] Yu. Nesterov, Universal gradient methods for convex optimization problems, Math. Program. 152 (2015), 381–404.
  * [42] Yu. Nesterov, Lectures on Convex Optimization, 2nd edition, Springer, Cham, Switzerland, 2018
  * [43] M. A. Nielsen, Neural Networks and Deep Learning. Determination Press, New York (2015)
  * [44] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd edition. New York, 2016.
  * [45] A. Ostrowski, Solution of Equations and Systems of Equations, 2nd edition, Academic Press, New York, 1966.
  * [46] B. T. Polyak, Gradient methods for minimizing functionals, USSR Comput. Math. & Math. Phys. 3 (1963), 864–878.
  * [47] B. T. Polyak, Introduction to Optimization, Optimization Software, New York, 1987.
  * [48] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976), 877–898.
  * [49] R. T. Rockafellar and R. J-B. Wets, Variational Analysis, Springer, Berlin, 1998.
  * [50] T. Rotaru, F. Glineur and P. Patrinos, Tight convergence rates of the gradient method on hypoconvex functions, DOI:10.48550/arXiv.2203.00775
  * [51] S. Ruder, An overview of gradient descent optimization algorithms, DOI: 10.48550/arXiv:1609.04747.
  * [52] A. Themelis, L. Stella and P. Patrinos, Forward–backward quasi-Newton methods for nonsmooth optimization problems. Comput. Optim. Appl.67 (2017), 443–487.
  * [53] Z. Xingyu, On the Fenchel duality between strong convexity and Lipschitz continuous gradient, DOI:10.48550/arXiv.1803.06573.