[Math] piecewise linear minimization equivalent to linear programming

Question

Why is

\begin{equation}
\begin{aligned}
& \min\max_{i=1,\ldots,n}
& &a_i^Tx+b_i\\
\end{aligned}
\end{equation}

equivalent to an LP

\begin{equation}
\begin{aligned}
& \min
& &t\\
& \text{s.t.} & & a_i^Tx+b_i\leq t \ \ \ \ \ \ \ i = 1,\ldots, n\\
\end{aligned}
\end{equation}

?

I am confused about in the equivalent LP form, where is "max"? How to say both are equivalent if ignoring "max" in the constraint in the LP?

Answer 1

---

From here

---

For example,

minimise $f(x) = \max(3x-4,2x-1)$

is equivalent to:

minimise t

subject to

$3x-4 \le t$

$2x-1 \le t$

Note that

$$f(x) = 3x-4 \iff x \ge 3$$

So if we have $x = 5$, then $f(5) = 11$ and

$$11 \le t$$

$$9 \le t$$