A Dual Face Algorithm for Linear Programming

Ping-Qi Pan(panpqseu.edu.cn)

Abstract: As a dual variant of the face algorithm for linear programming, the proposed algorithm proceeds from dual face to dual face until reaching a dual optimal face along with a pair of dual and primal optimal solutions. It computes the search direction as an orthogonal projection of the dual objective gradient onto a certain null space. A major advantage of it is that it handlessmaller systems than its primal counterpart. We report preliminary but favorable computational results with a set of standard Netlib test problems.

Keywords: linear programming, dual level face, dual optimal face, Cholesky factorization, orthogonal projection

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

Citation: Department of Mathematics, Southeast University, 210096, Chian, 10/2007

Download: [PDF]

Entry Submitted: 10/17/2007
Entry Accepted: 10/17/2007
Entry Last Modified: 10/17/2007

Modify/Update this entry