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

Séminaires passés

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.


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é