Acquis d'apprentissage

Ce cours se veut une introduction générale aux concepts de base de l'optimisation numérique. Deux questions sont abordées : comment "caractériser" une solution d'un problème d'optimisation (conditions d'optimalités) et comment concevoir une méthode numérique pour la calculer.

Objectifs

L'objet de ce cours est le développement et l'étude d'algorithmes numériques de résolution de problèmes en optimisation non linéaire avec ou sans contraintes.

Contenu

Nous considérons des problèmes d'optimisation non linéaire avec ou sans contraintes, continus mais pas nécessairement convexes. La première et majeure partie du cours est consacrée au cas sans contraintes. Après avoir étudié la caractérisation de minima dans le cas générique (conditions d'optimalité), nous développons les principales idées des approches de recherche linéaire et de région de confiance pour globaliser des méthodes du premier et second ordre du type plus forte pente, Newton ou quasi-Newton. Nous abordons également les aspects de convergence et de comportement numérique. La seconde partie du cours traite du cas avec contraintes et dérive les conditions d'optimalité de Karush-Kuhn-Tucker. Elle présente une ébauche de quelques méthodes connues telles que la méthode de programmation séquentielle quadratique, la méthode du Lagrangien augmenté et la méthode des points intérieurs.

Table des matières

Introduction

Partie I : Optimisation sans contraintes
  A. Conditions d’optimalité
  B. Survol d’algorithmes
  C. Les méthodes de recherche linéaire
  D. Les méthodes de région de confiance
  E. Calcul des dérivées
  F. Problèmes aux moindres carrés
  G. Systèmes d’équations non linéaires

Partie II : Optimisation avec contraintes
  A. Conditions d’optimalité
  B. Survol de méthodes

Exercices

Les séances d'exercices sont données à raison de 1h30 par semaine.

Méthodes d'enseignement

Cours magistral pour la théorie et séances d'exercises pour sa mise en application. Ce cours est donné à raison de 2h00 par semaine.

Méthode d'évaluation

Formule : L'évaluation consiste en deux épreuves : la première porte sur la théorie et est orale, la seconde porte sur les exercices et se fait soit sous forme d'évaluation écrite sur ordinateur, soit sous forme d'un travail écrit présenté oralement.

Modalité : Chaque épreuve compte pour moitié et constitue une unité d'apprentissage. Au cours d'une même année, l'étudiant est dispensé de repasser l'évaluation d'une des deux parties si elle est réussie (10/20) et pour autant qu'il ait présenté les deux parties la première fois.

Sources, références et supports éventuels

Source : Numerical Optimization (second edition), Jorge Nocedal and Stephen J. Wright. Springer, New York, 2006.

Supports sous forme de slides fournis avant le cours.

Langue d'instruction