Linear Programming with $ {L}_{1} $ Norm Constraint

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

As Brian notes, the problem is not convex. There are two workarounds for this.

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

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