4
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Thanks, but what happened to the $\max$? $\endgroup$ – user2303 Jul 2 '13 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$ – Wolfgang Bangerth Jul 2 '13 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$ – Brian Borchers Jul 3 '13 at 3:43

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.