2

In this video MIT professor says that you need to split $x$ into $x^+$ and $x^-$ such that $x = x^+ - x^-$ (at 53:42) to convert any LP to standard form.

Standard LP form is:

$max \ c^Tx$

$Ax = b$

$x \geq 0$

It does not make any sense to me. I do not understand what is happening. I will appreciate if you can explain.

thank you

Community
  • 1
YohanRoth
  • 1,437

1 Answers1

3

When you're converting an optimisation problem from general form to standard form, this is how you deal with variables which have no sign constraints.
If $x$ is a variable without a sign constraint, that means that $x$ can take on both positive and negative values. So both $x \geq 0$ and $x < 0$ are possible. But in standard form, we want all our variables to be non-negative. To deal with this problem, we introduce two variables in place of $x$, both of which are positive such that $x$ could take the whole spectrum of positive and negative values.
If we write $x = x^+ - x^-$ where both $x^+, x^- \geq 0$ are non negative, then if $x^+ \geq x^-\ , x \geq 0$ and if $x^- < x^+ \ ,x <0$. This way we meet the criteria for converting our variable (variables) into standard form.

Hikaru
  • 941
  • so I still don't get what is the problem of writing it as x >= 0 – YohanRoth Jun 02 '17 at 05:55
  • 1
    You're removing valid possibilities from your feasible set. When there is no sign constraint on $x$, there could be feasible points with $x<0$ and maybe one of them is optimal. In that case, if you try to solve the linear program with just $x \geq 0$ then you will not find the best solution. – Hikaru Jun 02 '17 at 06:00