[Math] Rewriting maximization and minimization of $|2x_1-3x_2|$ as linear programs

convex optimizationlinear programmingnon-convex-optimizationoptimization

$$\begin{array}{ll} \text{maximize} & |2x_1-3x_2|\\ \text{subject to} & 4x_1+x_2 \le 4\\ & 2x_1-x_2 \le 0.5\\ & x_1,x_2 \ge 0\end{array} \tag{Problem 1}$$


$$\begin{array}{ll} \text{minimize} & |2x_1-3x_2|\\ \text{subject to} & 4x_1+x_2 \le 4\\ & 2x_1-x_2 \le 0.5\\ & x_1,x_2 \ge 0\end{array} \tag{Problem 2}$$


According to the question, one of them can be rewritten as a linear program (LP), and the other one cannot. The question asks the reader to determine which one can be rewritten as an LP, and why the other one cannot.

I've never converted to an LP an optimization problem whose objective function contains an absolute value. So, I think I have no way of determining the one that can be rewritten as an LP. But, I know the simplex method and I can solve an LP using it.

Best Answer

For problem $2$: replace the objective function by a new variable $t\ge 0$, and add the constraints \begin{cases} 2x_1-3x_2 \le t \\ -2x_1 +3x_2 \le t \end{cases} These constraints are equivalent to $-t \le 2x_1-3x_2 \le t$, and so the absolute value is taken into account.

Since you are minimizing $t$, you are minimizing $\mid 2x_1-3x_2 \mid $ indeed.

It is not difficult to see that this does not work if you are maximizing $t$.