Question

We have a polyhedron P which is described by its set of extreme points: {x1, x2, · · · , xJ } and extreme rays: {d1, d2, · · · , dI }.

Given a vector ˆx, create a linear program that will find a hyperplane separating ˆx from P if ˆx is not in P , or will conclude no such separation is possible if ˆx ∈ P . Prove the validity of your LP.

Answer 1

To separate a vector ˆx from a polyhedron P using linear programming, construct an LP that maximizes the equation of a hyperplane over ˆx subject to constraints ensuring all points and directions of P are on one side of the hyperplane. If ˆx is not in P, a feasible solution exists; otherwise, the LP will be infeasible.

Step-by-step explanation:

To create a linear program (LP) that separates a vector ˆx from the polyhedron P if ˆx is not in P, we assume that P is represented by its set of extreme points (vertices) {x1, x2, ··· , xJ} and extreme rays {d1, d2, ···, dI}. The goal is to find a hyperplane defined by a vector w and a scalar b such that w^T x + b < 0 for all x in P, and w^T ˆx + b > 0 if ˆx is not in P. Conversely, if ˆx is in P, no such hyperplane exists, and the LP will indicate this by being infeasible.

The linear program can be written as:

1. Maximize w^T ˆx + b
2. Subject to w^T x_j + b <= 0 for all j = 1, ..., J
3. Subject to w^T d_i <= 0 for all i = 1, ..., I

To prove the validity of this LP, if ˆx is indeed outside the polyhedron, there will be a feasible solution to the LP where the objective function is positive, defining a separating hyperplane. If ˆx is inside P, then for any w and b satisfying the constraints, the objective function will not be positive, signaling no separation is possible. Therefore, the LP either finds a separating hyperplane or proves that the separation is impossible.