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?

  • $\begingroup$ 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. $\endgroup$ – Aretino Feb 8 '16 at 20:59
  • $\begingroup$ @Aretino I've added the definition. It boils down to the same as what you've mentioned, the set isn't convex! Thanks. $\endgroup$ – Srinivas Eswar Feb 8 '16 at 21:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.