Open AccessFeature PaperArticle

Douglas–Rachford Splitting Method with Linearization for the Split Feasibility Problem

College of Science, Civil Aviation University of China, Tianjin 300300, China

Department of Mathematics, NanChang University, Nanchang 330031, China

Department of Mathematics and Engineering Sciences, Hellenic Military Academy, 16673 Vari Attikis, Greece

⁴

Program in Interdisciplinary Studies, Institute for Advanced Study, 1 Einstein Drive, Princeton, NJ 08540, USA

Author to whom correspondence should be addressed.

Symmetry 2022, 14(3), 537; https://doi.org/10.3390/sym14030537

Submission received: 5 February 2022 / Revised: 24 February 2022 / Accepted: 25 February 2022 / Published: 6 March 2022

(This article belongs to the Special Issue Symmetry in Nonlinear Analysis and Fixed Point Theory)

Download

Browse Figures

Versions Notes

Abstract

The aim of this article is to introduce the Douglas–Rachford splitting method with linearization to solve the split feasibility problem (SFP). Our proposed method includes two existing methods in work of Tang et al. and Wang as special cases. The ranges of the parameters in work of Tang et al. are extended from (0,1) to (0,2). Under standard conditions, we prove the weak convergence of proposed algorithms. We also provide two numerical experiments to illustrate the effectiveness of the proposed algorithm by comparing the algorithms in work of Tang et al. and Wang.

Keywords:

split feasibility problem; Douglas–Rachford splitting method with linearization; relaxed Douglas–Rachford splitting method with linearization; CQ algorithm

MSC:

47H05; 47H07; 47H10; 54H25

1. Introduction

In this article, we consider the split feasibility problem (SFP) in the form

find x^{*} \in C and A x^{*} \in Q,

(1)

where C and Q are the nonempty closed convex subsets of the real Hilbert spaces

H_{1}

and

H_{2}

, respectively, and

A : H_{1} \to H_{2}

is a bounded linear operator. The SFP was introduced by Censor and Elfving [1] for inverse problems which arise from phase retrievals and medical image reconstruction [2] and were later generalized to the multiple-sets split feasibility problem [3].

Throughout this article, we assume that the SFP (1) is consistent, i.e., its solution set, denoted by

Γ = {x | x \in C and A x \in Q},

is nonempty.

By transforming the SFP as an equivalent constrained optimization problem, Byrne [2,4] firstly introduced the well-known CQ algorithms, which have received a great deal of attention from many authors, who improved it in various ways; see, e.g., [5,6,7,8,9,10,11,12].

To solve the SFP (1), Wang [13] introduced the following gradient method which was called Polyak’s gradient method:

x^{k + 1} = x^{k} - τ_{k} [(x^{k} - P_{C} x^{k}) + A^{*} (I - P_{Q}) A x^{k}],

(2)

where

τ_{k} = ρ_{k} \frac{∥ x^{k} - P_{C} x^{k} ∥^{2} + | | (I - P_{Q}) A x^{k} {| |}^{2}}{2 ∥ (x^{k} - P_{C} x^{k}) + A^{*} (I - P_{Q}) A x^{k} ∥^{2}},

and

ρ_{k} \in (0, 2) .

In fact, (2) is a special case of the so-called simple projection method in [14]. The authors [15] proposed an iterative method for solving the multiple-sets split feasibility problem with splitting self-adaptive stepsizes, which reduces to the following scheme when applied to the SFP (1):

x^{k + 1} = x^{k} - [μ_{k} (x^{k} - P_{C} x^{k}) + ν_{k} A^{*} (I - P_{Q}) A x^{k}],

(3)

where

μ_{k} \in (0, 1)

and

ν_{k} = σ_{k} \frac{∥ (I - P_{Q}) A x^{k} ∥^{2}}{∥ A^{*} (I - P_{Q}) A x^{k} ∥^{2}},

and

σ_{k} \in (0, 1) .

Note that the difference of the schemes (2) and (3) is the choices of the stepsizes.

The Douglas–Rachford splitting method introduced in [16] is a popular method to solve structured optimization problems. Let g and h be proper lower semicontinuous convex functions from a Hilbert space

H

(- \infty, + \infty)

. Consider the structured optimization problem:

min_{x \in H} g (x) + h (x) .

Given the initial guess

x^{0}

, the Douglas–Rachford splitting method generates the iterative sequence via the following scheme:

\{\begin{matrix} y^{k + 1} = \underset{x \in H}{argmin} \{g (y) + \frac{1}{2 λ_{k}} | | y - x^{k} {| |}^{2}\}, \\ z^{k + 1} = \underset{z \in H}{argmin} \{h (z) + \frac{1}{2 λ_{k}} | | z - (2 y^{k + 1} - x^{k}) {| |}^{2}\}, \\ x^{k + 1} = x^{k} + α_{k} (z^{k + 1} - y^{k + 1}), \end{matrix}

(4)

where

{α_{k}}_{k \in N} \subset (0, 2)

is a parameter sequence and

{λ_{k}}_{k \in N} \subset (0, \infty)

is the proximal parameter sequence of the regularization terms. Note that the scheme (4) with

{α_{k}}_{k \in N} \subset (0, + \infty)

was called the general splitting method in [17] and becomes the Peaceman–Rachford splitting method when

{α_{k}}_{k \in N} \subset [2, + \infty) .

It is easy to see that the split feasibility problem (1) also equals the following unconstrained minimization problem:

min_{x \in H_{1}} \{ι_{C} (x) + f (x)\},

(5)

where

f (x) = \frac{1}{2} {∥ (I - P_{Q}) A x ∥}^{2}

and

ι_{C} (x)

is the indicator function of the set C; that is,

ι_{C} (x) = 0

x \in C

, otherwise

ι_{C} (x) = + \infty

. Recall that the gradient of

f (x)

\nabla f (x) = A^{*} (I - P_{Q}) A x

. Letting

g = f

and

h = ι_{C}

in (4) and using the linearization technique, the authors [18] recently introduced the following general splitting methods with linearization for the SFP (1):

\{\begin{matrix} y^{k + 1} : = x^{k} - λ_{k} \nabla f (x^{k}), \\ z^{k + 1} : = P_{C} (2 y^{k + 1} - x^{k}), \\ x^{k + 1} : = x^{k} + α_{k} (z^{k + 1} - y^{k + 1}), \end{matrix}

(6)

where

{α_{k}}_{k \in N}

is a sequence of positive numbers and

λ_{k} : = \{\begin{matrix} γ \frac{f (x^{k})}{∥ \nabla f (x^{k}) ∥^{2}}, & if \nabla f (x^{k}) \neq 0, \\ 0, & otherwise, \end{matrix}

and

γ \in (0, 2) .

The weak convergence of the algorithm (6) was established under the standard conditions, and the algorithm (6) has good numerical performance comparing the algorithm (2) and Algorithm 3.1 in [10].

In this article, we present an iterative scheme by letting

g = ι_{C}

and

h = f

in (4) and using the linearization technique. The convergence of the corresponding scheme is analyzed.

The rest of the paper is constructed as follows. In Section 2, we recall some definitions and known results for further analysis. In Section 3, we present the Douglas–Rachford splitting method with linearization and its relaxed version. In Section 4, we show the weak convergence of the proposed algorithm, which converges weakly to a solution of the SFP. In Section 5, we give two numerical experiments to show the behavior of the algorithm. Finally, some concluding remarks are given in Section 6.

2. Preliminaries

Let

H

be a Hilbert space and K be a nonempty closed convex subset of

H

. We use the notation:

⇀ for weak convergence and → for strong convergence;
$ω_{w} (x^{k}) = {x : \exists x^{k_{l}} ⇀ x}$ denotes the weak $ω$ -limit set of ${x^{k}}_{k \in N}$ .

The following identity will be used for the main results (see [19], Corollary 2.15):

{∥ α x + (1 - α) y ∥}^{2} = {α ∥ x ∥}^{2} + {(1 - α) ∥ y ∥}^{2} - α (1 - α) {∥ x - y ∥}^{2}

(7)

for all

α \in R

and

(x, y) \in H \times H

Definition 1

([19], Definition 6.38). Let K be a nonempty convex subset of

H

and let

x \in H

. The normal cone to K at x is

N_{K} (x) = \{\begin{matrix} \{u \in H | sup 〈 K - x, u 〉 \leq 0\}, & if x \in K; \\ \emptyset, & otherwise . \end{matrix}

For a point x, the the classical metric projection of x onto K, denoted by

P_{K} (x)

, is defined by

P_{K} (x) : = argmin {∥ x - y ∥ : \forall y \in K} .

Lemma 1

([19], Proposition 4.4). For any

x, y \in H

and

z \in K

, the following hold:

(i): $∥ P_{K} (x) - P_{K} {(y) ∥}^{2} \leq 〈 P_{K} (x) - P_{K} (y), x - y 〉;$
(ii): $∥ P_{K} {(x) - z ∥}^{2} \leq {∥ x - z ∥}^{2} - {∥ P_{K} (x) - x ∥}^{2}$ ;
(iii): $〈 (I - P_{K}) x - (I - P_{K}) y, x - y 〉 \geq {∥ (I - P_{K}) x - (I - P_{K}) y ∥}^{2} .$

It follows from Lemma 1 (iii) that

〈 x - P_{K} (x), x - z 〉 \geq {∥ x - P_{K} (x) ∥}^{2}, \forall x \in H, \forall z \in K .

(8)

Recall that a mapping

T : H \to H

is called to be nonexpansive if

∥ T x - T y ∥ \leq ∥ x - y ∥, \forall x, y \in H .

Lemma 1 (i) implies that

P_{K}

is firmly nonexpansive and consequently nonexpansive.

The next lemma shows that the nonexpansive mappings are demiclosed at 0.

Lemma 2

([19], Theorem 4.27). Let K be a nonempty closed convex subset of

H

and

T : K \to H

be a nonexpansive mapping. Let

{x^{k}}_{k \in N}

be a sequence in K and

x \in H

such that

x^{k} ⇀ x

and

T x^{k} - x^{k} \to 0

k \to + \infty

. Then

x \in Fix (T)

Lemma 3

([19], Lemma 2.47). Let K be a nonempty closed convex subset of

H

and

{x^{k}}_{k \in N}

be a sequence in

H

such that the following two conditions hold:

(i): For all $x \in K$ , ${lim}_{n \to \infty} ∥ x^{k} - x ∥$ exists;
(ii): Every sequential weak cluster point of ${x^{k}}_{k \in N}$ is in K.

Then the sequence

{x^{k}}_{k \in N}

converges weakly to a point in K.

3. Douglas–Rachford Splitting Method with Linearization

In this section, we introduce Douglas–Rachford splitting method with linearization and its relaxed variant.

Using symmetry, we can set

g = ι_{C}

and

h = f

in (4). Now, we present a direct adaptation of the Douglas–Rachford splitting method (4), which can solve the equivalent problem (5) of the SFP (1). (see Algorithm 1)

Algorithm 1 Douglas–Rachford splitting method.

Step 0. Input $k : = 0$ , $x^{0} \in H_{1}$ .
Step 1. Generate $x^{k + 1}$ by

$\{\begin{matrix} y^{k + 1} : = P_{C} (x^{k}), \\ z^{k + 1} : = \underset{z \in H_{1}}{argmin} \{f (z) + \frac{1}{2 λ_{k}} {∥ z - (2 y^{k + 1} - x^{k}) ∥}^{2}\}, \\ x^{k + 1} : = x^{k} + α_{k} (z^{k + 1} - y^{k + 1}), \end{matrix}$

(9)

where ${α_{k}}_{k \in N}$ and ${λ_{k}}_{k \in N}$ are sequences of positive numbers.
Step 2. If a termination criterion is not met, then set $k : = k + 1$ and go to Step 1.

By the first-order optimality condition of the second formula of (9) in Algorithm 1,

\begin{matrix} 0 = \nabla f (z^{k + 1}) + \frac{1}{λ_{k}} [z^{k + 1} - (2 y^{k + 1} - x^{k})] \\ = A^{*} (I - P_{Q}) A z^{k + 1} + \frac{1}{λ_{k}} [z^{k + 1} - (2 y^{k + 1} - x^{k})] . \end{matrix}

To calculate

z^{k + 1}

, we need to get

{(I + λ_{k} A^{*} (I - P_{Q}) A)}^{- 1}

, which is very difficult. In order to overcome this difficulty, we linearize

f (z)

x^{k}

. Then, the second formula of (9) becomes

\begin{array}{l} z^{k + 1} : & = \underset{z \in H_{1}}{argmin} \{f (x^{k}) + 〈 \nabla f (x^{k}), z - x^{k} 〉 + \frac{1}{2 λ_{k}} {∥ z - (2 y^{k + 1} - x^{k}) ∥}^{2}\} \\ = \underset{z \in H_{1}}{argmin} \{〈 \nabla f (x^{k}), z - x^{k} 〉 + \frac{1}{2 λ_{k}} {∥ z - (2 y^{k + 1} - x^{k}) ∥}^{2}\} . \end{array}

Its first-order optimality condition is

\nabla f (x^{k}) + \frac{1}{λ_{k}} [z^{k + 1} - (2 y^{k + 1} - x^{k})] = 0 .

Then we have

z^{k + 1} = 2 y^{k + 1} - x^{k} - λ_{k} \nabla f (x^{k}) .

Thus, we get the following linearized Douglas–Rachford splitting method:

\{\begin{matrix} y^{k + 1} : = P_{C} (x^{k}), \\ z^{k + 1} : = 2 y^{k + 1} - x^{k} - λ_{k} \nabla f (x^{k}), \\ x^{k + 1} : = x^{k} + α_{k} (z^{k + 1} - y^{k + 1}) . \end{matrix}

After a simple calculation, we get

x^{k + 1} : = x^{k} + α_{k} [P_{C} (x^{k}) - x^{k} - λ_{k} \nabla f (x^{k})] .

In what follows, we present the Douglas–Rachford splitting method with linearization. (see Algorithm 2)

Algorithm 2 Douglas–Rachford splitting method with linearization.

Step 0. Input $k : = 0$ , $x^{0} \in H_{1}$ .
Step 1. Given $x^{k}$ , generate $x^{k + 1}$ by

$x^{k + 1} : = x^{k} - α_{k} [(x^{k} - P_{C} (x^{k})) + λ_{k} A^{*} (I - P_{Q}) A x^{k}],$

where ${α_{k}}_{k \in N}$ and ${λ_{k}}_{k \in N}$ are two sequences of positive numbers.
Step 2. If $\nabla f (x^{k}) = 0$ and $x^{k + 1} = x^{k}$ , then terminate. Otherwise, set $k : = k + 1$ and go to Step 1.

Remark 1.

Algorithm 2 is a general scheme with two parameters sequences

{α_{k}}_{k \in N}

and

{λ_{k}}_{k \in N}

, which includes the algorithms (2) and (3) as special cases. Indeed,

(i): Let $α_{k} = τ_{k}$ and $λ_{k} \equiv 1$ , $\forall k \in N;$ then, Algorithm 2 becomes the algorithm (2);
(ii): Let $α_{k} = μ_{k}$ and $λ_{k} = \frac{ν_{k}}{μ_{k}},$ $\forall k \in N;$ then, Algorithm 2 becomes the algorithm (3).

In the following, we extend the ranges of the parameter sequences

{μ_{k}}_{k \in N}

and

{σ_{k}}_{k \in N}

in the algorithm (3). To this end, let

α_{k} = β_{k} θ

and

λ_{k} = \frac{(1 - β_{k}) ρ}{α_{k}} η_{k},

where

β_{k} \in (0, 1),

θ \in (0, 2)

ρ \in (0, 2)

and

η_{k} = \frac{∥ (I - P_{Q}) A x^{k} ∥^{2}}{∥ A^{*} (I - P_{Q}) A x^{k} ∥^{2}} .

Then, Algorithm 2 becomes

x^{k + 1} = x^{k} - β_{k} θ (x^{k} - P_{C} (x^{k})) - (1 - β_{k}) ρ η_{k} A^{*} (I - P_{Q}) A x^{k} .

(10)

Note that

β_{k} θ \in (0, 2)

and

(1 - β_{k}) ρ \in (0, 2)

. Comparing (3) and (10), the ranges of the parameter sequences

{μ_{k}}_{k \in N}

and

{σ_{k}}_{k \in N}

in the algorithm (3) are extended from (0,1) to (0,2). It is worth noting that

{μ_{k}}_{k \in N}

and

{σ_{k}}_{k \in N}

cannot both be in (1,2). In fact, one is in (0,2), while the other is in (0,1). Due to

α_{k} \in (0, 2)

, Algorithm 2 is the Douglas–Rachford splitting method with linearization.

We give two choices of

β_{k}

, as follows:

Constant choice: $β_{k} : = β \in (0, 1)$ for all $k \in N$ ;
Adaptive choice: Let $\underset{̲}{β}, \bar{β} \in (0, 1)$ ,

$β_{k}^{*} = \frac{1}{2} + \frac{θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2} - ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2}}{2 {∥θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2}},$

(11)

and $β_{k} = max {\underset{̲}{β}, min {β_{k}^{*}, \bar{β}}}$ .

Note that the upper and lower bounds are imposed in the adaptive choice of

β_{k}

to guarantee

β_{k} \in (0, 1)

. Therefore, it is not fully adaptive.

Now, the following lemma shows the validity of the stopping criterion through Step 2 of the Douglas–Rachford splitting method with linearization.

Lemma 4.

\nabla f (x^{k}) = 0

and

x^{k + 1} = x^{k}

for some k, then

x^{k}

generated by Algorithm 2 is a solution of the SFP (1).

Proof.

Using

\nabla f (x^{k}) = 0

and

x^{k + 1} = x^{k}

, we get

x^{k} = P_{C} (x^{k})

, which implies

x^{k} \in C .

Thus,

0 \in N_{C} (x^{k}) .

We deduce that

x^{k}

is a solution of the SFP (1) because of the first-order optimality condition

0 \in N_{C} (x) + \nabla f (x)

of problem (5). □

In Algorithm 2, we generally assume that the projections

P_{C}

and

P_{Q}

are easy to calculate. However, projection is sometimes impossible or difficult to calculate. In order to solve this problem, we consider a general situation of C and Q in SFP (1).

C = {x \in H_{1} : c (x) \leq 0}

and

Q = {y \in H_{2} : q (y) \leq 0}

are level sets, where

c : H_{1} \to R

and

q : H_{2} \to R

are convex functions. We assume that

\partial c

and

\partial q

are bounded operators and define the sets

C_{k}

and

Q_{k}

as follows:

C_{k} = \{x \in H_{1} : c (x^{k}) + 〈 ξ^{k}, x - x^{k} 〉 \leq 0\},

where

ξ^{k} \in \partial c (x^{k})

, and

Q_{k} = \{y \in H_{2} : q (A x^{k}) + 〈 η^{k}, y - A x^{k} 〉 \leq 0\},

where

η^{k} \in \partial q (A x^{k})

Next, we define

f_{k} (x) : = \frac{1}{2} {∥ (I - P_{Q_{k}}) A x ∥}^{2}

and introduce the relaxed Douglas–Rachford splitting method with linearization. (see Algorithm 3)

Algorithm 3 Relaxed Douglas–Rachford splitting method with linearization.

Step 0. Input $k : = 0$ , $x^{0} \in H_{1}$ .
Step 1. Given $x^{k}$ , generate $x^{k + 1}$ by

$x^{k + 1} : = x^{k} - α_{k} [(x^{k} - P_{C_{k}} (x^{k})) + λ_{k} A^{*} (I - P_{Q_{k}}) A x^{k}],$

(12)

where ${α_{k}}_{k \in N}$ and ${λ_{k}}_{k \in N}$ are two sequences of positive numbers.
Step 2. If $\nabla f_{k} (x^{k}) = 0$ and $x^{k + 1} = x^{k}$ , then terminate. Otherwise, set $k : = k + 1$ and go to Step 1.

4. Convergence Analysis

In this section, we prove the weak convergence of Algorithm 2 under the standard conditions.

Firstly, we present two lemmas which are key for the convergence of Algorithm 2.

Lemma 5.

Let

{x^{k}}_{k \in N}

be the sequence generated by Algorithm 2 from any initial point

x^{0} \in H_{1}

and

x^{*} \in Γ

. Let

β_{k} \equiv β \in (0, 1),

\forall k \in N .

Then it holds

\begin{array}{l} {∥x^{k + 1} - x^{*}∥}^{2} \leq & {∥x^{k} - x^{*}∥}^{2} - β θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2} \\ - (1 - β) ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2} \\ - β (1 - β) {∥θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2} . \end{array}

(13)

Proof.

By (10) and (7), we have

\begin{matrix} {∥x^{k + 1} - x^{*}∥}^{2} \\ = {∥ β_{k} [x^{k} - θ (x^{k} - P_{C} (x^{k})) - x^{*}] + (1 - β_{k}) [x^{k} - ρ η_{k} A^{*} (I - P_{Q}) A x^{k} - x^{*}] ∥}^{2} \\ = β {∥x^{k} - x^{*} - θ (x^{k} - P_{C} (x^{k}))∥}^{2} \\ + (1 - β) {∥x^{k} - x^{*} - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2} \\ - β (1 - β) {∥θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2} . \end{matrix}

(14)

Using (8), we get

〈x^{k} - x^{*}, x^{k} - P_{C} (x^{k})〉 \geq {∥x^{k} - P_{C} (x^{k})∥}^{2},

(15)

and

〈x^{k} - x^{*}, A^{*} (I - P_{Q}) A x^{k}〉 = 〈A x^{k} - A x^{*}, (I - P_{Q}) A x^{k}〉 \geq {∥(I - P_{Q}) A x^{k}∥}^{2} .

(16)

By (15), we obtain

\begin{matrix} {∥x^{k} - x^{*} - θ (x^{k} - P_{C} (x^{k}))∥}^{2} \\ = {∥x^{k} - x^{*}∥}^{2} + θ^{2} {∥x^{k} - P_{C} (x^{k})∥}^{2} - 2 θ 〈x^{k} - x^{*}, x^{k} - P_{C} (x^{k})〉 \\ \leq {∥x^{k} - x^{*}∥}^{2} - θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2} . \end{matrix}

(17)

From (16) and the definition of

η_{k}

, it follows

\begin{matrix} {∥x^{k} - x^{*} - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2} \\ = {∥x^{k} - x^{*}∥}^{2} + ρ^{2} η_{k}^{2} {∥A^{*} (I - P_{Q}) A x^{k}∥}^{2} - 2 ρ η_{k} 〈x^{k} - x^{*}, A^{*} (I - P_{Q}) A x^{k}〉 \\ \leq {∥x^{k} - x^{*}∥}^{2} + ρ^{2} η_{k}^{2} {∥A^{*} (I - P_{Q}) A x^{k}∥}^{2} - 2 ρ η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2} \\ = {∥x^{k} - x^{*}∥}^{2} - ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2} . \end{matrix}

(18)

Combining (14), (17) and (18), we deduce (13). The proof is completed. □

Remark 2.

The inequality (13) with the ranges of the parameters

β, θ, ρ

shows the monotonically decreasing property of the sequence

{∥ x^{k} - x^{*} {| |}}_{k \in N}

. It is not the same as the inequality in [15], and the latter reduces to the following form for the SFP (1):

{∥x^{k + 1} - x^{*}∥}^{2} \leq {∥x^{k} - x^{*}∥}^{2} - 2 μ_{k} (1 - μ_{k}) {∥x^{k} - P_{C} (x^{k})∥}^{2} - 2 σ_{k} (1 - σ_{k}) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2} .

It is difficult to compare them and show which is better in theory. The numerical experiments in Section 5 illustrate that the optimal choices of the parameters of

{μ_{k}}_{k \in N}

and

{σ_{k}}_{k \in N}

is that one is in (0,2) while the others are in (0,1).

Lemma 6.

Let

{x^{k}}_{k \in N}

be the sequence generated by Algorithm 2 from any initial point

x^{0} \in H_{1}

x^{*} \in Γ

. Let

β_{k}

is given adaptively.

(i): If $β_{k}^{*} \in [\underset{̲}{β}, \bar{β}]$ , it holds

$\begin{matrix} {∥x^{k + 1} - x^{*}∥}^{2} \\ \leq {∥x^{k} - x^{*}∥}^{2} - \frac{1}{2} θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2} \\ - \frac{1}{2} ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2} \\ - \frac{1}{4} {∥θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2} \\ - \frac{{[θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2} - ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2}]}^{2}}{4 {∥θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2}}; \end{matrix}$

(19)
(ii): If $β_{k}^{*} \notin [\underset{̲}{β}, \bar{β}]$ , it holds

$\begin{matrix} {∥x^{k + 1} - x^{*}∥}^{2} \leq {∥x^{k} - x^{*}∥}^{2} - \underset{̲}{β} θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2} \\ - (1 - \bar{β}) ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2} \\ - (\underset{̲}{β} - {\bar{β}}^{2}) {∥θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2} . \end{matrix}$

(20)

Proof.

(i) In this case,

β_{k} = β_{k}^{*}

. Similar to Lemma 5, we have

\begin{matrix} {∥x^{k + 1} - x^{*}∥}^{2} \leq {∥x^{k} - x^{*}∥}^{2} - β_{k} θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2} \\ - (1 - β_{k}) ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2} \\ - β_{k} (1 - β_{k}) {∥θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k}∥}^{2} . \end{matrix}

(21)

Let

\begin{matrix} d_{k} = θ (2 - θ) {∥x^{k} - P_{C} (x^{k})∥}^{2}, \\ e_{k} = ρ (2 - ρ) η_{k} {∥(I - P_{Q}) A x^{k}∥}^{2}, \\ m_{k} = {∥ θ (x^{k} - P_{C} (x^{k})) - ρ η_{k} A^{*} (I - P_{Q}) A x^{k} ∥}^{2} . \end{matrix}

The inequality (21) becomes

∥ x^{k + 1} - x^{*} ∥^{2} \leq {∥ x^{k} - x^{*} ∥}^{2} - β_{k} d_{k} - (1 - β_{k}) e_{k} - β_{k} (1 - β_{k}) m_{k} .

(22)

After simple calculations, we get

\begin{matrix} - β_{k} d_{k} - (1 - β_{k}) e_{k} - β_{k} (1 - β_{k}) m_{k} \\ = m_{k} β_{k}^{2} - (d_{k} - e_{k} + m_{k}) β_{k} - e_{k} \\ = m_{k} {(β_{k} - \frac{d_{k} - e_{k} + m_{k}}{2 m_{k}})}^{2} - m_{k} {(\frac{1}{2} + \frac{d_{k} - e_{k}}{2 m_{k}})}^{2} - e_{k} \\ = - \frac{1}{2} d_{k} - \frac{1}{2} e_{k} - \frac{m_{k}}{4} - \frac{{(d_{k} - e_{k})}^{2}}{4 m_{k}}, \end{matrix}

(23)

where the last equality holds due to (11). Combining (22) and (23), we get (19);

(ii) In this case,

β_{k} = \underset{̲}{β}

β_{k} = \bar{β}

. By Lemma 5, it is easy to obtain (20). □

Theorem 1.

Let

{x^{k}}_{k \in N}

be generated by Algorithm 2; then,

{x^{k}}_{k \in N}

converges weakly to a solution of the SFP (1).

Proof.

By (13), (19) and (20), we have

∥ x^{k + 1} - x^{*} ∥ \leq ∥ x^{k} - x^{*} ∥,

which implies that

{x^{k}}_{k \in N}

is bounded and

{lim}_{k \to \infty} ∥ x^{k} - x^{*} ∥

exists. From the definition of

η_{k}

, it follows

η_{k} = \frac{∥ (I - P_{Q}) A x^{k} ∥^{2}}{∥ A^{*} (I - P_{Q}) A x^{k} ∥^{2}} \geq \frac{∥ A x^{k} - P_{Q} (A x^{k}) ∥^{2}}{{∥ A ∥}^{2} {∥ A x^{k} - P_{Q} (A x^{k}) ∥}^{2}} = \frac{1}{{∥ A ∥}^{2}} .

(24)

Combining (13), (19), (20) and (24), we deduce

lim_{k \to \infty} ∥ P_{C} (x^{k}) - x^{k} ∥ = 0,

(25)

and

lim_{k \to \infty} ∥ (I - P_{Q}) A x^{k} ∥ = 0 .

(26)

To use Lemma 3, we need to show

ω_{w} (x^{k}) \subseteq Γ

. To this end, take arbitrarily

\hat{x} \in ω_{w} (x^{k})

and let

x^{k_{l}} ⇀ \hat{x}

where

{x^{k_{l}}}_{l \in N}

is a subsequence of

{x^{k}}_{k \in N}

. From Lemma 2 and (25), we get

\hat{x} \in C

. Combining (26) and the weak lower semicontinuity of f, we obtain

0 \leq f (\hat{x}) \leq \underset{l \to \infty}{lim inf} f (x^{k_{l}}) = lim_{k \to \infty} f (x^{k}) = 0 .

Hence,

f (\hat{x}) = \frac{1}{2} ∥ (I - P_{Q}) A \hat{x} ∥ = 0

, i.e.,

A \hat{x} \in Q

. Thus, we have

ω_{w} (x^{k}) \subseteq Γ

. By Lemma 3, we deduce that

{x^{k}}_{k \in N}

converges weakly to a point in

Γ

. The proof is completed. □

Combining Theorem 1 and [18] (Theorem 3.2), it is easy to verify the convergence of Algorithm 3.

Theorem 2.

Let

{x^{k}}_{k \in N}

be generated by Algorithm 3; then,

{x^{k}}_{k \in N}

converges weakly to a solution of the SFP (1).

5. Numerical Results

In this section, we show the behavior of Algorithm 2 by comparing it with the algorithms (3) and (2) through two numerical examples.

For convenience, we denote the vector with all elements 0 by

e_{0}

and the vector with all elements 1 by

e_{1}

in what follows. In the next two numerical examples, we take the objective function value

p (x) = \frac{1}{2} ∥ x - P_{C} {(x) ∥}^{2} + \frac{1}{2} {∥ A x - P_{Q} (A x) ∥}^{2} \leq ϵ

as the stopping criterion.

Example 1

([6]). Consider the SFP, where

A = {(a_{i j})}_{m \times n} \in R^{m \times n}

(

m = 200, n = 500

) and

a_{i j} \in (0, 1)

generated randomly and

\begin{matrix} C = {x \in R^{n} : ∥ x - d ∥ \leq r}, \\ Q = {y \in R^{m} : L \leq y \leq U}, \end{matrix}

where d is the center of the ball C,

e_{0} \leq d \leq e_{1}

r \in (10, 20)

is the radius, d and r are both generated randomly. L and U are the boundary of the box Q and are also generated randomly, satisfying

10 e_{1} \leq L \leq 20 e_{1}

and

20 e_{1} \leq U \leq 30 e_{1}

, respectively.

In the numerical experiment, we take the objective function value

p (x^{k}) \leq ϵ = 10^{- 5}

as the stopping criterion.

In Figure 1, the initial point

x^{0} \in (0, 100 e_{1})

is randomly chosen. For comparing Algorithm 2 with the algorithms (2) and (3), we take

θ = 1.59

ρ = 1.86

and

β_{k} \equiv β = 0.37

in Algorithm 2,

ρ_{k} = 1.99

in the algorithm (2) and

μ_{k} = 0.72

and

ν_{k} = 0.88

in the algorithm (3).

In Table 1, we show the iteration steps and CPU time of Algorithm 2, algorithm (2) and algorithm (3) for 3 initial points. For case 1,

x^{0} = (100, \dots, 100)

; for case 2,

x^{0}

= (100, −100, ⋯, 100, −100); and for case 3,

x^{0} \in (- 100 e_{1}, 100 e_{1})

As shown in Figure 1 and the iteration steps in Table 1, Algorithm 2 behaves better than the algorithms (2) and (3).

Example 2.

Suppose that

H_{1} = H_{2} = L^{2} ([0, 1])

with norm

∥ x ∥ = {(\int_{0}^{1} {| x (t) |}^{2} d t)}^{\frac{1}{2}}

and inner product

〈 x, y 〉 = \int_{0}^{1} x (t) y (t) d t .

Let

C : = {x \in H_{1} : 〈 a, x 〉 = b},

where

a = sin (5 t^{3})

and

b = 0

. In this case, we have

P_{C} (x) = x + \frac{b - 〈 a, x 〉}{{∥ a ∥}^{2}} a .

Additionally, let

Q : = {x \in H_{2} : 〈 c, x 〉 \leq d},

where

c = sin (t / 4)

and

d = 1 / 5

; then, we obtain

P_{Q} (x) = \{\begin{matrix} x & if 〈 c, x 〉 \leq d \\ x + \frac{d - 〈 c, x 〉}{{∥ c ∥}^{2}} c & if 〈 c, x 〉 > d . \end{matrix}

Consider the matrix

A = \frac{1}{200} {(\begin{matrix} 0 & 0 & 0 & \dots & 0 & 0 \\ 1 & 1 & 0 & \dots & 0 & 0 \\ 1 & 2 & 1 & \dots & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋱ & ⋮ & ⋮ \\ 1 & 2 & 2 & \dots & 1 & 0 \\ 1 & 2 & 2 & \dots & 2 & 1 \end{matrix})}_{101 \times 101}

resulting from a discretization of the operator question of the first kind

y (t) = (A x) (t) : = \int_{0}^{t} x (s) d s, s, t \in [0, 1]; x, y : [0, 1] ⟶ [0, 1] .

In the numerical experiment, the initial function is

x^{0} (t) = 10 sin (t^{2} + 2 t)

. We take

p (x^{k}) \leq ϵ = 10^{- 10}

as the stopping criterion.

For comparing Algorithm 2 with the algorithms (2) and (3), we take

θ = 1.99

ρ = 1.99

and

β_{k} \equiv β = 0.41

in Algorithm 2,

ρ_{k} = 1.89

in the algorithm (2) and

μ_{k} = 0.5

and

ν_{k} = 0.99

in the algorithm (3). From Figure 2, we can see that the performance of Algorithm 2 is better than the algorithms (2) and (3).

6. Some Concluding Remarks

In this article, we introduce the Douglas–Rachford splitting method with linearization for the split feasibility problem, which is a general method and includes the methods in [13,15] as special cases. The weak convergence of the proposed method is established under the standard conditions. Numerical experiments illustrate the effectiveness of our methods.

The methods proposed in this article can be generalized to solve the multiple-sets split feasibility problem. It is interesting to investigate the other possible choices of the parameters

{α_{k}}_{k \in N}

and

{λ_{k}}_{k \in N}

Recently, some authors have applied self-adaptive step sizes to split generalized equilibrium and fixed point problems [20] and pseudo-monotone equilibrium problems [21]. The numerical examples illustrate that the step sizes have excellent behaviour. Applying the self-adaptive step size to the split feasibility problem is worth investigating.

Author Contributions

Methodology, Z.H. and Q.D.; formal analysis, Z.H. and Q.D.; writing—original draft preparation, Z.H.; writing—review and editing, Q.D., Y.T. and M.T.R. All authors have read and agreed to the published version of the manuscript.

Funding

Funding was provided to this project as the Scientific Research Project of Tianjin Municipal Education Commission (No. 2020ZD02).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

We express our thanks to anonymous referees for their constructive suggestions, which significantly improved the presentation of this paper.

Conflicts of Interest

The authors declare no conflict of interest.

References

Censor, Y.; Elfving, T. A multiprojection algorithm using Bregman projections in a product space. Numer. Algorithms 1994, 8, 221–239. [Google Scholar] [CrossRef]
Byrne, C.L. Iterative oblique projection onto convex sets and the split feasibility problem. Inverse Probl. 2002, 18, 441–453. [Google Scholar] [CrossRef]
Censor, Y.; Elfving, T.; Kopf, N.; Bortfeld, T. The multiple-sets split feasibility problem and its applications for inverse problems. Inverse Probl. 2005, 21, 2071–2084. [Google Scholar] [CrossRef] [Green Version]
Byrne, C.L. A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 2004, 20, 103–120. [Google Scholar] [CrossRef] [Green Version]
Dang, Y.; Sun, J.; Zhang, S. Double projection algorithms for solving the split feasibility problems. J. Ind. Manag. Optim. 2019, 15, 2023–2034. [Google Scholar] [CrossRef] [Green Version]
Dong, Q.L.; Tang, Y.C.; Cho, Y.J.; Rassias, T.M. “Optimal” choice of the step length of the projection and contraction methods for solving the split feasibility problem. J. Glob. Optim. 2018, 71, 341–360. [Google Scholar] [CrossRef]
Dong, Q.L.; Yao, Y.; He, S. Weak convergence theorems of the modified relaxed projection algorithms for the split feasibility problem in hilbert spaces. Optim. Lett. 2014, 8, 1031–1046. [Google Scholar] [CrossRef]
He, S.; Xu, H.K. The selective projection method for convex feasibility and split feasibility problems. J. Nonlinear Sci. Appl. 2018, 19, 1199–1215. [Google Scholar]
Gibali, A.; Liu, L.; Tang, Y.C. Note on the modified relaxation CQ algorithm for the split feasibility problem. Optim. Lett. 2018, 12, 817–830. [Google Scholar] [CrossRef]
López, G.; Martín-Márquez, V.; Wang, F.; Xu, H.K. Solving the split feasibility problem without prior knowledge of matrix norms. Inverse Probl. 2012, 27, 085004. [Google Scholar] [CrossRef]
Qu, B.; Wang, C.; Xiu, N. Analysis on Newton projection method for the split feasibility problem. Comput. Optim. Appl. 2017, 67, 175–199. [Google Scholar] [CrossRef]
Wang, J.; Hu, Y.; Li, C.; Yao, J.C. Linear convergence of CQ algorithms and applications in gene regulatory network inference. Inverse Probl. 2017, 33, 055017. [Google Scholar] [CrossRef]
Wang, F. Polyak’s gradient method for split feasibility problem constrained by level sets. Numer. Algorithms 2018, 77, 925–938. [Google Scholar] [CrossRef]
Zhao, J.; Yang, Q. A simple projection method for solving the multiple-sets split feasibility problem. Inverse Prob. Sci. Eng. 2013, 21, 537–546. [Google Scholar] [CrossRef]
Tang, Y.; Zhu, C.; Yu, H. Iterative methods for solving the multiple-sets split feasibility problem with splitting self-adaptive step size. Fixed Point Theory Appl. 2015, 2015, 178. [Google Scholar] [CrossRef] [Green Version]
Douglas, J.; Rachford, H.H. On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 1956, 82, 421–439. [Google Scholar] [CrossRef]
Li, M.; Wu, Z. Convergence analysis of the generalized splitting methods for a class of nonconvex optimization problems. J. Optimiz. Theory Appl. 2019, 183, 535–565. [Google Scholar] [CrossRef]
Dong, Q.L.; He, S.; Rassias, M.T. General splitting methods with linearization for the split feasibility problem. J. Glob. Optim. 2021, 79, 813–836. [Google Scholar] [CrossRef]
Bauschke, H.H.; Combettes, P.L. Convex Analysis and Monotone Operator Theory in Hilbert Spaces; Springer: New York, NY, USA, 2017; Volume 2. [Google Scholar]
Olona, M.A.; Alakoya, T.O.; Owolabi, A.O.-E.; Mewomo, O.T. Inertial shrinking projection algorithm with self-adaptive step size for split generalized equilibrium and fixed point problems for a countable family of nonexpansive multivalued mappings. Demonstr. Math. 2021, 54, 47–67. [Google Scholar] [CrossRef]
Pakkaranang, N.; Rehman, H.; Kumam, W. Two strongly convergent self-adaptive iterative schemes for solving pseudo-monotone equilibrium problems with applications. Demonstr. Math. 2021, 54, 280–298. [Google Scholar] [CrossRef]

Figure 1. The value of

p (x^{k})

versus the iteration numbers for Example 1.

Figure 1. The value of

p (x^{k})

versus the iteration numbers for Example 1.

Figure 2. The value of

p (x^{k})

versus the iteration numbers for Example 2.

Figure 2. The value of

p (x^{k})

versus the iteration numbers for Example 2.

Table 1. Comparison of Algorithm 2, algorithms (2) and (3) under different initial points.

Cases	Algorithm 2		algorithm (2)		algorithm (3)
Cases	Iter.	CPU Time	Iter.	CPU Time	Iter.	CPU Time
Case 1	18	0.0313	155	0.0313	38	0.0469
Case 2	22	0.0469	372	0.0781	37	0.0469
Case 3	16	0.0313	256	0.0469	35	0.0313

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Hu, Z.; Dong, Q.; Tang, Y.; Rassias, M.T. Douglas–Rachford Splitting Method with Linearization for the Split Feasibility Problem. Symmetry 2022, 14, 537. https://doi.org/10.3390/sym14030537

AMA Style

Hu Z, Dong Q, Tang Y, Rassias MT. Douglas–Rachford Splitting Method with Linearization for the Split Feasibility Problem. Symmetry. 2022; 14(3):537. https://doi.org/10.3390/sym14030537

Chicago/Turabian Style

Hu, Ziyue, Qiaoli Dong, Yuchao Tang, and Michael Th. Rassias. 2022. "Douglas–Rachford Splitting Method with Linearization for the Split Feasibility Problem" Symmetry 14, no. 3: 537. https://doi.org/10.3390/sym14030537

APA Style

Hu, Z., Dong, Q., Tang, Y., & Rassias, M. T. (2022). Douglas–Rachford Splitting Method with Linearization for the Split Feasibility Problem. Symmetry, 14(3), 537. https://doi.org/10.3390/sym14030537

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

Douglas–Rachford Splitting Method with Linearization for the Split Feasibility Problem

Abstract

1. Introduction

2. Preliminaries

3. Douglas–Rachford Splitting Method with Linearization

4. Convergence Analysis

5. Numerical Results

6. Some Concluding Remarks

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Acknowledgments

Conflicts of Interest

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI