How to show that a function is piecewise linear 
Let $$\begin{array}{rcl}  
z(t) & := & \min (c+t d)^T x  \\
 & \text{s.t.} & Ax \le b
  \end{array}$$
Show that $Z(t)$ is a concave, piecewise linear function of $t$.

I'm really not sure how to even start proving this, I would really appreciate some hints.
 A: $\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$.
