Кіріспе
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.
Алыстыру
Бұл бөлімнің туындысы Носедал мен Райт ұсынған жоспар бойынша жүргізілді.
Қадам ұзындығы
Іс жүзіндегі қолдануларда іздеу бағытында теріс мәнді бұзбастан жасала алатын ең үлкен қадам ұзындығын табу үшін сызықтық іздеудің бір түрі қолданылады.
Квадраттық бағдарламалауға бейімделу
Мехротра ұсынған өзгерістер сызықтық бағдарламалаудың ішкі нүктелік алгоритмдері үшін жасалғанмен, осы идеялар кеңейтіліп, квадралық бағдарламалау саласында да сәтті қолданылды.