Memaksimalkan bentuk kuadrat semidefinite positif di atas simplex standar

Aug 20 2020

Saya mencoba untuk memaksimalkan bentuk kuadrat semidefinite positif di atas simplex standar.

Diberikan matriks semidefinit (Hessian) positif simetris $A \in \Bbb R^{d \times d}$ dan matriks $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}$$

dimana $z_i \in [0,1]$ adalah nilai probabilitas yang digunakan untuk memberi bobot secara proporsional pada setiap kolom $W$.

Saya mencoba memecahkan masalah ini dengan memanfaatkan fakta yang memberi kendala $z^\top z = 1$, itu $z$ yang memaksimalkan $z^\top W^\top A W z$ adalah vektor eigen pertama dari matriks $A$. Tapi saya tidak yakin apakah ini cara yang benar.

Terima kasih.

Jawaban

2 user7530 Aug 21 2020 at 01:48

Secara umum masalah Anda adalah QP non-konveks dengan kemungkinan banyak maksima lokal (pertimbangkan misalnya bahwa bahkan dalam kasus yang paling sederhana $W^TAW = I$, setiap sudut nontrivial dari simpleks adalah maksimum lokal).

Jika $n$ cukup kecil, menguji semuanya $2^n$set aktif pasti akan berfungsi. Saya tidak tahu solusi analitik untuk kendala spesifik Anda; teknik bercabang-dan-terikat mungkin bisa menyelesaikannya secara numerik dalam praktiknya.