Optimisation conique
Public Concerné
Cours MPRO de programmation mathémathique
Objectifs pédagogiques
Ce cours enseigne les fondements de l'optimisation conique, et notamment l'optimisation conique du second ordre et l'optimisation semi-définie (dualité et algorithmes de base). On y introduit également quelques bases de l'optimisation polynomiale. Le cours comporte également une partie pratique : modélisation en optimisation conique, implémentation et résolution avec des solveurs standards.
Capacité et compétences acquises
- Connaitre les fondements de l'optimisation conique,
- Connaitre les algorithmes de résolution de l'optimisation conique,
- Savoir modéliser par un problème d'optimisation conique,
- Savoir implémenter un modèle et le résoudre avec les solveurs existants.
Contenu de la formation
- Introduction à l'optimisation conique.
Nous introduisons le concept d'un cône convexe ainsi que son cône dual dont on établira les propriétés. Ensuite, nous présentons la programmation conique. Nous poursuivons en exposant la théorie de la dualité et notamment les conditions de Salter pour assurer une dualité forte. Enfin, nous présentons quelques exemples de cônes dont le cône des puissances et le cône exponentiel.
- Optimisation Semi-définie, Introduction, Dualité et Algorithmes de base.
Nous introduisons tout d'abord les fondements de l'optimisation semi-définie positive (SDP) : caractérisation des matrices SDP, inégalités matricielles linéaires, problème primal et dual, théorie de la dualité. Ensuite, nous présentons les algorithmes de résolution des problèmes d'optimisation semi-définie, ainsi qu'une mise en oeuvre pratique avec utilisation de solveurs standards.
- Optimisation Conique du Second Ordre, Introduction, Dualité, Algorithmes de base, Applications.
Nous commençons par définir le cône de second-ordre. Nous utilisons ensuite la dualité conique pour produire le dual d'un programme conique de second ordre (SOCP). Nous donnons plusieurs exemples de programmes SOCP qui se posent dans différents domaines. Enfin, nous présentons une spécialisation d'un algorithme de points intérieurs pour résoudre les SOCP.
- Introduction à l'optimisation polynomiale.
Nous commençons par introduire les polynômes et l'optimisation polynomiale. Ensuite, nous présentons quelques résultats liés à la nonnégativité des polynômes sur $R^n$ et sur des ensembles particuliers. Nous nous focalisons sur les sommes de carrés et nous montrons comment les introduire à travers la programmation semi-définie.
- Modélisation et résolution d'un problème d'optimisation conique.
En démarrant d'un problème classique d'optimisation quadratique, nous proposons deux relaxations coniques de ce problème. Nous implémentons ensuite leurs résolutions pour les comparer expérimentalement.
Description des modalités de validation
- Examen final
Prévisions d'ouverture
| Groupe | Semestre | Modalité | État d'ouverture | Date du premier cours | Lieux | ||
|---|---|---|---|---|---|---|---|
| US331S | Optimisation conique | 2 | Cours de Jour | - | - | - | - |
Voir les dates et horaires, les lieux d'enseignement et les modes d'inscription sur les sites internet des centres régionaux qui proposent cette formation
