Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity

Authors: Jérôme Bolte, Aris Daniilidis, Olivier Ley and Laurent Mazet
Journal: Trans. Amer. Math. Soc. 362 (2010), 3319-3363
MSC (2010): Primary 26D10; Secondary 03C64, 37N40, 49J52, 65K10
Published electronically: December 22, 2009
MathSciNet review: 2592958
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The classical Łojasiewicz inequality and its extensions for partial differential equation problems (Simon) and to o-minimal structures (Kurdyka) have a considerable impact on the analysis of gradient-like methods and related problems: minimization methods, complexity theory, asymptotic analysis of dissipative partial differential equations, and tame geometry. This paper provides alternative characterizations of this type of inequality for nonsmooth lower semicontinuous functions defined on a metric or a real Hilbert space. In the framework of metric spaces, we show that a generalized form of the Łojasiewicz inequality (hereby called the Kurdyka-Łojasiewicz inequality) is related to metric regularity and to the Lipschitz continuity of the sublevel mapping, yielding applications to discrete methods (strong convergence of the proximal algorithm). In a Hilbert setting we further establish that asymptotic properties of the semiflow generated by $ -\partial f$ are strongly linked to this inequality. This is done by introducing the notion of a piecewise subgradient curve: such curves have uniformly bounded lengths if and only if the Kurdyka-Łojasiewicz inequality is satisfied. Further characterizations in terms of talweg lines --a concept linked to the location of the less steepest points at the level sets of $ f$-- and integrability conditions are given. In the convex case these results are significantly reinforced, allowing us in particular to establish a kind of asymptotic equivalence for discrete gradient methods and continuous gradient curves. On the other hand, a counterexample of a convex $ C^{2}$ function in $ \mathbb{R}^{2}$ is constructed to illustrate the fact that, contrary to our intuition, and unless a specific growth condition is satisfied, convex functions may fail to fulfill the Kurdyka-Łojasiewicz inequality.

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

  • 1. Absil, P.-A., Mahony, R. & Andrews, B., Convergence of the iterates of descent methods for analytic cost functions. SIAM J. Optim. 16 (2005), 531-547. MR 2197994 (2006j:90065)
  • 2. Albano, P. & Cannarsa, P., Singularities of semiconcave functions in Banach spaces, Stochastic analysis, control, optimization and applications, Systems Control Found. Appl., 171-190, Birkhäuser Boston, 1999.
  • 3. Ambrosio, L., Gigli, N. & Savaré, G. Gradient flows in metric spaces and in the space of probability measures, Lectures in Mathematics ETH Zurich. Birkhäuser Verlag, Basel, 2005. MR 2129498 (2006k:49001)
  • 4. Aussel, D., Daniilidis, A. & Thibault, L., Subsmooth sets: Functional characterizations and related concepts, Trans. Amer. Math. Soc. 357 (2005), 1275-1301. MR 2115366 (2007b:49033)
  • 5. Attouch, H. & Bolte, J. On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Programming 116 (2009), 5-16. MR 2421270
  • 6. Azé, D. & Corvellec, J.-N., Characterizations of error bounds for lower semicontinuous functions on metric spaces, ESAIM Control Optim. Calc. Var. 10 (2004), 409-425. MR 2084330 (2005e:49027)
  • 7. Baillon, J.-B., Un exemple concernant le comportement asymptotique de la solution du problème $ du/dt+\partial \varphi(u)\ni0$, J. Funct. Anal. 28 (1978), 369-376. MR 496964 (81a:47063)
  • 8. Bolte, J., Daniilidis, A. & Lewis, A.S., The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim. 17 (2006), 1205-1223. MR 2274510 (2007j:49020)
  • 9. Bolte, J., Daniilidis, A., Lewis, A. & Shiota, M., Clarke subgradients of stratifiable functions, SIAM J. Optimization 18 (2007), 556-572. MR 2338451 (2008m:49092)
  • 10. Brézis, H., Monotonicity methods in Hilbert spaces and some applications to nonlinear partial differential equations, Contributions to nonlinear functional analysis (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1971), Academic Press, New York, 1971, 101-156. MR 0394323 (52:15126)
  • 11. Brézis, H., Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert (French), North-Holland Mathematics Studies 5, North-Holland Publishing Co., 1973. MR 0348562 (50:1060)
  • 12. Bruck, Jr., R. E., Asymptotic convergence of nonlinear contraction semigroups in Hilbert space, J. Funct. Anal. 18 (1975), 15-26. MR 0377609 (51:13780)
  • 13. Cannarsa, P. & Sinestrari, C., Semiconcave functions, Hamilton-Jacobi equations, and optimal control, Progress in Nonlinear Differential Equations and their Applications, 58, Birkhäuser Boston Inc., 2004. MR 2041617 (2005e:49001)
  • 14. Clarke, F.H., Ledyaev, Yu., Stern, R.I. & Wolenski, P.R., Nonsmooth Analysis and Control Theory, Graduate Texts in Mathematics 178, Springer-Verlag, New-York, 1998. MR 1488695 (99a:49001)
  • 15. Combettes, P. & Pennanen, T., Proximal methods for cohypomonotone operators, SIAM J. Control Optim. 43 (2004), 731-742. MR 2086182 (2005f:49045)
  • 16. Corvellec, J.-N. & Motreanu, V., Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Programming 114 (2008), 291-319. MR 2393044 (2009b:49041)
  • 17. Coste, M., An Introduction to o-minimal Geometry, RAAG Notes, 81 pages, Institut de Recherche Mathématiques de Rennes, November 1999.
  • 18. D'Acunto, D., Sur les courbes intégrales du champ de gradient, 72 pp., Ph.D. Thesis (Université de Savoie, 2001).
  • 19. D'Acunto, D. & Kurdyka, K., Bounds for gradient trajectories and geodesic diameter of real algebraic sets, Bull. London Math. Soc. 38 (2006), 951-965. MR 2285249 (2007k:14118)
  • 20. Daniilidis, A., Ley, O. & Sabourau, S., Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions, preprint 19 pp., (UAB 31/2008).
  • 21. Degiovanni, M., Marino, A. & Tosques, M., Evolution equations with lack of convexity, Nonlinear Analysis 9 (1985), 1401-1443. MR 820649 (87h:35147)
  • 22. De Giorgi, E., Marino, A. & Tosques, M., Problems of evolution in metric spaces and maximal decreasing curve, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur. 68 (1980), 180-187. MR 636814 (83m:49052)
  • 23. Dontchev, A.L., Lewis, A.S. & Rockafellar, R.T., The radius of metric regularity, Trans. Amer. Math. Soc. 335 (2002), 493-517. MR 1932710 (2003i:49026)
  • 24. Dontchev, A. L., Quincampoix, M. & Zlateva, N., Aubin criterion for metric regularity, J. Convex Anal. 13 (2006), 281-297. MR 2252233 (2007d:49026)
  • 25. van den Dries, L. & Miller, C., Geometric categories and o-minimal structures, Duke Math. J. 84 (1996), 497-540. MR 1404337 (97i:32008)
  • 26. Evans, L. C. & Spruck, J., Motion of level sets by mean curvature. III, J. Geom. Anal. 2 (1992) 121-150. MR 1151756 (93d:58044)
  • 27. Fenchel, W., Convex Cones, Sets and Functions, Mimeographed lecture note, Princeton University, 1951.
  • 28. Forti, M., Nistri, P. & Quincampoix, M., Convergence of Neural Networks for Programming Problems via a Nonsmooth Łojasiewicz Inequality, IEEE Trans. on Neural Networks, 17 (2006), 1471-1486.
  • 29. Gage, M. & Hamilton, R. S., The heat equation shrinking convex plane curves, J. Differential Geom. 23 (1986) 69-96. MR 840401 (87m:53003)
  • 30. Haraux, A., A hyperbolic variant of Simon's convergence theorem. Evolution equations and their applications in physical and life sciences (Bad Herrenalb, 1998), Lecture Notes in Pure and Appl. Math. 215 (2001), 255-264, Marcel Dekker, New York. MR 1818007 (2002a:35147)
  • 31. Huang, S.-Z. Gradient inequalities. With applications to asymptotic behavior and stability of gradient-like systems, Mathematical Surveys and Monographs, 126, American Mathematical Society, Providence, RI, 2006. MR 2226672 (2007b:35035)
  • 32. Ioffe, A. Metric regularity and Subdifferential Calculus, Russian Math. Surveys 55 (2000), 501-558 MR 1777352 (2001j:90002)
  • 33. Ioffe, A., ``Towards metric theory of metric regularity'', in: Approximation, optimization and mathematical economics, (Pointe-à-Pitre, 1999), 165-176, Physica, Heidelberg, 2001. MR 1842886 (2002f:49034)
  • 34. Ioffe, A., On regularity estimates for mappings between embedded manifolds, Control Cybernet. 36 (2007), 659-668. MR 2376046 (2009c:49042)
  • 35. Jendoubi, M., A simple unified approach to some convergence theorems of L. Simon, J. Funct. Anal. 153 (1998), 187-202. MR 1609269 (99c:35101)
  • 36. Kannai, Y., Concavifiability and constructions of concave utility functions, J. Math. Econom. 4 (1977), 1-56. MR 0459523 (56:17715)
  • 37. Kurdyka, K., On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier 48 (1998), 769-783. MR 1644089 (2000b:03139)
  • 38. Kurdyka, K. & Parusinski, A., $ w\sb f$-stratification of subanalytic functions and the Lojasiewicz inequality, C. R. Acad. Sci. Paris Sér. I Math. 318 (1994), 129-133. MR 1260324 (95d:32012)
  • 39. Lageman, C., Convergence of gradient-like dynamical systems and optimization algorithms, Ph.D. Thesis, University of Würzburg, (2007), 205 pp.
  • 40. Lee, J. M., Introduction to smooth manifolds, Graduate Texts in Mathematics, 218. Springer-Verlag, New York, 2003. xviii+628 pp. MR 1930091 (2003k:58001)
  • 41. Lemaire, B., An Asymptotical Variational Principle Associated with the Steepest Descent Method for a Convex Function, J. Convex Anal. 3 (1996), 63-70. MR 1422752 (97m:90096)
  • 42. Łojasiewicz, S., ``Une propriété topologique des sous-ensembles analytiques réels.'', in: Les Équations aux Dérivées Partielles, pp. 87-89, Éditions du centre National de la Recherche Scientifique, Paris 1963. MR 0160856 (28:4066)
  • 43. Łojasiewicz, S., Ensembles semi-analytiques, preprint 112 pp. (IHES, 1965). Available at
  • 44. Marcellin, S. & Thibault, L., Evolution problems associated with primal lower nice functions, J. Convex Anal. 13 (2006), 385-421. MR 2252239 (2007e:49029)
  • 45. Mordukhovich, B., Complete characterization of openness, metric regularity and Lipschitzian properties of multifunctions. Trans. Amer. Math. Soc. 340 (1993), 1-35. MR 1156300 (94a:49011)
  • 46. Mordukhovich, B., Variational analysis and generalized differentiation. I. Basic theory, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 330. Springer-Verlag, Berlin, 2006. xxii+579 pp. MR 2191744 (2007b:49003a)
  • 47. Nesterov, Y. & Polyak, B. T., Cubic regularization of Newton method and its global performance. Math. Program. 108 (2006), no. 1, Ser. A, 177-205. MR 2229459 (2007f:90153)
  • 48. Nistri, P. & Quincampoix, M. On the properties of solutions to a differential inclusion associated with a nonsmooth constrained optimization problem, Proceedings of the 44th IEEE Conference on Decision and Control and the European Control Conference 2005, Seville, Spain, December 12-15, 2005.
  • 49. Penot, J.-P., Metric regularity, openness and Lipschitzian behaviour of multifunctions. Nonlinear Analysis, 13 (1989), 629-643. MR 998509 (90h:54024)
  • 50. Peypouquet, J., Analyse asymptotique de systèmes d'évolution et applications en optimisation, 116 pp. (Université Paris 6 & Universidad de Chile, 2007).
  • 51. Simon, L., Asymptotics for a class of non-linear evolution equations, with applications to geometric problems, Ann. Math. 118 (1983), 525-571. MR 727703 (85b:58121)
  • 52. Torralba, D., Convergence épigraphique et changements d'échelle en analyse variationnelle et optimisation, 160 pp., Ph.D. Thesis (Université de Montpellier 2, 1996).
  • 53. Rockafellar, R.T. & Wets, R., Variational Analysis, Grundlehren der Mathematischen Wissenschaften, Vol. 317, Springer, 1998. MR 1491362 (98m:49001)
  • 54. Zhu, X. Lectures on mean curvature flows, AMS/IP Studies in Advanced Mathematics 32, American Mathematical Society, 2002. MR 1931534 (2004f:53084)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 26D10, 03C64, 37N40, 49J52, 65K10

Retrieve articles in all journals with MSC (2010): 26D10, 03C64, 37N40, 49J52, 65K10

Additional Information

Jérôme Bolte
Affiliation: UPMC Université Paris 06 - Équipe Combinatoire et Optimisation (UMR 7090), Case 189, Université Pierre et Marie Curie, 4 Place Jussieu, F–75252 Paris Cedex 05, France

Aris Daniilidis
Affiliation: Departament de Matemàtiques, C1/308, Universitat Autònoma de Barcelona, E–08193 Bellaterra (Cerdanyola del Vallès), Spain

Olivier Ley
Affiliation: Laboratoire de Mathématiques et Physique Théorique (CNRS UMR 6083), Fédération Denis Poisson, Faculté des Sciences et Techniques, Université François Rabelais, Parc de Grandmont, F–37200 Tours, France
Address at time of publication: IRMAR (CNRS UMR 6625) INSA de Rennes, 20 avenue des buttes de Coesmes, F-35708 Rennes Cedex 7, France

Laurent Mazet
Affiliation: Université Paris-Est, Laboratoire d’Analyse et Mathématiques Appliquées, UMR 8050, UFR des Sciences et Technologie, Département de Mathématiques, 61 avenue du Général de Gaulle 94010 Créteil cedex, France

Keywords: \L ojasiewicz inequality, gradient inequalities, metric regularity, subgradient curve, talweg, gradient method, convex functions, global convergence, proximal method.
Received by editor(s): February 7, 2008
Received by editor(s) in revised form: March 11, 2009
Published electronically: December 22, 2009
Article copyright: © Copyright 2009 American Mathematical Society

American Mathematical Society