Why do BFS of an LP span the entire solution space?

Question

When discussing solutions to linear programs, the discussion immediately jumps to basic feasible solutions.

While I understand why they are important and useful in the context of LP, I need to satisfy myself that these basic feasible solutions span the entire solution space.

Is is something along the lines that every solution to the LP is necessarily a convex combination of basic feasible solutions? How can one show that this is always true?

For the record, I'm talking about the set of solutions to $\mathbf{A}\mathbf{x}=\mathbf{b}$ such that $\mathbf{x} \ge 0$, and I'm assuming the set is bounded and nonemtpy.

Can anyone shed some light on this?

Answer 1

The concept follows from a famous result by Leonid Kantorovich in 1939, where he proved that if $c\cdot x$ has a maximum in any polyhedron, it must also attain the maximum on its boundary.

In other words, e.g. if $Ax = b, x \ge 0$ describes some trapezoid $T \subset \mathbb{R}^2$, and $c\cdot x$ attains a maximum on $T$, it must also attain in on $\partial T$, which is the set of the edges describing the boundary of $T$. So there must be some edge $e \in \partial T$ where $c \cdot x$ is also maximized.

Now a second application of the same result shows that $c \cdot x$ must also have a maximum on $\partial e$, but the boundary of the edge $e$ are only 2 points between which $e$ is drawn.

By this example you can see if you attain a maximum anywhere in $T$, you must also attain it along one of the vertices of $T$. This is easy to extend to $\mathbb{R}^n$ for arbitrary finite $n$.

---

The intuition behind the proof of Kantorovich's result is exactly what you indicated - you can find a vector from your optimal point inside the polyhedron, moving along which you are guaranteed not to decrease $c \cdot x$ until you hit the boundary of the polyhedron in question.

Answer 2

I have finally found the answers I was looking for, so I thought I'd post them here for posterity.

My original question should have been "What is the deal with looking for solutions for LP on the vertices only?"

So what I figured out is as follows:

Definitions

First, a single inequality constraint can be interpreted geometrically as what's called a halfspace:

$$\mathcal{H}_i = \left\lbrace \mathbf{x} \in \mathbb{R}^n : \mathbf{a}^T \mathbf{x} \le b \right\rbrace$$

Equality constraints are called hyperplanes, and can be generalized as the intersection of two opposing halfspaces.

A polyhedron is the intersection of a bunch of halfspaces:

$$\mathcal{P} = \bigcap_i \mathcal{H}_i$$

Vertices

Now, a polyhedron has "corners", which have three equivalent definitions:

1. Extreme point
2. Vertex
3. BFS = Basic feasible solution (this one specifies how to calculate them)

Polyhedron is a convex hull of BFSs

It's possible to show that given all the vertices of a polyhedron, the polyhedron $\mathcal{P}$ can be redefined as all the convex combinations of it's vertices $V_\mathcal{P}$:

$$\mathcal{P} = \left\lbrace \sum_{\mathbf{v} \in V_\mathcal{P}} \lambda_\mathbf{v} \mathbf{v} : \sum_{\mathbf{v} \in V_\mathcal{P}} \lambda_\mathbf{v} = 1\right\rbrace$$

How is this proven? Start by observing that a polyhedron can be embedded in an affine subspace $S \subset \mathbb{R}^n$. We define the "dimension" of a polyhedron as the dimension of the smallest affine subspace that contains it.

For polyhedrons of dimension 0 (a single point), the proof is trivial (the point is also a vertex and is a trivial convex combination of itself).

Suppose now that we know the assumption to be true for polyhedrons of dimension up to $k-1$.

We now observe a polyhedron of dimension $k$, and select some point $\mathbf{x} \in \mathcal{P}$.

If the point is already a vertex, then we're done.

Otherwise, we choose some known vertex $\mathbf{p} \in \mathcal{P}$, and cast a ray from $\mathbf{p}$ through $\mathbf{x}$:

$$\mathbf{u}\left(\alpha\right) = \mathbf{x} + \alpha \left(\mathbf{x} - \mathbf{p}\right)$$

For some $\alpha$, the ray will leave the confines of the $\mathcal{P}$ by violating the constraint $\mathbf{a}_j^T \mathbf{x} \le b_j$.

We define a new polyhedron which forces the violated constraint as an equality constraint:

$$\mathcal{Q} = \left\lbrace \mathbf{x} \in \mathcal{P} : \mathbf{a}_j^T \mathbf{x} = b_j \right\rbrace$$

It can be shown that $\mathcal{Q}$ is of a dimension that's lower than $k$, and thus the assumption holds for it, specifically, for the intersection point of the ray:

$$\mathbf{u} = \sum_i \lambda_i \mathbf{q}_i$$

Where $\left\lbrace\mathbf{q}_i\right\rbrace$ are the vertices of $\mathcal{Q}$.

Now, we can rewrite $\mathbf{x}$ in terms of $\mathbf{u}$ and $\mathbf{p}$:

$$\mathbf{x} = \frac{\alpha}{1+\alpha}\mathbf{p} + \frac{1}{1+\alpha}\mathbf{u}$$

Replacing in $\mathbf{u}$ as a convex sum:

$$\mathbf{x} = \frac{\alpha}{1+\alpha}\mathbf{p} + \sum_i \frac{\lambda_i}{1+\alpha} \mathbf{q}_i$$

Now, since every vertex of $\mathcal{Q}$ is also a vertex of $\mathcal{P}$, we can say that $\mathbf{x}$ is a convex combination of vertices of $\mathcal{P}$.

Optimality

So, every point $\mathbf{x} \in \mathcal{P}$ can be written as a convex sum of the vertices (or BFSs):

$$\mathbf{x} = \sum \lambda_i \mathbf{x}_i$$

And the evaluation of the cost would be:

$$\mathbf{c}^T\mathbf{x} = \sum \lambda_i \mathbf{c}^T\mathbf{x}_i$$

Out of all the vertices, we can find one that has the highest cost, and one that gives the lowest:

$$\begin{eqnarray} \mathbf{c}^T\overline{\mathbf{v}} \ge \mathbf{c}^T\mathbf{v}_k \\ \mathbf{c}^T\underline{\mathbf{v}} \le \mathbf{c}^T\mathbf{v}_k \end{eqnarray}$$

Therefore, the cost of an arbitrary point is bounded:

$$\mathbf{c}^T\mathbf{\underline{v}} \le \mathbf{c}^T\mathbf{x} \le \mathbf{c}^T\mathbf{\overline{v}}$$

Which means that an optimum, will be attains only at the vertices.