표준 심플 렉스에 대해 양의 반정의 2 차 형식 최대화

Aug 20 2020

표준 심플 렉스에 대해 양의 반정의 2 차 형식을 최대화하려고합니다.

대칭 양의 반 정호 (헤 시안) 행렬이 주어지면 $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$. 그러나 이것이 올바른 방법인지 확실하지 않습니다.

감사합니다.

답변

2 user7530 Aug 21 2020 at 01:48

일반적으로 문제는 잠재적으로 로컬 최대 값이 많은 비 볼록 QP입니다 (예를 들어 가장 간단한 경우에도 $W^TAW = I$, 심플 렉스의 모든 중요하지 않은 모서리는 로컬 최대 값입니다).

만약 $n$ 충분히 작습니다. $2^n$활성 세트는 확실히 작동합니다. 나는 당신의 특정한 제약에 대한 분석적인 해결책을 모릅니다. 브랜치 앤 바운드 기술은 실제로 수치 적으로 해결할 수 있습니다.