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

Références