This is a classic question, its for a homework assignment, I have the solution but I've been breaking my head to understand how to approach the problem.
Minimize $||A\vec x - \vec b||_1$ subject to $||x||_\infty \leq1$
and the solution given is
Minimize $\textbf{1}^T$ subject to $-y \leq A\vec x - \vec b \leq y$ and $\textbf{-1} \leq x \leq \textbf{1}$
If anyone could shed some light on how to approach this problem...
HINT
The constraint $\|x\|_\infty \le 1$ means max of the coordinates of $x$ cannot be more than 1 in absolute value. How do you express this in terms of a regular inequality?
Also, think about what $\|Ax-b\|_1$ looks like if we have $y = Ax-b$?