Modèles et méthodes d'optimisation I

linma1702  2019-2020  Louvain-la-Neuve

Modèles et méthodes d'optimisation I
Note du 29 juin 2020
Sans connaitre encore le temps que dureront les mesures de distances sociales liées à la pandémie de Covid-19, et quels que soient les changements qui ont dû être opérés dans l’évaluation de la session de juin 2020 par rapport à ce que prévoit la présente fiche descriptive, de nouvelles modalités d’évaluation des unités d’enseignement peuvent encore être adoptées par l’enseignant ; des précisions sur ces modalités ont été -ou seront-communiquées par les enseignant·es aux étudiant·es dans les plus brefs délais.
5 crédits
30.0 h + 22.5 h
Q2
Enseignants
Glineur François;
Langue
d'enseignement
Français
Préalables
Ce cours suppose acquises les notions élémentaires d'analyse réelle et d'algèbre linéaire telles qu'enseignées dans les cours LEPL1101, LEPL1102 et LEPL1105.
Thèmes abordés
  • Concepts de base et typologie des problèmes d'optimisation ; distinction entre aspects modèles et méthodes.
  • Optimisation linéaire : formulations, géométrie, algorithme du simplexe, dualité et optimisation discrète
  • Optimisation non-linéaire : conditions d'optimalité, convexité, méthodes de résolution et implémentation.
Acquis
d'apprentissage

A la fin de cette unité d’enseignement, l’étudiant est capable de :

1 Eu égard au référentiel AA, ce cours contribue au développement, à l'acquisition et à l'évaluation des acquis d'apprentissage suivants :
AA1.1, AA1.2, AA1.3
AA2.2, AA2.4, AA2.5
A5.3, AA5.4, AA5.5



Plus précisément, au terme du cours, l'étudiant sera capable de :
  • formuler une situation problème sous la forme d'un modèle d'optimisation
  • analyser un modèle d'optimisation, en particulier déterminer s'il est linéaire ou s'il est convexe,
  • caractériser les solutions optimales d'un modèle d'optimisation et, lorsque c'est possible, les calculer analytiquement (à l'aides des conditions d'optimalité), analyser leur sensibilité à l'aide de la dualité dans le cas linéaire
  • proposer de façon argumentée l'utilisation d'un algorithme de résolution, sur base du type de problème, de sa taille et des propriétés de convergence attendues,
  • implémenter un algorithme de résolution (algorithme du simplexe, méthode du premier ou du second ordre sans contraintes)
  • appliquer une implémentation ou un logiciel de résolution à des problèmes concrets, commenter et interpréter les résultats obtenus
Acquis d'apprentissage transversaux :
  • utiliser un logiciel de calcul numérique de type Matlab
  • effectuer en petit groupe un travail de formulation, d'analyse et/ou de résolution de modèles d'optimisation
  • rendre compte par écrit d'un travail de formulation, d'analyse et/ou de résolution de modèles d'optimisation
 

La contribution de cette UE au développement et à la maîtrise des compétences et acquis du (des) programme(s) est accessible à la fin de cette fiche, dans la partie « Programmes/formations proposant cette unité d’enseignement (UE) ».
Contenu
Optimisation linéaire :
Introduction, formes canoniques, géométrie des polyèdres, algorithme du simplexe, dualité et analyse de sensibilité, introduction à l'optimisation discrète (branch & bound).
Optimisation non-linéaire :
Modèles : définitions et terminologie, conditions d'optimalité pour problèmes sans et avec contraintes ; reconnaître et exploiter la convexité d'un problème.
Méthodes : méthodes de recherche en ligne pour problèmes sans contraintes (méthodes du gradient, de Newton et de quasi-Newton) ; propriétés de convergence (locale et globale) ; détails d'implémentation ; introduction à d'autres types méthodes.
Méthodes d'enseignement
Cet enseignement est organisé autour de séances de cours, de séances d'exercices et de laboratoires informatiques supervisés, ainsi que d'un projet à réaliser par petits groupes. Une consultance est offerte pour un soutien dans la réalisation du projet.
Modes d'évaluation
des acquis des étudiants
Les étudiants sont évalués individuellement lors d'un examen écrit sur base des objectifs énoncés plus haut. En outre, les étudiants réalisent un projet dont l'évaluation est comptabilisée dans la note finale.
Ressources
en ligne
Les documents du cours (transparents, notes, énoncés des exercices) sont disponibles sur Moodle : https://moodleucl.uclouvain.be/course/view.php?id=9200
Bibliographie
  • Introduction to Linear Optimization, Dimitri Bertsimas and John Tsitsiklis, Athena Scientific, 1997.
  • Linear Programming. Foundation and Extensions, Robert Vanderbei, Kluwer Academic Publishers, 1996.
  • Integer Programming, Laurence Wolsey, Wiley, 1998.
  • Numerical Optimization, Jorge Nocedal et Stephen J. Wright, Springer, 2006.
  • Convex Optimization, Stephen Boyd et Lieven Vandenberghe, Cambridge University Press, 2004.
Faculté ou entité
en charge
MAP


Programmes / formations proposant cette unité d'enseignement (UE)

Intitulé du programme
Sigle
Crédits
Prérequis
Acquis
d'apprentissage
Approfondissement en statistique et sciences des données

Approfondissement en sciences informatiques

Approfondissement en sciences mathématiques

Mineure en sciences de l'ingénieur : mathématiques appliquées (accessible uniquement pour réinscription)

Filière en Mathématiques Appliquées

Mineure en Mathématiques appliquées

Master [120] : ingénieur civil en informatique

Master [120] : ingénieur civil électricien

Master [120] en sciences informatiques

Master [120] : ingénieur civil en chimie et science des matériaux

Bachelier en sciences mathématiques

Master [120] en statistique, orientation générale