Maximisation d'une forme quadratique semi-définie positive sur le simplexe standard

Aug 20 2020

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}$$

$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

2 user7530 Aug 21 2020 at 01:48

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.