Calcul différentiel, Algèbre linéaire, probabilités élémentaires. Idéalement programmation linéaire et introduction à l'optimisation (e.g. cours Optimisation de première année).

Le module d'optimisation convexe aura pour but de présenter les algorithmes classiques et plus récents de l'optimisation non linéaire. Les outils et méthodes développées dans ce module trouvent des applications dans l'industrie mais également au service d'autres domaines scientifiques comme l'apprentissage automatique ou l'analyse numérique, dont certaines seront traitées en exemple.

À l'issue du module les élèves sauront :

- modéliser un problème réel comme un problème d'optimisation

- identifier à quelle classe de problème d'optimisation appartient un problème

- proposer une méthode de résolution et évaluer la solution obtenue

- implémenter un algorithme d'optimisation à direction de descente

Partie 1 : Programmation Dynamique (1 séance - 1 projet)

Nous présentons l'outil flexible de la programmation dynamique pour la gestion de chaîne de Markov. L'un des exemples d'applications les plus courants est le problème de gestion de stock.

Cette partie ne comporte qu'une séance en présentiel mais est complété par un projet en binôme à rendre à la fin du cours et de temps de support dédié par les enseignants. Le projet propose de chercher une stratégie optimale de jeu de société. Il s'agit ainsi de s'attaquer à un problème bien défini mais complexe qui demandera de faire des hypothèses simplificatrices.

Partie 2 : Analyse Convexe (4 séances - 2 DM)

Nous présentons les outils basiques de l'analyse convexe qui nous permettent d'arriver aux conditions d'optimalité du premier ordre (dit de Karush-Kuhn-Tucker) pour un problème d'optimisation différentiable. Nous étudions ensuite le concept de problème dual et appliquons cela aux problèmes conique du second ordre (SOCP).

Partie 3 : Algorithmes du XXème siècle (3 séances - 1 TP)

Nous présentons le principe des algorithmes d'optimisation à direction de descente en exposant les plus classiques : algorithme du gradient, gradient conjugué, Newton, quasi-Newton. Ces algorithmes sont aujourd'hui utilisés dans de nombreux codes informatiques avec lesquels de futurs ingénieurs peuvent avoir à interagir.

L'étude théorique des algorithmes est complétée d'une mise en pratique par un TP informatique noté.

Partie 4 : Algorithmes du XXIème siècle (3 séances)

Dans cette dernière partie nous présentons des méthodes plus récentes. Nous verrons le principe de la méthode des points intérieurs, une des méthodes phares pour l'optimisation linéaire et plus largement conique. Nous terminons par une introduction à l'algorithme du gradient stochastique, qui est l'algorithme utilisé pour entraîner les méthodes d'apprentissage statistique.

Le cours se déroule sur 13 séances de 2.5 heures dont :

- 9 séances de cours magistral

- 2 séances de TD

- 1 séance de TP informatique

- 1 devoir surveillé

En complément :

- 2 DM (court) pour pratiquer les outils théoriques (travail personnel prévu : 2x 4h)

- 1 projet en binôme avec des " class-hours " dédiées pour aider les élèves (travail personnel : 20h)

L'évaluation du module repose sur:

- le projet en binôme (25%)

- les DM (15%)

- le TP (10%)

- le devoir final (50%)

La validation nécessitera d'avoir au moins 8/20 au devoir final.

Convex Optimization, S. Boyd and L. Vandenberghe