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$$