Matrice SDP complexe et valeur propre max

Soit $v_1,\cdots,v_k \in \mathbb{C}^n,$ avec $||v_i||=1$ pour $1\leq i\leq k$ une discrétisation de la $n$-sphère de $\mathbb{C}^n$.

Dans une certaine optimisation, je dois travailler avec une variable $W$ qui est une matrice SDP complexe de taille $n$ pour laquelle j'aimerais approximer linéairement (en m'appuyant sur l'opérateur Trace) la valeur propre maximale notée $\lambda_{W,\text{max}}$.

Puisque $\lambda_{W,\text{max}}=\max\limits_{v\in\mathbb{C}^n,\ ||v||=1} v^HWv$ (non linéaire en $W$), mon idée est d'approximer cette vp maximale de $W$ par :
$\max\limits_{1\leq i \leq k} v_i^HWv_i$ qui peut s'exprimer linéairement en programmation SDP.

Ma question est la suivante : puisque les $v_i$ sont connus, existe-t-il un moyen (analytique ou algorithmique) de trouver, avant de résoudre le problème d'optimisation qui m'intéresse vraiment, la matrice complexe SDP $W$ qui maximise
$$
\dfrac{\lambda_{W,\text{max}}}{\max_{1\leq i \leq k} v_i^HWv_i},

$$ ainsi que la valeur de ce ratio maximal ?

Note 1 : dans mon cas particulier, il serait suffisant de ne considérer que des matrices $W$ de rang 1 : je ne suis pas sûr que cela simplifie l'analyse mais si c'est le cas profitons-en.

Note 2 : ce ratio permettrait de connaître à l'avance de combien cette discrétisation de la $n$-sphère peut rater la valeur réelle de la plus grande valeur propre (ça quantifierait l'approximation que je propose).
Merci !!

[SDP = symétrique définie positive. AD]

Réponses

  • Qu'est-ce qui te fait penser qu'il existe une matrice qui maximise cette quantité ? Les matrices SDP ne forment pas un compact.
  • SDP complexe =HDP ?
  • Merci pour cette réponse qui m'a sorti la tête du guidon. Je n'ai pas fini ma démo de coin de table mais on doit en effet pouvoir conjecturer que pour tout $\alpha \in \mathbb{R}^+$ on pourra trouver/construire une matrice complexe SDP telle que le ratio que je cherche à maximiser est strictement supérieur à $\alpha$ en exploitant le fait qu'en l'état du problème posé on a accès à l'intégralité de l'espace des matrices complexes SDP.

    Je propose de mieux borner l'exercice (tout en conservant l'intérêt applicatif de mon côté) en considérant pour espace de recherche de W l'ensemble des matrices complexes SDP de rang 1 et dont l'unique valeur propre vaut 1.

    En exploitant le fait qu'une telle matrice peut s'écrire $W=ww^H$ avec $w \in \mathbb{C}^n$ et $||w|| = 1$, il me semble que le problème résultant peut s'exprimer comme un programme quadratique (linéaire sur l'objectif) contraint quadratiquement, mais qu'il a le mauvais goût d'être non-convexe à cause de la contrainte de normalisation du vecteur ||w||. Je crains que ça annihile tout espoir de résolution analytique mais aussi de résolution algorithmique exacte... Qu'en pensez-vous ?
  • Vous êtes sûr que ce n’est pas plutôt DSP = De Seguin Pazzis au lieu de SDP = Seguin De Pazzis.
  • Pas sûr de savoir si c'est de l'ironie, mais SDP = symétrique définie positive. La question de Math Coss était légitime puisqu'ici "symétrique" a pour signification hermitienne (c'est-à-dire symétrique pour le produit hermitien usuel).
  • Ai-je bien compris? Si $S$ est la sphere unite de l'espace hermitien de dimension $n$ tu te donnes une poussiere de vecteurs $ v_i$ de $S$ et tu cherches
    $$\min_{w\in S}\max_i (\langle v_i,w\rangle^2)?$$ C' est assez evident, non? Aussi je ne comprends pas pourquoi tu dis qu'on peut se ramener aux matrices $W$ de rang 1.
Connectez-vous ou Inscrivez-vous pour répondre.