# Getting rid of absolute value bars to rewrite a linear program in standard form

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 abolute value is a simple and useful concept. If you don't want to use it, you may find an alternative form which also works. However I expect that things only become more complicated. My advise is not to spend time and effort on this aspect of your program. – M. Wind Oct 28 '18 at 5:23
• @M.Wind I agree that doing this for every question is overkill- But it's important for the OP to understand that linear programs with absolute values are still standard linear programs, and that the absolute values do not invalidate the linearity. – DreamConspiracy Oct 28 '18 at 6:38
• |x| = $\sqrt {x^2}$ – William Elliot Oct 28 '18 at 8:45
• @WilliamElliot while that is an interesting approach, I should have clarified that I need the problem to remain a linear program, so all of the constraints should remain linear too. – BSplitter Oct 28 '18 at 16:35
• @BSplitter indeed you need to introduce more variables, one set per absolute value – LinAlg Oct 28 '18 at 19:41

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.