How to convert minimize $\| Ax - b \|_\infty$ to an equivalent linear program step by step?

Question

Given this question:

$$\text{minimize } \| Ax - b \|_\infty$$

Then this question is equivalent to

$\text{minimize } \max |Ax - b|$ = $\text{minimize } \max\limits_i |a_i^Tx - b_i|$

Let $t = |a_i^Tx - b_i|$, $t$ a fixed number

Then $ -t \leq a_i^Tx - b_i \leq t$

Then we are able to convert the original problem into the following: \begin{alignat*}{2} \text{minimize } t \\ \text{subject to } & -t \leq a_i^Tx - b_i \leq t \end{alignat*}

But somewhere along the way we lost our "max"

Then there to me this is no different from solving the question $\text{minimize } |Ax - b|$

What is a good justification for the disappearance of our max?

Answer 1

$ -t \leq a_i^Tx - b_i \leq t$ being true for all i is equivalent to $\max\limits_i |a_i^Tx - b_i| \leq t$

Minimizing t then drives $\| Ax - b \|_\infty$ as small as possible. It's really that simple.

Answer 2

Along @ Mark's answer, The answer is $\infty$ unless $A =0$. If $A=0$ the answer is $||b||_{\infty}$.

The reason is because, I can drag $Ax$ to $+\infty$ or $-\infty$ along any singular vector of A. To see why write $A$ using the SVD as $\Sigma \sigma_{i}u_{i}v_{i}^{T}$. Multiply by $x$ and set $x = tv_{i}$ and let $t \rightarrow \infty$. Try and see if you can work it out from here