Максимизация положительной полуопределенной квадратичной формы над стандартным симплексом

Question

Я пытаюсь максимизировать положительную полуопределенную квадратичную форму над стандартным симплексом.

Для симметричной положительно полуопределенной (гессенской) матрицы $A \in \Bbb R^{d \times d}$ и матрица $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]$ - значение вероятности, используемое для пропорционального взвешивания каждого столбца $W$.

Я попытался решить эту проблему, используя тот факт, что с учетом ограничения $z^\top z = 1$, то $z$ что максимизирует $z^\top W^\top A W z$ - первый собственный вектор матрицы $A$. Но я не уверен, правильный ли это путь.

Спасибо.

Answer 1

В общем, ваша проблема - невыпуклый КП с потенциально большим количеством локальных максимумов (подумайте, например, что даже в простейшем случае $W^TAW = I$, каждый нетривиальный угол симплекса является локальным максимумом).

Если $n$ достаточно мал, тестируя все $2^n$активные наборы определенно подойдут. Я не знаю аналитического решения для ваших конкретных ограничений; Методы ветвей и границ могли бы решить эту проблему численно на практике.