La théorie de l'optimisation (convexe, non convexe, discrète) est un domaine important qui s'applique à presque tous les domaines techniques et non techniques, y compris la communication sans fil, les réseaux, l'apprentissage automatique, la sécurité, les systèmes de transport, la finance (gestion de portefeuille) et la recherche opérationnelle (chaîne d'approvisionnement, inventaire). Il a récemment suscité un intérêt encore plus grand en tant qu'outil sous-jacent aux techniques d'apprentissage automatique avancées pour les « Big Data » (DNN, descente de gradient stochastique). Dans ce cours, nous aborderons à la fois les fondamentaux (algorithmes, dualité, convergence, optimalité) ainsi qu'une gamme d'applications dans le domaine de l'allocation de ressources (en réseau), de l'optimisation distribuée et de l'apprentissage automatique. Un accent particulier sera mis sur l'exemple des applications des techniques d'optimisation aux problèmes d'ingénierie modernes et de CS dans le but de développer les compétences et le background nécessaires pour reconnaître, formuler et résoudre les problèmes d'optimisation.
Modalités pédagogiques : Séances théoriques supportées par des exercices explicatifs et séances de travaux dirigés.
Règles du cours : La participation aux travaux dirigés n'est pas obligatoire mais fortement recommandée.
- Livre : SUNDARAM R. K. A First Course in Optimization Theory. Cambridge University Press, 1996, 376p.
- Livre : BOYD S., VANDENBERGHE L. Convex Optimization. Cambridge University Press, 2004, 727p.
Valeurs propres, variables gradient, matrice hessienne, calculs multivariés.
Principes fondamentaux d'optimisation
- Types de problèmes d'optimisation : sans contrainte, contrainte, linéaire, convexe, géométrique, etc.
- Conditions d'optimalité (minimums locaux / globaux), solutions analytiques
- Théorie de la convexité (ensembles, fonctions, composition)
Algorithmes d'optimisation sans contrainte
- Méthodes de premier ordre : descente par gradient, descente la plus raide, sous-gradient, théorie de la convergence
- Méthodes de second ordre : Newton, quasi newton
- Accélération et élan : Nesterov, heavy-ball
Algorithmes d'optimisation sous contraintes
- Lagrange, dualité, KKT, algorithmes primal-double
- Point intérieur, méthodes de pénalité.
Sujets avancés
- Optimisation distribuée, décomposition primale / double, ADMM
- Algorithmes proximaux, descente de miroir
- Descente de coordonnées (en bloc), descente de gradient stochastique, méthodes par lots, Adam, Adagrad
- Optimisation convexe en ligne (bandits multi-armés)
Optimisation discrète et non convexe
- Méthodes non convexes
- Algorithmes d'approximation
- Sous-modularité, SDP.
Applications :
- Régularisation des problèmes d'apprentissage automatique (régularisations Lasso, L1 / L2)
- Complétion matricielle (systèmes de recommandation, détection comprimée)
- Problèmes d'allocation de ressources (communication sans fil, cloud computing, mise en cache)
- Réseaux de neurones profonds et théorie d'optimisation
Objectifs d'apprentissage :
- Reconnaître, formuler et résoudre des problèmes d'optimisation.
- Transformer certaines classes de problèmes en problèmes convexes équivalents.
- Comprendre les avantages et les inconvénients de différents algorithmes d'optimisation
- Comprendre les limites d'application des techniques de programmation convexe à la programmation non convexe.
- Suivre les développements récents en optimisation pour le big data et l'apprentissage automatique
Nombre d'heure : 21.00
Evaluation :
- Examen (80% de la note finale) ;
- Devoirs maison (20% de la note finale).
