• 论文 • 上一篇    下一篇

一类自适应广义交替方向乘子法

姜帆, 刘雅梅, 蔡邢菊   

  1. 南京师范大学数学科学学院, 南京 210023
  • 收稿日期:2018-01-13 出版日期:2018-12-15 发布日期:2018-11-20
  • 基金资助:

    国家自然科学基金青年项目(11401315),国家自然科学基金项目(11571178).

姜帆, 刘雅梅, 蔡邢菊. 一类自适应广义交替方向乘子法[J]. 计算数学, 2018, 40(4): 367-386.

Jiang Fan, Liu Yamei, Cai Xingju. A SELF-ADAPTIVE GENERALIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS[J]. Mathematica Numerica Sinica, 2018, 40(4): 367-386.

A SELF-ADAPTIVE GENERALIZED ALTERNATING DIRECTION METHOD OF MULTIPLIERS

Jiang Fan, Liu Yamei, Cai Xingju   

  1. School of Mathematical Sciences, Nanjing Normal University, Nanjing 210023, China
  • Received:2018-01-13 Online:2018-12-15 Published:2018-11-20
广义交替方向乘子法是求解凸优化问题的有效算法.当实际问题中子问题难以求解时,可以采用在子问题中添加邻近项的方法处理,邻近矩阵正定时,算法收敛,然而这也会使迭代步长较小.最新研究表明,邻近矩阵可以有一定的不正定性.本文在基于不定邻近项的广义交替方向乘子法框架下,提出一种自适应的广义交替方向乘子法,动态地选择邻近矩阵,增大迭代步长.在一些较弱的假设下,证明了算法的全局收敛性.我们进行一些初等数值实验,验证了算法的有效性.
Generalized alternating direction method of multipliers (G-ADMM) is effective in solving the convex optimization problem. When the subproblem is difficult to solve in practical problem, we can add the proximal term in the subproblem. The positive definiteness of the proximal matrix guarantees the convergence while resulting in the tiny step size. A new study indicates that the proximal matrix can be indefinite. In this paper, based on the frame of G-ADMM with indefinite proximal term, we propose a self-adaptive G-ADMM while the proximal matrix is dynamically selected to increase the step size. Under mild assumptions, we prove the global convergence of the proposed method. The preliminary numerical results indicate that the new algorithm is efficient.

MR(2010)主题分类: 

()
[1] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends R in Machine Learning, 2011, 3(1):1-122.

[2] Eckstein J, Bertsekas D P. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators[J]. Mathematical Programming, 1992, 55(1):293-318.

[3] Fang E X, He B S, Liu H, Yuan X M. Generalized alternating direction method of multipliers:new theoretical insights and applications[J]. Mathematical Programming Computation, 2015, 7(2):149-187.

[4] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers and Mathematics with Applications, 1976, 2(1):17-40.

[5] Gao B, Ma F. Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization[J]. Journal of Optimization Theory and Applications, 2018, 176(1):1-27.

[6] Glowinski R, Marroco A. Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires[J]. Revue Française d'Automatique, Informatique, Recherche Opérationelle, 1975, 2:41-76.

[7] Hansen P C, Nagy J G, O'Leary D P. Deblurring images:matrices, spectra, and filtering[M]. SIAM, Philadelphia, 2006.

[8] He B S. PPA-like contraction methods for convex optimization:a framework using variational inequality approach[J]. Journal of Operations Research Society of China, 2015, 3(4):391-420.

[9] He B S, Ma F, Yuan X M. Linearized alternating direction method of multipliers via positiveindefinite proximal regularization for convex programming[J/OL]. http://www.optimizationonline.org, 2016-07-31.

[10] He B S, Xu M H, Yuan X M. Solving large-scale least squares semidefinite programming by alternating direction methods[J]. SIAM Journal on Matrix Analysis and Applications, 2011, 32(1):136-152.

[11] Li M, Li X X, Yuan X M. Convergence analysis of the generalized alternating direction method of multipliers with logarithmic-quadratic proximal regularization[J]. Journal of Optimization Theory and Applications, 2015, 164(1):218-233.

[12] Recht B, Fazel M, Parrilo P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J]. SIAM Review, 2010, 52(3):471-501.

[13] Tao M, Yuan X M. Recovering low-rank and sparse components of matrices from incomplete and noisy observations[J]. SIAM Journal on Optimization, 2011, 21(1):57-81.

[14] Tibshirani R J. Regression shrinkage and selection via the lasso[J]. Journal of the Royal Statistical Society. Series B, 1996, 267-288.

[15] Yang J F, Yuan X M. Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization[J]. Mathematics of Computation, 2013, 82(281):301-329.
[1] 米玲, 薛文娟, 沈春根. 球面上$\ell_1$正则优化的随机临近梯度方法[J]. 计算数学, 2022, 44(1): 34-62.
[2] 刘金魁, 孙悦, 赵永祥. 凸约束伪单调方程组的无导数投影算法[J]. 计算数学, 2021, 43(3): 388-400.
[3] 尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[4] 戴小英. 电子结构计算的数值方法与理论[J]. 计算数学, 2020, 42(2): 131-158.
[5] 林济铿, 袁恺明, 申丹枫, 罗萍萍, 刘阳升. 自适应稀疏伪谱逼近新方法[J]. 计算数学, 2020, 42(1): 80-100.
[6] 张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.
[7] 付姚姚, 曹礼群. 矩阵形式二次修正Maxwell-Dirac系统的多尺度算法[J]. 计算数学, 2019, 41(4): 419-439.
[8] 陈圣杰, 戴彧虹, 徐凤敏. 稀疏线性规划研究[J]. 计算数学, 2018, 40(4): 339-353.
[9] 郭科, 韩德仁. 单调算子理论与分裂算法[J]. 计算数学, 2018, 40(4): 418-435.
[10] 葛志昊, 葛媛媛. 几乎不可压线弹性问题的新的Uzawa型自适应有限元方法[J]. 计算数学, 2018, 40(3): 287-298.
[11] 王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62.
[12] 徐海文, 孙黎明. 一类凸优化的加速混合下降算法[J]. 计算数学, 2017, 39(2): 200-212.
[13] 刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.
[14] 刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112.
[15] 简金宝, 尹江华, 江羡珍. 一个充分下降的有效共轭梯度法[J]. 计算数学, 2015, 37(4): 415-424.
阅读次数
全文


摘要