0
$\begingroup$

I have been looking into the problem $\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time has been spent looking for a representation different from the one above (formed as a linear/integer program). I know there are approximation methods (Basis Pursuit, Matching Pursuit, the $\ell_1$ problem), but I haven't found an exact formulation in any of my searching and sparse representation literature. I have developed a formulation for the problem, but I would love to compare with anything else that is available. Does anyone know of such a formulation?

Thanks in advance, Clark

P.S. I'm aware that the $\|x\|_0$ problem is NP-hard, and as such, probably will not yield an exact formulation as an LP (unless P=NP). I was more referring to an exact formulation or an LP relaxation.

Improve this question
$\endgroup$
8
  • $\begingroup$ I am confused: Do you look for an exact reformulation or an LP relaxation? $\endgroup$
    – Dirk
    Commented Jul 7, 2012 at 14:09
  • $\begingroup$ An exact formulation is my major goal, but I would be interested to see a relaxation as well. $\endgroup$
    – Clark
    Commented Jul 7, 2012 at 14:30
  • $\begingroup$ Still a question remains: What is the aim of your reformulation? In other words: what is wrong with the $\ell^0$-minimization problem? As you have written: The problem is NP-hard and hence, there will be no "easy" reformulation with out any further assumption on $A$ (unless $P=NP$). $\endgroup$
    – Dirk
    Commented Jul 7, 2012 at 19:48
  • $\begingroup$ The goal of any reformulation that would be interesting to me would include a linear objective function. While the problem is NP-hard, the reformulation could be susceptible to various heuristics or other approximations. I know any formulation will not be an "easy" one, but I still wanted to see if any existed. $\endgroup$
    – Clark
    Commented Jul 7, 2012 at 20:58
  • $\begingroup$ Sorry, what do you denote by $\|\dot\|_0$? $\endgroup$
    – Dima Pasechnik
    Commented Jul 8, 2012 at 6:36

1 Answer 1

Reset to default
1
$\begingroup$

You can formulate this as an integer program. Let z be a vector of binary variables, and let Uj be upper bounds on the x variables. Hopefully you can derive some reasonably tight lower bounds based on the constraints Ax = b, but if not, use a suitably large value for each Uj. Then the following MIP will give you the minimal support that satisfies Ax = b:

min e'z // e is a vector of all ones Ax = b xj = Uj*zj <= 0 x >= 0, 0 <= z <= 1, z binary.

Note that I assumed x >= 0 here. If some or all of the x variables have lower bounds below 0, you can introduce nonnegative variables u and v, then let x = u - v do the some MIP formulation for the constraints Au - Av = b, adding a binary for each u and v variable.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .