2023-2024 / MATH0461-2

Introduction to numerical optimization

Durée

30h Th, 20h Pr, 25h Proj.

Nombre de crédits

 Master en science des données, à finalité5 crédits 
 Master : ingénieur civil électricien, à finalité5 crédits 
 Master : ingénieur civil en génie de l'énergie, à finalité5 crédits 
 Master : ingénieur civil électromécanicien, à finalité5 crédits 
 Master : ingénieur civil en informatique, à finalité5 crédits 
 Master : ingénieur civil en science des données, à finalité5 crédits 
 Master en sciences informatiques, à finalité5 crédits 
 Master : ingénieur civil physicien, à finalité5 crédits 
 Master en sciences mathématiques, à finalité6 crédits 
 Master en sciences mathématiques6 crédits 

Enseignant

Quentin Louveaux

Langue(s) de l'unité d'enseignement

Langue anglaise

Organisation et évaluation

Enseignement au premier quadrimestre, examen en janvier

Horaire

Horaire en ligne

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)
Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, II.2, III.1, III.2, III.3, III.4, IV.1, VI.1, VI.2, VI.3, VII.2, VII.3, VII.4, VII.5 du programme d'ingénieur civil en génie biomédical.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, II.2, III.1, III.2, III.3, III.4, IV.1, IV.4, VI.1, VI.2, VI.3, VII.2, VII.3, VII.4, VII.5 du programme d'ingénieur civil en science des données.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, II.2, III.1, III.2, III.3, III.4, IV.1, VI.1, VI.2, VI.3, VII.2, VII.3, VII.4, VII.5 du programme d'ingénieur civil électricien.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, II.2, III.1, III.2, III.3, III.4, IV.1, IV.3, VI.1, VI.2, VI.3, VII.2, VII.3, VII.4, VII.5 du programme d'ingénieur civil en informatique.

Ce cours contribue aux acquis d'apprentissage I.1, I.2, II.1, II.2, III.1, III.2, III.2, III.3, III.3, III.4, IV.1, VI.1, VI.2, VI.3, VII.2, VII.3, VII.4, VII.5 du programme d'ingénieur civil physicien.

 

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 est demandé.

Mode d'enseignement (présentiel, à distance, hybride)

Cours donné exclusivement en présentiel


Explications complémentaires:

Le cours est donné en présentiel.

Lectures recommandées ou obligatoires et notes de cours

D. Bertsimas, J. Tsistsiklis. Introduction to linear optimization, Dynamic Ideas, 1997.
S. Boyd, L. Vandenberghe. Convex Optimization, 2004.

Modalités d'évaluation et critères

Examen(s) en session

Toutes sessions confondues

- En présentiel

évaluation écrite ( questions ouvertes )

Travail à rendre - rapport


Explications complémentaires:

L'examen est un examen écrit.

Il comportera une question de théorie incluant des vrais ou faux avec justification, ainsi que des questions d'exercices similaires aux séances pendant l'année.

Pour la note finale, la note de l'examen compte pour 2/3 et la note de projet compte pour 1/3. Dans le cas où c'est plus avantageux pour l'étudiant, la note de l'examen peut compter pour l'entièreté de la note.

Le projet doit être présenté en première session dans la période prévue à cet effet. Il n'y a pas de possibilité de représenter le projet à un autre moment.

Stage(s)

Remarques organisationnelles et modifications principales apportées au cours

Le cours est donné en anglais.

Tous les documents relatifs au cours sont disponibles sur ecampus.

 

Contacts

Le professeur est Quentin Louveaux q.louveaux@uliege.be

Les assistants sont Adrien Bolland adrien.bolland@uliege.be et Laurie Boveroux Laurie.Boveroux@uliege.be

 

Association d'un ou plusieurs MOOCs