Coralia Cartis (Computing Laboratory, University of Oxford)

Overcoming some disadvantages of a Mehrotra-type primal-dual corrector interior point algorithm for linear programming
Wednesday 16 March 2005 at 15.30, JCMB 5327


The Primal-Dual Corrector (PDC) algorithm that we propose 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 new iterate is chosen by moving along the sum of these directions, from the current iterate. This technique is similar to the construction of Mehrotra's highly popular predictor-corrector algorithm (Mehrotra, 1991). We present examples, however, that show that the PDC algorithm may fail to converge to a solution of the LP problem, in both exact and finite arithmetic, regardless of the choice of stepsize that is employed. The cause of this bad behaviour is that the correctors exert too much influence on the direction in which the iterates move. We attempt to reduce the impact of the correctors by multiplying them by the square of the stepsize in the expression of the new iterates. The resulting algorithm, the Primal-Dual Second-Order Corrector (PDSOC), overcomes the failure that the PDC algorithm experienced on the aforementioned example. 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. Using standard terminology, we are concerned with long-step versions of this algorithm, where the iterates belong to a large neighbourhood of the primal-dual central path. We assume 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 show that the sequence of iterates converges to a primal-dual strictly complementary solution of the LP problem.

Seminars by year

Current 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996