I'm reading chapter 2, "The geometry of linear programming", in Bertsimas & Tsitsiklis's "Introduction to Linear Optimization" (Athena Scientific, 1997). I'm having some difficulty with the concept of adjacency (as in "adjacent basic solutions" and "adjacent bases"). I'll start by collecting a few definitions and results pertaining to adjacency (page numbers refer to Bertsimas & Tsitsiklis's book).
Definition 1 (Adjacent basic solutions; p. 53) Two distinct basic solutions to a set of linear constraints in $\mathbb{R}^n$ are said to be adjacent if we can find $n – 1$ linearly independent constraints that are active at both of them.
Definition 2 (Edge; p. 53) If two adjacent basic solutions are also feasible, then the line segment that joins them is called an edge of the feasible set.
Theorem 3 (Edges joining adjacent vertices; Exercise 2.15, p. 78) Consider the polyhedron $P = \{x \in \mathbb{R}^n \mid a_i'x\geq b_i, i = 1, \dots, m\}$. Suppose that $u$ and $v$ are distinct basic feasible solutions that satisfy $a_i'u = a_i'v = b_i$, $i = 1, \dots, n – 1$, and that the vectors $a_1, \dots, a_{n – 1}$ are linearly independent. (In particular, $u$ and $v$ are adjacent.) Let $L = \{\lambda u + (1-\lambda)v \mid 0\leq \lambda \leq 1\}$ be the segment that joins $u$ and $v$. Then $L = \{z \in P \mid a_i' z = b_i, i = 1, \dots, n – 1\}$.
Definition 4 (Adjacent bases; p. 56) For standard form problems, we say that two bases are adjacent if they share all but one basic column.
Theorem 5 (Equivalence of adjacent solutions and adjacent bases; p. 56)
a) Adjacent basic solutions can always be obtained from two adjacent bases.
b) Conversely, if two adjacent bases lead to distinct basic solutions, then the latter are adjacent.
Here's what I don't understand.
- Adjacent vertices, like basic solutions, are defined in terms of the way the polyhedron is represented: different representations may yield different basic solutions. However, the property of being a feasible basic solution was shown (Theorem 2.3, p. 50) to be independent of the representation used. Is adjacency of vertices also independent of the representation used? Conversely, is it possible that, given two vertices $u$ and $v$, they are adjacent under one representation, but not adjacent under a different representation?
- It seems intuitive that if two feasible basic solutions are adjacent, then the edge between them lies in a hyperplane whose intersection with the polyhedron consists exactly of the points along the edge and furthermore, the hyperplane separates the space into two halves, only one of which intersects with the polyhedron. However, I fall short of proving this formally.
- I don't see how to prove Theorem 5. It was not proved in the book, but rather dismissed with the phrase: "it is not hard to check".
Best Answer
You asked about vertices. A vertex is a basic feasible solution, which is more specific than merely a basic solution. Adjacency of vertices/bfs's is a geometric property of polyhedra; as such, it is independent of the representation used. Here's a proof.
If $x$ and $y$ are two distinct vertices, of the polyhedron $P = \{z \in \mathbb{R}^n\mid: a'_i z \leq b_i, i \in \{1, \dots, m\}\}$, there are $n - 1$ independent constraints that are active at both $x$ and $y$, say the first $n - 1$ constraints. Then $\Delta := \{a_i'\cdot z \leq b_i,\ i \in 1, \dots, n - 1\}$ is a subsystem of full rank (i.e. $a_1, \dots, a_{n - 1}$ are independent) and $x$ and $y$ are solutions to this subsystem. According to Proposition 3.3.2 of [2] (p. 46) (which is proved there):
Where a face of the convex set $A$ is defined ([2] p. 37) to be
Hence $F := P \cap \Delta$ lies along the line that passes through $x$ and $y$, and for every $a, b \in P$, if $\lambda a + (1 - \lambda) b \in F$ for some $\lambda \in (0,1)$, $a, b \in F$.
If $Q = \{\alpha^i\cdot x \leq \beta^i, i = 1, \dots, \ell\}$ is any other representation of $P$, $x$ and $y$ are still vertices of $Q$ and we still have that $F$ is a convex subset of $Q$ that lies along the line that passes through $x$ and $y$ and for every $a, b \in Q$, if $\lambda a + (1 - \lambda) b \in F$ for some $\lambda \in (0,1)$, $a, b \in Q$. Hence the line through $x$ and $y$ contains a $1$-dimensional face of $Q$ (namely, $F$) and is thus a solution to a subsystem $\Delta'$ of $n - 1$ independent constraints $\{\alpha'_1\cdot z = \beta_1, \cdots, \alpha'_{n - 1}\cdot z = \beta_{n - 1}\}$ of $Q$. In particular, $Q$'s first $n - 1$ constraints are independent and active at $x$ and at $y$, which means that $x$ and $y$ are adjacent vertices of $Q$ as per Bertsimas & Tsitsiklis.
Your intuition is correct. If the polyhedron is identical with the line segment between $x$ and $y$, the result is immediate. Otherwise, a proof can be obtained using Proposition 3.2.6 of [2], p. 45 (which is proved there):
Here $\mbox{ri}\, (A)$ is the relative interior of the convex set $A \subset \mathbb{R}^n$, defined ([2], p. 12) as
and $\mbox{aff}\, A$ is the affine hull of $A$, characterized (Proposition 1.1.3, p. 3) as being
where an affine combination of $\{x^1, \dots, x^p\}$ is ([2], p. 3) any vector of the form $\sum_{k = 1}^p\lambda_k x^k$ such that $\sum_{k = 1}^p\lambda_k = 1$.
Here's how you do it. Apply Proposition 3.2.6 cited above, setting $P$ to be the face comprising the line segment connecting $x$ and $y$ and setting $C$ to be the given polyhedron of which $x$ and $y$ are adjacent vertices. To see that $P \cap \mbox{ri}(C) = \emptyset$, let $p \in P$. Suppose to the contrary that $p \in \mbox{ri}(C)$ and let $\varepsilon \in (0,\infty)$ be such that whenever $r \in \mbox{aff}\, C$ satisfies $\|r - p\| < \varepsilon$, $r \in C$. Let $q \in C\setminus P$ (recall that we are assuming that $C\setminus P \neq \emptyset$). Let $q' := \lambda p + (1 - \lambda)q$ for some $\lambda > 1$ such that $\|q' - p\| < \varepsilon$. Then, by the choice of $\varepsilon$, $q' \in C$. But then $p$ can be expressed as a convex combination of $q$ and $q'$, so we must have $q, q' \in P$ (since P is a face of $C$), in contradiction to how we chose $q$.
I will prove a weaker result, where "basic solution" is replaced with "basic feasible solution" and where "base" is replaced with "feasible base" (a base $B$ is feasible iff $B^{-1}b \geq 0$). Additionally, I will use part 1 to replace "adjacent basic feasible solutions" with "adjacent vertices". So, to sum up, I will prove the following theorem:
Part 2 is proved in Proposition 8.13 of [1] (p. 221):
which, "translated" to Bertsimas and Tsitsiklis's vocabulary would read:
Whereas part 1 is proved by the implication $\mbox{(b)}\implies\mbox{(c)}$ of theorem 2.10 of [3], p. 61:
which, "translated" to Bertsimas and Tsitsiklis's vocabulary would read (I have "translated" only the relevant implication):
(As a matter of fact, part 2 can also be obtained from [3]'s theorem 2.10, but I find [3]'s proof of this direction far less clear than the proof in [1]).
Works cited
[1] Andréasson, Nicolas; Evgrafov, Anton and Patriksson, Michael. An Introduction to Continuous Optimization: Foundations and Fundamental Algorithms. Lightning Source Incorporated, 2005.
[2] Florenzano, Monique and Le Van, Cuong. Finite Dimensional Convexity and Optimization. Springer, 2001.
[3] Papadimitriou, Christos H. and Steiglitz, Kenneth. Combinatorial Optimization, Algorithms and Complexity. Dover, 1998.