Let $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m $. I have the following two problems:
P.1.
\begin{equation} \underset{x\in\mathbb{R}^n}{\text{minimize}} \| Ax-b \|_1 \\ \text{s.t. } \| x \|_{\infty} \leq 1 \end{equation}
P.2.
\begin{equation} \underset{x\in\mathbb{R}^n}{\text{minimize}} \| x \|_1 \\ \text{s.t. } \| Ax-b \|_{\infty} \leq 1 \end{equation}
How can one reduce each of those problems to a linear program?
This work like this: The $\infty$-norm constraints are straigtforward. In the first problem you write $$ -1 \leq x_i \leq 1 $$ or, more explicitely $$ x_i\leq 1\\-x_i\leq 1. $$ One could even just write $x\leq 1$ and $-x\leq 1$ with the all-ones vector. In the second problem you get $$ Ax\leq 1+b\\ -Ax\leq 1-b. $$ For the objective you introduce new variables: In the second case use $x^+$ and $x^-$ (which are to positive and the negative part of $x$, i.e. $x=x^+-x^-$) and use the objective $$ \sum_i x^+_i + x^-_i $$ and the constraints $x^+\geq 0$, $x^-\geq 0$. In the first case you could introduce $y=Ax-b$ and proceed like in the second case.
I may also suggest that you use the $\ell^1$-Houdini, the homotopy method from "A Primal-Dual Homotopy Algorithm for ℓ1-Minimization with ℓ∞-Constraints" (https://doi.org/10.1007/s10589-018-9983-4, http://www.optimization-online.org/DB_HTML/2016/10/5700.html) from Christoph Brauer to solve the second problem. Code is available at https://github.com/chrbraue/l1Houdini.
(By the way, the title contains the word "Frobenius" but the question does not seem to be about Frobenius norms…)
