Rewrite $\min _{z \in \mathbb{R}^{n}}\|z\|_{1}$ s.t. $B z=d$ as an equivalent standard LP problem.

Question

I want to rewrite the following problem

$$ \min _{z \in \mathbb{R}^{n}}\|z\|_{1} s.t. B z=d \ where\ \boldsymbol{B} \in \mathbb{R}^{\boldsymbol{m} \times \boldsymbol{n}} and \ \boldsymbol{d} \in \mathbb{R}^{\boldsymbol{m} \times \mathbf{1}}$$ into an equivalent LP problem in the form of

$$ \begin{array}{c} \min c^{T} x \\ A x=b \\ x \geq 0 \end{array} $$ $\|z\|_{1}$ is the norm 1 of vectors. The issue here is how to express this norm and how to find A,b, and c. I cannot think of a way to linearise and find these parameters. Any suggestions??

Answer 1

Hint: Write $z_j=z_j^+-z_j^-$, where $z_j^+\ge 0$ and $z_j^-\ge 0$. Then replace $|z_j|$ with $z_j^++z_j^-$ in the objective.