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

Концептуально, в алгоритме Левенберга — Марквардта целевая функция итеративно аппроксимируется поверхностью второго порядка, затем решается соответствующая система линейных уравнений и оценка обновляется, после чего цикл повторяется до достижения нужной точности аппроксимации. Если использовать только этот алгоритм и если начальное предположение было «слишком далеко» от оптимального решения, то метод может не дать сходимости к нужной точности аппроксимации. По этой причине алгоритм ограничивает каждый шаг, предотвращая слишком «далёкую» аппроксимацию. Алгоритм определяет «слишком далеко» следующим образом. Вместо решения ${\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