Extreme Points and Basic Feasible Solutions

Corners of the feasible region are geometric. Basic feasible solutions are algebraic. They turn out to be the same points, which is what makes an infinite search finite.

This is the result that makes the simplex method possible. A linear program can have infinitely many feasible points, which is far too many to search. This principle says that the optimum, when one exists, can always be found among a finite set: the corners. It also says that the corners have an algebraic description, so a program can move between them without ever drawing a picture.

This unit assumes you can convert a program to standard form and that you can decide whether a set of vectors is linearly independent.

Consider standing somewhere in the feasible region.

In the middle of the region you can step a little in any direction and remain feasible. On an edge you can still slide along that edge. At a corner the freedom is gone in a precise sense: enough constraints hold with equality, with independent normals, that no direction keeps all of them tight.

That is not the same as being unable to move. From a corner you can still travel along either incident edge, and into the region, by releasing one of the active constraints, which is exactly what a simplex step does. What the active set removes is the freedom to move while holding every one of those equalities, and with enough independent ones that condition pins the point down to a single solution.

That is what makes a corner special, and it is also what makes it describable. Being pinned down means enough independent constraints hold with equality to determine the point uniquely. Choosing which constraints those are is choosing a basis.

So two descriptions that sound unrelated turn out to name the same thing:

• Geometric: a point that is not in the middle of any segment lying inside the region.
• Algebraic: a point whose positive components correspond to linearly independent columns.

The definition that follows makes the second precise, and the equivalence is what lets an algorithm work entirely in the algebra.

Let

where $A$ is $m\times n$ with rank $m$.

Extreme point. A point $x\in P$ is an extreme point of $P$ if it is not a strict convex combination of two distinct points of $P$: there are no $y,z\in P$ with $y\ne z$ and $\lambda \in (0,1)$ such that $x=\lambda y+(1-\lambda )z$.

Basis, basic solution, basic feasible solution. These are established in the unit on basic solutions: a basis is a set $B$ of $m$ independent columns, the basic solution it determines is $x_B=A_B^{-1}b$ with the nonbasic components zero, and a basic feasible solution is one that additionally passes the test $x\ge 0$. The separation of the construction from that test is the subject of that unit; what follows uses both.

The correspondence. For $x\in P$, the following are equivalent:

1. $x$ is an extreme point of $P$;
2. the columns are linearly independent;
3. $x$ is a basic feasible solution for some basis $B$.

This is the result the unit exists for. A geometric property, not lying strictly inside any segment of $P$, turns out to be decidable by an algebraic test on columns, and that is what allows an algorithm to search corners without ever drawing one.

Read condition 2 carefully. It constrains only the columns of strictly positive components. If fewer than $m$ components are positive, those columns can be extended to a full basis by adding columns whose components are zero, and there may be several ways to do so. The point is then degenerate, and the several-bases-one-point consequence is taken up in the unit on degeneracy.

The direction that matters. Every basic feasible solution is an extreme point, and every extreme point arises from at least one basis. The phrase is "at least one", not "exactly one".

Take the standard-form system

so that

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

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 ${\mathbb{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.

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 $(\genfrac{}{}{0ex}{}{n}{m})$ is not an incidental detail. It is this asymmetry showing up in the arithmetic.

This principle is what turns an infinite search into a finite one.

A feasible region typically contains infinitely many points, so optimizing by inspection is hopeless. Two facts change that:

1. When a linear program in standard form has an optimal solution, one of its extreme points is optimal. The objective is linear, so it cannot have a strict interior maximum along any segment; pushing toward the better end always reaches a boundary.
2. Extreme points are exactly the basic feasible solutions, and there are only finitely many bases: at most $(\genfrac{}{}{0ex}{}{n}{m})$ ways to choose $m$ columns from $n$.

Together these say the search can be confined to a finite list of algebraically describable points.

The simplex method exploits this directly. It holds a basis, reads off the corresponding basic feasible solution, and asks whether swapping one column out and another in improves the objective. Each swap is an algebraic operation on the basis; geometrically it is a step from one corner to an adjacent one.

This is also why converting to standard form earns its keep. The conversion looks like bookkeeping, but it is what makes the basis description available at all, and with it the entire method.

One caution carried forward from the contrast case: because a degenerate corner has several bases, a swap can change the basis without moving the point. Simplex implementations need an anti-cycling rule for exactly this reason.

The characterization has an immediate consequence: because every extreme point is a basic feasible solution, and every basic feasible solution comes from choosing $m$ columns of $A$ to form a basis, the corners can be counted by counting those choices.

With $n$ variables and $m$ equality constraints there are

ways to choose the basis columns, so a standard-form program has at most $(\genfrac{}{}{0ex}{}{n}{m})$ extreme points.

The bound is loose, in both directions. Not every choice of $m$ columns is a basis: the columns may be linearly dependent, in which case $A_B$ is singular and defines no basic solution at all. Of the choices that do give a basis, many produce a point with a negative component, which is basic but not feasible and so not a corner. Pulling the other way, degeneracy lets several distinct bases describe the same point, so even the count of valid bases overstates the number of distinct corners.

So $(\genfrac{}{}{0ex}{}{n}{m})$ is an upper bound and usually a generous one.

Finiteness is not practicality. The bound licenses a tempting argument: the list of corners is finite, so enumerate it, evaluate the objective at each, and take the best. The reasoning is sound. The algorithm is useless.

Take a small problem by industrial standards, $n=60$ variables, $m=30$ constraints:

At a billion bases evaluated per second, that is roughly 3.75 years. Add ten more variables, giving $(\genfrac{}{}{0ex}{}{70}{30})\approx 5.5\times {10}^{19}$, and the same machine needs about 1,750 years. The word "finite" does no work here at all; the growth rate of the count is what matters, and $(\genfrac{}{}{0ex}{}{n}{m})$ grows combinatorially.

This is exactly why the simplex method matters. It does not enumerate corners. It starts at one, and each iteration moves to an adjacent corner that does not worsen the objective, so it visits a path through the corners rather than all of them. In practice that path is short, typically a small multiple of $m$, even though no bound guarantees it.

The general lesson outlives linear programming: a termination proof establishes that an algorithm stops, and says nothing whatever about whether you can afford to wait.