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?



How to minimize l1-norm constrained by "infinity norm"
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…)


