# $l_{0}$-norm constrained quadratic programming optimization

I intend to solve for vector $$x \in \mathbb{R}^{N \times 1}$$ by solving the following optimization problem

\begin{align} \arg \min_{x} \tfrac{1}{2} \mathbf{x}^T Q\mathbf{x} + \mathbf{c}^T \mathbf{x} \end{align} \begin{align} \text{S.t. } & x_{i}^{min} \leq x_{i} \leq x_{i}^{max} \\ \end{align}

\begin{align} \text{S.t. } & \|x\|_0 \leq k\\ \end{align} where $$\mathbf{Q} \in \mathbb{R}^{N \times N}$$ is a positive definite matrix, and $$\mathbf{c} \in \mathbb{R}^{N \times 1}$$.

Obviously if I remove the second constraint it is possible to solve the above using regular constrained quadratic programming (like quadprog command in MATLAB).

I know the $$l_{0}$$-norm makes the problem non-convex but I was hoping if someone can give me a hint how I could find the solution to this?

One option is to use integer programming -- add binary variables $$y_i$$ with constraints $$x^{min}_i y_i \leq x_i \leq x^{max}_i y_i$$. Then, your cardinality constraint becomes $$\sum_i y_i \leq k$$. You now have a mixed-integer quadratic program with linear constraints. It is harder to solve than a continuous QP, but at least this is a well-known class of optimization problems and there are already solvers out there that can tackle it; for example, the Gurobi suite has an MIQP solver. You will have to worry about all the usual issues that arise in IP.