Why do BFS of an LP span the entire solution space? 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?
 A: 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.
A: 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:

*

*Extreme point

*Vertex

*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.
