Year: 2013
Author: Leihong Zhang, Weihong Yang, Lizhi Liao
Journal of Computational Mathematics, Vol. 31 (2013), Iss. 4 : pp. 335–354
Abstract
In this paper, we consider the solution of the standard linear programming (LP). A remarkable result in LP claims that all optimal solutions form an optimal face of the underlying polyhedron. In practice, many real-world problems have infinitely many optimal solutions and pursuing the optimal face, not just an optimal vertex, is quite desirable. The face algorithm proposed by Pan [19] targets at the optimal face by iterating from face to face, along an orthogonal projection of the negative objective gradient onto a relevant null space. The algorithm exhibits a favorable numerical performance by comparing the simplex method. In this paper, we further investigate the face algorithm by proposing an improved implementation. In exact arithmetic computation, the new algorithm generates the same sequence as Pan's face algorithm, but uses less computational costs per iteration, and enjoys favorable properties for sparse problems.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1301-m4106
Journal of Computational Mathematics, Vol. 31 (2013), Iss. 4 : pp. 335–354
Published online: 2013-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 20
Keywords: Linear programming Level face Optimal face Rank-one correction.