How to convert mathematical program into an LP?

Question

This might be a stupid question. For that, I'm truly sorry. But I appreciate any help!

minimize (max {2x-4, |x|})

subject to -3 <= x <= 6

Answer 1

If $-3\le x\le 2$ then it is clear that $2x-4\le |x|.$ (Why? Because $2x-4\le 0\le |x|.$) Thus

$$\max_{-3\le x\le 2}\{2x-4,|x|\}=\max_{-3\le x\le 2} |x|=3.$$ Now, if $2\le x \le 6$ then note that $2x-4=|x|=x$ if and only if $x=4.$ It is $2x-4\le |x|$ if $2\le x\le 4$ and $2x-4\ge |x|$ if $4\le x\le 6.$ Thus

$$\max_{2\le x\le 4}\{2x-4,|x|\}=\max_{2\le x\le 4} |x|=4$$ and

$$\max_{4\le x\le 6}\{2x-4,|x|\}=\max_{4\le x\le 6} 2x-4=8.$$

Thus the answer is $8.$

Answer 2

In general, mathematical programming with linear inequalities and a convex, piecewise linear, objective function can be converted to an LP by the following method:

Introduce a new variable $z={\rm max}\{ 2x-4,-x,x\}$. This is equivalent to minimizing $z\in \mathbb{R}$ subject to the inequalities \begin{align} z\geq& 2x-4,\\ z\geq& -x,\\ z\geq& x. \end{align} So the linear program is to minimize $z$ subject to those three constraints along with your original constraint for $x$.