 | editer cette page |
Optimisation numérique et combinatoire (OPT)
Responsable :
Rumen Andonov
Équipe pédagogique : Rumen Andonov, Dietmar Berwanger, Éric Fabre, Sophie Pinchinat
Description
Les problèmes d'optimisation apparaissent dès que l'on doit choisir entre plusieurs solutions à un problème, et qu'il s'agit de choisir la meilleure. Une formulation aussi vague souligne en fait que les problèmes d'optimisation apparaissent sous des formes très diverses. Par exemple approcher un nuage de points de mesure par une droite ou une courbe, résoudre au mieux un système linéaire sur-contraint, trouver la meilleure correspondance entre deux image similaires, maximiser le débit dans un réseau, etc. D'autres problèmes sont de nature plus combinatoire, comme trouver le meilleur alignement de deux graphes, trouver le meilleur chemin dans un graphe, optimiser une stratégie de jeu, etc. Enfin, certains problèmes impliquent plusieurs "joueurs" ou "agents" qui coopèrent pour résoudre au mieux une tâche, ou au contraire ont des objectifs différents et sont en concurrence, ce qui ouvre une fenêtre vers la théorie des jeux.
L'objectif de ce module est de procurer aux étudiants une culture générale en optimisation, en présentant les problèmes classiques, leur complexité et les méthodes à mettre en oeuvre pour les résoudre.
Pré-requis : algèbre linéaire, théorie des graphes, notions de base en complexité des algorithmes
Structure générale et contenu
- Partie 1 (10h)
- Introduction
- classification des méthodes d'optimisation
- cas continu : caractérisation d'un optimum, choix de la fonction objectif, importance des problèmes convexes
- exemple : moindres carrés
- rappel sur les développements de Taylor
- Optimisation en domaine continu : méthodes du premier ordre
- recherches linéaires
- méthode du gradient
- Optimisation en domaine continu : méthodes du second ordre
- méthode de Newton
- gradient conjugué
- Optimisation sous contrainte
- contraintes linéaires
- multiplicateurs de Lagrange
- relaxation
- caractérisation d'un optimum
- Dualité
- résolution par passage au dual
- problèmes min-max, point selle
- notions d'équilibre (Nash)
- Partie 2 (10h)
- Théorie des polyèdres
- description par facettes, rayons, et points maximaux
- lemme de Farkas
- liens polyédriques entre programmation linéaire et programmation en nombres entiers
- méthode d'élimination de Fourrier-Motzkin
- Programmation linéaire
- simplexe
- application aux problèmes de flot max/coupe min
- traduction de l'implication logique en contraintes linéaires
- Algorithmes généraux de résolution exacte
- méthode "branch and bound"
- utilisation de relaxation LP/lagrangienne
- programmation dynamique
- NP complétude et approximation
- arbre de Steiner
- heuristiques
- introduction à l'optimisation multi-objective (frontière de Pareto)
- Nemhauser G., Wolsey L. Integer and combinatorial optimization. John Willey & Son, 1999
- Culioli J.-C. Introduction à l’optimisation. coll Ellipses, 1994
-
Automata, logics, and infinite games. Chap. 2 Infinite games. Eds : Grädel E., Thomas W., Wilke T., Springer-Verlag, LNCS, Vol 2500, 2002
Documents de cours
- Partie É. Fabre
- Partie R. Andonov
- Partie S. Pinchinat