標準シンプレックスよりも正の半定値二次形式を最大化する

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

一般に、問題は潜在的に多くの極大値を持つ非凸QPです（たとえば、最も単純な場合でもそれを考慮してください） $W^TAW = I$、シンプレックスの重要なコーナーはすべて極大値です）。

場合 $n$ 十分に小さいので、すべてをテストします $2^n$アクティブセットは間違いなく機能します。私はあなたの特定の制約に対する分析的な解決策を知りません。分枝限定法は、実際にはそれを数値的に解くことができるかもしれません。