凸可行问题的平行近似次梯度投影算法

运筹学学报 ›› 2015, Vol. 19 ›› Issue (1): 117-124.

凸可行问题的平行近似次梯度投影算法

党亚峥^1,2,*, 薛中会³

1. 上海理工大学管理学院, 上海 200093; 2. 河南理工大学计算机学院, 河南焦作，454001; 3. 河南理工大学理化学院, 河南焦作，454001

收稿日期:2013-11-07 出版日期:2015-03-15 发布日期:2015-03-15
通讯作者: 党亚峥 E-mail:jgdyz@163.com
基金资助:
上海市科委科研创新项目(No.15ZZ073), 国家自然科学基金(No. 11171221)

Parallel approximate subgradient projection algorithm for convex feasibility problem

DANG Yazheng^1,2,*, XUE Zhonghui³

1. School of Management, University of Science and Technology, Shanghai 200093, China; 2. College of Computer Science and Technology, Henan Polytechnic University, Jiaozuo Henan 454001, China; 3. School of Physics and Chemistry, Henan Polytechnic University, Jiaozuo Henan 454001, China

Received:2013-11-07 Online:2015-03-15 Published:2015-03-15

摘要/Abstract

摘要： 对凸可行问题提出了包括上松弛的平行近似次梯度投影算法和加速平行近似次梯度投影算法．与序列近似次梯度投影算法相比, 平行近似次梯度投影算法(每次迭代同时运用多个凸集的近似次梯度超平面上的投影)能够保证迭代序列收敛到离各个凸集最近的点．上松弛的迭代技术和含有外推因子的加速技术的应用, 减少了数据存储量, 提高了收敛速度. 最后在较弱的条件下证明了算法的收敛性, 数值实验结果验证了算法的有效性和优越性.

关键词: 凸可行问题, 近似次梯度, 收敛性分析

Abstract: In this paper, a relaxed parallel $\varepsilon$-subgradient projection algorithm which includes the over-relaxed case and an accelerated parallel $\varepsilon$-subgradient projection algorithm for solving convex feasibility problem (CFP) are presented. Compared with the previous subgradient projection algorithms, the algorithms presented in this paper use parallel process, i.e. in each iteration consider several approximation subgradient projections simultaneously. Algorithms adopt over-relaxed iterative process and accelerated technique. Hence, they can reduce the amounts of data storage and improve the convergence speed. And we also discuss the convergence of the methods under some mild conditions. Finally, the results of numerical experiment indicate that the algorithms are valid and have faster convergence speed than that of the algorithm in [18].

Key words: convex feasibility problem, approximation subgradient, convergence analysis

中图分类号:

O221

党亚峥, 薛中会. 凸可行问题的平行近似次梯度投影算法[J]. 运筹学学报, 2015, 19(1): 117-124.

DANG Yazheng, XUE Zhonghui. Parallel approximate subgradient projection algorithm for convex feasibility problem[J]. Operations Research Transactions, 2015, 19(1): 117-124.

参考文献

Chinneck J W. The constraint consensus method for finding approximately feasible points in nonlinear programs [J]. J Informs Comput, 2004, 16: 255-265.
Censor Y, Lent A. Cyclic subgradient projections [J]. Math Programming, 1982, 24: 233-235.
Deutsch F. The Method of Alternating Orthogonal Projections, Approximation Theory, Spline Functions and Applications [M]. Dordrecht: Kluwer Academic Publishers, 1992, 105-121.
Censor Y. Parallel application of block iterative methods in medical imaging and radiation therapy [J]. Math Programming, 1998, 12: 307-325.
Herman G T. Image Reconstruction from Projections, the Fundamentals of Computerized Tomography [M]. New York: Academic Press, 1980.
Herman G T. Image Reconstruction from Projections, the Fundamentals of Computerized Tomography [M]. New York: Academic Press, 1980.
高岩. 仿射非线性控制系统生存性的判别 [J]. 控制理论与应用, 2009, 29: 654-656.
Gao Y. Viability criteria for differential inclusions [J]. Journal of Systems Science and Complexity, 2011, 24(5): 825-834.

Bauschke H H, Borwein J M. On projection algorithms for solving convex feasibility problems [J]. SIAM Rev, 1996, 38: 367-426.
Garcia-Palomares U M, Gonzialez-Castano F J. Incomplete projection algorithms for solving the convex feasibility problem [J]. Numer Algorithms, 1998, 18: 177-193.

Gould I M. How good are projection methods for convex feasibility problems [J]. Comput Optim Appl, 2008, 40: 1-12.
Li L, Gao Y. Projection algorithm with line search for solving the convex feasibility problem [J]. J Inform Comput, 2008, 3: 62-68.
Bauschke H H, Borwein J M, Lewis A S. The method of cyclic projections for closed convex sets in Hilbert space [C]//Proceeding of the Special Session on Optimization and Nonlinear Analysis, 1995.
Garcia-palomares U. Parallel projected aggregation methods for solving the convex feasibility problem [J]. SIAM J Optim, 1933, 1: 882-900.
Kiwiel K C. Block-iterative surrogate projection methods for convex feasibility problem [J]. Linear Algebra Appl, 1995, 215: 225-260.
Santos L T. A parallel subgradient projections method for the convex feasibility problem [J]. J Comput Appl Math, 1987, 18: 307-320.
Dang Y Z, Gao Y. Block-iterative subgradient projection algorithms for the convex feasibility problem [J]. OR Transactions, 2011, 15(1): 59-70.
Eremin I I. On systems of inequalities with convex functions in the left sides [J]. Amer Math Soc Trans, 1970, 88: 67-83.
Li L, Gao Y. Approximate subgradient projection algorithm for a convex feasibility problem [J]. Systems Engineering and Electronics, 2010, 21(3): 527-530.

高岩. 非光滑优化 [M]. 北京：科学出版社, 2008.