Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods | Mathematical Programming Skip to main content
Springer Nature Link
Log in

Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods

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

Abstract

In view of the minimization of a nonsmooth nonconvex function f, we prove an abstract convergence result for descent methods satisfying a sufficient-decrease assumption, and allowing a relative error tolerance. Our result guarantees the convergence of bounded sequences, under the assumption that the function f satisfies the Kurdyka–Łojasiewicz inequality. This assumption allows to cover a wide range of problems, including nonsmooth semi-algebraic (or more generally tame) minimization. The specialization of our result to different kinds of structured problems provides several new convergence results for inexact versions of the gradient method, the proximal method, the forward–backward splitting algorithm, the gradient projection and some proximal regularization of the Gauss–Seidel method in a nonconvex setting. Our results are illustrated through feasibility problems, or iterative thresholding procedures for compressive sensing.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Absil P.-A., Mahony R., Andrews B.: Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16(2), 531–547 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aragon A., Dontchev A., Geoffroy M.: Convergence of the proximal point method for metrically regular mappings. ESAIM Proc., EDP Sci., Les Ulis 17, 1–8 (2007)

    MATH  Google Scholar 

  3. Attouch H., Bolte J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. Ser. B 116, 5–16 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Attouch H., Bolte J., Redont P., Soubeyran A.: Alternating proximal algorithms for weakly coupled convex minimization problems. Applications to dynamical games and PDE’s. J. Convex Anal. 15, 485–506 (2008)

    MathSciNet  MATH  Google Scholar 

  5. Attouch H., Bolte J., Redont P., Soubeyran A.: Proximal alternating minimization and projection methods for nonconvex problems. An approach based on the Kurdyka–Lojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  6. Attouch H., Briceño-Arias L.M., Combettes P.L.: A parallel splitting method for coupled monotone inclusions. SIAM J. Control Optim. 48(5), 3246–3270 (2010)

    Article  MATH  Google Scholar 

  7. Attouch, H., Soubeyran, A.: Local search proximal algorithms as decision dynamics with costs to move, Set Valued and Variational Analysis, Online First, 12 May 2010

  8. Auslender A.: Asymptotic properties of the Fenchel dual functional and applications to decomposition problems. J. Optim. Theory Appl. 73, 427–449 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  9. Beck, A., Teboulle, M.: A Linearly Convergent Algorithm for Solving a Class of Nonconvex/Affine Feasibility Problems, July 2010, to appear in the book Fixed-Point Algorithms for Inverse Problems in Science and Engineering, part of the Springer Verlag series Optimization and Its Applications. Available online http://ie.technion.ac.il/Home/Users/becka.html

  10. Benedetti R., Risler J.-J.: Real Algebraic and Semialgebraic Sets. Hermann, Éditeur des Sciences et des Arts, Paris (1990)

  11. Blumensath T., Davis M.E.: Iterative Thresholding for Sparse Approximations. J. Fourier Anal. Appl. 14, 629–654 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  12. Blumensath T., Blumensath T.: Iterative hard thresholding for compressed sensing. Appl. Comput. Harmon. Anal. 27, 265–274 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  13. Bochnak J., Coste M., Roy M.-F.: Real Algebraic Geometry, Ergebnisse der Mat., vol. 36. Springer, Berlin (1998)

    Google Scholar 

  14. Bolte, J., Combettes, P.L., Pesquet, J.-C.: Alternating proximal algorithm for blind image recovery. In: Proceedings of the IEEE International Conference on Image Processing. Hong-Kong, Sept 26–29 2010

  15. Bolte J., Daniilidis , Lewis A.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205–1223 (2006)

    Article  MathSciNet  Google Scholar 

  16. Bolte J., Daniilidis A., Lewis A.: A nonsmooth Morse-Sard theorem for subanalytic functions. J. Math. Anal. Appl. 321(2), 729–740 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  17. Bolte J., Daniilidis A., Lewis A., Shiota M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556–572 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Bolte J., Daniilidis A., Ley O., Mazet L.: Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Am. Math. Soc. 362, 3319–3363 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  19. Bredies, K., Lorenz, D.A.: Minimization of non-smooth, non-convex functionals by iterative thresholding, preprint available at http://www.uni-graz.at/~bredies/publications.html (2009)

  20. Burke J.V.: Descent methods for composite nondifferentiable optimization problems. Math. Program. 33, 260–279 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  21. Chartrand R.: Exact Reconstruction of Sparse Signals via Nonconvex Minimization. Signal Process. Lett. IEEE 14, 707–710 (2007)

    Article  Google Scholar 

  22. Chill R., Jendoubi M.A.: Convergence to steady states in asymptotically autonomous semilinear evolution equations. Nonlinear Anal. 53, 1017–1039 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  23. Clarke F.H., Ledyaev Y., Stern R.I., Wolenski P.R.: Nonsmooth Analysis and Control Theory, Graduate Texts in Mathematics, vol. 178. Springer, New York (1998)

    Google Scholar 

  24. Combettes P.L.: Quasi-Fejerian analysis of some optimization algorithms. In: Butnariu, D., Censor, Y., Reich, S. (eds) Inherently Parallel Algorithms in Feasibility and Optimization and Their Applications, pp. 115–152. Elsevier, New York (2001)

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  26. Coste, M.: An introduction to o-minimal geometry, RAAG Notes, Institut de Recherche Mathématiques de Rennes, 81 pp., Nov 1999

  27. Curry H.B.: The method of steepest descent for non-linear minimization problems. Q. Appl. Math. 2, 258–261 (1944)

    MathSciNet  MATH  Google Scholar 

  28. Palis, J., De Melo, W.: Geometric theory of dynamical systems. An introduction. (Translated from the Portuguese by A. K. Manning). Springer, New York, Berlin (1982)

  29. Donoho D.L.: Compressed Sensing. IEEE Trans. Inform. Theory 4, 1289–1306 (2006)

    Article  MathSciNet  Google Scholar 

  30. van den Dries, L.: Tame Topology and o-minimal Structures. London Mathematical Society Lecture Note Series, vol. 248. Cambridge University Press, Cambridge, x+180 pp. (1998)

  31. van den Dries L., Miller C.: Geometric categories and o-minimal structures. Duke Math. J. 84, 497–540 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  32. Grippo L., Sciandrone M.: Globally convergent block-coordinate techniques for unconstrained optimization. Optim. Methods Softw. 10(4), 587–637 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  33. Hare W., Sagastizábal C.: Computing proximal points of nonconvex functions. Math. Program. Ser. B 116(1–2), 221–258 (2009)

    Article  MATH  Google Scholar 

  34. Haraux A., Jendoubi M.A.: Convergence of solutions of second-order gradient-like systems with analytic nonlinearities. J. Differ. Equ. 144(2), 313–320 (1999)

    Article  MathSciNet  Google Scholar 

  35. Huang S.-Z., Takač P.: Convergence in gradient-like systems which are asymptotically autonomous and analytic. Nonlinear Anal., Ser. A Theory Methods 46, 675–698 (2001)

    Article  MATH  Google Scholar 

  36. Iusem A.N., Pennanen T., Svaiter B.F.: Inexact variants of the proximal point algorithm without monotonicity. SIAM J. Optim. 13(4), 1097–1894 (2003)

    Article  MathSciNet  Google Scholar 

  37. Kruger A.Y.: About regularity of collections of sets. Set Valued Anal. 14, 187–206 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  38. Kurdyka K.: On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier 48, 769–783 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  39. Lageman C.: Pointwise convergence of gradient-like systems. Math. Nachr. 280(13–14), 1543–1558 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  40. Lewis A.S.: Active sets, nonsmoothness and sensitivity. SIAM J. Optim. 13, 702–725 (2003)

    Article  Google Scholar 

  41. Lewis A.S., Malick J.: Alternating projection on manifolds. Math. Oper. Res. 33(1), 216–234 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  42. Lewis A.S., Luke D.R., Malick J.: Local linear convergence for alternating and averaged nonconvex projections. Found. Comput. Math. 9, 485–513 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  43. Lewis, A.S., Wright, S.J.: A proximal method for composite minimization, Optimization online 2008

  44. Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels. In: Les Équations aux Dérivées Partielles, Éditions du centre National de la Recherche Scientifique, Paris, pp. 87–89 (1963)

  45. Łojasiewicz S.: Sur la géométrie semi- et sous-analytique. Ann. Inst. Fourier 43, 1575–1595 (1993)

    Article  MATH  Google Scholar 

  46. Mordukhovich B.: Variational Analysis and Generalized Differentiation. I. Basic Theory, Grundlehren der Mathematischen Wissenschaften, vol. 330. Springer, Berlin (2006)

    Google Scholar 

  47. Nesterov Y.: Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program. Ser. B 112(1), 159–181 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  48. Nesterov, Y., Nemirovskii, A.: Interior-point polynomial algorithms in convex programming. SIAM Studies in Applied Mathematics, vol. 13, Philadelphia, PA (1994)

  49. Ortega J.M., Rheinboldt W.C.: Iterative Solutions of Nonlinear Equations in Several Variables. Academic Press, New York (1970)

    Google Scholar 

  50. Pennanen T.: Local convergence of the proximal point algorithm and multiplier methods without monotonicity. Math. Oper. Res. 27, 170–191 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  51. Poliquin R.A., Rockafellar R.T., Thibault L.: Local differentiability of distance functions. Trans. AMS 352, 5231–5249 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  52. Rockafellar R.T., Wets R.J.-B.: Variational Analysis, Grundlehren der Mathematischen Wissenschaften, vol. 317. Springer, Berlin (1998)

    Google Scholar 

  53. Simon L.: Asymptotics for a class of non-linear evolution equations, with applications to geometric problems. Ann. Math. 118, 525–571 (1983)

    Article  MATH  Google Scholar 

  54. Solodov M.V., Svaiter B.F.: A hybrid projection-proximal point algorithm. J. Convex Anal. 6(1), 59–70 (1999)

    MathSciNet  MATH  Google Scholar 

  55. Solodov M.V., Svaiter B.F.: A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set Valued Anal. 7, 323–345 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  56. Solodov M.V., Svaiter B.F.: A unified framework for some inexact proximal point algorithms. Numer. Funct. Anal. Optim. 22, 1013–1035 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  57. Wright S.J.: Identifiable surfaces in constrained optimization. SIAM J. Control Optim. 31, 1063–1079 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  58. Wright, S.J.: Accelerated block-coordinate relaxation for regularized optimization, Optimization online 2010

Download references

Author information

Authors and Affiliations

  1. I3M UMR CNRS 5149, Université Montpellier II, Place Eugène Bataillon, 34095, Montpellier, France

    Hedy Attouch

  2. TSE (GREMAQ, Université Toulouse I), Manufacture des Tabacs, 21 allée de Brienne, Toulouse, France

    Jérôme Bolte

  3. IMPA, Estrada Dona Castorina 110, Rio de Janeiro, 22460-320, Brazil

    Benar Fux Svaiter

Authors
  1. Hedy Attouch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jérôme Bolte
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Benar Fux Svaiter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hedy Attouch.

Additional information

Hedy Attouch: Partially supported by ANR-08-BLAN-0294-03. Jérôme Bolte: Partially supported by ANR-08-BLAN-0294-03. Benar Fux Svaiter: Partially supported by CNPq grants 474944/2010-7, 303583/2008-8, FAPERJ grant E-26/102.821/2008 and PRONEX-Optimization.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Attouch, H., Bolte, J. & Svaiter, B.F. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods. Math. Program. 137, 91–129 (2013). https://doi.org/10.1007/s10107-011-0484-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-011-0484-9

Keywords

Mathematics Subject Classification (2010)

Search

Navigation