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

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.

• For brevity let's define $y=Ax-b$. We have $\|y\|_\infty = \max_i|y_i| = \max(\max_iy_i,\max_i-y_i) = \arg\min_{\substack{t\ge y_i\\t\ge-y_i}}t$. – Rahul Jan 3 '18 at 10:56

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.

• How do I start solving this problem? What should be my first step if I want to solve it without using existing LP solver softwares? I want to do it for the sake of understanding. Also I used cvx software whose computational time is rather high. Any suggestion which software should I use for this particular problem? – Christina Lemuix Jan 4 '18 at 22:13
• You can run the simplex algorithm using pen & paper (rather than silicon). – Rodrigo de Azevedo Jan 5 '18 at 2:46
• Could you elaborate a bit more please? – Christina Lemuix Jan 5 '18 at 8:40
• Algorithms can be run on pen & paper, if you have the patience. Try $m=3$ and $n=2$. – Rodrigo de Azevedo Jan 5 '18 at 10:28
• found the following matlab code that minimizes the infinity norm. Can you please help me understand what is going on here? Why are $f$, $Ane$ and $bne$ like that? A = randn(m,n); b = randn(m,1); % infinity norm f = [ zeros(n,1); 1 ]; Ane = [ +A, -ones(m,1) ; ... -A, -ones(m,1) ]; bne = [ +b; -b ]; xt = linprog(f,Ane,bne); x_lp = xt(1:n,:); – Christina Lemuix Jan 5 '18 at 13:10

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.

• Thanks Erwin. I am new to solving an optimization problem. So could you please tell me how do I formulate my cost function from the above information? – Christina Lemuix Jan 3 '18 at 12:33
• The cost function $f(x,t)$ is just $f(x,t) = t$ which is linear. Note that both $x$ and $t$ are decision variables, where $t$ is a scalar variable. The cost coefficients are 1 for $t$ and zero for the original $x$ variables. So your cost vector $c$ will be very sparse: one element with value 1 and the rest zero. – Erwin Kalvelagen Jan 3 '18 at 12:37
• So how do I define the Lagrangian in this case? – Christina Lemuix Jan 3 '18 at 12:46
• Why do you need a Lagrangian for an LP problem? Does not make sense to me. – Erwin Kalvelagen Jan 3 '18 at 12:47
• @ChristinaLemuix it cannot be solved by hand. It must be solved numerically. – Michael Grant Jan 3 '18 at 15:18