Une classe de problèmes d'optimisation convexe où un objectif linéaire est minimisé ou maximisé sous des contraintes affines et une variable matricielle symétrique contrainte à être semi-définie positive.

Principe

Remplacer des contraintes matricielles non convexes par le cône convexe des matrices semi-définies positives ; exprimer des inégalités matricielles linéaires et des objectifs linéaires pour obtenir un problème résoluble par méthodes intérieures ou méthodes convexes du premier ordre.

Démonstration

Minimiser trace(CX) sous contraintes trace(A_i X) = b_i pour i = 1..m et X >= 0 (X semi-définie positive) ; cette formulation capture des relaxations de problèmes combinatoires et des problèmes de conception en commande et traitement du signal.

Mauvaise application

Considérer des relaxations SDP comme des solutions exactes sans vérifier les conditions de rang ou d'intégralité peut conduire à des conclusions trop optimistes ; utiliser des solveurs SDP denses pour des problèmes creux et très grands sans exploiter la structure rend le calcul impraticable.

Conséquence

Bien utilisée, la SDP fournit des relaxations convexes serrées pour de nombreux problèmes difficiles, permet une résolubilité en temps polynomial au sens des méthodes intérieures et fournit des certificats d'optimalité ou d'infaisabilité via les solutions duales.

Inversion

L'inversion consiste à restreindre au programme linéaire en imposant des matrices diagonales ou en supprimant les contraintes PSD, ce qui simplifie le calcul mais fait perdre la capacité à modéliser corrélations et formes quadratiques.

Limite

S'applique aux problèmes exprimables par des inégalités matricielles linéaires et des variables matricielles PSD symétriques ; exclut les objectifs ou contraintes intrinsèquement non convexes et les cas où des contraintes entières sont obligatoires sans relaxation.

Tension sémantique

Tension entre la précision de la solution (qualité de la relaxation SDP) et la faisabilité numérique (taille et exploitation de la parcimonie), et entre solveurs intérieurs denses (haute précision) et méthodes du premier ordre (scalabilité mais garanties de terminaison plus faibles).

Synthèse

La programmation semi-définie formule des problèmes avec variables matricielles et contraintes PSD comme des programmes convexes : objectifs linéaires et inégalités matricielles linéaires définissent un problème de cône convexe conciliant expressivité de modélisation et complexité algorithmique.