Linear function on a non convex domain I want to find the minimum of a linear function $F$ over a domain $D \subseteq \mathbb{R}^n$ which is the intersection of $n$ sets $D_i$ of the form $f(x_{i-1}) \leq x_i \leq g(x_{i-1})$, where $f(t), g(t)$ are continuous piecewise lienar functions.
Such a domain $D$ is in general nonconvex. 
I am not familiar with the field of optimization, and I hope the question is not trivial; I tried looking in the literature for similar problems, but I could not find an answer.
Since $F$ is linear, its minimum is in one of the vertices of the polytope $D$, and I claim in particular that it must lie on one of the vertices of the convex hull of $D$.
If what I claim is true, then the only difficulty would be finding the convex hull of such a domain. I would like in particular to describe the convex hull as the intersection of half spaces $A_i x \leq b_i$.
Since the convex hull operation does not commute with the intersection, one cannot simply take the convex hull of $D_i$'s and intersect them.
So I have two questions:
1) Is it true that the minimum lies on one of the vertices of the convex hull?
2) How can one compute the convex hull of a domain like the one I described as the intersections of halfspaces?
EDIT: a typo and reformulated the question for clarity
 A: Partial answer: about to the first question:
Let's make a change of variables to aid intuition: let $y_i = x_1+...+x_i, (i=1,..., n)$, then the region $D_i$ is described as $f_i(y_{i-1}) \le y_i - y_{i-1} \le g_i(y_{i-1})$, and, taking $\tilde f_i(u) = f_i(u) + u$, etc., we can write $D_i$ condition defining $D_i $ as $\tilde f_i(y_{i-1}) \le y_i \le \tilde g_i(y_{i-1})$. I'll drop the $\tilde \; $ going foward.
Let's also assume that the linear function $f$ to be minimized is not constant.
Since the condition defining $D_i$ bounds each dimension, one at a time, $D = \cap_i D_i$ is compact, so $f$ attains a minimum in $D$. Since the gradient of $f$ is not null, the point that affords the minimum cannot be in the interior of $D$, so it is a boundary point.  
What you call a "vertix" can be made more precise. A point of a set is call extreme iff it is not contained in the relative interior of a segment with end-points in the set. For example, in two dimensions, consider the set $ D = \{(x_1,x_2) | -2 \le x_1 \le 2 \text{ and } -1 \le x_2 \le max(|x_1|,1-|x_1|) \}$ the point $(0,1)$ is a boundary point that is not extremal, because the segment with endpoints $(-1,1), (1,1)$ has endpoints in $D$, and contains $(0,1)$ in is relative interior.
(Note: the concept of extreme points appears in relation to convex sets. I used it as it would apply to the convex hull of the underlying set.)  
Now if $f$ attains its minimum at a non-extereme point, then it must be constant along the segment containing the non-extemal point ($f$ restricted to the segment is affine, so it is minimized at the boundaries, or it is constant). Continue the segment until it hits a face of $D$ and argue by induction on the affine dimension of the polytope $D$.
Minkowski's theorem (or Krein-Milman theorem in locally convex Housdorf vector spaces) says that a compact convex is the convex hull of its extreme points, but if $K = \text{ closed convex hull of }D$, then the extreme points of $K$ must lie in $D$, else they will be convex combinations of other points in $K$. 
So, to sum up:
1) $f$ attains its minimum at extreme points of $D$
2) the convex hull of $D$ is generated by the exteme points of $D$
$$ \ll \gg \fallingdotseq  \doteqdot \doteqdot \doteqdot \doteqdot \risingdotseq \ll \gg$$
As for the second part (computing the convex hull of $D$), your problem is essentially 2 dimmensional, because the functions involved depend on only one variable. If $g_i^* = \text{ least concave majorant of }g_i$, i.e.:$g_i^*(u) = \inf\{h(u)| h \text{ is concave and } g_i(\zeta) \le h(\zeta) \text{ for all }\zeta\}$, then $g_i^*$ is convave. Similarly define $f_i^* = \text{ greatest convex minorant of } f_i $.
Because $g_i$ is piecewise linear, so is $g_i^*$, and because it is a least concave majorant, it can be written as
$$ g_i^*(u) = \min_t\{ b_{it} + m_{it}\; u \}$$
for a finite family of affine functions $u \mapsto b_{it} + m_{it}\:u$.  
Likewise, $f_i^*$ can be written as
$$  f_i^*(u) = \max_s\{ \beta_{is} + \gamma_{is}\; u \}$$
for some finite family of affine functions.
There are computer algorithms to compute the convex envelope of a finete set of points on the plain, i.e.: ponts in 2D. I suspect those algorithms can be make to work to find the concave majorant, and convex nimorants above (this is the point where my answer has a gap....).   
Why looking at $f_i^*, g_i^*$? Because the convex hull of $D$ can be written in terms of these functions as:
$$ f_i^*(y_{i-1}) \le y_i \le g_i^*(y_{i-1}) \;\;\;(i=1,..,n) \tag{1}, $$
and, recalling the structure of $f_i^*, g_i^*$, (1) is a description of the convex hull of $D$ in terms of hyperplanes. In all its glory, the convex hull of $D$ is:  for all $i$,
$$   \begin{align}
y_i &\le b_{it} + m_{it}\; y_{i-1}  &\text{ for all $t$}\\
 \beta_{is} + \gamma_{is}\; y_{i-1} &\le y_i &\text{ for all $s$}
\end{align} \\
$$.
