Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. (English) Zbl 1373.90111
Summary: Motivated by big data applications, first-order methods have been extremely popular in recent years. However, naive gradient methods generally converge slowly. Hence, much effort has been made to accelerate various first-order methods. This paper proposes two accelerated methods towards solving structured linearly constrained convex programming, for which we assume composite convex objective that is the sum of a differentiable function and a possibly nondifferentiable one. The first method is the accelerated linearized augmented Lagrangian method (LALM). At each update to the primal variable, it allows linearization to the differentiable function and also the augmented term, and thus it enables easy subproblems. Assuming merely convexity, we show that LALM owns \(O(1/t)\) convergence if parameters are kept fixed during all the iterations and can be accelerated to \(O(1/t^2)\) if the parameters are adapted, where \(t\) is the number of total iterations. The second method is the accelerated linearized alternating direction method of multipliers (LADMM). In addition to the composite convexity, it further assumes two-block structure on the objective. Different from classic alternating direction method of multipliers, our method allows linearization to the objective and also augmented term to make the update simple. Assuming strong convexity on one block variable, we show that LADMM also enjoys \(O(1/t^2)\) convergence with adaptive parameters. This result is a significant improvement over that in [T. Goldstein et al., SIAM J. Imaging Sci. 7, No. 3, 1588–1623 (2014; Zbl 1314.49019)], which requires strong convexity on both block variables and no linearization to the objective or augmented term. Numerical experiments are performed on quadratic programming, image denoising, and support vector machine. The proposed accelerated methods are compared to nonaccelerated ones and also existing accelerated methods. The results demonstrate the validity of acceleration and superior performance of the proposed methods over existing ones.
MSC:
| 90C25 | Convex programming |
| 90C06 | Large-scale problems in mathematical programming |
| 68W40 | Analysis of algorithms |
| 49M27 | Decomposition methods |
Keywords:
acceleration; linearization; first-order method; augmented Lagrangian method (ALM); alternating direction method of multipliers (ADMM)Citations:
Zbl 1314.49019References:
| [1] | A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problems}, SIAM J. Imag. Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009 |
| [2] | D. P. Bertsekas, {\it Constrained Optimization and Lagrange Multiplier Methods}, Academic Press, New York, 2014. · Zbl 0572.90067 |
| [3] | K. Bredies and H. Sun, {\it Accelerated Douglas-Rachford methods for the solution of convex-concave saddle-point problems}, preprint, , (2016). |
| [4] | A. Chambolle and T. Pock, {\it A first-order primal-dual algorithm for convex problems with applications to imaging}, J. Math. Imaging Vision, 40 (2011), pp. 120-145. · Zbl 1255.68217 |
| [5] | Y. Chen, G. Lan, and Y. Ouyang, {\it Optimal primal-dual methods for a class of saddle point problems}, SIAM J. Optim., 24 (2014), pp. 1779-1814. · Zbl 1329.90090 |
| [6] | L. Condat, {\it A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms}, J. Optim. Theory Appl., 158 (2013), pp. 460-479. · Zbl 1272.90110 |
| [7] | C. Dang and G. Lan, {\it Randomized methods for saddle point computation}, preprint, , 2014. |
| [8] | W. Deng and W. Yin, {\it On the global and linear convergence of the generalized alternating direction method of multipliers}, J. Sci. Comput., 66 (2016), pp. 889-916. · Zbl 1379.65036 |
| [9] | O. Fercoq and P. Richtárik, {\it Accelerated, parallel, and proximal coordinate descent}, SIAM J. Optim., 25 (2015), pp. 1997-2023. · Zbl 1327.65108 |
| [10] | D. Gabay and B. Mercier, {\it A dual algorithm for the solution of nonlinear variational problems via finite element approximation}, Comput. Math. Appl., 2 (1976), pp. 17-40. · Zbl 0352.65034 |
| [11] | X. Gao, Y. Xu, and S. Zhang, {\it Randomized primal-dual proximal block coordinate updates}, arXiv preprint , 2016. |
| [12] | X. Gao and S.-Z. Zhang, {\it First-order algorithms for convex optimization with nonseparable objective and coupled constraints}, J. Oper. Res. Soc. China, (2015), pp. 1-29. |
| [13] | S. Ghadimi and G. Lan, {\it Accelerated gradient methods for nonconvex nonlinear and stochastic programming}, Math. Prog., 156 (2016), pp. 59-99. · Zbl 1335.62121 |
| [14] | R. Glowinski and A. Marrocco, {\it Sur l’approximation, par eléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires}, ESAIM: Math. Model. Numer. Anal., 9 (1975), pp. 41-76. · Zbl 0368.65053 |
| [15] | D. Goldfarb, S. Ma, and K. Scheinberg, {\it Fast alternating linearization methods for minimizing the sum of two convex functions}, Math. Prog., 141 (2013), pp. 349-382. · Zbl 1280.65051 |
| [16] | T. Goldstein, B. O’Donoghue, S. Setzer, and R. Baraniuk, {\it Fast alternating direction optimization methods}, SIAM J. Imag. Sci., 7 (2014), pp. 1588-1623. · Zbl 1314.49019 |
| [17] | M. Grant, S. Boyd, and Y. Ye, {\it CVX: Matlab software for disciplined convex programming}, 2008. |
| [18] | B. He and X. Yuan, {\it On the acceleration of augmented Lagrangian method for linearly constrained optimization}, Optimization online, 3 (2010). |
| [19] | Y. He and R. D. Monteiro, {\it An accelerated hpe-type algorithm for a class of composite convex-concave saddle-point problems}, SIAM J. Optim., 26 (2016), pp. 29-56. · Zbl 1329.90179 |
| [20] | M. Hong and Z.-Q. Luo, {\it On the linear convergence of the alternating direction method of multipliers}, Math. Program. Ser. A, 162 (2017), pp. 165-199. · Zbl 1362.90313 |
| [21] | B. Huang, S. Ma, and D. Goldfarb, {\it Accelerated linearized Bregman method}, J. Sci. Comput., 54 (2013), pp. 428-453. · Zbl 1271.65096 |
| [22] | M. Kadkhodaie, K. Christakopoulou, M. Sanjabi, and A. Banerjee, {\it Accelerated alternating direction method of multipliers}, in Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015, pp. 497-506. |
| [23] | M. Kang, M. Kang, and M. Jung, {\it Inexact accelerated augmented Lagrangian methods}, Comput. Optim. Appl., 62 (2015), pp. 373-404. · Zbl 1353.90145 |
| [24] | M. Kang, S. Yun, H. Woo, and M. Kang, {\it Accelerated Bregman method for linearly constrained \(ℓ_1--ℓ_2\) minimization}, J. Sci. Comput., 56 (2013), pp. 515-534. · Zbl 1276.65033 |
| [25] | G. Lan, {\it An optimal method for stochastic composite optimization}, Math. Prog., 133 (2012), pp. 365-397. · Zbl 1273.90136 |
| [26] | Q. Lin, Z. Lu, and L. Xiao, {\it An accelerated proximal coordinate gradient method}, in Adv. Neural Info. Process. Sys., 2014, pp. 3059-3067. |
| [27] | Y. Nesterov, {\it A method of solving a convex programming problem with convergence rate \({O}(1/k^2)\)}, Soviet Math. Doklady, 27 (1983), pp. 372-376. · Zbl 0535.90071 |
| [28] | Y. Nesterov, {\it Excessive gap technique in nonsmooth convex minimization}, SIAM J. Optim., 16 (2005), pp. 235-249. · Zbl 1096.90026 |
| [29] | Y. Nesterov, {\it Smooth minimization of non-smooth functions}, Math. Program. Ser. A, 103 (2005), pp. 127-152. · Zbl 1079.90102 |
| [30] | Y. Nesterov, {\it Gradient methods for minimizing composite functions}, Math. Program. Ser. B, 140 (2013), pp. 125-161. · Zbl 1287.90067 |
| [31] | R. Nishihara, L. Lessard, B. Recht, A. Packard, and M. Jordan, {\it A general analysis of the convergence of ADMM}, in Proceedings of the 32nd International Conference on Machine Learning, Lille, France, 2015, pp. 343-352. |
| [32] | J. Nocedal and S. Wright, {\it Numerical Optimization}, Springer Science & Business Media, New York, 2006. · Zbl 1104.65059 |
| [33] | B. ÓDonoghue and E. Candes, {\it Adaptive restart for accelerated gradient schemes}, Found. Comput. Math., 15 (2015), pp. 715-732. · Zbl 1320.90061 |
| [34] | Y. Ouyang, Y. Chen, G. Lan, and E. Pasiliao Jr, {\it An accelerated linearized alternating direction method of multipliers}, SIAM J. Imaging Sci., 8 (2015), pp. 644-681. · Zbl 1321.90105 |
| [35] | W. Su, S. Boyd, and E. Candes, {\it A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights}, J. Mach. Learn. Res., 17 (2016), pp. 1-43. · Zbl 1391.90667 |
| [36] | P. Tseng, {\it On Accelerated Proximal Gradient Methods for Convex-Concave Optimization}, preprint, 2008. |
| [37] | Y. Wang, J. Yang, W. Yin, and Y. Zhang, {\it A new alternating minimization algorithm for total variation image reconstruction}, SIAM J. Imag. Sci., 1 (2008), pp. 248-272. · Zbl 1187.68665 |
| [38] | A. Wibisono, A. C. Wilson, and M. I. Jordan, {\it A variational perspective on accelerated methods in optimization}, Proc. Natl Acad. Sci. USA, (2016), pp. E7351-E7358. · Zbl 1404.90098 |
| [39] | Y. Xu, I. Akrotirianakis, and A. Chakraborty, {\it Proximal gradient method for huberized support vector machine}, Pattern Anal. Appl., 19 (2016), pp. 989-1005. · Zbl 1425.68358 |
| [40] | Y. Xu and W. Yin, {\it A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion}, SIAM J. Imag. Sci., 6 (2013), pp. 1758-1789. · Zbl 1280.49042 |
| [41] | Y. Xu and S. Zhang, {\it Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization}, preprint, , 2017. · Zbl 1391.90483 |
| [42] | G.-B. Ye, Y. Chen, and X. Xie, {\it Efficient variable selection in support vector machines via the alternating direction method of multipliers.}, in Proceedings of the 14th AISTATS, Ft. Lauderdale, 2011, pp. 832-840. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
