An attractive feature of the face method \cite{pan14} for solving LP problems is that it uses the orthogonal projection of the negative objective gradient on the related null space as the search direction. However, the method would not be amenable for solving large sparse problems, since it handles the involved normal system by orthogonal transformations. This work derives a new type of search directions using Gaussian elimination, and formulates an algorithm using LU factorization. In a single iteration, the objective reduction by the latter is of the squares order, compared with the first order reduction by the simplex algorithm. The search direction is shown to be the best in certain sense. Some anti-degenerate tactics are incorporated by taking advantage of the face framework.
Citation
Southeast University, Nanjing 210096, China, 12/2018