Let $U$ be a polyhedron. I usually see the definition as:

$i) \quad U = \{x \in R^n: Dx\leq d \}$

But I also have seen in another paper that we can define this as:

$ii) \quad U = \{x \in R^n_+: Dx= d \}$

I don't understand how we can use the second definition. For example how can I show the following set with the second definition: $\{x_1: 0 \leq x \leq 1\}$? Will I add a nonnegative slack variable to make the inequality an equality?


Note that $\mathbb{R}_+^n = \{ x \in \mathbb{R}^n : x_i \geq 0 \}$. Consider the inequality $$ A x \leq b, \; x \in \mathbb{R}^n. $$

Decompose $x$ into its positive and negative parts $x^+, x^- \geq 0$ such that $x = x^+ - x^-$. Then you can write $ A(x^+ - x^-) \leq b $

and augment it with a slack variable $s$ so that $A(x^+ - x^-) + s = b, s \geq 0$. This gives you a new equivalent definition:

$$ \underbrace{\begin{bmatrix} A & -A & I \end{bmatrix}}_{=: D} \underbrace{\begin{pmatrix} x^+ \\ x^- \\ s \end{pmatrix}}_{=: x'} \leq b, \\ x' \geq 0. $$

In your example, you have

$$ 0 \leq x^+ - x^- \leq 1 \Rightarrow \begin{cases} x^+ - x^- + s_1 = 1 \\ x^- - x^+ - s_2 = 0 \end{cases}, \quad \; x^+, x^-, s \geq 0. $$

  • $\begingroup$ Thank you! As I see, it will be costly to change the notation considering the increase in the number of variables. But if I have a theorem for one of the definitions, I will use this trick. $\endgroup$ – independentvariable May 29 '18 at 0:22

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.