ON AN EFFICIENT IMPLEMENTATION OF THE FACE ALGORITHM FOR LINEAR PROGRAMMING＊

作     者：Lei-Hong Zhang Wei Hong Yang Li-Zhi Liao 

作者机构：Department of Applied Mathematics Shanghai University of Finance and Economics Shanghai 200433 China School of Mathematical Sciences Fudan University Shanghai 200433 China Department of Mathematics and Institute of Computational and Theoretical Studies Hong Kong Baptist University Hong Kong China 

出 版 物：《Journal of Computational Mathematics》 (计算数学（英文）)

年 卷 期：2013年第31卷第4期

页      面：335-354页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 081105[工学-导航、制导与控制] 070105[理学-运筹学与控制论] 0701[理学-数学] 0811[工学-控制科学与工程] 

基　　金：国家自然科学基金 the Basic Academic Discipline Program the 11th five year plan of 211 Project for Shanghai University of Finance and Economics supported in part by GRF from the Research Grant Council of Hong Kong 

主　　题：Linear programming Level face Optimal face Rank-one correction. 

摘      要：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.