Доверительная область

Концептуально, в алгоритме Левенберга — Марквардта целевая функция итеративно аппроксимируется поверхностью второго порядка, затем решается соответствующая система линейных уравнений и оценка обновляется, после чего цикл повторяется до достижения нужной точности аппроксимации. Если использовать только этот алгоритм то метод может не дать сходимости к нужной точности аппроксимации, если начальное предположение было «слишком далеко» от оптимального решения. По этой причине алгоритм ограничивает каждый шаг, предотвращая слишком «далёкую» аппроксимацию. Алгоритм определяет «слишком далеко» следующим образом. Вместо решения ${\displaystyle A\,\Delta x=b}$ относительно ${\displaystyle \Delta x}$ метод предлагает решать ${\displaystyle {\big (}A+\lambda \operatorname {diag} (A){\big )}\,\Delta x=b}$, где ${\displaystyle \operatorname {diag} (A)}$ является диагональной матрицей с той же диагональю, что и у матрицы A, а ${\displaystyle \lambda }$ является параметром, который контролирует размер доверительной области. Геометрически, метод добавляет параболоид с центром в ${\displaystyle \Delta x=0}$, что приводит к меньшему шагу каждой итерации.

Смысл заключается в том, чтобы изменять размер доверительной области (${\displaystyle \lambda }$). На каждой итерации квадратичная аппроксимация предсказывает уменьшение целевой функции ${\displaystyle \Delta f_{p}}$ (здесь и ниже ${\displaystyle f_{p}}$ означает полученное аппроксимацией значение, а ${\displaystyle f_{a}}$ означает действительное значение функции), которая ожидается меньшей по сравнению с истинным уменьшением. Если дано ${\displaystyle \Delta x}$, мы можем вычислить

${\displaystyle \Delta f_{a}=f(x)-f(x+\Delta x).}$

После вычисления отношения ${\displaystyle \Delta f_{p}/\Delta f_{a}}$ мы можем изменить размер доверительной области. В общем случае ожидается, что ${\displaystyle \Delta f_{p}}$ будет чуть меньше, чем ${\displaystyle \Delta f_{a}}$, так что отношение окажется в интервале между 0,25 и 0,5. Если отношение больше 0,5, то значит взят слишком большой шаг, поэтому требуется расширить доверительную область (уменьшить ${\displaystyle \lambda }$) и продолжить итерации. Если отношение меньше 0,25, то истинная функция «слишком сильно» отличается от аппроксимации в доверительной области, значит требуется уменьшить доверительную область (увеличиваем ${\displaystyle \lambda }$) и продолжить итерации.

• Kranf site: Trust Region Algorithms
• Trust-region methods