### Shifted Barrier Methods for Linear Programming

Almost all interior-point methods for linear programming published to date
can be viewed as application of Newton's method to minimize (approximately)
a sequence of logarithmic barrier functions. These methods have been
observed to suffer from certain undesirable features---most notably, badly
behaved subproblems arising from large derivatives of the barrier function
near the constraint boundary. We define a shifted barrier method intended
to avoid these difficulties. Convergence proofs are given for both exact
and approximate solution of the shifted barrier subproblems corresponding
to the primal and dual problems. We also show that the usual Newton
iterates eventually satisfy the requirements for sufficiently accurate
approximate solutions. Several practical strategies are suggested for
initializing and updating the weights and shifts.

Return To PEG's
Home Page.