Maximizar una forma cuadrática semidefinida positiva sobre el simplex estándar

Question

Estoy intentando maximizar una forma cuadrática semidefinida positiva sobre el simplex estándar.

Dada una matriz semidefinita (hessiana) positiva simétrica $A \in \Bbb R^{d \times d}$ y una matriz $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}$$

dónde $z_i \in [0,1]$ es un valor de probabilidad utilizado para ponderar proporcionalmente cada columna de $W$.

Traté de resolver este problema utilizando el hecho de que dada una restricción $z^\top z = 1$, la $z$ que maximiza $z^\top W^\top A W z$ es el primer vector propio de la matriz $A$. Pero no estoy seguro de si esta es la forma correcta.

Gracias.

Answer 1

En general, su problema es un QP no convexo con potencialmente muchos máximos locales (considere, por ejemplo, que incluso en el caso más simple $W^TAW = I$, cada esquina no trivial del símplex es un máximo local).

Si $n$ es lo suficientemente pequeño, probando todos $2^n$los conjuntos activos definitivamente funcionarán. No conozco una solución analítica para sus limitaciones específicas; Las técnicas de ramificación y vinculación podrían resolverlo numéricamente en la práctica.