A Build-Up Interior-Point Method for Linear Programming: Affine Scaling Form

We propose a build-up interior-point method for solving an m equation n variable linear program which has the same convergence properties as its well known analogue Dikin's algorithm in dual affine form but may require less computational effort. It differs from Dikin's algorithm in that the ellipsoid chosen to generate the improving direction in dual space is constructed from only a subset of the dual constraints. We also present some preliminary computational results for this method. Key words: linear programming, interior method, affine scaling scaling, active column. Abbreviated title: A Build-Up Interior-Point Method for LP y Department of Operations Research, Stanford University, Stanford, CA 94305 z Department of Management Sciences, The University of Iowa, Iowa City, IA 52242. Research supported in part by NSF Grant DDM-8922636 and an Interdisciplinary Research Grant from The University of Iowa Center for Advanced Studies. 1. Steps of Dikin's Algorithm We are concerned with ..