<p>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 ℓ<sub>2</sub><sup>2</sup> case is equivalent to the minimum-weight vertex cover if I am not mistaken.</p>

<ol>
<li>Without loss of generality we can assume that |<i>S</i>|=2 in every constraint, because a constraint with |<i>S</i>|&gt;2 is equivalent to the set of constraints where <i>S</i> runs over all pair of elements in the original set <i>S</i>.  Therefore, the ℓ<sub>0</sub> constraints can be visualized as a graph <i>G</i> with <i>d</i> vertices.  Using the graph <i>G</i>, the constraints can be restated as follows: the set of the vertices corresponding to the coordinates <i>i</i> with <i>q</i><sub>i</sub>=0 must be a vertex cover of <i>G</i>.</li>
<li>Assume that the distance is defined by ℓ<sub>2</sub><sup>2</sup> or some norm.  In this case, any point <i>q</i> can be transformed to a point <i>q</i>′ that satisfies for every <i>i</i>, <i>q</i>′<sub><i>i</i></sub>∈{0,<i>p</i><sub><i>i</i></sub>}, 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 <i>p</i>.  In particular, if the distance is the sum of coordinate-wise distance (as in the case of the ℓ<sub>2</sub><sup>2</sup> distance), the problem is exactly the same as the minimum-weight vertex cover.</li>
</ol>

<p>As for an LP relaxation of the vertex cover problem, a quick search leads to e.g. the <a href="http://www.wisdom.weizmann.ac.il/~feige/lp02.html" rel="nofollow">lecture notes (Lecture 9) by Uriel Feige</a>.</p>

CC BY-SA 2.5
2010-11-03T20:25:42.570Z
Pretty interesting. I like the observation about |S| not needing to be more than 2
Suresh Venkat
CC BY-SA 2.5
2010-11-04T06:40:05.710Z
There's one thing that doesn't quite work. The variables in general can be arbitrary (not between zero and one). So you can't really encode the LP constraints for the "variables set to zero must form a vertex cover". This becomes an issue (which I should have mentioned) because there are other (linear) constraints on the coordinates that have to be incorporated as well.
Suresh Venkat
CC BY-SA 2.5
2010-11-07T06:31:20.717Z
@Suresh: If you really think that you have mentioned it, you can always modify the question.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-06T00:33:35.520Z
@Suresh: I meant to say “If you really think that you _should have_ mentioned it ….”
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-03T19:19:25.100Z
2010-11-03T19:19:25.100Z
Tsuyoshi Ito
<p>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</p>

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

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

<p>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"</p>

CC BY-SA 2.5
2010-11-04T22:46:37.307Z
Are the constraints allowed to depend non-linearly on $p$?
Warren Schudy
CC BY-SA 2.5
2010-11-04T22:50:44.323Z
Can you elaborate on what sort of polytope you're looking for? The convex hull of feasible points $q$ points with at most one non-zero coordinate is $\mathcal{R}^d$, so there's no hope of a good polyhedral approximation of the set of feasible $q$ points.
Warren Schudy
CC BY-SA 2.5
2010-11-04T23:31:35.223Z
If $p$ is a constant known in advance then for any distance constant $\delta$ you can easily compute the feasible points that are within $\delta$ of $p$ (looking at a single constraint only). For some metrics the feasible points will be a union of polytopes; for others you may have to approximate them by such or use a separation oracle. Then write linear constraints encoding that $q$ is within the convex hull of these.
Warren Schudy
CC BY-SA 2.5
2010-11-05T04:53:33.153Z
@warren: the constraints depend linearly on p, but p itself is not a constant (rather, it's the input to the problem). The constraints are of the above kind, or are linear constraints on the q_i.
Suresh Venkat
<ds.algorithms><approximation-algorithms><linear-programming>
Relaxing $\ell_0$ constraints in an optimization
Suresh Venkat
# Relaxing $\ell_0$ constraints in an optimization

(Asked by: username_0 on 2010-11-03)

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"

**Tags:** ds.algorithms, approximation-algorithms, linear-programming

> **Comments:**
> **username_1**: Are the constraints allowed to depend non-linearly on $p$?  
> **username_1**: Can you elaborate on what sort of polytope you're looking for? The convex hull of feasible points $q$ points with at most one non-zero coordinate is $\mathcal{R}^d$, so there's no hope of a good polyhedral approximation of the set of feasible $q$ points.  
> **username_1**: If $p$ is a constant known in advance then for any distance constant $\delta$ you can easily compute the feasible points that are within $\delta$ of $p$ (looking at a single constraint only). For some metrics the feasible points will be a union of polytopes; for others you may have to approximate them by such or use a separation oracle. Then write linear constraints encoding that $q$ is within the convex hull of these.  
> **username_0**: @warren: the constraints depend linearly on p, but p itself is not a constant (rather, it's the input to the problem). The constraints are of the above kind, or are linear constraints on the q_i.  

---

## 1 answers

### Answer by username_2 on 2010-11-03. Score: 7

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.

1. Without loss of generality we can assume that |*S*|=2 in every constraint, because a constraint with |*S*|>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 *q*i=0 must be a vertex cover of *G*.
2. 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,*p**i*}, simply by setting $$ q'\_i = \begin{cases} p\_i, & q\_i \ne 0, \\ 0, & 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](http://www.wisdom.weizmann.ac.il/~feige/lp02.html).

> **Comments:**
> **username_0**: Pretty interesting. I like the observation about |S| not needing to be more than 2  
> **username_0**: There's one thing that doesn't quite work. The variables in general can be arbitrary (not between zero and one). So you can't really encode the LP constraints for the "variables set to zero must form a vertex cover". This becomes an issue (which I should have mentioned) because there are other (linear) constraints on the coordinates that have to be incorporated as well.  
> **username_2**: @Suresh: If you really think that you have mentioned it, you can always modify the question.  
> **username_2**: @Suresh: I meant to say “If you really think that you _should have_ mentioned it ….”  

---

