Aris Daniliidis
Universidad de Chile / Ecole Polytechnique
Objectifs de l'UE :
Nonsmoothness prevails optimization in most of its theoretical and practical aspects. Even if the starting point is a smooth (or even a polynomial) model, natural operations like marginal/value functions, min/max selections etc destroy smoothness. In addition, extrema of nonsmooth functions occur, in general, at points of nondifferentiability. This has inevitably led to the development of the modern variational analysis and of nonsmooth optimization algorithms. Since the seminal example of Weierstrauss, back to 1872, exhibiting a univariate continuous real-valued function which is nowhere differentiable, it has been commonly understood that pathologies are tightly linked with almost all theories in classical analysis. Variational Analysis, handling nonsmooth objects cannot be an exception. Notwithstanding, in most applications nonsmoothness arises together with an intrinsic structure: for instance, an initial polynomial model will give rise to a semialgebraic structure. Therefiore, although a general nonsmooth theory will be full of pathological situations, it is founded to consider the trace of this theory within well-behaved paradigms. This course aims at underlining the use of these paradigms in optimization, focusing in minimization algorithms or general descent systems. After an introductory crash course in Nonsmooth Analysis, we shall consider Nonsmooth Optimization problems enjoying a nice intrinsic structure: The Tame paradigm —which is what is nowadays called Tame Optimization encompassing the semialgebraic structures— and the (classical) Convex paradigm. Convergence analysis of the proximal algorithm —a central tool in nonsmooth minimization— will be presented in the light of these two paradigms, emphasizing important convergence properties. So far, some of these properties seem to be eluded even in the convex case. Relations between continuous vs discrete dynamical descent systems will be presented. A secondary aim of this course is to provide essential background and material for further research. During the lectures, some open problems will be eventually mentioned.
Thèmes abordés :
- A quick survey of Nonsmooth Analysis
- From smooth manifolds to tangent and normal cones
- Subdifferentials and co-derivatives
- Lipschitz functions, Clarke subdifferential
- A nonsmooth Morse-Sard theorem and applications
- Tame variational analysis
- Semialgebraic functions, o-minimal structures
- Stratification vs Clarke subdiferential
- Sard theorem for tame multivalued maps
- Lojasiewicz inequality and generalizations
- Asymptotic analysis of descent systems
- Proximal algorithm – steepest descent
- Asymptotic analysis: convergence, length, Palis & De Melo example
- Kurdyka’s desigularization: characterization and applications
- Tame Sweeping process – desingularizing co-derivatives.
- The convex paradigm
- A convex counterexample to Kurdyka’s desigularization
- Asymptotic equivalence between continuous and discrete systems
- Self-contracted curves, Mancelli-Pucci mean width technique
- Snake-like curves: convergence and rectifiability.
Assessment. Active participation in discussions, oral presentations, oral exam.
Références :
- Bolte, J., Daniilidis, A., Ley, O. Mazet, L.,
Characterizations of Lojasiewicz inequalities: subgradient flows, talweg, convexity.
Trans. Amer. Math. Soc. 362 (2010), 3319–3363. - Ioffe, A. D., Critical values of set-valued maps with stratifiable graphs.
Extensions of Sard and Smale-Sard theorems, Proc. Amer. Math. Soc. 136 (2008), 3111–3119. - Ioffe, A. D., An invitation to tame optimization.
SIAM J. Optim. 19 (2008), 1894–1917. - Bolte, J., Daniilidis, A., Lewis, A., The Lojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17 (2006), 1205–1223
- Kurdyka, K., On gradients of functions definable in o-minimal structure,
Ann. Inst. Fourier (Grenoble) 48 (1998), 769–783. - Manselli, P., Pucci, C., Maximum length of steepest descent curves for quasi-convex functions.
Geom. Dedicata 38 (1991), 211–227. - Coste, M. An Introduction to Semialgebraic Geometry.
Istituti Editoriali e Poligrafici Internazionali, Pisa (2000)