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

Доверительная область — обобщённое понятие доверительного интервала на случай многомерного параметра целевой функции, которая аппроксимируется с помощью числовой функции, часто квадратичной: если найдена числовая функция, соответствующая точности целевой функции внутри доверительной области, то область расширяется, и наоборот, если точность аппроксимации низкая, то область сужается. Под точностью аппроксимации обычно понимается ширина доверительной области.

Метод доверительной области известен также, как одношаговый метод. В некотором смысле он двойственен методу линейного поиска — в методе доверительной области сначала выбирают размер шага (размер доверительной области), затем его направление, в методе линейного поиска выбирают, сначала направление шага, а затем его размер.

Подходящий размер вычисляется после сравнения отношения ожидаемого улучшения по числовой функции и действительного улучшения, полученного вычислением целевой функции,

В качестве критерия расширения или сужения, используется простой принцип — числовая функция достоверна только в области, где она обеспечивает приемлемую аппроксимацию.

Пример

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

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

[math]\displaystyle{ \Delta f_a = f(x) - f(x + \Delta x). }[/math]

После вычисления отношения [math]\displaystyle{ \Delta f_p/\Delta f_a }[/math] мы можем изменить размер доверительной области. В общем случае ожидается, что [math]\displaystyle{ \Delta f_p }[/math] будет чуть меньше, чем [math]\displaystyle{ \Delta f_a }[/math], так что отношение окажется в интервале между 0.25 и 0.5. Если отношение больше 0.5, то значит взят слишком большой шаг, поэтому требуется расширить доверительную область (уменьшить [math]\displaystyle{ \lambda }[/math]) и продолжить итерации. Если отношение меньше 0.25, то истинная функция «слишком сильно» отличается от аппроксимации в доверительной области, значит требуется уменьшить доверительную область (увеличиваем [math]\displaystyle{ \lambda }[/math]) и продолжить итерации.

Ссылки

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