Maksimize etme $\mathbf{x}^T A \mathbf{x}$ tabi $| \mathbf{x} | \preceq \mathbf{1}$

Question

Yukarı / aşağı sınırlanmış maksimum ikinci dereceden fonksiyon bulmaya çalışıyorum. Sorun şu şekilde formüle edilmiştir:

\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} nerede $\mathbf{A}$ pozitif yarı kesindir.

Bu fonksiyonun Lagrangian'ı \ begin {equation} \ mathcal {L} = \ mathbf {x} ^ T \ mathbf {A} \ mathbf {x} + {\ lambda} _- ^ T (\ mathbf {x} + \ mathbf {1}) - \ lambda _ + ^ T (\ mathbf {x} - \ mathbf {1}), \ end {equation} nerede${\lambda}_-^T$ ve ${\lambda}_+^T$Lagrange çarpanlarıdır. Optimal olanı nasıl bulacağımla uğraşıyorum$\mathbf{x}^*$hedefi maksimize etmek. Teşekkür ederim!

Answer 1

Hiperküp üzerinde bir dışbükey kuadratiğin maksimizasyonu klasik bir inatçı problemdir ve en kötü durumda, hiperküpün tüm köşelerini kontrol etmekten çok daha iyi performans gösteren bir algoritmayı cihazlayamayacaksınız.