×

A first-order primal-dual algorithm with linesearch. (English) Zbl 1390.49033

Summary: The paper proposes a linesearch for a primal-dual method. Each iteration of the linesearch requires an update of only the dual (or primal) variable. For many problems, in particular for regularized least squares, the linesearch does not require any additional matrix-vector multiplications. We prove convergence of the proposed method under standard assumptions. We also show an ergodic \(O(1/N)\) rate of convergence for our method. In the case when one or both of the prox-functions are strongly convex, we modify our basic method to get a better convergence rate. Finally, we propose a linesearch for a saddle-point problem with an additional smooth term. Several numerical experiments confirm the efficiency of our proposed methods.

MSC:

49M29 Numerical methods involving duality
65K10 Numerical optimization and variational techniques
65Y20 Complexity and performance of numerical algorithms
90C25 Convex programming

References:

[1] A. Agarwal, S. Negahban, and M. J. Wainwright, {\it Fast global convergence rates of gradient methods for high-dimensional statistical recovery}, in Advances in Neural Information Processing Systems 23, Vancouver, Canada, 2010, pp. 37-45.
[2] H. H. Bauschke and P. L. Combettes, {\it Convex Analysis and Monotone Operator Theory in Hilbert Spaces}, Springer, New York, 2011. · Zbl 1218.47001
[3] A. Beck and M. Teboulle, {\it A fast iterative shrinkage-thresholding algorithm for linear inverse problem}, SIAM J. Imaging Sci., 2 (2009), pp. 183-202. · Zbl 1175.94009
[4] A. Chambolle and T. Pock, {\it A first-order primal-dual algorithm for convex problems with applications to imaging}, J. Math. Imaging. Vis., 40 (2011), pp. 120-145. · Zbl 1255.68217
[5] A. Chambolle and T. Pock, {\it On the ergodic convergence rates of a first-order primal-dual algorithm}, Math. Program., 159 (2016), pp. 253-287. · Zbl 1350.49035
[6] A. Chambolle and T. Pock, {\it An introduction to continuous optimization for imaging}, Acta Numer., 25 (2016), pp. 161-319. · Zbl 1343.65064
[7] 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
[8] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, {\it Efficient projections onto the}{\it \(ℓ_1\)-ball for learning in high dimensions}, in Proceedings of the 25th International Conference on Machine Learning, 2008, pp. 272-279.
[9] T. Goldstein, M. Li, and X. Yuan, {\it Adaptive primal-dual splitting methods for statistical learning and image processing}, in Advances in Neural Information Processing Systems, 2015, pp. 2089-2097.
[10] T. Goldstein, M. Li, X. Yuan, E. Esser, and R. Baraniuk, {\it Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems}, preprint, , 2013.
[11] B. He, H. Yang, and S. Wang, {\it Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities}, J. Optim. Theory Appl., 106 (2000), pp. 337-356. · Zbl 0997.49008
[12] B. He and X. Yuan, {\it Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective}, SIAM J. Imaging Sci., 5 (2012), pp. 119-149. · Zbl 1250.90066
[13] N. Komodakis and J. C. Pesquet, {\it Playing with duality: An overview of recent primal-dual approaches for solving large-scale optimization problems}, IEEE Signal Process. Mag., 32 (2015), pp. 31-54.
[14] Y. Malitsky, {\it Proximal extrapolated gradient methods for variational inequalities}, Optim. Methods Softw., 33 (2018), pp. 140-164, . · Zbl 1483.65107
[15] Y. Malitsky, {\it Reflected projected gradient method for solving monotone variational inequalities}, SIAM J. Optim., 25 (2015), pp. 502-520. · Zbl 1314.47099
[16] T. Pock and A. Chambolle, {\it Diagonal preconditioning for first order primal-dual algorithms in convex optimization}, in 2011 IEEE International Conference on Computer Vision (ICCV), Barcelona, Spain, 2011, pp. 1762-1769.
[17] P. Tseng, {\it A modified forward-backward splitting method for maximal monotone mappings}, SIAM J. Control Optim., 38 (2000), pp. 431-446. · Zbl 0997.90062
[18] B. C. Vu͂, {\it A splitting algorithm for dual monotone inclusions involving cocoercive operators}, Adv. Comput. Math., 38 (2013), pp. 667-681. · Zbl 1284.47045
[19] S. J. Wright, R. D. Nowak, and M. A. Figueiredo, {\it Sparse reconstruction by separable approximation}, IEEE Trans. Signal Process., 57 (2009), pp. 2479-2493. · Zbl 1391.94442
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.