208k views
1 vote
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.

1 Answer

2 votes

Final answer:

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.

User Kiechlus
by
8.6k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories