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]
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]
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
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 ?
$$\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.