Consider the optimization problem $\min_{x\in S}f(x)$ where $f(x)=\max_{i=1,...,m}{a_ix+b_i}$ and $S$ is a polyhedron contained in $R^n$.
First I want to show that the function $f$ is a convex function.
What I have done so far: We know $\max$ function is convex and $a_ix+b_i$ is linear so it is also convex, hence $f(x)$ is convex. Now I am stuck at the $\min_{x\in S}f(x)$ part. I am not sure how I can handle the $\min$ function with $S$ region.
Second I want to show that the optimization problem $\min_{x\in S}f(x)$ can be solved by a linear optimization problem. I don't have any idea on how to approach this one.
Any helps would be appreciated!
Notice that $$\min_{x\in S} \max_{i=1,\ldots, m} a_ix+b_i$$
can be rewritten as
$$\min_{x \in S, z \in \mathbb{R}} z$$
Subject to $$z \ge a_ix+b_i, i = 1, \ldots, m$$
Since $S$ is a polyhedral, the optimization problem is a linear program.
The equivalence can be seen by at optimality, one of the inequality must hold and that would attain the maximal of $\max_{i=1, \ldots, m}a_i x+b_i$.