Relaxing $\ell_0$ constraints in an optimization I have a feasibility question that can be framed as follows. I'm given a point $p$ in a $d$-dimensional vector space, and I want to find the closest point $q$ to $p$ that satisfies a set of "$\ell_0$ constraints" of the form


  Given a set $S \in [1\ldots d]$, at
  most one of $\{q_j, j \in S\}$ can be
  nonzero.


The notion of closeness varies, but for now it is sufficient to assume a convenient distance like $\ell_2^2$.

Are there any known relaxations to linear constraints that are "good" in the sense of providing a "close enough" polytope to approximate the original constraints, where I'm also pretty flexible on the definition of "close enough"
I am not sure if I understand the problem correctly, but as is written, the problem seems to admit several simplifications, and in particular the problem in the ℓ22 case is equivalent to the minimum-weight vertex cover if I am not mistaken.


Without loss of generality we can assume that |S|=2 in every constraint, because a constraint with |S|&gt;2 is equivalent to the set of constraints where S runs over all pair of elements in the original set S.  Therefore, the ℓ0 constraints can be visualized as a graph G with d vertices.  Using the graph G, the constraints can be restated as follows: the set of the vertices corresponding to the coordinates i with qi=0 must be a vertex cover of G.
Assume that the distance is defined by ℓ22 or some norm.  In this case, any point q can be transformed to a point q′ that satisfies for every i, q′i∈{0,pi}, simply by setting $$ q'_i = \begin{cases} p_i, &amp; q_i \ne 0, \\ 0, &amp; q_i = 0, \end{cases} $$ and this transformation never increases the distance from the point p.  In particular, if the distance is the sum of coordinate-wise distance (as in the case of the ℓ22 distance), the problem is exactly the same as the minimum-weight vertex cover.


As for an LP relaxation of the vertex cover problem, a quick search leads to e.g. the lecture notes (Lecture 9) by Uriel Feige.