Maximieren $\mathbf{x}^T A \mathbf{x}$ vorbehaltlich $| \mathbf{x} | \preceq \mathbf{1}$

Question

Ich versuche, ein Maximum an quadratischer Funktion zu finden, das oben / unten begrenzt ist. Das Problem wird wie folgt formuliert

\begin{align} &\underset{\mathbf{x}}{\max}~\mathbf{x}^T \mathbf{A} \mathbf{x} \label{eq:16a} \\ &\text{s.t.}\, \left. \begin{array}{l} |\mathbf{x}| \preceq \mathbf{1} \end{array} \right. \label{eq:16b} \end{align} wo $\mathbf{A}$ ist positiv semi-definit.

Der Lagrange dieser Funktion ist \ begin {Gleichung} \ mathcal {L} = \ mathbf {x} ^ T \ mathbf {A} \ mathbf {x} + {\ lambda} _- ^ T (\ mathbf {x} + \ mathbf {1}) - \ lambda _ + ^ T (\ mathbf {x} - \ mathbf {1}), \ end {Gleichung} wobei${\lambda}_-^T$ und ${\lambda}_+^T$sind Lagrange-Multiplikatoren. Ich habe Probleme damit, das Optimum zu finden$\mathbf{x}^*$Maximierung des Ziels. Vielen Dank!

Answer 1

Die Maximierung eines konvexen Quadrats über dem Hyperwürfel ist ein klassisches unlösbares Problem, und Sie können keinen Algorithmus verwenden, der im schlimmsten Fall eine viel bessere Leistung erzielt, als einfach alle Eckpunkte des Hyperwürfels zu überprüfen.