The Primal-Dual Second Order Corrector (PDSOC) algorithm that we investigate computes on each iteration a corrector direction in addition to the direction of the standard primal-dual path-following interior point method (Kojima et al., 1989) for Linear Programming (LP), in an attempt to improve performance. The corrector is multiplied by the square of the stepsize in the expression of the new iterate. While the outline of the PDSOC algorithm is known (Zhang et al., 1995), we present a substantive theoretical interpretation of its construction. Further, we investigate its convergence and complexity properties, provided that a primal-dual strictly feasible starting point is available. Firstly, we use a new long-step linesearch technique suggested by M. J. D. Powell, and show that, when the centring parameters are bounded away from zero, the limit points of the sequence of iterates are primal-dual strictly complementary solutions of the LP problem. We consider also the popular choice of letting the centring parameters be of the same order as the duality gap of the iterates asymptotically. A standard long-step linesearch is employed to prove that the sequence of iterates converges to a primal-dual strictly complementary solution of the LP problem, which may not be the analytic centre of the primal-dual solution set as further shown by an example.
Citation
Technical Report 05/04, Numerical Analysis Group, Computing Laboratory, Oxford University, United Kingdom, March 2005.