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.