Knapsack problem with fixed number of elements?

Question

I am looking at an optimization problem that looks like this:

$$ \text{minimize}\;\; \mathbf{x}^TQ\mathbf x \;\;, \; \mathbf x \in \mathbb R^n, x_i \in \lbrace 0, 1 \rbrace\\ \text{subject to}\;\; ||\mathbf x||_1 = m < n $$ In words, the goal is to select a fixed number $m$ of elements from $\mathbf x$ that minimizes the quadratic term.

$Q$ is a correlation matrix, i.e. a $n \times n$ symmetric matrix with $Q_{ji} \in [-1, 1]$.

I am looking for an efficient algorithm for this problem, by approximation if necessary, and was wondering if this problem belongs to any known class of optimization problems. It is certainly similar to the Quadratic Knapsack Problem, but in this case the constraint here is not an upper limit on a weighted sum, but simply the number of non-zero elements.

Answer 1

I don't know if this exactly works for you, but will give the relaxed version a shot:

Preliminaries:

Correlation matrix can be seen as the covariance matrix of the standardized random variables $X_{i}/\sigma (X_{i})$. And, any correlation matrix can be converted to a covariance matrix as: $$Q={\text{corr}}({X} )=\left({\text{diag}}(\Sigma )\right)^{-{\frac {1}{2}}}\,\Sigma \,\left({\text{diag}}(\Sigma )\right)^{-{\frac {1}{2}}}$$

If standard deviations $\{\sigma_i\}$ are known, then using $D = \sqrt{diag(\Sigma)}$: $$ \Sigma = DQD. $$

Formulation:

Using the definition above we can equivalently write $Q = D^{-1}\Sigma D^{-1}$. If we use this definition of $Q$ and set $B=D^{-1}$, then: $$ \begin{align} x^T Q x &= x^T B^T \Sigma B x \\ &= x^T B^T V^T \Lambda V B x \\ &= x^T B^T V^T \sqrt{\Lambda}^T\sqrt{\Lambda} V B x \\ \end{align} $$ $\Sigma=V^T \Lambda V$ follows from the eigen-decomposition and nicely exists for the covariance matrix. Then, substituting $M = B^T V^T \sqrt{\Lambda}^T$, one can show that:

$$ x^T Q x = x^T M^T M x = \lVert M x \rVert^2. $$

The problem then turns to : $$ \arg\min_x \lVert M x \rVert^2 + \lambda (\|x\|_0-m) $$ which is generally tackled via the $L_1$ variant of the form: $$ \arg\min_x \lVert M x \rVert^2 + \lambda \|x\|_1. $$

Now instead of thinking about $x$ as a binary vector, we could relax this constraint and seek for the sparsest solution under real $x$. This is a non-quadratic $L_1$-regularized Least Squares problem and one can solve it by standard techniques, such as (I guess) Lasso. Maybe it is then possible to look at the solution and determine $m$. This gives local optimality but should work well in practice. For hard constraints Lagrange multipliers can be used.

I might have to double check the formulation. As I don't have much time now, I'll do it later, but the method above should give you the idea.

Answer 2

The number of subsets of size $m$ of a set of size $n$ is $\binom{n}{m}$, which is bounded by

$\left(\frac{n}{m}\right)^m \le \binom{n}{m} \le \left(\frac{en}{m}\right)^m$.

So in the limit of $m \ll n$, you can come up with an $O(n^m)$ algorithm by trying all subsets of size $m$, and in the limit of $m \approx n$, you can try complements of all subsets of size $n - m$. For $m$ on the order of $n/2$, however, the brute force approach has a runtime on the order of $2^n$ and I don't think there's any getting around this, i.e. the problem is NP-hard in general.

There are several heuristics on the wiki article about the quadratic knapsack problem; many of them were either designed for the 0-1 problem or can be adapted from the weighted. The article also has a comprehensive list of references, many of which discuss both the weighted and 0-1 cases. You could also try searching github for example codes (this one came up right away but it's for the linear knapsack problem).

A simple heuristic is to pick an initial candidate set $x$ of size $m$, and improve it by swapping elements. Let $e_i$ be the standard basis vector in the $i$-th direction. To implement this heuristic, pick an index $i$ such that $x_i = 1$, and evaluate the objective function at $x - e_i + e_j$ for all $j$ such that $x_j = 0$. If there are any $j$ such that the exchange $i \leftrightarrow j$ reduces the objective function, pick the one that gives the smallest value of the objective, and then repeat for some other value of $i$. If run all the way to optimality, this could take $O(2^n)$ swaps, but it might give you an acceptable solution in less time. Additionally, the inner loop over $j$ can be parallelized.