Demystifying the characterization of SDP matrices in mathematical programming

EasyChair Preprint 2530

Abstract

Cette communication s'adresse aux chercheurs (en programmation linéaire (en nombre
entiers), meta-heuristiques ou d'autres branches de la RO) qui voudraient élargir leurs connaissances pour utiliser des techniques d'optimisation sémi-définie positive (SDP)
dans leur travaux. Plus exactement, je présente un travail d'environ 100 pages qui permettra au lecteur d'acquérir les bases de ce domaine. J'ai réalisé ce travail principalement parce que je n'ai pas trouvé d'autre introduction à l'optimisation SDP qui cible le même public (voir Section 2).

Le manuscrit proposé devrait être accessible à tous ceux qui ne détestent pas les mathématiques, qui savent ce qu'est une dérivée et peuvent accepter sans preuve
des résultats très basiques comme $\det(AB)=\det(A)\det(B)$. Si vous êtes dans ce cas, je pense vous pouvez comprendre ce manuscrit sans acheter d'autres
livres. L'objectif primordial n'est pas de rappeler ou d'énumérer une liste de résultats, mais
de faire le lecteur examiner (les preuves de) ces résultats, pour qu'il puisse développer une compréhension profonde du sujet.

Pour se lancer dans l'optimisation SDP, on pourrait naturellement être tenté de commencer par un livre consacré ou un « handbook of SDP ... ». Mais si le lecteur ne possède pas déjà des connaissances assez fraiches en mémoire sur les matrices SDP, je pense que cette voie,
 bien que basée sur d'excellentes intentions, risque d'être inaccessible.
Un pas crucial pour comprendre la programmation SDP est la  décomposition
d'une matrice SDP en éléments propres; c'est un concept que le néophyte ne devrait pas
prendre à la légère, c.à.d, une lecture rapide d'attention moyenne serait insuffisante.
Il suffit de regarder comment ces livres$/$handbooks présentent cette décomposition pour comprendre qu'ils ciblent un public tout simplement très différent (voir des détails en Section 2).

Keyphrases: Optimisation combinatoire, décompositions de matrices, optimisation SDP

@booklet{EasyChair:2530,
  author    = {Daniel Porumbel},
  title     = {Demystifying the characterization of SDP matrices in mathematical programming},
  howpublished = {EasyChair Preprint 2530},
  year      = {EasyChair, 2020}}