I have a quadratic binary optimization problem of the form

\begin{align} &\max x^TQx \cr &\text{subject to }x\in\mathcal{X}\subseteq\{0,1\}^n, \end{align}

where $$\mathcal{X}$$ is the feasible area defined by linear constraints and binary requirement on the variables. I can assume that all entries in the matrix $$Q$$ are non-negative. My question is as follows: is it possible to write the function $$x^TQx$$ as a "combination" of two non-negative linear functions in the following way:

$$x^TQx = aF(x)^2 + bG(x)^2+cF(x)G(x) + dF(x) + eG(x) \tag{1}$$

where $$F(x)=\sum_{i=1}^nf_ix_i + f_0$$ and $$G(x)=\sum_{i=1}^ng_ix_i + g_0$$ are linear funtions, and $$a,b,c,d,e\geq 0$$ are real/rational constants. Or stated in another way; can I find values for $$f_i,g_i,\ i=0,\dots,n$$ and $$a,b,c,d,e$$ such that (1) is true?

Your conjecture can not be correct, for two purely formal reasons:

• In $x^T Q x$, if you multiplied this out as a sum $\sum_i \sum_j Q_{ij}x_ix_j$, every term in the sum is the product of two entries of the vector $x$. On the other hand, in your conjecture the formula (1) contains terms that are linear in the components of $x$. This can only be correct if you set $d=e=0$.

• Your functions $F,G$ depend on coefficients $f_i,g_i$, of which there are only $2n$. (I'm neglecting $f_0,g_0$ for the same reason as above: they must be zero, because otherwise the resulting function would have terms that are linear in some of the $x_i$.) But $Q$ contains $n^2$ entries. So, for a fixed $x$, the term $x^T Q x$ is an $n^2$ dimensional object depending on the coefficients of $Q$, whereas $aF(x)^2 + bG(x)^2 + cF(x)G(x)$ is only a $2n+3$ dimensional object. These cannot, in general, be the same. In other words, you try to represent $Q$ in a space that is too small.

• Regarding the linear terms in the the representation, I think that is fine, as it is a binary optimization problem, and thus $x_i^2=x_i$. I'm not completely sure I know what is meant by a $2n+3$ dimensional object''. Is it because $Q$ could have full rank, and the coefficient matrices of $F(x)^2,G(x)^2,$ and $F(x)G(x)$ all have rank 1? Is it possible to say anything about when a QP could be represented in this way? Sep 6 '17 at 10:40
• The only thing I can come up with is that$$Q_{ij}+Q_{ji} = 2af_if_j+2bg_ig_j+c(f_ig_j+f_jg_i)$$ when $i\neq j$ and $$Q_{ii}=af_i^2+bg_i^2+cf_ig_i+df_i+eg_i$$ when $i=j$. Sep 8 '17 at 11:42
• @user25340: I don't think the binary nature makes as much difference to the number of free parameters as you hope. From case counting your formulae in your last comment you effectively have $n(n+1)/2$ free parameters on the left and at most 2n+7 on the right (although I don't think all of those actually contribute). That's not a situation where you have any guarantee of a general solution. Sep 9 '17 at 0:15
• Yes, you got that right: you are adding up only a fixed number of rank-1 objects, so you can't in general get a rank-$n$ matrix. Sep 10 '17 at 23:26

The answer is "yes" if the matrix $Q$ is at most rank-2.

First, we note that for the equality to hold for all $x$, we must have $d=e=f_{0}=g_{0}=0$. The reason is that function $\Phi(x)=x^{T}Qx$ is quadratic homogenous, meaning it satisfies $\Phi(0)=0$ and $\Phi(\alpha x)=\alpha^{2}\Phi(x)$, whereas (1) would not be quadratic homogenous if these values weren't set to zero.

Next, we show that the RHS is the quadratic form of a rank-2 matrix. First, note that with $d=e=0,$ we have $$\text{(1) =}\begin{bmatrix}F(x)\\ G(x) \end{bmatrix}^{T}\begin{bmatrix}a & \frac{1}{2}c\\ \frac{1}{2}c & b \end{bmatrix}\begin{bmatrix}F(x)\\ G(x) \end{bmatrix}$$ and that with $f_{0}=g_{0}=0$, we have $$\begin{bmatrix}F(x)\\ G(x) \end{bmatrix}=\begin{bmatrix}f_{1} & \cdots & f_{n}\\ g_{1} & \cdots & g_{n} \end{bmatrix}\begin{bmatrix}x_{1}\\ \vdots\\ x_{n} \end{bmatrix}=\begin{bmatrix}f & g\end{bmatrix}^{T}x,$$ by defining $f=[f_{1},\ldots,f_{n}]^{T}$ and similarly for $g=[f_{1},\ldots,f_{n}]^{T}$. Combining the two and applying Gaussian elimination yields \begin{align*} (1) & =x^{T}\begin{bmatrix}f & g\end{bmatrix}\begin{bmatrix}a & \frac{1}{2}c\\ \frac{1}{2}c & b \end{bmatrix}\begin{bmatrix}f & g\end{bmatrix}^{T}x.\\ & =x^{T}\begin{bmatrix}f & g\end{bmatrix}\begin{bmatrix}1 & 0\\ \frac{1}{2}c & 1 \end{bmatrix}\begin{bmatrix}a & 0\\ 0 & b-\frac{1}{4}c^{2}/a \end{bmatrix}\begin{bmatrix}1 & 0\\ \frac{1}{2}c & 1 \end{bmatrix}^{T}\begin{bmatrix}f & g\end{bmatrix}^{T}x\\ & =x^{T}\left(\begin{bmatrix}f & g\end{bmatrix}\begin{bmatrix}1 & 0\\ \frac{1}{2}c & 1 \end{bmatrix}\right)\begin{bmatrix}a & 0\\ 0 & b-\frac{1}{4}c^{2}/a \end{bmatrix}\left(\begin{bmatrix}f & g\end{bmatrix}\begin{bmatrix}1 & 0\\ \frac{1}{2}c & 1 \end{bmatrix}\right)^{T}x\\ & =x^{T}\left(\mu_{1}v_{1}v_{1}^{T}+\mu_{2}v_{2}v_{2}^{T}\right)x \end{align*} where $$\mu_{1}=a,\quad\mu_{2}=b-\frac{c^{2}}{4a},\quad v_{1}=f+\frac{c}{2}g,\quad v_{2}=g.$$

Finally, we use the above result to write a closed-form solution. Given a rank-2 decomposition for the left-hand side $Q=\mu_{1}v_{1}v_{1}^{T}+\mu_{2}v_{2}v_{2}^{T}$, we pick any choice of $c$ and write $$a=\mu_{1},\quad b=\mu_{2}+\frac{c^{2}}{4a},\quad G(x)=v_{2}^{T}x,\quad F(x)=(v_{1}-\frac{c}{2}v_{2})^{T}x$$ to yield the desired decomposition. The decomposition is clearly nonunique, because it remains valid for any choice of $c$ that conforms to the equation above.