# minimization of a convex piecewise linear function [closed]

Let $$f(x) = \left\{ \begin{array}{l} {a_1}x + {b_1} & if\,0 \le {x_1} \le x \le {x_2}\\ {a_2}x + {b_2} & if\,{x_2} < x \le {x_3}\\ \vdots \\ {a_n}x + {b_n} & if\,{x_{n - 1}} < x \le {x_n} \end{array} \right.$$ be a piecewise continuous function and $0\leq a_1\leq a_2\leq \cdots \leq a_n$.

Formulate the problem of miniimizing $f(x)$ in terms of linear programming

• Is this problem a homework problem? – Geoff Oxberry Sep 30 '13 at 17:30

Note that $f(x)=\max_{i} a_{i}x+b_{i}$. You can then reformulate the problem as
$\min_{t,x} t$
$t \geq a_{i}x + b_{i}$, $i=1, 2, \ldots, n$.
• Your comment doesn't make sense as a sentence in English, so I'm not sure what you're asking. If you're concerned that the minimum of the LP might be outside of the interval $[x_{1},x_{n}]$, you can simply add the constraints $x \geq x_{1}$ and $x \leq x_{n}$. Pick any numbers that you want for $a_{1}$, $b_{1}$, $a_{2}$, and $b_{2}$ and try it. – Brian Borchers Sep 30 '13 at 16:14