### 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*

##### Abstract

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*