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.
Forme de l'enseignement: 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.
- Sundaram, "A First Course in Optimization Theory", Cambridge University Press
- Boyd and Vandenberghe, "Convex Optimization", Cambridge University Press
1. 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)
2. 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
3. Algorithmes d'optimisation sous contraintes
- Lagrange, dualité, KKT, algorithmes primal-double
- Point intérieur, méthodes de pénalité.
4. 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)
5. Optimisation discrète et non convexe
- Méthodes non convexes
- Algorithmes d'approximation
- Sous-modularité, SDP.
6. 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
Résultats de l'Apprentissage:
- être capable de reconnaître, de formuler et de résoudre des problèmes d'optimisation.
- être capable de transformer certaines classes de problèmes en problèmes convexes équivalents.
- être capable de comprendre les avantages et les inconvénients de différents algorithmes d'optimisation
- être capable de comprendre les limites d'application des techniques de programmation convexe à la programmation non convexe.
- être capable de suivre les développements récents en optimisation pour le big data et l'apprentissage automatique
Nb Heures : 21.00.
Evaluation: 80% examen, 20% pour les devoirs maison .
