Mehrotra predictor–corrector method: Difference between revisions

Revision as of 01:49, 15 May 2006

Revision as of 16:55, 8 February 2007

Line 1:

'''Mehrotra's predictor-corrector method''' in [[Optimization (mathematics)|optimization]] is an implementation of [[interior point method]]s. It was proposed in 1991 by [[Sanjay Mehrotra]].

The method is based on the fact that at each [[iteration]] of an interior point algorithm it is necessary to compute the [[Cholesky decomposition]] (factorization) of a large matrix in order to find the search direction. The factorization step is the most computationally expensive step in the algorithm. Therefore it makes sense to use the same decomposition more than once before recomputing it.

Mehrotra's predictor-corrector method uses the Cholesky decomposition to find two different directions: a predictor and a corrector.

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 thecomplete 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 same [[Cholesky decomposition]] offound during the linearpredictor systemstep in thean predictoreffective step.way, Thusand thus it hasis veryonly littlemarginally more expensive than a standard interior point algorithm. However, the additional overhead per iteration is usually paid off by a reduction in the number of iterations needed to reach an optimal solution. It also appears to converge very fast when close to the optimum.