Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Accelerated Uzawa methods for convex optimization


Authors: Min Tao and Xiaoming Yuan
Journal: Math. Comp. 86 (2017), 1821-1845
MSC (2010): Primary 90C25; Secondary 94A08
DOI: https://doi.org/10.1090/mcom/3145
Published electronically: October 20, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We focus on a linearly constrained strongly convex minimization model and discuss the application of the classical Uzawa method. Our principal goal is to show that some existing acceleration schemes can be used to accelerate the Uzawa method in the sense that the worst-case convergence rate (measured by the iteration complexity) of the resulting accelerated Uzawa schemes is $ O(1/k^2)$ where $ k$ represents the iteration counter. Our discussion assumes that the objective function is given by a black-box oracle; thus an inexact version of the Uzawa method with a sequence of dynamically-chosen step sizes is implemented. A worst-case convergence rate of $ O(1/k)$ is also shown for this inexact version. Some preliminary numerical results are reported to verify the acceleration effectiveness of the accelerated Uzawa schemes and their superiority over some existing methods.


References [Enhancements On Off] (What's this?)

  • [1] Kenneth J. Arrow, Leonid Hurwicz, and Hirofumi Uzawa, Studies in Linear and Non-Linear Programming, With contributions by H. B. Chenery, S. M. Johnson, S. Karlin, T. Marschak, R. M. Solow. Stanford Mathematical Studies in the Social Sciences, vol. II, Stanford University Press, Stanford, Calif., 1958. MR 0108399
  • [2] Alfred Auslender and Marc Teboulle, Interior gradient and proximal methods for convex and conic optimization, SIAM J. Optim. 16 (2006), no. 3, 697-725. MR 2197553, https://doi.org/10.1137/S1052623403427823
  • [3] Ivo Babuška, The finite element method with Lagrangian multipliers, Numer. Math. 20 (1972/73), 179-192. MR 0359352
  • [4] Constantin Bacuta, A unified approach for Uzawa algorithms, SIAM J. Numer. Anal. 44 (2006), no. 6, 2633-2649. MR 2272609, https://doi.org/10.1137/050630714
  • [5] Amir Beck and Marc Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), no. 1, 183-202. MR 2486527, https://doi.org/10.1137/080716542
  • [6] Amir Beck and Marc Teboulle, Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process. 18 (2009), no. 11, 2419-2434. MR 2722312, https://doi.org/10.1109/TIP.2009.2028250
  • [7] Dimitri P. Bertsekas, On the Goldstein-Levitin-Polyak gradient projection method, IEEE Trans. Automatic Control AC-21 (1976), no. 2, 174-184. MR 0416017
  • [8] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation, Numerical Methods, Prentice-Hall, Englewood Cliffs, NJ, 1989.
  • [9] Åke Björck, Numerical Methods for Least Squares Problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1996. MR 1386889
  • [10] Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, 2004. MR 2061575
  • [11] James H. Bramble, The Lagrange multiplier method for Dirichlet's problem, Math. Comp. 37 (1981), no. 155, 1-11. MR 616356, https://doi.org/10.2307/2007496
  • [12] James H. Bramble, Joseph E. Pasciak, and Apostol T. Vassilev, Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal. 34 (1997), no. 3, 1072-1092. MR 1451114, https://doi.org/10.1137/S0036142994273343
  • [13] Franco Brezzi and Michel Fortin, Mixed and Hybrid Finite Element Methods, Springer Series in Computational Mathematics, vol. 15, Springer-Verlag, New York, 1991. MR 1115205
  • [14] Jian-Feng Cai, Emmanuel J. Candès, and Zuowei Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim. 20 (2010), no. 4, 1956-1982. MR 2600248, https://doi.org/10.1137/080738970
  • [15] Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for compressed sensing, Math. Comp. 78 (2009), no. 267, 1515-1536. MR 2501061, https://doi.org/10.1090/S0025-5718-08-02189-3
  • [16] Jian-Feng Cai, Stanley Osher, and Zuowei Shen, Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sci. 2 (2009), no. 1, 226-252. MR 2486529, https://doi.org/10.1137/080733371
  • [17] Antonin Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging Vision 20 (2004), no. 1-2, 89-97. Special issue on mathematics and image analysis. MR 2049783, https://doi.org/10.1023/B:JMIV.0000011320.81911.38
  • [18] Antonin Chambolle and Thomas Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vision 40 (2011), no. 1, 120-145. MR 2782122, https://doi.org/10.1007/s10851-010-0251-1
  • [19] Raymond H. Chan and Michael K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev. 38 (1996), no. 3, 427-482. MR 1409592, https://doi.org/10.1137/S0036144594276474
  • [20] Raymond H. Chan, Min Tao, and Xiaoming Yuan, Constrained total variation deblurring models and fast algorithms based on alternating direction method of multipliers, SIAM J. Imaging Sci. 6 (2013), no. 1, 680-697. MR 3036992, https://doi.org/10.1137/110860185
  • [21] R. H. Chan, B. Morini and M. Porcelli, Affine scaling methods for image deblurring problems, American Institute of Physics Conference Proceedings 1281 (2010), no. 11, 1043-1046.
  • [22] Howard C. Elman and Gene H. Golub, Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal. 31 (1994), no. 6, 1645-1661. MR 1302679, https://doi.org/10.1137/0731085
  • [23] Ernie Esser, Xiaoqun Zhang, and Tony F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci. 3 (2010), no. 4, 1015-1046. MR 2763706, https://doi.org/10.1137/09076934X
  • [24] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appl. 2 (1976), no. 1, 17-40.
  • [25] R. Glowinski and 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. Française Automat. Informat. Recherche Opérationnelle Sér. Rouge Anal. Numér. 9 (1975), no. R-2, 41-76 (French, with Loose English summary). MR 0388811
  • [26] Roland Glowinski and Patrick Le Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM Studies in Applied Mathematics, vol. 9, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1989. MR 1060954
  • [27] Tom Goldstein and Stanley Osher, The split Bregman method for $ L1$-regularized problems, SIAM J. Imaging Sci. 2 (2009), no. 2, 323-343. MR 2496060, https://doi.org/10.1137/080725891
  • [28] Bingsheng He and Xiaoming Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective, SIAM J. Imaging Sci. 5 (2012), no. 1, 119-149. MR 2902659, https://doi.org/10.1137/100814494
  • [29] Magnus R. Hestenes, Multiplier and gradient methods, J. Optimization Theory Appl. 4 (1969), 303-320. MR 0271809
  • [30] G. M. Korpelevič, An extragradient method for finding saddle points and for other problems, Èkonom. i Mat. Metody 12 (1976), no. 4, 747-756 (Russian). MR 0451121
  • [31] P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal. 16 (1979), no. 6, 964-979. MR 551319, https://doi.org/10.1137/0716071
  • [32] B. Martinet, Régularisation d'inéquations variationnelles par approximations successives, Rev. Française Informat. Recherche Opérationnelle 4 (1970), no. Ser. R-3, 154-158 (French). MR 0298899
  • [33] Benedetta Morini, Margherita Porcelli, and Raymond H. Chan, A reduced Newton method for constrained linear least-squares problems, J. Comput. Appl. Math. 233 (2010), no. 9, 2200-2212. MR 2577759, https://doi.org/10.1016/j.cam.2009.10.006
  • [34] A. S. Nemirovsky and D. B. Yudin, Problem Complexity and Method Efficiency in Optimization, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1983. Translated from the Russian and with a preface by E. R. Dawson. MR 702836
  • [35] Yu. E. Nesterov, A method for solving the convex programming problem with convergence rate $ O(1/k^{2})$, Dokl. Akad. Nauk SSSR 269 (1983), no. 3, 543-547 (Russian). MR 701288
  • [36] Yu. E. Nesterov, Smooth minimization of non-smooth functions, Math. Program. 103 (2005), no. 1, Ser. A, 127-152. MR 2166537, https://doi.org/10.1007/s10107-004-0552-5
  • [37] Yu. E. Nesterov, Gradient methods for minimizing composite functions, Math. Program. 140 (2013), no. 1, Ser. B, 125-161. MR 3071865, https://doi.org/10.1007/s10107-012-0629-5
  • [38] Stanley Osher, Yu Mao, Bin Dong, and Wotao Yin, Fast linearized Bregman iteration for compressive sensing and sparse denoising, Commun. Math. Sci. 8 (2010), no. 1, 93-111. MR 2655902
  • [39] L. D. Popov, A modification of the Arrow-Hurwitz method of search for saddle points, Mat. Zametki 28 (1980), no. 5, 777-784, 803 (Russian). MR 599872
  • [40] M. J. D. Powell, A method for nonlinear constraints in minimization problems, Optimization (Sympos., Univ. Keele, Keele, 1968) Academic Press, London, 1969, pp. 283-298. MR 0272403
  • [41] R. Tyrrell Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optimization 14 (1976), no. 5, 877-898. MR 0410483
  • [42] Leonid I. Rudin, Stanley Osher, and Emad Fatemi, Nonlinear total variation based noise removal algorithms, Phys. D 60 (1992), no. 1-4, 259-268. Experimental mathematics: computational issues in nonlinear science (Los Alamos, NM, 1991). MR 3363401
  • [43] P. Tseng, On the accelerated proximal gradient methods for convex-concave optimization, manuscript, 2008, available at http://www.math.washington.edu/ tseng/papers/apgm.pdf.
  • [44] Wotao Yin, Analysis and generalizations of the linearized Bregman model, SIAM J. Imaging Sci. 3 (2010), no. 4, 856-877. MR 2735964, https://doi.org/10.1137/090760350
  • [45] Hui Zhang, Jian-Feng Cai, Lizhi Cheng, and Jubo Zhu, Strongly convex programming for exact matrix completion and robust principal component analysis, Inverse Probl. Imaging 6 (2012), no. 2, 357-372. MR 2942744, https://doi.org/10.3934/ipi.2012.6.357
  • [46] Xiaoqun Zhang, Martin Burger, and Stanley Osher, A unified primal-dual algorithm framework based on Bregman iteration, J. Sci. Comput. 46 (2011), no. 1, 20-46. MR 2753250, https://doi.org/10.1007/s10915-010-9408-8
  • [47] M. Zhu and T. F. Chan, An efficient primal-dual hybrid gradient algorithm, CAM Report 08-34, UCLA, Los Angeles, CA, 2008.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 90C25, 94A08

Retrieve articles in all journals with MSC (2010): 90C25, 94A08


Additional Information

Min Tao
Affiliation: Department of Mathematics, Nanjing University, Nanjing, 210093, People’s Republic of China
Email: taom@nju.edu.cn

Xiaoming Yuan
Affiliation: Department of Mathematics, Hong Kong Baptist University, Hong Kong, People’s Republic of China
Email: xmyuan@hkbu.edu.hk

DOI: https://doi.org/10.1090/mcom/3145
Keywords: Convex optimization, Uzawa method, acceleration, convergence rate, black-box oracle
Received by editor(s): March 31, 2015
Received by editor(s) in revised form: January 28, 2016
Published electronically: October 20, 2016
Additional Notes: The first author was supported by the Natural Science Foundation of China grant NSFC-11301280, and the Fundamental Research Funds for the Central Universities, 020314330019
The second author was supported in part by the General Research Fund from Hong Kong Research Grants Council, HKBU 12300515
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society