When we consider the following optimization problem: \begin{equation}\label{P}\tag{P} \begin{array}{ll} \displaystyle\min_{x \in \mathbb{R}^n} & f(x) \\ \text{s.t.} & Ax = b,~ x \geq 0, \\ & \|x\|_0 \leq s. \end{array} \end{equation} Here, $\|x\|_0$ denotes the number of nonzero components of a vector $x$, $s \leq n$ is the sparsity parameter, and $f(x)$ is a convex function.

Is there any method to solve this kind of problem in the literature?

  • 4
    $\begingroup$ You can add a binary variable $y_i$ for each $x_i$, which is activated if $x_i >0$. And add $\sum_i y_i \le s$ $\endgroup$
    – Kuifje
    Commented Jun 12 at 14:18

1 Answer 1


The Pseudo ${L}_{0}$ Norm means the problem is an integer problem.
For very small $n$ discrete optimization might work.

For large dimensions you should do something greedy.
Assuming $f$ is smooth, you may use Projected Gradient Descent and using the Hard Threshold Operator as the projection onto the Pseudo ${L}_{0}$ Norm constraint (See Derivation of Hard Thresholding Operator (Least Squares with Pseudo L0 Norm).

You may also utilize ADMM and then break the projection into "smaller pieces".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.