# How to show that a function is piecewise linear

Let z(t) = min $(c+t d)^T x$ s.t $Ax <= b$ 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.

-
What is $T$? What connection does the objective have with $x$ in the constraint? –  copper.hat Dec 29 '12 at 21:54
Honestly, this is an exam question and no further information is given in the exercise. I am just guessing that everything is arbitrary. This is exactly how the exercise was written but I am thinking now that "T" is actually transpose ( and not a some other variable) –  bubbly Dec 29 '12 at 22:12
If you let $C=\{x|Ax\leq b\}$ and $\phi_x(t) = \langle c+td, x \rangle$, then you can write $z$ as $z(t) = \inf_{x \in C} \phi_x(t)$, the pointwise infimum of a collection of linear (hence concave) functions, which is concave. However, $z$ may 'easily' take the value $-\infty$. –  copper.hat Dec 30 '12 at 8:06
So actually set C doesn't matter and it could be any any set that respects some sort of condition for x? –  bubbly Dec 30 '12 at 9:30
Well, for concavity, the set $C$ doesn't matter. I am still struggling with piecewise linearity. –  copper.hat Dec 30 '12 at 9:33