Maximiser $\mathbf{x}^T A \mathbf{x}$ sujet à $| \mathbf{x} | \preceq \mathbf{1}$

Question

J'essaie de trouver un maximum de fonction quadratique délimitée au-dessus / au-dessous. Le problème est formulé comme

\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} où $\mathbf{A}$ est semi-défini positif.

Le lagrangien de cette fonction est \ begin {equation} \ mathcal {L} = \ mathbf {x} ^ T \ mathbf {A} \ mathbf {x} + {\ lambda} _- ^ T (\ mathbf {x} + \ mathbf {1}) - \ lambda _ + ^ T (\ mathbf {x} - \ mathbf {1}), \ end {équation} où${\lambda}_-^T$ et ${\lambda}_+^T$sont des multiplicateurs lagrangiens. J'ai du mal à trouver le meilleur$\mathbf{x}^*$maximiser l'objectif. Je vous remercie!

Answer 1

La maximisation d'un quadratique convexe sur l'hypercube est un problème classique insoluble, et vous ne pourrez pas installer un algorithme qui, dans le pire des cas, fonctionne bien mieux que de simplement vérifier tous les sommets de l'hypercube.