Gauss-Jordan Canonical Form

This semester, I am taking a class of Prof. Ramaswamy Chandrasekaran for linear programming related to optimization. It is a nice journey… Go fighting!

Pivot operation

We repeat pivot operation until we cannot improve anymore. However, sometimes we will find that pivot operation cannot increase or decrease the result, this is called degeneracy.

  • Degeneracy
    The reason of degeneracy is explained in Introduction to Algorithms:

    Degeneracy can prevent the simplex algorithm from terminating, because it can lead to a phenomenon known as cycling: the slack forms at two different iterations of SIMPLEX are identical. Because of degeneracy, SIMPLEX could choose a sequence of pivot operations that leave the objective value unchanged but repeat a slack form within the sequence. Since SIMPLEX is a deterministic algorithm, if it cycles, then it will cycle through the same series of slack forms forever, never terminating.

It also recalls my memory of Apple WWDC2018 about High Performance Auto Layout.

Lexicographic Simplex Method

  • Prevent degenerate cycling
  • Reorganize computations

Reference

[1]. Introduction to Algorithms, Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. MIT Press.
[2]. Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time. Daniel A. Spielman, Shang-Hua Teng. J. ACM 51, 3 (May 2004), 385-463.