Factoring a quadratic function

Question

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?

Answer 1

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.

Answer 2

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.