Double projection algorithms for solving the split feasibility problems

Ya-zheng Dang; Jie Sun; Su Zhang

doi:10.3934/jimo.2018135

Article Contents

2019, Volume 15, Issue 4: 2023-2034. Doi: 10.3934/jimo.2018135

This issue Previous Article An efficient algorithm for non-convex sparse optimization Next Article

Double projection algorithms for solving the split feasibility problems

1.
School of Management, University of Shanghai for Science and Technology, Shanghai PRC 200093
2.
Faculty of Science, Curtin University, Benteley, West Australia 6102
3.
Business School, Nankai University, Tianjin PRC 300071

* Corresponding author: Jie Sun
* Corresponding author: Jie Sun

Received: September 30, 2016

Revised: October 31, 2017

Early access: September 2018

Published: July 2019

This work was partially supported by National Science Foundation of China (Grants 71572113 and 11401322) and Australian Research Council (Grant DP160102819).

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

Abstract

We propose two new double projection algorithms for solving the split feasibility problem (SFP). Different from the extragradient projection algorithms, the proposed algorithms do not require fixed stepsize and do not employ the same projection region at different projection steps. We adopt flexible rules for selecting the stepsize and the projection region. The proposed algorithms are shown to be convergent under certain assumptions. Numerical experiments show that the proposed methods appear to be more efficient than the relaxed- CQ algorithm.

Keywords:

Mathematics Subject Classification: Primary: 37C25, 47H09; Secondary: 90C25.

Citation:

Full Text(HTML)

Table 1. The numerical results of Example 5.1

Initiative point	CQ Algorithm with stepsize $\frac{1}{\rho(A^{T}A})$	Algorithm 3.1	Algorithm 4.1
$ x^{0}=$	$ k=269; s=0.063$	$ k=54; s=0.101$	$ k=28; s=0.077$
$ (-5,-2,-10)^{T}$	$x^{\ast}=(0.5071,-1.8186,01.9072)^{T}$	$x^{\ast}=(0.8718; -1.6577; -1.4080)^{T}$	$x^{\ast}=(1.1595;-1.0082;0-1.0814)^{T}$
$ x^{0}=$	$ k=261; s =0.063$	$ k=16; s=0.061$	$ k=1; s=0.045$
$ (-2,-1,-5)^{T}$	$x^{\ast}=(0.1098;-1.7655; -1.6134)^{T}$	$x^{\ast}=(0.6814;-1.4212; -1.0762)^{T}$	$x^{\ast}=(0.4734;-1.7714 ; -1.3758)^{T}$
$ x^{0}=$	$ k=6450; s =0.525$	$ k=59; s=0.096$	$ k=1; s=0.048$
$(-6,0,-1)^{T}$	$x^{\ast}=(-3.9899;-0.6144; 1.8062)^{T}$	$x^{\ast}=((-3.8898;-0.5850; 1.9604)^{T}$	$x^{\ast}=(-3.9302,-1.0861,1.9786)^{T}$

| Show Table

DownLoad: CSV

Table 2. The numerical results of Example 5.2

$M, N $	CQ Algorithm with stepsize $\frac{1}{\rho(A^{T}A}$	$t_{k}$	Algorithm3.1	Algorithm 4.1
$ M=20, N=10$	$ k=485, s =1.040$	0.8	$ k=274, s =0.312$	$ k=210, s =0.270$
		1.0	$ k=193, s =0.100$	$ k=108, s =0.070$
		1.8	$ k=103, s =0.067$	$ k=64, s =0.021$
$M=100, N=90$	$ k=3987, s =3.100$	0.4	$ k=1534, s =0.690$	$ k=1244, s =0.530$
		1	$ k=1074, s =0.500$	$ k=630, s =0.261$
		1.6	$ k=674, s =0.201$	$ k=412, s =0.132$

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review, 38 (1996), 367-426. doi: 10.1137/S0036144593251710.
[2]	C. Byrne, An unified treatment of some iterative algorithm algorithms in signal processing and image reconstruction, Inverse Problems, 20 (2004), 103-120. doi: 10.1088/0266-5611/20/1/006.
[3]	C. Byrne, Iterative oblique projection onto convex sets and the split feasibility problem, Inverse Problems, 18 (2002), 441-453. doi: 10.1088/0266-5611/18/2/310.
[4]	J. W. Chinneck, The constraint consensus method for finding approximately feasible points in nonlinear programs, INFORMS Journal on Computing, 16 (2004), 255-265. doi: 10.1287/ijoc.1030.0046.
[5]	Y. Censor, Parallel application of block iterative methods in medical imaging and radiation therapy, Mathematical Programming, 42 (1998), 307-325. doi: 10.1007/BF01589408.
[6]	Y. Censor and T. Elfving, A multiprojection algorithm using Bregman projections in a product space, Numerical Algorithms, 8 (1994), 221-239. doi: 10.1007/BF02142692.
[7]	Y. Censor, T. Elfving, N. Kopf and T. Bortfeld, The multiple-sets split feasibility problem and its applications for inverse problems, Inverse Problems, 21 (2005), 2071-2084. doi: 10.1088/0266-5611/21/6/017.
[8]	L. C. Ceng, Q. H. Ansari and J. C. Yao, An extragradient method for solving split feasibility and fixed point problems, Computers and Mathematics with Applications, 64 (2012), 633-642. doi: 10.1016/j.camwa.2011.12.074.
[9]	F. Deutsch, The method of alternating orthogonal projections, in Approximation Theory, Spline Functions and Applications, Kluwer Academic Publishers, Dordrecht, 1992,105-121.
[10]	Y. Dang and Y. Gao, The strong convergence of a KM-CQ-Like algorithm for split feasibility problem, Inverse Problems, 27 (2011), 9pp. doi: 10.1088/0266-5611/27/1/015007.
[11]	Y. Gao, Nonsmooth Optimization (in Chinese), Science Press, Beijing, 2008.
[12]	B. He, Inexact implicit methods for monotone general variational inequalities, Mathematical Programming, 35 (1999), 199-217. doi: 10.1007/s101070050086.
[13]	G. T. Herman, Image Reconstruction From Projections: The Fundamentals of Computerized Tomography, Academic Press, New York, 1980.
[14]	D. Kinderlehrer and G. Stampacchia, An Introduction to Variational Inequalities and Their Applications, Academic Press, New York, 1980.
[15]	N. Nadezhkina and W. Takahashi, Weak convergence theorem by an extragradient method for nonexpansive mappings and monotone mappings, Journal of Optimization Theory and Applications, 128 (2006), 191-201. doi: 10.1007/s10957-005-7564-z.
[16]	B. Qu and N. Xiu, A note on the CQ algorithm for the split feasibility problem, Inverse Problem, 21 (2005), 1655-1665. doi: 10.1088/0266-5611/21/5/009.
[17]	B. Qu and N. Xiu, A new halfspace-relaxation projection method for the split feasibility problem, Linear Algebra and Its Application, 428 (2008), 1218-1229. doi: 10.1016/j.laa.2007.03.002.
[18]	R. T. Rockafellar, Convex Analysis, Princeton University Press, 1971.
[19]	H. Xu, A variate Krasnosel$'$ ski-Mann algorithm and the multiple-set split feasibility problem, Inverse Problems, 22 (2006), 2021-2034. doi: 10.1088/0266-5611/22/6/007.
[20]	A. L. Yan, G. Y. Wang and N. Xiu, Robust solutions of split feasibility problem with uncertain linear operator, Journal of Industrial and Management Optimization, 3 (2007), 749-761. doi: 10.3934/jimo.2007.3.749.
[21]	Q. Yang, The relaxed CQ algorithm solving the split feasibility problem, Inverse Problems, 20 (2004), 1261-1266. doi: 10.1088/0266-5611/20/4/014.
[22]	Y. N. Yang, Q. Yang and S. Zhang, Modified alternating direction methods for the modified multiple-sets split feasibility problems, Journal of Optimization Theory and Applications, 163 (2014), 130-147. doi: 10.1007/s10957-013-0502-6.
[23]	W. X. Zhang, D. Han and Z. B. Li, A self-adaptive projection method for solving the multiple-sets split feasibility problem, Inverse Problem, 25 (2009), 115001, 16pp. doi: 10.1088/0266-5611/25/11/115001.
[24]	J. L. Zhao and Q. Yang, Self-adaptive projection methods for the multiple-sets split feasibility problem, Inverse Problem, 27 (2011), 035009, 13pp. doi: 10.1088/0266-5611/27/3/035009.
[25]	J. Zhao and Q. Yang, Several solution methods for the split feasibility problem, Inverse Problems, 21 (2005), 1791-1799. doi: 10.1088/0266-5611/21/5/017.
[26]	E. H. Zarantonello, Projections on convex set in Hilbert space and spectral theory, in Contributions to Nonlinear Functional Analysis (ed. E. H. Zarantonello), Academic, New York, 1971.