Programmé en UVF2RMRIR101, MR2AMRIR701, MR2ARIR101
Présentation :
Responsable : Rumen Andonov (randonov@irisa.fr)
Équipe pédagogique : Rumen Andonov, Dietmar Berwanger, Éric Fabre, Sophie Pinchinat
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.
Pré-requis :
Algèbre linéaire, théorie des graphes, notions de base en complexité des algorithmes.
Liens :
http://master.irisa.fr/master/live/modules/tc3_fr.html
Volume horaire :
20h
Contenu détaillé :
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)
Année 2016/2017
Dernière mise à jour le 08-FEB-16
Validation par le responsable de programme le
|
