Optimisation Conique (OPCO)

dernière modif : le 18/12/2023 à 18:40:09
Titre :
Optimisation Conique (OPCO)
Section :
Optionnel
État pour cette année :
OPEN
Mots clés :
Optimisation Conique, Optimisation Semi-définie, Optimisation Conique du Second-Ordre, Optimisation Polynomiale.
Ects :
2
Responsable :
Walid Ben-Ameur (TELECOM SudParis)
Intervenants :
Walid Ben-Ameur (TELECOM SudParis)
Amélie Lambert (CNAM/CEDRIC)
Prérequis :

Cours MPRO PM1 et PM2

Objectif :

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.

Contenu / Plan :

  • (W. Ben-Ameur) 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.

  • (A. Lambert) 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.

  • (W. Ben-Ameur) 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.

  • (W. Ben-Ameur) 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.

  • (A. Lambert) TP : 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.

  • Examen

Bibliographie :

  • H. Wolkowicz, R. Saigal, L. Vandenberghe, Handbook of semidefinite programming, Theory, Algorithms, and applications, Kluwer, Dordrecht, 2000.

  • A. Nemirovski. Advances in convex optimization: Conic programming. In Marta Sanz-Sol, Javier Soria, Juan L. Varona, and Joan Verdera, editors, Proceedings of International Congress of Mathematicians, Madrid, August 22-30, 2006, Volume 1, pages 413 to 444. EMS - European Mathematical Society Publishing House, 2007.

  • C. Coey, M. Lubin, J-P. Vielma, Outer approximation with conic certificates for mixed-integer convex problems, Math. Program. Comput. Vol 12, page 249--293, 2020.

  • A. Ben-Tal, A. Nemirovski, Lectures on Modern Convex Optimization, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001.

  • S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

  • J-B. Lasserre, Moments, positive polynomials and their applications, Imperial College Press.

Liens :
(aucun)
Compétences visées :

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

Modalités de contrôle :

Examen écrit