If you look at the definition geometrically (on $\mathbb{R}$) it states that a function is convex if each point of the graph $(x, f(x))$ is below any line that adjoins graph points $(a, f(a))$ and $(b, f(b))$ where $a<x<b$. In other words, for any ordered triple $a<x<b$
the point $(x,f(x))$ is below the lint through $(a,f(a))$ and $(b,f(b))$.
Now think about the graph of your function - look at $x<1$... look at $x>1$... look at $x=1$...
Consider any $a_i, a_{i+1}$ and $z \in [a_i, a_{i+1}]$. No doubt, that
$$
f(x) =
\begin{cases}
a_ix+b_i, & x \in [\frac{b_{i-1}-b_i}{a_i - a_{i-1}};\
\frac{b_{i}-b_{i+1}}{a_{i+1} - a_{i}}]=c_i
\\
a_{i+1}x+b_{i+1}, & x \in [\frac{b_{i}-b_{i+1}}{a_{i+1} - a_{i}};\
\frac{b_{i+1}-b_{i+2}}{a_{i+2} - a_{i+1}}]= c_{i+1}
\end{cases}
$$
We are interested in calculating
$$
f^*(z)=\sup_{x}\ (xz-\max_j(a_jx+b_j))
$$
Step 1. Let's prove, that
$$
\sup_{c_i \cup c_{i+1}}\ (xz-\max_{j = i, i+1 }(a_jx+b_j))
=
x^*z-a_ix^*-b_i
=
x^*z-a_{i+1}x^*-b_{i+1}
$$
where $x^* = \frac{b_{i}-b_{i+1}}{a_{i+1} - a_{i}}$. Since $c_i \cup c_{i+1}$ is a compact, we can write $max$ instead of $sup$. Since $z - a_i >0$:
$$
\text{argmax}_{c_i}\ (xz-a_ix-b_i)
=
\text{argmax}_{c_i}\ (x(z-a_i)-b_i)
=x^*
$$
And because $z - a_{i+1} < 0$:
$$
\text{argmax}_{c_{i+1}}\ (xz-a_{i+1}x-b_{i+1})
=
\text{argmax}_{c_{i+1}}\ (x(z-a_{i+1})-b_{i+1})
=x^*
$$
It's true, that $a_ix^*+b_i = a_{i+1}x^*+b_{i+1}$. Q.E.D.
Step 2.
It remains only to prove, that the following is true:
$$
\sup_{R\setminus \{c_i, c_{i+1}\}}\ (xz-f(x))
<
\sup_{c_i \cup c_{j+1}}\ (xz-\max_{j = i, i+1}(a_jx+b_j))
=
$$
Define $c_1 = [- \infty; \frac{b_1-b_2}{a_2-a_1}]$, $c_2 = [\frac{b_1-b_2}{a_2-a_1}; \frac{b_2-b_3}{a_3-a_2}]$. Since $z-a_1 > 0, z-a_2 > 0$:
$$
\sup_{c_1}\ (xz-a_1x-b_1)
= \sup_{c_1}\ (x(z-a_1)-b_1)
= \frac{b_1-b_2}{a_2-a_1}(z-a_1)-b_1
= \frac{b_1-b_2}{a_2-a_1}(z-a_2)-b_2
$$
$$
\sup_{c_2}\ (xz-a_2x-b_2)
= \sup_{c_2}\ (x(z-a_2)-b_2)
= \frac{b_2-b_3}{a_3-a_2}(z-a_2)-b_2
$$
No doubt, that
$$
\sup_{c_1} < \sup_{c_2}
$$
By induction you can verify, that if $z \in [a_i; a_{i+1}]$
$$
\sup_{c_1} < \sup_{c_2} < ... < \sup_{c_i}
$$
That's why we have the following:
$$
\sup_{c_1 \cup c_2 \cup ...\cup c_{i-1}} < \sup_{c_i \cup c_{i+1}}
$$
Similarly, one can check, that:
$$
\sup_{c_{i+2} \cup c_{i+3} \cup ...\cup c_n} > \sup_{c_i \cup c_{i+1}}
$$
Q.E.D.
All in all, we show, that
$$
\sup_{x}\ (xz-\max_j(a_jx+b_j))
= x^*z-a_ix^*-b_i
$$
I don't think that is very strict and elegant proof, but I hope, that it is at least correct.
Best Answer
$\newcommand\R{\mathbb R} $Let us start by associating with each $t\in\R$ a linear form $\omega_t$ with $\omega_t(x) = (c+td)^T x$. Denote by $\Omega\colon \R\to (\R^n)^*$ the map sending $t$ to $\omega_t$.
Now $z(t)$ is obtained by minimizing the linear form $\omega_t$ along the polyhedron $Q=\{\,x\in\R^n\,|\, Ax\le b\,\}$. I'll assume that $Q$ is bounded and hence a polytope, otherwise the minima defining $z$ might not exist. Convex geometry tells us, that $\omega_t$ will attain its minimum on a face of $Q$. This face is determined by the cone of the normal fan $\mathcal N(Q)$ that contains $\omega_t$.
If you take the subdivision of $(\R^n)^*$ given by the normal fan of $Q$ and pull it back to $\mathbb R$ along $\Omega$, you get a partition of $\R$ into intervals $I_1,\dots,I_k$ such that for all $t$ in a fixed $I_j$, all linear forms $\omega_t$ attain their minimum at the same face of $Q$. (Think of this as $\Omega$ embedding the real line into $(\R^n)^*$, where you intersect this line with the cones of the normal fan.) Hence, letting $x_0$ be some point on this face, you have $z(t) = \min_Q \omega_t(x) = \omega_t(x_0)$ for all $t\in I_j$. You can see that $\omega_t(x_0)$ is an (affine) linear function in $t$ and hence $z$ is a piecewise-linear function on $\R$ with linearity regions $I_1,\dots,I_k$.