| ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING＊ |
| |
| 摘 要： | In this paper, we consider the solution of the standard linear programming Lt＇）. 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.
|
| 关 键 词： | 线性规划算法 FACE 标准线性规划 现实世界 正交投影 单纯形法 算术运算 计算成本 |
On an Efficient Implementation of the Face Algorithm for Linear Programming |
| |
| Authors: | Lei-Hong Zhang Wei Hong Yang Li-Zhi Liao |
| |
| Institution: | [1]Department of Applied Mathematics, Shanghai University of Finance and Economics, Shanghai 200433, China [2]School of Mathematical Sciences, Fudan University, Shanghai 200433, China [3]Department of Mathematics and Institute of Computational and Theoretical Studies, Hong Kong Baptist University, Hong Kong, China |
| |
| 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. |
| |
| Keywords: | Linear programming Level face Optimal face Rank-one correction |
| 本文献已被 维普 等数据库收录！ |
| 点击此处可从《计算数学(英文版)》浏览原始摘要信息 |
|
