US331S

Optimisation conique


2 crédits Safia KEDAD SIDHOUM EPN05 - Informatique Unité spécifique de type cours

Publié Du 01-09-2024 au 31-08-9999

Prérequis

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.

Compétences

  • 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

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

Modalités de validation

  • Examen final

Thésaurus du Cnam :

  • Aucune indexation

Thésaurus Formacode :

  • Aucune indexation

Secrétariat

Libellé
Recherche opérationnelle
Nom du contact
Adresses email
secretariat.ro@cnam.fr
Numéros de téléphone
01 40 27 22 67
Adresse postale
2D4P20, 33-1-10, 2 rue Conté
Paris 75003