Consider this optimization problem:
$$\begin{matrix}\min & |x_1| + |x_2| && \\ s.t & a_{11}x_1 + a_{12}x_2 & = b_1 \\ & a_{21}x_1 + a_{22}x_2 & = b_2 \end{matrix}$$ Which $a_{ij}$ and $b_j$ are constant and fixed real number and $x_i\in\mathbb{R}$. Can i solve this problem with linear programming methods? If i can, how?

  • $\begingroup$ This system does not have a guaranteed solution, is that ok? $\endgroup$ – user130512 Feb 26 '14 at 16:07
  • $\begingroup$ yes, for example if $a_{11}=a_{21}$ and $a_{12}=a_{22}$ but $b_1 \neq b_2$. $\endgroup$ – Stefano Feb 26 '14 at 17:18
  • $\begingroup$ math.stackexchange.com/questions/432003/… $\endgroup$ – Opt Dec 17 '17 at 13:29

You can! Set $x_1=x_1^+ - x_1^-$ where $x_1^+ \geq 0$ and $x_1^- \geq 0$ then $|x_1|=x_1^+ + x_1^-$. Same for $x_2$.

This works since it is a minimization problem.

  • 1
    $\begingroup$ To be more clear: every real number can be written as a difference. If $x_1$ is negative the problem is going to set $x_1^-=x_1$ and $x_1^+=0$ since it wants to minimize their sum. $\endgroup$ – Stefano Feb 26 '14 at 16:16

You can divide the problem up in four parts. One part is minimizing $x_1 + x_2$ subject to your constraints and $x_1, x_2 \geq 0$.

Another part would be minimizing $-x_1 + x_2$ subject to your constraints and $x_1 \leq 0$, $x_2 \geq 0$, and so on. One part for each quadrant.

Each part can be solved by linear programming methods, and the lowest minimum of all is the minimum of the original problem.


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.