多集分裂等式问题的逐次松弛投影算法

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

运筹学学报 ›› 2021, Vol. 25 ›› Issue (2): 93-103.doi: 10.15960/j.cnki.issn.1007-6093.2021.02.007

多集分裂等式问题的逐次松弛投影算法

周雪玲¹, 李梅霞²^,*(), 车海涛²

1. 扬州大学数学科学学院, 江苏扬州 225002
2. 潍坊学院数学与信息科学学院, 山东潍坊 261061

收稿日期:2019-10-08 出版日期:2021-06-15 发布日期:2021-05-06
通讯作者: 李梅霞 E-mail:limeixia001@163.com
作者简介:李梅霞 E-mail: limeixia001@163.com
基金资助:
国家自然科学基金(11401438);国家自然科学基金(11571120);山东省自然科学基金(ZR2020MA027);山东省自然科学基金(ZR2019MA022)

Successive relaxed projection algorithm for multiple-sets split equality problem

Xueling ZHOU¹, Meixia LI²^,*(), Haitao CHE²

1. School of Mathematical Science, Yangzhou University, Yangzhou 225002, Jiangsu, China
2. School of Mathematics and Information Science, Weifang University, Weifang 261061, Shandong, China

Received:2019-10-08 Online:2021-06-15 Published:2021-05-06
Contact: Meixia LI E-mail:limeixia001@163.com

摘要/Abstract

摘要：

多集分裂等式问题是分裂可行性问题的拓展问题，在图像重建、语言处理、地震探测等实际问题中具有广泛的应用。为了解决这个问题，提出了逐次松弛投影算法，设计了变化的步长，使其充分利用当前迭代点的信息且不需要算子范数的计算，证明了算法的弱收敛性。数值算例验证了算法在迭代次数与运行时间等方面的优越性。

关键词: 多集分裂等式问题, 逐次松弛投影算法, 收敛性

Abstract:

The multiple-sets split equality problem is an extended split feasibility problem, which has a wide application in image reconstruction, language processing, and seismic exploration. In order to solve this problem, we propose a successive relaxed projection algorithm with a variable stepsize which can fully use the information of the current iteration point and does not need the calculation of the operator norm. Furthermore the weak convergence of the algorithm is proved. The numerical examples show the superiority of the algorithm in the number of iterations and the running time.

Key words: multiple-sets split equality problem, successive relaxed projection algorithm, convergence

中图分类号:

O224

周雪玲, 李梅霞, 车海涛. 多集分裂等式问题的逐次松弛投影算法[J]. 运筹学学报, 2021, 25(2): 93-103.

Xueling ZHOU, Meixia LI, Haitao CHE. Successive relaxed projection algorithm for multiple-sets split equality problem[J]. Operations Research Transactions, 2021, 25(2): 93-103.

图/表 4

表1

表2

图1

图2

参考文献 20

1	Censor Y , Elfving T . A multiprojection algorithm using Bregman projection in a product space[J]. Numerical Algorithm, 1994, 8, 221- 239. doi: 10.1007/BF02142692
2	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
3	Dang Y , Gao Y . The strong convergence of a KM-CQ-like algorithm for split feasibility problem[J]. Inverse Problems, 2011, 27, 015007. doi: 10.1088/0266-5611/27/1/015007
4	Yang Q . The relexed CQ algorithm solving the split feasibility problem[J]. Inverse Problems, 2004, 20, 1261- 1266. doi: 10.1088/0266-5611/20/4/014
5	Moudafi A . Alternating CQ algorithm for convex feasibility and split fixed point problem[J]. Journal of Nonlinear Convex Analysis, 2014, 15, 809- 818.
6	Chang S, Agarwal R. Strong convergence theorems of general split equality problems for quasi-nonexpansive mappings[J]. Journal of Inequalities and Applications, 2014, 2014: Article ID 367.
7	Dong Q , He S . Self-adaptive projection algorithms for solving the split equality problems[J]. Fixed Point Theory, 2017, 18, 191- 202. doi: 10.24193/fpt-ro.2017.1.15
8	Li M , Kao X , Che H . Relaxed inertial accelerated algorithms for solving split equality feasibility problem[J]. Journal of Nonlinear Sciences and Applications, 2017, 10, 4109- 4121. doi: 10.22436/jnsa.010.08.07
9	Censor Y , Elfving T . The multiple-sets split feasibility problem and its applications for inverse problems[J]. Inverse Problems, 2005, 21, 2071- 2084. doi: 10.1088/0266-5611/21/6/017
10	Zhang W, Han D, Li Z. A self-adaptive projection method for solving the multiple-sets split feasibility problem[J]. Inverse Problems, 2009, 25: 115001: 1-115001: 16.
11	Censer Y , Motova A , Segal A . Perturbed projections and subgradient projections for the multiple-sets split feasibility problem[J]. Journal of Mathematical Analysis and Applications, 2007, 327, 1244- 1256. doi: 10.1016/j.jmaa.2006.05.010
12	Qu B , Chang H . Remark on the successive projection algorithm for the multiple-sets split feasibility problem[J]. Numerical Function Analysis and Optimizations, 2017, 38 (12): 1614- 1623. doi: 10.1080/01630563.2017.1369109
13	Shi L, Chen R, Wu Y. An iterative algorithm for the split equality and multiple-sets split equality problem[J]. Abstract and Applied Analysis, 2014, 2014: Article ID 620813.
14	Wu Y, Chen R, Shi L. Split equality problem and multiple sets split equality problem for quasi-nonexpansive multi-valued mapping[J]. Journal of Inequalities and Applications, 2014, 2014: Article ID 428.
15	Dang Y , Yao J , Gao Y . Relaxed two points projection method for solving the multiple-sets split equality problem[J]. Numerical Algorithm, 2018, 78, 263- 275. doi: 10.1007/s11075-017-0375-0
16	Zarantonello E . Projections on convex sets in Hilbert space and spectral theory[J]. Contributions to Nonlinear Functional Analysis, 1971, 237- 424.
17	程其襄, 张奠宙, 魏国强, 等. 实变函数与泛函分析基础[M]. 北京: 高等教育出版社, 2010.
18	Rockafeller R . Convex Analysis[M]. Princeton: Princeton University Press, 1977.
19	Fukushima M . Relaxed projection method for variational inequalities[J]. Mathematical Programming, 1986, 35, 58- 70. doi: 10.1007/BF01589441
20	Polyak B . Minimization of unsmooth functionals[J]. USSR Computational Mathematics and Mathematical Physics, 1969, 9, 14- 29.

初始点	算法1	算法RTPPM
Case 1	$ n = 65; s = 0.025\;512 $ $ x^* = (-0.240, 0.092, 0.049)^\mathrm{T} $ $ y^* = (-0.130, 0.054, 0.009, 0.006)^\mathrm{T} $	$ n = 169; s = 0.003\;357 $ $ x^* = (-0.241, -0.037, 0.058)^\mathrm{T} $ $ y^* = (-0.073, 0.043, -0.022, -0.055)^\mathrm{T} $
Case 2	$ n = 172; s = 0.065\;433 $ $ x^* = (-0.016, -0.071, -0.002)^\mathrm{T} $ $ y^* = (0.008, -0.010, -0.018, -0.021)^\mathrm{T} $	$ n = 9\;464; s = 0.172\;677 $ $ x^* = (0.033, -0.074, -0.015)^\mathrm{T} $ $ y^* = (0.042, -0.006, -0.007, -0.037)^\mathrm{T} $
Case 3	$ n = 203; s = 0.075\;807 $ $ x^* = (-0.022, -0.096, -0.006)^\mathrm{T} $ $ y^* = (0.008, -0.015, -0.024, -0.027)^\mathrm{T} $	$ n = 36\;951; s = 0.644\;358 $ $ x^* = (0.074, -0.099, -0.053)^\mathrm{T} $ $ y^* = (0.044, -0.0179, 0.001, -0.035)^\mathrm{T} $
Case 4	$ n = 331; s = 0.115\;664 $ $ x^* = (0.036, 0.265, -0.097)^\mathrm{T} $ $ y^* = (-0.152, 0.019, 0.098, 0.140)^\mathrm{T} $	$ n = 40\;670; s = 0.773\;443 $ $ x^* = (0.158, 0.274, -0.134)^\mathrm{T} $ $ y^* = (-0.089, 0.022, 0.126, 0.124)^\mathrm{T} $

				算法1		算法RTPPM
	$ J $	$ N $	$ M $	$ n $	$ s $	$ n $	$ s $
	6	15	10	42	0.003 060	2 469	0.062 804
Case 1	10	20	30	52	0.002 697	9 349	0.308 245
	40	30	35	325	0.016 372	50 147	1.890 826
	$ 6 $	$ 15 $	$ 10 $	76	0.003 525	1 013	0.030 080
Case 2	10	20	30	48	0.003 492	2 896	0.098 542
	40	30	35	241	0.011 117	21 248	0.818 620
	$ 6 $	$ 15 $	$ 10 $	99	0.004 066	3 085	0.065 888
Case 3	10	20	30	52	0.003 352	9 317	0.319 493
	40	30	35	355	0.013 316	54 935	2.134 303
	$ 6 $	$ 15 $	$ 10 $	29	0.002 937	3 360	0.075 676
Case 4	10	20	30	49	0.002 736	9 423	0.326 474
	40	30	35	250	0.008 530	54 172	2.057 903

[1]	屈彪, 徐伟, 王新艳. 关于求解变分不等式问题的2-次梯度外梯度算法收敛性的一个补注[J]. 运筹学学报, 2021, 25(2): 144-148.
[2]	潘少华, 文再文. 低秩稀疏矩阵优化问题的模型与算法[J]. 运筹学学报, 2020, 24(3): 1-26.
[3]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[4]	田明雨, 杨永建. 求解多项式规划的一个全局最优化算法[J]. 运筹学学报, 2018, 22(4): 79-88.
[5]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[6]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[7]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[8]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[9]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[10]	霍永亮. 极大极小随机规划逼近问题最优解集和最优值的稳定性[J]. 运筹学学报, 2016, 20(1): 75-83.
[11]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[12]	濮定国, 尚有林, 王关琳. 无罚函数和滤子的一个新的QP-free方法[J]. 运筹学学报, 2015, 19(3): 48-56.
[13]	陈宁, 孙文瑜, 袁锦昀. 解线性等式约束优化问题的模式搜索过滤集方法[J]. 运筹学学报, 2015, 19(3): 96-107.
[14]	党亚峥, 薛中会. 凸可行问题的平行近似次梯度投影算法[J]. 运筹学学报, 2015, 19(1): 117-124.
[15]	程聪, 张立卫. 二次规划逆问题的牛顿方法[J]. 运筹学学报, 2014, 18(3): 60-70.

多集分裂等式问题的逐次松弛投影算法

Successive relaxed projection algorithm for multiple-sets split equality problem

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 20

相关文章 15

编辑推荐

Metrics

本文评价