2 added 592 characters in body

Looking at a figure one is lead to the following algorithm which traces out the graph of $f$:

One may assume $a_1< a_2 < \ldots < a_n$. If $0 < a_1$ or $a_n < 0$ then $m:=\min_x f(x)=-\infty$. Otherwise for $x$ large negative one has $f(x)=a_1 x + b_1$ and for $x$ large positive one has $f(x)=a_n x+b_n$. Therefore put $x_1:=-\infty$, $j_1:=1$ and for $k\geq1$ define recursively $$r_i := {b_{j_k}-b_i\over a_i-a_{j_k}} \ (j_k < i \leq n),\quad x_{k+1}:=\min_{j_k < i \leq n}\ r_i\ ,\quad j_{k+1}:=\arg\min_{j_k < i \leq n} r_i\ .$$ When for the first time $a_{j_{k+1}}\geq0$ the minimum is found: One has $m=a_{j_k}x_{k+1}+b_{j_k}$.

As a bonus I propose the following algorithm which seems more sophisticated and is maybe faster:

Put $g_i(x):=a_i x+ b_i$ and denote by $g_i\wedge g_j$ the point of intersection of the two graphs. Assume for simplicity $a_1 < \ldots a_s<0 < a_{s+1} < \ldots < a_n$. Then apply in succession

1. Put $l:=1$, $\ r:=n$.
2. Put $(\xi,\eta):= g_l\wedge g_r\$.
3. If $l=s$ and $r=s+1$, goto 7.
4. Let $\tau:=\max_{l < i < r}\ g_i(\xi)\ ,\quad p:=\arg\max_{l < i < r}\ g_i(\xi).$
5. If $\tau\leq \eta$ goto 7.
6. If $p\leq s$ put $l:=p$, else put $r:=p$; then goto 2.
7. $m=\eta$.
1

Looking at a figure one is lead to the following algorithm which traces out the graph of $f$:

One may assume $a_1< a_2 < \ldots < a_n$. If $0 < a_1$ or $a_n < 0$ then $m:=\min_x f(x)=-\infty$. Otherwise for $x$ large negative one has $f(x)=a_1 x + b_1$ and for $x$ large positive one has $f(x)=a_n x+b_n$. Therefore put $x_1:=-\infty$, $j_1:=1$ and for $k\geq1$ define recursively $$r_i := {b_{j_k}-b_i\over a_i-a_{j_k}} \ (j_k < i \leq n),\quad x_{k+1}:=\min_{j_k < i \leq n}\ r_i\ ,\quad j_{k+1}:=\arg\min_{j_k < i \leq n} r_i\ .$$ When for the first time $a_{j_{k+1}}\geq0$ the minimum is found: One has $m=a_{j_k}x_{k+1}+b_{j_k}$.