分裂可行性问题的外推加速线性交替方向乘子法及其全局收敛性

doi:10.11896/jsjkx.230100009

计算机科学 ›› 2023, Vol. 50 ›› Issue (6): 261-265.doi: 10.11896/jsjkx.230100009

分裂可行性问题的外推加速线性交替方向乘子法及其全局收敛性

刘洋^1,2, 薛中会³, 王永全¹, 曹永胜¹

1 华东政法大学智能科学与信息法学系上海 201620
2 上海交通大学智慧法院研究院上海 200030
3 上海出版印刷高等专科学校信息与智能工程系上海 200093

收稿日期:2023-01-03 修回日期:2023-04-10 出版日期:2023-06-15 发布日期:2023-06-06
通讯作者: 薛中会(hnlgxzh@163.com)
作者简介:(lyang@ecupl.edu.cn)
基金资助:
国家社科基金重大项目(20&ZD199,21&ZD200);教育部人文社科青年基金项目(20YJC820030);国家新闻出版署“智能与绿色柔板印刷”重点实验室招标课题(KLIGFP-02)

Extrapolation Accelerated Linear Alternating Direction Multiplier Method for Split Feasibility Problems and Its Global Convergence

LIU Yang^1,2, XUE Zhonghui³, WANG Yongquan¹, CAO Yongsheng¹

1 Department of Intelligent Science and Information Law,East China University of Political Science and Law,Shanghai 201620,China
2 China Institute for Smart Court,Shanghai Jiao Tong University,Shanghai 200030,China
3 Department of Information and Intelligent Engineering,Shanghai Publishing and Printing College,Shanghai 200093,China

Received:2023-01-03 Revised:2023-04-10 Online:2023-06-15 Published:2023-06-06
About author:LIU Yang,born in 1983,Ph.D,lecturer.Her main research interests include algorithm optimization and artificial intelligence.XUE Zhonghui,born in 1974,Ph.D,associate professor.His main research interests include operational research and optimization theory,image reconstruction and restoration,artificial intelligence and brain science.
Supported by:
National Social Science Fund Major Project of China (20&ZD199,21&ZD200),Youth Fund for Humanities and Social Sciences of the Ministry of Education (20YJC820030) and Bidding Project of the Key Laboratory of “Intelligent and Green Flexographic Printing” of the State Press and Publication Administration(KLIGFP-02).

摘要/Abstract

摘要： 针对在图像重建以及语言处理系统等领域有着广泛应用的分裂可行性问题(SFP)的最优化求解,提出了外推加速线性交替方向乘子法。首先将SFP描述为一个具有线性约束的可分离凸极小化问题;然后引进外推线性交替方向乘子法,利用问题的可分离结构,产生了具有闭式解的子问题,并在适当条件下证明了该算法的全局收敛性;最后,通过数值实验验证了该算法的可行性和有效性。

关键词: 分裂可行性问题, 线性交替方向乘子法, 凸极小化问题, 外推加速

Abstract: This paper deals with a linear alternating direction multiplier method (ADMM) for Split feasibility problems (SFP).More specifically,the SFP has been formulated as a separable convex minimization problem with linear constraints,and then extrapolation accelerated linear ADMM has been proposed,which takes advantage of the separable structure,and then rising to sub-problems with closed-form solutions have been given.Furthermore,the global convergence of the proposed method is proved under some suitable conditions.Moreover,the algorithm has been tested by applying to two SFP examples in our theoretical results.

Key words: Split feasible problem, ADMM, Separable convex problem, Extrapolation accelerated

中图分类号:

TP301.6

刘洋, 薛中会, 王永全, 曹永胜. 分裂可行性问题的外推加速线性交替方向乘子法及其全局收敛性[J]. 计算机科学, 2023, 50(6): 261-265. https://doi.org/10.11896/jsjkx.230100009

LIU Yang, XUE Zhonghui, WANG Yongquan, CAO Yongsheng. Extrapolation Accelerated Linear Alternating Direction Multiplier Method for Split Feasibility Problems and Its Global Convergence[J]. Computer Science, 2023, 50(6): 261-265. https://doi.org/10.11896/jsjkx.230100009

参考文献

[1]CENSOR Y,ELFVING T.A multiprojection algorithm usingbregman projections in a product space [J].Numerical Algorithms,1994,8:221-239.
[2]BYRNE C.A unified treatment of some iterative algorithm algorithms in signal processing and image reconstruction [J].Inverse Problems,2004,20:103-120.
[3]DANG Y Z,GAO Y.The strong convergence of a KM-CQ-like algorithm for a split feasibility problem [J].Inverse Problems,2011,27(1):015007.
[4]QU B,XIU N.A note on the CQ algorithm for the split feasibility problem [J].Inverse Problem,2005,21:1655-1665.
[5]XU H.A variable Krasnosel'skii-Mann algorithm and themultiple-set split feasibility problem [J].Inverse Problems,2006,22:2021-2034.
[6]ZHAO J,YANG Q.Several solution methods for the split feasibility problem [J].Inverse Problems,2005,21:1791-1799.
[7]ROCKAFELLAR R.Augmented lagrangians and applications of the proximal point algorithm in convex programming [J].Mathmetics of Operations Research,1976,1(2):97-116.
[8]XUE Z H,YIN Q W,DANG Y Z.Inertia approximate relaxation alternating direction multiplier method for separable convex optimization problems[J].Journal of University of Shanghai for Science and Technology,2022,44(2):204-212.
[9]YANG J,ZHANG Y.Alternating direction algorithms for l1-problems in compressive sensing [J].SIAM Journal on Scientific Computing,2011,33(1):250-278.
[10]YANG J,ZHANG Y,YIN W.A fast alternating direction me-thod for TV l1Cl2 signal reconstruction from partial fourier data [J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2):288-297.
[11]HE H J,LING C,XU H.An implementable splitting algorithm for the l1norm regularized split feasibility problem [J].Journal of Scientific Computing,2016,67(1):281-298.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

分裂可行性问题的外推加速线性交替方向乘子法及其全局收敛性

Extrapolation Accelerated Linear Alternating Direction Multiplier Method for Split Feasibility Problems and Its Global Convergence

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

Metrics

本文评价

推荐阅读 0