• Characterizations of Lojasiewi...

Result: Characterizations of Lojasiewicz inequalities: Subgradient flows, talweg, convexity

Title:
Characterizations of Lojasiewicz inequalities: Subgradient flows, talweg, convexity
Authors:
Bolte, Jerome, Daniilidis, Aris, Ley, Olivier, Mazet, Laurent
Contributors:
Equipe combinatoire et optimisation (C&O), Institut de Mathématiques de Jussieu - Paris Rive Gauche (IMJ-PRG (UMR_7586)), Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre de Mathématiques Appliquées de l'Ecole polytechnique (CMAP), Institut National de Recherche en Informatique et en Automatique (Inria)-École polytechnique (X), Institut Polytechnique de Paris (IP Paris)-Institut Polytechnique de Paris (IP Paris)-Centre National de la Recherche Scientifique (CNRS), Departament de Matemàtiques [Barcelona] (UAB), Universitat Autònoma de Barcelona = Autonomous University of Barcelona = Universidad Autónoma de Barcelona (UAB), Laboratoire de Mathématiques et Physique Théorique (LMPT), Université de Tours (UT)-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche Mathématique de Rennes (IRMAR), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Laboratoire d'Analyse et de Mathématiques Appliquées (LAMA), Université Paris-Est Marne-la-Vallée (UPEM)-Fédération de Recherche Bézout (BEZOUT), Centre National de la Recherche Scientifique (CNRS)-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), ANR grant ANR-05-BLAN-0248-01 (France). MEC grant MTM2005-08572-C03-03 (Spain), ANR-05-BLAN-0248,Décisionprox,Optimisation, jeux et dynamique de la décision avec coût au changement: modélisation et algorithmes proximaux(2005)
Source:
Transactions of the American Mathematical Society. 362(6):3319-3363
Publisher Information:
CCSD; American Mathematical Society, 2010.
Publication Year:
2010
Collection:
collection:UNIV-PARIS7
collection:X
collection:UPMC
collection:UNIV-RENNES1
collection:UNIV-TOURS
collection:IRMAR
collection:UR2-HB
collection:CNRS
collection:UNIV-MLV
collection:INSA-RENNES
collection:INSMI
collection:X-CMAP
collection:X-DEP-MATHA
collection:IRMAR-INSA
collection:LAMA_UMR8050
collection:IMJ
collection:CV_UNIV-MLV
collection:CV_LAMA_UMR8050
collection:LAMA_PLC
collection:UPEC
collection:UNAM
collection:LMPT
collection:CV_UPEC
collection:CMAP
collection:IRMAR-AN
collection:TDS-MACS
collection:UR1-HAL
collection:UR1-MATH-STIC
collection:AGREENIUM
collection:UNIV-RENNES2
collection:UPMC_POLE_1
collection:IDP
collection:TEST-UNIV-RENNES
collection:TEST-UR-CSS
collection:UNIV-RENNES
collection:INSA-GROUPE
collection:SORBONNE-UNIVERSITE
collection:SU-SCIENCES
collection:UNIV-PARIS
collection:UP-SCIENCES
collection:SU-TI
collection:ANR
collection:UR1-MATH-NUM
collection:ALLIANCE-SU
collection:UNIV-EIFFEL
collection:UPEM-UNIVEIFFEL
collection:TEST3-HALCNRS
collection:INSTITUT-AGRO
collection:IRMAR-ANM
collection:IRMAR-ANUM
collection:TEST-UPEC-ODD
collection:DEPARTEMENT-DE-MATHEMATIQUES
collection:IP-PARIS-MATHEMATIQUES
Subject Terms:
Lojasiewicz inequality, proximal method., global convergence, convex functions, gradient method, subgradient curve, metric regularity, gradient inequalities, proximal method, 26D10 ; 03C64 ; 37N40 ; 49J52 ; 65K10., [MATH.MATH-OC]Mathematics [math], Optimization and Control [math.OC], [MATH.MATH-DS]Mathematics [math], Dynamical Systems [math.DS]
Original Identifier:
ARXIV: 0802.0826
HAL: hal-00243094
Document Type:
Journal article<br />Journal articles
Language:
English
ISSN:
0002-9947
1088-6850
Relation:
info:eu-repo/semantics/altIdentifier/arxiv/0802.0826; info:eu-repo/semantics/altIdentifier/doi/10.1090/S0002-9947-09-05048-X
DOI:
10.1090/S0002-9947-09-05048-X
Access URL:
https://hal.science/hal-00243094
https://hal.science/hal-00243094v1/document
https://hal.science/hal-00243094v1/file/bdlm08-soumis.pdf
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.hal.00243094v1
Database:
HAL

Further Information

The classical Lojasiewicz 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, tame geometry. This paper provides alternative characterizations of this type of inequalities for nonsmooth lower semicontinuous functions defined on a metric or a real Hilbert space. In a metric context, we show that a generalized form of the Lojasiewicz inequality (hereby called the Kurdyka-Lojasiewicz inequality) relates 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-Lojasiewicz 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 in particular to establish the asymptotic equivalence of discrete gradient methods and continuous gradient curves. On the other hand, a counterexample of a convex C^2 function in in the plane 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-Lojasiewicz inequality.