SpringerLink
Log in

Fast alternating linearization methods for minimizing the sum of two convex functions

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We present in this paper alternating linearization algorithms based on an alternating direction augmented Lagrangian approach for minimizing the sum of two convex functions. Our basic methods require at most \({O(1/\epsilon)}\) iterations to obtain an \({\epsilon}\) -optimal solution, while our accelerated (i.e., fast) versions of them require at most \({O(1/\sqrt{\epsilon})}\) iterations, with little change in the computational effort required at each iteration. For both types of methods, we present one algorithm that requires both functions to be smooth with Lipschitz continuous gradients and one algorithm that needs only one of the functions to be so. Algorithms in this paper are Gauss-Seidel type methods, in contrast to the ones proposed by Goldfarb and Ma in (Fast multiple splitting algorithms for convex optimization, Columbia University, 2009) where the algorithms are Jacobi type methods. Numerical results are reported to support our theoretical conclusions and demonstrate the practical potential of our algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Canada)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Afonso M., Bioucas-Dias J., Figueiredo M.: Fast image recoery using variable splitting and constrained optimization. IEEE Trans. Image Process. 19, 2345–2356 (2010)

    Article  MathSciNet  Google Scholar 

  2. Afonso M., Bioucas-Dias J., Figueiredo M.: An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems. IEEE Trans. Image Process. 20, 681–695 (2011)

    Article  MathSciNet  Google Scholar 

  3. Aybat, N.S., Goldfarb, D., Iyengar, G.: Fast first-order methods for stable principal component pursuit. Preprint available at http://arxiv.org/abs/1105.2126 (2011)

  4. Banerjee O., El Ghaoui L., d’Aspremont A.: Model selection through sparse maximum likelihood estimation for multivariate gaussian for binary data. J. Mach. Learn. Res. 9, 485–516 (2008)

    MathSciNet  MATH  Google Scholar 

  5. Beck A., Teboulle M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  6. Bertsekas D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)

    Google Scholar 

  7. Candès E.J., Li X., Ma Y., Wright J.: Robust principal component analysis?. J. ACM 58, 1–37 (2011)

    Article  Google Scholar 

  8. Candès E.J., Recht B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Candès E.J., Romberg J., Tao T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52, 489–509 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Candès E.J., Tao T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inform. Theory 56, 2053–2080 (2009)

    Article  Google Scholar 

  11. Combettes P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53, 475–504 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  12. Combettes P.L., Pesquet Jean-Christophe: A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Top. Signal Process. 1, 564–574 (2007)

    Article  Google Scholar 

  13. Combettes P.L., Wajs V.R.: Signal recovery by proximal forward-backward splitting. SIAM J. Multiscale Model. Simul. 4, 1168–1200 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Donoho D.: Compressed sensing. IEEE Trans. Inform. Theory 52, 1289–1306 (2006)

    Article  MathSciNet  Google Scholar 

  15. Douglas J., Rachford H.H.: On the numerical solution of the heat conduction problem in 2 and 3 space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)

    Article  MathSciNet  MATH  Google Scholar 

  16. Eckstein J., Bertsekas D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  17. Eckstein J., Svaiter B.F.: A family of projective splitting methods for sum of two maximal monotone operators. Math. Program. Ser. B 111, 173–199 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  18. Figueiredo M., Nowak R.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process. 12, 906–916 (2003)

    Article  MathSciNet  Google Scholar 

  19. Friedman J., Hastie T., Tibshirani R.: Sparse inverse covariance estimation with the graphical lasso. Biostatistics 9(3), 432–441 (2008)

    Article  MATH  Google Scholar 

  20. Gabay D., Mercier B.: A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Comp. Math. Appl. 2, 17–40 (1976)

    Article  MATH  Google Scholar 

  21. Glowinski R., Le Tallec P.: Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia (1989)

    Book  MATH  Google Scholar 

  22. Goldfarb, D., Ma, S.: Fast multiple splitting algorithms for convex optimization. Technical report, Department of IEOR, Columbia University. Preprint available at http://arxiv.org/abs/0912.4570 (2009)

  23. Goldfarb D., Ma S.: Convergence of fixed point continuation algorithms for matrix rank minimization. Found. Comput. Math. 11, 183–210 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  24. Goldfarb, D., Scheinberg, K.: Fast first-order methods for composite convex optimization with line search. Technical report, Department of IEOR, Columbia University (2011)

  25. Goldstein T., Osher S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2, 323–343 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  26. Hale E.T., Yin W., Zhang Y.: Fixed-point continuation for ℓ1-minimization: Methodology and convergence. SIAM J. Optim. 19, 1107–1130 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  27. He B.S., Liao L.-Z., Han D., Yang H.: A new inexact alternating direction method for monotone variational inequalities. Math. Program. 92, 103–118 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  28. He, B.S., Tao, M., Xu, M., Yuan, X.: Alternating direction based contraction method for generally separable linearly constrained convex programming problems. Optimization-online: http://www.optimization-online.org/DB_HTML/2009/11/2465.html (2009)

  29. He B.S., Yang H., Wang S.L.: Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory Appl. 106, 337–356 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  30. Keshavan R.H., Montanari A., Oh S.: Matrix completion from a few entries. IEEE Trans. Info. Theory 56, 2980–2998 (2010)

    Article  MathSciNet  Google Scholar 

  31. Kiwiel K.C., Rosa C.H., Ruszczynski A.: Proximal decomposition via alternating linearization. SIAM J. Optim. 9, 668–689 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  32. Lions P.L., Mercier B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  33. Ma S., Goldfarb D., Chen L.: Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program. Ser. A 128, 321–353 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  34. Malick J., Povh J., Rendl F., Wiegele A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20, 336–356 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  35. Monteiro, R.D.C., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating minimization augmented Lagrangian method. Technical report, School of ISyE, Georgia Tech (2010)

  36. Nesterov Y.E.: A method for unconstrained convex minimization problem with the rate of convergence \({\mathcal{O}(1/k^2)}\) . Dokl. Akad. Nauk SSSR 269, 543–547 (1983)

    MathSciNet  Google Scholar 

  37. Nesterov, Y.E.: Introductory lectures on convex optimization. 87, xviii+236 (2004). A basic course

  38. Nesterov Y.E.: Smooth minimization for non-smooth functions. Math. Program. Ser. A 103, 127–152 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  39. Nesterov, Y.E.: Gradient methods for minimizing composite objective function. CORE Discussion Paper 2007/76 (2007)

  40. Peaceman D.H., Rachford H.H.: The numerical solution of parabolic elliptic differential equations. SIAM J. Appl. Math. 3, 28–41 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  41. Recht B., Fazel M., Parrilo P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 471–501 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  42. Scheinberg, K., Ma, S., Goldfarb, D.: Sparse inverse covariance selection via alternating linearization methods. In: Proceedings of the Neural Information Processing Systems (NIPS) (2010)

  43. S**arn J.E.: Partial inverse of a monotone operator. Appl. Math. Optim. 10, 247–265 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  44. Toh K.-C., Yun S.: An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pac. J. Optim. 6, 615–640 (2010)

    MathSciNet  MATH  Google Scholar 

  45. Tseng P.: Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming. Math. Program. 48, 249–263 (1990)

    Article  MATH  Google Scholar 

  46. Tseng P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29, 119–138 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  47. Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Technical report, Department of Mathematics, University of Washington (2008)

  48. Wainwright M., Ravikumar P., Lafferty J.: High-dimensional graphical model selection using ℓ1-regularized logistic regression. NIPS 19, 1465–1472 (2007)

    Google Scholar 

  49. Wen Z., Goldfarb D., Yin W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2, 203–230 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  50. Yang J., Zhang Y.: Alternating direction algorithms for ℓ1 problems in compressive sensing. SIAM J. Sci. Comput. 33, 250–278 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  51. Yuan M., Lin Y.: Model selection and estimation in the Gaussian graphical model. Biometrika 94, 19–35 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  52. Yuan X. (2009) Alternating direction methods for sparse covariance selection. Preprint available at http://www.optimization-online.org/DB_HTML/2009/09/2390.html

  53. Yuan, X., Yang, J.: Sparse and low rank matrix decomposition via alternating direction methods. Pac. J. Optim. (2012, to appear)

Download references

Author information

Authors and Affiliations

  1. Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, 10027, USA

    Donald Goldfarb

  2. Institute for Mathematics and Its Applications, University of Minnesota, 400 Lind Hall, 207 Church Street SE, Minneapolis, MN, 55455, USA

    Shiqian Ma

  3. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, 18015-1582, USA

    Katya Scheinberg

Authors
  1. Donald Goldfarb
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shiqian Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Katya Scheinberg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Donald Goldfarb.

Additional information

Donald Goldfarb is supported in part by NSF Grants DMS 06-06712 and DMS 10-16571, ONR Grant N00014-08-1-1118 and DOE Grant DE-FG02-08ER25856.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Goldfarb, D., Ma, S. & Scheinberg, K. Fast alternating linearization methods for minimizing the sum of two convex functions. Math. Program. 141, 349–382 (2013). https://doi.org/10.1007/s10107-012-0530-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-012-0530-2

Keywords

Mathematics Subject Classification

Search

Navigation