Modèles et méthodes d'optimisation I

https://moodleucl.uclouvain.be/course/view.php?id=9200

Ce cours suppose acquises les notions élémentaires d'analyse réelle et d'algèbre linéaire (cours LFSAB1101 et LFSAB1102), 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.

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

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.