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.

 

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.