Optimisation conique

Cours MPRO de programmation mathémathique

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.

• 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 œuvre 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.