2
$\begingroup$

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?

$\endgroup$
1
  • 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

0
$\begingroup$

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".

$\endgroup$

Your Answer

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