Proximal ADMM with larger step size for two-block separable convex programming and its application to the correlation matrices calibrating problems
-
2167
Downloads
-
3720
Views
Authors
Hongchun Sun
- School of Sciences, Linyi University, Shandong 276005, P. R. China.
Min Sun
- School of Mathematics and Statistics, Zaozhuang University, Shandong 277160, P. R. China.
- School of Management, Qufu Normal University, Shandong 276826, P. R. China.
Yiju Wang
- School of Management, Qufu Normal University, Shandong 276826, P. R. China.
Abstract
The alternating direction method of multipliers (ADMM) is a benchmark for solving two-block separable convex programming. However, as other first-order iteration methods, the ADMM also suffers from low convergence. In this paper, to accelerate the convergence of {the} ADMM, the restriction region of the Fortin and Glowinski's constant \(\gamma\) in the ADMM is relaxed from \(\Big(0,\frac{1+\sqrt{5}}{2}\Big)\) to \((0,+\infty)\), thus we get a proximal ADMM with larger step size. By proving some properties of the method, we show its global
convergence under mild conditions. Finally, some numerical experiments on the correlation matrices calibrating problems are given to demonstrate the efficiency and the performance of the new method.
Share and Cite
ISRP Style
Hongchun Sun, Min Sun, Yiju Wang, Proximal ADMM with larger step size for two-block separable convex programming and its application to the correlation matrices calibrating problems, Journal of Nonlinear Sciences and Applications, 10 (2017), no. 9, 5038--5051
AMA Style
Sun Hongchun, Sun Min, Wang Yiju, Proximal ADMM with larger step size for two-block separable convex programming and its application to the correlation matrices calibrating problems. J. Nonlinear Sci. Appl. (2017); 10(9):5038--5051
Chicago/Turabian Style
Sun, Hongchun, Sun, Min, Wang, Yiju. "Proximal ADMM with larger step size for two-block separable convex programming and its application to the correlation matrices calibrating problems." Journal of Nonlinear Sciences and Applications, 10, no. 9 (2017): 5038--5051
Keywords
- Alternating direction method of multipliers
- the Fortin and Glowinski's constant
- global convergence
MSC
References
-
[1]
J. M. Bardsley, S. Knepper, J. Nagy, Structured linear algebra problems in adaptive optics imaging, Adv. Comput. Math., 35 (2011), 103–117.
-
[2]
H. H. Bauschke, P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces , Springer, New York (2011)
-
[3]
S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2011), 1–122.
-
[4]
H. B. Chen, Y. J. Wang, H. g. Zhao, Finite convergence of a projected proximal point algorithm for generalized variational inequalities, Oper. Res. Lett., 40 (2012), 303–305.
-
[5]
E. Esser, Applications of Lagrangian-based alternating direction methods and connections to split Bregman, , CAM report (2009)
-
[6]
M. Fortin, R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems, Studies in Applied Mathematics, Amsterdam (1983)
-
[7]
M. Fukushima, Fundamentals of Nonlinear Optimization, Asakura Shoten, Tokyo (2001)
-
[8]
R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer, New York (1984)
-
[9]
R. Glowinski, A. Marrocco,, 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, Rev. Francaise Autom. Inf. Recherche Opérationnelle Anal. Numér, 9 (1975), 41–76.
-
[10]
H.-J. He, X.-J. Cai, D. Han, A fast splitting method tailored for Dantzig selectors, Comput. Optim. Appl., 62 (2015), 347–372.
-
[11]
H.-J. He, D. Han, A distributed Douglas-Rachford splitting method for multi-block convex minimization problems, Adv. Comput. Math., 42 (2016), 27–53.
-
[12]
D. R. Han, H. J. He, H. Yang, X. M. Yuan , A customized Douglas-Rachford splitting algorithm for separable convex minimization with linear constraints, Numer. Math., 127 (2014), 167–200.
-
[13]
B.-S. He, L.-S. Hou, X.-M. Yuan , On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming, SIAM J. Optim., 25 (2015), 2274–2312.
-
[14]
B.-S. He, L.-Z. Liao, D. R. Han, H. Yang, A new inexact alternating directions method for monotone variational inequalities, Math. Program., 92 (2002), 103–118.
-
[15]
H.-J. He, C. Ling, H.-K. Xu, An implementable splitting algorithm for the \(\ell_1\)-norm regularized split feasibility problem, J. Sci. Comput., 67 , 281–298. (2016)
-
[16]
B.-S. He, F. Ma, Convergence study on the proximal alternating direction method with larger step size, , manuscript (2017)
-
[17]
B.-S. He, M. Tao, X.-M. Yuan, A splitting method for separable convex programming, IMA J. Numer. Anal., 35 (2015), 394–426.
-
[18]
B.-S. He, S.-L. Wang, H. Yang, A modified variable-penalty alternating direction method for monotone variational inequalities, J. Comput. Math., 21 (2003), 495–504.
-
[19]
B.-S. He, X.-M. Yuan, W.-X. Zhang, A customized proximal point algorithm for convex minimization with linear constraints, Comput. Optim. Appl., 56 (2013), 559–572.
-
[20]
M. Li , A hybrid LQP-based method for structured variational inequalities, Int. J. Comput. Math., 89 (2012), 1412–1425.
-
[21]
J. Liu, Y.-R. Duan, M. Sun, A symmetric version of the generalized alternating direction method of multipliers for two-block separable convex programming, J. Inequal. Appl., 2017 (2017), 21 pages.
-
[22]
H. Qiu, X. Chen, W. Liu, G. Zhou, Y.-J. Wang, J.-H. Lai , A fast \(\ell_1\)-solver and its applications to robust face recognition, J. Ind. Manag. Optim., 8 (2012), 163–178.
-
[23]
R. T. Rockafellar, Convex Analysis, University Press, Princeton (1970)
-
[24]
M. Sun, J. Liu , An inexact generalized PRSM with LQP regularization for structured variational inequalities and its applications traffic equilibrium problems, J. Inequal. Appl., 2016 (2016), 17 pages.
-
[25]
M. Sun, J. Liu, Generalized Peaceman-Rachford splitting method for separable convex programming with applications to image processing, J. Appl. Math. Comput., 51 (2016), 605–622.
-
[26]
M. Sun, Y.-J. Wang, J. Liu, Generalized Peaceman-Rachford splitting method for multiple-block separable convex programming with applications to robust PCA, Calcolo, 54 (2017), 77–94.
-
[27]
K.Wang, J. Desai, H.-J. He, A proximal partially parallel splitting method for separable convex programs, Optim. Methods Softw., 32 (2017), 39–68.
-
[28]
Y. Wang, W. Liu, L. Caccetta, G. Zhou , Parameter selection for nonnegative \(\ell_1\) matrix/tensor sparse decomposition, Operations Research Lett., 43 (2015), 423–426.
-
[29]
Y. Wang, G. Zhou, L. Caccetta, W. Liu, An alternative Lagrange-dual based algorithm for sparse signal reconstruction, IEEE Transactions on Signal Processing, 59 (2011), 1895–1901.
-
[30]
Y.-Y. Xu, Accelerated first-order primal-dual proximal methods for linear constrained composite convex programming, SIAM Journal on Optimization, 27 (2017), 1459–1484.
-
[31]
M. H. Xu, T. Wu, A class of linearized proximal alternating direction methods, J. Optim. Theory Appl., 151 (2011), 321–337.
-
[32]
J.-F. Yang, Y. Zhang, Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 332 (2011), 250–278.
-
[33]
C.-H. Ye, X.-M. Yuan, A descent method for structured monotone variational inequalities, Optim. Methods Softw., 22 (2007), 329–338.
-
[34]
X.-M. Yuan, An improved proximal alternating direction method for monoton variational inequalities with separable structure, Computational Optimization and Applications, 49 (2011), 17–29.