# Different polyhedron definitions

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?

## 1 Answer

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

• 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. – independentvariable May 29 '18 at 0:22