Formulating Linear Program: Separating Hyperplane

Question

Consider a polyhedron $P$ that has at least one extreme point.

Suppose that we are given the extreme points $x^i$ and a complete set of extreme rays $w^j$ of P. Create a linear programming problem whose solution provides with a separating hyperplane that separates $P$ from the origin, or allows us to conclude that none exists.

Idea: By Resolution/Representation Theorem:

I write Polyhedron $P$ as: $P=\{x \in R^n\mid x=\sum_{i=1}^{k} \lambda_i x^{i}+ \sum_{j=1}^{r} \theta_jw^j, \lambda_i \geq 0, \theta_j \geq 0, \sum_{i=1}^{k} \lambda_{i}=1\}$

So I think the idea is we want to minimize the distance between a point $x \in P$ and $0$, or $||x||_1$. So I

Write Primal LP as follows:

min $z_1+....z_n$ subject to

$x=\sum_{i=1}^{k} \lambda_i x^{i}+ \sum_{j=1}^{r} \theta_jw^j$

$\sum_{i=1}^{k} \lambda_{i}=1$

$\lambda_i \geq 0$

$\theta_i \geq 0$

$z_i \geq x_i$

$z_i \geq -x_i$

I want to the Dual LP of this, however, I don't know exactly how to (I tried doing a similar thing to Dantzig Wolfe, but couldn't do it).

Thus, if anyone could let me know what the Dual LP and how the Dual LP will perhaps give us a solution that provides us with a separating hyperplane that separates P from the origin as I'm really lost on what I'm doing. I tried my best to show what I have so far. thanks.

Answer 1

The approach described above assumed $0 \notin P$. Here is the general case.

A hyperplane is such $\{ x \in \mathbb{R}^n\ s.t. \ c^t x = c_0 \},$ where $c \in \mathbb{R}^n, \ c \neq 0$ and $c_0 \in \mathbb{R}$.

There exists a hyperplane that satisfies: $$ c^t 0 \leq c_0$$ and $$c^t x \geq c_0, \ \forall x \in P.$$ Hence, we get: $$c_0 \geq 0.$$

Using the resolution theorem you mentioned, we must also have:

$$c^t x^i \geq c_0,\ \forall i,$$

and

$$c^t w^j \geq 0, \forall j.$$

Therefore, to find the separating hyperplane, we could solve the following LP: $$ \max_{c, c_0} c_0 \ s.t. $$ $$c^t x^i \geq c_0,\ \forall i,$$ $$c^t w^j \geq 0, \forall j,$$ $$c_0 \geq 0.$$

This will not work. Indeed, $c=0$ and $c_0 = 0$ is always a solution. Moreover, if $0$ is an extreme point of $P$ then $\max c_0 = 0$, therefore having a maximum of $0$ cannot be used to determine the existence or not of the hyperplane. The problem is that we do not include the constraint $c \neq 0.$ So, here is a modification. Introduce the variable $z$ such that $z_k \geq c_k$ and $z_k \geq -c_k$. Clearly, $z \geq 0.$ Now consider the following LP.

$$ \min_{c, c_0, z} \sum_{k=1}^n z_k \ s.t. $$ $$c^t x^i \geq c_0,\ \forall i,$$ $$c^t w^j \geq 0, \forall j,$$ $$z_k \geq c_k, \forall k,$$ $$z_k \geq -c_k, \forall k,$$ $$c_0 \geq 0.$$

If there exists an hyperplane with $(c_0,c), \ c \neq 0$ then clearly $\min_{c, c_0, z} \sum_{k=1}^n z_k > 0.$

On the other hand, if $\min_{c, c_0, z} \sum_{k=1}^n z_k = 0$, this implies that $z = 0$, hence $c=0.$

Answer 2

Here is a suggestion based on your idea. I will consider the case where $0 \notin P.$

A hyperplane is such $\{ x \in \mathbb{R}^n\ s.t. \ c^t x = c_0 \},$ where $c \in \mathbb{R}^n, \ c \neq 0$ and $c_0 \in \mathbb{R}$.

As $0 \notin P$, there exists a hyperplane that satisfies: $$ c^t 0 < c_0$$ and $$c^t x \geq c_0, \ \forall x \in P.$$ Hence, we get: $$c_0 > 0,$$ and we can set $c_0 = 1$ wlog.

Using the resolution theorem you mentioned, we must also have:

$$c^t x^i \geq 1,\ \forall i,$$

and

$$c^t w^j \geq 0, \forall j.$$

Therefore, to find the separating hyperplane, we can solve the following LP: $$ \max_{c} 0 \ s.t. $$ $$c^t x^i \geq 1,\ \forall i,$$ $$c^t w^j \geq 0, \forall j.$$