Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
HTML articles powered by AMS MathViewer
- by Jérôme Bolte, Aris Daniilidis, Olivier Ley and Laurent Mazet PDF
- Trans. Amer. Math. Soc. 362 (2010), 3319-3363 Request permission
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
- P.-A. Absil, R. Mahony, and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim. 16 (2005), no. 2, 531–547. MR 2197994, DOI 10.1137/040605266
- 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.
- Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré, Gradient flows in metric spaces and in the space of probability measures, Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2005. MR 2129498
- D. Aussel, A. Daniilidis, and L. Thibault, Subsmooth sets: functional characterizations and related concepts, Trans. Amer. Math. Soc. 357 (2005), no. 4, 1275–1301. MR 2115366, DOI 10.1090/S0002-9947-04-03718-3
- Hedy Attouch and Jérôme Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program. 116 (2009), no. 1-2, Ser. B, 5–16. MR 2421270, DOI 10.1007/s10107-007-0133-5
- Dominique Azé and Jean-Noël Corvellec, Characterizations of error bounds for lower semicontinuous functions on metric spaces, ESAIM Control Optim. Calc. Var. 10 (2004), no. 3, 409–425. MR 2084330, DOI 10.1051/cocv:2004013
- J.-B. Baillon, Un exemple concernant le comportement asymptotique de la solution du problème $du/dt+\partial \varphi (u)\ni 0$, J. Functional Analysis 28 (1978), no. 3, 369–376 (French). MR 496964, DOI 10.1016/0022-1236(78)90093-9
- Jérôme Bolte, Aris Daniilidis, and Adrian Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim. 17 (2006), no. 4, 1205–1223. MR 2274510, DOI 10.1137/050644641
- Jérôme Bolte, Aris Daniilidis, Adrian Lewis, and Masahiro Shiota, Clarke subgradients of stratifiable functions, SIAM J. Optim. 18 (2007), no. 2, 556–572. MR 2338451, DOI 10.1137/060670080
- Haïm Brézis, 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, pp. 101–156. MR 0394323
- H. Brézis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert, North-Holland Mathematics Studies, No. 5, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973 (French). MR 0348562
- Ronald E. Bruck Jr., Asymptotic convergence of nonlinear contraction semigroups in Hilbert space, J. Functional Analysis 18 (1975), 15–26. MR 377609, DOI 10.1016/0022-1236(75)90027-0
- Piermarco Cannarsa and Carlo Sinestrari, Semiconcave functions, Hamilton-Jacobi equations, and optimal control, Progress in Nonlinear Differential Equations and their Applications, vol. 58, Birkhäuser Boston, Inc., Boston, MA, 2004. MR 2041617
- F. H. Clarke, Yu. S. Ledyaev, R. J. Stern, and P. R. Wolenski, Nonsmooth analysis and control theory, Graduate Texts in Mathematics, vol. 178, Springer-Verlag, New York, 1998. MR 1488695
- Patrick L. Combettes and Teemu Pennanen, Proximal methods for cohypomonotone operators, SIAM J. Control Optim. 43 (2004), no. 2, 731–742. MR 2086182, DOI 10.1137/S0363012903427336
- Jean-Noël Corvellec and Viorica V. Motreanu, Nonlinear error bounds for lower semicontinuous functions on metric spaces, Math. Program. 114 (2008), no. 2, Ser. A, 291–319. MR 2393044, DOI 10.1007/s10107-007-0102-z
- Coste, M., An Introduction to o-minimal Geometry, RAAG Notes, 81 pages, Institut de Recherche Mathématiques de Rennes, November 1999.
- D’Acunto, D., Sur les courbes intégrales du champ de gradient, 72 pp., Ph.D. Thesis (Université de Savoie, 2001).
- D. D’Acunto and K. Kurdyka, Bounds for gradient trajectories and geodesic diameter of real algebraic sets, Bull. London Math. Soc. 38 (2006), no. 6, 951–965. MR 2285249, DOI 10.1112/S0024609306018911
- 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).
- Marco Degiovanni, Antonio Marino, and Mario Tosques, Evolution equations with lack of convexity, Nonlinear Anal. 9 (1985), no. 12, 1401–1443. MR 820649, DOI 10.1016/0362-546X(85)90098-7
- Ennio De Giorgi, Antonio Marino, and Mario Tosques, Problems of evolution in metric spaces and maximal decreasing curve, Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8) 68 (1980), no. 3, 180–187 (Italian, with English summary). MR 636814
- A. L. Dontchev, A. S. Lewis, and R. T. Rockafellar, The radius of metric regularity, Trans. Amer. Math. Soc. 355 (2003), no. 2, 493–517. MR 1932710, DOI 10.1090/S0002-9947-02-03088-X
- A. L. Dontchev, M. Quincampoix, and N. Zlateva, Aubin criterion for metric regularity, J. Convex Anal. 13 (2006), no. 2, 281–297. MR 2252233
- Lou van den Dries and Chris Miller, Geometric categories and o-minimal structures, Duke Math. J. 84 (1996), no. 2, 497–540. MR 1404337, DOI 10.1215/S0012-7094-96-08416-1
- L. C. Evans and J. Spruck, Motion of level sets by mean curvature. III, J. Geom. Anal. 2 (1992), no. 2, 121–150. MR 1151756, DOI 10.1007/BF02921385
- Fenchel, W., Convex Cones, Sets and Functions, Mimeographed lecture note, Princeton University, 1951.
- 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.
- M. Gage and R. S. Hamilton, The heat equation shrinking convex plane curves, J. Differential Geom. 23 (1986), no. 1, 69–96. MR 840401
- Alain Haraux, 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., vol. 215, Dekker, New York, 2001, pp. 255–264. MR 1818007
- Sen-Zhong Huang, Gradient inequalities, Mathematical Surveys and Monographs, vol. 126, American Mathematical Society, Providence, RI, 2006. With applications to asymptotic behavior and stability of gradient-like systems. MR 2226672, DOI 10.1090/surv/126
- A. D. Ioffe, Metric regularity and subdifferential calculus, Uspekhi Mat. Nauk 55 (2000), no. 3(333), 103–162 (Russian, with Russian summary); English transl., Russian Math. Surveys 55 (2000), no. 3, 501–558. MR 1777352, DOI 10.1070/rm2000v055n03ABEH000292
- Alexander Ioffe, Towards metric theory of metric regularity, Approximation, optimization and mathematical economics (Pointe-à-Pitre, 1999) Physica, Heidelberg, 2001, pp. 165–176. MR 1842886
- Alexander Ioffe, On regularity estimates for mappings between embedded manifolds, Control Cybernet. 36 (2007), no. 3, 659–668. MR 2376046
- Mohamed Ali Jendoubi, A simple unified approach to some convergence theorems of L. Simon, J. Funct. Anal. 153 (1998), no. 1, 187–202. MR 1609269, DOI 10.1006/jfan.1997.3174
- Yakar Kannai, Concavifiability and constructions of concave utility functions, J. Math. Econom. 4 (1977), no. 1, 1–56. MR 459523, DOI 10.1016/0304-4068(77)90015-5
- Krzysztof Kurdyka, On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier (Grenoble) 48 (1998), no. 3, 769–783 (English, with English and French summaries). MR 1644089
- Krzysztof Kurdyka and Adam Parusiński, $\textbf {w}_f$-stratification of subanalytic functions and the Łojasiewicz inequality, C. R. Acad. Sci. Paris Sér. I Math. 318 (1994), no. 2, 129–133 (English, with English and French summaries). MR 1260324
- Lageman, C., Convergence of gradient-like dynamical systems and optimization algorithms, Ph.D. Thesis, University of Würzburg, (2007), 205 pp.
- John M. Lee, Introduction to smooth manifolds, Graduate Texts in Mathematics, vol. 218, Springer-Verlag, New York, 2003. MR 1930091, DOI 10.1007/978-0-387-21752-9
- B. Lemaire, An asymptotical variational principle associated with the steepest descent method for a convex function, J. Convex Anal. 3 (1996), no. 1, 63–70. MR 1422752
- S. Łojasiewicz, Une propriété topologique des sous-ensembles analytiques réels, Les Équations aux Dérivées Partielles (Paris, 1962) Éditions du Centre National de la Recherche Scientifique (CNRS), Paris, 1963, pp. 87–89 (French). MR 0160856
- Łojasiewicz, S., Ensembles semi-analytiques, preprint 112 pp. (IHES, 1965). Available at http://perso.univ-rennes1.fr/michel.coste/Lojasiewicz.pdf
- Sylvie Marcellin and Lionel Thibault, Evolution problems associated with primal lower nice functions, J. Convex Anal. 13 (2006), no. 2, 385–421. MR 2252239
- Boris Mordukhovich, Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctions, Trans. Amer. Math. Soc. 340 (1993), no. 1, 1–35. MR 1156300, DOI 10.1090/S0002-9947-1993-1156300-4
- Boris S. Mordukhovich, Variational analysis and generalized differentiation. I, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 330, Springer-Verlag, Berlin, 2006. Basic theory. MR 2191744
- Yurii Nesterov and B. T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program. 108 (2006), no. 1, Ser. A, 177–205. MR 2229459, DOI 10.1007/s10107-006-0706-8
- 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.
- Jean-Paul Penot, Metric regularity, openness and Lipschitzian behavior of multifunctions, Nonlinear Anal. 13 (1989), no. 6, 629–643. MR 998509, DOI 10.1016/0362-546X(89)90083-7
- Peypouquet, J., Analyse asymptotique de systèmes d’évolution et applications en optimisation, 116 pp. (Université Paris 6 & Universidad de Chile, 2007).
- Leon Simon, Asymptotics for a class of nonlinear evolution equations, with applications to geometric problems, Ann. of Math. (2) 118 (1983), no. 3, 525–571. MR 727703, DOI 10.2307/2006981
- Torralba, D., Convergence épigraphique et changements d’échelle en analyse variationnelle et optimisation, 160 pp., Ph.D. Thesis (Université de Montpellier 2, 1996).
- R. Tyrrell Rockafellar and Roger J.-B. Wets, Variational analysis, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317, Springer-Verlag, Berlin, 1998. MR 1491362, DOI 10.1007/978-3-642-02431-3
- Xi-Ping Zhu, Lectures on mean curvature flows, AMS/IP Studies in Advanced Mathematics, vol. 32, American Mathematical Society, Providence, RI; International Press, Somerville, MA, 2002. MR 1931534, DOI 10.1090/amsip/032
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
- Email: bolte@math.jussieu.fr
- Aris Daniilidis
- Affiliation: Departament de Matemàtiques, C1/308, Universitat Autònoma de Barcelona, E–08193 Bellaterra (Cerdanyola del Vallès), Spain
- MR Author ID: 613204
- Email: arisd@mat.uab.es
- 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
- MR Author ID: 677802
- Email: ley@lmpt.univ-tours.fr, olivier.ley@univ-rennes1.fr
- 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
- MR Author ID: 722767
- Email: laurent.mazet@univ-paris12.fr
- Received by editor(s): February 7, 2008
- Received by editor(s) in revised form: March 11, 2009
- Published electronically: December 22, 2009
- © Copyright 2009 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 362 (2010), 3319-3363
- MSC (2010): Primary 26D10; Secondary 03C64, 37N40, 49J52, 65K10
- DOI: https://doi.org/10.1090/S0002-9947-09-05048-X
- MathSciNet review: 2592958