Mehrotra predictor–corrector method: Difference between revisions

Revision as of 09:59, 20 April 2013

Revision as of 17:33, 13 July 2014

Line 9:

The complete 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.<ref>"In 1989, Mehrotra described a practical algorithm for linear programming that remains the basis of most current software; his work appeared in 1992."<p>{{cite journal|last=Potra|first=Florian A.|coauthorsauthor2=Stephen J. Wright|title=Interior-point methods|journal=Journal of Computational and Applied Mathematics|volume=124|year=2000|issue=1–2|pages=281–302|doi=10.1016/S0377-0427(00)00433-7}}</ref> Its corrector step uses the same [[Cholesky decomposition]] found during the predictor step in an effective way, and thus it is only marginally 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.

==References==