Discrete Convex Optimization with Sparse Solutions

Solution 1:

Your problem is a mixed integer nonlinear program (MINLP). It's not "convex" in the classical sense because the feasible region is not convex, but such problems are often called convex MINLP because the continuous relaxation of the problem is convex.

You should be aware that this problem is NP-Hard- the available algorithms have exponential worst-case complexity and you may simply not be able to solve large instances.

There's a huge literature on methods for MINLP and many software packages are available.

One approach that you're already aware of is to reformulate the problem in terms of 0-1 integer variables and then turn your quadratic objective into a linear objective in terms of products of the 0-1 integer variables. This would result in a huge problem and isn't likely to be a good approach for your problems.

Another widely used approach is branch-and-bound using the continuous relaxation of the problem. Since the continuous relaxation is convex (and quadratic), it's quite easy to solve. This could be a good approach for your problem.

A third family of approaches are "Generalized Benders Decomposition" or "Outer Approximation". These methods might also work well for your problem.

The NEOS optimization guide and the NEOS online solvers are a wonderful resource in this area. See

https://neos-guide.org/content/mixed-integer-nonlinear-programming

https://neos-server.org/neos/