Convergence rate of primal dual reciprocal Barrier Newton interior-point methods

Abstract

Primal-dual interior-point methods for linear programming are often motivated by a certaijn nonlinear transformation of the Karush-Kuhn-Tucker conditions of the logarithmic Barrier formulation. Recently, Nassar [5] studied the reciprocal Barrier function formulation of the problem. Using a similar nonlinear transformation, he proved local convergence fir Newton interior-point method on the resulting perturbed Karush-Kuhn-Tucker systerp. This result poses the question whether this method can exhibit fast convergence ral[e for linear programming. In this paper we prove that, for linear programming, Newton's method on the reciprocal Barrier formulation exhibits at best Q-linear convergence rattf. Moreover, an exact Q₁ factor is established which precludes fast linear convergence

Keywords:

• Convergence Rate
• Interior-Point Methods
• Reciprocal Barrier Function