3
$\begingroup$

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.

  1. 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?
  2. 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.
  3. 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".
$\endgroup$
3
$\begingroup$
  1. 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?

    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):

    Let $P = \{x \in \mathbb{R}^n\mid a^i\cdot x = b^i, i = 1, \dots, m\}$ be a polyhedral convex set. If the system $a^i\cdot x = b^i$, $i = 1, \dots, m$ has a subsystem of rank $n - 1$, let $\Delta$ be the line of the solutions to this subsystem. Then either $P \cap \Delta$ has at most one point, or $P \cap \Delta$ is a $1$-dimensional face of $P$. Conversely, every line which contains a $1$-dimensional face of $P$ is the solution to such a subsystem.

    Where a face of the convex set $A$ is defined ([2] p. 37) to be

    a convex subset $F$ of $A$ verifying: $$ \left.\begin{aligned} x & \in F \cap (y,z) \\ y & \in A, z \in A \end{aligned}\right\} \implies y \in F, z \in F $$

    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.

  2. 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):

    Let $P$ and $C$ be nonempty convex sets such that $P$ is polyhedral and $P \cap \mbox{ri}(C) = \emptyset$. Then there exists a hyperplane separating $P$ and $C$ which does not contain $C$.

    Here $\mbox{ri}\, (A)$ is the relative interior of the convex set $A \subset \mathbb{R}^n$, defined ([2], p. 12) as

    the set of the points $x$ of $A$ such that there exists a ball with center $x$ and radius $\varepsilon$ whose intersection with $\mbox{aff}\, A$ is contained in A

    and $\mbox{aff}\, A$ is the affine hull of $A$, characterized (Proposition 1.1.3, p. 3) as being

    the set of all affine combinations of finitely many members of $A$

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

  3. 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:

    Considering a polyhedron in standard form,

    1. Adjacent vertices (in the sense that the line segment between them is a 1-dimensional face of the polyhedron) can always be expressed as bfs's corresponding to adjacent feasible bases.

    2. Conversely, if two adjacent feasible bases lead to two distinct bfs's, then the latter are adjacent vertices (in the sense specified above).

    Part 2 is proved in Proposition 8.13 of [1] (p. 221):

    (algebraic characterization of adjacency) Let $\mathbf{u}$ and $\mathbf{v}$ be the extreme points that correspond to the partitions $(\mathbf{B}^1, \mathbf{N}^1)$ and $(\mathbf{B}^2, \mathbf{N}^2)$ described above. Then $\mathbf{u}$ and $\mathbf{v}$ are adjacent BFSs.

    which, "translated" to Bertsimas and Tsitsiklis's vocabulary would read:

    Let $\mathbf{u} = (\mathbf{B}_1^{-1}\mathbf{b}, \mathbf{0})$ and $\mathbf{v} = (\mathbf{B}_2^{-1}\mathbf{b}, \mathbf{0})$ be two distinct bfs's of a polyhedron given in standard form. Then $\mathbf{u}$ and $\mathbf{v}$ are adjacent vertices (i.e. the line segments connecting the two vertices is a 1-dimensional face of the feasible set).

    Whereas part 1 is proved by the implication $\mbox{(b)}\implies\mbox{(c)}$ of theorem 2.10 of [3], p. 61:

    Let $P$ be a polytope, $F = \{x: Ax = b, x\geq 0\}$ the corresponding feasible set, and $\hat{x} = (x_1, \dots, x_{n - m})$, $\hat{y} = (y_1, \dots, y_{n - m})$ be distinct vertices of $P$. Then the following are equivalent.

    (a) The segment $[\hat{x}, \hat{y}]$ is an edge of $P$.

    (b) For every $\hat{z} \in [\hat{x}, \hat{y}]$, if $\hat{z} = \lambda \hat{z}' + (1 - \lambda) \hat{z}''$ with $0 < \lambda < 1$ and $\hat{z}', \hat{z}'' \in P$, then $\hat{z}', \hat{z}'' \in [\hat{x}, \hat{y}]$.

    (c) The corresponding vectors $x$, $y$ of $F$ are adjacent bfs's.

    which, "translated" to Bertsimas and Tsitsiklis's vocabulary would read (I have "translated" only the relevant implication):

    Let $F = \{x: Ax = b, x\geq 0\} $ be a polyhedron given in standard form, and let $\hat{x}$, $\hat{y}$ be distinct vertices of $F$. Then if $\hat{x}$ and $\hat{y}$ are adjacent vertices (in the sense that the line segments connecting them is a face of dimension 1, then they can be expressed as the bfs's $\hat{x} = (B_1^{-1}b\ 0)$ and $\hat{y} = (B_2^{-1}b\ 0)$, where $B_1$ and $B_2$ are two adjacent feasible bases.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.