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?
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|$.
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$.