2
$\begingroup$

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: enter image description here

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.