10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $c^Tx$ means $c_1x_1+\cdots+c_nx_n$, but what does the $|x|$ mean? it would have to denote a vector for $c^T|x|$ to make sense. $\endgroup$ – coffeemath Jun 29 '13 at 0:51
  • $\begingroup$ Absolute value of the individual terms of X not the norm of the vector $\endgroup$ – frogeyedpeas Jun 29 '13 at 1:09
  • 1
    $\begingroup$ @coffeemath Most likely he/she means $\Vert \mathbf{c}^\mathrm{T}\mathbf{x} \Vert_1$. $\endgroup$ – AnonSubmitter85 Jun 29 '13 at 1:09
  • $\begingroup$ @coffeemath My mistake. I meant $|\mathbf{c}^\mathrm{T} \mathbf{x}|$. $\endgroup$ – AnonSubmitter85 Jun 29 '13 at 1:19
  • $\begingroup$ You can always convert a maximization problem to a minimization problem by inverting the cost function. Both problems will give you the same answer. $\endgroup$ – AnonSubmitter85 Jun 29 '13 at 1:31
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This doesn't work with glpsol (from glpk) forced to use simplex algorithm. I give a shortened version because MathProg is too verbose: maximize abspos+absneg when y<=10 & x<=y & v=x-y & abspos-absneg=v & y>=0 & x>=0 & abspos>=0 & absneg>=0 It gives the error PROBLEM HAS UNBOUNDED SOLUTION. The problem that this translates: maximize |x-y| when y<=10 & x<=y & x,y >=0 is well defined. Thus the transformation doesn't work (or I did it wrong). $\endgroup$ – Eponymous Apr 22 '14 at 5:40
  • $\begingroup$ This approach makes more sense to me. $\endgroup$ – tuxdna Apr 2 '15 at 11:06
  • 1
    $\begingroup$ @Eponymous The reason your approach fails is because this technique only works for minimization problems: we have to do something different for maximization objectives. $\endgroup$ – Discrete lizard Mar 29 at 9:54
  • 1
    $\begingroup$ What works for the maximisation case is to add the constraint $t_1+t_2=x$ and optimise $t_1-t_2$ $\endgroup$ – Discrete lizard Mar 29 at 10:00
  • $\begingroup$ @Discretelizard The method outlined above should work for either minimization or maximization, no change needed. $\endgroup$ – awkward Mar 29 at 12:51
5
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Where did $$min |X_a - X_b|$$ come from? $\endgroup$ – tuxdna Apr 2 '15 at 11:07
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\min c^T y$

$ y_i\leq 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.

$\endgroup$
  • $\begingroup$ This formulation only makes sense if $x_i$ is positive. If, for example, $x_i=-1$, there exists no $y_i$ that's both weakly smaller than $-1$ and weakly larger than $+1$. ... and of course, if you already know that $x_i$ is positive, then there's no need to worry about the absolute value. $\endgroup$ – mimuller Apr 17 '18 at 2:12
  • $\begingroup$ Actually, I just noted that this problem crept in with the edit... will try to undo the edit to reflect the original idea. $\endgroup$ – mimuller Apr 17 '18 at 2:14
  • $\begingroup$ This (original approach, before the edit by @kvathe) works for positive $c_i$, but I can't adapt it to negative $c_i$. Any leads, @AndreaCassioli? $\endgroup$ – mimuller Apr 17 '18 at 2:17
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The simplex algorithm runs in poly time?! $\endgroup$ – Dirk Mar 18 '17 at 0:54
0
$\begingroup$

The top answer correctly solves this issue for the minimisation case, but does not work for maximisation. Why it fails is easy to see. Suppose we are given a constant $x$, then the program

$\begin{align} \max t_1+t_2 \quad\text{ s.t }\quad t_1 - t_2 &=x \\ t_1,t_2&\geq 0 \end{align}$

is in fact unbounded when $x\geq 0$, as we can take $t_1=Y$ for any $Y\geq x$ and set $t_2 = Y - x$ so that we have a valid solution of cost $2Y-x$ and this can be arbitrarily large, as $x$ is constant.

What does work for the maximisation case is the following, and is based on roughly the same idea:

$\begin{align} \max t_1-t_2 \quad \text{s.t.} \quad t_1+t_2 &= x\\ t_1,t_2&\geq 0 \end{align}$

If $x\geq 0$, then setting $t_1=x$ and $t_2=0$ yields the optimum, which has value $x+0 = x$. If $x\leq 0$, then setting $t_1=0$ and $t_2= -x$ yields the optimum, which has value $0-x = -x$. So, the solution to this program is indeed $|x|$. As before, simply change $x$ by the objective of the part that you want to take the absolute value of to get the solution to your program.


I said that both approaches are based on the same idea, but I haven't seen anyone make that idea explicit, so I will do so now. The main trick is to get two parts that should sum up together to $x$ and add the sum of them to the objective, where one of the parts is negated. To see the similarities more clearly, we can rewrite the max form as follows:

$\begin{align} \max t_1+t_2 \quad \text{s.t.} \quad t_1-t_2 &= x\\ t_1&\geq 0 \\ t_2&\leq 0 \end{align}$

The main difference between min and max is how each variable gets selected. We want to ensure that the optimal solution 'selects' one part and sets it to $x$ and the other to $0$.

For min, as we want to minimize $t_1+t_2$, we have to bound $t_1$ and $t_2$ from below to not get an unbounded solution and then minimization will pick the absolute value, as other methods of satisfying the equation will only increase the value of $t_1+t_2$ and hence are suboptimal.

For max (in the most recent form), we want to maximise $t_1+t_2$. $t_1$ is bounded from above by the equality, as $t_1 = x+t_2\leq x$. $t_2$ is bounded from above directly. So we get a feasible result. Again, the optimal choice is to pick one as $x$ or $-x$ and set the other to $0$.

$\endgroup$

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.