Master M1 ENS. Optimisation convexe et combinatoire, première partie.

Description

Etude de la complexité de classes de problèmes convexes et d'algorithmes de performance optimale. Applications à l'approximation de problèmes combinatoires et en apprentissage statistique, imagerie, jeux, etc.

Thèmes abordés:
Algorithmes du premier ordre de performance optimale. Régularité et classes de complexité. Optimisation stochastique.
Régularisation déterministe et stochastique. Algorithmes de localisation, projections alternées, ellipsoïde, centre analytique.
Résolution d'inégalités variationelles. Approximation de problèmes combinatoires. Bornes d'approximations par méthodes probabilistes.
Applications à l'estimation parcimonieuse, au filtrage collaboratif (NETFLIX), à la sélection de covariance, aux jeux matriciels, à la reconstruction de molécules, etc.

Informations pratiques

  • Horaires: Jeudi, 9h15 - 12h15, salle R. Premier cours le 15 septembre 2016.

Organisation

Trois heures par cours.

  • Fondamentaux

    • Rappels de convexité et dualité

  • Complexité algorithmique

    • Méthodes de point intérieur, self-concordance

    • Méthodes du premier ordre, localisation

  • Applications récentes

    • Statistiques, apprentissage

    • Problèmes géométriques, graphes

    • etc.

  • Approximations, asymptotique, convexité cachée

    • Concentration de la mesure

    • S-lemma, MaxCut, solutions de rang faible pour SDP

    • Géométrie en grandes dimensions

    • Reconstruction l1, complétion de matrices, déconvolution convexe, etc.

Références

Notes

Exercices

Tous les exercices sont extraits du livre de Boyd et Vandenberghe.

  • DM1 pour le jeudi 27 octobre 2016 à 9h15.

Projets