Extreme Points and Basic Feasible Solutions

For a linear program in standard form, a point of the feasible region is an extreme point exactly when it is a basic feasible solution. The geometric notion of a corner and the algebraic notion of a basis describe the same set of points, which is why an algorithm that moves between bases is searching corners.

Definition

Let $P = {x : A x = b, x \geq 0}$ with $A$ an $m \times n$ matrix of rank $m$ . A point $x \in P$ is an extreme point if it cannot be written as a strict convex combination of two distinct points of $P$ . A point $x \in P$ is a basic feasible solution if there is a set $B$ of $m$ linearly independent columns of $A$ such that every component of $x$ outside $B$ is zero. The two conditions select the same points.

Formal statement

For $P = {x : A x = b, x \geq 0}$ with $rank (A) = m$ , the point $x$ is an extreme point of $P$ if and only if the columns ${A_{j} : x_{j} > 0}$ are linearly independent; equivalently, if and only if $x$ is a basic feasible solution for some basis $B$ .

Assumptions and scope

The program must be in standard form. The characterization is stated for the equality system $A x = b$ with $x \geq 0$ , not for an arbitrary mix of inequalities.
$A$ is assumed to have full row rank. Redundant equality constraints must be removed first, or no basis of $m$ independent columns exists.
A basic solution need not be feasible: a basis determines a unique solution, but that solution is a basic feasible solution only when it also satisfies $x \geq 0$ .
The correspondence is between points and bases, but it is not one-to-one in both directions. A degenerate basic feasible solution, one with fewer than $m$ strictly positive components, corresponds to more than one basis.

Worked material

Example

Checking two candidate points

Take the standard-form system

\begin{aligned} x_{1} + x_{2} + x_{3} & = 4, \\ x_{1} + x_{4} & = 2, \\ x_{1}, x_{2}, x_{3}, x_{4} & \geq 0, \end{aligned}

so that

A = (\begin{matrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \end{matrix}), b = (\begin{matrix} 4 \\ 2 \end{matrix}), m = 2 .

Candidate 1: $x = (2, 2, 0, 0)$ .

Feasibility: $2 + 2 + 0 = 4$ and $2 + 0 = 2$ , and every component is nonnegative. Feasible.

Positive components: $x_{1}$ and $x_{2}$ , giving columns

A_{1} = (\begin{matrix} 1 \\ 1 \end{matrix}), A_{2} = (\begin{matrix} 1 \\ 0 \end{matrix}) .

These are not multiples of one another, so they are linearly independent. There are exactly $m = 2$ of them, so they already form a basis. The point is a basic feasible solution, and therefore an extreme point.

Candidate 2: $x = (1, 2, 1, 1)$ .

Feasibility: $1 + 2 + 1 = 4$ and $1 + 1 = 2$ , all components nonnegative. Feasible.

Positive components: all four, giving all four columns of $A$ . Four vectors in $R^{2}$ cannot be linearly independent, so the test fails. The point is feasible but is not a basic feasible solution, and therefore not an extreme point.

The second point is genuinely interior to a segment of $P$ . For instance it is the midpoint of $(0, 2, 2, 2)$ and $(2, 2, 0, 0)$ , both of which are feasible. That is the geometric statement matching the algebraic failure.

Contrast

Vertices and bases under degeneracy

The equivalence between extreme points and basic feasible solutions invites a reading it does not support: that corners and bases are paired off, one each.

What holds in both directions. Every basic feasible solution is an extreme point, and every extreme point arises from at least one basis. Nothing in this unit is weakened by what follows.

What does not hold. That each extreme point arises from exactly one basis. Condition 2 of the correspondence constrains only the columns of strictly positive components. When fewer than $m$ components are positive, the basis must be completed with columns whose components are zero, and there may be several valid ways to complete it. Each describing the same point.

Where this is worked through. The unit on degenerate basic feasible solutions takes this up: how to detect the situation from the component count, what it looks like as a surplus of active constraints, and why it makes a basis change capable of arriving where it started. The worked cases belong there.

What to carry out of this unit. The correspondence is a map from bases onto extreme points. It is surjective. It is not injective, and the wrong prediction that follows from assuming otherwise, that every basis change moves you to a new corner with a better objective, is the one to guard against.

Why the distinction is worth making here rather than later. The enumeration argument in this unit counts bases to bound the number of corners. That bound is an over-count precisely because several bases can name one point, so the looseness of $(\binom{n}{m})$ is not an incidental detail. It is this asymmetry showing up in the arithmetic.

Common errors

Common misconception

Every basic feasible solution corresponds to exactly one basis, so two different bases always identify two different corners of the feasible region.

Extreme Points and Basic Feasible Solutions

Assumptions and scope

Worked material

Checking two candidate points

Vertices and bases under degeneracy

Common errors

Related units

Requires

Connected

Learn this topic

Used in

Sources

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history