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

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

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.

• 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.

À 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

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.

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.

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).

• 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.