Durée
30h Th, 20h Pr, 25h Proj.
Nombre de crédits
Enseignant
Langue(s) de l'unité d'enseignement
Langue anglaise
Organisation et évaluation
Enseignement au premier quadrimestre, examen en janvier
Horaire
Unités d'enseignement prérequises et corequises
Les unités prérequises ou corequises sont présentées au sein de chaque programme
Contenus de l'unité d'enseignement
Dans de nombreux problèmes de l'ingénieur, un grand nombre de décisions peuvent être prises, donnant lieu à des solutions de plus ou moins grande valeur. Une façon de décider de la meilleure solution à envisager est de modéliser mathématiquement les différentes variables de décision et d'ensuite choisir celles qui seront implémentées en optimisant une fonction mathématique.
Ce formalisme modélisant de nombreux problèmes réels est appelé programmation mathématique.
Dans un programme mathématique, on définit un ensemble de variables de décision, des contraintes sous forme d'égalités et d'inégalités déterminant l'ensemble des solutions réalisables du problème, et un objectif à optimiser.
En fonction des propriétés des fonctions présentes dans les contraintes et de la fonction objectif, on obtiendra un problème d'optimisation plus ou moins difficile à résoudre. Nous reviendrons sur les problèmes où toutes les contraintes et l'objectif sont linéaires (programmation linéaire). Nous étudierons les propriétés de ces problèmes et en particulier le concept de dualité. Nous verrons des problèmes non linéaires (coniques) qui conservent les bonnes propriétés de dualité. Finalement nous traiterons de problèmes non linéaires sans structure particulière.
Les concepts suivants sont abordés dans le cours.
- Algorithme du simplexe révisé
- Dualité pour la programmation linéaire
- Analyse post-optimale et algorithme du dual simplexe
- Introduction aux méthodes de point intérieur
- Conditions d'optimalité pour les problèmes non-linéaires
- Programmation conique et dualité
- Méthodes numériques pour l'optimisation non linéaire
Ce cours est donné en anglais.
Acquis d'apprentissage (objectifs d'apprentissage) de l'unité d'enseignement
A l'issue de ce cours, l'étudiant sera capable de
- formuler un problème réel en termes d'un modèle d'optimisation mathématique
- déterminer la complexité d'un problème d'optimisation et en particulier si celui-ci peut être résolu en temps polynomial
- écrire le dual d'un problème linéaire ou conique
- appliquer ou implémenter les principaux algorithmes d'optimisation (simplexe, dual simplexe, points intérieurs, descente de gradient, quasi-Newton)
Savoirs et compétences prérequis
Un cours de base en algèbre linéaire et en analyse. Des compétences de base en programmation sont également nécessaires.
Activités d'apprentissage prévues et méthodes d'enseignement
Des séances de répétitions en salle sont organisées à concurrence d'une vingtaine d'heures. Un travail de modélisation et de résolution d'un problème pratique à l'aide d'un logiciel de programmation linéaire et convexe est demandé.
Mode d'enseignement (présentiel, à distance, hybride)
Le cours est donné en présentiel.
Le nombre de places dans le local est suffisant pour accueillir avec une place sur deux de libre. Tous les cours sont également podcastés.
Adaptations organisationnelles liées au contexte sanitaire
Evaluation en présentiel possible:
Examen oral (théorie + exercices) avec préparation.
Evaluation à distance imposée par la situation sanitaire:
Examen oral en vidéoconférence (théorie + exercices) sans préparation
Lectures recommandées ou obligatoires et notes de cours
D. Bertsimas, J. Tsistsiklis. Introduction to linear optimization, Dynamic Ideas, 1997. M. Bierlaire. Introduction à l'optimisation différentiable. Presses polytechniques et universitaires romandes. 2006
Modalités d'évaluation et critères
Vous trouverez ci-dessous les modalités d'évaluation envisagées pour les examens en présentiel et à distance ainsi que celle souhaitée en cas de session hybride. En fonction de l'évolution sanitaire, la modalité choisie vous sera communiquée au plus tard un mois avant le début de la session d'examen.
L'examen est un examen oral de théorie et d'exercices.
Pour la note finale, la note de l'examen compte pour 2/3 et la note de projet compte pour 1/3.
Si le projet n'est pas présenté en première session, celui-ci doit être remis en seconde session (le même énoncé est valable).
L'absence de projet résulte en une note d'absence.
Stage(s)
Remarques organisationnelles
Le cours est donné en anglais.
Tous les documents relatifs au cours sont disponibles sur
https://dox.uliege.be/index.php/s/uv41XbH1cgFLyeC
Contacts
Le professeur est Quentin Louveaux q.louveaux@uliege.be
L'assistant est Mathias Berger mathias.berger@uliege.be