Optimization models and methods [ LINMA2471 ]

Les documents du cours (notes, transparents, énoncés des exercices et des devoirs) sont disponibles sur iCampus.

Ce cours suppose le suivi au préalable d'un cours de base en optimisation (tel que  le cours INMA1702) ainsi que certaines notions élémentaires d'analyse réelle et d'algèbre linéaire.

Optimisation linéaire, optimisation convexe (y compris l'optimisation structurée conique) ; dualité et applications ; méthodes de point intérieur ; méthodes du premier ordre, méthodes de région de confiance ; pratique d'un langage de modélisation.

À l'issue de ce cours, l'étudiant sera en mesure de :

• Reconnaître un problème pouvant être formulé ou converti sous forme linéaire, convexe, ou conique
• Exploiter le concept de dualité pour la compréhension d'un problème, la production de certificats d'optimalité ou d'impossibilité, pour l'analyse de sensibilité ou la formulation de problèmes robustes
• Décrire, analyser et Implémenter des algorithmes de résolution avancés dans les domaines de l'optimisation linéaire, convexe ou non-linéaire
• Utiliser un langage de modélisation pour formuler et résoudre un problème d'optimisation, en exploitant la séparation entre modèle, données et algorithme de résolution
• 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 et par écrit sur base des objectifs énoncés plus haut. En outre les étudiants réalisent une série de devoirs par petits groupes, comptabilisés dans la note finale.

Le cours est organisé autour de séances de cours, de séances d'exercices supervisées et de laboratoires en salle informatique (pour la pratique du langage AMPL). 

Modèles : Techniques avancées de modélisation linéaire et convexe ; théorèmes de l'alternative et dualité linéaires et convexes ; analyse de sensibilité et optimisation robuste ;  optimisation conique (programmations linéaire, conique quadratique et sémidéfinie), dualité Lagrangienne
Méthodes : méthode de point intérieur pour l'optimisation linéaire (suivi de chemin à pas courts et à pas longs) et pour l'optimisation convexe (barrières auto-concordantes), méthodes du premier ordre pour l'optimisation convexe, étude de la complexité algorithmique ; méthode de région de confiance ; découverte et utilisation du langage de modélisation AMPL.
Applications traitées dans des domaines variés tels que l'analyse de données, le machine learning, la finance, l'optimisation de formes ou de structures mécaniques, ou les télécommuncations.

• Convex Optimization, Stephen Boyd et Lieven Vandenberghe, Cambridge University Press, 2004.
• Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, Aharon Ben-Tal, Arkadi Nemirovski, SIAM 2001.
• Interior point methods for linear optimization, Cornelis Roos, Tamas Terlaky, Jean-Philippe Vial, Springer, 2006.
• Introductory Lectures on Convex Optimization: A Basic Course, Yurii Nesterov, Kluwer, 2004.
• Trust-region methods, A. Andrew R. Conn, Nicholas I. M. Gould, Ph. Philippe L. Toint, SIAM, 2000.