A build-up variant of the logarithmic barrier method for LP

The authors propose a strategy for building up the linear program while using a logarithmic barrier method. The method starts with a (small) subset of the dual constraints, and follows the corresponding central path until the iterate is close to (or violates) one of the constraints, which is in turn added to the current system. This process is repeated until an optimal solution is reached. If a constraint is added to the current system, the central path will, of course, change. The authors analyze the effect on the barrier function value if a constraint is added. More importantly, they give an upper bound for the number of iterations needed to return to the new path. The authors prove that in the worst case the complexity is the same as that of the standard logarithmic barrier method. In practice this build-up scheme is likely to save a great deal of computation.