The Boolean Quadratic Programming problem is defined as follows
$$\displaystyle\min_{x \in \{0,1\}^n} f(x) = x^TQx + c^Tx$$
It is a well-studied NP-hard problem with many approximation algorithms proposed. I am interested in finding the number of minima given arbitrary $Q, c$.
If the problem as such is not well-studied then we can simplify it by adding some special conditions on $Q$ (like positive definiteness). In the worst case can we determine the number of minima if we remove the Boolean restriction and consider $x \in \mathbb R^n$ or $ x \in [0,1]^n$?
If there are papers or online links that I can refer that will help me sort this problem out, it will be of great help.
Thanks!
1, The proposed theory
If an irrational sequential analysis was applied under huge dimension, it will need much time because the Boolean vector has $2^n$ combinations. Hence, the other rational algorithms are necessary. For definition, we suppose a real symmetric matrix $Q=[q_{ij}]\in\mathbf{R}^{n\times n}$ so that $Q=Q^{\text{T}}$ and $q_{ij}=q_{ji}$ are established. Also, the quadratic function $f(\boldsymbol{x})$ can be described as follows:
$$ \begin{aligned} f(\boldsymbol{x})=& \boldsymbol{x}^{\text{T}}Q\boldsymbol{x}+\boldsymbol{c}^{\text{T}}\boldsymbol{x} \\=& \sum_{i,j=1}^{n}q_{ij}x_{i}x_{j}+ \sum_{i=1}^{n}c_{i}x_{i} \\=& \sum_{i=1}^{n}\biggl( \sum_{j=1}^{n}q_{ij}x_{i}x_{j}+c_{i}x_{i} \biggr) \\=& \sum_{i=1}^{n}g(x_{i}) \end{aligned} $$
where specific functions $g_{i}=g(x_{i})$ are defined:
$$ g(x_{i})=\sum_{j=1}^{n}q_{ij}x_{i}x_{j}+c_{i}x_{i} $$
Of course, the Boolean vector indicates only binary number so that the function can be divided the following two cases:
$$ g_{i}= \begin{cases} \displaystyle \sum_{j=1}^{n}q_{ij}x_{j}+c_{i} & (x_{i}=1) \\ \\ 0 & (x_{i}=0) \end{cases} $$
To get the minimized solution, the functions $g_{i}$ must be made to become smaller. Now the condition is set to compare with each cases:
$$ \begin{aligned} g_{i}(1)<&g_{i}(0) \\ \sum_{j=1}^{n}q_{ij}x_{j}+c_{i}<& \ 0 \end{aligned} $$
Then, when we turn over the one binary parameter by the above condition, all equations must be changed because the a matrix coefficient includes all conditions. For instance, when the $k \ (1\leq k \leq n)$ th function satisfies the above condition and switches "True$=1$" from "False$=0$", the all functions except own are renew using the following top case. On the other hand, the opposite case as switched "False$=0$" from "True$=1$", the middle equation is used. The otherwise case, it does not need to change the value. Likewise, other functions are applied simultaneously below:
$$ \begin{aligned} &g_{i\neq k}'= \begin{cases} g_{i}+q_{ik} & (x_{k}=0\to 1)\\ g_{i}-q_{ik} & (x_{k}=1\to 0)\\ g_{i} & (\text{no change}) \end{cases}\\ \\ &g_{i=k}'= \begin{cases} g_{k} & (x_{k}=1)\\ 0 & (x_{k}=0) \end{cases} \end{aligned} $$
Then these operations are repeated until convergence under finite number of trials $t$ and can be converted with the matrix and vectors as follows. Then the Boolean vector is decided by the result of logical operation:
$$ \begin{aligned} \boldsymbol{g}^{t+1}=&Q \biggl\{\Big(\boldsymbol{x}^t+ (\boldsymbol{g}^{t}<\mathbf{0})- (\boldsymbol{g}^{t}>\mathbf{0}) \Big)>\mathbf{0}\biggr\} +\boldsymbol{c} \\=& Q(\boldsymbol{g}^{t}<\mathbf{0})+\boldsymbol{c} \\=& Q\boldsymbol{x}^{t+1}+\boldsymbol{c} \end{aligned} $$
where:
$$ \begin{aligned} \boldsymbol{g}^t=& \begin{bmatrix} g_{1}^t & g_{2}^t & \cdots & g_{i}^t & \cdots & g_{n}^t \end{bmatrix}^{\text{T}} \\=& Q\boldsymbol{x}^t+\boldsymbol{c} \end{aligned} $$
and the logical operation can be simplified owing to the following table:
$$ \begin{array}{ccc|c} \hline (x_{i}^t) &(g_{i}^{t}<0) & (g_{i}^{t}>0) & (x_{i}^{t+1}) \\ \hline 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ \hline \end{array} \Longrightarrow \begin{array}{c|c} \hline (g_{i}^{t}<0) & (x_{i}^{t+1}) \\ \hline 1 & 1 \\ 0 & 0 \\ 1 & 1 \\ 0 & 0 \\ \hline \end{array} $$
Then, the initial values is set $\boldsymbol{x}^{t=0}=(\boldsymbol{c}<\mathbf{0})$ because it is ensured that $\boldsymbol{c}^{\text{T}}\boldsymbol{x}^{t=0}$ is indicated negative. Herewith, it is easy to converge rapidly.
2, Numerical experiment
An arbitrary real symmetric matrix and a vector are set when the size $n=8$:$$ Q= \begin{bmatrix} 16 & -2 & -8 & -12 & 7 & -2 & -2 & 1 \\ & -10 & 25 & 3 & -4 & -13 & 22 & -19 \\ & & 7 & -8 & -14 & -15 & -4 & -25 \\ & & & -5 & -20 & 8 & 8 & 10 \\ & & & & 18 & 7 & -10 & 4 \\ & & & & & 5 & 11 & -12 \\ & & & & & & -2 & 15 \\ & & & & & & & 12 \end{bmatrix} , \ \ \ \ \boldsymbol{c}= \begin{bmatrix} -1 \\ -11 \\ 7 \\ -7 \\ 28 \\ 9 \\ 3 \\ -10 \end{bmatrix} $$
Then $t=3$, the minimum value was found on $f(\boldsymbol{x}^{t=3})=-116$ and the combination of Boolean vector was shown below:
$$ \boldsymbol{x}^{t=3}= \begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 \end{bmatrix}^{\text{T}} $$
Next, we attempt a large case as $n=2^8$. Generally, it is impossible to find the minimum value due to numerous number of combination ($1.158\times 10^{77}$). However we can see the below figure which is described that the minimum value is discovered on the number of trial $t=18$.