How can the infinity norm minimization problem be rewritten as a linear program?

Question

I have been trying to solve the infinity norm minimization problem and after quite a bit of reading I have found out that infinity norm minimization problem can be re-written as linear optimization problem. I have been trying to understand how and why it is done so, but failing miserably. Could anyone please explain me about this and also tell how the cost function looks like?

My optimization problem looks like following: (I have to solve for $x$ when $A$ and $b$ are given.)

$$\mbox{minimize} \quad \|A x - b\|_{\infty}$$

which can be rewritten as follows

\begin{split}\begin{array}{lccl} \mbox{minimize} & t & &\\ \mbox{subject to} & Ax + t \mathbb 1 - b & \geq & 0,\\ & A x - t \mathbb 1 - b & \leq & 0, \end{array}\end{split}

where $\mathbb 1$ is a vector of ones.

Answer 1

If we want to minimize $|x|$ (for a scalar $x$) we can linearize this as:

$$\begin{align} \min\>& t\\& -t \le x \le t\end{align}$$

This means that if we want to minimize $||Ax-b||_{\infty}$ we can write:

$$\begin{align} \min\>& t\\& -t \le (Ax-b)_i \le t&&\forall i\end{align}$$

You need to split this into two different inequalities:

$$\begin{align} \min\>& t\\& -t \le (Ax-b)_i &&\forall i\\ &(Ax-b)_i \le t&&\forall i\end{align}$$

There are some other LP formulations shown here.

Answer 2

To complement Erwin Kalvelagen's answer, we have the following optimization problem in $\mathrm x \in \mathbb R^n$

$$\begin{array}{ll} \text{minimize} & \|\mathrm A \mathrm x - \mathrm b\|_\infty\end{array}$$

where $\mathrm A \in \mathbb R^{m \times n}$ and $\mathrm b \in \mathbb R^m$ are given. Let $\mathrm a_i^\top \in \mathbb R^n$ denote the $i$-th row of $\rm A$.

Introducing decision variable $t \in \mathbb R$ and rewriting in epigraph form, we then obtain the following constrained optimization problem in $\mathrm x \in \mathbb R^n$ and $t \in \mathbb R$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \|\mathrm A \mathrm x - \mathrm b\|_\infty \leq t\end{array}$$

which can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \displaystyle\max_{1 \leq i \leq m} | \mathrm a_i^\top \mathrm x - b_i | \leq t\end{array}$$

which can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & | \mathrm a_1^\top \mathrm x - b_1 | \leq t\\ & | \mathrm a_2^\top \mathrm x - b_2 | \leq t\\ & \qquad \vdots\\ & |\mathrm a_m^\top \mathrm x - b_m | \leq t\end{array}$$

which can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & -t \leq \mathrm a_1^\top \mathrm x - b_1 \leq t\\ & -t \leq \mathrm a_2^\top \mathrm x - b_2 \leq t\\ & \qquad\quad \vdots\\ & -t \leq \mathrm a_m^\top \mathrm x - b_m \leq t\end{array}$$

which can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & -t 1_m \leq \mathrm A \mathrm x - \mathrm b \leq t 1_m\end{array}$$

where the optimal $\rm x$ and the optimal $t$ are the minimizer and the minimum of the original problem, respectively.