Let $A \in \mathbb{R}^{n\times n}$ be symmetric and positive definite. What is the following maximum?

$$\max_{x\in\{\pm1\}^n}x^T A x$$

My attempt:

if all $a_{ij}\geq 0$, then

\begin{equation} \max_{x\in\{\pm1\}^n}x^TAx=\sum a_{ij} \end{equation}

and in this case $x=[1\quad 1\quad\cdots\quad 1]'$ or $x=[-1\quad -1\quad\cdots\quad -1]'$.

if some $a_{ij}<0$, then situation is not clear, but we know that $x^TAx\leq\sum{|a_{ij}|}$.

For example:

\begin{equation} A= \begin{bmatrix} 2 & 3 & 1 \\ 3 & 10 & -8 \\ 1 & -8 & 17 \end{bmatrix}. \end{equation} \begin{equation} \max_{x\in\{\pm1\}^n}x^TAx=49<\sum |a_{ij}|=53 \end{equation} and in this case $x=[1\quad1\quad-1]'$ or $x=[-1\quad-1\quad1]'$. So idea is to sacrifice $2a_{13}$ since it is smaller than $2a_{23}$ and $2a_{12}$.

Is there any systematic way to tell the maximum of $x^TAx$ for any $n$ if $A$ is given? and if yes how to find $x$ that will give the maximum? Any suggestions are welcome :)

  • $\begingroup$ in the example above, spectral radius of $A$ is 22.265 But maximum is 49. Please correct me if I am wrong $\endgroup$ – Lee Nov 15 '18 at 7:39
  • $\begingroup$ so $|x_i|$=1 and $||x||_{\infty}=1$ are similar? $\endgroup$ – Lee Nov 15 '18 at 7:49
  • 1
    $\begingroup$ what I wanted to say is that all elements of $x$ are equal to 1 or -1, so I think I will better stick to $|x_i|=1$ $\endgroup$ – Lee Nov 15 '18 at 7:54
  • 1
    $\begingroup$ Related: math.stackexchange.com/q/2126489/339790 $\endgroup$ – Rodrigo de Azevedo Nov 15 '18 at 7:59
  • 1
    $\begingroup$ This is known as a Binary Quadratic Problem and is hard. There are some solvers for it, for instance www-lipn.univ-paris13.fr/BiqCrunch and you can have some success solving a sequence of semidefinite relaxations. $\endgroup$ – Michal Adamaszek Nov 15 '18 at 10:00

I found an answer, maybe will be useful for someone.

For details go to this paper: http://users.isy.liu.se/en/rt/claal20/Publications/bipartite_consensus.pdf

Here $A$ represents an undirected graph. If $A$ is structurally balanced (condition of structurally balanced given in the paper), then $\max x^TAx = \sum |a_{ij}|$ and we can find at which corner objective function achieves maximum. However, if $A$ is not structurally balanced, $\sum |a_{ij}|$ can never be achieved. In this case, we have to go through all corners numerically to find the maximum.

For example, $\begin{equation} A= \begin{bmatrix} 2 & 3 & 1 \\ 3 & 10 & -8 \\ 1 & -8 & 17 \end{bmatrix} \end{equation}$ is structurally unbalanced so we can never achieve 53. However, $\begin{equation} A= \begin{bmatrix} 2 & 3 & -1 \\ 3 & 10 & -8 \\ -1 & -8 & 17 \end{bmatrix} \end{equation}$ is structurally balanced and for $x=[1\quad 1\quad -1]'$ or $x=[-1\quad -1\quad 1]'$ we can achieve 53.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.