# Maximizing $\mathbf{x}^T A \mathbf{x}$ subject to $| \mathbf{x} | \preceq \mathbf{1}$

I am trying to find a maximum of quadratic function bounded above/below. The problem is formulated as

\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} where $$\mathbf{A}$$ is positive semi-definite.

The Lagrangian of this function is $$\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}$$ where $${\lambda}_-^T$$ and $${\lambda}_+^T$$ are Lagrangian multipliers. I am struggling with how to find the optimal $$\mathbf{x}^*$$ maximizing the objective. Thank you!

• your usage of $\preceq$ is confusing. Is $\mathbf x$ a matrix, a vector, or a scalar? Sep 7, 2020 at 11:18
• @BenGrossmann Thanks for asking. $\mathbf{x}$ is a vector, and $\preceq$ means a component-wise inequality. Sep 7, 2020 at 11:58
• That makes sense, thanks for clarifying Sep 7, 2020 at 12:01
• Another approach, with which we might be able to find a solution in existing literature. Without loss of generality, we can assume that $\mathbf A$ here is symmetric (in addition to being positive semidefinite). With that, $\mathbf A$ has positive semidefinite and symmetric square root $\mathbf B := \mathbf A^{1/2}$. With that, we can rewrite your problem in the form $$\max_{\mathbf x} \|\mathbf B \mathbf x \|_2 \quad \text{s.t.} \quad \|\mathbf x\|_{\infty} \leq 1.$$ In other words, we want the induced $p,q$ norm $\|\mathbf B\|_{\infty,2}$. Sep 7, 2020 at 12:09
• A small step forward: we have $$\frac{\partial \mathcal L}{\partial \mathbf x} = 2(\mathbf A \mathbf x)^T + \lambda_+^T + \lambda_-^T = 0 \implies \mathbf A \mathbf x = \frac 12 (\lambda_+ + \lambda_-),$$ but I'm not sure where one would go from there Sep 7, 2020 at 12:24