ENSAE: Optimisation.

Description

Ce cours introduit les résultats fondamentaux de l'optimisation convexe moderne. Il se concentre d'abord sur les questions de modélisation, pour couvrir dans un cadre simple les résultats fondamentaux de théorie de la dualité. Une attention particulière sera portée à la programmation sur les cônes symétriques, qui généralise les résultats de programmation linéaire aux problèmes quadratiques et semidéfinis. Le cours décrit ensuite les principaux algorithmes d'optimisation convexe, ainsi que des bornes sur leur complexité. Ces résultats seront illustrés par une présentation de plusieurs applications et expériences numériques dans des domaines comme les statistiques, l’économie et la finance, ou le traitement du signal.

Informations pratiques

• Horaires: Les cours sont programmés du 13 janvier au 25 février 2014, le lundi de 11h00 à 13h00 et le mardi de 8h30 à 10h30.

• TD: Du 17 janvier au 28 mars, le vendredi de 8h30 à 10h30.

• Lieu: ENSAE.

Plan du cours

• Modélisation
  Ensembles, fonctions et programmes convexes.
  Rappels d'analyse convexe.
  Dualité.
  

• Applications
  Statistiques et apprentissage.
  Economie et finance.
  Traitement du signal.
  Combinatoire, relaxations convexes.
  

• Algorithmes
  Méthode de Newton.
  Méthodes de points intérieurs.
  Contraintes, barrières, complexité.
  Méthodes du premier ordre, optimisation stochastique.
  

Références

• Convex Optimization, S. Boyd and L. Vandenberghe, Cambridge University Press.

• Lectures on Modern Convex Optimization, A. Nemirovski and A. Ben-Tal, SIAM.

Notes

• Intro
  

• LP Intro
  

• Sets
  

• Functions
  

• Problems
  

• Duality
  

• Finance
  

• Networks
  

• Statistics
  

• Geometrical problems
  

• Newton's method
  

• First-order algorithms
  

TPs

Les exercices sont principalement extraits du livre de Boyd et Vandenberghe.

• TP1: Exercices 2.5, 2.8, 2.12, 4.8, 4.11

• TP2: Exemples 2.7, 2.8, 2.10-12, 2.25

• TP3: Exercices 2.16, 2.23, 2.24, 2.25

• TP4: Exemples 3.10, 3.11, 3.13, Exercices 3.13, 3.16, 3.21

• TP5: Exercices 3.22, 3.24, 3.36

• TP6: Examen intermédiaire

• TP7: Exemple 4.5 Exercices 4.1, 4.15, 4.18, 4.21

• TP8: Exercices 5.5, 5.3, 5.7, 5.11

• TP9: Exercices 5.12, 5.27, 6.3, 6.6

Examen