The convergence of an interior-point method using modified search directions in final iterations

AbstractWe provide an asymptotic analysis of a primal-dual algorithm for linear programming that uses modified search directions in the final iterations. The algorithm determines the search directions by solving the normal equations using the preconditioned conjugate gradient algorithm. Small dual slack variables are slightly perturbed in the later stage of the interior-point algorithm to obtain better conditioned systems without interfering with convergence. The modification and its motivation are discussed, and a convergence analysis of the resulting algorithm is presented. The analysis shows the iterates of the modified system converge to the solution of the Karush-Kuhn-Tucker optimality system associated with the Lagrangian of the logarithmic barrier subproblem. The global convergence of the interior-point method is thus established