Ускорение интервальных методов ветвей и границ

Процедуры локального поиска могут быстро найти локальный минимум локально выпуклой функции. Алгоритмы ветвей и границ, однако, имеют тенденцию тратить много рабочего времени, пытаясь отбросить области, закрытые для этих локальных минимумов. Поэтому, на практике, важно объединять чистые методы ветвей и границ с дополнительными тестами для ускорения сходимости.

Если целевая функция ¦ дифференцируема достаточное количество раз, то простой способ ускорить метод ветвей и границ состоит в использовании одного из многих быстрых методов локальной оптимизации [10]. Локальная оптимизация может быть совмещена с интервальными проверками для градиента или гессиана: если интервальная оценка для градиента Ñ ¦ на подобласти D не содержит 0, то D не может содержать локальный минимизатор. Если интервальная оценка для гессиана показывает, что он положительно определен на D, то D также не может содержать локальный минимизатор.

Back-Boxing

Back-Boxing [1] – методика ускорения для алгоритмов ветвей и границ, объединяющая процедуры быстрого локального поиска с результатом проверяющих методов для устранения и уменьшения большого объема выполненной работы, когда она выполняется вблизи локального минимума. Цель Back-Boxing ’а состоит в том, чтобы определить большие области в W, где целевая функция ¦ гарантированно имеет один локальный минимум. Если только такие области известны, их локальный минимум может быть вычислен эффективно и затем проверен, является ли он глобальным минимумом.

Back-Boxing первоначально локализует минимум x ^* в некоторой подобласти D. Затем ищется наибольший параллелепипед B ÍD, такой, что x ^* - уникальный локальный минимум для B; область D\ B затем помещается в список L для дальнейшей обработки. Поскольку мы теперь знаем, что параллелепипед B имеет уникальный минимум, нам в дальнейшем не нужно делить B, в попытке найти меньшее значение функции.