Методы доверительных областей (Trust Region) в нелинейной оптимизации
Мощная альтернатива классическому линейному поиску
При решении невероятно сложных задач нелинейной безусловной оптимизации (численный поиск глобального минимума многомерной топологической функции) математики исторически пользуются алгоритмами, идейно основанными на методе касательных Ньютона. Классический итерационный подход называется линейным поиском (Line Search). В нем математический алгоритм сначала строго определяет направление наискорейшего спуска в пространстве (используя вектор антиградиента или матрицу Гессиана), а затем решает одномерную задачу оптимизации: как далеко нужно шагнуть в этом конкретном направлении, чтобы целевая функция гарантированно и максимально уменьшилась. Однако в сильно искривленных топологических оврагах и возле коварных седловых точек выбор базового направления по Гессиану может оказаться катастрофически ошибочным, и линейный поиск быстро зайдет в вычислительный тупик.
Методы доверительных областей (Trust Region Methods) используют совершенно противоположную вычислительную философию. Вместо того чтобы сначала угадать направление, а потом мучительно искать длину геометрического шага, этот мощный алгоритм сначала определяет максимальную допустимую длину шага (сферический радиус доверия), а уже строго внутри этой очерченной пространственной области ищет оптимальное направление и точку минимума.
Построение суррогатной квадратичной модели и адаптивный радиус
На каждом шаге вычислений алгоритм Trust Region математически строит вокруг текущей рабочей точки сильно упрощенную суррогатную модель целевой функции. Обычно это гладкая квадратичная многомерная парабола, вычисляемая с использованием обрезки ряда Тейлора строго до второй производной. Мы из анализа знаем, что эта невероятно простая для расчетов парабола хорошо совпадает с реальной сложной физической функцией только в очень небольшой окрестности вокруг текущей точки аппроксимации. Эта локальная окрестность (гиперсфера в многомерном пространстве) и называется доверительной областью алгоритма.
Затем численный алгоритм ищет строгий локальный минимум именно этой простой суррогатной квадратичной модели, но с очень жестким математическим ограничением — итоговое решение ни при каких условиях не должно выходить за пределы вычисленного радиуса доверительной гиперсферы. Найдя перспективную пробную точку, алгоритм проверяет ее на реальной (исходной сложнейшей) целевой функции. Вычисляется важный коэффициент согласования: точное отношение реального падения функции к теоретически предсказанному падению на параболе. Если предсказание совпало с суровой реальностью (коэффициент оказался близок к 1), значит наша квадратичная модель отлично описывает физику! Алгоритм с радостью принимает шаг и на следующей итерации оптимистично увеличивает радиус доверия. Если же реальное значение функции оказалось значительно хуже предсказанного (парабола «обманула» расчеты из-за сверхвысокой нелинейности), шаг немедленно отвергается, точка не меняется, а радиус доверительной области принудительно и жестко сжимается. Этот класс методов обладает потрясающей робастностью сходимости.