LP: New way of minimizing sum of absolute values

453 Views Asked by At

Original Optimization:

Let say I want to minimize below function:

minimize

$\left|a_1x_1+a_2x_2-c_1\right| + \left|b_1x_1+b_2x_2-c_2\right|$

subject to:

$x_1^{lower} \le x_1 \le x_1^{upper}$

$x_2^{lower} \le x_2 \le x_2^{upper}$

Solutions online: I have seen that the proposed solutions are mainly to introduce an auxiliary variables $t_1$ and $t_2$, and try to minimize $(t_1 + t_2)$ subject to some constraints around $t_1$ and $t_2$ values. (e.g. this post).


Can below Linear Programming reformulation work?

But here is another possibility with seems simpler and effective. I am not sure what am I missing and why nobody has suggested this:

maximize

$a_1x_1+a_2x_2 + b_1x_1+b_2x_2$

subject to:

$a_1x_1+a_2x_2 \le c_1$

$b_1x_1+b_2x_2 \le c_2$

$x_1^{lower} \le x_1 \le x_1^{upper}$

$x_2^{lower} \le x_2 \le x_2^{upper}$


1

There are 1 best solutions below

2
On BEST ANSWER

No, it doesn't. Let's consider an extreme case where $$\min |x_1 +x_2 - 1|+ |x_1 +x_2 - 1|$$

$$1 \le x_1 \le 1$$

$$1 \le x_2 \le 1$$

which is feasible.

Your method would construct the following feasible set.

$$x_1 + x_2 \le 1$$ $$x_1 + x_2 \le 1$$ $$1 \le x_1 \le 1$$

$$1 \le x_2 \le 1$$

which is not feasible.