强收敛的球松弛CQ算法及其应用

doi:10.15960/j.cnki.issn.1007-6093.2021.01.004

Abstract

Abstract:

In order to solve the split feasibility problem, Yu et al. proposed a ballrelaxed CQ algorithm. Since this algorithm only needs to calculate the projection on the closed balls and does not need to calculate the norm of bounded linear operator, it is easy to implement. But the ball-relaxed CQ algorithm only has weak convergence in infinite dimensional Hilbert spaces. Firstly, a strongly convergent ball-relaxed CQ algorithm is constructed. Under weaker conditions, the strong convergence of the algorithm is proved. Secondly, the algorithm is applied to the projection problem on a class of closed convex sets. Finally, numerical experiments verify the effectiveness of the algorithm.

Key words: split feasibility problem, CQ algorithm, strongconvergence, strongly convex function

CLC Number:

O221

Hai YU, Wanrong ZHAN. Strongly convergent ball-relaxed CQ algorithm and its application[J]. Operations Research Transactions, 2021, 25(1): 50-60.

Figures/Tables 3

References 19

1	Censor Y , Elfving T . A multiprojection algorithm using Bregman projections in product space[J]. Numerical Algorithms, 1994, 8, 221- 239. doi: 10.1007/BF02142692
2	López G , Martín V , Wang F , et al. Solving the split feasibility problem without prior knowledge of matrix norms[J]. Inverse Problems, 2012, 28, 085004. doi: 10.1088/0266-5611/28/8/085004
3	Byrne C . Iterative oblique projection onto convex sets and the split feasibility problem[J]. Inverse Problems, 2002, 18, 441- 453. doi: 10.1088/0266-5611/18/2/310
4	Byrne C . A unified treatment of some iterative algorithms in signal processing and image reconstruction[J]. Inverse Problems, 2004, 20, 103- 120. doi: 10.1088/0266-5611/20/1/006
5	Qu B , Xiu N . A note on the CQ algorithm for the split feasibility problem[J]. Inverse Problems, 2005, 21, 1655- 1665. doi: 10.1088/0266-5611/21/5/009
6	Wang F . On the convergence of CQ algorithm with variable steps for the split equality problem[J]. Numerical Algorithms, 2017, 74, 927- 935. doi: 10.1007/s11075-016-0177-9
7	Wang F , Xu H , Su M . Choices of variable steps of the CQ algorithm for the split feasibility problem[J]. Fixed Point Theory, 2011, 12, 489- 496.
8	Yang Q . On variable-step relaxed projection algorithm for variational inequalities[J]. Journal of Mathematical Analysis and Applications, 2005, 302, 166- 179. doi: 10.1016/j.jmaa.2004.07.048
9	He S , Zhao Z , Luo B . A relaxed self-adaptive CQ algorithm for the multiple-setes split feasibility problem[J]. Optimization, 2015, 64, 1907- 1918. doi: 10.1080/02331934.2014.895898
10	Moudafi A . A relaxed alternating CQ-algorithm for convex feasibility problems[J]. Nonlinear Analysis, 2013, 79, 117- 121. doi: 10.1016/j.na.2012.11.013
11	Qu B , Xiu N . A new halfspace-relaxation projection method for the split feasibility problem[J]. Linear Algebra and its Applications, 2008, 428, 1218- 1229. doi: 10.1016/j.laa.2007.03.002
12	Wang F . Polyak's gradient method for split feasibility problem constrained by level sets[J]. Numerical Algorithms, 2018, 77, 925- 938. doi: 10.1007/s11075-017-0347-4
13	Yang Q . The relaxed CQ algorithm solving the split feasibility problem[J]. Inverse Problems, 2004, 20, 1261- 1266. doi: 10.1088/0266-5611/20/4/014
14	Yu H , Zhan W , Wang F . The ball-relaxed CQ algorithms for the split feasibility problem[J]. Optimization, 2018, 67 (10): 1687- 1699. doi: 10.1080/02331934.2018.1485677
15	Bauschke H , Combettes P . Convex Analysis and Monotone Operator Theory in Hilbert Space[M]. New York: Springer-Verlag, 2011.
16	He S , Tian H . Selective projection methods for solving a class of variational inequalities[J]. Numerical Algorithms, 2019, 80 (2): 617- 634. doi: 10.1007/s11075-018-0499-x
17	Xu H . A variable Krasnosel$\rm{\ddot{s}}$kii-Mann algorithm and the multiple-set split feasibility problem[J]. Inverse Problems, 2006, 22 (6): 2021- 2034. doi: 10.1088/0266-5611/22/6/007
18	Lin A, Han S. Projection on an ellipsoid[R]. Department of Mathematical Sciences, The Johns Hopkins University, 2001.
19	Dai Y . Fast algorithms for projection on an ellipsoid[J]. SIAM Journal on Optimization, 2006, 16 (4): 986- 1006. doi: 10.1137/040613305

$w$	$v$	A1		A2		$w$	$v$	A1		A2
$w$	$v$	iter	cpu/s	iter	cpu/s	$w$	$v$	iter	cpu/s	iter	cpu/s
0	2	84	0.493 3	79	0.197 9	$\frac{1}{8}$	2	94	0.549 6	102	0.258 7
0	5	155	0.892 7	161	0.390 6	$\frac{1}{8}$	5	175	0.982 9	199	0.477 6
0	10	215	1.212 6	213	0.537 9	$\frac{1}{8}$	10	240	1.332 9	249	0.605 6
0	50	311	1.746 6	436	1.044 2	$\frac{1}{8}$	50	343	1.911 4	475	1.132 9
$\frac{1}{4}$	2	106	0.627 3	129	0.312 1	$\frac{1}{2}$	2	131	0.773 5	189	0.491 1
$\frac{1}{4}$	5	195	1.084 1	239	0.571 8	$\frac{1}{2}$	5	236	1.311 8	303	0.749 0
$\frac{1}{4}$	10	265	1.476 2	284	0.718 1	$\frac{1}{2}$	10	310	1.723 1	336	0.825 1
$\frac{1}{4}$	50	372	2.075 5	523	1.244 5	$\frac{1}{2}$	50	410	2.296 4	658	1.541 0

$w$	$v$	A1		A2		$w$	$v$	A1		A2
$w$	$v$	iter	cpu/s	iter	cpu/s	$w$	$v$	iter	cpu/s	iter	cpu/s
0	2	269	1.489 4	161	0.397 9	$\frac{1}{8}$	2	336	1.873 9	242	0.600 8
0	5	567	3.104 6	394	0.911 5	$\frac{1}{8}$	5	713	3.957 9	615	1.439 6
0	10	912	4.940 6	705	1.638 6	$\frac{1}{8}$	10	1 149	6.153 3	1 063	2.466 4
0	50	1 857	10.002 2	1 825	4.271 1	$\frac{1}{8}$	50	2 321	12.314 0	2 260	5.249 2
$\frac{1}{4}$	2	417	2.326 4	379	0.890 9	$\frac{1}{2}$	2	668	3.750 4	923	2.160 6
$\frac{1}{4}$	5	887	4.778 6	974	2.275 4	$\frac{1}{2}$	5	1 385	7.407 3	2 096	4.860 6
$\frac{1}{4}$	10	1 420	7.625 3	1 583	3.685 4	$\frac{1}{2}$	10	2 110	11.378 7	2 805	6.506 7
$\frac{1}{4}$	50	2 791	14.787 8	2 758	6.397 3	$\frac{1}{2}$	50	3 628	19.288 2	3 832	8.895 9

$w$	$v$	A1		A2		$w$	$v$	A1		A2
$w$	$v$	iter	cpu/s	iter	cpu/s	$w$	$v$	iter	cpu/s	iter	cpu/s
0	2	700	3.819 2	269	0.638 2	$\frac{1}{8}$	2	990	5.449 5	426	0.995 8
0	5	1 567	8.520 6	674	1.562 8	$\frac{1}{8}$	5	2 261	12.148 7	1 148	2.666 1
0	10	2 754	14.776 1	1 338	3.093 5	$\frac{1}{8}$	10	4 031	21.511 3	236 3	5.506 7
0	50	7 807	41.516 6	5 776	13.365 6	$\frac{1}{8}$	50	1 1707	62.032 6	9 298	21.547 4
$\frac{1}{4}$	2	1 362	7.345 6	747	1.742 3	$\frac{1}{2}$	2	2 809	14.743 2	2 895	6.682 9
$\frac{1}{4}$	5	3 141	16.843 6	2 182	5.069 9	$\frac{1}{2}$	5	6 443	34.464 1	8 865	20.602 0
$\frac{1}{4}$	10	5 620	29.412 6	4 582	10.652 6	$\frac{1}{2}$	10	11 156	58.522 5	16 660	38.647 4
$\frac{1}{4}$	50	16 174	86.554 5	15 110	34.959 0	$\frac{1}{2}$	50	27 381	143.962 4	29 754	69.398 2

[1]	XUAN Hongwei, LI Zhendong, SHENG Zhoushan, LIU Lindong. Cost allocation for multiple pairs of shortest paths recovery game on disrupted networks [J]. Operations Research Transactions, 2021, 25(3): 183-199.
[2]	ZHANG Liwei. Discussion on second-order analysis in augmented Lagrange method [J]. Operations Research Transactions, 2021, 25(3): 1-14.
[3]	HUANG Zhipeng, LI Xingquan, ZHU Wenxing. Optimization models and algorithms for placement of very large scale integrated circuits [J]. Operations Research Transactions, 2021, 25(3): 15-36.
[4]	CHEN Feng. Research and application of operations research on intelligent scheduling decision support system for automotive outbound logistics [J]. Operations Research Transactions, 2021, 25(3): 37-73.
[5]	XU Zi, ZHANG Huiling. Optimization algorithms and their complexity analysis for non-convex minimax problems [J]. Operations Research Transactions, 2021, 25(3): 74-86.
[6]	KE Rongzhu, ZHANG Jin. On the first order approach for bilevel programming: moral hazard case [J]. Operations Research Transactions, 2021, 25(3): 87-104.
[7]	SUN Cong, ZHANG Ya. A brief review on gradient method [J]. Operations Research Transactions, 2021, 25(3): 119-132.
[8]	Jianfeng REN, Xiaoyun TIAN. Squared metric facility location problem with outliers [J]. Operations Research Transactions, 2021, 25(1): 114-122.
[9]	Deqiang QU, Youlin SHANG, Yue ZHAN, Dan WU. A new parameterless filled function for global optimization problems [J]. Operations Research Transactions, 2021, 25(1): 89-95.
[10]	Jiali CHEN, Ying ZHANG, Shenggang WANG, Xiaoying XIE. A new filled function and its application in data fitting problems [J]. Operations Research Transactions, 2021, 25(1): 81-88.
[11]	Xiuling WANG, Xunhua GONG. An existence theorem for efficient solutions of symmetric vector quasi-equilibrium problems [J]. Operations Research Transactions, 2021, 25(1): 73-80.
[12]	Hongwu LI, Min XIE, Rong ZHANG. A proximal gradient method for nonsmooth convex optimization problems [J]. Operations Research Transactions, 2021, 25(1): 61-72.
[13]	MIAO Xiaonan, GU Jian, XIAO Xiantao. A cubic regularization method for solving nonsmooth equations [J]. Operations Research Transactions, 2019, 23(2): 17-30.
[14]	LIANG Renli, BAI Yanqin. A splitting augmented Lagrangian method embedding in the BB method for solving the sparse logistic problem [J]. Operations Research Transactions, 2019, 23(2): 86-94.
[15]	ZHOU Xinyi, WANG Ke, WU Donghua, WANG Chen. Cross entropy algorithm with multiple important sample level estimation for global optimization problems [J]. Operations Research Transactions, 2019, 23(1): 15-27.

Strongly convergent ball-relaxed CQ algorithm and its application

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 19

Related Articles 15

Recommended Articles

Metrics

Comments