Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. (English) Zbl 1202.26026
From the authors abstract: The paper gives alternative characterizations of Łojasiewicz inequality for nonsmooth lower semicontinuous functions defined on a metric or a real Hilbert space. Thus in the metric space setting it was shown that a generalized form of Łojasiewicz inequality (called the Kurdyka-Łojasiewicz inequality) is related to metric regularity and Lipschitz continuity of the sublevel mapping, yielding applications to discrete methods (strong convergence of the proximal algorithm). In the Hilbert space setting, it was established that asymptotic properties of the semiflow generated by \(-\partial f\) are strongly linked to Kurdyka-Łojasiewicz inequality. Furthermore, characterizations in terms of talweg lines and integrability conditions are given. Results on asymptotic equivalence for discrete gradient methods and continuous gradient curves are established for the convex case. However, a counterexample of a convex \(C^ 2\) function in \(\mathbb R^ 2\) is constructed to show that convex functions may fail to fulfill the Kurdyka-Łojasiewicz inequality.
Reviewer: James Adedayo Oguntuase (Abeokuta)
MSC:
| 26D10 | Inequalities involving derivatives and differential and integral operators |
| 03C64 | Model theory of ordered structures; o-minimality |
| 49J52 | Nonsmooth analysis |
| 37N40 | Dynamical systems in optimization and economics |
Keywords:
Łojasiewicz inequality; gradient inequalities; metric regularity; subgradient curve; talweg; gradient method; convex functions; global convergence; proximal methodReferences:
| [1] | 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. · Zbl 1092.90036 · doi:10.1137/040605266 |
| [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. · Zbl 0923.49010 |
| [3] | 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. · Zbl 1090.35002 |
| [4] | D. Aussel, A. Daniilidis, and L. Thibault, Subsmooth sets: functional characterizations and related concepts, Trans. Amer. Math. Soc. 357 (2005), no. 4, 1275 – 1301. · Zbl 1094.49016 |
| [5] | 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. · Zbl 1165.90018 · doi:10.1007/s10107-007-0133-5 |
| [6] | 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. · Zbl 1085.49019 · doi:10.1051/cocv:2004013 |
| [7] | J.-B. Baillon, Un exemple concernant le comportement asymptotique de la solution du problème \?\?/\?\?+\partial \?(\?)∋0, J. Funct. Anal. 28 (1978), no. 3, 369 – 376 (French). · Zbl 0386.47041 · doi:10.1016/0022-1236(78)90093-9 |
| [8] | 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. · Zbl 1129.26012 · doi:10.1137/050644641 |
| [9] | 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. · Zbl 1142.49006 · doi:10.1137/060670080 |
| [10] | 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. · Zbl 0278.47033 |
| [11] | H. Brézis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973 (French). North-Holland Mathematics Studies, No. 5. Notas de Matemática (50). · Zbl 0252.47055 |
| [12] | Ronald E. Bruck Jr., Asymptotic convergence of nonlinear contraction semigroups in Hilbert space, J. Funct. Anal. 18 (1975), 15 – 26. · Zbl 0319.47041 · doi:10.1016/0022-1236(75)90027-0 |
| [13] | 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. · Zbl 1095.49003 |
| [14] | 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. · Zbl 1047.49500 |
| [15] | Patrick L. Combettes and Teemu Pennanen, Proximal methods for cohypomonotone operators, SIAM J. Control Optim. 43 (2004), no. 2, 731 – 742. · Zbl 1078.47003 · doi:10.1137/S0363012903427336 |
| [16] | 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. · Zbl 1190.90206 · doi:10.1007/s10107-007-0102-z |
| [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. 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. · Zbl 1106.14046 · doi:10.1112/S0024609306018911 |
| [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). · Zbl 1201.37023 |
| [21] | Marco Degiovanni, Antonio Marino, and Mario Tosques, Evolution equations with lack of convexity, Nonlinear Anal. 9 (1985), no. 12, 1401 – 1443. · Zbl 0545.46029 · doi:10.1016/0362-546X(85)90098-7 |
| [22] | 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. Natur. (8) 68 (1980), no. 3, 180 – 187 (Italian, with English summary). · Zbl 0465.47041 |
| [23] | 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. · Zbl 1042.49026 |
| [24] | A. L. Dontchev, M. Quincampoix, and N. Zlateva, Aubin criterion for metric regularity, J. Convex Anal. 13 (2006), no. 2, 281 – 297. · Zbl 1098.49018 |
| [25] | Lou van den Dries and Chris Miller, Geometric categories and o-minimal structures, Duke Math. J. 84 (1996), no. 2, 497 – 540. · Zbl 0889.03025 · doi:10.1215/S0012-7094-96-08416-1 |
| [26] | L. C. Evans and J. Spruck, Motion of level sets by mean curvature. III, J. Geom. Anal. 2 (1992), no. 2, 121 – 150. · Zbl 0768.53003 · doi:10.1007/BF02921385 |
| [27] | Fenchel, W., Convex Cones, Sets and Functions, Mimeographed lecture note, Princeton University, 1951. · Zbl 0053.12203 |
| [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] | M. Gage and R. S. Hamilton, The heat equation shrinking convex plane curves, J. Differential Geom. 23 (1986), no. 1, 69 – 96. · Zbl 0621.53001 |
| [30] | 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. · Zbl 0977.35091 |
| [31] | 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. · Zbl 1132.35002 |
| [32] | 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. · Zbl 0979.49017 · doi:10.1070/rm2000v055n03ABEH000292 |
| [33] | Alexander Ioffe, Towards metric theory of metric regularity, Approximation, optimization and mathematical economics (Pointe-à-Pitre, 1999) Physica, Heidelberg, 2001, pp. 165 – 176. · Zbl 0986.54039 |
| [34] | Alexander Ioffe, On regularity estimates for mappings between embedded manifolds, Control Cybernet. 36 (2007), no. 3, 659 – 668. · Zbl 1168.49036 |
| [35] | Mohamed Ali Jendoubi, A simple unified approach to some convergence theorems of L. Simon, J. Funct. Anal. 153 (1998), no. 1, 187 – 202. · Zbl 0895.35012 · doi:10.1006/jfan.1997.3174 |
| [36] | Yakar Kannai, Concavifiability and constructions of concave utility functions, J. Math. Econom. 4 (1977), no. 1, 1 – 56. · Zbl 0361.90008 · doi:10.1016/0304-4068(77)90015-5 |
| [37] | 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). · Zbl 0934.32009 |
| [38] | Krzysztof Kurdyka and Adam Parusiński, \?_{\?}-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). · Zbl 0799.32007 |
| [39] | Lageman, C., Convergence of gradient-like dynamical systems and optimization algorithms, Ph.D. Thesis, University of Würzburg, (2007), 205 pp. · Zbl 1130.37012 |
| [40] | John M. Lee, Introduction to smooth manifolds, Graduate Texts in Mathematics, vol. 218, Springer-Verlag, New York, 2003. |
| [41] | 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. · Zbl 0866.65043 |
| [42] | 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, Paris, 1963, pp. 87 – 89 (French). |
| [43] | Łojasiewicz, S., Ensembles semi-analytiques, preprint 112 pp. (IHES, 1965). Available at http://perso.univ-rennes1.fr/michel.coste/Lojasiewicz.pdf |
| [44] | Sylvie Marcellin and Lionel Thibault, Evolution problems associated with primal lower nice functions, J. Convex Anal. 13 (2006), no. 2, 385 – 421. · Zbl 1102.49012 |
| [45] | Boris Mordukhovich, Complete characterization of openness, metric regularity, and Lipschitzian properties of multifunctions, Trans. Amer. Math. Soc. 340 (1993), no. 1, 1 – 35. · Zbl 0791.49018 |
| [46] | 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. Boris S. Mordukhovich, Variational analysis and generalized differentiation. II, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 331, Springer-Verlag, Berlin, 2006. Applications. |
| [47] | 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. · Zbl 1142.90500 · doi:10.1007/s10107-006-0706-8 |
| [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. · Zbl 1090.90157 |
| [49] | Jean-Paul Penot, Metric regularity, openness and Lipschitzian behavior of multifunctions, Nonlinear Anal. 13 (1989), no. 6, 629 – 643. · Zbl 0687.54015 · doi:10.1016/0362-546X(89)90083-7 |
| [50] | Peypouquet, J., Analyse asymptotique de systèmes d’évolution et applications en optimisation, 116 pp. (Université Paris 6 & Universidad de Chile, 2007). |
| [51] | 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. · Zbl 0549.35071 · doi:10.2307/2006981 |
| [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] | 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. · Zbl 0888.49001 |
| [54] | 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. · Zbl 1197.53087 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
