1 Introduction
Let
$\mathcal {H}$
be a real Hilbert space. A mapping
$T\colon \mathcal {H}\rightarrow \mathcal {H}$
is said to be nonexpansive if
$\Vert Tx-Ty\Vert \le \Vert x-y\Vert $
for all
$x,y\in \mathcal {H}$
. We use
$\text {Fix}(T)$
to denote the set of fixed points of T (that is,
$\text {Fix}(T)=\{u\in \mathcal {H} : Tu=u\}$
). The class of nonexpansive mappings includes all contractions but the existence of a fixed point of a nonexpansive mapping is not guaranteed unless some additional conditions are assumed.
We are interested in the following projection algorithm introduced by Nakajo and Takahashi [Reference Nakajo and Takahashi15]:
$x_{0}=x\in \mathcal {H}$
and
for
$k=0,1,2,\ldots , $
where
$\{\alpha _{k}\}\subset [\alpha ,1]$
for some
$\alpha \in (0,1]$
and
$P_{K}$
denotes the metric projection from
$\mathcal {H}$
onto a closed convex subset K of
$\mathcal {H}$
. The idea of (1.1) is based on the strongly convergent inexact proximal point algorithm of Solodov and Svaiter [Reference Solodov and Svaiter18, Algorithm 1]. The sequence
$\{x_k\}$
generated by (1.1) converges strongly to
$P_{\text {Fix}(T)}x$
[Reference Nakajo and Takahashi15, Theorem 3.4]. In the original result, the existence of the iterates
$\{x_k\}$
was established under the assumption that
$\text {Fix}(T)\neq \emptyset $
. In contrast, in [Reference Matsushita and Takahashi13], we showed that even in the absence of fixed points, it is possible to ensure that the set
$C_{k}\cap Q_{k}$
is always nonempty; that is, the sequence
$\{x_{k}\}$
is always well-defined. Furthermore, we showed that the boundedness of
$\{x_k\}$
guarantees the existence of a fixed point. The projection algorithm (1.1) has subsequently been developed in various directions (see, for example, [Reference Martinez-Yanes and Xu11, Reference Matsushita and Takahashi12, Reference Matsushita and Takahashi14, Reference Xu20]).
The inertial extrapolation technique was made immensely popular by Nesterov’s accelerated gradient algorithm [Reference Nesterov16]. Subsequently, many methods have been proposed to improve the convergence speed of these algorithms (see, for example, the proximal point algorithm [Reference Alvarez and Attouch1], Krasnosel’skiı̆–Mann algorithm [Reference Cortild and Peypouquet6, Reference Mainge10], forward-backward algorithm [Reference Beck and Teboulle4] and Douglas–Rachford algorithm [Reference Boţ, Csetnek and Hendrich5]). Especially, Dong et al. [Reference Dong, Yuan, Je and Rassias7] proposed the following algorithm, which incorporates a one-step inertial term into (1.1):
$x, x_{-1}, x_{0}\in \mathcal {H}$
and
for
$k=0,1,2,\ldots ,$
where
$\{\lambda _{k}\}\subset (a,b)$
for some
$a\in (-\infty ,0]$
and
$b\in [0,\infty )$
, and
$\{\beta _{k}\}\subset [\beta ,1]$
for some
$\beta \in (0,1]$
. The main idea of (1.2) is to introduce an inertial effect at the current iterate
$x_k$
by extrapolating
$x_k$
in the direction
$x_k-x_{k-1}$
.
Although the algorithm incorporating the inertial term is convergent, we emphasise that algorithms with a one-step inertial term do not necessarily achieve acceleration. For instance, it has been reported in [Reference Poon, Liang, Wallach, Larochelle, Beygelzimer, d’Alché-Buc, Fox and Garnett17, Section 4] that the Douglas–Rachford algorithm with a one-step inertial term may converge more slowly than the original algorithm. Multi-step inertial techniques could help to achieve the expected improvements in the speed of convergence of algorithms.
In this paper, we analyse extensions of these projection algorithms.
-
• First, we introduce a projection algorithm that employs an arbitrary sequence and encompasses many existing methods. Using the proposed algorithm, we show that even in the absence of fixed points, the intersection of the half-spaces remains nonempty; that is, the existence of iterates is guaranteed, independent of the existence of a fixed point.
-
• Second, as an extension of algorithms such as (1.1) and (1.2), we propose a multi-step inertial projection algorithm. The idea of the multi-step inertial term is inspired by the approach applied to the forward-backward splitting algorithm in [Reference Liang9, Ch. 6]. We show that the boundedness of the iterates is equivalent to the existence of a fixed point of the nonexpansive mappings. Furthermore, we establish the strong convergence of the proposed algorithm under less restrictive assumptions on the inertial parameters. Finally, we present results on the iteration complexity.
The paper is organised as follows. Section 2 presents the mathematical preliminaries. Section 3 establishes the well-definedness of the algorithm in a general setting. Section 4 provides results on the existence, strong convergence and iteration complexity of the inertial projection algorithm.
2 Preliminaries
This section reviews basic definitions, facts and notation that will be used throughout the paper.
Let
$\mathcal {H}$
denote a real Hilbert space endowed with the inner product
$\langle \cdot ,\cdot \rangle $
and the norm
$\Vert \cdot \Vert $
.
$\mathbb {R}$
and
$\mathbb {N}$
denote the set of real numbers and the set of positive integers, respectively. For any
$\{x_k\}\subset \mathcal {H}$
and
$x\in \mathcal {H}$
, we write
$x_{k}\rightarrow x$
and
$x_k\rightharpoonup x$
to denote the strong and weak convergence of
$\{x_k\}$
to x, respectively. For
$x,y\in \mathcal {H}$
and
$\alpha \in \mathbb {R}$
,
(see, for example, [Reference Bauschke and Combettes3, Lemma 2.12 and Corollary 2.14]).
Let
${C}$
be a closed convex subset of
$\mathcal {H}$
. Then for any
$x\in \mathcal {H}$
, there exists a unique point
$x^{*}\in C$
such that
The mapping
$P_{C}\colon \mathcal {H} \rightarrow C$
defined by
$P_{C}x=x^{*}$
is called the metric projection from
$\mathcal {H}$
onto C. We have
$u=P_{C}x$
if and only if
(see, for example, [Reference Bauschke and Combettes3, Reference Takahashi19]).
We use the following result of Martinez-Yanes and Xu [Reference Martinez-Yanes and Xu11] to prove the convergence result.
Lemma 2.1 [Reference Martinez-Yanes and Xu11, Lemma 1.5]
Let D be a closed convex subset of
$\mathcal {H}$
and
$u \in \mathcal{H}$
and
$\{x_{k}\}$
be a sequence in
$\mathcal {H}$
. Suppose that
-
• every weak cluster point of $\{x_{k}\}$
belongs to D; -
• $\|u-x_k\| \le \|u-P_Du\| $
for all
$k\ge 1$
.
Then
$x_{k}\rightarrow P_{D}u$
.
We use the following result of Khatibzadeh [Reference Khatibzadeh8] to prove the convergence rate result.
Lemma 2.2 [Reference Khatibzadeh8, Lemma 5.1]
Suppose that
$\{a_k\}$
and
$\{b_k\}$
are two positive real sequences such that
-
• $\{a_k\}$
is nonincreasing and convergent to zero; -
• $\sum _{k=1}^{\infty }a_{k}b_{k}<\infty $
.
Then
$a_{k}=o(1/\sum _{n=1}^{k}b_{n})$
(that is,
$\lim _{k\rightarrow \infty }(\sum _{n=1}^{k}b_n)a_{k}=0$
).
Finally, we present a technical lemma.
Lemma 2.3. Let
$a,b\in \mathcal {H}$
. For any
$z\in \mathcal {H}$
, the following statements are equivalent:
-
(i) $\Vert a-z\Vert \le \Vert b-z\Vert $
; -
(ii) $\langle {\tfrac 12(b+a)-z},{\tfrac 12(b+a)-a}\rangle \le 0$
.
Proof.
3 A projection algorithm
In this section, we first investigate the following algorithm, which generalises (1.1).
Algorithm 3.1. Let x
0 ∈
$\mathcal {H}$
and let {w
k
} be an arbitrary sequence in
$\mathcal {H}$
. Define
k = 0, 1, 2, … , where {β k }⊂ [0, 1].
Remark 3.2. Algorithm 3.1 includes existing algorithms. If we set
$w_{k}\equiv x_{k}$
, then Algorithm 3.1 becomes (1.1). Moreover, if we set
$w_{k} \equiv x_{k}+\lambda _{k}(x_{k}-x_{k-1})$
, Algorithm 3.1 becomes (1.2).
Simple calculations show that
$C_{k}$
and
$Q_{k}$
can be equivalently written as
From Algorithm 3.1, the next iterate
$x_{k+1}$
is defined by metric projection of
$x_0$
onto the intersection
$C_k\cap Q_k$
of the half-spaces
$C_k$
and
$Q_k$
. The closed-form representation of the projection onto the intersection of two half-spaces is discussed in [Reference Solodov and Svaiter18, Section 3] and [Reference Bauschke and Combettes3, Ch. 29].
3.1 Well-definedness of Algorithm 3.1
In this subsection, we will prove the well-definedness of Algorithm 3.1. The following result guarantees the existence of the sequence generated by Algorithm 3.1.
Lemma 3.3. Consider the sequences generated by Algorithm 3.1:
-
(i) for all $k\in \mathbb {N}\cup \{0\}$
, we have
$\bigcap _{i=0}^{k}C_{i}\subset C_{k}\cap Q_{k}$
and
$\bigcap _{i=0}^{k}C_{i}\neq \emptyset $
; -
(ii) $\{x_{k}\}$
is well-defined; -
(iii) for all $k\in \mathbb {N}\cup \{0\}$
, we have
$\mathrm {Fix}(T)\subset C_{k}\cap Q_{k}$
; -
(iv) if $\mathrm {Fix}(T)\neq \emptyset $
, then
$\{x_{k}\}$
is bounded.
Proof. (
$\mathrm {i}$
) For
$k=0$
, the inclusion
$C_{0}\subset C_{0}\cap Q_{0}$
follows from
$Q_{0}=\mathcal {H}$
. Note that
$y_{0}\in C_{0}$
and hence
$C_0\neq \emptyset $
. Let
$m\in \mathbb {N}$
and assume that for all
$l\in \{0,1,\ldots ,m-1\}$
,
${\bigcap _{i=0}^{l}C_i\subset C_l\cap Q_l}$
and
$\bigcap _{i=0}^{l}C_i\neq \emptyset $
are true. In this case, we can define
$x_{m}$
by
$x_{m}=P_{C_{m-1}\cap Q_{m-1}}(x_0)$
.
We first show
$\bigcap _{i=0}^{k}C_{i}\subset C_{k}\cap Q_{k}$
. It follows from (2.2) that
and hence
$C_{m-1}\cap Q_{m-1}\subset Q_{m}$
. This implies that
Therefore, by induction,
$\bigcap _{i=0}^{k}C_{i}\subset C_{k}\cap Q_{k}$
.
We next show that
$\bigcap _{i=0}^{k}C_{i}\neq \emptyset $
. Set
$D = \{u\in \mathcal {H}:\Vert u\Vert \le \max _{0\le i\le m}\{\Vert Tw_{i}\Vert , \Vert y_{i}\Vert \}\}$
, let
$l\in \{0,1,\ldots ,m\}$
and let
$P_{D}$
be the metric projection onto D. Since D is bounded, closed and convex, and the composition
$P_{D}\circ T$
is nonexpansive on D, it follows from the Browder–Göhde–Kirk fixed point theorem (see, for example, [Reference Takahashi19, Corollary 3.1.7], [Reference Bauschke and Combettes3, Theorem 4.20]) that there exists
$z\in D$
such that
$P_{D}\circ T(z)=z$
. From (2.2),
and hence
It follows that
Since l was chosen arbitrarily in
$\{0,1,\ldots ,m\}$
, this shows that
$z\in \bigcap _{i=0}^{m}C_{i}$
. Therefore,
$\bigcap _{i=0}^{k}C_{i}\neq \emptyset $
for
$k=0,1,2,\ldots .$
(
$\mathrm {ii}$
) The well-definedness of
$\{x_k\}$
can be obtained straightforwardly by (
$\mathrm {i}$
).
(
$\mathrm {iii}$
) Let
$k\in \mathbb {N}\cup \{0\}$
and let
$p\in \text {Fix}(T)$
. For all
$i\in \{0,\ldots ,k\}$
,
and hence
$p\in \bigcap _{i=0}^{k}C_{i}$
. It follows that
$\text {Fix}(T)\subset \bigcap _{i=0}^{k}C_{i}\subset C_{k}\cap Q_{k}$
.
(
$\mathrm {iv}$
) From the definition of
$Q_{k}$
, we have
$x_{k}=P_{Q_{k}}(x_0)$
. Fix
$p\in \text {Fix}(T)\,(\subset C_{k}\cap Q_{k})$
. Then
for all
$k\in \mathbb {N}\cup \{0\}$
. This implies that
$\{x_{k}\}$
is bounded.
Remark 3.4. Lemma 3.3 is a generalisation of [Reference Matsushita and Takahashi13, Theorem 2.2], and its proof, which we presented here, follows the ideas from [Reference Matsushita and Takahashi13, Theorem 2.2].
In previous work (for example, [Reference Dong, Yuan, Je and Rassias7, Reference Matsushita and Takahashi12, Reference Matsushita and Takahashi14, Reference Nakajo and Takahashi15, Reference Xu20]), the well-definedness of the projection-type algorithms was proved with the assumption that
$\textrm {Fix}(T)\neq \emptyset $
.
4 Existence and convergence results
In this section, we propose a multi-step inertial projection algorithm and establish boundedness, existence and convergence results.
Algorithm 4.1. Let l ≥ 1 and set S = {0, 1, … , l − 1}. Assume that x
−i
= x
0 ∈
$\mathcal {H}$
for each i ∈ S. We consider the following multi-step inertial projection algorithm:
for k = 0, 1, 2, … , where (λ k, 0, λ k, 1, … , λ k, l−1) ∈ ℝ l and {β k }⊂ [0, 1].
To establish the results, we need the following assumption.
Assumption 4.2. Assume that
$\{\beta _k\}$
and
$\{\lambda _{k,n}\}$
satisfy the following conditions:
-
(A1) $\{\beta _{k}\}\subset [\beta ,1]$
for some
$\beta \in (0,1]$
; -
(A2) $(\lambda _{k,0},\lambda _{k,1},\ldots ,\lambda _{k,l-1})\in (-a,a)^{l}$
for all k for some
$a\in (0,\infty )$
.
4.1 Existence result
In this subsection, we establish a fixed point theorem for nonexpansive mappings in Hilbert spaces.
Theorem 4.3. Let
$\{x_{k}\}$
be a sequence generated by Algorithm 4.1 and assume that Assumption 4.2 holds for
$\{(\lambda _{k,0},\lambda _{k,1},\ldots ,\lambda _{k,l-1})\}$
and
$\{\beta _{k}\}$
. Then the following statements are equivalent:
-
• $\{x_{k}\}$
is bounded; -
• $\mathrm {Fix}(T)\neq \emptyset $
.
Proof. From Lemma 3.3(
$\mathrm {iv}$
), it is sufficient to consider the case when
$\{x_{k}\}$
is bounded. Since
$x_{k+1}=P_{C_k\cap Q_k}x_{0}\in Q_{k}$
,
This implies that
This together with the boundedness assumption implies that
$\{\Vert x_{k}-x_{0}\Vert ^{2}\}$
is convergent. Moreover,
and hence
$\lim _{k\rightarrow \infty }\Vert x_{k+1}-x_{k}\Vert =0$
.
On the other hand,
and it follows that
$\lim _{k\rightarrow \infty }\Vert w_{k}-x_{k}\Vert =0$
. Moreover, from
$T(w_{k})-w_{k}=\ (1/\beta _{k})(y_{k}-w_{k})$
,
Consequently,
$\lim _{k\rightarrow \infty }\Vert T(w_{k})-w_{k}\Vert =0$
. Now, we see that
and hence
$\lim _{k\rightarrow \infty }\Vert T(x_{k})-x_{k}\Vert =0$
. This together with the boundedness of
$\{x_{k}\}$
and Browder’s demiclosedness principle [Reference Bauschke and Combettes3, Theorem 4.27] shows that
$\text {Fix}(T)\neq \emptyset $
.
4.2 Strong convergence and iteration complexity results
In this subsection, we first establish the convergence of iterates generated by Algorithm 4.1.
Theorem 4.4. Let
$\{x_{k}\}$
be a sequence generated by Algorithm 4.1. Assume that Assumption 4.2 holds for
$\{(\lambda _{k,0},\lambda _{k,1},\ldots ,\lambda _{k,l-1})\}$
and
$\{\beta _{k}\}$
.
-
(1) If $\mathrm {Fix}(T)\neq \emptyset $
, then
$x_{k}\rightarrow P_{\mathrm {Fix}(T)}x_{0}$
. -
(2) If $\{x_{k}\}$
is unbounded, then
$\mathrm {Fix}(T)=\emptyset $
.
Proof.
Next, we establish iteration complexity results for Algorithm 4.1.
Theorem 4.5. Let
$\{x_{k}\}$
be a sequence generated by Algorithm 4.1 and assume that
$\mathrm {Fix}(T)\neq \emptyset $
. Then the following statements hold:
-
(1) $\min _{0\le i\le k}\Vert x_{i+1}-x_{i}\Vert =o(1/\sqrt {k})$
; -
(2) if $\mathcal {S} = \{0\}$
and Assumption 4.2 holds for
$\{\lambda _{k,0}\}$
and
$\{\beta _{k}\}$
, then $$ \begin{align*}\min_{0\le i\le k}\Vert Tx_{i}-x_{i}\Vert=o(1/\sqrt{k}).\end{align*} $$
Proof. (1) Using (4.1), summing from
$j = 0$
to l gives
where the last inequality follows from
$\textrm {Fix}(T)\subset C_{l}\cap Q_{l}$
. Let 
and 
for each k. Then
$\{a_k\}$
is nonincreasing and converges to
$0$
from (4.1). Furthermore,
By taking
$l\rightarrow \infty $
, we see that
$\sum _{j=0}^{\infty }a_{j}b_{j}<\infty $
. It follows from Lemma 2.2 that
$\min _{0\le i\le k}\Vert x_{i+1}-x_{i}\Vert ^{2}=o(1/{k})$
and hence
$\min _{0\le i\le k}\Vert x_{i+1}-x_{i}\Vert =o(1/\sqrt {k})$
.
(2) In this case, Algorithm 4.1 becomes (1.2). From the definition of
$w_{k}$
,
and hence
It follows from (2.1) that
and hence
On the other hand, from the definition of
$C_{k}$
and Lemma 2.3,
for all
$z\in C_{k}$
. This implies that
$\tfrac 12(w_{k}+y_{k})=P_{C_{k}}y_{k}$
. Since
$x_{k+1}\in C_{k}$
and
$w_{k}-y_{k}=\beta _{k}(w_{k}-Tw_{k})$
,
This together with (4.2) and (4.3) yields
The result now follows by a similar argument to that in (1).
Remark 4.6. Theorem 4.4 includes the corresponding results in [Reference Bauschke and Combettes2, Corollary 6.6(ii)], [Reference Nakajo and Takahashi15, Theorem 3.4] and [Reference Dong, Yuan, Je and Rassias7, Theorem 4.1] as special cases.
To the best of our knowledge, Theorem 4.5 is the first iteration complexity result for the projection algorithm for nonexpansive mappings.
