I would like to find the optimal set $ \{ x_i \} $ given $ L $ and $ \{ a_i \} $ that minimizes the problem below. My first thought was to use linear programming. Is there a transformation that makes it possible, or do I need a more general optimization technique?

$$ \min_{x_i} \left[ 2\sum_i | x_i | + \max_i | x_i + a_i | \right]$$ $$ \mathrm{s.t.} \sum_i (x_i + a_i) \le L$$


1 Answer 1


You haven't told us what set $i$ ranges over, so I'll just assume $i=1, 2, \ldots, n$.

A standard trick in LP formulation of problems with absolute values is to introduce auxiliary variables and constraints with the basic idea that

$\min | x | $

is equivalent to

$\min t $

$t \geq x $

$t \geq -x $

Applying that idea to your problem, introduce auxiliary variables $t_{i}$, $i=1, 2, \ldots n$, and $s$. Then formulate the problem as:

$\min 2 \sum_{i=1}^{n} t_{i} + s $

subject to

$t_{i} \geq x_{i}$, $i=1, 2, \ldots n$.

$t_{i} \geq -x_{i}$, $i=1, 2, \ldots n$.

$s \geq x_{i}+a_{i} $, $i=1, 2, \ldots, n$.

$s \geq -(x_{i}+a_{i}) $, $i=1, 2, \ldots, n$.

$\sum_{i=1}^{n} (x_{i}+a_{i}) \leq L$

  • $\begingroup$ Thanks, but what happened to the $\max$? $\endgroup$
    – user2303
    Jul 2, 2013 at 20:29
  • 3
    $\begingroup$ $s$ is larger than any of the $x_i+a_i$ and $-(x_i+a_i)$, so it is larger than their max. What Brian has shown you is a standard trick to convert a problem like yours into a linear problem with linear constraints -- the sort of problem for which there are many standard implementations. $\endgroup$ Jul 2, 2013 at 21:30
  • $\begingroup$ As Wolfgang explained, $s$ will be greater than or equal to $ | x_{i}+a_{i} | $ for $i=1, 2, \ldots, n$. Also, since $s$ is being minimized in the objective, it will come out equal to the maximum of the absolute values of $x_{i}+a_{i}$. $\endgroup$ Jul 3, 2013 at 3:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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