Séminaire Français d’Optimisation

Le Séminaire Français d’Optimisation est un séminaire en ligne à destination de la communauté française d’optimisation. Il est  parrainé par le GDR MOA, PGMO et SMAI-MODE.

Il s’agit d’un séminaire régulier qui a lieu une fois par mois. La plateforme utilisée est Zoom. Un lien est donné quelques jours avant chaque conférence.

Pour recevoir les annonces du séminaire, vous pouvez vous inscrire ici à la liste de diffusion.

Comité scientifique : S. Adly, J. Bolte, A. Chambolle, S. Gaubert, N. Oudjane, F. Santambrogio, H. Zidani.

Prochains séminaires

Date: Jeudi 16 juin 2022 à 16h00 (heure de Paris).
Speaker: Chloé Jimenez (LMBA, UBO)
Title: Représentation L^2 de trajectoires dans l’espace de Wasserstein P_2 et solutions de viscosité définies par des fonctions test sur P_2

Abstract: En théorie du contrôle optimal dans l’espace P_2, on est amené à considérer des courbes absolument continues sur P_2 satisfaisant une inclusion différentielle. Nous allons montrer comment ces trajectoires peuvent être représentées par des courbes absolument continues sur P_2 satisfaisant l’inclusion différentielle associée. Nous verrons également une notion de solution de viscosité utilisant des fonctions test définies sur P_2, dérivables au sens MFG. Cette notion a été utilisée avec succès par A. Marigonda, M. Quincampoix et co-auteurs pour caractériser des fonctions valeurs associées à des problèmes de contrôle.

Information de connexion à la réunion zoom :
https://univ-lyon1-fr.zoom.us/j/89263476526?pwd=MnhKMGszc0ljL2tSeWtzSDBDcjR5dz09

ID de réunion : 892 6347 6526
Code secret : SFO2021/22

Séminaires passés

Date: Jeudi 12 mai 2022 à 16h
Speaker: Olivier Ley (IRMAR, INSA Rennes)
Title: Une fonction convexe très régulière dont les trajectoires de gradient spiralent

Abstract: Je présenterai un travail effectué en collaboration avec Aris Daniilidis (Vienne) et Mounir Haddou (Rennes) dont le sujet remonte à des questions plus anciennes que nous nous étions posées avec Aris Daniilidis et Jérôme Bolte : la convexité est une notion très forte et essentielle en optimisation. Est-ce que le fait qu’une fonction soit convexe renforce les propriétés qu’on peut attendre des trajectoires de gradient ? Je citerai quelques résultats positifs et négatifs et construirai une fonction convexe en dimension 2, analytique sauf en 0 où elle atteint son unique minimum et dont les trajectoires de gradient spiralent autour du minimum mais aussi à l’infini. En outre, cette fonction satisfait l’inégalité de Lojasiewicz en 0. Cette fonction fournit un contre-exemple à la conjecture de gradient de Thom au voisinage du minimum de la fonction mais également à l’infini.

À consulter : À venir

Date: Jeudi 14 avril 2022 à 16h
Speaker: Gabriel Peyré (CNRS and ENS)
Title: Smooth Bilevel Programming for Sparse Regularization

Abstract: Iteratively reweighted least square (IRLS) is a popular approach to solve sparsity-enforcing regression problems in machine learning. State of the art approaches are more efficient but typically rely on specific coordinate pruning schemes. In this work, we show how a surprisingly simple reparametrization of IRLS, coupled with a bilevel resolution (instead of an alternating scheme) is able to achieve top performances on a wide range of sparsity (such as Lasso, group Lasso and trace norm regularizations), regularization strength (including hard constraints), and design matrices (ranging from correlated designs to differential operators). Similarly to IRLS, our method only involves linear systems resolutions, but in sharp contrast, corresponds to the minimization of a smooth function. Despite being non-convex, we show that there is no spurious minima and that saddle points are « ridable », so that there always exists a descent direction. We thus advocate for the use of a BFGS quasi-Newton solver, which makes our approach simple, robust and efficient. At the end of the talk, I will discuss the associated gradient flows as well as the connection with Hessian geometry and mirror descent. This is a joint work with Clarice Poon (Bath Univ.). The corresponding article is available: https://arxiv.org/abs/2106.01429. A python notebook introducing the method is available at this address: https://nbviewer.org/github/gpeyre/numerical-tours/blob/master/python/optim_7_noncvx_pro.ipynb

À consulter : À venir

Date : Jeudi 10 mars 2022 à 16h
Speaker: Aude Rondepierre (IMT, Toulouse)
Title: FISTA is an automatic geometrically optimized algorithm for strongly convex functions

Abstract: In this talk we are interested in the famous FISTA algorithm. We show that FISTA is an automatic geometrically optimized algorithm for functions satisfying a quadratic growth assumption. This explains why FISTA works better than the standard Forward-Backward algorithm (FB) in such a case, although FISTA is known to have a polynomial asymptotical convergence rate while FB is exponential. We provide a simple rule to tune the friction parameter within the FISTA algorithm to reach an ε-solution with an optimal number of iterations. These new results highlight the efficiency of FISTA algorithms, and they rely on new non asymptotic bounds for FISTA.

À consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 3 février 2022 à 16h
Orateur: Laurent Pfeiffer (INRIA)
Titre: Generalized conditional gradient method for potential mean field games

Abstract: The starting point of our work is a general connexion, in the context of potential non-atomic games, between the Frank-Wolfe algorithm and the fictitious play, a best-response procedure. We investigate this connexion in the context of potential mean-field games, in their formulation as a coupled system of two PDEs. More precisely, we show that in this framework, the fictitious play algorithm is nothing but a particular implementation of the so-called generalized conditional gradient method. At a technical level, we investigate the rate of convergence of the variables of the model for various stepsize rules.
Joint work with Pierre Lavigne (Institut Louis Bachelier).

À consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 16 décembre 2021 à 16h
Orateur : Ludovic Rifford (Université Côte d’Azur)
Titre : Combien de temps faut il à un coureur pour être seul ?

Résumé : La conjecture du coureur solitaire prévoit le résultat suivant : Si n coureurs courent sur une piste d’athéltisme circulaire de longueur 1, à vitesses constantes deux à deux distinctes et en partant d’un même point, alors chaque coureur se retrouve solitaire à un certain moment, c’est à dire que pour chaque coureur il existe un temps t > 0 tel que ce coureur est à distance au moins 1/n de tous les autres. Cette conjecture, liée à des problèmes d’approximation diophantienne et de théorie de l’obstruction, est résolue jusqu’à n=7 et reste ouverte pour tous les n restants ; nous nous intéresserons au temps mis par un coureur pour devenir solitaire ou en d’autre terme pour être seul.

À consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 18 novembre 2021 à 16h
Orateur : Thierry Champion (Université de Toulon)
Titre : Obtention de bornes pour la convergence de méthodes de points fixes via le transport optimal

Résumé : On s’intéresse dans cet exposé à une famille de métriques sur les entiers naturels associées à l’étude du taux de convergence des itérés produits par des méthodes de points fixe de type Krasnodesl’skii-Mann. Ces métriques sont définies de manière inductive via des problèmes de transport optimal emboités : on donnera des propriétés de ces distances, et leurs applications dans l’obtention de taux de convergence précis, guidant ainsi le choix de paramètres optimaux.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 14 octobre 2021 à 16h
Orateur : Pierre Cardaliaguet (CEREMADE, Paris Dauphine)
Titre : Quelques aspects des jeux à champ moyen

Résumé : Les jeux à champ moyen étudient des problèmes de contrôle optimal avec un très grand nombre d’agents. Après une introduction générale, on présentera des résultats récents sur les jeux à champ moyen avec un bruit commun, nécessitant de nouvelles notions de solutions faibles d’équations de Hamilton-Jacobi et de master equations.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 1er juillet 2021 à 16h
Speaker: Silvia Villa (Université de Gène, Italie)
Title : A randomized Zeroth-order algorithm

Abstract: In this talk I will present a randomized zeroth-order approach, based on approximating the exact gradient by finite difference computed in a set of orthogonal random directions.
A number of previously proposed methods are derived as special cases. including spherical smoothing, coordinate descent, as well as discretized gradient descent.
The main contribution is proving convergence guarantees as well as convergence rates, under different parameter choices and assumptions. The results apply to convex functions, but also to non-convex ones satisfying geometric conditions. Theoretical results are complemented and illustrated by numerical experiments.

Date : Jeudi 17 juin 2021 à 16h
Orateur: Aris Daniilidis (DIM-CMM, Université du Chili)
Titre : Courbes et suite auto-contractantes

Résumé : Les courbes (resp. suites) auto-contractantes sont étroitement liées à la convexité. Les trajectoires du gradient, les suites proximales et les suites obtenues par l’algorithme de la plus grande pente d’une fonction convexe sont des exemples typiques, la suite obtenue par l’algorithme des projections alternées pour le problème de la faisabilité de deux ensembles convexes en est un autre. Ces courbes (resp. suites) possèdent de bonnes propriétés asymptotiques exploitable en optimisation. Dans cet exposé nous présenterons une revue de résultats récents ainsi que l’état des lieux suivi par quelques problèmes ouverts.

Date : Jeudi 3 juin 2021 à 16h
Orateur: Philippe Toint
Titre : Recent results in worst-case evaluation complexity for smooth and non-smooth, exact and inexact, nonconvex optimization.

Résumé : Nous présenterons une revue de résultats récents concernant la complexité (dans le pire des cas) pour des algorithms d’optimisation non-convexes qui utilisent des modèles de degré potentiellemnt élevé. Les résultats obtenus sont donc valides quelque soit le degré du modèle et l’ordre d’optimalité requis, ce qui généralise les théorèmes connus pour les ordres un et deux. Après avoir considére les problèmes sans contraintes et sans bruit, nous examinerons ce qui peut être dit des problèmes bruités et des problèmes avec contraintes.

Date : Jeudi 20 mai 2021 à 16h
Orateur: Nelly Pustelnik (ENS Lyon).
Titre : Itérations de gradient ou proximales en traitement du signal et des images.

Résumé : Dans de nombreuses tâches de traitement du signal et des images, le problème d’optimisation sous-jacent peut se formuler comme une somme de deux fonctions dont l’une est différentiable et de gradient Lipschitz et la seconde convexe mais non-lisse. De nombreux algorithmes proximaux ont été développés pour résoudre ce problème mais il reste très difficile de prédire celui qui aura le meilleur comportement numérique pour un problème de traitement du signal ou des images donné. 

Dans cet exposé, nous illustrerons notre propos sur un exemple de segmentation de texture pouvant se formuler comme un problème d’optimisation fortement convexe et nous fournirons quelques résultats expérimentaux comparant FISTA sur le dual et l’algorithme de Chambolle-Pock exploitant la forte convexité. Dans un second temps, nous pousserons l’analyse un peu plus loin en proposant des comparaisons théoriques et numériques dans un cadre d’étude simplifié entre différents algorithmes proximaux standards (descente de gradient, explicite-implicite, Douglas-Rachford, Peaceman-Rachford).

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 6 mai 2021 à 16h
Orateur: Guillaume Carlier (CEREMADE, Paris Dauphine).
Titre : Remarques sur le transport optimal entropique et l’algorithme de Sinkhorn dans le cas multi-marges.

Résumé :Le transport optimal entropique est devenu très populaire ces dernières années en particulier grâce à l’algorithme de Sinkhorn. Dans cet exposé je m’intéresserai au cas multi-marginales qui a des applications en physique, économie et machine learning. Je montrerai que le système de Schrödinger multi-marginales est bien posé (travail commun avec Maxime Laborde) puis que l’algorithme de Sinkhorn converge linéairement.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 15 avril 2021 à 16h
Speaker: Luis Briceño (Universidad Técnica Federico Santa Maria, Chili)
Title: Splitting algorithms for non-smooth convex optimization: Review and application to Mean Field Game.

Abstract:In this talk we review some classical algorithms for solving structured convex optimization problems, from gradient descent to proximal iterations and going further to modern proximal primal-dual splitting algorithms in the case of more complicated objective functions. We put special attention to constrained convex optimization appearing in Mean-Field Games and we compare the performance of several splitting algorithms in this context.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 1er avril 2021 à 16h
Orateur : Alexandre D’Aspremont (ENS)
Titre : Bornes d’approximations pour problèmes avec contrainte de parcimonie (Avec Armin Askari et Laurent El Ghaoui).

Résumé : Nous montrons comment le théorème de Shapley Folkman, un résultat qui s’apparente à un théorème central limite pour la convexité, permet de borner le saut de dualité de problèmes d’optimisation avec contrainte de parcimonie, écrits sur des sous espaces de dimension faible. Nous montrons en particulier que dans des applications en statistiques comme LASSO et la régression logistique parcimonieuse, ces bornes sont pratiquement exactes dès que toutes les variables informatives ont été incorporées au modèle.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 18 mars 2021 à 16h
Orateur : Giuseppe Buttazzo (Università di Pisa, Italie)
Title : On the relations between principal eigenvalue and torsional rigidity

Abstract : The relations between principal eigenvalue of the Laplace operator and torsional rigidity are studied in the class of general domains, convex domains, and domains with a small thickness. This is of help to provide some bounds for the Blasche-Santaló diagram of the two quantities. The results have been obtained in a joint work with Michiel van den Berg (Bristol) and Aldo Pratelli (Pisa).

Date : Jeudi 4 mars 2021 à 16h
Orateur : Daniela Tonon (Université de Padoue, Italie)
Title : A comparison principle for the Mean Field Schrödinger problem

Abstract : In this talk we introduce the Mean Field Schrödinger problem (MFSP), that is the problem of finding the most likely evolution of a cloud of interacting Brownian particles conditionally on observations. Using classical results on the representation of entropy functionals, one can in many cases recast the MFSP as a mean field control problem whose optimality conditions are expressed by a PDE system consisting in a Fokker-Planck equation coupled with a Hamilton Jacobi Bellman equation with boundary marginal constraints. In this sense MFSP shows some analogies with Mean Field games problems. However, the coupling terms are often of different nature from those covered in the MFG literature, thus posing new challenges. In addition to this mean field control interpretation, the optimal value of MFSP can be formally seen in duality with the solution to an Hamilton Jacobi Bellman equation on the space of probability measures; we present a comparison principle for this equation.

Date : Jeudi 11 février 2021 à 16h
Orateur : G. Vigeral.
Titre : Structure des ensembles d’équilibres de Nash de jeux à paiements entiers ; conséquences sur la complexité de certains problèmes de décision en théorie des jeux.

Résumé : L’ensemble des paiements d’équilibres de Nash d’un jeu statique fini à paiements entiers est non vide, semi algébrique et compact. On montre que dans le cas de 3 joueurs ou plus la réciproque est vraie : si E est un ensemble de R^N non vide, semi algébrique et compact on peut construire explicitement un jeu fini à N joueurs et paiements entiers dont E est l’ensemble des paiements d’équilibres de Nash. On montre également un résultat du même ordre concernant les équilibres plutôt que les paiements d’équilibres.
On donnera des conséquences de ces résultats concernant la complexité algorithmique de certains problèmes concernant les jeux à 3 joueurs ou plus.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 28 janvier 2021 à 16h
Orateur : Anne Auger (INRIA, CMAP).
Title : Gradient-based and Gradient-free Multiobjective Optimization Converging to the Entire Pareto Front

Abstrat : In the context of mutliobjective (or vector) optimization where we want to optimize several conflicting objectives at the same time, we discuss a novel approach where we incrementally build an approximation of the Pareto set (the set of best trade-off solutions: that cannot be improved along one objective without to degrade along another one) by optimizing a single-objective criterion. This single-objective optimization problem is based on the so-called hypervolume improvement and tackled by using the quasi-Newton BFGS algorithm or SLSQP either using the gradient of the objective functions or approximating it. We present numerical results as well as discuss theoretical convergence results where convergence to the entire Pareto-front is shown.

Date : Jeudi 14 janvier 2021 à 16h
Orateur : Nadia Oudjane (EDF).
Title : Decomposition of high dimensional aggregative stochastic control problems. Application to energy management
Joint work with Adrien Séguret (EDF/OSIRIS), Clémence Alasseur (EDF/OSIRIS, FIME), J. Frédéric Bonnans (INRIA, CMAP), Antonio De Paola (Bath University, UK) and Vincenzo Trovato (Imperial College, UK)

Abstrat : We consider high dimensional stochastic control problems, in which the controls are aggregated in the cost function. Our motivation comes from one specific application from power systems consisting in optimally managing electricity generation from power plants and flexible consumption from domestic appliances in order to balance the system. In the general framework, we introduce a modified problem, whose optimal control is under some reasonable assumptions an ε-optimal solution of the original problem. Then we present a decentralized stochastic algorithm whose convergence to the solution of the modified problem is established.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 17 décembre 2020 à 16h
Orateur : Hasnaa Zidani (ENSTA, Paris).
Title : Relationship between Pontryagin’s principle and Hamilton-Jacobi approach for a class of control problems with intermediate state constraints

Abstrat : In optimal control theory, it is well known that the costate variable of the Pontryagin principle can be interpreted in term of gradient of the value function, evaluated along the optimal trajectory. This claim is well established when the problem is without state constraints.
In this talk, we will examine the validity of such relationship in the case when the control problem is in presence of intermediate state constraints and without controllability assumptions. Then we will show how to combine this sensitivity relation with the shooting method for solving some aerospace problems.

ID de réunion : 846 7187 9268 ; Code secret : SFO2020/21 -->
A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 3 décembre 2020 à 16h
Orateur : Pierre Weiss (Université de Toulouse).
Title : Sampling rates for l1-synthesis

Abstrat : In this talk, I will try to shed some light on the geometry of l1-based signal recovery. This setting has been studied extensively in the last decade with the advent of compressed sensing and super-resolution. There is however clear evidence that the best existing theories are still unable to predict some of the observed numerical behaviours, especially when using redundant dictionaries. I will work in the simple framework of under-sampled noisy Gaussian measurements, and try to explain how the geometry of high dimensional convex cones enters in the game and how certain quantities such as the Renegar condition number or the circumangle of a descent cone can provide decent bounds on the number of measurements sufficient for efficient recovery.

A preprint is available here.
A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 19 novembre 2020 à 16h
Orateur : Lénaïc Chizat (Paris Saclay)
Title : Analyse du flot de gradient pour les réseaux de neurones larges à deux couches

Abstrat : Les réseaux de neurones artificiels sont des familles paramétrées de fonctions de prédiction, utiles dans de nombreuses tâches en apprentissage automatique (classification, régression, modèles génératifs, etc). Pour une tâche d’apprentissage donnée, les paramètres du réseau sont ajustés à l’aide d’un algorithme de descente de gradient, de sorte que le prédicteur correspondant atteigne une bonne performance sur un jeu de données d’entraînement. Dans cet exposé, on présentera une analyse de cet algorithme pour les réseaux de neurones larges à deux couches en apprentissage supervisé, qui aboutit à une caractérisation précise du prédicteur appris. L’idée maîtresse consiste à étudier la dynamique d’entraînement en temps continu lorsque la taille du réseau de neurones tend vers l’infini: cet objet limite est un flot de gradient Wasserstein. Bien que la fonction objectif ne soit pas géodésiquement convexe, on montre que pour une initialisation adéquate, la limite de ce flot de gradient (si elle existe) est un minimiseur global. Nous étudierons aussi le « biais implicite » de cet algorithme quand l’objectif d’entraînement est la fonction de perte logistique sans régularisation : parmi la multitude de minimiseurs globaux, l’algorithme en choisit un en particulier, qui s’avère être un classifieur de type « marge maximale ». Enfin, nous discuterons des conséquences de ces résultats sur les performances statistiques de ces modèles en grande dimension. Il s’agit d’un travail en collaboration avec Francis Bach.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 5 novembre 2020 à 16h
Orateur : Serge Gratton (ENSEEIHT)
Title : Optimization with inexact gradient and function

Abstrat : Important saving can be obtained on nowadays computer architectures by performing computation with reduced arithmetic: single precision, half precision, and even less. In this talk, we demonstrate that it is possible to produce robust optimization method that make use of an available hierarchy of arithmetic. In particular we propose adaptive algorithms that guarantee the same attainable accuracy accuracy as full precision algorithms. We propose a convergence theory for these algorithms as well as complexity guarantees. We will first address quadratic convex programming and then consider non convex situations.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 15 octobre 2020 à 16h
Orateur : Emilie Chouzenoux (INRIA Saclay)
Title : Majorization-Minimization Subspace Algorithms for Large Scale Data Processing

Abstrat : Modern image recovery problems require powerful optimization frameworks to handle high dimensionality while providing reliable numerical solutions in a reasonable time. New optimization algorithms have thus to be designed, paying attention to computational complexity, scalability, and robustness. Majorization-Minimization (MM) approaches have become increasingly popular recently, in both signal/image processing and machine learning areas. My talk will present new theoretical and practical results regarding the MM Memory Gradient (3MG) algorithm [1], where the update of each iterate is restricted to a subspace of low dimension. I will show how to cast this efficient scheme into a block distributed version of it, named BD3MG, where blocks of variables are processed in an asynchronous manner, so as to take advantage of a distributed memory environment [2]. Convergence of the sequence built by the proposed BD3MG method will be analysed under mild assumptions. Application to the restoration of 3D images degraded by a depth-variant blur will illustrate the significant computational time reduction and the great scalability potential offered by the BD3MG approach when compared to several synchronous and asynchronous competitors.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Jeudi 1er octobre 2020 à 16h
Orateur : Alessio Figalli (ETH Zürich)
Title : Strong rigidity of crystals

Abstrat : Geometric and functional inequalities play a crucial role in several problems in the calculus of variations, partial differential equations, geometry, etc. More recently, there has been a growing interest in studying the stability of such inequalities. This talk aims to give an overview of some results on this topic, focusing mainly on a recent stability result for anisotropic isoperimetric inequalities, which implies a robust rigidity property of crystals.

Date : Jeudi 17 septembre 2020 à 16h
Orateur : Francisco Silva (Université de Limoges)
Title : Approximation of first order mean field games

Abstrat : In this talk we will review some results on equilibria of first order mean field games and their approximation. The main focus of the talk will be a detailed exposition on how these equilibria can be approximated by equilibria of a suitable sequence of mean field games in discrete time and with finite state space.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Mercredi 8 juillet 2020 à 17h
Orateur : Roberto Cominetti (Université Adolfo Ibañez, UAI, Chili)
Title : Large congestion games: Wardrop v/s Poisson ?

Abstrat : Congestion is a common phenomenon in transportation networks, both in large urban areas and telecommunication networks. We revisit the Wardrop equilibrium concept for routing games, as a continuous approximation for finite games with an increasing number of small players. We consider two scenarios: a deterministic model in which players have a small weight, as well as a stochastic scenario where players have non-negligible weights but are present with a small probability. In both cases, we obtain convergence towards two different Wardrop models, where in the second case the flows in the network retain their stochastic nature and are described by Poisson distributions. The latter can also be seen as a Poisson equilibrium in the sense of Myerson, and is consistent with the empirical flows observed in urban traffic.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Mercredi 24 juin 2020 à 17h30
Orateur : Edouard Pauwels (Université Toulouse 3)
Titre : Un bestiaire de contre-exemples en optimisation convexe lisse.

Résumé : Cet exposé présente deux contre-exemples en optimisation convexe lisse coercitive. Le premier montre qu’en général la descente de gradient avec recherche linéaire exacte n’est pas convergente, le second que les trajectoires du système dynamique gradient n’ont pas de tangente à l’infini, contrairement au cas analytique (cf. conjecture de Thom établie par Kurdyka et al.). Ces exemples sont construits dans le plan à l’aide d’un résultat d’interpolation: étant donné une suite croissante d’ensembles convexes compacts dont la frontière est une courbe k fois différentiable (k > 1) à courbure positive, il existe une fonction convexe Ck pour laquelle chaque sous ensemble est un sous niveau. L’exposé portera sur les éléments de preuve de ce résultat d’interpolation et la manière dont il peut être utilisé pour construire les contre exemples annoncés. D’autres pathologies convexes lisses peuvent être produites grâce à cette approche : la méthode de Gauss-Seidel, les algorithmes de type Bregman, le flot de Newton, peuvent par exemple induire des trajectoires minimisantes non convergentes. Ces cas seront brièvement évoqués.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé

Date : Mercredi 10 juin 2020 à 17h30
Oratrice : Monique Laurent (Centrum Wiskunde & Informatica, Amsterdam and Tilburg University)
Title : Convergence analysis of approximation hierarchies for polynomial optimization.

Abstract : Minimizing a polynomial function f over a compact set K is a computationally hard problem. Upper bounds have been introduced by Lasserre (2011), which are obtained by searching for a degree 2r sum-of-squares density function minimizing the expected value of f over K with respect to a given reference measure supported by K. We will discuss several techniques that permit to analyse the performance guarantee of these bounds. This includes an eigenvalue reformulation of the bounds, links to extremal roots of orthogonal polynomials and to cubature rules, and reducing to the univariate case by means of push-forward measures. For simple sets K like the box, the unit ball, the simplex and the unit sphere one can show that the convergence rate to the global minimum is in O(1/r^2) and that this bound is tight for some classes of polynomials. These results extend to smooth strictly convex bodies satisfying some boundary conditions and, for general convex bodies, one can show a slightly weaker convergence rate in O((log(r)/r)^2). Based on joint works with Etienne de Klerk and Lucas Slot.

A consulter : Slides de l’exposé (PDF) – Vidéo de l’exposé