This blog is talking about the concept of degeneracy. Which is actually a horrible situation in following algorithm called simplex we will going to talk about.

Degeneracy

Consider the polyhedron in ${ \mathbb{R}^n }$ determined by the linear constraints

$$ \begin{equation} \begin{aligned} \bar{a_i}^\top \bar{x} &\leq b_i, \forall i \in L \\ \bar{a_i}^\top \bar{x} &= b_i, \forall i \in E \\ \bar{a_i}^\top \bar{x} &\geq b_i, \forall i \in G \\ \end{aligned} \end{equation} $$

Given a point ${ \bar{y}\in \mathbb{R}^n }$, let

$$ \begin{equation} \begin{aligned} L_{\bar{y}} = \{i\in L \mid \bar{a_i}^\top \bar{y} = b_i\} \\ E_{\bar{y}} = \{i\in E \mid \bar{a_i}^\top \bar{y} = b_i\} \\ G_{\bar{y}} = \{i\in G \mid \bar{a_i}^\top \bar{y} = b_i\} \\ \end{aligned} \end{equation} $$

be the subsets of indices corresponding to the linear constraints that are active at ${ \bar{y} }$.

Recall that the point ${ \bar{y} }$ is a basic solution, iff ${E_{\bar{y}}= E}$ and ${\dim \text{ } span \{\bar{a_i} \mid i \in E\cup L_{\bar{y}} \cup G_{\bar{y}}\} = n}$.

Assume ${\bar{y}}$ is a basic solution, we have

$$ \begin{equation} \begin{aligned} n &= \dim \text{ } span \{\bar{a_i} \mid i \in E\cup L_{\bar{y}} \cup G_{\bar{y}}\} \\ &\leq \dim \text{ } span \{\bar{a_i} \mid i \in E\} + \dim \text{ } span \{\bar{a_i} \mid i \in L_{\bar{y}} \cup G_{\bar{y}} \} \\ & \leq \dim \text{ } span \{\bar{a_i} \mid i \in E\} + \# (L_{\bar{y}} \cup G_{\bar{y}}) \end{aligned} \end{equation} $$

We now have ${ n \leq \dim \text{ } span \{\bar{a_i} \mid i \in E\} + \#(L_{\bar{y}} \cup G_{\bar{y}})}$, or equivalently,

$$ \#(L_{\bar{y}} \cup G_{\bar{y}}) \geq n- \dim \text{ } span \{\bar{a_i} \mid i \in E\} $$

Here, ${ \#(L_{\bar{y}} \cup G_{\bar{y}}) }$ is the number of ineqaulity constraints active at ${\bar{y}}$.

${ n- \dim \text{ } span \{\bar{a_i} \mid i \in E\}}$ means the dimension of the solution set of the linear system ${A\bar{x}=\bar{b}}$.

Definition: If the above inequality is strictly larger, we say ${\bar{y}}$ is a degenarate basic solution. Else, we take equal here, we say ${\bar{y}}$ is a non-degenarate basic solution.

Degeneracy in Geometric

In fact, we noticed that the degeneracy situation happens to the basic solution that are over-determined, that means the the number of hyperplanes that are passing through ${\bar{y})}$ is greater than the dimension of whole space.

Degenerate basic solution in Std form

Definition: Given a basic solution ${\bar{y}}$ of a standard form polyhedron ${P = \{\bar{x} \in \mathbb{R}^n \mid A\bar{x} = \bar{b}, \bar{x}\geq \bar{0}\}}$. We say that ${\bar{y}}$ is a degenerate basic solution if

$$ \#(L_{\bar{y}} \cup G_{\bar{y}}) > n- \dim \text{ } span \{\bar{a_i} \mid i \in E\} $$

i.e. more than ${n-rank(A)}$ of components of ${\bar{y}}$ are zero.

Observation

• At a non-degenerate basic solution of a std form polyhedron ${P=\{\bar{x}\in \mathbb{R}^n \mid A\bar{x} = \bar{b},\bar{x}\geq \bar{0}\}}$, exactly ${n-rank(A)}$ constraints ${x_i \geq 0}$ are active, namely all ${n-rank(A)}$ non-basic variables are zero and all basic variables are non-zero.

• At a degenerate basic solution of a std form polyhedron ${P=\{\bar{x}\in \mathbb{R}^n \mid A\bar{x} = \bar{b},\bar{x}\geq \bar{0}\}}$, more than ${n-rank(A)}$ constraints ${x_i \geq 0}$ are active, namely all ${n-rank(A)}$ non-basic variables are zero and at least one of the basic variables is zero.