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

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.

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

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é).

• 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)

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.

• 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)

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.

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

• 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)