Optimisation avancée

Objectif

Ce cours a pour objectif de familiariser les étudiants avec l’optimisation convexe et ses algorithmes les plus populaires. Nous étudierons certaines méthodes d’optimisation convexes en les illustrant par des exemples empruntés à d’autres disciplines telles que l’apprentissage statistique, l’économie, etc. Notre approche sera théorique, dans la mesure où nous démontrerons des résultats de convergence des algorithmes et nous réfléchirons à l’optimalité de ces algorithmes. Nous nous efforcerons aussi de comprendre quels sont les avantages et les limites des méthodes abordées.

Plan

1.       Rappels

• a.       Ensembles convexes, fonctions convexes
• b.      Programmation linéaire
• c.       Dualité, multiplicateur de Lagrange, conditions de Karush-Kuhn-Tucker

2.       Idées générales : Algorithmes, oracles et complexité

• a.       Quelques exemples : Pourquoi la convexité est-elle si importante ?
• b.      Notions d’oracle et de complexité d’un algorithme
• c.       Complexité : Comment obtenir des bornes supérieures et inférieures

3.       Méthodes géométriques

• a.       Méthode du centre de gravité
• b.      Méthode de l’ellipsoïde
• c.       Méthode des plans sécants

4.        Variations sur un thème de gradients

• a.       Descende de (sous) gradient : Idée générale, cas non contraint
• b.      Cas particuliers : Fonctions régulières  
• c.       Descente de gradient projeté : Cas contraint
• d.      Descente de coordonnées
• e.       Quelques autres méthodes (descente de mirroir, méthode de Frank-Wolfe, etc.)

5.       Pour aller plus loin…

• a.       Descente de gradient accélérée
• b.      Méthodes du second ordre
• c.       Fonctions non convexes : Que faire ?
• d.      Quelques mots sur l’optimisation robuste et l’optimisation stochastique