×

A golden ratio primal-dual algorithm for structured convex optimization. (English) Zbl 1468.90082

Summary: We design, analyze and test a golden ratio primal-dual algorithm (GRPDA) for solving structured convex optimization problem, where the objective function is the sum of two closed proper convex functions, one of which involves a composition with a linear transform. GRPDA preserves all the favorable features of the classical primal-dual algorithm (PDA), i.e., the primal and the dual variables are updated in a Gauss-Seidel manner, and the per iteration cost is dominated by the evaluation of the proximal point mappings of the two component functions and two matrix-vector multiplications. Compared with the classical PDA, which takes an extrapolation step, the novelty of GRPDA is that it is constructed based on a convex combination of essentially the whole iteration trajectory. We show that GRPDA converges within a broader range of parameters than the classical PDA, provided that the reciprocal of the convex combination parameter is bounded above by the golden ratio, which explains the name of the algorithm. An \(\mathcal{O}(1/N)\) ergodic convergence rate result is also established based on the primal-dual gap function, where \(N\) denotes the number of iterations. When either the primal or the dual problem is strongly convex, an accelerated GRPDA is constructed to improve the ergodic convergence rate from \(\mathcal{O}(1/N)\) to \(\mathcal{O}(1/N^2)\). Moreover, we show for regularized least-squares and linear equality constrained problems that the reciprocal of the convex combination parameter can be extended from the golden ratio to 2 and meanwhile a relaxation step can be taken. Our preliminary numerical results on LASSO, nonnegative least-squares and minimax matrix game problems, with comparisons to some state-of-the-art relative algorithms, demonstrate the efficiency of the proposed algorithms.

MSC:

90C25 Convex programming
65K10 Numerical optimization and variational techniques
65Y20 Complexity and performance of numerical algorithms

Software:

PDCO; LSQR
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bauschke, HH; Combettes, PL, Convex Analysis and Monotone Operator Theory in Hilbert Spaces (2011), Cham: Springer, Cham · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7
[2] Beck, A., First-Order Methods in Optimization (2017), Philadelphia: SIAM-Society for Industrial and Applied Mathematics, Philadelphia · Zbl 1384.65033 · doi:10.1137/1.9781611974997
[3] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[4] Bertsekas, DP; Gafni, EM, Projection methods for variational inequalities with application to the traffic assignment problem, Math. Program. Stud., 17, 139-159 (1982) · Zbl 0478.90071 · doi:10.1007/BFb0120965
[5] Bouwmans, T., Aybat, N.S., Zahzah, E.H.: Algorithms for Stable PCA. In: Bouwmans, T., Aybat, N.S., Zahzah, E. (eds.) Handbook of Robust Low-Rank and Sparse Matrix Decomposition: Applications in Image and Video Processing, chap. 2. CRC Press, Taylor and Francis Group (2016) · Zbl 1339.68002
[6] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2010) · Zbl 1229.90122 · doi:10.1561/2200000016
[7] Chambolle, A.; Ehrhardt, MJ; Richtarik, P.; Schonlieb, C-B, Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging application, SIAM J. Optim., 28, 4, 2783-2808 (2018) · Zbl 06951767 · doi:10.1137/17M1134834
[8] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 1, 120-145 (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[9] Chambolle, A.; Pock, T., On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program., 159, 1-2, 253-287 (2016) · Zbl 1350.49035 · doi:10.1007/s10107-015-0957-3
[10] Chen, S.; Saunders, MA; Donoho, DL, Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010 · doi:10.1137/S003614450037906X
[11] Donoho, DL, Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[12] Duchi, J., Shalev-Shwartz, S., Singer, Y., Chandra, T.: Efficient projections onto the \(l_1\)-ball for learning in high dimensions. In: The 25th International Conference on Machine Learning, pp. 272-279 (2008)
[13] Esser, E.; Zhang, X.; Chan, TF, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci., 3, 4, 1015-1046 (2010) · Zbl 1206.90117 · doi:10.1137/09076934X
[14] Fazel, M.; Pong, TK; Sun, DF; Tseng, P., Hankel matrix rank minimization with applications in system identification and realization, SIAM J. Matrix Anal. Appl., 34, 946-977 (2013) · Zbl 1302.90127 · doi:10.1137/110853996
[15] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appl., 2, 17-40 (1976) · Zbl 0352.65034 · doi:10.1016/0898-1221(76)90003-1
[16] Glowinski, R., Marrocco, 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. R.A.I.R.O., R2 9(R-2), 41-76 (1975) · Zbl 0368.65053
[17] Hayden, S.; Stanley, O., A low patch-rank interpretation of texture, SIAM J. Imaging Sci., 6, 1, 226-262 (2013) · Zbl 1335.68287 · doi:10.1137/110854989
[18] He, B.; Yuan, X., Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci., 5, 1, 119-149 (2012) · Zbl 1250.90066 · doi:10.1137/100814494
[19] Jonathan, E.; Dimitri, P., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 1-3, 293-318 (1992) · Zbl 0765.90073
[20] Lions, PL; Mercier, B., Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 6, 964-979 (1979) · Zbl 0426.65050 · doi:10.1137/0716071
[21] Liu, Y., Xu, Y., Yin, W.: Acceleration of primal-dual methods by preconditioning and simple subproblem procedures. arXiv:1811.08937v2 (2018)
[22] Malitsky, Y.: Golden ratio algorithms for variational inequalities. Math. Program. (to appear) · Zbl 07263698
[23] Malitsky, Y.; Pock, T., A first-order primal-dual algorithm with linesearch, SIAM J. Optim., 28, 1, 411-432 (2018) · Zbl 1390.49033 · doi:10.1137/16M1092015
[24] Monteiro, RDC; Svaiter, BF, Complexity of variants of Tseng’s modified FB splitting and Korpelevich’s methods for hemivariational inequalities with applications to saddle-point and convex optimization problems, SIAM J. Optim., 21, 4, 1688-1720 (2011) · Zbl 1245.90155 · doi:10.1137/100801652
[25] Nedic, A.; Ozdaglar, A., Subgradient methods for saddle-point problems, J. Optim. Theory Appl., 142, 1, 205-228 (2009) · Zbl 1175.90415 · doi:10.1007/s10957-009-9522-7
[26] Needell, D.; Ward, R., Near-optimal compressed sensing guarantees for anisotropic and isotropic total variation minimization, IEEE Trans. Image Process., 22, 10, 3941-3949 (2013) · Zbl 1373.94673 · doi:10.1109/TIP.2013.2264681
[27] Nemirovski, A., Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15, 1, 229-251 (2006) · Zbl 1106.90059 · doi:10.1137/S1052623403425629
[28] Paige, CC; Saunders, MA, Lsqr: an algorithm for sparselinear equations and sparse least squares, ACM Trans. Math. Soft., 8, 43-71 (1982) · Zbl 0478.65016 · doi:10.1145/355984.355989
[29] Pock, T., Chambolle, A.: Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: IEEE International Conference on Computer Vision, pp. 1762-1769 (2011)
[30] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton · Zbl 0932.90001 · doi:10.1515/9781400873173
[31] Shefi, R.; Teboulle, M., Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex minimization, SIAM J. Optim., 24, 1, 269-297 (2014) · Zbl 1291.90176 · doi:10.1137/130910774
[32] Tibshirani, R., Regression shrinkage and selection via the lasso, J. R. Stat. Soc., 58, 1, 267-288 (1996) · Zbl 0850.62538
[33] Uzawa, H.; Arrow, KJ; Hurwicz, L.; Uzawa, H., Iterative methods for concave programming, Studies in Linear and Nonlinear Programming (1958), Stanford, CA: Stanford University Press, Stanford, CA · Zbl 0091.16002
[34] Yang, J.; Zhang, Y., Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 1, 250-278 (2011) · Zbl 1256.65060 · doi:10.1137/090777761
[35] Zhu, M., Chan, T.F.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. In: CAM Report 08-34, UCLA, Los Angeles, CA (2008)
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.