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

摘要

We proposed a build-up interior method for solving an m equation n variable linear program which has the same convergence properties as their well known analogues in dual affine and projective forms but requires less computational effort. The algorithm has three forms, an affine scaling form, a projective scaling form, and an exact form (that used pivot steps). In this paper, we present the first of these. It differs from Dikin's algorithm of dual affine form in that the ellipsoid chosen to generate the improving directions in dual space is constructed from only a subset of the dual constraints. Keywords: Iterations. (KR)