Dauphine Numérique - Nos recherches
Optimisation et contrôle optimal

Résoudre efficacement
des problèmes d’intelligence artificielle

L’optimisation et le contrôle optimal sont au cœur des algorithmes avancés d’Intelligence Artificielle, que ce soit pour accélérer les outils de calibration ou d’estimation, ou plus en amont pour entraîner des algorithmes d’apprentissage, y compris les réseaux de neurones profonds.

Optimisation continue

Optimisation combinatoire

Optimisation non convexe

Optimisation sans dérivées

Contrôle optimal stochastique

Applications

 

Ce champ de recherche mathématique est au cœur du développement des algorithmes utilisés en intelligence artificielle avec des applications dans différents domaines

Apprentissage machine

Apprentissage profond

Traitement du signal et des images

Vision par ordinateur

Théorie des jeux

Economie et finance

Nos recherches
dans les laboratoires de l'université

L’optimisation est représentée selon ses différentes facettes à Dauphine - PSL : optimisation continue et contrôle optimale au CEREMADE, optimisation discrète et optimisation sans dérivée au LAMSADE.


Nos recherches par
thématique

Optimisation continue

Il s’agit de construire des algorithmes efficaces pour l’estimation de paramètre ou la calibration de réseau de neurones. Ceci recouvre notamment la résolution des problèmes inverses, des méthodes de discrétisation d’ordre supérieur pour les flots de gradients sur l’espace de Wasserstein, les systèmes de Langevin avec interaction à champs moyen, ou le contrôle.

L’une des spécialités du CEREMADE, à travers son équipe INRIA Mokaplan, est le transport optimal qui est fortement lié aux problèmes de minimisation sur l’espace de Wasserstein.

Calibration

Problèmes inverses

Flots de gradients

Transport optimal

Optimisation sur l’espace de Wasserstein

Nos chercheurs

Irène Waldspruger (chaire PRAIRIE), Gabriel Turinici (anciennement membre de l’Institut Universitaire de France), Guillaume Legendre, Guillaume Carlier, Jean-David Benamou, Laurent Cohen (chaire PRAIRIE), Zhenjie Ren

Exemples de travaux

  • Hu K., Kazeykina A., Ren Z. Mean-field Langevin System, Optimal Control and Deep Neural Networks. Paris, Cahier de recherche CEREMADE, Université Paris-Dauphine, 25 p. (2019)
  • Waldspurger I., d’Aspremont A., Mallat S. Phase recovery, Maxcut and complex semidefinite programming. Mathematical Programming, vol. 149, n°1-2, p. 47-81. (2015)
  • Legendre G., Turinici G. Second-order in time schemes for gradient flows in Wasserstein and geodesic metric spaces. Comptes rendus. Mathématique, vol. 355, n°3, p. 345-353. (2017)
  • Carlier G., Duval V., Peyré G., Schmitzer B. Convergence of Entropic Schemes for Optimal Transport and Gradient Flows. SIAM Journal on Mathematical Analysis, vol. 49, n°2, p. 1385-1418. (2017)
  • Benamou J-D., Carlier G., Cuturi M., Nenna L., Peyré G. Iterative Bregman Projections for Regularized Transportation Problems. SIAM Journal on Scientific Computing, vol. 37, n°2, p. A1111–A1138. (2015)
  • Turinici G. Metric gradient flows with state dependent functionals : the Nash-MFG equilibrium flows and their numerical schemes. Nonlinear Analysis, vol. 165, p. 163-181. (2017)

Optimisation combinatoire

Plusieurs problèmes d’intelligence artificielle, que ce soit en apprentissage automatique, en choix social, ou en décision collective, se posent comme un problème d’optimisation combinatoire sous contraintes.

Le LAMSADE a depuis sa création structuré les communautés nationales et européennes de l’optimisation combinatoire/Recherche Opérationnelle et de l’aide à la décision (seul laboratoire européen dont deux membres ont dirigé la société savante EURO).

Les recherches dans ces thématiques sont structurées au sein des projets MATHIS (Programmation Mathématique et Structures Discrètes) du pôle « Optimisation combinatoire et algorithmique » et « Optimisation Combinatoire Multicritère » à l’interface des pôles Aide à la Décision et Optimisation combinatoire et algorithmique du LAMSADE.

Approche polyédrale
Conception de réseaux
Théorie des Graphes
Méthode probabiliste
Robustesse
Programmation semi-définie positive
Système (box-)TDI
Problèmes de grandes tailles
Génération de colonnes
Algorithmes de plans coupants
Ensemble efficace
Pareto
Approximation
Énumération
Compromis

Nos chercheurs

Denis Cornaz, Fabio Furini, Virginie Gabrel, Ararat Harutyunyan, Ridha Mahjoub, Cécile Murat, Lucie Galand, Daniek Vanderpooten, Aissi Hassene

Optimisation non convexe

De nombreuses situations en apprentissage sont naturellement formulées comme des problèmes d’optimisation non convexe : c’est le cas par exemple des réseaux de neurones profonds ou de problèmes en variables matricielles (complétion, factorisation, apprentissage de dictionnaire).

Sur de telles instances, il peut être particulièrement délicat de garantir la résolution globale du problème et il devient crucial de garantir que les méthodes ne restent pas bloquées au voisinage de points selles.

On cherche donc à développer des algorithmes avec de fortes garanties théoriques au second ordre, exprimées en termes de complexité au pire cas, qui soient aussi capables de fonctionner en très grande dimension (par rapport au nombre de variables ou à la taille du jeu de données utilisé).

Optimisation non convexe

Méthodes d’ordre deux

Complexité au pire cas

Exemples de travaux

  • C. W. Royer, M. O’Neill et S. J. Wright. A Newton-CG algorithm with complexity guarantees for smooth unconstrained optimization. Mathematical Programming, 180(1), 451-488 (2019)
  • C. W. Royer et S. J. Wright. Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization. SIAM Journal on Optimization 28 (2) :1448-1477 (2018)
  • E. Bergou, Y. Diouane, V. Kungurstev et C. W. Royer. A subsampling line-search method with second-order results. Rapport technique (2018)
  • S. Gratton, C. W. Royer et L. N. Vicente. A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds. Mathematical Programming, 179(1-2), 195-222 (2018)

Optimisation sans dérivées

Lorsque l’on cherche à calibrer les hyperparamètres d’un modèle d’apprentissage complexe ou à déterminer la meilleure perturbation d’un jeu de données pour fausser l’apprentissage, on se trouve face à des problèmes d’optimisation pour lesquels la fonction « objectif » est extrêmement coûteuse à évaluer, souvent bruitée, et représente la seule information disponible pour l’optimisation.

Les techniques associées, dites d’optimisation sans dérivées, reposent soit sur l’exploration par échantillonnage, soit sur la construction de modèles simulant le comportement de la fonction. Nos travaux considèrent principalement l’utilisation de versions probabilistes de ces approches, dont le coût est plus faible que celui des méthodes déterministes, mais pour lequel on peut toujours obtenir des garanties théoriques (convergence presque sûre, complexité en forte probabilité).

L’intérêt à la fois théorique et pratique de l’aléatoire permet ainsi d’envisager l’application de ces stratégies en grande dimension.

Optimisation sans dérivées

Propriétés probabilistes

Évaluations coûteuses

Exemples de travaux

  • E. Bergou, Y. Diouane, V. Kungurstev et C. W. Royer. A stochastic Levenberg-Marquardt method using random models with application to data assimilation. Rapport technique (2018)
  • S. Gratton, C. W. Royer, L. N. Vicente et Z. Zhang. Direct search based on probabilistic feasible descent for bound and linearly constrained problems. Computational Optimization and Applications, 72(3) : 525-559, 2019.S. (2019)
  • Gratton, C. W. Royer, L. N. Vicente et Z. Zhang. Complexity and global rates of trust-region methods based on probablistic models. IMA Journal of Numerical Analysis, 38(3) : 1579-1597 (2018)
  • S. Gratton, C. W. Royer et L. N. Vicente. A second-order globally convergent direct-search method and its worst-case complexity. Optimization : A Journal of Mathematical Programming and Operations Research, 65(6) : 1105-1128 (2016)
  • S. Gratton, C. W. Royer, L. N. Vicente et Z. Zhang. Direct search based on probabilistic descent. SIAM Journal on Optimization, 25(3) : 1515-1541 (2015)

Contrôle optimal stochastique

Le contrôle optimal consiste à maximiser un critère lié à la trajectoire d’un système contrôlé, souvent dans un environnement aléatoire, parfois en présence d’un joueur adverse.

Il peut s’agir, par exemple, de définir une stratégie d’utilisation de robots de trading en présence d’incertitude sur les paramètres de marché, de définir une stratégie d’enchère optimale face à un provider d’espace publicitaire et en présence de multiples enchérisseurs, etc.

Il peut également s’agir de contrôler un système de manière à le maintenir dans un espace défini, par exemple une voiture autonome sur une route. On parle alors de problème de cible stochastique.

C’est l’un des domaines historiquement phare du CEREMADE, suivant en particulier les travaux de Pierre-Louis Lions (Chaire au Collège de France, Médaille Fields 1994) qui est tout à la fois à l’origine de l’invention de la théorie des solutions de viscosité, particulièrement adaptée aux problèmes de contrôle, et de celle des jeux à champ moyen qui permettent de tenir compte des interactions entre joueurs lorsqu’ils sont très nombreux.

C’est également à Dauphine qu’est née la théorie des cibles stochastiques, sous l’impulsion de Nizar Touzi, alors maître de conférences au CEREMADE.

Contrôle optimal stochastique

Solution de viscosité

Optimisation en environnement incertain

Robustesse

Learning

Cibles stochastiques

Invariance stochastique

Jeux à champs moyens

Nos chercheurs

Pierre-Louis Lions (médaille Fields), Jean-Michel Lasry, Pierre Cardaliaguet, Bruno Bouchard, Daniela Tonon, Julien Claisse, Imen Ben Tahar

Exemples de travaux

  • Briani A., Cardaliaguet P. Stable solutions in potential mean field game systems, NoDEA. Nonlinear Differential Equations and Applications, vol. 25, n°1. (2018)
  • Abi Jaber E., Bouchard B., Illand C. Stochastic invariance of closed sets with non-Lipschitz coefficients. Stochastic Processes and their Applications, vol. 129, n°5, p. 1726-1748. (2019)
  • Graber P., Mészáros A., Silva F., Tonon D. The planning problem in mean field games as regularized mass transport. Calculus of Variations and Partial Differential Equations, vol. 58, n°3. (2019)
  • Baradel N., Bouchard B., Dang N. Optimal Control Under Uncertainty and Bayesian Parameters Adjustments. SIAM Journal on Control and Optimization, vol. 56, n°2, p. 1038-1057. (2018)
  • Claisse J. Optimal control of branching diffusion processes : A finite horizon problem. The Annals of Applied Probability, vol. 28, n°1, p. 1-34. (2018)
  • Bouchard B., Djehiche B., Kharroubi I. Quenched mass transport of particles towards a target. JOTA, to appear (2020)
  • Fernandez Tapia J., Guéant O., Lasry J-M. Optimal Real-Time Bidding Strategies. Applied Mathematics Research Express, vol. March 2017, n°1, 1, p. 142–183. (2017)