# Formulating Linear Program: Separating Hyperplane

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.

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

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

• Hi @Pebeto so you are just considering the case where $0 \notin P$?. What happens if $0 \in P$? Thanks – Boy Wonder Nov 11 '19 at 15:26
• @BoyWonder, see below for an update – Pebeto Nov 11 '19 at 23:52