Iterative process for solving a multiple-set split feasibility problem: [Doc 576]

Abstract

This paper deals with a variant relaxed CQ algorithm by using a new searching direction, which is not the gradient of a corresponding function. The strategy is to intend to improve the convergence. Its convergence is proved under some suitable conditions. Numerical results illustrate that our variant relaxed CQ algorithm converges more quickly than the existing algorithms.

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 DOI 10.1186/s13660-015-0576-9

R E S E A R C H Open Access

Iterative process for solving a multiple-set split feasibility problem

Yazheng Dang1,2* and Zhonghui Xue3

*Correspondence: mailto:[email protected]

Web End [email protected]

1School of Management, University of Shanghai for Science and Technology, Shanghai, 200093, China

2College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, Henan 454000, China

Equal contributorsFull list of author information is available at the end of the article

Abstract

This paper deals with a variant relaxed CQ algorithm by using a new searching direction, which is not the gradient of a corresponding function. The strategy is to intend to improve the convergence. Its convergence is proved under some suitable conditions. Numerical results illustrate that our variant relaxed CQ algorithm converges more quickly than the existing algorithms.

MSC: 47H05; 47J05; 47J25

Keywords: multiple-set split feasibility problem; subgradient; accelerated iterative algorithm; convergence

1 Introduction

The multiple-set split feasibility problem (MSSFP) is to nd a point contained in the in

tersection of a family of closed convex sets in one space such that its image under a linear

transformation is contained in the intersection of another family of closed convex sets

in the image space. Formally, given nonempty closed convex sets Ci N, i = , , . . . , t, in the N-dimensional Euclidean space N and nonempty closed convex sets Qj M, j = , , . . . , r, and an M N real matrix A, the MSSFP is to nd a point x such that

x C =

t

i=

Qj. (.)

Such MSSFP, formulated in [], arises in the eld of intensity-modulated radiation therapy

(IMRT) when one attempts to describe physical dose constrains and equivalent uniform

dose (EUD) constraints within a single model, see [, ]. Specially, when t = r = , the

problem reduces to the two-set split feasibility problem (abbreviated as SFP), which is to

nd a point x C such that Ax Q (see []).For solving the MSSFP, Censor et al. in [] introduced a proximity function p(x) to mea

sure the aggregate distance of a point to all sets. The function p(x) is dened as

p(x) :=

t

i=

Ci, Ax Q =

r

j=

i x PCi(x) +

j Ax PQj(Ax) ,

2015 Dang and Xue; licensee Springer. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly credited.

r

j=

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 2 of 10

where i > , j > for all i and j, respectively, and t

posed a projection algorithm as follows:

xk+ = P xk p xk ,

where N is an auxiliary set, xk is the current iterative point. < < /L with L = t

i= i + (ATA) rj= j and (ATA) is the spectral radius of ATA. Subsequently, many methods have been developed for solving the MSSFP [], while most of these algorithms aimed at minimizing the proximity function p(x) and used its gradient p.

Dierent from most of the existing methods, in this paper, we construct a new searching direction, which is not the gradient p. And this dierence causes a very dierent way of analysis. Moreover, some preliminary numerical experiments show that our new method converges faster than most existing methods.

The paper is organized as follows. Section reviews some preliminaries. Section gives a variant relaxed projection algorithm and shows its convergence. Section gives some numerical experiments. Some conclusions are drawn in Section .

2 Preliminaries

Throughout the rest of the paper, I denotes the identity operator, Fix(T) denotes the set of the xed points of an operator T, i.e., Fix(T) := {x | x = T(x)}.

Let T be a mapping from N into N. T is called co-coercive on with modulus

> if

T(x) T(y), x y T(x) T(y) , x, y ;

it is called Lipschitz continuous on for constant L > if

T(x) T(y) L x y , x, y ;

it is called monotone on if

T(x) T(y), x y , x, y .

It is obvious that the co-coercivity (with modulus ) implies the Lipschitz continuity (with constant /) and monotonicity.

Let S be a nonempty closed convex subset of N. Denote by PS the orthogonal projection onto S; that is,

PS(x) = arg min

y

N

over all x S.

It is well known that the orthogonal projection operator PS, for any x, y N and any z S, is characterized by the inequalities []

x PS(x), z PS(x) (.)

i= i + rj= j = . Then they pro-

x y ,

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 3 of 10

and

PS(x) z x z PS(x) x . (.)

Recall the notion of the subdierential for an appropriate convex function.

Denition . Let f : N be convex. The subdierential of f at x is dened as

f (x) = N | f (y) f (x) + , y x , y N . (.)

Evidently, an element of f (x) is said to be a subgradient.

Lemma . [] An operator T is co-coercive with modulus if and only if the operator I T is co-coercive with modulus , where I denotes the identity operator.

It is easy to see from the above lemmas that the orthogonal projection operators are monotone, co-coercive with modulus , and the operator I PQ is also co-coercive with modulus .

3 Algorithm and its convergence3.1 The variant relaxed-CQ algorithm

As in [], we suppose that the following conditions are satised:

() The solution set of the MSSFP is nonempty. () The sets Ci, i = , , . . . , t, are denoted as

Ci = x N | ci(x) , (.)

where ci : N , i = , , . . . , t, are appropriately convex and Ci, i = , , . . . , t, are nonempty.

The set Qj, j = , , . . . , r, is denoted as

Qj = y M | qj(y) , (.)

where qj : M , j = , , . . . , r, are appropriately convex and Qj, j = , , . . . , r, are nonempty.

() For any x N, at least one subgradient i ci(x) can be calculated. For any y M, at least one subgradient j qj(y) can be computed.

Now, we dene the following half-spaces at point xk:

Cki = x N | ci xk +

ki , x xk , (.)

where ki is an element in ci(xk) for i = , , . . . , t, and

Qkj = y M | qj Axk + kj, y Axk , (.)

where kj is an element in qj(Axk) for j = , , . . . , r.

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 4 of 10

By the denition of subgradient, it is clear that the half-spaces Cki and Qkj contain Ci and Qj, i = , , . . . , r; j = , , . . . , t, respectively. Due to the specic form of Cki and Qkj, the orthogonal projections onto Cki and Qkj, i = , , . . . , r; j = , , . . . , t, may be computed directly, see [].

Now, we give the variant relaxed CQ algorithm.

Algorithm . Given i > and j such that ti= i = , rj= j = , (,

tk (, ).

For an arbitrary initial point, x n is the current point. Dene a mapping Fk : N N as

Fk(x) =

t

i=

dk = xk yk + Fk yk Fk xk . (.)

xk+ = xk tkdk. (.)

In this algorithm, we can take dk < for some given precision as the stopping criterion. And we apply yk and Fk to construct the searching direction dk. The choice of a new searching direction leads to quite dierent in establishing the convergence result of Algorithm ..

By Lemma . in [], the operator AT(I PQkj )A is /(ATA)-inverse strongly monotone (/(ATA)-ism) or co-coercive with modulus /(ATA) and Lipschitz continuous with (ATA).

3.2 Convergence of the variant relaxed-CQ algorithm

In this subsection, we establish the convergence of Algorithm ..

The following results will be needed in convergence analysis of the proposed algorithm.

Lemma . [, ] Suppose that f : N is convex. Then its subdierential is uniformly bounded on any bounded subsets of N.

Lemma . Assume that z is an arbitrary solution of the MSSFP (i.e., z SOL(MSSFP)) and u N, it holds that

Fk(u), u z

r

j=

(AT A) ),

r

j=

jAT(I PQkj )Ax. (.)

For k = , , , . . . , compute

yk =

iPCk

i

xk Fk xk . (.)

Let

Set

j (I PQ

kj )(Au) . (.)

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 5 of 10

Proof If z SOL(MSSFP), then Az Qj Qkj for all j = , . . . , r, thus Fk(z) = , we have known that the mappings I PQkj are co-coercive with modulus , it follows that

Fk(u), u z = Fk(u) Fk(z), u z

r

j=

= j (AT(I PQkj )Au AT(I PQkj )Az, u z

r

j=

= j (I PQkj )Au (I PQkj )Az, Au Az

r

j=

j (I PQ

kj )Au (I PQkj )Az

r

j=

= j (I PQ

kj )Au .

Now, we state the convergence of Algorithm ..

Theorem . Assume that the set of solutions of the constrained multiple-set split feasibility problem is nonempty. Then any sequence {xk}k= generated by Algorithm . converges to a solution of the multiple-set split feasibility problem.

Proof Let z be a solution of MSSFP. Since Ci Ci,k, Qj Qkj, then z = PCiz = PCi,kz and Az = PQjAz = PQj,kAz for all i and j and therefore Fk(z) = . By Algorithm ., we have

xk+ z = xk tkdk z = xk z tk dk, xk z + tk dk ,

hence

xk+ z = xk z tk dk, yk z tk dk, xk yk + tk dk . (.)

By (.) we have

dk, yk z = xk Fk xk yk, yk z + Fk yk , yk z . (.)

From Lemma ., we obtain

Fk yk , yk z

r

j=

j (I PQ

kj )Ayk . (.)

Let zk = xk Fk(xk). For that t

i= i = , we obtain from (.) that

xk Fk xk yk, yk z = zk yk, yk z

=

t

i=

i zk PCk

i

zk ,

t

i=

iPCk

i

zk z

t

i=

t

h=

= ih zk PCk

i

zk , PCk

h

zk z .

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 6 of 10

If i = h, then zk PC

ki (zk), PCk

h (zk) z , since z Ci Cki by Lemma .. Otherwise, if

i = h, we have

ih zk PCk

i

zk , PCk

h

zk z + hi zk PCk

h

zk , PCk

i

zk z

= ih zk PCk

i

zk , PCk

i

zk z + zk PCk

i

zk , PCk

h

zk PCk

i

zk

+ hi zk PCk

h

zk , PCk

h

zk z + zk PCk

h

zk , PCk

i

zk PCk

h

zk

ih PC

k i

zk PCk

h

zk .

It means

xk kFk xk yk, yk z

i<h

ih PC

k i

zk PCk

h

zk . (.)

By combining (.) and (.) with (.), we obtain

dk, yk z

i<h

ih PC

k i

zk PCk

h

zk +

r

j=

j (I PQ

kj )Ayk . (.)

On the other hand, by denition of dk in (.), we have

dk, xk yk = dk, xk yk + Fk yk kFk xk + dk, Fk xk Fk yk

= dk +

xk yk + Fk yk Fk xk , Fk xk Fk yk

= dk +

xk yk, Fk xk Fk yk Fk xk Fk yk .

From Lemma ., we arrive at xk yk, Fk(xk) Fk(yk) /(ATA) Fk(xk) Fk(yk) for all k, hence

dk, xk yk dk + ATA xk yk, Fk xk Fk yk

= d

k

+

ATA

r

j=

j Axk Ayk,

(I PQkj )Axk (I PQkj )Ayk .

Furthermore, from the -co-coercivity of I PQkj , we have

dk, xk yk dk + ATA

r

j=

j (I PQ

kj )Axk (I PQkj )Ayk . (.)

From (.), (.) and (.), we have

xk+ z = xk z tk dk, yk z tk dk, xk yk + tk dk ,

x

k z tk( tk) d

k

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 7 of 10

tk ( ATA

r

j=

j (I PQ

kj )Axk (I PQkj )Ayk

tk

i<h

ih PC

k i

zk PCk

h

zk

j (I PQ

kj )Ayk

. (.)

Since tk (, ), (,

+

r

j=

(AT A) ) in the algorithm, we conclude that the sequence { xk z } is monotonously nonincreasing and convergent and {xk} is bounded. We have shown that the sequence { xk z } is monotonically decreasing and bounded, therefore there exists the limit

lim

k xk z = d, (.)

which combined with (.)-(.), (.) implies

lim

k dk =

lim

k xk yk +

Fk yk Fk xk = , (.)

lim

k(I PQ

kj )Axk (I PQkj )Ayk

= , j, (.)

lim

k P

Ck

i

zk PCk

h

zk = , i = h, (.)

lim

kj )Ayk = , j. (.)

Since the sequence {xk} is bounded, there exist a subsequence {xk

k (I PQ

l } of {xk} converging

l } of {Axk} converging to a point Ax.

Now we will show that x SOL(MSFP), namely we will show limkl ci(xk

l ) and

limkl qi(xk

l ) for all i and j.

First, since PQkl

j

to a point x and a corresponding subsequence {Axk

Qklj, we have

qj Axkl + kl

j , PQkl

j

Axkl Axkl .

We know from Lemma . that the subgradient sequence {kj} is bounded. By (.) we get PQkl

j (Axk

l ) Axkl . Thus, we have limkl qi(xk

l ) for all and j.

Second, noting that PCkl

i

Ckli, we have

ci xkl +

kli , PCkl

i

xkl xkl .

Since {xk} is bounded, by Lemma . the sequence {ki} is also bounded. Then all we need is to show that PCkl

i xk

l . We know from (.) and (.) that Fkl(yk

l ) and

bining ykl = t

i= iPCkl

Fkl(xkl ) . It follows that zk

l = xkl Fkl(xkl ) x, and then by (.), yk

l x. Com-

i (xk

l Fkl(xkl )) with Fkl(xkl ) and PC

kli (xk

l ) PCkl

h (xk

l ) ,

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 8 of 10

i = h by (.), we conclude that yk

l PCkl

i (xk

l ) since ti= i = . This leads to

PCkl

i (xk

l ) xkl , and thereby limkl ci(xk

l ) for i = , , . . . , t.

Replacing z by x in (.), we have

lim

k xk x = d,

furthermore

lim

k Axk Ax = Ad,

on the other hand,

lim

l xkl x =

lim

l Axkl Ax = .

Thus, limk xk x = liml Axk Ax = . The proof of Theorem . is complete.

4 Numerical experiments

In the numerical results listed in Tables and , Iter., Sec. denote the number of iterations and the cpu time in seconds, respectively. We denote e = (, , . . . , ) N and e = (, , . . . , ) N. In the both numerical experiments, we take the weights /(r + t) for both Algorithm . and Censors algorithm. The stopping criterion is d < = .

Example . The MSFP with

A =

;

C = x | x + x + x + x ;

C = x | x + x + x

and

Q = y | y + y ;

Q = y | y + y ;

Q = y | y + y .

Consider the following three cases:

Case : x = (, , , , );

Case : x = (, , , , ); Case : x = (, , , , ).

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 9 of 10

Table 1 The numerical results of Example 4.1

Case Censor = 1

Algo. 3.1 = 1tk = 0.1

Censor = 0.6

Algo. 3.1 = 0.6 tk = 0.1

Censor = 1.8

Algo. 3.1 = 1.8 tk = 0.1

I Iter. = 1,051 Sec. = 1.043

Iter. = 146 Sec. = 0.401

Iter. = 1,867 Sec. = 1.480

Iter. = 224 Sec. = 0.334

Iter. = 832 Sec. = 0.700

Iter. = 89 Sec. = 0.062

II Iter. = 197 Sec. = 0.320

Iter. = 28 Sec. = 0.017

Iter. = 289 Sec. = 0.466

Iter. = 62 Sec. = 0.0751

Iter. = 87 Sec. = 0.068

Iter. = 9 Sec. = 0.010

III Iter. = 207

Sec. = 0.360

Iter. = 62 Sec. = 0.049

Iter. = 362 Sec. = 0.551

Iter. = 67 Sec. = 0.0728

Iter. = 139 Sec. = 0.217

Iter. = 17 Sec. = 0.020

Table 2 The numerical results of Example 4.2

N t, r Censor

= 1

Algo. 3.1 = 1tk = 0.01

Censor = 0.8

Algo. 3.1 = 0.8 tk = 0.01

Censor = 1.6

Algo. 3.1 = 1.6 tk = 0.01

N = 20 t = 5 r = 5

Iter. = 181 Sec. = 0.268

Iter. = 16 Sec. = 0.021

Iter. = 288 Sec. = 0.499

Iter. = 20 Sec. = 0.022

Iter. = 147 Sec. = 0.213

Iter. = 9 Sec. = 0.017

N = 40 t = 10 r = 15

Iter. = 1,012 Sec. = 1.032

Iter. = 39 Sec. = 0.048

Iter. = 2,320 Sec. = 2.122

Iter. = 57 Sec. = 0.059

Iter. = 893 Sec. = 0.795

Iter. = 19 Sec. = 0.031

Example . [] In this example, because the step is related to (ATA), for easy control of the spectral radius, we take diagonal matrices A and aii (, ) generated randomly

Ci = x N | x di ri , i = , , . . . , t;

Qj = x N | Lj y Uj , j = , , . . . , r;

where di is thecenter of the ball Ci, e di e, and ri (, ) is the radius, di and ri are all generated randomly. Lj and Uj are the boundary of the box Qj and are also generated randomly, satisfying e Lj e, e Uj e. In this test, we take e as the initial point.

In Tables -, the results showed that for most of the initial point, the number of iterative steps and the CPU time of Algorithm . are obviously less than those of Censor et al.s algorithm. Moreover, when we take N = ,, the number of iteration steps of Algorithm . is only hundreds of times. The numerical results also show that for large scale problems Algorithm . converges faster than Censors algorithm.

5 Conclusion

The multiple-set split feasibility problem arises in many practical applications in the real world. This paper constructed a new searching direction, which is not the gradient of a corresponding function. This dierent direction results in a very dierent way of analysis. And preliminary numerical results show that our new method converges faster, and this becomes more obvious while the dimension is increasing. Finally, the theoretically analysis is based on the assumption that the solution set of the MSSFP is nonempty.

Competing interests

The authors declare that they have no competing interests.

Authors contributions

All authors contributed equally to the writing of this paper. All authors read and approved the nal manuscript.

Dang and Xue Journal of Inequalities and Applications (2015) 2015:47 Page 10 of 10

Author details

1School of Management, University of Shanghai for Science and Technology, Shanghai, 200093, China. 2College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo, Henan 454000, China. 3School of Physics and Chemistry, Henan Polytechnic University, Shiji Road, Jiaozuo, Henan 454000, China.

Acknowledgements

This work was supported by Natural Science Foundation of Shanghai (14ZR1429200), National Science Foundation of China (11171221), National Natural Science Foundation of China (61403255), Shanghai Leading Academic Discipline Project under Grant XTKX2012, Innovation Program of Shanghai Municipal Education Commission under Grant 14YZ094, Doctoral Program Foundation of Institutions of Higher Education of China under Grant 20123120110004, Doctoral Starting Projection of the University of Shanghai for Science and Technology under Grant ID-10-303-002, and Young Teacher Training Projection Program of Shanghai for Science and Technology.

Received: 2 November 2014 Accepted: 26 January 2015

References

1. Censor, Y, Elfving, T, Kopf, N, Bortfeld, T: The multiple-sets split feasibility problem and its applications for inverse problems. Inverse Problems 21, 2071-2084 (2005)

2. Censor, Y, Elfving, T: A multiprojection algorithm using Bregman projections in a product space. Numer. Algorithms 8, 221-239 (1994)

3. Censor, Y, Bortfel, D, Martin, B, Tromov, A: A unied approach for inversion problems in intensity-modulated radiation therapy. Phys. Med. Biol. 51, 2353-2365 (2006)

4. Byrne, C: Iterative oblique projection onto convex sets and the split feasibility problem. Inverse Probl. 18, 441-453 (2002)

5. Dang, Y, Gao, Y: The strong convergence of a KM-CQ-like algorithm for split feasibility problem. Inverse Problems 27, 015007 (2011)

6. Dang, Y, Gao, Y: A perturbed projection algorithm with inertial technique for split feasibility problem. J. Appl. Math. (2012). doi:10.1155/2012/207323

7. Dang, Y, Gao, Y: An extrapolated iterative algorithm for multiple-set split feasibility problem. Abstr. Appl. Anal. 2012, Article ID 149508 (2012)

8. Yang, Q: The relaxed CQ algorithm solving the split feasibility problem. Inverse Problems 20, 1261-1266 (2004)9. Xu, H: A variable Krasnoselskii-Mann algorithm and the multiple-set split feasibility problem. Inverse Problems 22, 2021-2034 (2006)

10. Masad, E, Reich, S: A note on the multiple-set split convex feasibility problem in Hilbert space. J. Nonlinear Convex Anal. 8, 367-371 (2007)

11. Censor, Y, Alexander, S: On string-averaging for sparse problems and on the split common xed point problem. Contemp. Math. 513, 125-142 (2010)

12. Censor, Y, Alexander, S: The split common xed point problem for directed operators. J. Convex Anal. 16, 587-600 (2009)

13. Censor, Y, Motova, A, Segal, A: Perturbed projections and subgradient projections for the multiple-sets split feasibility problem. J. Math. Anal. Appl. 327, 1244-1256 (2007)

14. Gao, Y: Piecewise smooth Lyapunov function for a nonlinear dynamical system. J. Convex Anal. 19, 1009-1016 (2012)15. Bauschke, HH, Jonathan, MB: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367-426 (1996)

16. Bauschke, HH, Combettes, PL: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, Berlin (2011)

17. Byne, C: An unied treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20, 103-120 (2004)

18. Gao, Y: Nonsmooth Optimization. Science Press, Beijing (2008) (in Chinese)19. Rocafellar, RT: Convex Analysis. Princeton University Press, Princeton (1971)