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.
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|$.