I have a minimisation problem in the following form $$\textrm{min}: x^TAx$$ constrained by $\sum x_i=N$
where $x$ is a vector containing only 1's and 0's, and $A$ is a square matrix of real numbers.
In my case size($x$) is very large and $0<<N<<\textrm{size}(x)$.
Is there a class of methods for solving this program efficiently?
Many thanks for anybody's help!
Let $M$ be the dimension of $x.$ For any $i,j\in \lbrace 1,\dots,M\rbrace$ with $i\neq j,$ the term $A_{i,j}$ appears in the objective value if and only if $A_{j,i}$ also appears (i.e., if and only if $x_i=1=x_j$). So we can do a bit of preprocessing by replacing $A_{i,j}$ and $A_{j,i}$ with their average $(A_{i,j}+A_{j,i})/2.$ After this step, we have an equivalent problem with a symmetric $A$ matrix. Also, if it proves useful (I'm not sure it will), we can exploit the fact that we know the number of $A_{i,j}$ that will end up in the objective sum ($N^2$), so if we want $A\ge 0$ we can just subtract the smallest entry in $A$ from every entry in the matrix, which produces an equivalent problem (where the objective value is changed by a constant amount).
Armed with that, consider a complete graph with $M$ nodes, where each edge $(i,j)$ has weight $A_{i,j}.$ Your problem can now be stated as selecting a minimum weight $N$-clique from the graph. If you search for "minimum weight clique", you will find relevant references. Here is one: https://cstheory.stackexchange.com/questions/2221/heuristics-for-the-minimum-weight-k-clique-problem.