KEMBAR78
Polyhedron Corner Points Explained | PDF | Vector Space | Vertex (Geometry)
Scribd
Upload
85 views2 pages

Polyhedron Corner Points Explained

The document defines and compares three concepts related to the "corner points" of a polyhedron: 1) Extreme points - vectors that cannot be written as a convex combination of other vectors in the polyhedron. 2) Vertices - vectors for which there exists a hyperplane such that the vector is the only point on or above the hyperplane within the polyhedron. 3) Basic feasible solutions - vectors for which there are n linearly independent active constraints determining the vector within the polyhedron. The document proves that these three concepts are equivalent, so they all characterize the "corner points" of a polyhedron, but from different geometric or algebraic perspectives.

Uploaded by

ወንድሙ ዘገዬ
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
85 views2 pages

Polyhedron Corner Points Explained

The document defines and compares three concepts related to the "corner points" of a polyhedron: 1) Extreme points - vectors that cannot be written as a convex combination of other vectors in the polyhedron. 2) Vertices - vectors for which there exists a hyperplane such that the vector is the only point on or above the hyperplane within the polyhedron. 3) Basic feasible solutions - vectors for which there are n linearly independent active constraints determining the vector within the polyhedron. The document proves that these three concepts are equivalent, so they all characterize the "corner points" of a polyhedron, but from different geometric or algebraic perspectives.

Uploaded by

ወንድሙ ዘገዬ
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Extrem Points, Vertices and basic feasible solutions

Serkan Hoten s
Department of Mathematics, San Francisco State University, San Francisco

September 9, 2003

Denitions

We will clarify what we mean by a corner point of a polyhedron. We will dene three objects: extreme points, vertices, and basic feasible solutions. The rst two are geometric denitions. The last one is algebraic. Then we will show that they are all the same. But this is convenient since we will have three dierent ways of knowing and describing corner points, and we will choose the best depending on the context. Denition 1. A vector x of a polyhedron P is called an extreme point if there are no two vectors y = x and z = x in P such that x is a convex combination of y and z. This means an extreme point is a vector which does not lie on the line connecting any two vectors in P . Note that we did not use the inequality description of P in this denition. Denition 2. A vector x of a polyhedron P is called a vertex if there exists c such that c x < c y for all y = x P . This means P is contained entirely on one side of the hyperplane dened by c, and the only point that is on this hyperplane is x. A polyhedron is given by P = {x Rn : Ax b}. If x is a vector in P , then some of these equations could be satised with equality: ai x = bi . Such a constraint is called active or binding at x . Note that if there are 1

n linearly independent constraints active at x , the vector x is uniquely determined by these active constraints. Denition 3. A vector x is called a basic solution if the active constraints at x contain the equality constraints, and among the active constraints there are n linearly independent ones. Moreover, if x is actually in P , then it is called a basic feasible solution. Example 1.1. Give a two dimensional geometric example with degeneracy.

Equivalence of the denitions

Theorem 2.1. Let x be a point of a polyhedron P . Then the following are equivalent. a) x is a vertex. b) x is an extreme point. c) x is a basic feasible solution. Proof. a) = b). Suppose c is the supporting hyperplane of the vertex x . If x is a convex combination of two vectors y and z in P , then x = y + (1 )z for some 0 < < 1. This means c x = c y + (1 )c z. But c x < c y and c x < c z. A contradiction. b) = c). Suppose x is a not BFS. We will show that x is not an extreme point. Since x is feasible but not a BFS, the active constraints at x cannot have n linearly independent constraints. If we assume that the active constraints are the rst k constraints, then the system of equations ai x = 0 for i = 1, . . . , k has a nontrivial solution d. Now for very small we dene y = x + d and z = x d. Both y and z are in P for suitably chosen , and x = (1/2)y + (1/2)z. c) = a). Lets assume that the rst k constraints are the active constraints at x . We let c = k ai . It is easy to see that c is a supporting hyperplane. i=1

You might also like