I'm attempting to reformulate a linear program into standard form. Part of this problem requires me to eliminate absolute values from all of my variables. Specifically, I have the problem: \begin{align*} &\min_{x\in \mathbb{R}^2} 2x_1 + 3|x_2-10|\\ &\text{Subject to } |x_1+2| + |x_2| \le 5 \end{align*} I have determined the following:
Let $$x_2^+:=\max\{x_2-10,0\}$$
and
$$x_2^-:=\max\{-x_2+10,0\}$$
Then $$|x_2-10| = x_2^++x_2^- \text{ and } x_2-10 = x_2^+-x_2^-$$ Here, we note that $x_2^+, x_2^- \ge 0$.
What I need is some way to express $|x_2|$ in terms of $x_2^+$ and $x_2^-$ that doesn't use absolute value bars.
I've tried several things on this front, but I keep getting stuck. Do I need to introduce more variables to make this work? Any hints or insight would be greatly appreciated.
Note: I don't actually need to know the solution to this linear program.
The first step is usually to introduce new variables, but with inequalities: \begin{align*} &\text{minimize} &&2x_1 + 3t_1\\ &\text{Subject to } &&t_2 + t_3 \le 5,\\ &&&|x_2-10|\le t_1,\\ &&&|x_1+2|\le t_2,\\ &&&|x_2|\le t_3. \end{align*} Note that the solution is the same (obviously an upper bound plus equalities are included).
The second step is to observe that e.g. $$ |x_2-10|\le t_1\iff -t_1\le x_2-10\le t_1 $$ etc, that is each absolute value inequality can be replaced by two linear ones.
The price to pay: increased dimension.
The gain (?): linear programming software.