# Constrained optimization with max and absolute values in objective function

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

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$

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