$\begingroup$
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?
$\endgroup$ 21 Answer
$\begingroup$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$$
$\endgroup$
