Avis de Soutenance
Monsieur Dawen WU
Informatique mathématique
Soutiendra publiquement ses travaux de thèse intitulés
Résolution de quelques problèmes d’optimisation non linéaire avec l’apprentissage profond
(English title: Solving Some Nonlinear Optimization Problems with Deep Learning)
dirigés par Monsieur Abdel LISSER
Soutenance prévue le jeudi 30 novembre 2023 à 14h00
Lieu : Amphi sc.071 – bâtiment Bouygues, 9 rue Joliot Curie, 91190 Gif sur Yvette
Lien public pour l’accès a la salle virtuelle de soutenance :
https://teams.microsoft.com/l/meetup-join/19%3ameeting_OWQxZWYxNzAtYTQwNS00NjcxLWE0YjAtYzNkZDEwZDhkMmFi%40thread.v2/0?context=%7b%22Tid%22%3a%2261f3e3b8-9b52-433a-a4eb-c67334ce54d5%22%2c%22Oid%22%3a%22028ad2a2-15b8-4f09-8c4f-523b52d10648%22%7d
ID de reunion : 321 840 011 222
Code secret: Vne9Ky
Composition du jury proposé
| Alexei GAIVORONSKI | Norwegian University of Science and Technology | Rapporteur |
| Andrea SIMONETTO | ENSTA-Paris, Institut Polytechnique de Paris | Rapporteur |
| Salah-Eddine EL AYOUBI | Laboratoire des Signaux et Systèmes, Université Paris-Saclay | Examinateur |
| Jia LIU | Xi’an jiaotong university | Examinateur |
| Sihem TEBBANI | Laboratoire des Signaux et Systèmes, Université Paris-Saclay | Examinatrice |
| Résumé : |
| Cette thèse examine quatre types de problèmes d’optimisation non linéaire, à savoir les jeux à bimatrices, les équations de projection non linéaires (NPEs), les problèmes d’optimisation convexe non lisse (NCOPs) et les jeux à contraintes aléatoires (CCGs). Ces quatre classes de problèmes d’optimisation non linéaire trouvent de nombreuses applications dans divers domaines tels que l’ingénierie, l’informatique, l’économie et la finance. Nous visons à introduire des algorithmes de solution basés sur l’apprentissage profond pour ces problèmes. Pour les jeux à bimatrices, nous utilisons des réseaux neuronaux à convolution (CNNs) pour calculer les équilibres de Nash. Plus précisément, nous concevons une architecture de CNN où l’entrée est un jeu à bimatrice et la sortie est l’équilibre de Nash prédit pour le jeu. Pour construire un ensemble de données d’entraînement, nous générons un ensemble de jeux à bimatrices selon une distribution de probabilité donnée et utilisons l’algorithme de Lemke-Howson pour trouver leurs véritables équilibres de Nash. Le CNN proposé est entraîné sur cet ensemble de données pour améliorer sa précision de prédiction. Après l’entraînement, le CNN est capable de prédire les équilibres de Nash pour des jeux à bimatrices non vus. Les résultats expérimentaux démontrent l’efficacité computationnelle exceptionnelle de notre approche basée sur CNN, au prix de sacrifier un peu de précision. Pour les NPEs, les NCOPs et les CCGs, qui sont des problèmes d’optimisation plus complexes, ils ne peuvent pas être directement introduits dans les réseaux neuronaux. Par conséquent, nous avons besoin d’outils plus avancés pour gérer ces problèmes, à savoir l’optimisation neurodynamique et les réseaux neuronaux informés par la physique (PINNs). Plus précisément, nous utilisons d’abord une approche neurodynamique pour modéliser un problème d’optimisation non linéaire comme un système d’équations différentielles ordinaires (ODEs). Nous utilisons ensuite un modèle basé sur PINN comme solution approximative au système d’ODE résultant, où l’état final du modèle représente une prédiction au problème d’optimisation original. Le réseau neuronal est formé en vue de résoudre le système d’ODE, résolvant ainsi le problème d’optimisation original. Une contribution clé est que notre approche transforme un problème d’optimisation non linéaire en un problème d’entraînement de réseau neuronal. En conséquence, nous résolvons les problèmes d’optimisation en utilisant uniquement l’infrastructure d’apprentissage profond comme PyTorch, Tensorflow, Jax, sans compter sur les solveurs d’optimisation convexe tels que CVXPY, CPLEX ou Gurobi. |
Abstract :
This thesis considers four types of nonlinear optimization problems, namely bimatrix games, nonlinear projection equations (NPEs), nonsmooth convex optimization problems (NCOPs), and chance-constrained games (CCGs). These problems find extensive applications in various domains such as engineering, computer science, economics, and finance. We aim to introduce deep learning-based solution algorithms for these problems.
For bimatrix games, we use Convolutional Neural Networks (CNNs) to compute Nash equilibria. Specifically, we design a CNN architecture where the input is a bimatrix game and the output is the predicted Nash equilibrium for the game. To construct a training dataset, we generate a set of bimatrix games by a given probability distribution and use the Lemke-Howson algorithm to find their true Nash equilibria. The proposed CNN is trained on this dataset to improve its prediction accuracy. After training, the CNN is capable of predicting Nash equilibria for unseen bimatrix games. Experimental results demonstrate the exceptional computational efficiency of our CNN-based approach, at the cost of sacrificing some accuracy.
For NPEs, NCOPs, and CCGs, which are more complex optimization problems, they cannot be directly fed into neural networks. Therefore, we need more advanced tools to handle these problems, namely neurodynamic optimization and Physics-Informed Neural Networks (PINNs). Specifically, we first use a neurodynamic approach to model a nonlinear optimization problem as a system of Ordinary Differential Equations (ODEs). We then use a PINN-based model as an approximate solution to the resulting ODE system, where the end state of the model represents a prediction to the original optimization problem. The neural network is trained toward solving the ODE system, thereby solving the original optimization problem. A key contribution is that our approach transforms a nonlinear optimization problem into a neural network training problem. As a result, we solve the optimization problems using only deep learning infrastructure such as PyTorch, Tensorflow, Jax, without relying on convex optimization solvers such as CVXPY, CPLEX, or Gurobi.
