# Absolute value constrained optimization

Let

$$f(x) := \begin{cases} 3|x| & \text{if } x > 0\\ \,\,\,|x| & \text{otherwise}\end{cases}$$

Given $d_i > 0$,

$$\begin{array}{ll} \text{minimize} & \displaystyle\sum_i f(d_i - x_i)\\ \text{subject to} & x_{i} \leq x_{i+1}\end{array}$$

Can someone give me any advice how to solve it?

I first tried to rewrite this function with the absolute value trick into the standard linear program, which did not work for me, because the system seemed to have empty solution set. I could have made a mistake of course. -- it was due to typo.

I would also consider approximation of $f$ but don't have any experience with this and don't know where to. Thank you.

The edit was done in response to an already deleted answer. EDIT: Solved with

$\displaystyle \min_{x} f(x)$ s.t.

$Ax \leq b$

is equivalent to

$\displaystyle \min_y y$, s.t.

$y \geq -3x$,

$y \geq x$,

$Ax \leq b$.

$$f (x) := 2 |x| + x$$
$$\sum_{i=1}^n f (d_i - x_i) = 2 \sum_{i=1}^n |d_i - x_i| + \sum_{i=1}^n d_i - \sum_{i=1}^n x_i = 2 \| \mathrm x - \mathrm d \|_1 + 1_n^\top \mathrm d - 1_n^\top \mathrm x$$
Introduce optimization variable $\mathrm y \in \mathbb R^n$, replace $\| \mathrm x - \mathrm d \|_1$ with $1_n^\top \mathrm y$ in the objective function, and then add the inequality constraints $-\mathrm y \leq \mathrm x - \mathrm d \leq \mathrm y$. We then have a linear program in variables $\mathrm x, \mathrm y \in \mathbb R^n$ and with objective $1_n^\top \left( 2 \mathrm y - \mathrm x \right)$. Note that the constant term $1_n^\top \mathrm d$ was discarded.