 # Degeneracy

The solution $LaTeX: (x, y, s)$ to the primal-dual pair of linear programs: $LaTeX: \min \{c^Tx : x \ge 0, \; Ax = b\}$ and $LaTeX: \max \{y^Tb: s \ge 0, \; yA + s = c\}$
is degenerate if it is not strictly complementary ---i.e. $LaTeX: x_i = s_i = 0$ for some $LaTeX: i$. The pair $LaTeX: (x_i, s_i)$ is primal degenerate if there is an optimal solution $LaTeX: x'$ such that $LaTeX: x'_i > 0$. Similarly, the pair is dual degenerate if there is a dual optimal solution $LaTeX: (y', s')$ such that $LaTeX: s'_i > 0$.
With regards to a basic optimal solution, such a solution is (primal) degenerate when some basic variable is at one of its bound values (canonically zero). A basic optimal is dual degenerate if one of its nonbasic variables has a zero reduced cost. Geometrically, this corresponds to a degenerate polyhedron. Suppose we have $LaTeX: \{x: Ax \le b\}$ (where $LaTeX: A$ is $LaTeX: m$ by $LaTeX: n$). This polyhedron is degenerate if there exists an extreme point that is an element of the intersection of more than $LaTeX: n$ hyperplanes. The pyramid is degenerate because four planes meet at a point. (Example.)