Box Method for Linear Programming. Part 1. Basic Theory

摘要

This paper presents a new interior-point algorithm for linear programming where the constraints are all expressed as inequalities. Along with the concept of minimum-weight basis, the algorithm features a novel mechanism for finding search directions. Unlike other interior-point methods which implicity or explicitly involve optimization over ellipsoids for their direction-finding schemes, the one reported here uses boxes. The corresponding subproblems are simple linear programs having closed form solutions. It is shown that the iterates generated by the algorithm converge to an extreme point of the feasible region. When this point is nondegenerate, it is optimal and reached within finitely any steps. The methodology introduced here also gives rise to a polyhedral subdivision of the problem's feasible region and in fact to the entire space of decision variables.