Converting absolute value program into linear program

Question

I have the generic optimization problem:

$$ \max c^T|x|$$

$$ \text{s.t. } Ax \le b $$

$x$ is unrestricted

How do I convert it into a linear programming problem?

Online I read something about letting $x$ equal the difference of 2 positive numbers but I could not intuitively grasp why that worked. Plus the example applied only to minimization problems where the $c^T$ entries are all greater than $0$.

I'm sort of stuck

Answer 1

I think the question you are trying to ask is this: If we have a set of linear constraints involving a variable $x$, how can we introduce $|x|$ (the absolute value of $x$) into the objective function?

Here is the trick. Add a constraint of the form $$t_1 - t_2 = x$$ where $t_i \ge 0$. The Simplex Algorithm will set $t_1 = x$ and $t_2 = 0$ if $x \ge 0$; otherwise, $t_1 = 0$ and $t_2 = -x$. So $t_1 + t_2 =|x|$ in either case.

On the face of it, this trick shouldn't work, because if we have $x = -3$, for example, there are seemingly many possibilities for $t_1$ and $t_2$ other than $t_1 = 0$ and $t_2 = 3$; for example, $t_1 = 1$ and $t_2 = 4$ seems to be a possibility. But the Simplex Algorithm will never choose one of these "bad" solutions because it always chooses a vertex of the feasible region, even if there are other possibilities.

EDIT added Mar 29, 2019

For this trick to work, the coefficient of the absolute value in the objective function must be positive and you must be minimizing, as in

min $2(t_1+t_2)+\dots$

or the coefficient can be negative if you are maximizing, as in

max $-2(t_1+t_2)+\dots$

Otherwise, you end up with an unbounded objective function, and the problem must be solved by other methods, e.g. mixed integer-linear programming.

(If I knew this before, I had forgotten. Thanks to Discretelizard for pointing this out to me.)

Answer 2

I realize this is old, but I just ran into this issue. Please see: http://lpsolve.sourceforge.net/5.1/absolute.htm, which has a great explanation of the solution (both for minimization and maximization of an absolute value), and helped me a lot.

Answer 3

I'm quite late to the party, but all current answers neglect an important point. The answers given here exposit tricks for converting an $L^1$-minimization problem into a linear program, introducing one or more auxiliary variables. If $A$ is square this is not the end of the world. The simplex algorithm runs in $O(n^3)$ time on an average case, so introducing an auxiliary variable multiplies the running time by 8. Bad but not horrible. However if your $L^1$ program is, for example

$$ \text{minimize} \hspace{0.5em} \lVert b - Ax \rVert_1 \hspace{0.5em} \text{s.t.} \hspace{0.5em} x \geq 0 $$

with $x \in \mathbb{R}^{100}$ and $A \in M_{64000 \times 100}(\mathbb{R})$ then by turning this into a linear program you've increased the dimensionality by a factor of (more than) 640, increasing the running time by a factor of more than a quarter-billion.

There are special algorithms for approximating $L^1$-minimization that have running times that depend on the dimensionality of the "intrinsic" variable, as opposed to the "trick" variable. Emmanuel Candés has one on his website; another is provided by the Python package CVXOPT.

Answer 4

A simpler way: if all $c_i$ are non negative, it is possible to reformulate the problem as:

$\min c^T y$

$ y_i\geq x_i$

$ y_i\geq -x_i$

$Ax \leq b$

If $c_i$ have the same sign you can easily adapt the same idea. I guess that also the case of generic sign can be dealt with.

Answer 5

$$ min |X_a-X_b| $$ can be written as

$$ min (X_{ab1}+X_{ab2}) $$

Such that

$$ X_a -X_b = X_{ab1} - X_{ab2}; $$

$$ X_{ab1}, X_{ab2} >=0; $$

Answer 6

$$ \begin{array}{rcr} \min_{\mathbf{u},\mathbf{x}} \mathbf{1}^\mathrm{T}\mathbf{u} & \mathrm{s.t.} & \mathbf{x}-\mathbf{u} \preceq \mathrm{0} \\ & & -\mathbf{x}-\mathbf{u} \preceq \mathrm{0} \\ & & \mathbf{Ax} \preceq \mathrm{b} \\ \end{array} $$

where $\preceq$ is meant to signify an element-wise less-than relationship. I also left out $\mathbf{c}$ since you can just scale the elements of $\mathbf{x}$ to be $c_i x_i$.

As for implementation, some software may require you to combine $\mathbf{x}$ with the dummy vector $\mathbf{u}$. In which case, the problem might look like

$$ \begin{array}{rcr} \min_{\mathbf{u},\mathbf{x}} \left[ \mathbf{1} \,\, \mathbf{0}\right]^\mathrm{T}\left[ \mathbf{u} \,\, \mathbf{x} \right] & \mathrm{s.t.} & \mathbf{x}-\mathbf{u} \preceq \mathrm{0} \\ & & -\mathbf{x}-\mathbf{u} \preceq \mathrm{0} \\ & & \mathbf{Ax} \preceq \mathrm{b} \\ \end{array} $$

You would then just take the portion of the final answer that corresponds to $\mathbf{x}$.