4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why not? ( Why it doesn't work for the maximizing problem?) $\endgroup$ – Arman Malekzadeh Apr 21 '17 at 12:21
  • $\begingroup$ When you minimize $t$ you minimize $2x_1-3x_2$, which is what you want. But if you maximize $t$, nothing happens to $2x_1-3x_2$. $\endgroup$ – Kuifje Apr 21 '17 at 12:58
  • $\begingroup$ What is your answer if someone claims that there is another way to do the trick and this is just 1 way which fails for the maximization problem? $\endgroup$ – Arman Malekzadeh Apr 21 '17 at 13:05
  • $\begingroup$ If the question says only one of them can be converted to an LP and that you have converted problem $2$, you can conclude that it is not possible for problem $1$ by elimination. However, in a more general perspective, you have a good point, I will think about it. $\endgroup$ – Kuifje Apr 21 '17 at 14:55
  • $\begingroup$ I made an embarrassingly elementary mistake. I have corrected my answer. I apologize for the red herring. The teacher is correct. $\endgroup$ – Rodrigo de Azevedo Apr 23 '17 at 7:21
2
$\begingroup$

Let $f (x, y) := | 2 x - 3 y |$. Note that $f$ is convex. Its epigraph is the convex set

$$\left\{ (x,y,z) \in \mathbb R^3 \mid z \geq 2 x - 3 y \land z \geq - 2 x + 3 y \right\}$$

Hence, the minimization problem ("problem 2") can be written as the following linear program

$$\boxed{\begin{array}{ll} \text{minimize} & z\\ \text{subject to} & \begin{bmatrix} 2 & -3 & -1\\ -2 & 3 & -1\\ 4 & 1 & 0\\ 4 & -2 & 0\end{bmatrix} \begin{bmatrix} x\\ y\\ z\\ \end{bmatrix} \leq \begin{bmatrix} 0\\ 0\\ 4\\ 1\end{bmatrix}\\ & x, y, z \geq 0\end{array}}$$

The maximization problem ("problem 1") can be written in minimization form as follows

$$\begin{array}{ll} \text{minimize} & -|2 x - 3 y|\\ \text{subject to} & 4x + y \leq 4\\ & 4x - 2y \leq 1\\ & x, y \geq 0\end{array}$$

where the objective function $g (x, y) := - f (x, y)$ is concave. Thus, the epigraph of $g$ is non-convex and cannot be defined by the intersection of half-spaces. Although we cannot write "problem 1" as a linear program, we can write is as two linear programs, namely,

$$\begin{array}{ll} \text{minimize} & -2 x + 3 y\\ \text{subject to} & 4x + y \leq 4\\ & 4x - 2y \leq 1\\ & 2 x - 3 y \geq 0\\ & x, y \ge 0\end{array}$$

and

$$\begin{array}{ll} \text{minimize} & 2 x - 3 y\\ \text{subject to} & 4x + y \leq 4\\ & 4x - 2y \leq 1\\ & 2 x - 3 y \leq 0\\ & x, y \ge 0\end{array}$$

We solve both linear programs and then take the minimum of the two minima. Reversing the sign, we obtain the maximum of "problem 1".


Addendum

From Boyd & Vandenberghe:

enter image description here

enter image description here

$\endgroup$
  • 1
    $\begingroup$ According to the question, one of them cannot be written as a LP! How could this be possible?! $\endgroup$ – Arman Malekzadeh Apr 22 '17 at 14:03
  • $\begingroup$ @RodrigodeAzevedo Interesting! This definitely deserves more attention and begs the question: is OP's question from a book ? $\endgroup$ – Kuifje Apr 22 '17 at 15:54
  • $\begingroup$ @Kuifje My teacher at the university gave us this question! I don't know where it came from! $\endgroup$ – Arman Malekzadeh Apr 22 '17 at 17:13
  • 1
    $\begingroup$ @ArmanMalekzade Could you show all of the above answers to your teacher and get back to us? $\endgroup$ – Kuifje Apr 22 '17 at 17:59
  • $\begingroup$ @Kuifje Sure! The class is tomorrow, i'll speak with my teacher about this :) $\endgroup$ – Arman Malekzadeh Apr 22 '17 at 18:07

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.