# Knapsack problem with fixed number of elements?

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.

• When you say "number of nonzero elements", did you mean to use the $l_0$ norm instead of the $l_1$ norm? – Wolfgang Bangerth Jan 20 '18 at 1:24
• @WolfgangBangerth I guess they would amount to the same thing here, since $x_i \in \lbrace0, 1 \rbrace$? – Slug Pue Jan 20 '18 at 12:58
• Oh yes, good point. – Wolfgang Bangerth Jan 20 '18 at 16:14
• Does Q have a special structure? – Tolga Birdal Jan 21 '18 at 20:18
• This is very close to the MAX-CUT problem, and the standard semidefinite relaxation alongside a randomized rounding should work well. See Goemans and Williamson. – Richard Zhang Jan 21 '18 at 20:45

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.

• hm, yes. I guess then, one can vary $\lambda$ until $|| x ||_0 = m$? – Slug Pue Jan 22 '18 at 13:22
• Exactly. I do think that many algorithms do exist at this point, but I would just resort to the standard ones. Simplifying the problem this way helps to get a better solution. – Tolga Birdal Jan 22 '18 at 14:23
• One can also regularize by $(\lVert x \rVert_0 -m)$ I guess. – Tolga Birdal Jan 22 '18 at 19:17
• yes, but come to think of it, I think regularization by $(||x||_0 - m)$ is the only way to make this approach work for this problem. Because it seems in order to get the solution close to the solution of the original problem, one would have to constrain $x$ to $x \geq 0$. But then the solution is simply $x = 0$ for all values of $\lambda$ – Slug Pue Jan 22 '18 at 21:17
• Sure, but nevertheless well doable. – Tolga Birdal Jan 22 '18 at 21:34

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.