# Polyhedral Sets and $min$-function

I'm asked to verify if the following set is polyhedral,

$$X = \{[x_1;x_2]: min(x_1,x_2) \leq 0\}$$

Definition of a polyhedral set,

A set $Y$ is polyhedral if $Y = \{y: Ay \leq b\}$, for finite $A$ and $b$.

I think that it isn't polyhedral but I'm not sure how to go about proving it. By looking at the feasible space we can see that it fills up 3 quadrants (the second, third and fourth) and I believe we can't represent this as a finite number of inequalities in $x_1$ and $x_2$.

I also tried introducing a slack variable $\tau$ such that,

$$\begin{split} min(x_1,x_2) &\leq \tau \\ \tau &\leq 0 \end{split}$$

But in this case we'll need to introduce some branching constraints to select which one of $x_1$ and $x_2$ is the minimum and less than $\tau$.

Could someone give me pointers on how to approach this?

• What is your definition of polyhedral set? If you define that as the intersection of finitely many halfspaces, then it must be a convex set, which your $X$ is not. – Aretino Feb 8 '16 at 20:59
• @Aretino I've added the definition. It boils down to the same as what you've mentioned, the set isn't convex! Thanks. – Srinivas Eswar Feb 8 '16 at 21:07