<p>This may be related to what you have in mind: <a href="http://arxiv.org/abs/0804.4666" rel="nofollow noreferrer">arxiv.org/abs/0804.4666</a></p>

CC BY-SA 4.0
2020-07-15T21:33:42.553Z
2020-07-15T21:33:42.553Z
Mahdi Cheraghchi
<p>Optimization problems of the type: minimize <span class="math-container">$c^T x$</span> subject to [maybe some linear constraints and] <span class="math-container">$||x||_0\le k$</span> are known to be NP-hard. [Actually, I just realized that I don't have a reference, so if anyone has one handy, please say so in the comments!] The <span class="math-container">$\ell_0$</span> &quot;norm&quot; is the number of non-zero elements in the vector <span class="math-container">$x$</span>. A common way to solve such problems is via a convex relaxation: relax <span class="math-container">$||x||_0\le k$</span> to <span class="math-container">$||x||_1\le k$</span> and solve the resulting linear program. With luck, one can quantify how close the relaxed solution is to the optimal.</p>
<p>My question is: What if we try a more gradual relaxation, via the <span class="math-container">$\ell_p$</span> norm for <span class="math-container">$0&lt;p&lt;1$</span>? These result in non-convex programs, but the non-convexity degree can be tweaked. Surely the <span class="math-container">$p=0.999$</span> case, for reasonably set other parameters, cannot be much harder than the <span class="math-container">$p=1$</span> case?.. Has anybody tried this approach? The idea is to seek a better efficiency/optimality tradeoff via values of <span class="math-container">$p$</span> other than <span class="math-container">$1$</span>.</p>

<np-hardness><optimization><convex-optimization>
Parametrized complexity of sparse optimization
Aryeh
# Parametrized complexity of sparse optimization

(Asked by: username_0 on 2020-07-15)

Optimization problems of the type: minimize $c^T x$ subject to [maybe some linear constraints and] $||x||\_0\le k$ are known to be NP-hard. [Actually, I just realized that I don't have a reference, so if anyone has one handy, please say so in the comments!] The $\ell\_0$ "norm" is the number of non-zero elements in the vector $x$. A common way to solve such problems is via a convex relaxation: relax $||x||\_0\le k$ to $||x||\_1\le k$ and solve the resulting linear program. With luck, one can quantify how close the relaxed solution is to the optimal.

My question is: What if we try a more gradual relaxation, via the $\ell\_p$ norm for $0? These result in non-convex programs, but the non-convexity degree can be tweaked. Surely the $p=0.999$ case, for reasonably set other parameters, cannot be much harder than the $p=1$ case?.. Has anybody tried this approach? The idea is to seek a better efficiency/optimality tradeoff via values of $p$ other than $1$.

**Tags:** np-hardness, optimization, convex-optimization

---

## 1 answers

### Answer by username_1 on 2020-07-15. Score: 1 | Accepted answer

This may be related to what you have in mind: [arxiv.org/abs/0804.4666](http://arxiv.org/abs/0804.4666)


---

