Extreme point

From Glossary

Jump to: navigation, search

A point in the closure of a set, say LaTeX: S, that is not the midpoint of any open line segment with end points in closure of LaTeX: S. Equivalently, LaTeX: x is an extreme point of a closed set, LaTeX: S, if there do not exist LaTeX: y, z \in S \backslash {x} for which LaTeX: \textstyle x = (y + z)/2. When LaTeX: S is a polyhedron of the standard form, LaTeX: S=\{x: Ax=b, \; x \ge 0\}, with LaTeX: A of full row rank, we have one of the fundamental theorems of linear programming that underlies the simplex method:

LaTeX: x is an extreme point of the feasible region if, and only if, LaTeX: x is a basic feasible solution.

Personal tools