Optimization Online


On the Convergence of a Primal-Dual Second-Order Corrector Interior Point Algorithm for Linear Programming

Coralia Cartis (ccartis***at***comlab.ox.ac.uk)

Abstract: 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.

Keywords: primal-dual path-following interior point methods, linear programming

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Technical Report 05/04, Numerical Analysis Group, Computing Laboratory, Oxford University, United Kingdom, March 2005.

Download: [Compressed Postscript][PDF]

Entry Submitted: 03/23/2005
Entry Accepted: 03/23/2005
Entry Last Modified: 03/23/2005

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society