Why is the Fenchel conjugate of a piecewise linear function piecewise linear? Consider the function:
$$ f: x \mapsto
  \begin{cases}
    a_1 x + b_1 & x \le \frac{b_1 - b_2}{a_2 - a_1}  \\
a_i x + b_i &  \frac{b_{i-1} - b_i}{a_i - a_{i-1}} \le x \le \frac{b_i - b_{i+1}}{a_{i+1} - a_i} \quad \forall 1 \le i \le n-1  \\
a_nx + b_n & x \ge \frac{b_{n-1} - b_n}{a_n - a_{n-1}}
  \end{cases} \, $$
where we can assume that $a_1 < \dots < a_n$. This is question 3.36 in Boyd and Vandenberghe. The solutions manual (p. 55 of the PDF) claims that:

For $a_i ≤ z ≤ a_{i+1}$, the supremum in the
  definition of $f^∗$ is reached at the breakpoint between the segments $i$ and $i + 1$, i.e.,
  at the point $(b_{i+1} − b_i)/(a_{i+1} − a_i)$, so we obtain 
  $$f^∗(z) = −b_i − (b_{i+1} − b_i)\frac{y − a_i}{ a_{i+1} − a_i}$$
  where $i$ is defined by $a_i ≤ z ≤ a_{i+1}$.

Question: Why is this claim true? How can we prove that claim without knowing anything about the $b$'s or the relative sizes of the $(a_i - a_{i-1})$'s?
What I have figured out so far about $f^*(z)$ is included below, but it doesn't seem strong enough to allow me to reach the same conclusion.
Note: This is a follow-up to a previous question.
Work so far: One can write (note: $c_{i,i+1}$ is meant to denote the breakpoint between the $i$th and $(i+1)$st segments, specifically $(b_i - b_{i+1})/(a_{i+1} - a_i)$):
$$\begin{array}{rcl}
  f^*(z) & = & \sup_{x \in \mathbb{R}}[ xz - f(x) ] \\
& = & \max_{i \in [n]} \left\{
  \begin{array}{l}
   \displaystyle \sup_{x \le c_{12}} [ xz - a_1 x - b_1] \,, \\
\displaystyle \sup_{c_{12} \le x \le c_{23}} [xz - a_2 x - b_2] \,, \\
\vdots \\
\displaystyle \sup_{x \ge c_{n-1, n}} [xz - a_n x - b_n]
  \end{array}
\right\}  \\
& = & \max_{i \in [n]} \left\{
  \begin{array}{l}
   \displaystyle \sup_{x \le c_{12}} [ (z - a_1)x - b_1] \,,  \\
\displaystyle \sup_{c_{12} \le x \le c_{23}} [(z - a_2) x - b_2] \,, \\
\vdots \\
\displaystyle \sup_{x \ge c_{n-1, n}} [(z - a_n) x - b_n]
  \end{array}
\right\}  \,. \\
\end{array}$$
We note that the supremum terms over $[c_{i-1, i} , c_{i, i+1}]$ will always be finite (i.e. for $1  < i < n$), since we are always taking the supremum of a continuous function over a compact set (closed interval), making the extreme value theorem applicable. Thus, when checking to see when (if ever) $f^*(z)$ is unbounded, it suffices to only consider the terms corresponding to suprema over $(-\infty, c_{12}]$ and $[c_{n-1, n}, \infty)$.
Because a linear function is unbounded \textit{from above} (we don't need to consider whether it's unbounded from below since we're taking a supremum) as $x \to -\infty$ if and only if its slope is negative, we have that:
$$   \left[ \sup_{x \le c_{12}} [ (z-a_1) x - b_1 ] = +\infty  \quad \iff \quad z - a_1 < 0 \right] \quad \quad \implies \quad \quad f^*(z) = +\infty \text{ whenever }z < a_1 \,, $$
since the maximum over a finite set will always be $+\infty$ if one of the elements of that set is $+\infty$.
Similarly, since a linear function is unbounded from above as $x \to \infty$ if and only if its slope is positive:
$$  \left[   \sup_{x \ge c_{n-1,n} } [ (z-a_n) x - b_n ] = +\infty \quad \iff \quad z - a_n > 0   \right] \quad \quad \implies \quad \quad f^*(z) = +\infty \text{ whenever }z > a_n \,.  $$
Therefore we only need to do any work calculating $f^*(z)$ for $z$ in the closed interval $[a_1, a_n]$.
When $z \in [a_1, a_n]$, $z - a_1 \ge 0$, so the slope of $(z-a_1)x - b_1$ is non-negative, and thus the supremum of the first term occurs at the right endpoint ($c_{12}$). Similarly, $z-a_n \le 0$, so the slope of $(z - a_n)$ is non-positive, and the supremum of the last term occurs at the left endpoint ($c_{n-1, n}$). 
For the terms $1 < i < n$, consider that the slope is non-positive, and thus the supremum occurs at the left endpoint ($c_{i-1, i}$) of the interval in question, only when $z \le a_i$, whereas the slope is non-negative, and the supremum occurs at the right endpoint ($c_{i,i+1}$) of the interval only when $z \ge a_i$. Therefore, when restricted to $[a_1, a_n]$, we have for $f^*(z)$ that:
$$\begin{array}{rcl}
  f^*(z) & = & \max_{i \in [n]} \left\{
  \begin{array}{l}
   (z - a_1)c_{12} - b_1 \,, \\
\vdots\\
    \begin{cases}
      (z-a_i)c_{i-1,i} - b_i & z \in [a_1, a_i] \\
      (z-a_i)c_{i,i+1} - b_i & z \in [a_i, a_n]
    \end{cases} \\
\vdots \\
(z - a_n)c_{n-1, n} - b_n
  \end{array}
\right\}  \,. \\
\end{array}$$
Specifically, for a $z$ within a given $[a_i, a_{i+1}]$, we have:
$$\begin{array}{rcl}
  f^*(z) & = & \max_{i \in [n]} \left\{
  \begin{array}{l}
   (z - a_1)c_{12} - b_1 \,, \\
\vdots\\
(z - a_{i-1})c_{i-1, i} - b_{i-1}\\
       (z-a_i)c_{i,i+1} - b_i   \\
(z - a_{i+1}) c_{i, i+1} - b_{i+1} \\
\vdots \\
(z - a_n)c_{n-1, n} - b_n
  \end{array}
\right\}   \\
& = & \max_{i \in [n]} \left\{
  \begin{array}{l}
   (z - a_1) \frac{b_1 - b_2}{a_2 - a_1} - b_1 \,, \\
\vdots\\
(z - a_{i-1})\frac{b_{i-1} - b_i}{a_i - a_{i-1}} - b_{i-1}\\
       (z-a_i)\frac{b_i - b_{i+1}}{a_{i+1} - a_i} - b_i   \\
(z - a_{i+1}) \frac{b_i - b_{i+1}}{a_{i+1} - a_i} - b_{i+1} \\
\vdots \\
(z - a_n)\frac{b_{n-1} - b_n}{a_n - a_{n-1}} - b_n
  \end{array}
\right\} \,. \\
\end{array}$$
Note that for $j < i$, $z - a_j > z - a_i > 0$ due to the fact that $a_1 < \dots < a_n$. Similarly, for $j > i$, $z - a_j < 0  < z - a_i$. With the information above, it's very unclear to me how one could evaluate this expression further to get the result of Boyd and Vandenberghe.
 A: 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.
