<- Archives UCL - Programme d'études ->



Modèles et méthodes d'optimisation I [ LINMA1702 ]


5.0 crédits ECTS  30.0 h + 22.5 h   2q 

Enseignant(s) Glineur François (supplée Blondel Vincent) ; Blondel Vincent ; Glineur François (coordinateur) ;
Langue
d'enseignement:
Français
Lieu de l'activité Louvain-la-Neuve
Ressources
en ligne

Les documents du cours (transparents, énoncés des exercices et du projet, anciens examens) sont disponibles sur iCampus.

Préalables

Ce cours suppose acquises les notions élémentaires d'analyse réelle et d'algèbre linéaire, et nécessite une maturité suffisante en mathématique, de niveau équivalent à celle d'un étudiant ingénieur arrivé au terme de sa première année d'étude.

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

À l'issue de ce cours, l'étudiant sera en mesure 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
  • rendre compte par écrit d'un travail de formulation, d'analye et/ou de résolution de modèles d'optimisation
Modes d'évaluation
des acquis des étudiants

Les étudiants sont évalués individuellement par écrit sur base des objectifs énoncés plus haut. En outre, les étudiants réalisent un projet donnant lieu à la rédaction d'un rapport, comptabilisé dans la note finale.

Méthodes d'enseignement

Le cours est organisé autour de séances de cours, de séances d'exercices et d'un laboratoire en salle informatique supervisés, et d'un projet à réaliser par petits groupes. Une consultance est offerte pour un soutien dans la réalisation du projet.

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 méthodes (gradients conjugués, problèmes avec contraintes, indisponibilité des dérivées).

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.
Cycle et année
d'étude
> Master [120] en statistiques, orientation générale
> Bachelier en information et communication
> Bachelier en philosophie
> Bachelier en sciences pharmaceutiques
> Bachelier en sciences informatiques
> Bachelier en sciences économiques et de gestion
> Bachelier en sciences de la motricité, orientation générale
> Bachelier en sciences humaines et sociales
> Bachelier en sociologie et anthropologie
> Bachelier en sciences politiques, orientation générale
> Bachelier en sciences mathématiques
> Bachelier en sciences biomédicales
> Bachelier en sciences de l'ingénieur, orientation ingénieur civil
> Bachelier en sciences religieuses
> Master [120] en sciences informatiques
> Master [120] : ingénieur civil en informatique
> Master [120] : ingénieur civil biomédical
> Master [120] : ingénieur civil physicien
> Master [120] : ingénieur civil électricien
> Master [120] : ingénieur civil en mathématiques appliquées
> Master [120] : ingénieur civil en chimie et science des matériaux
Faculté ou entité
en charge
> MAP


<<< Page précédente