计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (5): 232-241.doi: 10.11896/jsjkx.240200027

• 人工智能 • 上一篇    下一篇

求解不可分离非凸非光滑问题的线性惯性ADMM算法

刘洋1, 刘康2, 王永全1   

  1. 1 华东政法大学智能科学与信息法学系 上海 201620
    2 上海理工大学管理学院 上海 200093
  • 收稿日期:2024-02-04 修回日期:2024-03-20 出版日期:2024-05-15 发布日期:2024-05-08
  • 通讯作者: 刘洋(lyang@ecupl.edu.cn)
  • 基金资助:
    国家重点研发计划(2023YFC3306100,2023YFC3306105,2023YFC3306103);国家社会科学基金重大项目(20&ZD199);上海市哲学社会科学规划课(2023EFX011);教育部人文社科青年基金项目(20YJC820030);中国犯罪学学会重大项目(FZXXH2022A02)

Linear Inertial ADMM for Nonseparable Nonconvex and Nonsmooth Problems

LIU Yang1, LIU Kang2, WANG Yongquan1   

  1. 1 Department of Intelligent Science and Information Law,East China University of Political Science and Law,Shanghai 201620,China
    2 Business school,University of Shanghai for Science and Technology,Shanghai 200093,China
  • Received:2024-02-04 Revised:2024-03-20 Online:2024-05-15 Published:2024-05-08
  • About author:LIU Yang,born in 1983,Ph.D,lectu-rer.Her main research interests include algorithm optimization and artificial intelligence.
  • Supported by:
    National Key Research and Development Program of China(2023YFC3306100,2023YFC3306105,2023YFC3306103),Major Projects of National Social Science Foundation(20&ZD199),Shanghai Philosophy and Social Science Planning Project(2023EFX011),Ministry of Education Youth Fund for Humanities and Social Sciences(20YJC820030) and Chinese Criminology Society Major Project(FZXXH2022A02).

PDF (PC)

290

摘要： 针对目标函数中包含耦合函数H(x,y)的非凸非光滑极小化问题,提出了一种线性惯性交替乘子方向法(Linear Inertial Alternating Direction Method of Multipliers,LIADMM)。为了方便子问题的求解,对目标函数中的耦合函数H(x,y)进行线性化处理,并在x-子问题中引入惯性效应。在适当的假设条件下,建立了算法的全局收敛性;同时引入满足 Kurdyka-Łojasiewicz 不等式的辅助函数,验证了算法的强收敛性。通过两个数值实验表明,引入惯性效应的算法比没有惯性效应的算法收敛性能更好。

关键词: 耦合函数H(x,y), 非凸非光滑优化, 交替乘子方向法, 惯性效应, Kurdyka-Łojasiewicz 不等式

Abstract: In this paper,a linear inertial alternating direction multiplier method (LIADMM ) is proposed for the nonconvex non-smooth miniaturisation problem of the objective function containing the coupling function H(x,y),and to facilitate the solution of the subproblems,the objective function is linearised and the inertial effect is introduced into the x-subproblem.To facilitate the solution of the subproblem,the coupling function H(x,y) is linearised in the objective function and the inertial effect is introduced into the x-subproblem.The global convergence of the algorithm is established under appropriate assumptions,and the strong convergence of the algorithm is proved by introducing auxiliary functions satisfying the Kurdyka-Łojasiewicz inequality.Two numerical experiments show that the algorithm with the introduction of inertial effect converges has better convergence performance than the algorithm without inertial effect.

Key words: Coupling function H(x, y), Nonconvex nonsmooth optimization, Alternating direction method of multipliers (ADMM), Inertial effect, Kurdyka-Łojasiewicz inequality

中图分类号: 

  • TP301.6
[1]BOYD S,PARIKH N,CHU E,et al.Distributed Optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends in Machine learning,2011,3(1):1-122.
[2]HE B,YUAN X.On the O(1/n) Convergence Rate of theDouglas-Rachford Alternating Direction Method[J].SIAM Journal on Numerical Analysis,2012,50(2):700-709.
[3]HE B S,HOU L S,YUAN X M.On Full Jacobian Decomposition of the Augmented Lagrangian Method for Separable Convex Programming[J].SIAM Journal on Optimization,2015,25(4):2274-2312.
[4]YANG W H,HAN D.Linear Convergence of the AlternatingDirection Method of Multipliers for a Class of Convex Optimization Problems[J].SIAM Journal on Numerical Analysis,2016,54(2):625-640.
[5]WANG F,CAO W,XU Z B.Convergence of Multi-block Breg-man ADMM for Nonconvex Composite Problems[J].Science China Information Sciences,2018,61(12):122101.
[6]GUO K,HAN D.Convergence of alternating direction methodfor minimizing sum of two nonconvex functions with linear constraints[J].International Journal of Computer Mathematics,2017,94(8):1653-1669.
[7]YANG L,PONG T K,CHEN X.Alternating Direction Method of Multipliers for A Class of Nonconvex and Nonsmooth Pro-blems with Applications to Background/Foreground Extraction[J].SIAM Journal on Imaging Sciences,2017,10(1):74-110.
[8]ALVAREZ F,ATTOUCH H.An Inertial Proximal Method for MaximalMonotone Operators via Discretization of a Nonlinear Oscillator with Damping[J].Set Valued Analysis,2001,9(1/2):3-11.
[9]DANG Y,SUN J,XU H.Inertial accelerated algorithms for solving asplit feasibility problem[J].Journal of Industrial and Management Optimization,2016,13(3):78-78.
[10]CHEN C,CHAN R H,MA S Q,et al.Inertial Proximal ADMM for Linearly Constrained Separable Convex Optimization[J].Siam Journal onImaging Sciences,2015,8(4):2239-2267.
[11]BOT R I.An Inertial Alternating Direction Method of Multi-pliers[J].Optimization and Control,2014,9(7):1404-1425.
[12]YANG Y,TANG Y C.An Inertial Alternating Direction Me-thod of Multipliers for Solving a Two-Block Separable Convex Minimization Problem[J].Journal of Mathematical Research with Applications,2021,41(2):204-220.
[13]CHEN C,LI M,LIU X,et al.Extended ADMM and BCD forNonseparable Convex Minimization models with Quadratic Coupling Terms[J].Mathematical Programming:Series A and B,2019,173:37-77.
[14]GUO K,WANG X.Convergence of Generalized Alternating Direction Method of Multipliers for Nonseparable Nonconvex Objective with Linear Constraints[J].Journal of Mathematical Research with Applications,2018,38(5):87-104.
[15]CHAO M,DENG Z,JIAN J.Convergence of Linear BregmanADMM for Nonconvex and Nonsmooth Problems with Nonseparable Structure[J].Complexity,2020,2020:6237942.
[16]ZHANG Y X.HE S N.Inertial proximal alternating minimization fornonconvex and nonsmooth problems[J].Journal of Inequalities and Applications,2017(1):1-13.
[17]ATTOUCH H,BOLTE H,REDONT P,et al.Proximal Alternating Minimization and Projection Methods for Nonconvex Problems:An ApproachBased on the Kurdyka-Lojasiewicz Inequality[J].Mathematics of Operations Research,2010,35(2):438-457.
[18]BOT R I.CSETNEK E R,NGUYEN D K.A proximal minimization algorithm for structured nonconvex and nonsmooth pro-blems[J].SIAMJ.OPTIM,2020,29(2):1300-1328.
[19]BOLTE J,SABACH S,TEBOULLU M.Proximal alternating linearized minimizationfor nonconvex and nonsmooth problems [J].Mathematical Programming,2014,146(1/2):459-494.
[20]BAUSCHKE H H,COMBETTES P L.Convex Analysis andMonotone Oper-23ator Theory in Hilbert Spacel[M].Springer,New York,2011.
[21]BOT R I.CSETNEK E R.An Inertial Tseng's Type Proximal Algorithm241 for Nonsmooth and Nonconvex Optimization Problems[J].Journal of Optimization Theory and Applications,2016,171(2):600-616.
[22]ZENG L,XIE J.Group variable selection via SCAD-L 2[J].Statistics,2014,48(1):49-66.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发