Extreme points
Extreme Points
An extreme point is a feasible point that cannot be written as a nontrivial convex combination of two different feasible points.
Definition
A point $x\in P$ is extreme if there do not exist distinct $y,z\in P$ and $0<\lambda<1$ such that
\[x=\lambda y+(1-\lambda)z.\]Meaning
An extreme point is not in the middle of a feasible line segment. In a polyhedron, this is the same idea as a vertex.
Example
In the interval $[0,1]$, the points $0$ and $1$ are extreme. The point $1/2$ is not, because
\[\frac12=\frac12(0)+\frac12(1).\]LP Importance
If $x=\lambda y+(1-\lambda)z$, then
\[c^Tx=\lambda c^Ty+(1-\lambda)c^Tz.\]So an interior point of a segment cannot be strictly better than both endpoints. This is why LP optima can be searched at extreme points.
Equivalence
For polyhedra:
\[\text{extreme point}=\text{vertex}.\]In standard form, these correspond to basic feasible solutions.
Checklist
You should be able to use the convex-combination definition and explain why endpoints matter in linear optimization.
See Also
Exam checkpoint
For BFS questions, convert to standard form before checking the point. A candidate in original variables must be lifted with slack and surplus variables before testing basis columns.