0
$\begingroup$

Given a system of

$$(\text{P})\ \begin{cases} Ax=b \\ x \ge 0\end{cases}$$

where $A \in \Bbb{R}^{m \times n}, m \le n, \ \text{rank}(A) = m, b \in \Bbb{R}^m, x \in \Bbb{R}^n$. By $x \ge 0$, we mean termwise, each term is nonnegative.

By definition, the Polyhedron of the Allowed Solutions are:

$$P = \{x \in \Bbb{R}^n | Ax = b, x \ge 0\}$$

This is a polyhedron since each row of matrix $A$ gives a restriction to the solutionspace, and cuts off a halfspace from it. And a polyhedron is by definition the intersection of halfspaces.

Def. $\overline{x} \in P$ is called a basis solution if $\ \overline{x} =(x_1, \dots, x_n),\ J_+ = \{j\in \{1,\dots,n\}| x_j > 0\},\ A = [a_j]_{j \in \{1,\dots n\}}$ are the columvectors of $A$, and the set of vectors $\{a_j\}_{j \in J_+}$ are linearly independent. (These are the columns of $A$ such that their indicies are exactly those indicies where $\overline{x}$ is positive.)

Def. $\overline{x} \in P$ is called the extreme point of $P$, if $\ \forall x_1,x_2 \in P$ and $0 < \lambda < 1$: $$\overline{x} = \lambda x_1 + (1- \lambda) x_2 \ \Rightarrow\ \overline{x} = x_1 = x_2$$ (These are the "edges" of the $P$ polyhedron.)

Question: Why do these two definitions match up exactly? Why is the following theorem true?

Theorem: $\overline{x}$ is a basis solution $\Longleftrightarrow$ $\overline{x}$ is a emtreme point of $P$.

I'd like to understand both directions of the proof ($\Leftarrow, \Rightarrow$), and haven't found anything that explains this in a great detail. Thank you in advance!

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.