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!

  • $\begingroup$ your usage of $\preceq$ is confusing. Is $\mathbf x$ a matrix, a vector, or a scalar? $\endgroup$ Sep 7, 2020 at 11:18
  • $\begingroup$ @BenGrossmann Thanks for asking. $\mathbf{x}$ is a vector, and $\preceq$ means a component-wise inequality. $\endgroup$
    – Sean Cho
    Sep 7, 2020 at 11:58
  • $\begingroup$ That makes sense, thanks for clarifying $\endgroup$ Sep 7, 2020 at 12:01
  • $\begingroup$ 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}$. $\endgroup$ Sep 7, 2020 at 12:09
  • $\begingroup$ 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 $\endgroup$ Sep 7, 2020 at 12:24

1 Answer 1


Maximization of a convex quadratic over the hypercube is a classical intractable problem, and you will not be able to device an algorithm which, in the worst case, performs much better than simply checking all the vertices of the hypercube.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .