Mehrotra predictor–corrector method

Mehrotra's predictor-corrector method in optimization is an implementation of interior point methods. It was proposed in 1991 by Sanjay Mehrotra.

The idea is to first compute an optimizing search direction based on a first order term (predictor). The step size that can be taken in this direction is used to evaluate how much centrality correction is needed. Second, a corrector term is computed: this contains both a centrality term and a second order term.

Therefore, the search direction is the sum of the predictor direction and the corrector direction.

Although there is no theoretical complexity bound on it yet, Mehrotra's predictor-corrector method is widely used in practice. Its corrector step effectively uses the Cholesky decomposition of the linear system in the predictor step. Thus it has very little overhead. It also appears to converge very fast when close to the optimum.

http://locus.siam.org/SIOPT/volume-06/art_0806004.html

The Mehrotra Predictor-Corrector Interior-Point Method As a Perturbed Composite Newton Method

It is well known that the celebrated Kojima–Mizuno–Yoshise primal-dual interior-point method for linear programming can be viewed as a damped perturbed Newton’s method. Recently, Mehrotra suggested a predictor-corrector variant of this method. It is currently the interior-point method of choice for linear programming. The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton’s method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. In this work we demonstrate that if the Newton component in the Kojima–Mizuno–Yoshise primal-dual method is replaced with a composite Newton component, then the resulting method is the Mehrotra predictor-corrector method.