5
$\begingroup$

P is a bounded polyhedron in $\mathbb{R}^n$, $a$ a vector in $\mathbb{R}^n$, and $b$ some scalar. Define $$Q = {x \in P | a'x = b}$$. Show that every extreme point in Q is either an extreme point of P or a convex combination of two adjacent extreme points of P.

Intuitively, this makes complete sense to me. For example, given the 2D case, Q is simple a line within the polyhedron P. Thus, its two intersections with P are either on extreme points, or on the "boundary" of two extreme points, which can be written as a convex combination of two adjacent extreme points.

I have absolutely no idea how to approach this and prove it. Any suggestions would be greatly appreciated!

$\endgroup$
1
  • $\begingroup$ Although the below answer to this question gives the main idea behind the proof, there are some not entirely trivial nuances concerning the existence of the adjacent extreme points in the second part. It is important to demonstrate that both exist using the fact that $P$ is bounded and moving along a line segment. For instance, see here: math.solverer.com/library/dimitris_bertsimas/… $\endgroup$ Dec 11 '21 at 18:29
4
$\begingroup$

Suppose $x$ is an extreme point in $Q$. If this point coincides with an extreme point in $P$, there is nothing to show.

Suppose it is not an extreme point in $P$.

Since it's an extreme point in $Q$, it is also a basic feasible solution, which means that $n$ of the constraints are active in $x$.

One of these constraints is $a'x = b$. the other active constraints are $n-1$ of those constraints that are associated with the polyhedron $P$.

Two adjacent extreme points are two points that by definition share $n-1$ constraints. Therefore, $x$ lies in the segment that lies in between those two extreme points.

$\endgroup$

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.