Mehrotra predictor-corrector method
Encyclopedia
Mehrotra's predictor–corrector method in optimization
is an implementation of interior point method
s. It was proposed in 1989 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 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.
At each iteration of the algorithm, Mehrotra's predictor–corrector method uses the same 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. Then, a corrector term is computed: this contains both a centrality term and a second order term.
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. 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.
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
is an implementation of interior point method
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...
s. It was proposed in 1989 by Sanjay Mehrotra.
The method is based on the fact that at each iteration
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
of an interior point algorithm it is necessary to compute the Cholesky decomposition
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices...
(factorization) of a large matrix 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.
At each iteration of the algorithm, Mehrotra's predictor–corrector method uses the same 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. Then, a corrector term is computed: this contains both a centrality term and a second order term.
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. Its corrector step uses the same Cholesky decomposition
Cholesky decomposition
In linear algebra, the Cholesky decomposition or Cholesky triangle is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose. It was discovered by André-Louis Cholesky for real matrices...
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.