Interior path following primal-dual algorithms

Abstract

We describe a primal-dual interior point algorithm for linear programming and convex quadratic programming problems which requires a total of O(n$\sp3$L) arithmetic operations. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithm barrier function problem. The algorithm is based on the path following idea. We show that the duality gap is reduced at each iteration by a factor of (1 $-$ $\delta$/$\sqrt{n}$) where 0.1 $\leq$ $\delta$ $<$ 1. As a consequence, an optimal solution for our problem can be found in at most O($\sqrt{n}$L) iterations. We also describe how the primal-dual algorithm can be extended to solve a class of convex separable programming problems subject to linear constraints. In this case, it is shown that the duality gap is reduced at each iteration by a factor of (1 $-$ $\delta$/$\sqrt{n}$), where $\delta$ is positive and depends on some parameters associated with the objective function.