Optimization Online


A New Face Method for Linear Programming

Ping-Qi Pan(panpq***at***seu.edu.cn)

Abstract: 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.

Keywords: linear programming, face, least squares, LU factorization, degeneracy

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Southeast University, Nanjing 210096, China, 12/2018

Download: [PDF]

Entry Submitted: 12/03/2018
Entry Accepted: 12/04/2018
Entry Last Modified: 12/03/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society