3
$\begingroup$

I'm having difficulty following a proof in the book Nonlinear Programming Theory and Algorithms, Third Edition by Bazaraa, Sherali, and Shetty on page 68 section 2.6.4. The proof is reproduced below, up to the part of the proof I'm confused about.

My question concerns the author's statement:

But this implies that $x_{11} = x_{21} = B^{-1}b$.

I don't see how the author makes that connection.

Theorem (Existence of Extreme Points)

Let $S = \{ x : Ax = b, x \geq 0\}$, where $A$ is an m x n matrix and $b$ is an m-vector. A point $x$ is an extreme point of $S$ if and only if $A$ can be decomposed into $[B, N]$ such that

$x = \begin{bmatrix} x_B \\ x_N \end{bmatrix} = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$

Proof:

Suppose that $A$ can be decomposed into $[B, N]$ with $x = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$ and $B^{-1}b \geq 0$. It is obvious that $x \in S$. Now suppose that $x = \lambda x_1 + (1 - \lambda)x_2$ with $x_1$, $x_2 \in S$ for some $\lambda \in (0,1)$. In particular, let $x^{t}_{1} = (x^{t}_{11}, x^{t}_{12})$ and $x^{t}_{2} = (x^{t}_{21}, x^{t}_{22})$. Then

$\begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} = \lambda \begin{bmatrix} x_{11} \\ x_{12} \end{bmatrix} + (1 - \lambda) \begin{bmatrix} x_{21} \\ x_{22} \end{bmatrix}$

Since $x_{12}, x_{22} \geq 0$ and $\lambda \in (0,1)$, it follows that $x_{12} = x_{22} = 0$. But this implies that $x_{11} = x_{21} = B^{-1}b$ and hence $x = x_1 = x_2$. This shows that $x$ is an extreme point of $S$.

  • 1
    First: It's only proper when excerpting a proof (or when quoting or paraphrasing a text) to provide the author's name, the title, edition of the text, page numbers...etc. Second: I'm assuming this is only "half" the proof? (i.e., the proof of "if" portion of Theorem?)2011-05-21
  • 0
    @Theo: I just submitted an edit of the question, and only afterwards saw your edit. Sorry if I impacted your edit.2011-05-21
  • 0
    @Amy: no problem, I had a mathematical objection. Pete L. Clark seems to have approved and slightly improved on your purely linguistic submission, so I just re-introduced my simple corrections.2011-05-21
  • 0
    @Amy: Thanks Amy, I edited the post to include the author, title, and page number. You are correct in assuming it was only half the proof as I wasn't able to get past that sentence.2011-05-21

1 Answers 1

4

Note that $x_1,x_2 \in S$ and hence $Ax_1 = b$ and $Ax_2 = b$. Hence, you get $x_{11} = x_{21} = B^{-1}b$ and hence $x_1 = x_2$.

To elaborate a bit, since $x_{1},x_{2} \geq 0$ and $\lambda \in (0,1)$, we have $x_{12} = 0 = x_{22}$.

Now, $Ax_1 = b \implies Bx_{11} + Nx_{12} = b \implies B x_{11} = b \implies x_{11} = B^{-1}b$.

Similarly, $Ax_2 = b \implies Bx_{21} + Nx_{22} = b \implies B x_{21} = b \implies x_{21} = B^{-1}b$.

Hence, $x_1 = x_2$ and both equals $x$.

  • 0
    Thanks! That was very helpful. I think a big part of my source of confusion was that I forgot that the matrix A was full rank so Ax=b must have only one solution for x.2011-05-21
  • 1
    @coderdave: I seriously hope that this was a typo in your last comment. What is true is that $B$ is invertible and so $Bx_{B} = b$ exactly one solution among the vectors *whose first $m$ entries* are the only non-zero ones, that's what Sivarams argument rests upon. If what you said was true, the theorem would be rather pointless! Think of the two-dimensional case, e.g. $A = \begin{bmatrix}1\\1\end{bmatrix}$ and draw a picture of $S$! Similarly, draw a picture of $S$ for $A = \begin{bmatrix}1\\1\\1\end{bmatrix}$ in $\mathbb{R}^3$ and different inhomogeneities $b$.2011-05-21
  • 1
    @coderdave: sorry, that should have been $A = [1 \;1]$ and $A = [1 \; 1 \; 1]$ in the previous comment.2011-05-21
  • 0
    @Theo: Thanks, it was a typo but I did what you said and then went through the proof and I have a better understanding of it. It was a lot easier when I worked out examples, I should have done that from the beginning. Thank you for the help.2011-05-23