Введение
1989 Алгоритм оптимизации
Метод прогноза-коррекции Мехроты в оптимизации — это специфический метод внутренней точки для линейного программирования. Он был предложен в 1989 году Санджаем Мехротрой. Метод основан на том, что на каждой итерации алгоритма внутренней точки необходимо вычислять разложение Чолеского (факторизацию) большой матрицы для нахождения направления поиска. Эта факторизация является наиболее вычислительно затратным этапом алгоритма. Поэтому целесообразно использовать одно и то же разложение несколько раз, прежде чем пересчитывать его. На каждой итерации алгоритма метод прогноза-коррекции Мехроты использует одно и то же разложение Чолеского для нахождения двух различных направлений: направления прогноза и направления коррекции. Идея заключается в том, чтобы сначала вычислить оптимизирующее направление поиска, основанное на члене первого порядка (направление прогноза). Размер шага, который можно сделать в этом направлении, используется для оценки необходимой коррекции центральности. Затем вычисляется корректирующий член, включающий как член центральности, так и член второго порядка. Полное направление поиска — это сумма направления прогноза и направления коррекции. Несмотря на отсутствие пока теоретической оценки сложности, метод прогноза-коррекции Мехроты широко применяется на практике. Его корректирующий шаг эффективно использует то же разложение Чолеского, полученное на этапе прогноза, и поэтому он лишь незначительно дороже стандартного алгоритма внутренней точки. Однако дополнительные накладные расходы на итерацию обычно компенсируются уменьшением количества итераций, необходимых для достижения оптимального решения. Кроме того, он демонстрирует быструю сходимость при приближении к оптимуму.
Mehrotra's predictor–corrector method in optimization is a specific interior point method for linear programming. 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.
Вывод
Вывод этого раздела соответствует плану, предложенному Носедалом и Райтом.
Длина шагов
В практических реализациях выполняется вариант поиска вдоль прямой (line search) для определения максимальной длины шага, которую можно сделать в направлении поиска, не нарушая условие неотрицательности.
Адаптация к квадрическому программированию
Хотя модификации, предложенные Мехротрой, предназначались для алгоритмов внутренней точки в линейном программировании, эти идеи были расширены и успешно применены также и к квадратичному программированию.