1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user25340 Sep 6 '17 at 10:40
  • $\begingroup$ The only thing I can come up with is that\begin{equation} Q_{ij}+Q_{ji} = 2af_if_j+2bg_ig_j+c(f_ig_j+f_jg_i)\end{equation} when $i\neq j$ and \begin{equation} Q_{ii}=af_i^2+bg_i^2+cf_ig_i+df_i+eg_i\end{equation} when $i=j$. $\endgroup$ – user25340 Sep 8 '17 at 11:42
  • 1
    $\begingroup$ @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. $\endgroup$ – origimbo Sep 9 '17 at 0:15
  • $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Sep 10 '17 at 23:26
1
$\begingroup$

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.

$\endgroup$

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.