1
$\begingroup$

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!

$\endgroup$
9
  • $\begingroup$ your usage of $\preceq$ is confusing. Is $\mathbf x$ a matrix, a vector, or a scalar? $\endgroup$
    – Ben Grossmann
    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$
    – Ben Grossmann
    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$
    – Ben Grossmann
    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$
    – Ben Grossmann
    Sep 7, 2020 at 12:24

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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