Глобальная оптимизация: интервальный анализ и методы гарантированного поиска

Основой метода является интервальная арифметика, заложенная Рамоном Муром в 1960-х годах. Вместо оперирования конкретными числами с плавающей запятой, алгоритм работает с интервалами (например, $X = [a, b]$). Для всех базовых математических операций (сложение, умножение, функции $\sin$, $\exp$) выводятся интервальные аналоги. Если мы подставим интервал $X$ в интервальное расширение функции $F(X)$, мы получим новый интервал $Y = [c, d]$, который гарантированно содержит внутри себя все возможные значения исходной функции для любого $x \in X$. Это свойство "гарантированного включения" является математическим сердцем метода.

Алгоритм глобальной оптимизации строится на базе метода ветвей и границ, применяемого в непрерывном многомерном пространстве (Branch-and-Bound over Intervals). Исходная область (гиперпрямоугольник, или брус) загружается в список. На каждой итерации брус извлекается и делится пополам. Для каждой половины вычисляется интервальное расширение целевой функции $F(X)$. Если нижняя граница полученного интервала оказывается строго больше текущего известного рекорда глобального минимума (верхней оценки), то этот брус безвозвратно отбрасывается. В этой зоне математически не может быть глобального минимума. Если брус отбросить нельзя, он отправляется в очередь для дальнейшего дробления.

Главной проблемой классической интервальной арифметики является "эффект зависимости" (Dependency Problem). Из-за того, что интервальная арифметика не учитывает взаимозависимость вхождений одной и той же переменной в формуле (например, $X - X$ в интервалах даст не 0, а $[-a, a]$), происходит катастрофическое переоценивание ширины интервала (Overestimation). Для борьбы с этим используются продвинутые методы сужения брусьев: Форма Тейлора (Taylor Form), центрированные формы, а также интервальный метод Ньютона, который способен за один шаг кардинально "схлопнуть" область поиска, доказывая отсутствие корней градиента в огромных секторах пространства.

Современные интервальные решатели глобальной оптимизации способны с математической строгостью находить глобальный оптимум и гарантировать его точность, учитывая даже ошибки округления процессора (через направленные округления IEEE 754). Хотя интервальные алгоритмы обладают экспоненциальной вычислительной сложностью в худшем случае, их применение абсолютно необходимо там, где ошибка оптимизатора может привести к техногенной катастрофе. Они превращают процесс оптимизации из "поиска вслепую" в исчерпывающее математическое доказательство.

Список литературы:
1. Moore R.E., Kearfott R.B., Cloud M.J. Introduction to Interval Analysis. — SIAM, 2009.
2. Hansen E., Walster G.W. Global Optimization Using Interval Analysis. — Marcel Dekker, 2004.
3. Шарый С.П. Конечная интервальная арифметика и ее приложения. — Новосибирск: Наука, 2010.