Accession Number : ADA182711

Title :   The Box Method for Linear Programming. Part 1. Basic Theory.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s) : Zikan,Karel ; Cottle,Richard W

PDF Url : ADA182711

Report Date : Jun 1987

Pagination or Media Count : 21

Abstract : 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.

Descriptors :   *LINEAR PROGRAMMING, ALGORITHMS, BOXES, SEARCHING, THEORY, DIRECTION FINDING, ELLIPSOIDS, OPTIMIZATION, INEQUALITIES, ITERATIONS, CONVERGENCE

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE