  


On the Convergence of a PrimalDual SecondOrder Corrector Interior Point Algorithm for Linear Programming
Coralia Cartis (ccartiscomlab.ox.ac.uk) Abstract: The PrimalDual Second Order Corrector (PDSOC) algorithm that we investigate computes on each iteration a corrector direction in addition to the direction of the standard primaldual pathfollowing 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 primaldual strictly feasible starting point is available. Firstly, we use a new longstep 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 primaldual 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 longstep linesearch is employed to prove that the sequence of iterates converges to a primaldual strictly complementary solution of the LP problem, which may not be the analytic centre of the primaldual solution set as further shown by an example. Keywords: primaldual pathfollowing 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 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  