Optimisation Différentiable

Objectif

L'optimisation est la discipline qui étudient les problèmes dans lesquels on cherche à déterminer «au mieux» des variables, qui sont contraintes d'appartenir à un ensemble donné; déterminer «au mieux» signifie que l'on cherche à minimiser ou maximiser un critère fonctionnel dépendant de ces variables. Ce cours présente les concepts, méthodes et algorithmes principaux de l'optimisation en dimension finie. L'optimisation repose sur l'analyse convexe, si bien que le cours décrit quelques notions et démontre quelques résultats de cette branche importante des mathématiques, située entre l'algèbre linéaire et l'analyse non  linéaire.

Mode d'évaluation:

La note finale du cours sera la moyenne de la note de contrôle continu (50%) et de l'examen final (50%). La note de contrôle continue est égale à la moyenne de la note de participation et de la note de mi-parcours. La note de participation est la moyenne de la note de présence et de la note de participation aux TD, laissée à la l'appreciation du chargé de TD.

A l’issue de ce cours, les étudiants doivent être capable de

• calculer des gradients et des hessiennes de fonctions de plusieures variables,
• déterminer les points extrémaux d’une fonction de plusieures variables et identifier leur nature grace à la hessienne,
•  déterminer les conditions KKT et savoir les résoudre pour les problèmes d’optimisation sous contraintes,
• déterminer le problème dual d’un problème d’optimisation convexe différentiable et de s’en servir pour résoudre KKT, 
• démontrer la qualification de contrainte.
• savoir construire un algorithme de descente de gradient pour résoudre un problème d’optimisation.

Plan

Le cours est structuré comme suit.

1.      Introduction aux problèmes d'optimisation, existence et unicité de solution, caractérisation de la convexité d'une fonction par ses dérivées.
 2. Cône tangent, condition d'optimalité de Kantorovitch, opérations sur les ensembles convexes (projection sur un convexe, séparation des convexes, cône dual et lemme de Farkas).
 3. Conditions d'optimalité des problèmes avec contraintes d'égalité : qualification de contraintes, conditions de Lagrange, conditions du second ordre.
 4. Conditions d'optimalité des problèmes avec contraintes d'inégalité : qualification des contraintes et conditions de Karush, Kuhn et Tucker.
 5. Algorithmes de descente sans contrainte: recherche linéaire et régions de confiance.
 6. Algorithmes newtoniens et quasi-newtoniens pour les systèmes d'équations et l'optimisation sans contrainte.
 7. Pénalisation (extérieure et intérieure), lagrangien augmenté.
 8. Optimisation quadratique successive: l'algorithme local et sa globalisation par pénalisation exacte.
 9. Dualité: dualité minmax, dualisation de contraintes fonctionnelles par le lagrangien et le lagrangien augmenté, algorithmes associés.
10. Optimisation linéaire: théorie, algorithme du simplexe, algorithmes de points intérieurs.
11. Conjugaison: enveloppe convexe fermée, fonction conjuguée.
12. Sous-différentiabilité: dérivabilité directionnelles des fonctions convexes, sous-différentiabilité des fonctions convexes ; applications: sous-différentiabilité de la fonction valeur, interprétation marginaliste des multiplicateurs.

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.