Relaxing $\ell_0$ constraints in an optimization
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.