# Converting nested absolute value into linear programming

I am having trouble writing the following optimization problem as a linear program (LP)

$$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$

where $a \in \mathbb Z^2$ is given. I tried adding the following constraints and replacing objective function to min $U$, but it did not work out.

$$x_{i}-a_{i}\le y_{i}$$

$$a_{i}-x_{i}\le y_{i}$$

$$y_{1}-y_{2}\le U_{}$$

$$y_{2}-y_{1}\le U_{}$$

This sounds like a homework problem, so just hints here.

We'd usually just transform $x_1$ and $x_2$ into two new variables, $$\begin{array}{ccccc} x_1^{'}~{\equiv}~x_1-a_1 & & \text{and} & & x_2^{'}~{\equiv}~x_2-a_2 \end{array} ,$$such that the new problem is$$\min{\left| \begin{array}{c} {\left|x_1^{'}\right|}-{\left|x_2^{'}\right|} \end{array} \right|}.$$ Then, the absolute values imply symmetries such that we don't need to consider some parts of the domain.

We may ignore:

1. $x_1^{'}<0$, because it's degenerate with $x_1^{'}>0$ under $\left|x_1^{'}\right|$.

2. $x_2^{'}<0$, because it's degenerate with $x_2^{'}>0$ under $\left|x_2^{'}\right|$.

3. $\left|x_1^{'}\right|<\left|x_2^{'}\right|$, because it's degenerate with $\left|x_1^{'}\right|>\left|x_2^{'}\right|$ under $\left|\left|x_1^{'}\right|-\left|x_2^{'}\right|\right|$.

Typically you can specify these sorts of domains to ignore in terms of constraints.

Then, since the degenerate cases have been removed, the objective function's just$$\min{ \left( {x_1^{'}}-{x_2^{'}} \right) }.$$