# Inexact gradient projection method with relative error tolerance

A. A. Aguiar Instituto de Matemática e Estatística, Universidade Federal de
Goiás, CEP 74001-970 - Goiânia, GO, Brazil, E-mails:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>The authors was
supported in part by CNPq grants 305158/2014-7 and 302473/2017-3,
FAPEG/PRONEM- 201710267000532 and CAPES. O. P. Ferreira 11footnotemark: 1 L.
F. Prudente 11footnotemark: 1

###### Abstract

A gradient projection method with feasible inexact projections is proposed in
the present paper. The inexact projection is performed using a relative error
tolerance. Asymptotic convergence analysis and iteration-complexity bounds of
the method employing constant and Armijo step sizes are presented. Numerical
results are reported illustrating the potential advantages of considering
inexact projections instead of exact ones in some medium scale instances of a
least squares problem over the spectrohedron.

Keywords: Gradient method, feasible inexact projection, constrained convex
optimization.

AMS subject classification: 49J52, 49M15, 65H10, 90C30.

##  1 Introduction

In this paper, we address general constrained convex optimization problems of
the form

$\min\\{f(x):~{}x\in C\\},$ (1)

where $C$ is a closed and convex subset of $\mathbb{R}^{n}$ and
$f:\mathbb{R}^{n}\to{\mathbb{R}}$ is a continuously differentiable function.
Denote by $f^{*}:=\inf_{x\in C}f(x)$ the optimal value of (1) and by
$\Omega^{*}$ its solution set, which we will assume to be non-empty unless the
contrary is explicitly stated. The Problem (1) is a basic optimization issue,
it has appeared in several areas of science and engineering, including machine
learning, control theory and signal processing, see for example [9, 10, 17,
36, 46]. In the present paper, we are interested in gradient-type algorithms
to solve it.

The gradient projection method (GPM) is the one of the most oldest method to
solve Problem (1), its convergence properties go back to the works of
Goldstein [22] and Levitin and Polyak [35]. After these works, many variants
of it have appeared throughout the years, resulting in a wide literature on
the subject, see, for example, [4, 5, 6, 16, 17, 25, 27, 28, 43, 51]. The GPM
has attracted the attention of the scientific community working in
optimization, mainly due to its simplicity and easy implementation. Besides,
since this method uses only first order derivatives, it is often considered as
a scalable solver for large-scale optimization problems, see [31, 38, 39, 41,
46, 48]. At each iteration, the classical GPM moves along the direction of the
negative gradient, and then projects the iterate onto $C$ if it is infeasible.
Although the feasible set of many important problems has an easy-to-handle
structure, in general this set could be so complex that the exact projection
can not be easily computed. It is well known that the mostly computational
burden of each iteration of the GPM is in the solution of this subproblem. In
fact, one drawback of methods that use exact projections is to solve a
quadratic problem at each stage, which can lead to a substantial increase in
the cost per iteration if the number of unknowns is large. In order to reduce
the computational effort spent on projections, inexact procedures have been
proposed, resulting in more efficient methods, see for example [8, 16, 43,
51]. Moreover, considering inexact schemes provides theoretical support for
real computational implementations of exact methods. It is worth mentioning
that throughout the years there has been an increase in the popularity of
inexact methods due to the emergence of large-scale problems in compressed
sensing, machine learning applications and data fitting, see for instance [21,
44, 45, 46]. Motivated by practical and theoretical reasons, the purpose of
the present paper is to present a new inexact version of the GPM, which we
call Gradient-InexP method (GInexPM). It consists of using a general inexact
projection instead of the exact one used in the GPM. The inexact projection
concept considered in the present paper is a variation of the one appeared in
[49, Example 1], which is defined by using an approximated property of the
exact projection. In particular, it accepts the exact projection which can be
adopted when it is easily obtained (for instance, the exact projection onto a
box constraint or Lorentz cone can be easily obtained; see [42, p. 520] and
[20, Proposition 3.3], respectively). It is worth noting that our approach to
compute the inexact projection has not being considered in the study of the
classical gradient method, in particular it is different from the ones
proposed in [8, 16, 21, 43, 45, 51]. The analyses of GInexPM will be made
employing two diferent step sizes, namely, constant step size and Armijo’s
step size along the feasible direction. We point out that these step sizes are
discussed extensively in the literature on this subject, where many of our
results were inspired, see for example [4, 6, 28, 29, 33, 40].

Contributions: The main novelty in our work is the use of relative error
tolerances in the computation of the inexact projection, to analyze the
convergence properties of GInexPM. Our numerical experiments showed that
GInexPM outperformed the GPM on a set of least squares problem over the
spectrohedron. From a theoretical point of view, under suitable assumptions,
the classic results of GPM were obtained for GInexPM as well. More
specifically, we have showed that all cluster points of the sequence generated
by GInexPM with constant step size or Armijo’s step size are solutions of
problem (1). Futhermore, under convexity of the objective function, this
sequence converges to a solution, if any. In both cases, the analysis
establishes convergence results without any compactness assumption. We have
also studied iteration-complexity bounds of GInexPM for both constant step
size and Armijo’s step size. The presented analysis establishes that the
complexity bound $\mathcal{O}(1/\sqrt{k})$ is unveil for finding
$\epsilon$-stationary points for Problem (1), and, under convexity on $f$, the
rate to find a $\epsilon$-optimal functional value is $\mathcal{O}(1/k)$.

Content of the paper: In section 2, some notations and basic results used
throughout the paper is presented. In particular, section 2.1 is devoted to
present the concept relative feasible inexact projection and some properties
about this concept. In section 3, we describe GInexPM method using the
constant step size. The results of convergence using constant step size, as
well as, results of iteration-complexity bound are presented in the sections
3.1 and 3.2, respectively. The results related to Armijo’s step sizes is
presented in section 4. In section 4.1, we present the asymptotic convergence
analysis of GInexPM using Armijo’s step size, and an iteration-complexity
bound is presented in section 4.2. Numerical experiments are provided in
section 5. Finally, the last section presents some final considerations.

##  2 Preliminaries

In this section, we introduce some notation and results used throughout our
presentation. We denote ${\mathbb{N}}:=\\{0,1,2,\ldots\\}$,
$\langle\cdot,\cdot\rangle$ is the usual inner product in $\mathbb{R}^{n}$ and
$\|\cdot\|$ is the Euclidean norm. Let $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ be
a differentiable function and $C\subseteq{\mathbb{R}}^{n}$. The gradient
$\nabla f$ of $f$ is said to be Lipschitz continuous on $C$ with constant
$L>0$ if

$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|,\qquad\forall~{}x,y\in C.$ (2)

Combining this definition with the fundamental theorem of calculus, we obtain
the following result, for which the proof can found in [6, Proposition A.24].

######  Lemma 1.

Let $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ be a differentiable function with
Lipschitz continuous gradient on $C\subseteq{\mathbb{R}}^{n}$ with constant
$L>0$. Then, $f(y)-f(x)-\langle\nabla
f(x),y-x\rangle\leq\frac{L}{2}\|x-y\|^{2}$, for all $x,y\in C$.

Let $f:{\mathbb{R}}^{n}\to{\mathbb{R}}$ be a differentiable function and
$C\subseteq{\mathbb{R}}^{n}$ be a convex set. The function $f$ is strongly
convex on $C$, if there exists a constant $\mu\geq 0$ such that

$f(y)-f(x)-\langle\nabla
f(x),y-x\rangle\geq\frac{\mu}{2}\|x-y\|^{2},\qquad\forall~{}x,y\in C.$ (3)

When $\mu=0$, $f$ is said to be convex. If $f(x)\leq f(y)$ implies
$\langle\nabla f(y),x-y\rangle\leq 0$, for any $x,y\in C$, then $f$ is said to
be quasiconvex. Moreover, $f$ is said to be pseudoconvex if $\langle\nabla
f(y),x-y\rangle\geq 0$ implies $f(x)\leq f(y)$, for any $x,y\in C$, for more
details, see [37]. Recall that the convexity of a function guarantees
pseudoconvexity, which in turn guarantees quasiconvexity, see [37].

A point ${\bar{x}}\in C$ is said to be a stationary point for Problem (1) if

$\langle\nabla f({\bar{x}}),x-{\bar{x}}\rangle\geq 0,\qquad\forall~{}x\in C.$
(4)

We end this section with a useful concept in the analysis of the sequence
generated by the gradient method, for more details, see [12].

######  Definition 1.

A sequence $(y^{k})_{k\in\mathbb{N}}$ in $\mathbb{R}^{n}$ is quasi-Fejér
convergent to a set $W\subset{\mathbb{R}}^{n}$ if, for every $w\in W$, there
exists a sequence $(\epsilon_{k})_{k\in\mathbb{N}}\subset\mathbb{R}$ such that
$\epsilon_{k}\geq 0$, $\sum_{k\in\mathbb{N}}\epsilon_{k}<+\infty$, and
$\|y_{k+1}-w\|^{2}\leq\|y_{k}-w\|^{2}+\epsilon_{k}$, for all $k\in\mathbb{N}$.

The main property of a quasi-Fejér convergent sequence is stated in the next
result, and its proof can be found in [12].

######  Theorem 2.

Let $(y^{k})_{k\in\mathbb{N}}$ be a sequence in $\mathbb{R}^{n}$. If
$(y^{k})_{k\in\mathbb{N}}$ is quasi-Fejér convergent to a nomempty set
$W\subset{\mathbb{R}}^{n}$, then $(y^{k})_{k\in\mathbb{N}}$ is bounded.
Furthermore, if a cluster point $y$ of $(y^{k})_{k\in\mathbb{N}}$ belongs to
$W$, then $\lim_{k\rightarrow\infty}y_{k}=y$.

###  2.1 Inexact projection

In this section, we present the concept of feasible inexact projection onto a
closed and convex set. This concept has already been used in [1, 13, 14]. We
also present some new properties of the feasible inexact projection used
throughout the paper. The definition of feasible inexact projection is as
follows.

######  Definition 2.

Let $C\subset{\mathbb{R}}^{n}$ be a closed convex set and
$\varphi_{\gamma}:{\mathbb{R}}^{n}\times{\mathbb{R}}^{n}\times{\mathbb{R}}^{n}\to{\mathbb{R}}_{+}$
be a function satisfying the following condition

$\varphi_{\gamma}(u,v,w)\leq\gamma_{1}\|v-u\|^{2}+\gamma_{2}\|w-v\|^{2}+\gamma_{3}\|w-u\|^{2},\qquad\forall~{}u,v,w\in{\mathbb{R}}^{n},$
(5)

where $\gamma=(\gamma_{1},\gamma_{2},\gamma_{3})\in{\mathbb{R}}^{3}_{+}$ is a
given forcing parameter. The feasible inexact projection mapping relative to
$u\in C$ with error tolerance $\varphi_{\gamma}$, denoted by ${\cal
P}_{C}(\varphi_{\gamma},u,\cdot):{\mathbb{R}}^{n}\rightrightarrows C$, is the
set-valued mapping defined as follows

${\cal P}_{C}(\varphi_{\gamma},u,v):=\left\\{w\in
C:~{}\big{\langle}v-w,y-w\big{\rangle}\leq\varphi_{\gamma}(u,v,w),\quad\forall~{}y\in
C\right\\}.$ (6)

Each point $w\in{\cal P}_{C}(\varphi_{\gamma},u,v)$ is called a feasible
inexact projection of $v$ onto $C$ relative to $u$ with error tolerance
$\varphi_{\gamma}$.

The feasible inexact projection generalizes the concept usual projection. In
the following, we present some remarks about this concept and some examples of
functions satisfying (5).

######  Remark 1.

Let $\gamma_{1}$, $\gamma_{2}$ and $\gamma_{3}$ be nonnegative forcing
parameters, $C\subset{\mathbb{R}}^{n}$, $u\in C$ and $\varphi_{\gamma}$ be as
in Definition 2. Therefore, for all $v\in{\mathbb{R}}^{n}$, it follows from
(6) that ${\cal P}_{C}(\varphi_{0},u,v)$ is the exact projection of $v$ onto
$C$; see [6, Proposition 2.1.3, p. 201]. Moreover, ${\cal
P}_{C}(\varphi_{0},u,v)\in{\cal P}_{C}(\varphi_{\gamma},u,v)$ which implies
that ${\cal P}_{C}(\varphi_{\gamma},u,v)\neq\varnothing$, for all $u\in C$ and
$v\in{\mathbb{R}}^{n}$. Consequently, the set-valued mapping ${\cal
P}_{C}(\varphi_{\gamma},u,\cdot)$ as stated in (6) is well-defined. Note that
the following functions
$\varphi_{1}(u,v,w)=\gamma_{1}\|v-u\|^{2}+\gamma_{2}\|w-v\|^{2}+\gamma_{3}\|w-u\|^{2}$,
$\varphi_{2}(u,v,w)=\gamma_{1}\|v-u\|^{2}$,
$\varphi_{3}(u,v,w)=\gamma_{2}\|w-v\|^{2}$,
$\varphi_{4}(u,v,w)=\gamma_{3}\|w-u\|^{2}$, and
$\varphi_{5}(u,v,w)=\gamma_{1}\gamma_{2}\gamma_{3}\|v-u\|^{2}\|w-v\|^{2}\|w-u\|^{2}$
satisfy (5).

Item (a) of the next lemma is a variation of [14, Lemma 6]. By using item (a),
we will derive an inequality that together with this item will play an
important role in the remainder of this paper.

######  Lemma 3.

Let $v\in{\mathbb{R}}^{n}$, $u\in C$,
$\gamma=(\gamma_{1},\gamma_{2},\gamma_{3})\in{\mathbb{R}}^{3}_{+}$ and
$w\in{\cal P}_{C}(\varphi_{\gamma},u,v)$. Then, there hold:

  * (a)

$\displaystyle\|w-x\|^{2}\leq\|v-x\|^{2}+\frac{2\gamma_{1}+2\gamma_{3}}{1-2\gamma_{3}}\|v-u\|^{2}-\frac{1-2\gamma_{2}}{1-2\gamma_{3}}\|w-v\|^{2}$,
for all $x\in C$ and $0\leq\gamma_{3}<1/2$;

  * (b)

$\displaystyle\big{\langle}v-w,y-w\big{\rangle}\leq\frac{\gamma_{1}+\gamma_{2}}{1-2\gamma_{2}}\|v-u\|^{2}+\frac{\gamma_{3}-\gamma_{2}}{1-2\gamma_{2}}\|w-u\|^{2}$,
for all $y\in C$ and $0\leq\gamma_{2}<1/2$.

###### Proof.

Let $x\in C$ and $0\leq\gamma_{3}<1/2$. First note that
$\|w-x\|^{2}=\|v-x\|^{2}-\|w-v\|^{2}+2\langle v-w,x-w\rangle$. Since
$w\in{\cal P}_{C}(\varphi_{\gamma},u,v)$, combining the last equality with (5)
and (6), we obtain

$\|w-x\|^{2}\leq\|v-x\|^{2}-(1-2\gamma_{2})\|w-v\|^{2}+2\gamma_{1}\|v-u\|^{2}+2\gamma_{3}\|w-u\|^{2}.$
(7)

On the other hand, we have $\|w-u\|^{2}=\|v-u\|^{2}-\|w-v\|^{2}+2\langle
v-w,u-w\rangle$. Thus, due to $w\in{\cal P}_{C}(\varphi_{\gamma},u,v)$ and
$u\in C$, using (5) and (6), and considering that $0\leq\gamma_{3}<1/2$, we
have

$\|w-u\|^{2}\leq\frac{1+2\gamma_{1}}{1-2\gamma_{3}}\|v-u\|^{2}-\frac{1-2\gamma_{2}}{1-2\gamma_{3}}\|w-v\|^{2}.$

Therefore, combining the last inequality with (7), we obtain the inequality of
item $(a)$. For proving item $(b)$, take $y\in C$ and $0\leq\gamma_{2}<1/2$.
Using (5) and (6), we have

$\big{\langle}v-w,y-w\big{\rangle}\leq\gamma_{1}\|v-u\|^{2}+\gamma_{2}\|w-v\|^{2}+\gamma_{3}\|w-u\|^{2}.$
(8)

Applying item $(a)$ with $x=u$, after some algebraic manipulations, we
conclude that

$\|w-v\|^{2}\leq\frac{1+2\gamma_{1}}{1-2\gamma_{2}}\|v-u\|^{2}-\frac{1-2\gamma_{3}}{1-2\gamma_{2}}\|w-u\|^{2}.$

The last inequality together (8) yield

$\big{\langle}v-w,y-w\big{\rangle}\leq\left(\gamma_{1}+\frac{\gamma_{2}+2\gamma_{1}\gamma_{2}}{1-2\gamma_{2}}\right)\|v-u\|^{2}+\left(\gamma_{3}-\frac{\gamma_{2}-2\gamma_{2}\gamma_{3}}{1-2\gamma_{2}}\right)\|w-u\|^{2},$

which is equivalent to the inequality in $(b)$. ∎

##  3 GInexPM employing the constant step size rule

In this section, we describe the GInexPM with a feasible inexact projection
for solving problem (1). The rule for choosing the step size will be the same
used in [3, 6], namely, the constant step size rule. For that, we take a
exogenous sequence of real numbers $(a_{k})_{k\in\mathbb{N}}$ satisfying

$0\leq a_{k}\leq b_{k-1}-b_{k},\qquad k=0,1,\ldots,$ (9)

for some given nonincreasing sequence of nonegative real numbers
$(b_{k})_{k\in\mathbb{N}}$ converging to zero, with the notation
$b_{-1}\in{\mathbb{R}}_{++}$ such that $b_{-1}>b_{0}$.

######  Remark 2.

Condition (9) implies that $\sum_{k\in\mathbb{N}}a_{k}<b_{-1}$. Examples of
sequences $(a_{k})_{k\in\mathbb{N}}$ and $(b_{k})_{k\in\mathbb{N}}$ satisfying
(9) are obtained by taking $a_{k}:=b_{k-1}-b_{k}$ and, for a given
$\bar{b}>0$: (i) $b_{-1}=3\bar{b}$, $b_{0}=2\bar{b}$, $b_{k}=\bar{b}/k$, for
all $k=1,2,\ldots$; (ii) $b_{-1}=3\bar{b}$, $b_{0}=2\bar{b}$,
$b_{k}=\bar{b}/\ln(k+1)$, for all $k=1,2,\ldots$.

The conceptual GInexPM is formally stated as follows.

Algorithm 1 GInexPM employing constant step size

Step 0: Take $(a_{k})_{k\in\mathbb{N}}$, $(b_{k})_{k\in\mathbb{N}}$ satisfying
(9) and an error tolerance function $\varphi_{\gamma}$. Let $x^{0}\in C$ and
set $k=0$.

Step 1: If $\nabla f(x^{k})=0$, then stop; otherwise, choose real numbers
$\gamma_{1}^{k},\gamma_{2}^{k}$ and $\gamma_{3}^{k}$ such that
$0\leq\gamma_{1}^{k}+\gamma_{2}^{k}\leq\frac{a_{k}}{\|\nabla
f(x^{k})\|^{2}},\qquad 0\leq\gamma_{2}^{k}<\bar{\gamma_{2}}<\frac{1}{2},\qquad
0\leq\gamma_{3}^{k}<\bar{\gamma}<\frac{1}{2},$ (10) and a fixed step size
$\alpha>0$ and define the next iterate $x^{k+1}$ as any feasible inexact
projection of $z^{k}:=x^{k}-\alpha\nabla f(x^{k})$ onto $C$ relative to
$x^{k}$ with forcing parameters
$\gamma^{k}:=(\gamma^{k}_{1},\gamma^{k}_{2},\gamma^{k}_{3})$, i.e.,
$x^{k+1}\in{\cal P}_{C}\left(\varphi_{\gamma^{k}},x^{k},z^{k}\right).$

Step 2: Set $k\leftarrow k+1$, and go to Step 1.

Let us describe the main features of the GInexPM. Firstly, we take exogenous
sequences $(a_{k})_{k\in\mathbb{N}}$ and $(b_{k})_{k\in\mathbb{N}}$ satisfying
(9) and an error tolerance function $\varphi_{\gamma}$. Then, we check if at
the current iterate $x^{k}$ we have $\nabla f(x^{k})=0$, otherwise, we choose
nonnegative forcing parameters $\gamma_{1}^{k}$, $\gamma_{2}^{k}$ and
$\gamma_{3}^{k}$ satisfying (10). Set a fixed step size $\alpha>0$. By using
some inner procedure, the next iterate $x^{k+1}$ is computed as any feasible
inexact projection of $z^{k}=x^{k}-\alpha\nabla f(x^{k})$ onto the feasible
set $C$ relative to $x^{k}$, i.e., $x^{k+1}\in{\cal
P}_{C}(\varphi_{\gamma^{k}},x^{k},z^{k})$; an example of such procedure will
be presented in section 5. Note that, if $\gamma_{1}^{k}\equiv 0$,
$\gamma_{2}^{k}\equiv 0$ and $\gamma_{3}^{k}\equiv 0$, then ${\cal
P}_{C}({\varphi_{0}},x^{k},z^{k})$ is the exact projection, see Remark 1, and
our method corresponds to the usual projected gradient method proposed, for
example, in [3, 6]. It is worth noting that $\gamma_{1}^{k}$ and
$\gamma_{2}^{k}$ in (10) can be chosen as any nonnegative real numbers
satisfying $0\leq(\gamma_{1}^{k}+\gamma_{2}^{k})\|\nabla f(x^{k})\|^{2}\leq
a_{k}$, for prefixed sequences $(a_{k})_{k\in\mathbb{N}}$ and
$(b_{k})_{k\in\mathbb{N}}$ satisfying (9). In this case, we have

$\sum_{k\in\mathbb{N}}\big{[}(\gamma_{1}^{k}+\gamma_{2}^{k})\|\nabla
f(x^{k})\|^{2}\big{]}<+\infty.$ (11)

In the next sections, we will deal with the convergence analysis of the
sequence $(x^{k})_{k\in\mathbb{N}}$ generated by GInexPM.

###  3.1 Asymptotic convergence analysis

The aim of this section is to prove the main convergence results about the
asymptotic behavior of the sequence $(x^{k})_{k\in\mathbb{N}}$ generated by
Algorithm 1. We assume that the gradient of the objective function $f$ is
Lipschitz continuous with constant $L>0$. Moreover, we also assume that

$0<\alpha<\frac{1-2\bar{\gamma}}{L}.$ (12)

For future references, it is convenient to define the following constants:

$\nu:=\frac{1-\bar{\gamma_{2}}-\bar{\gamma}}{\alpha}-\frac{L}{2}>0,\qquad\rho:=\frac{\alpha}{1-2\bar{\gamma_{2}}}>0.$
(13)

In the sequel, we state and prove our first result for the sequence
$(x^{k})_{k\in\mathbb{N}}$. The obtained inequality is the counterpart of the
one obtained, for example, in [3, Lemma 9.11, p. 176].

######  Lemma 4.

The following inequality holds:

$f(x^{k+1})\leq f(x^{k})+\rho(\gamma_{1}^{k}+\gamma_{2}^{k})\|\nabla
f(x^{k})\|^{2}-\nu\|x^{k+1}-x^{k}\|^{2},\qquad\forall~{}{k\in\mathbb{N}}.$
(14)

###### Proof.

Since $\nabla f$ satisfies (2), applying Lemma 1 with $x=x^{k}$ and
$y=x^{k+1}$, we obtain

$f(x^{k+1})\leq f(x^{k})+\big{\langle}\nabla
f(x^{k}),x^{k+1}-x^{k}\big{\rangle}+\frac{L}{2}\|x^{k+1}-x^{k}\|^{2}.$

Thus, after some algebraic manipulations, we have

$f(x^{k+1})\leq f(x^{k})+\frac{1}{\alpha}\big{\langle}[x^{k}-\alpha\nabla
f(x^{k})]-x^{k+1},x^{k}-x^{k+1}\big{\rangle}-\left(\frac{1}{\alpha}-\frac{L}{2}\right)\|x^{k+1}-x^{k}\|^{2}.$
(15)

Since $x^{k+1}\in{\cal P}_{C}(\varphi_{\gamma^{k}},x^{k},z^{k})$ with
$z^{k}=x^{k}-\alpha\nabla f(x^{k})$, applying item $(b)$ of Lemma 3 with
$u=x^{k}$, $y=x^{k}$, $v=z^{k}$, $w=x^{k+1}$, and
$\varphi_{\gamma}=\varphi_{\gamma_{k}}$, we have

$\big{\langle}[x^{k}-\alpha\nabla
f(x^{k})]-x^{k+1},x^{k}-x^{k+1}\big{\rangle}\leq\frac{\gamma_{1}^{k}+\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\alpha^{2}\|\nabla
f(x^{k})\|^{2}+\frac{\gamma_{3}^{k}-\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\|x^{k+1}-x^{k}\|^{2}.$

Then, combining (15) with the latter inequality yields

$f(x^{k+1})\leq
f(x^{k})+\frac{\alpha(\gamma_{1}^{k}+\gamma_{2}^{k})}{1-2\gamma_{2}^{k}}\|\nabla
f(x^{k})\|^{2}-\left[\frac{1-\gamma_{2}^{k}-\gamma_{3}^{k}}{\alpha(1-2\gamma_{2}^{k})}-\frac{L}{2}\right]\|x^{k+1}-x^{k}\|^{2}.$

Therefore, taking into account (10) and (13), we have (14), which concludes
the proof. ∎

The next result is an immediate consequence of Lemma 4.

######  Corollary 5.

The sequence $(f(x^{k})+\rho b_{k-1})_{k\in\mathbb{N}}$ is monotone non-
increasing. In particular, $\inf_{k}(f(x^{k})+\rho b_{k-1})=\inf_{k}f(x^{k})$.

###### Proof.

Combining (10) with (14), we have $f(x^{k+1})\leq f(x^{k})+\rho a_{k}$, for
all ${k\in\mathbb{N}}$. Thus, taking into account that
$(a_{k})_{k\in\mathbb{N}}$ satisfies (9), we obtain
$f(x^{k+1})+\rho{b_{k}}\leq f(x^{k})+\rho{b_{k-1}}$, for all
${k\in\mathbb{N}}$, implying the first statement. Since
$(b_{k})_{k\in\mathbb{N}}$ converges to zero, the second statement holds. ∎

Now, we are ready to state and prove a partial asymptotic convergence result
on $(x^{k})_{k\in\mathbb{N}}$.

######  Theorem 6.

Assume that $-\infty<f^{*}$. If ${\bar{x}}\in C$ is a cluster point of the
sequence $(x^{k})_{k\in\mathbb{N}}$, then ${\bar{x}}$ is a stationary point
for problem (1).

###### Proof.

By (10), we have $(\gamma_{1}^{k}+\gamma_{2}^{k})\|\nabla f(x^{k})\|^{2}\leq
a_{k}$, for all ${k\in\mathbb{N}}$. Thus, Lemma 4 implies that that
$\nu\|x^{k+1}-x^{k}\|^{2}\leq[f(x^{k})-f(x^{k+1})]+\rho a_{k}$, for all
${k\in\mathbb{N}}$. Using (9), after some adjustments, we obtain
$\|x^{k+1}-x^{k}\|^{2}\leq\left[f(x^{k})+\rho
b_{k-1}\right]/{\nu}-\left[f(x^{k+1})+\rho b_{k}\right]/{\nu}$, for all
$k\in\mathbb{N}$. Hence, due to $f^{*}\leq\inf_{k}f(x^{k})$, Corollary 5
implies $\sum_{\ell=0}^{k}\|x^{\ell+1}-x^{\ell}\|^{2}\leq[f(x^{0})+\rho
b_{-1}]/{\nu}-f^{*}/{\nu}$. Thus, we conclude that
$\lim_{k\to+\infty}\|x^{k+1}-x^{k}\|=0$. Let ${\bar{x}}$ be a cluster point of
$(x^{k})_{k\in\mathbb{N}}$ and $(x^{k_{j}})_{j\in\mathbb{N}}$ a subsequence of
$(x^{k})_{k\in\mathbb{N}}$ such that $\lim_{j\to+\infty}x^{k_{j}}=~{}\bar{x}$.
Since, $\lim_{j\to+\infty}(x^{k_{j}+1}-x^{k_{j}})=0$, we have
$\lim_{j\to+\infty}x^{k_{j}+1}={\bar{x}}$. On the other hand, due to
$x^{k_{j}+1}\in{\cal P}_{C}(\varphi_{\gamma^{k_{j}}},x^{k_{j}},z^{k_{j}})$,
where $z^{k_{j}}:=x^{k_{j}}-\alpha\nabla f(x^{k_{j}})$, applying item $(b)$ of
Lemma 3 with $v=z^{k_{j}}$, $u=x^{k_{j}}$, $w=x^{k_{j}+1}$, and
$\varphi_{\gamma}=\varphi_{\gamma^{k_{j}}},$ we obtain

$\big{\langle}z^{k_{j}}-x^{k_{j}+1},y-x^{k_{j}+1}\big{\rangle}\leq\frac{\gamma_{1}^{k_{j}}+\gamma_{2}^{k_{j}}}{1-2\gamma_{2}^{k_{j}}}\alpha^{2}\|\nabla
f(x^{k_{j}})\|^{2}+\frac{\gamma_{3}^{k_{j}}-\gamma_{2}^{k_{j}}}{1-2\gamma_{2}^{k_{j}}}\|x^{k_{j}+1}-x^{k_{j}}\|^{2},\qquad\forall~{}y\in
C.$

Thus, taking limits on both sides of the last inequality, we conclude, by
using (11) and continuity of $\nabla f$, that
$\big{\langle}[{\bar{x}}-\alpha\nabla
f({\bar{x}})]-{\bar{x}},y-{\bar{x}}\big{\rangle}\leq 0$, for all $y\in C$.
Therefore, $\big{\langle}\nabla f({\bar{x}}),y-{\bar{x}}\big{\rangle}\geq 0$,
for all $y\in C$, which implies that ${\bar{x}}\in C$ is a stationary point
for problem (1). ∎

In the following lemma, we establish a basic inequality satisfied by
$(x^{k})_{k\in\mathbb{N}}$. In particular, it will be useful to prove the full
asymptotic convergence of $(x^{k})_{k\in\mathbb{N}}$ under quasiconvexity of
$f$.

######  Lemma 7.

For each $x\in C$ and ${k\in\mathbb{N}}$, there holds

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+2\alpha\rho(\gamma_{1}^{k}+\gamma_{2}^{k})\|\nabla
f(x^{k})\|^{2}+2\alpha\big{[}f(x^{k})-f(x^{k+1})+\langle\nabla
f(x^{k}),x-x^{k}\rangle\big{]}.$

###### Proof.

Let $x\in C$. By using $z_{k}=x^{k}-\alpha\nabla f(x^{k})$, after some
algebraic manipulations, we have

$\displaystyle\|x^{k+1}-x\|^{2}=\|x^{k}-x\|^{2}-\|x^{k+1}-x^{k}\|^{2}+2\big{\langle}z^{k}-x^{k+1},x-x^{k+1}\big{\rangle}+2\alpha\big{\langle}\nabla
f(x^{k}),x-x^{k+1}\big{\rangle}.$

Since $x^{k+1}\in{\cal P}_{C}(\varphi_{\gamma^{k}},x^{k},z^{k})$, applying
item $(b)$ of Lemma 3 with $y=x$, $v=z^{k}$, $u=x^{k}$, $w=x^{k+1}$, and
$\varphi_{\gamma}=\varphi_{\gamma^{k}},$ we obtain

$\big{\langle}z^{k}-x^{k+1},x-x^{k+1}\big{\rangle}\leq\frac{\gamma_{1}^{k}+\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\alpha^{2}\|\nabla
f(x^{k})\|^{2}+\frac{\gamma_{3}^{k}-\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\|x^{k+1}-x^{k}\|^{2}.$

On the other hand, since $\nabla f$ satisfies (2), Lemma 1 with $x=x^{k}$ and
$y=x^{k+1}$ yields

$\displaystyle\big{\langle}\nabla f(x^{k}),x-x^{k+1}\big{\rangle}$
$\displaystyle=\big{\langle}\nabla
f(x^{k}),x^{k}-x^{k+1}\big{\rangle}+\big{\langle}\nabla
f(x^{k}),x-x^{k}\big{\rangle}$ $\displaystyle\leq
f(x^{k})-f(x^{k+1})+\frac{L}{2}\|x^{k+1}-x^{k}\|^{2}+\big{\langle}\nabla
f(x^{k}),x-x^{k}\big{\rangle}.$

Combining last two inequities with the above equality, we conclude that

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}-\left[\frac{1-2\gamma_{3}^{k}}{1-2\gamma_{2}^{k}}-\alpha
L\right]\|x^{k+1}-x^{k}\|^{2}\\\
+2\alpha^{2}\left(\frac{\gamma_{1}^{k}+\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\right)\|\nabla
f(x^{k})\|^{2}+2\alpha\left[f(x^{k})-f(x^{k+1})+\big{\langle}\nabla
f(x^{k}),x-x^{k}\big{\rangle}\right].$ (16)

Taking into account (10), we have $0\leq 1-2\bar{\gamma_{2}}\leq
1-2\gamma_{2}^{k}\leq 1$ and $1-2\gamma_{3}^{k}\geq 1-2\bar{\gamma}\geq 0$.
Hence, it follows from (12) and (13) that

$\frac{\alpha}{1-2\gamma_{2}^{k}}\leq\frac{\alpha}{1-2\bar{\gamma_{2}}}=\rho,\qquad\qquad\left[\frac{1-2\gamma_{3}^{k}}{1-2\gamma_{2}^{k}}-\alpha
L\right]\geq\left[1-2\gamma_{3}^{k}-\alpha
L\right]\geq\left[1-2\bar{\gamma}-\alpha L\right]\geq 0.$

These inequalities, together with (16), imply the desired inequality, which
concludes the proof. ∎

To proceed with the analysis of $(x^{k})_{k\in\mathbb{N}}$, we also need the
following auxiliary set

$T:=\left\\{x\in C:f(x)\leq\inf_{k}f(x^{k}),\quad{k\in\mathbb{N}}\right\\}.$

######  Corollary 8.

Assume that $f$ is a quasiconvex function. If $T\neq\varnothing$, then
$(x^{k})_{k\in\mathbb{N}}$ converges to a stationary point for problem (1).

###### Proof.

Let $x\in T$. Since $f$ is a quasiconvex function and $f(x)\leq f(x^{k})$ for
all $k\in\mathbb{N}$, we have $\big{\langle}\nabla
f(x^{k}),x-x^{k}\big{\rangle}\leq~{}0$, for all $k\in\mathbb{N}$. Thus,
applying Lemma 7, we conclude that

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+2\alpha\rho(\gamma_{1}^{k}+\gamma_{2}^{k})\|\nabla
f(x^{k})\|^{2}+\\\
2\alpha\left[f(x^{k})-f(x^{k+1})\right],\qquad\forall~{}{k\in\mathbb{N}}.$

Thus, using the first condition in (10) and considering that
$(a_{k})_{k\in\mathbb{N}}$ and $(b_{k})_{k\in\mathbb{N}}$ satisfy (9), the
latter inequality implies

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+2\alpha\left([f(x^{k})+\rho
b_{k-1}]-[f(x^{k+1})+\rho b_{k}]\right),\quad\forall~{}k\in\mathbb{N}.$ (17)

On the other hand, performing a sum of (17) for $k=0,1,\ldots,N$ and using
that $x\in T$, we obtain

$\sum_{k=0}^{N}\left(\big{[}f(x^{k})+\rho
b_{k-1}\big{]}-\big{[}f(x^{k+1})+\rho b_{k}\big{]}\right)\leq
f(x^{0})-f(x)+\rho(b_{-1}-b_{N}),$ (18)

for any $N\in\mathbb{N}$. Therefore, (17) and (18) imply that
$(x^{k})_{k\in\mathbb{N}}$ is quasi-Fejér convergent to $T$. Since by
assumption $T\neq\varnothing$, it follows from Theorem 2 that
$(x^{k})_{k\in\mathbb{N}}$ is bounded. Let $\bar{x}$ be a cluster point of
$(x^{k})_{k\in\mathbb{N}}$ and $(x^{k_{j}})_{j\in\mathbb{N}}$ a subsequence of
$(x^{k})_{k\in\mathbb{N}}$ such that $\lim_{j\to+\infty}x^{k_{j}}=\bar{x}$.
Considering that $f$ is continuous, it follows from Corollary 5 that

$\inf_{k}f(x^{k})=\inf_{k}\left(f(x^{k})+\rho
b_{k-1}\right)=\lim_{j\to+\infty}\left(f(x^{k_{j}})+\rho
b_{k_{j}-1}\right)=\lim_{j\to+\infty}f(x^{k_{j}})=f(\bar{x}).$

Therefore $\bar{x}\in T$. Using again Theorem 2, we have that
$(x^{k})_{k\in\mathbb{N}}$ converges to $\bar{x}$, and the conclusion is
obtained from Theorem 6. ∎

In the following, we present an important result, when
$(x^{k})_{k\in\mathbb{N}}$ has no cluster points. This result has already
appeared in several papers studding gradient method with exact projetion, see
for example [4, 30]; however, since its proof is very simple and concise, we
include it here for the sake of completeness.

######  Lemma 9.

If $f$ is a quasiconvex function and $(x^{k})_{k\in\mathbb{N}}$ has no cluster
points then $\Omega^{*}=\varnothing$, $\lim_{k\to\infty}\|x^{k}\|=\infty$, and
$\lim_{k\to\infty}f(x^{k})=\inf\\{f(x):x\in C\\}$.

###### Proof.

Since $(x^{k})_{k\in\mathbb{N}}$ has no cluster points, then
$\lim_{k\to\infty}\|x^{k}\|=\infty$. Assume that problem (1) has an optimum,
say $\tilde{x}$, so $f(\tilde{x})\leq f(x^{k})$ for all $k$. Thus,
$\tilde{x}\in T$. Using Corollary 8, we have that $(x^{k})_{k\in\mathbb{N}}$
is convergent, contradicting that $\lim_{k\to\infty}\|x^{k}\|=\infty$.
Therefore, $\Omega^{*}=\varnothing$. Now, we claim that
$\lim_{k\to\infty}f(x^{k})=\inf\\{f(x):x\in C\\}$. If
$\lim_{k\to\infty}f(x^{k})=-\infty$, the claim holds. Let $f^{*}=\inf_{x\in
C}f(x)$. By contradiction, suppose that $\lim_{k\to\infty}f(x^{k})>f^{*}$.
Then, there exists $\tilde{x}\in C$ such that $f(\tilde{x})\leq f(x^{k})$ for
all $k$. Using Corollary 8, we obtain that $(x^{k})_{k\in\mathbb{N}}$ is
convergent, contradicting again $\lim_{k\to\infty}\|x^{k}\|=\infty$, which
conclude the proof. ∎

Finally, we presented the main convergence result when $f$ is pseudoconvex,
which is a version of [4, Corollary 3] for our algorithm, see also [29,
Proposition 5].

######  Theorem 10.

Assume that $f$ is a pseudoconvex function. Then, $\Omega^{*}\neq\varnothing$
if and only if $(x^{k})_{k\in\mathbb{N}}$ has at least one cluster point.
Moreover, $(x^{k})_{k\in\mathbb{N}}$ converges to an optimum point if
$\Omega^{*}\neq\varnothing$; otherwise, $\lim_{k\to\infty}\|x^{k}\|=\infty$
and $\lim_{k\to\infty}f(x^{k})=\inf\\{f(x):x\in C\\}$.

###### Proof.

Note that pseudoconvex functions are quasiconvex. First assume that
$\Omega^{*}\neq\varnothing$. In this case, we have also $T\neq\varnothing$.
Thus, using Corollary 8, we conclude that $(x^{k})_{k\in\mathbb{N}}$ converges
to a stationary point of problem (1) and, in particular,
$(x^{k})_{k\in\mathbb{N}}$ has a cluster point. Considering that $f$ is
pseudoconvex, this point is also an optimum point. Reciprocally, let $\bar{x}$
be a cluster point of $(x^{k})_{k\in\mathbb{N}}$ and
$(x^{k_{j}})_{j\in\mathbb{N}}$ a subsequence of $(x^{k})_{k\in\mathbb{N}}$
such that $\lim_{j\to+\infty}x^{k_{j}}=\bar{x}$. Since, by Corollary 5,
$(f(x^{k})+\rho b_{k-1})_{k\in\mathbb{N}}$ is monotone non-increasing, using
the continuity of $f$, we have

$\inf_{k}f(x^{k})=\inf_{k}\left(f(x^{k})+\rho
b_{k-1}\right)=\lim_{j\to+\infty}\left(f(x^{k_{j}})+\rho
b_{k_{j}-1}\right)=\lim_{j\to+\infty}f(x^{k_{j}})=f(\bar{x}).$

Therefore $\bar{x}\in T$. From Corollary 8, we obtain that
$(x^{k})_{k\in\mathbb{N}}$ converges to a stationary point $\tilde{x}$ of
problem (1). Thus, by (4), we have $\langle\nabla
f(\tilde{x}),x-\tilde{x}\rangle\geq 0$ for all $x\in C$, which by the pseudo-
convexity of $f$ implies $f(x)\geq f(\tilde{x})$ for all $x\in C$. Therefore,
$\bar{x}\in\Omega^{*}$ and $\Omega^{*}\neq\varnothing$. The last part of the
theorem follows by combining the first one with Lemma 9. ∎

###  3.2 Iteration-complexity bound

In this section, we establish some iteration-complexity bounds for the
sequence $(x^{k})_{k\in\mathbb{N}}$ generated by Algorithm 1. For that, we
take $x^{*}\in\Omega^{*}\neq\varnothing$, set $f^{*}=f(x^{*})$, and define the
constant

$\eta:=f(x^{0})-f^{*}+\rho b_{-1}.$

In next result, we do not assume any assumption on the convexity of the
objective function.

######  Theorem 11.

Let $\nu>0$ as in (13). Then, for all $N\in\mathbb{N}$, there holds

$\min\left\\{\|x^{k+1}-x^{k}\|:~{}\forall~{}{k\in\mathbb{N}}\right\\}\leq\frac{\sqrt{\eta/\nu}}{\sqrt{N+1}}.$
(19)

###### Proof.

It follows from (10) and (14) that $f(x^{k+1})\leq f(x^{k})+\rho
a_{k}-\nu\|x^{k+1}-x^{k}\|^{2}$, for all ${k\in\mathbb{N}}$. Hence using (9),
we have $\|x^{k+1}-x^{k}\|^{2}\leq\frac{1}{\nu}\left[\big{(}f(x^{k})+\rho
b_{k-1}\big{)}-\big{(}f(x^{k+1})+\rho b_{k}\big{)}\right]$, for all
${k\in\mathbb{N}}$. Thus, summing both sides for $k=0,1,\ldots,N$ and using
that $f^{*}\leq f(x^{k})$ for all ${k\in\mathbb{N}}$ , we obtain

$\sum_{k=0}^{N}\|x^{k+1}-x^{k}\|^{2}\leq\frac{1}{\nu}\big{[}f(x^{0})-f^{*}+\rho(b_{-1}-b_{N})\big{]}\leq\frac{1}{\nu}\big{[}f(x^{0})-f^{*}+\rho
b_{-1})\big{]}=\eta/\nu.$

Therefore,
$(N+1)\min\left\\{\|x^{k+1}-x^{k}\|^{2}:~{}k=0,1,\ldots,N\right\\}\leq\eta/\nu$,
which implies (19). ∎

In the following, we present an iteration-complexity bound for the sequence
$(x^{k})_{k\in\mathbb{N}}$, for finding $\epsilon$-stationary points of
function $f$.

######  Theorem 12.

For every $N\in\mathbb{N}$, there holds

$\min_{k=0,1,\ldots,N}\big{\langle}\nabla
f(x^{k}),x^{k}-x\big{\rangle}\leq\left[\frac{1}{2\alpha}\|x^{0}-x\|^{2}+\eta\right]\frac{1}{N+1},\qquad\forall~{}x\in
C.$

As a consequence, given $\epsilon>0$, the maximum number of iterations $N$
necessary for Algorithm 1 to generate an iterate $x^{\ell}$ such that
$\big{\langle}\nabla f(x^{\ell}),x-x^{\ell}\big{\rangle}>-\epsilon$, for all
$x\in C$, is $N\geq[\frac{1}{2\alpha}\|x^{0}-x\|^{2}+\eta]/\epsilon-1$.

###### Proof.

Using Lemma 7 and (10), we obtain

$\big{\langle}\nabla
f(x^{k}),x^{k}-x\big{\rangle}\leq\frac{1}{2\alpha}\left[\|x^{k}-x^{*}\|^{2}-\|x^{k+1}-x^{*}\|^{2}\right]+\left[\rho
a_{k}+f(x^{k})-f(x^{k+1})\right],$

for all ${k\in\mathbb{N}}$. Since $(a_{k})_{k\in\mathbb{N}}$ and
$(b_{k})_{k\in\mathbb{N}}$ satisfy (9), we conclude that

$\big{\langle}\nabla
f(x^{k}),x^{k}-x\big{\rangle}\leq\frac{1}{2\alpha}\left[\|x^{k}-x^{*}\|^{2}-\|x^{k+1}-x^{*}\|^{2}\right]+\left[\left(f(x^{k})+\rho
b_{k-1}\right)-\left(f(x^{k+1})+\rho b_{k}\right)\right].$

Thus, summing both sides for $k=0,1,\ldots,N$ and using that $f^{*}\leq
f(x^{k})$ for all ${k\in\mathbb{N}}$, we have

$\sum_{k=0}^{N}\big{\langle}\nabla
f(x^{k}),x^{k}-x\big{\rangle}\leq\frac{1}{2\alpha}\|x^{0}-x\|^{2}+\big{[}f(x^{0})-f^{*}+\rho(b_{-1}-b_{N})\big{]}=\frac{1}{2\alpha}\|x^{0}-x\|^{2}+\eta,$

which implies that $(N+1)\min\left\\{\big{\langle}\nabla
f(x^{k}),x^{k}-x\big{\rangle}:~{}k=0,1,\ldots,N\right\\}\leq\frac{1}{2\alpha}\|x^{0}-x\|^{2}+\eta,$
obtaining the first statement of the theorem. The second statement follows
trivially from the first one. ∎

####  3.2.1 Iteration-complexity bound under convexity

Next result presents an iteration-complexity bound for
$(f(x^{k}))_{k\in\mathbb{N}}$ when $f$ is a convex function. Similar bound for
unconstrained problems can be found in [40, Theorem 2.1.14].

######  Theorem 13.

Assume that $f$ is a convex function. Then, for every $N\in\mathbb{N}$, there
holds

$\min\left\\{f(x^{k})-f^{*}:~{}k=1\ldots,N\right\\}\leq\frac{\|x^{0}-x^{*}\|+2\alpha\rho
b_{-1}}{2\alpha N}.$

###### Proof.

Since $f$ is convex, we have $2\alpha\langle\nabla
f(x^{k}),x^{*}-x^{k}\rangle\leq 2\alpha\left[f(x^{*})-f(x^{k})\right]$. Thus,
using (10) and Lemma 7 with $x=x^{*}$, we obtain
$2\alpha[f(x^{k+1})-f^{*}]\leq\|x^{k}-x^{*}\|^{2}-\|x^{k+1}-x^{*}\|^{2}+2\alpha\rho
a_{k}$, for all $k\in\mathbb{N}$. Performing the sum of the this inequality
for $k=0,1,\ldots,N-1$, we have

$2\alpha\sum_{k=0}^{N-1}\left[f(x^{k+1})-f^{*}\right]\leq\|x^{0}-x^{*}\|^{2}-\|x^{N}-x^{*}\|^{2}+2\alpha\rho\sum_{k=0}^{N-1}a_{k}.$

Since $\sum_{k\in\mathbb{N}}a_{k}<b_{-1}$, we have $2\alpha
N\min\left\\{f(x^{k})-f^{*}:k=1\ldots,N\right\\}\leq\|x^{0}-x^{*}\|+2\alpha\rho
b_{-1},$ which implies the desired inequality. ∎

####  3.2.2 Iteration-complexity bound under strong convexity

Our next goal is to show an iteration-complexity bound for
$\left(f(x^{k})\right)_{k\in\mathbb{N}}$ when $f$ is strongly convex. For this
purpose, we first present an inequality that is a variation of [11, Lemma
3.6].

######  Lemma 14.

Assume that $f$ is $\mu-$strongly convex. Then, for all $k\in\mathbb{N}$,
there holds

$f(x^{k+1})-f^{*}\leq\frac{1}{\alpha}\big{\langle}x^{k}-x^{k+1},x^{k}-x^{*}\big{\rangle}-\nu\|x^{k+1}-x^{k}\|^{2}+\frac{\gamma_{1}^{k}+\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\alpha\|\nabla
f(x^{k})\|^{2}-\frac{\mu}{2}\|x^{k}-x^{*}\|^{2}.$

###### Proof.

Applying Lemma 1 with $x=x^{k}$ and $y=x^{k+1}$, and then using (3), we obtain

$\displaystyle f(x^{k+1})-f^{*}$ $\displaystyle\leq\big{\langle}\nabla
f(x^{k}),x^{k+1}-x^{k}\big{\rangle}+\frac{L}{2}\|x^{k}-x^{k+1}\|^{2}+\big{\langle}\nabla
f(x^{k}),x^{k}-x^{*}\big{\rangle}-\frac{\mu}{2}\|x^{k}-x^{*}\|^{2}.$
$\displaystyle=\big{\langle}\nabla
f(x^{k}),x^{k+1}-x^{*}\big{\rangle}+\frac{L}{2}\|x^{k}-x^{k+1}\|^{2}-\frac{\mu}{2}\|x^{k}-x^{*}\|^{2}.$
(20)

On the order hand, due to $z^{k}=x^{k}-\alpha\nabla f(x^{k})$, after some
algebraic manipulations, we have

$\big{\langle}\nabla
f(x^{k}),x^{k+1}-x^{*}\big{\rangle}=\frac{1}{\alpha}\big{\langle}x^{k}-x^{k+1},x^{k+1}-x^{*}\big{\rangle}+\frac{1}{\alpha}\big{\langle}z^{k}-x^{k+1},x^{*}-x^{k+1}\big{\rangle}.$
(21)

Since $x^{k+1}\in{\cal P}_{C}(\varphi_{\gamma^{k}},x^{k},z^{k})$, applying
item $(b)$ of Lemma 3 with $y=x^{*}$, $v=z^{k}$, $u=x^{k}$, $w=x^{k+1}$, and
$\varphi_{\gamma}=\varphi_{\gamma^{k}}$, we obtain

$\big{\langle}z^{k}-x^{k+1},x^{*}-x^{k+1}\big{\rangle}\leq\frac{\gamma_{1}^{k}+\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\|z^{k}-x^{k}\|^{2}+\frac{\gamma_{3}^{k}-\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\|x^{k+1}-x^{k}\|^{2}.$
(22)

Taking into account that $\langle x^{k}-x^{k+1},x^{k+1}-x^{*}\rangle=\langle
x^{k}-x^{k+1},x^{k}-x^{*}\rangle-\|x^{k}-x^{k+1}\|^{2}$ and
$z^{k}-x^{k}=-\alpha\nabla f(x^{k})$, the combination of (21) and (22) yields

$\big{\langle}\nabla
f(x^{k}),x^{k+1}-x^{*}\big{\rangle}\leq\frac{1}{\alpha}\big{\langle}x^{k}-x^{k+1},x^{k}-x^{*}\big{\rangle}-\frac{1}{\alpha}\left(\frac{1-\gamma_{3}^{k}-\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\right)\|x^{k+1}-x^{k}\|^{2}\\\
+\frac{\gamma_{1}^{k}+\gamma_{2}^{k}}{1-2\gamma_{2}^{k}}\alpha\|\nabla
f(x^{k})\|^{2}.$

Therefore, considering that $0\leq\gamma_{2}^{k}\leq\bar{\gamma_{2}}$ and
$0\leq\gamma_{3}^{k}\leq\bar{\gamma}$, the desired inequality follows by using
the first condition in (13) and (3.2.2). ∎

To proceed, we assume that the sequence $(x^{k})_{k\in\mathbb{N}}$ converges
to a point $x^{*}\in\Omega^{*}$. Moreover, to establish the iteration-
complexity bound for $(f(x^{k}))_{k\in\mathbb{N}}$, we also take

$\gamma_{1}^{k}=\gamma_{2}^{k}=0,\qquad\forall~{}{k\in\mathbb{N}}.$ (23)

######  Theorem 15.

Assume that $f$ is $\mu-$strongly convex on $\mathbb{R}^{n}$. Then, the
following inequality holds

$\|x^{k+1}-x^{*}\|^{2}\leq\left(1-\alpha\mu\right)\|x^{k}-x^{*}\|^{2}.$ (24)

###### Proof.

Using Lemma 14, considering (23) and $f^{*}\leq f(x^{k})$ for all
${k\in\mathbb{N}}$, we have that
$-2\big{\langle}x^{k}-x^{k+1},x^{k}-x^{*}\big{\rangle}\leq-\alpha\mu\|x^{k}-x^{*}\|^{2}-2\alpha\nu\|x^{k+1}-x^{k}\|^{2}$.
Therefore, since $1-2\alpha\nu<0$ and taking into account that
$\|x^{k+1}-x^{*}\|^{2}=\|x^{k}-x^{*}\|^{2}+\|x^{k+1}-x^{k}\|^{2}-2\big{\langle}x^{k}-x^{k+1},x^{k}-x^{*}\big{\rangle}$,
we obtain (24). ∎

######  Remark 3.

Letting $\alpha=1/L$, (24) yields
$\|x^{k+1}-x^{*}\|^{2}\leq\left(1-\mu/L\right)^{k+1}\|x^{0}-x^{*}\|^{2}$,
which is closed related to [11, Theorem 3.10]. See also [40, Theorem 2.1.15],
for the unconstrained case.

##  4 GInexPM employing Armijo’s step size rule

The aim of this section is to present the GInexPM for solving problem (1)
employing Armijo’s search. Our method is an inexact version of the projected
gradient method proposed in [28], see also [4]. Let us remind the iteration of
the projected gradient method: If the current iterate $x^{k}$ is a non-
stationary point of problem (1), then set $z^{k}=x^{k}-\alpha_{k}\nabla
f(x^{k})$, compute $w^{k}={\cal P}_{C}(z^{k})$ and define the next iterate as
$x^{k+1}=x^{k}+\tau_{k}(w^{k}-x^{k})$, where ${\cal P}_{C}$ is the exact
projection operator on $C$, $\alpha_{k}$ and $\tau_{k}$ are suitable positive
constants. In this scheme, $d^{k}=w^{k}-x^{k}$ is a feasible descent direction
for $f$ at $x^{k}$. Thus, an Armijo’s search is employed to compute $\tau_{k}$
so that it decreases the function $f$ at $x^{k+1}$. In the same way as in
Algorithm 1, we propose to compute a feasible inexact projection instead of
calculating the exact one. Hence, for guarantee that the feasible direction is
also a descent direction, we need to use
$\varphi_{\gamma}:{\mathbb{R}}^{n}\times{\mathbb{R}}^{n}\to{\mathbb{R}}_{+}$
satisfying

$\varphi_{\gamma_{3}}(u,w)\leq\gamma_{3}\|w-u\|^{2},\qquad\forall~{}u,w\in{\mathbb{R}}^{n},$

as the error tolerance function, i.e., we take $\gamma_{1}=\gamma_{2}=0$ in
Definition 2. Hence, the inexact projection ${\cal
P}_{C}(\varphi_{\gamma},u,v)$ onto $C$ of $v\in{\mathbb{R}}^{n}$ relative to
$u\in C$ with error tolerance $\varphi_{\gamma}(u,\cdot)$ becomes

${\cal P}_{C}(\varphi_{\gamma},u,v):=\left\\{w\in
C:~{}\big{\langle}v-w,y-w\big{\rangle}\leq\varphi_{\gamma_{3}}(u,w),\quad\forall~{}y\in
C\right\\}.$ (25)

Also, we assume that the mapping
$(\gamma_{3},u,w)\mapsto\varphi_{\gamma_{3}}(u,w)$ is continuous. In this
case, the gradient algorithm with inexact projection employing Armijo’s step
size rule is formally defined as follows.

Algorithm 2 GInexPM employing Armijo search

Step 0: Choose $\sigma\in(0,1)$, $\tau\in(0,1)$ and
$0<\alpha_{\min}\leq\alpha_{\max}$. Let $x^{0}\in C$ and set $k=0$.

Step 1: Choose an error tolerance function $\varphi_{\gamma}$, real numbers
$\alpha_{k}$ and $\gamma_{3}^{k}$ such that
$\alpha_{\min}\leq\alpha_{k}\leq\alpha_{\max},\qquad\qquad
0\leq\gamma_{3}^{k}\leq\bar{\gamma}<\frac{1}{2},$ (26) and take $w^{k}$ as any
feasible inexact projection of $z^{k}:=x^{k}-\alpha_{k}\nabla f(x^{k})$ onto
$C$ relative to $x^{k}$ with error tolerance
$\varphi_{\gamma_{3}^{k}}(x^{k},w^{k})$, i.e.,  $w^{k}\in{\cal
P}_{C}\left(\varphi_{\gamma_{3}^{k}},x^{k},z^{k}\right).$ (27) If
$w^{k}=x^{k}$, then stop; otherwise, set $\tau_{k}:=\tau^{j_{k}}$, where
$j_{k}:=\min\left\\{j\in\mathbb{N}:~{}f\big{(}x^{k}+\tau^{j}(w^{k}-x^{k})\big{)}\leq
f(x^{k})+\sigma\tau^{j}\big{\langle}\nabla
f(x^{k}),w^{k}-x^{k}\big{\rangle}\right\\},$ (28) and set the next iterate
$x^{k+1}$ as  $x^{k+1}=x^{k}+\tau_{k}(w^{k}-x^{k}).$ (29)

Step 2: Set $k\leftarrow k+1$, and go to Step 1.

Let us describe the main features of Algorithm 2. In Step 1, we check if
$w^{k}=x^{k}$. In this case, as we will show, the current iterate $x^{k}$ is a
solution of problem (1), otherwise, we choose $\alpha_{k}$ such that
$\alpha_{\min}\leq\alpha_{k}\leq\alpha_{\max}$. Then, by using some inner
procedure, we compute $w^{k}$ as any feasible inexact projection of
$z^{k}=x_{k}-\alpha_{k}\nabla f(x_{k})$ onto the feasible set $C$ relative to
$x^{k}$, i.e., $w^{k}\in{\cal P}_{C}(\varphi_{\gamma_{3}^{k}},x^{k},z^{k})$.
Recall that, if $\gamma_{3}^{k}=0$, then ${\cal
P}_{C}(\varphi_{0},x^{k},z^{k})$ is the exact projection, see Remark 1.
Therefore, Algorithm 2 can be seen as inexact version of the algorithm
considered in [4, 28]. In the remainder of this section, we study the
asymptotic properties and iteration-complexity bounds related to Algorithm 2.
We begin by presenting some import properties of the inexact projection (25).

######  Lemma 16.

Let $x\in C$, $\alpha>0$, and $0\leq\gamma_{3}\leq\bar{\gamma}<1/2$. Take
$w(\alpha)$ as any feasible inexact projection of $z(\alpha)=x-\alpha\nabla
f(x)$ onto $C$ relative to $x$ with error tolerance
$\varphi_{\gamma_{3}}(x,w(\alpha))$, i.e., $w(\alpha)\in{\cal
P}_{C}(\varphi_{\gamma_{3}},x,z(\alpha))$. Then, there hold:

  * (i)

$\big{\langle}\nabla
f(x),w(\alpha)-x\big{\rangle}\leq\left(\dfrac{\gamma_{3}-1}{\alpha}\right)\|w(\alpha)-x\|^{2}$;

  * (ii)

the point $x$ is stationary for problem (1) if and only if $x\in{\cal
P}_{C}(\varphi_{\gamma_{3}},x,z(\alpha))$;

  * (iii)

if $x$ is a nonstationary point for problem (1), then $\big{\langle}\nabla
f(x),w(\alpha)-x\big{\rangle}<0$. Equivalently, if there exists
${\bar{\alpha}}>0$ such that $\big{\langle}\nabla
f(x),w({\bar{\alpha}})-x\big{\rangle}\geq 0$, then $x$ is stationary for
problem (1).

###### Proof.

Since $w(\alpha)\in{\cal P}_{C}(\varphi_{\gamma_{3}},x,z(\alpha))$, applying
item $(b)$ of Lemma 3 with $\gamma_{1}=\gamma_{2}=0$, $w=w(\alpha)$,
$v=z(\alpha)$, $y=x$, and $u=x$, we obtain $\big{\langle}x-\alpha\nabla
f(x)-w(\alpha),x-w(\alpha)\big{\rangle}\leq\gamma_{3}\|w(\alpha)-x\|^{2}$
which, after some algebraic manipulations, yields the inequality of item
$(i)$. For proving item $(ii)$, we first assume that $x$ is stationary for
problem (1). In this case, (4) implies that $\big{\langle}\nabla
f(x),w(\alpha)-x\big{\rangle}\geq 0$. Thus, considering that $\alpha>0$ and
$0\leq\gamma_{3}\leq\bar{\gamma}<1/2$, the last inequality together item $(i)$
implies that $w(\alpha)=x$. Therefore, $x\in{\cal
P}_{C}(\varphi_{\gamma_{3}},x,z(\alpha))$. Reciprocally, if $x\in{\cal
P}_{C}(\varphi_{\gamma_{3}},x,z(\alpha))$ then applying item $(b)$ of Lemma
(3) with $\gamma_{1}=\gamma_{2}=0$, $w=x$, $v=z(\alpha)$, and $u=x$, we obtain
$\big{\langle}x-\alpha\nabla f(x)-x,y-x\big{\rangle}\leq 0$, for all $y\in C$.
Considering that $\alpha>0$, the last inequality is equivalently to
$\big{\langle}\nabla f(x),y-x\big{\rangle}\geq 0$, for all $y\in C$. Thus,
according to (4), we conclude that $x$ is stationary point for problem (1).
Finally, for prove item $(iii)$, take $x$ a nonstationary point for problem
(1). Thus item $(ii)$ implies that $x\notin{\cal
P}_{C}(\varphi_{\gamma_{3}},x,z(\alpha))$ and taking into account that
$w(\alpha)\in{\cal P}_{C}(\varphi_{\gamma_{3}},x,z(\alpha))$, we conclude that
$x\neq w(\alpha)$. Therefore, due to $\alpha>0$ and
$0<\gamma_{3}\leq\bar{\gamma}$, it follows from item $(i)$ that
$\big{\langle}\nabla f(x),w(\alpha)-x\big{\rangle}<0$ and the first sentence
is proved. Finally, note that the second statement is the contrapositive of
the first sentence. ∎

The next result follows from item $(iii)$ of Lemma 16 and its proof will be
omitted.

######  Proposition 17.

Let $\sigma\in(0,1)$, $x\in C$, $\alpha>0$, and
$0\leq\lambda<{\bar{\lambda}}$. Take $w(\alpha)$ as any feasible inexact
projection of $z(\alpha)=x-\alpha\nabla f(x)$ onto $C$ relative to $x$ with
error tolerance $\varphi_{\lambda}(x,w(\alpha))$, i.e., $w(\alpha)\in{\cal
P}_{C}(\varphi_{\lambda},x,z(\alpha))$. If $x$ is a nonstationary point for
problem (1), then there exists $\delta>0$ such that
$f\big{(}x+\zeta[w(\alpha)-x]\big{)}<f(x)+\sigma\zeta\big{\langle}\nabla
f(x),w(\alpha)-x\big{\rangle}$, for all $\zeta\in(0,\delta)$.

In the following, we establish the well definition of Algorithm 2.

######  Proposition 18.

The sequence $(x^{k})_{k\in\mathbb{N}}$ generated by Algorithm 2 is well
defined and belongs to $C$.

###### Proof.

Proceeding by induction, let $x^{0}\in C$,
$\alpha_{\min}\leq\alpha_{0}\leq\alpha_{\max}$ and
$0\leq\gamma_{3}^{0}<\bar{\gamma}$. Set $z^{0}=x^{0}-\alpha_{0}\nabla
f(x^{0})$. Since $C$ is closed and convex, it follows from Remark 1 that
${\cal P}_{C}(\varphi_{\gamma_{3}^{0}},x^{0},z^{0})\neq\varnothing$. Thus, we
can take $w^{0}\in P_{C}(\varphi_{\gamma_{3}^{k}},x^{0},z^{0})$. If Algorithm
2 does not stop, i.e., $w^{0}\neq x^{0}$, then it follows from item $(i)$ of
Lemma 16 that $\langle\nabla f(x^{0}),w^{0}-x^{0}\rangle<0$. In this case,
Propoposition 17 implies that it is possible to compute $\tau_{0}\in(0,1]$
satisfying (28), for $k=0$. Therefore, $x^{1}=x^{0}+\tau_{0}(w^{0}-x^{0})$ in
(29) is well defined and, considering that $x^{0},w^{0}\in C$ and
$\tau_{0}\in(0,1]$, we have $x^{1}\in C$. The induction step is completely
analogous, implying that $(x^{k})_{k\in\mathbb{N}}$ is well defined and
belongs to $C$. ∎

###  4.1 Asymptotic convergence analysis

The aim of this section is to study asymptotic convergence properties related
to Algorithm 2. We begin by presenting a partial convergence result of the
sequence $(x^{k})_{k\in\mathbb{N}}$ generated by Algorithm 2.

######  Proposition 19.

Algorithm 2 finishes in a finite number of iterations at a stationary point of
problem (1), or generates an infinite sequence $(x^{k})_{k\in\mathbb{N}}$ for
which $\left(f(x^{k})\right)_{k\in\mathbb{N}}$ is a decreasing sequence and
every cluster point of $(x^{k})_{k\in\mathbb{N}}$ is stationary for problem
(1).

###### Proof.

First we assume that $(x^{k})_{k\in\mathbb{N}}$ is finite. In this case,
according to Step 1, there exists $k\in\mathbb{N}$ such that
$x^{k}=w^{k}\in{\cal P}_{C}(\varphi_{\gamma_{3}^{k}},x^{k},z^{k})$, where
$z^{k}=x^{k}-\alpha_{k}\nabla f(x^{k})$, $0\leq\gamma_{3}^{k}\leq\bar{\gamma}$
and $\alpha_{k}>0$. Therefore, applying the second statement of item $(ii)$ of
Lemma 16 with $x=x^{k}$, $\alpha=\alpha_{k}$, and $\gamma_{3}=\gamma_{3}^{k}$,
we conclude that $x^{k}$ is stationary for problem (1). Now, we assume that
$(x^{k})_{k\in\mathbb{N}}$ is infinite. Thus, according to Step 1, $x^{k}\neq
w^{k}$ for all $k=0,1,\ldots$. Consequently, applying item $(ii)$ of Lemma 16
with $x=x^{k}$, $\alpha=\alpha_{k}$, and $\gamma_{3}=\gamma_{3}^{k}$, we have
that $x^{k}$ is nonstationary for problem (1). Hence, item $(iii)$ of Lemma 16
implies that $\big{\langle}\nabla f(x^{k}),w^{k}-x^{k}\big{\rangle}<0$, for
all $k=0,1,\ldots$. Therefore, it follows from (28) and (29) that

$0<-\sigma\tau_{k}\big{\langle}\nabla f(x^{k}),w^{k}-x^{k}\big{\rangle}\leq
f(x^{k})-f(x^{k+1}),\qquad\forall~{}k\in\mathbb{N},$ (30)

with implies that $f(x^{k+1})<f(x^{k})$, for all $k=0,1,\ldots$, and then
$\left(f(x^{k})\right)_{k\in\mathbb{N}}$ is a decreasing sequence. Let
${\bar{x}}$ be a cluster point of $(x^{k})_{k\in\mathbb{N}}$ and
$(x^{k_{j}})_{j\in\mathbb{N}}$ a subsequence of $(x^{k})_{k\in\mathbb{N}}$
such that $\lim_{j\to+\infty}x^{k_{j}}=\bar{x}$. Since $C$ is closed, by
Proposition 18, we have $\bar{x}\in C$. Since
$\left(f(x^{k})\right)_{k\in\mathbb{N}}$ is decreasing and
$\lim_{j\to+\infty}f(x^{k_{j}})=f(\bar{x})$, we conclude that
$\lim_{k\to+\infty}f(x^{k})=f(\bar{x})$. On the order hand, using the last
condition in (26), we have $1/(1-2\gamma_{3}^{k})<1/(1-2\bar{\gamma})$, for
all $k=0,1,\ldots$. Since $w^{k}\in{\cal
P}_{C}(\varphi_{\gamma_{3}^{k}},x^{k},z^{k})$, where
$z^{k}=x^{k}-\alpha_{k}\nabla f(x^{k})$, applying item $(a)$ of Lemma 3 with
$x=x^{k}$, $u=x^{k}$, $v=z^{k}$, $w=w^{k}$, $\gamma_{1}=\gamma_{2}=0$, and
$\gamma_{3}=\gamma_{3}^{k}$, we obtain

$\|w^{k_{j}}-x^{k_{j}}\|^{2}\leq\frac{\alpha_{k_{j}}^{2}}{1-2\gamma_{3}^{k_{j}}}\|\nabla
f(x^{k_{j}})\|^{2}<\frac{\alpha_{\max}^{2}}{1-2\bar{\gamma}}\|\nabla
f(x^{k_{j}})\|^{2},\qquad\forall~{}j\in\mathbb{N}.$

Considering that $(x^{k_{j}})_{j\in\mathbb{N}}$ converges to ${\bar{x}}$ and
$\nabla f$ is continuous, the last inequality implies that
$(w^{k_{j}})_{j\in\mathbb{N}}\subset C$ is also bounded. Thus, we can assume
without loss of generality that $\lim_{j\to+\infty}w^{k_{j}}=\bar{w}\in C$.
Now, due to $\tau_{k}\in(0,1]$, for all $k=0,1,\ldots$, we can also assume
without loss of generality that
$\lim_{j\to+\infty}\tau_{k_{j}}=\bar{\tau}\in[0,1].$ Therefore, owing to
$\lim_{j\to+\infty}f(x^{k})=f(\bar{x})$, taking limits in (30) along an
appropriate subsequence, we obtain $\bar{\tau}\big{\langle}\nabla
f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}=0.$ We have two possibilities:
$\bar{\tau}>0$ or $\bar{\tau}=0$. If $\bar{\tau}>0$, then $\big{\langle}\nabla
f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}=0.$ Now, we assume that
$\lim_{j\to+\infty}\tau_{k_{j}}=\bar{\tau}=0$. In this case, for any fixed
$q\in\mathbb{N}$, there exits $j$ such that $\tau_{k_{j}}<\tau^{q}$. Hence,
Armijo’s condition (28) does not hold for $\tau^{q}$, i.e.,
$f\big{(}x^{k_{j}}+\tau^{q}(w^{k_{j}}-x^{k_{j}})\big{)}>f(x^{k_{j}})+\sigma\tau^{q}\big{\langle}\nabla
f(x^{k_{j}}),w^{k_{j}}-x^{k_{j}}\big{\rangle}$, for all $j\in\mathbb{N}.$
Thus, taking limits as $j$ goes to $+\infty$, we obtain
$f\big{(}\bar{x}+\tau^{q}(\bar{w}-\bar{x})\big{)}\geq
f(\bar{x})+\sigma\tau^{q}\big{\langle}\nabla
f(\bar{x}),\bar{w}-\bar{x}\big{\rangle},$ which is equivalent to

$\frac{f\big{(}\bar{x}+\tau^{q}(\bar{w}-\bar{x})\big{)}-f(\bar{x})}{\tau^{q}}\geq\sigma\big{\langle}\nabla
f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}.$

Since this inequality holds for all $q\in\mathbb{N}$, taking limits as $q$
goes to $+\infty$, we conclude that $\langle\nabla
f(\bar{x}),\bar{w}-\bar{x}\rangle\geq\sigma\big{\langle}\nabla
f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}$. Hence, due to $\sigma\in(0,1)$, we
obtain $\big{\langle}\nabla f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}\geq 0$. We
recall that $\langle\nabla f(x^{k_{j}}),w^{k_{j}}-x^{k_{j}}\rangle<0$, for all
$j=0,1,\ldots$, which taking limits as $j$ goes to $+\infty$ yields
$\big{\langle}\nabla f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}\leq 0$. Hence,
$\big{\langle}\nabla f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}=0$. Therefore,
for any of two possibilities, $\bar{\tau}>0$ or $\bar{\tau}=0$, we have
$\langle\nabla f(\bar{x}),\bar{w}-\bar{x}\rangle=0$. On the other hand,

$w^{k_{j}}\in{\cal P}_{C}(\varphi_{\gamma_{3}^{k_{j}}},x^{k_{j}},z^{k_{j}}),$

where $z^{k_{j}}=x^{k_{j}}-\alpha_{k_{j}}\nabla f(x^{k_{j}})$,
$0\leq\gamma_{3}^{k_{j}}\leq\bar{\gamma}$, and $\alpha_{k_{j}}>0$. Thus, it
follows from (25) that

$\big{\langle}z^{k_{j}}-w^{k_{j}},y-w^{k_{j}}\big{\rangle}\leq\varphi_{\gamma_{3}^{k_{j}}}(x^{k_{j}},w^{k_{j}}),\qquad
y\in C,\quad\forall~{}j\in\mathbb{N}.$ (31)

Moreover, since $\alpha_{k}\in[\alpha_{\min},\alpha_{\max}]$, for all
$k=0,1,\ldots$, we also assume without loss of generality that
$\lim_{j\to+\infty}\alpha_{k_{j}}=\bar{\alpha}\in[\alpha_{\min},\alpha_{\max}]$.
Thus, taking limits in (31) and considering that the mapping
$(\gamma_{3},u,w)\mapsto\varphi_{\gamma_{3}}(u,w)$ is continuous,
$\lim_{j\to+\infty}x^{k_{j}}=\bar{x}\in C$,
$\lim_{j\to+\infty}w^{k_{j}}=\bar{w}\in C$, and
$\lim_{j\to+\infty}\tau_{k_{j}}=\bar{\tau}\in[0,1]$, we conclude that
$\big{\langle}\bar{z}-\bar{w},y-\bar{w}\big{\rangle}\leq\varphi_{\bar{\gamma}}(\bar{x},\bar{w})$,
for all $y\in C$, where $\bar{z}=\bar{x}-{\bar{\alpha}}\nabla f(\bar{x})$.
Hence, it follows from (25) that $\bar{w}\in{\cal
P}_{C}\left(\varphi_{\bar{\gamma}},{\bar{x}},{\bar{z}}\right)$, where
$\bar{z}=\bar{x}-{\bar{\alpha}}\nabla f(\bar{x})$. Therefore, due to
$\big{\langle}\nabla f(\bar{x}),\bar{w}-\bar{x}\big{\rangle}=0$, we can apply
the second sentence in item $(iii)$ of Lemma 16 with $x=\bar{x}$,
$z({\bar{\alpha}})=\bar{z}$, and $w({\bar{\alpha}})=\bar{w}$ to conclude that
$\bar{x}$ is stationary for problem (1). ∎

Due to Proposition 19, from now on we assume that the sequence
$(x^{k})_{k\in\mathbb{N}}$ generated by Algorithm 2 is infinite. The following
result establishes a basic inequality satisfied by the iterates of Algorithm
2, which will be used to study its convergence properties. For simplify the
notations we define the following constant:

$\xi:=\dfrac{2\alpha_{\max}}{\sigma}>0.$ (32)

######  Lemma 20.

For each $x\in C$, there holds

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+2\alpha_{k}\tau_{k}\big{\langle}\nabla
f(x^{k}),x-x^{k}\big{\rangle}+\xi\left[f(x^{k})-f(x^{k+1})\right],\quad\forall~{}k\in\mathbb{N}.$
(33)

###### Proof.

We know that
$\|x^{k+1}-x\|^{2}=\|x^{k}-x\|^{2}+\|x^{k+1}-x^{k}\|^{2}-2\big{\langle}x^{k+1}-x^{k},x-x^{k}\big{\rangle}$,
for all $x\in C$ and $k=0,1,\ldots$. Thus, using (29), we have

$\|x^{k+1}-x\|^{2}=\|x^{k}-x\|^{2}+\tau_{k}^{2}\|w^{k}-x^{k}\|^{2}-2\tau_{k}\big{\langle}w^{k}-x^{k},x-x^{k}\big{\rangle},\qquad\forall~{}k\in\mathbb{N}.$
(34)

On the other hand, by using (27) we have $w^{k}\in{\cal
P}_{C}(\varphi_{\gamma_{3}^{k}},x^{k},z^{k})$ with
$z^{k}=x^{k}-\alpha_{k}\nabla f(x^{k})$. Thus, applying item $(b)$ of Lemma 3
with $y=x$, $u=x^{k}$, $v=z^{k}$, $w=w^{k}$, $\gamma_{1}=\gamma_{2}=0$,
$\gamma_{3}=\gamma_{3}^{k}$, and
$\varphi_{\gamma_{3}}=\varphi_{\gamma_{3}^{k}}$, we obtain $\langle
x^{k}-\alpha_{k}\nabla
f(x^{k})-w^{k},x-w^{k}\rangle\leq\gamma_{3}^{k}\|w^{k}-x^{k}\|^{2}$, for all
$k\in\mathbb{N}$. After some algebraic manipulations in the last inequality,
we have

$\big{\langle}w^{k}-x^{k},x-x^{k}\big{\rangle}\geq\alpha_{k}\big{\langle}\nabla
f(x^{k}),w^{k}-x\big{\rangle}+(1-\gamma_{3}^{k})\|w^{k}-x^{k}\|^{2}.$

Combining the last inequality with (34), we conclude

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}-\tau_{k}\big{[}2(1-\gamma_{3}^{k})-\tau_{k}\big{]}\|w^{k}-x^{k}\|^{2}+2\tau_{k}\alpha_{k}\big{\langle}\nabla
f(x^{k}),x-w^{k}\big{\rangle}.$ (35)

Since $0\leq\gamma_{3}^{k}<\bar{\gamma}<1/2$ and $\tau_{k}\in(0,1]$, we have
$2(1-\gamma_{3}^{k})-\tau_{k}\geq 1-2\bar{\gamma}>0$. Thus, (35) becomes

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+2\tau_{k}\alpha_{k}\big{\langle}\nabla
f(x^{k}),x-w^{k}\big{\rangle},\qquad\forall~{}k\in\mathbb{N}.$

Therefore, considering that $\big{\langle}\nabla
f(x^{k}),x-w^{k}\big{\rangle}=\big{\langle}\nabla
f(x^{k}),x-x^{k}\big{\rangle}+\big{\langle}\nabla
f(x^{k}),x^{k}-w^{k}\big{\rangle}$ and taking into account (28), we conclude
that

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+2\tau_{k}\alpha_{k}\big{\langle}\nabla
f(x^{k}),x-x^{k}\big{\rangle}+\frac{2\alpha_{k}}{\sigma}\left[f(x^{k})-f(x^{k+1})\right],\qquad\forall~{}k\in\mathbb{N}.$
(36)

Since $0<\alpha_{k}\leq\alpha_{\max}$, Proposition 19 implies
$\alpha_{k}\big{[}f(x^{k})-f(x^{k+1})\big{]}<\alpha_{\max}\big{[}f(x^{k})-f(x^{k+1})\big{]}$.
Therefore, the desired inequality (33) follows from (36) by using (32). ∎

For the sequence $(x^{k})_{k\in\mathbb{N}}$ generated by Algorithm 2, we
define the following auxiliary set:

$U:=\left\\{x\in C:f(x)\leq\inf_{k}f(x^{k}),\quad{k\in\mathbb{N}}\right\\}.$

Next, we analyze the behavior of the sequence $(x^{k})_{k\in\mathbb{N}}$ when
$f$ is a quasiconvex function.

######  Corollary 21.

Assume that $f$ is a quasiconvex function. If $U\neq\varnothing$, then
$(x^{k})_{k\in\mathbb{N}}$ converges to a stationary point of problem (1).

###### Proof.

Let $x\in U$. Thus, $f(x)\leq f(x^{k})$ for all $k\in\mathbb{N}$. Since $f$ is
quasiconvex, we have $\big{\langle}\nabla f(x^{k}),x-x^{k}\big{\rangle}\leq
0$, for all $k\in\mathbb{N}$. Using Lemma 20, we obtain

$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+\xi\left[f(x^{k})-f(x^{k+1})\right],\quad\forall~{}k\in\mathbb{N}.$

Defining $\epsilon_{k}=\xi\big{[}f(x^{k})-f(x^{k+1})\big{]}$, we have
$\|x^{k+1}-x\|^{2}\leq\|x^{k}-x\|^{2}+\epsilon_{k}$, for all $k\in\mathbb{N}$.
On the other hand, summing $\epsilon_{k}$ with $k=0,1,\ldots,N$, we have
$\sum_{k=0}^{N}\epsilon_{k}\leq\xi\big{[}f(x^{0})-f(x)\big{]}<\infty$. Thus,
it follows from Definition 1 that $(x^{k})_{k\in\mathbb{N}}$ is quasi-Fejér
convergent to $U$. Since $U$ is nonempty, it follows from Theorem 2 that
$(x^{k})_{k\in\mathbb{N}}$ is bounded, and therefore it has a cluster point.
Let $\bar{x}$ be a cluster point of $(x^{k})_{k\in\mathbb{N}}$ and
$(x^{k_{j}})_{j\in\mathbb{N}}$ be a subsequence of $(x^{k})_{k\in\mathbb{N}}$
such that $\lim_{j\to\infty}x^{k_{j}}=\bar{x}$. Considering that $f$ is
continuous, we have $\lim_{j\to\infty}f(x^{k_{j}})=f(\bar{x})$. Hence, since,
by Proposition 19, $\left(f(x^{k})\right)_{k\in\mathbb{N}}$ is decreasing, we
obtain
$\inf\\{f(x^{k}):k=0,1,2,\ldots\\}=\lim_{k\to\infty}f(x^{k})=f(\bar{x}).$
Therefore, $\bar{x}\in U$. It follows from Theorem 2 that
$(x^{k})_{k\in\mathbb{N}}$ converges to $\bar{x}$ and the conclusion is
obtained by using again Proposition 19. ∎

The next two results are similar to Lemma 9 and Theorem 10, respectively. For
completeness reasons, we have included their proofs here.

######  Lemma 22.

If $f$ is a quasiconvex function and $(x^{k})_{k\in\mathbb{N}}$ has no cluster
points, then $\Omega^{*}=\varnothing$, $\lim_{k\to\infty}\|x^{k}\|=\infty$,
and $\lim_{k\to\infty}f(x^{k})=\inf\\{f(x):x\in C\\}$.

###### Proof.

Since $(x^{k})_{k\in\mathbb{N}}$ has no cluster points, then
$\lim_{k\to\infty}\|x^{k}\|=\infty$. Assume that problem (1) has an optimum,
say $\tilde{x}$, so $f(\tilde{x})\leq f(x^{k})$ for all $k$. Thus,
$\tilde{x}\in U$. Using Corollary 21, we obtain that
$(x^{k})_{k\in\mathbb{N}}$ is convergent, contradicting that
$\lim_{k\to\infty}\|x^{k}\|=\infty$. Therefore, $\Omega^{*}=\varnothing$. Now,
we claim that $\lim_{k\to\infty}f(x^{k})=\inf\\{f(x):x\in C\\}$. If
$\lim_{k\to\infty}f(x^{k})=-\infty$, the claim holds. Let $f^{*}=\inf_{x\in
C}f(x)$. By contradiction, suppose that $\lim_{k\to\infty}f(x^{k})>f^{*}$.
Then, there exists $\tilde{x}\in C$ such that $f(\tilde{x})\leq f(x^{k})$ for
all $k$. Using Corollary 21, we have that $(x^{k})_{k\in\mathbb{N}}$ is
convergent, contradicting again $\lim_{k\to\infty}\|x^{k}\|=\infty$, which
concludes the proof. ∎

######  Theorem 23.

Assume that $f$ is a pseudoconvex function. Then, $\Omega^{*}\neq\varnothing$
if and only if $(x^{k})_{k\in\mathbb{N}}$ has at least one cluster point.
Moreover, $(x^{k})_{k\in\mathbb{N}}$ converges to an optimum point if
$\Omega^{*}\neq\varnothing$; otherwise, $\lim_{k\to\infty}\|x^{k}\|=\infty$
and $\lim_{k\to\infty}f(x^{k})=\inf\\{f(x):x\in C\\}$.

###### Proof.

Recall that pseudoconvex functions are also quasiconvex. Assume that
$\Omega^{*}\neq\varnothing$. In this case, $U\neq\varnothing$. Using Corollary
21, we conclude that $(x^{k})_{k\in\mathbb{N}}$ converges to a stationary
point of problem (1). Reciprocally, let $\bar{x}$ be a cluster point of
$(x^{k})_{k\in\mathbb{N}}$ and $(x^{k_{j}})_{j\in\mathbb{N}}$ be a subsequence
of $(x^{k})_{k\in\mathbb{N}}$ such that $\lim_{j\to+\infty}x^{k_{j}}=\bar{x}$.
Since, from Proposition 19, $(f(x^{k}))_{k\in\mathbb{N}}$ is monotone non-
increasing, by continuity of $f$, we conclude that
$\inf_{k}f(x^{k})=f(\bar{x})$ and hence $\bar{x}\in U$. Using Corollary 21, we
obtain that $(x^{k})_{k\in\mathbb{N}}$ converges to a stationary point
$\tilde{x}$ of problem (1). Since $f$ is pseudoconvex, this point is also an
optimal solution of problem (1). The last part of the theorem follows by
combining the first one with Lemma 22. ∎

###  4.2 Iteration-complexity bound

This section is devoted to study iteration-complexity bounds for the sequence
generated by Algorithm 2, similar results in the multiobjetive context can be
found in [19]. For that we assume that $f^{*}>-\infty$ and the objective
function $f$ has Lipschitz continuous gradient with constant $L\geq 0$, i.e.,
we assume that $\nabla f$ satisfies (2). Moreover, we also assume that
$(x^{k})_{k\in\mathbb{N}}$ generated by Algorithm 1 converges to a point
$x^{*}$, i.e, $\lim_{k\to\infty}x^{k}=x^{*}$. To simplify the notations, we
set

$\tau_{\min}:=\min\left\\{\frac{2\tau(1-\sigma)(1-\bar{\gamma})}{\alpha_{\max}L},~{}1\right\\}.$
(37)

The next lemma is a version of [19, Lemma 3.1] for our specific context.

######  Lemma 24.

The step size $\tau_{k}$ in Algorithm 2 satisfies $\tau_{k}\geq\tau_{\min}$.

###### Proof.

If $\tau_{k}=1$, then the result trivially holds. Thus, assume that
$\tau_{k}<1$. It follows from Armijo’s condition in (28) that
$f(x^{k}+\frac{\tau_{k}}{\tau}(w^{k}-x^{k}))>f(x^{k})+\sigma\frac{\tau_{k}}{\tau}\big{\langle}\nabla
f(x^{k}),w^{k}-x^{k}\big{\rangle}$. Now, using Lemma 1, we have
$f\left(x^{k}+\frac{\tau_{k}}{\tau}(w^{k}-x^{k})\right)\leq
f(x^{k})+\frac{\tau_{k}}{\tau}\big{\langle}\nabla
f(x^{k}),w^{k}-x^{k}\big{\rangle}+\frac{1}{\tau^{2}}\frac{L}{2}\tau_{k}^{2}\|w^{k}-x^{k}\|^{2}$.
Hence, combining the two previous inequalities, we obtain

$\tau(1-\sigma)\big{\langle}\nabla
f(x^{k}),w^{k}-x^{k}\big{\rangle}+\frac{L}{2}\tau_{k}\|w^{k}-x^{k}\|^{2}>0.$
(38)

On the order hand, since $w^{k}\in{\cal
P}_{C}(\varphi_{\gamma_{3}^{k}},x^{k},z^{k})$, where
$z^{k}=x^{k}-\alpha_{k}\nabla f(x^{k})$, applying item $(i)$ of Lemma 16 with
$x=x^{k}$, $w(\alpha)=w^{k}$, $z=z^{k}$, $\gamma_{1}=\gamma_{2}=0$,
$\gamma_{3}=\gamma_{3}^{k}$, and $\varphi_{\gamma}=\varphi_{\gamma^{k}}$, we
have

$\big{\langle}\nabla
f(x^{k}),w^{k}-x^{k}\big{\rangle}\leq\left(\frac{\gamma_{3}^{k}-1}{\alpha_{k}}\right)\|w^{k}-x^{k}\|^{2}.$

Combining the last inequality with (38) yields
$\left[{\tau(1-\sigma)(\gamma_{3}^{k}-1)}/{\alpha_{k}}+{L}\tau_{k}/2\right]\|w^{k}-x^{k}\|^{2}>0.$
Hence, using (26), it follows that

$\tau_{k}>\frac{2\tau(1-\sigma)(1-\gamma_{3}^{k})}{\alpha_{k}L}\geq\frac{2\tau(1-\sigma)(1-\bar{\gamma})}{\alpha_{\max}L}.$

Therefore, since $\tau_{k}$ is never larger than one, the result follows and
the proof is concluded. ∎

It follows from item $(ii)$ of Lemma 16 that if $x^{k}\in{\cal
P}_{C}(\varphi_{\gamma_{3}},x^{k},z^{k})$, then the point $x^{k}$ is
stationary for problem (1). Since $w^{k}\in{\cal
P}_{C}(\varphi_{\gamma_{3}},x^{k},z^{k})$, the quantity $\|w^{k}-x^{k}\|$ can
be seen as a measure of stationarity of $x^{k}$. Next theorem presents an
iteration-complexity bound for this quantity, see a similar result in [19,
Theorem 3.1].

######  Theorem 25.

Let $\tau_{\min}$ be defined in (37). Then, for every $N\in\mathbb{N}$, the
following inequality holds

$\min\left\\{\|w^{k}-x^{k}\|:~{}k=0,1\ldots,N-1\right\\}\leq\sqrt{\frac{\alpha_{\max}\left[f(x^{0})-f^{*}\right]}{\sigma\tau_{\min}{\left(1-\bar{\gamma}\right)}}}\frac{1}{\sqrt{N}}.$

###### Proof.

From the definition of $\tau_{k}$ and condition (28), we have

$f(x^{k+1})-f(x^{k})\leq\sigma\tau_{k}\big{\langle}\nabla
f(x^{k}),w^{k}-x^{k}\big{\rangle}.$ (39)

Since $w^{k}\in{\cal P}_{C}(\varphi_{\gamma_{3}^{k}},x^{k},z^{k})$, where
$z^{k}=x^{k}-\alpha_{k}\nabla f(x^{k})$, applying item $(i)$ of Lemma 16 with
$x=x^{k}$, $w(\alpha)=w^{k}$, $z=z^{k}$, $\gamma_{1}=\gamma_{2}=0$,
$\gamma_{3}=\gamma_{3}^{k}$, and $\varphi_{\gamma}=\varphi_{\gamma^{k}}$, we
obtain

$\big{\langle}\nabla
f(x^{k}),w^{k}-x^{k}\big{\rangle}\leq\left(\frac{\gamma_{3}^{k}-1}{\alpha_{k}}\right)\|w^{k}-x^{k}\|^{2}.$
(40)

By (26), we have
$(1-\gamma_{3}^{k})/\alpha_{k}\geq(1-\bar{\gamma})/\alpha_{\max}$. Thus,
combining (39) with (40) and taking into account Lemma 24, it follows that

$f(x^{k})-f(x^{k+1})\geq\sigma\tau_{k}\left(\frac{1-\bar{\gamma}}{\alpha_{\max}}\right)\|w^{k}-x^{k}\|^{2}\geq\sigma\tau_{\min}\left(\frac{1-\bar{\gamma}}{\alpha_{\max}}\right)\|w^{k}-x^{k}\|^{2}.$

Hence, performing the sum of the above inequality for $k=0,1,\ldots,N-1$, we
have

$\sum_{k=0}^{N-1}\|w^{k}-x^{k}\|^{2}\leq\frac{\alpha_{\max}\left[f(x^{0})-f(x^{N})\right]}{\sigma\tau_{\min}(1-\bar{\gamma})}\leq\frac{\alpha_{\max}\left[f(x^{0})-f^{*}\right]}{\sigma\tau_{\min}(1-\bar{\gamma})},$

which implies the desired inequality. ∎

####  4.2.1 Iteration-complexity bound under convexity

In this section, we present an iteration-complexity bound for the sequence
$\left(f(x^{k})\right)_{k\in\mathbb{N}}$ when $f$ is convex.

######  Theorem 26.

Let $f$ be a convex function on $C$. Then, for every $N\in\mathbb{N}$, there
holds

$\min\left\\{f(x^{k})-f^{*}:~{}k=0,1\ldots,N-1\right\\}\leq\frac{\|x^{0}-x^{*}\|+\xi\left[f(x^{0})-f^{*}\right]}{2\alpha_{\min}\tau_{\min}}\frac{1}{N}.$

###### Proof.

Using the first inequality in (26) and Lemma 24, we have
$2\alpha_{\min}\tau_{\min}\leq 2\alpha_{k}\tau_{k}$, for all
$k\in{\mathbb{N}}$. From the convexity of $f$, we have $\big{\langle}\nabla
f(x^{k}),x^{*}-x^{k}\big{\rangle}\leq f^{*}-f(x^{k})$, for all
$k\in{\mathbb{N}}$. Thus, applying Lemma 20 with $x=x^{*}$, after some
algebraic manipulations, we conclude

$2\alpha_{\min}\tau_{\min}\left[f(x^{k})-f^{*}\right]\leq\|x^{k}-x^{*}\|^{2}-\|x^{k+1}-x^{*}\|^{2}+\xi\left[f(x^{k})-f(x^{k+1})\right]\quad
k=0,1,\ldots.$

Hence, performing the sum of the above inequality for $k=0,1,\ldots,N-1$, we
obtain

$2\alpha_{\min}\tau_{\min}\sum_{k=0}^{N-1}\left[f(x^{k})-f^{*}\right]\leq\|x^{0}-x^{*}\|^{2}-\|x^{N}-x^{*}\|^{2}+\xi\left[f(x^{0})-f(x^{N})\right].$

Therefore,
$2\alpha_{\min}\tau_{\min}N\min\\{f(x^{k})-f^{*}:k=0,1\ldots,N-1\\}\leq\|x^{0}-x^{*}\|+\xi\left[f(x^{0})-f(x^{N})\right]$,
which implies the desired inequality. ∎

##  5 Numerical experiments

In this section, we summing up the results of our preliminary numerical
experiments in order to verify the practical behavior of the proposed
algorithms. In particular, we will illustrate the potential advantages of
considering inexact projections instead of exact ones in a problem of least
squares over the spectrahedron. The codes are written in Matlab and are freely
available at https://orizon.ime.ufg.br. All experiments were run on a macOS
10.15.7 with 3.7GHz Intel Core i5 processor and 8GB of RAM.

Let $\mathbb{S}^{n}$ be the space of $n\times n$ symmetric real matrices and
$\mathbb{S}^{n}_{+}$ be the cone of positive semidefinite matrices in
$\mathbb{S}^{n}$. Given $A$ and $B$ two $n\times m$ matrices, with $m\geq n$,
we consider the following problem:

$\begin{array}[]{cl}\displaystyle\min_{X\in\mathbb{S}^{n}}&f(X):=\displaystyle\frac{1}{2}\|AX-B\|^{2}_{F}\\\
\mbox{s.t.}&\textrm{tr}(X)=1,\\\ &X\in\mathbb{S}^{n}_{+},\\\ \end{array}$ (41)

where $X$ is the $n\times n$ matrix that we seek to find. Here,
$\|\cdot\|_{F}$ denotes the Frobenius matrix norm $\|A\|_{F}=\sqrt{\langle
A,A\rangle}$, where the inner product is given by $\langle
A,B\rangle=\textrm{tr}(A^{T}B)$. Problem (41) and its variants appear in
applications in different areas such as statistics, physics and economics [15,
18, 26, 50], and were considered, for example, in the numerical tests of [8,
24, 31, 32].

Following we briefly discuss how to compute projections onto the feasible
region of (41). Define $C=\\{X\in\mathbb{R}^{n\times
n}\mid\textrm{tr}(X)=1,\;X\in\mathbb{S}^{n}_{+}\\}$. Since
$\mathbb{S}^{n}_{+}$ is a convex and closed set, $C$ is convex and compact.
Formally the problem of projection a given vector $V\in\mathbb{R}^{n\times n}$
onto $C$ is stated as

$\begin{array}[]{cl}\displaystyle\min_{W\in\mathbb{S}^{n}}&\displaystyle\frac{1}{2}\|W-V\|_{F}^{2}\\\
\mbox{s.t.}&W\in C.\\\ \end{array}$ (42)

Since $\|W-V\|_{F}^{2}=\|W-V_{S}\|_{F}^{2}+\|V_{A}\|^{2}_{F}$ for any
$W\in\mathbb{S}^{n}$, where $V_{S}$ and $V_{A}$ denote the symmetric and the
antisymmetric part of $V$, respectively, it can be assumed, without loss of
generality, that $V\in\mathbb{S}^{n}$. Let $W^{*}$ be the unique solution of
(42). Given the eigen-decomposition $V=QDQ^{T}$, it is well known that
$W^{*}=QP_{\Delta_{n}}(D)Q^{T}$, where $P_{\Delta_{n}}(D)$ denotes the
diagonal matrix obtained by projecting the diagonal elements of $D$ onto the
$n$-dimensional simplex $\Delta_{n}=\\{x\in\mathbb{R}^{n}\mid
x_{1}+\ldots+x_{n}=1;\;x\geq 0\\}$, see, for example, [26]. This means that
computing $W^{*}$ requires a priori the full eigen-decomposition of $V$, which
can be computationally prohibitive for high-dimensional problems. This
drawback will appear clearly in the results reported in section 5.2. Inexact
projections can be obtained by adding the constraint $\textrm{rank}(W)\leq p$,
for a given $1\leq p<n$, to Problem (42). Denoting by $W_{p}$ the solution of
this latter problem, we have $W_{p}=\sum_{i=1}^{p}\lambda_{i}q_{i}q_{i}^{T}$,
where the scalars $(\lambda_{1},\ldots,\lambda_{p})\in\mathbb{R}^{p}$ are
obtained by projecting the $p$ largest eigenvalues of $V$ onto the
$p$-dimensional simplex $\Delta_{p}$ and $q_{i}\in\mathbb{R}^{n}$ are the
corresponding unit eigenvectors for all $i=1,\ldots,p$, see [2]. Therefore,
inexact projections can be computed by means of an incomplete eigen-
decomposition of $V$, resulting in computational savings. Note that if
$\textrm{rank}(W^{*})\leq p$, then $W_{p}$ coincides with $W^{*}$. As far as
we know, this approach was first proposed in [2] and was also used in [24,
23].

We implemented the inexact projection scheme discussed above by choosing
parameter $p$ in an adaptive way and introducing a suitable error criterion.
Let us formally describe the adopted scheme to find an inexact solution
$\tilde{W}$ to Problem (42) relative to $U\in C$ with error tolerance mapping
$\varphi_{\gamma}$ and real numbers $\gamma_{1}$, $\gamma_{2}$ and
$\gamma_{3}$ satisfying the suitable conditions (10) or (26), depending on the
main algorithm.

Algorithm 3 Procedure to compute $\tilde{W}\in{\cal
P}_{C}\left(\varphi_{\gamma},U,V\right)$

Input: Let $1\leq p<n$ be given.

Step 1: Compute $(\lambda_{i}^{V},q_{i})_{i=1}^{p}$ (with $\|q_{i}\|=1$,
$i=1,\ldots,p$) the $p$ largest eigenpairs of $V$, then set
$W_{p}:=\sum_{i=1}^{p}\lambda_{i}q_{i}q_{i}^{T},$ where
$(\lambda_{1},\ldots,\lambda_{p})\in\mathbb{R}^{p}$ are obtained by projecting
$(\lambda_{1}^{V},\ldots,\lambda_{p}^{V})\in\mathbb{R}^{p}$ onto the
$p$-dimensional simplex $\Delta_{p}$.

Step 2: Compute $Y_{p}:=\displaystyle\arg\min_{Y\in C}\,\langle
W_{p}-V,Y-W_{p}\rangle$.

Step 3: If $\langle
W_{p}-V,Y_{p}-W_{p}\rangle\geq-\varphi_{\gamma}(U,V,W_{p})$, then set
$\tilde{W}:=W_{p}$ and return to the main algorithm.

Step 4: Set $p\leftarrow p+1$ and go to Step 1.

Output: $\tilde{W}:=W_{p}$.

Some comments regarding Algorithm 3 are in order. First, in Step 1 we compute
the rank-$p$ projection of $V$ onto $C$. The computational cost os this step
is dominated by the cost of computing the $p$ leading eigenpairs of $V$, since
the projection of $(\lambda_{1}^{V},\ldots,\lambda_{p}^{V})\in\mathbb{R}^{p}$
onto the $p$-dimensional simplex $\Delta_{p}$ can be easily done in $O(p\log
p)$ time, see, for example, [2]. Second, the subproblem in Step 2 is solved by
computing the largest eigenpair of $V-W_{p}$. Indeed, $Y_{p}=qq^{T}$, where
$q\in\mathbb{R}^{n}$ is the unit eigenvector corresponding to the largest
eigenvalue of $V-W_{p}$, see, also, [2]. In our implementations, we used the
Matlab function eigs to compute eigenvalues/eigenvectors [47, 34]. Third, in
Step 3 if the stopping criterion $\langle
W_{p}-V,Y_{p}-W_{p}\rangle\geq-\varphi_{\gamma}(U,V,W_{p})$ is satisfied, then
from Definition 2, we conclude that $\tilde{W}=W_{p}\in{\cal
P}_{C}\left(\varphi_{\gamma},U,V\right)$, i.e., the output is a feasible
inexact projection of $V\in\mathbb{S}^{n}$ relative to $U\in C$. Otherwise, we
increase parameter $p$ and proceed to calculate a more accurate eigen-
decomposition of $V$. Fourth, in the first iteration of the main algorithm, we
set $p=1$ as the input for Algorithm 3. For the subsequent iterations, we
used, in principle, the success value for $p$ from the previous outer
iteration. Without attempting to go into details, seeking computational
savings, in some iterations, we consider decreasing the input $p$ with respect
to the previous successful one.

Concerning the stopping criterion of the main algorithms, all runs were
stopped at an iterate $X^{k}$ declaring convergence if

$\frac{\|X^{\ell}-X^{\ell-1}\|_{F}}{\|X^{\ell-1}\|_{F}}\leq 10^{-4},$

for $\ell=k$ and $\ell=k-1$. This means that we stopped the execution of the
main algorithms when the above convergence metric is satisfied for two
consecutive iterations.

We used a similar strategy as in [24] to generate the test instances of (41).
Given the dimensions $n$ and $m$, with $m\geq n$, we randomly generate $A$ (a
sparse matrix with density $10^{-4}$) with elements between $(-1,1)$. Also,
for a give parameter $\omega>1$, we define
$\bar{X}:=\sum_{i=1}^{\omega}g_{i}g_{i}^{T}$, where $g_{i}\in\mathbb{R}^{n}$
is a random vector with only two nonnull components with the following
structure
$g_{i}=(\cdots\cos(\theta)\cdots\sin(\theta)\cdots)^{T}\in\mathbb{R}^{n}$, and
then set $B=A\bar{X}$. Since $\bar{X}\notin C$, this procedure generally
results in nonzero residue problems.

###  5.1 Influence of the forcing parameter $\gamma$

We start the numerical experiments by checking the influence of the forcing
parameter $\gamma^{k}=(\gamma_{1}^{k},\gamma_{2}^{k},\gamma_{3}^{k})$ in
Algorithm 1. We implemented Algorithm 1 with: $(a_{k})_{k\in\mathbb{N}}$ and
$(b_{k})_{k\in\mathbb{N}}$ given as in Remark 2(ii) with $\bar{b}=100$, and
using

$\varphi_{\gamma^{k}}(U,V,W)=\gamma_{1}^{k}\|V-W\|_{F}^{2}+\gamma_{2}^{k}\|W-V\|_{F}^{2}+\gamma_{3}^{k}\|W-U\|_{F}^{2},\quad\forall
k=1,2,\ldots,$ (43)

as the error tolerance function, see Definition 2. We also set
$\bar{\gamma_{2}}=0.49995$. Concerning parameter $\bar{\gamma}$, we considered
different values for it, as we will explain below. Given a particular
$\bar{\gamma}<1/2$, we set

$\alpha=0.9999\cdot\frac{1-2\bar{\gamma}}{L},$ (44)

where the Lipschitz constant $L$, with respect to problem (41), is given by
$L=\|A^{T}A\|_{F}$. The choice (44) for the fixed step size $\alpha$ trivially
satisfies (12). Since parameter $\gamma_{3}^{k}$ and the step size $\alpha$
are closely related (see (44) and recall that
$0\leq\gamma_{3}^{k}\leq\bar{\gamma}<1/2$), we first investigate the behavior
of Algorithm 1 by varying only the strategy for $\gamma_{3}^{k}$. We set

$\gamma_{2}^{k}=\min\left(\frac{1}{2}\frac{a_{k}}{\|\nabla
f(X^{k})\|_{F}^{2}},\bar{\gamma_{2}}\right),\quad\gamma_{1}^{k}=\frac{a_{k}}{\|\nabla
f(X^{k})\|_{F}^{2}}-\gamma_{2}^{k},\quad\mbox{and}\quad\gamma_{3}^{k}=\bar{\gamma},\quad\forall
k=1,2,\ldots,$ (45)

and considered some different values for $\bar{\gamma}$. Note that the forcing
parameter $\gamma^{k}$ given by (45) satisfies (10). We used an instance of
problem (41) with $n=2000$, $m=4000$, and $\omega=10$. The results for the
starting point $X^{0}=(1/n)I$ and different choices for $\bar{\gamma}$ are in
Table 1. In the table, “$f(X^{*})$” is the function value at the final
iterate, “it” is the number of outer iterations, “time(s)” is the run time in
seconds, and “$\alpha$” is the corresponding fixed step size given by (44).

$\gamma_{3}^{k}=\bar{\gamma}$ | $f(X^{*})$ | it | time(s) | $\alpha$
---|---|---|---|---
$0.0$ | 0.4899 | 107 | 28.9 | 0.0698
$0.1$ | 0.4899 | 129 | 36.6 | 0.0558
$0.2$ | 0.4899 | 162 | 43.5 | 0.0419
$0.3$ | 0.4899 | 223 | 59.6 | 0.0279
$0.4$ | 0.4899 | 375 | 101.0 | 0.0140
Table 1: Influence of parameter $\bar{\gamma}_{3}$ in the performance of
Algorithm 1 with the forcing parameter $\gamma^{k}$ given as in (45) for an
instance of problem (41) with $n=2000$, $m=4000$, and $\omega=10$.

As can be seen in Table 1, Algorithm 1 performs better for lower values of
$\bar{\gamma}_{3}$. This is undoubtedly due to the fact that the fixed step
size $\alpha$ is inversely proportional to $\bar{\gamma}_{3}$, see (44) and
the last column of the table. This result suggests that for the gradient
method with constant step size, the best choice is to take $\gamma_{3}^{k}=0$
for all $k$, leaving the inexactness of the projections to be controlled only
by the terms of $\gamma_{1}^{k}$ and $\gamma_{2}^{k}$ in (43). From an
algorithmic point of view, the term corresponding to $\gamma_{3}^{k}$ in (43)
involves the last two generated iterates and is often used in inexactness
measures. Therefore, for projection algorithms that use a constant step size,
at least under restrictions as in (12), the theory developed here presents
practical alternatives for the formulation of such measures.

Taking $\bar{\gamma}=0$, we consider different combinations of
$\gamma_{1}^{k}$ and $\gamma_{2}^{k}$ such that
$\gamma_{1}^{k}+\gamma_{2}^{k}=a_{k}/\|\nabla f(X^{k})\|_{F}^{2}$. Our
experiments showed that Algorithm 1 presented no significant performance
difference with these combinations. Therefore, in the experiments reported in
section 5.2, we set for Algorithm 1 the forcing parameter $\gamma^{k}$ as in
(45) with $\bar{\gamma}=0$.

###  5.2 Comparison with exact projection approaches

In the present section, we compare the performance of Algorithms 1 and 2 with
their exact counterparts. Algorithm 2 was implemented using the error
tolerance function (43) with

$\gamma^{k}=(0,0,0.49995),\quad\forall k=1,2,\ldots,$

and

$\alpha_{k}:=\left\\{\begin{array}[]{ll}\displaystyle\min\left(\alpha_{\max},\max\left(\alpha_{\min},\langle
S^{k},S^{k}\rangle/\langle
S^{k},Y^{k}\rangle\right)\right),&\mbox{if}\;\langle S^{k},Y^{k}\rangle>0\\\
\alpha_{\max},&\mbox{otherwise},\end{array}\right.$ (46)

where $S^{k}:=X^{k}-X^{k-1}$, $Y^{k}:=\nabla f(X^{k})-\nabla f(X^{k-1})$,
$\alpha_{\min}=10^{-10}$, and $\alpha_{\max}=10^{10}$. We observe that (46)
corresponds to the spectral choice for $\alpha_{k}$, see [8, 7]. In the exact
versions, the projections are calculated exactly, that is, involving full
eigen-decompositions.

We considered some instances of problem (41) with different parameters $n$,
$m$ and $\omega$ and using three starting points given by
$X^{0}(\beta)=(1-\beta)(1/n)I+\beta e_{1}e_{1}^{T}$, where
$e_{1}\in\mathbb{R}^{n}$ is the first canonical vector and
$\beta\in\\{0.00,0.50,0.99\\}$. The results in Table 2 shows that, in relation
to the CPU time, the inexact algorithms were notably more efficient (mainly in
the larger instances) than the corresponding exact versions. In general,
moderate values for the rank parameter $p$ in Algorithm 3 (typically, less
than 10) were sufficient to compute the inexact projections, allowing
significant computational savings with respect to the exact approaches.
Finally, we observe that Algorithm 2 was much more efficient than Algorithm 1
on the chosen set of test problems. This was already expected, due to the
simplicity of the objective function of (41). Note that Algorithm 1 does not
require evaluations of the objective function (only gradient evaluations).
Therefore, we hope that Algorithm 1 can be competitive in problems where the
objective function is expensive to be computationally evaluated.

| Algorithm 1 | Algorithm 2
---|---|---
| Inexact | Exact | Inexact | Exact
$n$ | $m$ | $\omega$ | $\beta$ | $f(X^{*})$ | it | time(s) | $f(X^{*})$ | it | time(s) | $f(X^{*})$ | it | time(s) | $f(X^{*})$ | it | time(s)
|  |  | 0.00 | 0.4899 | 107 | 30.0 | 0.4899 | 108 | 78.3 | 0.4899 | 8 | 3.6 | 0.4899 | 8 | 6.8
|  | 10 | 0.50 | 0.4899 | 108 | 36.7 | 0.4899 | 108 | 78.4 | 0.4899 | 9 | 4.0 | 0.4899 | 9 | 7.7
|  |  | 0.99 | 0.4899 | 110 | 29.2 | 0.4899 | 110 | 78.8 | 0.4899 | 9 | 4.0 | 0.4899 | 9 | 7.6
|  |  | 0.00 | 0.7887 | 141 | 47.6 | 0.7887 | 141 | 101.7 | 0.7887 | 9 | 4.2 | 0.7887 | 9 | 7.5
|  | 20 | 0.50 | 0.7887 | 139 | 46.8 | 0.7887 | 139 | 100.4 | 0.7887 | 9 | 4.2 | 0.7887 | 9 | 7.6
2000 |  4000 |  | 0.99 | 0.7887 | 136 | 36.1 | 0.7887 | 138 | 96.6 | 0.7887 | 10 | 4.8 | 0.7887 | 10 | 8.3
|  |  | 0.00 | 0.2139 | 189 | 124.3 | 0.2139 | 189 | 543.1 | 0.2139 | 8 | 9.6 | 0.2139 | 8 | 27.0
|  | 10 | 0.50 | 0.2139 | 189 | 133.2 | 0.2139 | 189 | 541.5 | 0.2139 | 8 | 9.6 | 0.2139 | 9 | 30.0
|  |  | 0.99 | 0.2139 | 190 | 121.8 | 0.2139 | 190 | 537.1 | 0.2139 | 10 | 11.5 | 0.2139 | 9 | 30.2
|  |  | 0.00 | 0.9837 | 173 | 113.1 | 0.9837 | 172 | 491.6 | 0.9837 | 11 | 13.0 | 0.9837 | 12 | 39.4
|  | 20 | 0.50 | 0.9837 | 170 | 109.9 | 0.9837 | 170 | 485.2 | 0.9837 | 11 | 12.9 | 0.9837 | 10 | 33.2
3000 |  6000 |  | 0.99 | 0.9837 | 161 | 102.8 | 0.9837 | 164 | 466.3 | 0.9837 | 12 | 14.1 | 0.9837 | 10 | 33.3
|  |  | 0.00 | 1.0046 | 166 | 194.2 | 1.0046 | 165 | 1092.5 | 1.0046 | 10 | 22.8 | 1.0046 | 11 | 83.7
|  | 10 | 0.50 | 1.0046 | 165 | 191.6 | 1.0046 | 165 | 1088.8 | 1.0046 | 12 | 26.4 | 1.0046 | 11 | 83.7
|  |  | 0.99 | 1.0046 | 169 | 193.4 | 1.0046 | 169 | 1113.0 | 1.0046 | 11 | 25.0 | 1.0046 | 12 | 91.2
|  |  | 0.00 | 3.0753 | 90 | 126.2 | 3.0753 | 89 | 585.9 | 3.0753 | 8 | 16.9 | 3.0753 | 8 | 63.6
|  | 20 | 0.50 | 3.0753 | 89 | 122.8 | 3.0753 | 89 | 584.9 | 3.0753 | 9 | 18.5 | 3.0753 | 8 | 62.0
4000 |  8000 |  | 0.99 | 3.0753 | 87 | 99.4 | 3.0753 | 86 | 566.0 | 3.0753 | 9 | 18.8 | 3.0753 | 9 | 67.3
|  |  | 0.00 | 0.7182 | 243 | 599.6 | 0.7182 | 243 | 3212.4 | 0.7181 | 10 | 39.7 | 0.7181 | 10 | 150.8
|  | 10 | 0.50 | 0.7182 | 244 | 594.4 | 0.7182 | 244 | 3206.3 | 0.7181 | 9 | 36.3 | 0.7181 | 10 | 151.4
|  |  | 0.99 | 0.7182 | 246 | 571.2 | 0.7182 | 246 | 3227.1 | 0.7181 | 10 | 38.2 | 0.7181 | 10 | 150.0
|  |  | 0.00 | 2.7721 | 178 | 436.3 | 2.7721 | 178 | 2339.8 | 2.7721 | 8 | 29.8 | 2.7721 | 8 | 122.8
|  | 20 | 0.50 | 2.7721 | 177 | 436.2 | 2.7721 | 177 | 2325.5 | 2.7721 | 8 | 30.5 | 2.7721 | 7 | 108.5
5000 |  10000 |  | 0.99 | 2.7721 | 172 | 395.9 | 2.7721 | 172 | 2253.6 | 2.7721 | 8 | 29.6 | 2.7721 | 8 | 122.3
Table 2: Performance of the inexact and exact versions of Algorithms 1 and 2
in some instances of problem (41).

##  6 Conclusions

In this paper, we proposed a new inexact version of the classical gradient
projection method (GPM) denoted by Gradient-InexP method (GInexPM) for solving
constrained convex optimization problems. As a way to compute an inexact
projection the GInexPM uses a relative error tolerance. Two different
strategies for choosing the step size were employed in the analyses of the
method. The convergence analysis was carried out without any compactness
assumption. In addition, we provided some iteration-complexity results related
to GInexPM. Numerical results were reported illustrating potential advantages
of considering inexact projections instead of exact ones. We expect that this
paper will contribute to the development of research in this field of inexact
projections, mainly to solve large-scale problems.

## References

  * [1] A. A. Aguiar, O. P. Ferreira, and L. F. Prudente.  Subgradient method with feasible inexact projections for constrained convex optimization problems.  page arXiv:2006.08770, June 2020, 2006.08770.
  * [2] Z. Allen-Zhu, E. Hazan, W. Hu, and Y. Li.  Linear convergence of a Frank-Wolfe type algorithm over trace-norm balls.  In Advances in Neural Information Processing Systems, pages 6191–6200, 2017.
  * [3] A. Beck.  Introduction to nonlinear optimization, volume 19 of MOS-SIAM Series on Optimization.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2014.  Theory, algorithms, and applications with MATLAB.
  * [4] J. Y. Bello Cruz and L. R. Lucambio Pérez.  Convergence of a projected gradient method variant for quasiconvex objectives.  Nonlinear Anal., 73(9):2917–2922, 2010.
  * [5] D. P. Bertsekas.  On the Goldstein-Levitin-Polyak gradient projection method.  IEEE Trans. Automatic Control, AC-21(2):174–184, 1976.
  * [6] D. P. Bertsekas.  Nonlinear programming.  Athena Scientific Optimization and Computation Series. Athena Scientific, Belmont, MA, second edition, 1999.
  * [7] E. G. Birgin, J. M. Martínez, and M. Raydan.  Nonmonotone spectral projected gradient methods on convex sets.  SIAM Journal on Optimization, 10(4):1196–1211, 2000, https://doi.org/10.1137/S1052623497330963.
  * [8] E. G. Birgin, J. M. Martínez, and M. Raydan.  Inexact spectral projected gradient methods on convex sets.  IMA Journal of Numerical Analysis, 23(4):539–559, 2003.
  * [9] L. Bottou, F. E. Curtis, and J. Nocedal.  Optimization methods for large-scale machine learning.  SIAM Rev., 60(2):223–311, 2018.
  * [10] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan.  Linear matrix inequalities in system and control theory, volume 15 of SIAM Studies in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994.
  * [11] S. Bubeck.  Convex optimization: Algorithms and complexity.  Foundations and Trends® in Machine Learning, 8(3-4):231–357, 2015\.
  * [12] R. Burachik, L. M. G. Drummond, A. N. Iusem, and B. F. Svaiter.  Full convergence of the steepest descent method with inexact line searches.  Optimization, 32(2):137–146, 1995.
  * [13] F. R. de Oliveira, O. P. Ferreira, and G. N. Silva.  Newton’s method with feasible inexact projections for solving constrained generalized equations.  Comput. Optim. Appl., 72(1):159–177, 2019.
  * [14] R. Díaz Millán, O. P. Ferreira, and L. F. Prudente.  Alternating conditional gradient method for convex feasibility problems.  arXiv e-prints, page arXiv:1912.04247, Dec 2019, 1912.04247.
  * [15] R. Escalante and M. Raydan.  Dykstra’s algorithm for constrained least-squares rectangular matrix problems.  Computers & Mathematics with Applications, 35(6):73 – 79, 1998\.
  * [16] J. Fan, L. Wang, and A. Yan.  An inexact projected gradient method for sparsity-constrained quadratic measurements regression.  Asia-Pac. J. Oper. Res., 36(2):1940008, 21, 2019.
  * [17] M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright.  Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems.  IEEE Journal of Selected Topics in Signal Processing, 1(4):586–597, Dec 2007.
  * [18] R. Fletcher.  A nonlinear programming problem in statistics (educational testing).  SIAM Journal on Scientific and Statistical Computing, 2(3):257–267, 1981, https://doi.org/10.1137/0902021.
  * [19] J. Fliege, A. I. F. Vaz, and L. N. Vicente.  Complexity of gradient descent for multiobjective optimization.  Optim. Methods Softw., 34(5):949–959, 2019.
  * [20] M. Fukushima, Z.-Q. Luo, and P. Tseng.  Smoothing functions for second-order-cone complementarity problems.  SIAM J. Optim., 12(2):436–460, 2001/02.
  * [21] M. Golbabaee and M. E. Davies.  Inexact gradient projection and fast data driven compressed sensing.  IEEE Transactions on Information Theory, 64(10):6707–6721, 2018\.
  * [22] A. A. Goldstein.  Convex programming in Hilbert space.  Bull. Amer. Math. Soc., 70:709–710, 1964.
  * [23] D. S. Gonçalves, M. L. Gonçalves, and F. R. Oliveira.  Levenberg-marquardt methods with inexact projections for constrained nonlinear systems.  arXiv preprint arXiv:1908.06118, 2019.
  * [24] D. S. Gonçalves, M. L. N. Gonçalves, and T. C. Menezes.  Inexact variable metric method for convex-constrained optimization problems.  Optimization-Online e-prints, 2020.
  * [25] P. Gong, K. Gai, and C. Zhang.  Efficient euclidean projections via piecewise root finding and its application in gradient projection.  Neurocomputing, 74(17):2754 – 2766, 2011.
  * [26] D. Gonçalves, M. Gomes-Ruggiero, and C. Lavor.  A projected gradient method for optimization over density matrices.  Optimization Methods and Software, 31(2):328–341, 2016, https://doi.org/10.1080/10556788.2015.1082105.
  * [27] M. L. N. Gonçalves, J. G. Melo, and R. D. C. Monteiro.  Projection-free accelerated method for convex optimization.  Optimization Methods and Software, 0(0):1–27, 2020.
  * [28] A. N. Iusem.  On the convergence properties of the projected gradient method for convex optimization.  Comput. Appl. Math., 22(1):37–52, 2003.
  * [29] A. N. Iusem and B. F. Svaiter.  A proximal regularization of the steepest descent method.  RAIRO Rech. Opér., 29(2):123–130, 1995.
  * [30] K. C. Kiwiel and K. Murty.  Convergence of the steepest descent method for minimizing quasiconvex functions.  J. Optim. Theory Appl., 89(1):221–226, 1996.
  * [31] G. Lan.  The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle.  arXiv e-prints, page arXiv:1309.5550, Sep 2013, 1309.5550.
  * [32] G. Lan and Y. Zhou.  Conditional gradient sliding for convex optimization.  SIAM J. Optim., 26(2):1379–1409, 2016.
  * [33] C.-P. Lee and S. Wright.  First-order algorithms converge faster than $o(1/k)$ on convex problems.  In K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 3754–3762, Long Beach, California, USA, 09–15 Jun 2019. PMLR.
  * [34] R. B. Lehoucq, D. C. Sorensen, and C. Yang.  ARPACK Users’ Guide.  Society for Industrial and Applied Mathematics, 1998, https://epubs.siam.org/doi/pdf/10.1137/1.9780898719628.
  * [35] E. Levitin and B. Polyak.  Constrained minimization methods.  USSR Computational Mathematics and Mathematical Physics, 6(5):1 – 50, 1966.
  * [36] G. Ma, Y. Hu, and H. Gao.  An accelerated momentum based gradient projection method for image deblurring.  In 2015 IEEE International Conference on Signal Processing, Communications and Computing (ICSPCC), pages 1–4, 2015.
  * [37] O. L. Mangasarian.  Nonlinear programming, volume 10 of Classics in Applied Mathematics.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994.  Corrected reprint of the 1969 original.
  * [38] J. J. Moré.  Gradient projection techniques for large-scale optimization problems.  In Proceedings of the 28th IEEE Conference on Decision and Control, Vol. 1–3 (Tampa, FL, 1989), pages 378–381. IEEE, New York, 1989.
  * [39] J. J. Moré.  On the performance of algorithms for large-scale bound constrained problems.  In Large-scale numerical optimization (Ithaca, NY, 1989), pages 32–45. SIAM, Philadelphia, PA, 1990.
  * [40] Y. Nesterov.  Introductory lectures on convex optimization, volume 87 of Applied Optimization.  Kluwer Academic Publishers, Boston, MA, 2004.  A basic course.
  * [41] Y. Nesterov and A. Nemirovski.  On first-order algorithms for $\ell_{1}$/nuclear norm minimization.  Acta Numer., 22:509–575, 2013.
  * [42] J. Nocedal and S. J. Wright.  Numerical optimization.  Springer Series in Operations Research and Financial Engineering. Springer, New York, second edition, 2006.
  * [43] A. Patrascu and I. Necoara.  On the convergence of inexact projection primal first-order methods for convex minimization.  IEEE Trans. Automat. Control, 63(10):3317–3329, 2018.
  * [44] M. Schmidt, N. L. Roux, and F. Bach.  Convergence rates of inexact proximal-gradient methods for convex optimization.  In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS’11, page 1458–1466, Red Hook, NY, USA, 2011. Curran Associates Inc.
  * [45] A. M.-C. So and Z. Zhou.  Non-asymptotic convergence analysis of inexact gradient methods for machine learning without strong convexity.  Optim. Methods Softw., 32(4):963–992, 2017.
  * [46] S. Sra, S. Nowozin, and S. Wright.  Optimization for Machine Learning.  Neural information processing series. MIT Press, 2012.
  * [47] G. W. Stewart.  A krylov–schur algorithm for large eigenproblems.  SIAM Journal on Matrix Analysis and Applications, 23(3):601–614, 2002, https://doi.org/10.1137/S0895479800371529.
  * [48] J. Tang, M. Golbabaee, and M. E. Davies.  Gradient projection iterative sketch for large-scale constrained least-squares.  In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 3377–3386, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.
  * [49] S. Villa, S. Salzo, L. Baldassarre, and A. Verri.  Accelerated and inexact forward-backward algorithms.  SIAM J. Optim., 23(3):1607–1633, 2013.
  * [50] K. G. Woodgate.  Least-squares solution of f = pg over positive semidefinite symmetric p.  Linear Algebra and its Applications, 245:171 – 190, 1996.
  * [51] F. Zhang, H. Wang, J. Wang, and K. Yang.  Inexact primal–dual gradient projection methods for nonlinear optimization on convex set.  Optimization, 0(0):1–27, 2019.