I am reading Bertsimas and Tsitsiklis which says that minimization of piecewise linear functions(maximum of linear functions) can be reduced to linear programing. For example,
$$\min |x|+|y|$$ is equivalent to
$$\min \max(x,-x)+\max(y,-y)$$
which is equivalent to
$$\min \max(\pm x \pm y)$$
which is finally the Linear program
$$\min z$$
$$s.t. \quad z \geq \pm x \pm y$$
If I undestand correctly $|x| -|y|$ is not convex and hence not piecewise linear. However, can't I still write
$$\min |x|-|y|$$ as
$$\min \max(x,-x)-\max(y,-y)$$
which is same as
$$\min z-w$$
$$s.t.$$
$$ \quad z \geq x$$
$$ \quad z \geq -x$$
$$ \quad w \geq y$$
$$ \quad w \geq -y$$
which is a linear program. Am I making any mistake or is it true that this problem can infact be reduced to a LP.
Best Answer
In the first example, where you minimize $z$ subject to the four inequalities $z \ge \pm x \pm y$, you don't really enforce the equation $z = |x|+|y|$. You only enforce the inequality $z \ge |x| + |y|$; however, because we're minimizing $z$, the optimal solution will always push it down to $|x|+|y|$ exactly.
In the second example, the inequalities $z \ge \pm x$ and $w \ge \pm y$ together enforce the inequalities $z \ge |x|$ and $w \ge |y|$. To minimize $z - w$, we are free to make $w$ arbitrarily large - much larger than $|y|$ - and this will improve the objective value. This means that our resulting linear program is not equivalent to minimizing $|x|-|y|$. (And, in the absence of other constraints, it will simply be unbounded: we can make $z-w$ arbitrarily negative.)
This distinction is hard to see in this bare-bones example, where the optimization problem is unbounded either way. But suppose we try to minimize $|x|-|y|$ subject to $-1 \le y \le 2$ (or whatever). Now, there is a unique optimal solution: $x=0$ and $y=2$. However, minimizing $z-w$ subject to $z \ge \pm x$ and $w \ge \pm y$ (and $-1\le y \le 2$ as before), we are still free to make $w$ as large as possible. This shows that we haven't truly succeeded in representing the objective function $|x|-|y|$.