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$

2 Answers 2

3
$\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$
3
  • $\begingroup$ Many years later but I have a question here: How is $c_0 = c_k = z_k = 0$ not always a feasible point in the second optimization problem? I thought the first was correct to be honest. $\endgroup$
    – qp212223
    Oct 2, 2022 at 3:19
  • $\begingroup$ It is, but to ensure the existence of the hyperplane, we need to have $c \neq0$ $\endgroup$
    – user605486
    Oct 7, 2022 at 15:57
  • $\begingroup$ What if we just maximize the sum of components of vector ‘c’ for a fixed $c_0 > 0$ subject to constraints that $c’ x^{i} \geq c_0$ and $c’ w^{i} \geq 0$, then if we get an optimal solution we know that we have a hyperplane, else we can’t find one (0 might be in the polyhedron) $\endgroup$
    – 28ADY0901
    Oct 26, 2023 at 0:59
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$
2
  • $\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, 2019 at 15:26
  • $\begingroup$ @BoyWonder, see below for an update $\endgroup$
    – user605486
    Nov 11, 2019 at 23:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .