= Solution
An extreme point is not a nontrivial convex combination of two distinct points of the set. Write $x=x^+-x^-$ with nonnegative parts and set $y=(x^+,x^-)$, $c=(1,1)$, $M=(A,-A)$, $a=b$. An extreme feasible point of this standard-form LP has at most $m$ positive coordinates (otherwise the corresponding columns are dependent and permit a two-sided feasible perturbation); an optimum may be chosen extreme, and cancelling simultaneous positive pairs gives an $x$ with at most $m$ nonzeros. For the final problem, fix $b=Ax^*$ for any optimum and replace $x^*$ by such a sparse minimum-$\ell^1$ solution of $Ax=b$; $f(Ax)$ is unchanged and the penalty cannot increase.
Back to article page
