Massimizzare una forma quadratica semidefinita positiva rispetto allo standard simplex

Question

Sto tentando di massimizzare una forma quadratica semidefinita positiva rispetto al simplex standard.

Data una matrice simmetrica semidefinita positiva (Hesse) $A \in \Bbb R^{d \times d}$ e una 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}$$

dove $z_i \in [0,1]$ è un valore di probabilità utilizzato per pesare proporzionalmente ogni colonna di $W$.

Ho provato a risolvere questo problema utilizzando il fatto che dato un vincolo $z^\top z = 1$, il $z$ che massimizza $z^\top W^\top A W z$ è il primo autovettore della matrice $A$. Ma non sono sicuro che sia la strada giusta.

Grazie.

Answer 1

In generale il tuo problema è un QP non convesso con potenzialmente molti massimi locali (considera ad esempio che anche nel caso più semplice $W^TAW = I$, ogni angolo non banale del simplex è un massimo locale).

Se $n$ è sufficientemente piccolo, testando tutto $2^n$i set attivi funzioneranno sicuramente. Non conosco una soluzione analitica per i tuoi vincoli specifici; le tecniche branch-and-bound potrebbero essere in grado di risolverlo numericamente nella pratica.