Linear Programming with $ {L}_{1} $ Norm Constraint When solving a linear programming problem in MATLAB using linprog of the form
$$ \min c^T x $$
subject to
$$ Ax \leq b, \; \left\| x \right\|_{1} = 1 $$
if we need to enforce the additional constraint that $L_1$ norm of $x$ is $1$, or $\|x\|_1=1$, how can this be converted into a set of inequations of the above form so that the trivial solution $x=0$ can be avoided?
 A: As Brian notes, the problem is not convex. There are two workarounds for this.


*

*It seems like the right hand side of $||x||_1=1$ is arbitrary. Maybe you can replace it with $x_1=1$ (if you know that $x_1\geq  0$)? Or solve two problems: one with $x_1=1$ and one with $x_1=-1$? This only works if you know $x_1 \neq 0$.

*You can use binary variables to deal with the nonconvexity:
$$ \sum y_i = 1$$
$$ y_i = x_i + s_i$$
$$ y_i = -x_i + t_i$$
$$ 0 \leq s_i \leq M b_i$$
$$ 0 \leq t_i \leq M (1-b_i)$$
$$ y_i \geq 0$$
$$ b_i \in \{0,1\}$$
The big-M constraints set either $s_i=0$ or $t_i=0$. Consequently, $y_i = x_i$ or $y_i = -x_i$. Since $y_i\geq 0$, we obtain $y_i = |x_i|$.
A: Unfortunately, this problem cannot be formulated as an LP, since the constraint $\| x \|_{1}=1$ describes a non-convex set and the feasible set of linear programming problem is always a convex set.  
A: We have
$\|x\|_1= |x_1| + |x_2| + ... + |x_n|$
which is equivalent to
$ \max\{x_1,-x_1\}+\max\{x_2,-x_2\}+...+\max\{x_n,-x_n\}$
So $\|x\|_1=1$ can be substituted as
$y_i \geq x_i$
$y_i \geq -x_i$
$y_i \geq 0$
Then the minimum $L_1$ norm solution for $x$ is given by $y$.
