Maximisation d'une forme quadratique semi-définie positive sur le simplexe standard
J'essaie de maximiser une forme quadratique semi-définie positive sur le simplexe standard.
Étant donné une matrice semi-définie symétrique positive (Hesse) $A \in \Bbb R^{d \times d}$ et une matrice $W \in \Bbb R^{d \times n}$,
$$\begin{array}{ll} \underset{z \in \Bbb R^n}{\text{maximize}} & z^\top W^\top A W z\\ \text{subject to} & \Bbb 1_n^\top z = 1\\ & z \geq \Bbb 0_n\end{array}$$
où $z_i \in [0,1]$ est une valeur de probabilité utilisée pour pondérer proportionnellement chaque colonne de $W$.
J'ai essayé de résoudre ce problème en utilisant le fait que, étant donné une contrainte $z^\top z = 1$, la $z$ qui maximise $z^\top W^\top A W z$ est le premier vecteur propre de la matrice $A$. Mais je ne suis pas sûr que ce soit la bonne manière.
Je vous remercie.
Réponses
En général, votre problème est un QP non convexe avec potentiellement de nombreux maxima locaux (considérez par exemple que même dans le cas le plus simple $W^TAW = I$, chaque coin non trivial du simplexe est un maximum local).
Si $n$ est suffisamment petit, testant tout $2^n$les ensembles actifs fonctionneront certainement. Je ne connais pas de solution analytique pour vos contraintes spécifiques; des techniques de branchement et de délimitation pourraient permettre de le résoudre numériquement dans la pratique.