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


Note that

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

  • $\begingroup$ Thanks for formal equations. Exactly what I did. $\endgroup$ – reicja May 22 '18 at 10:04
  • $\begingroup$ I see that someone deleted his response where I wrote it is solved. Thank you for the response anyway. $\endgroup$ – reicja May 22 '18 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.