Interested Article - Доверительная область
- 2020-12-10
- 1
Доверительная область — обобщение понятия доверительного интервала на случай целевой функции , которая аппроксимируется с помощью числовой функции , часто квадратичной : если найдена числовая функция, соответствующая точности целевой функции внутри доверительной области, то область расширяется, и наоборот, если точность аппроксимации низкая, то область сужается. Под точностью аппроксимации обычно понимается ширина доверительной области .
Метод доверительной области известен также, как . В некотором смысле он двойственен методу линейного поиска — в методе доверительной области сначала выбирают размер шага (размер доверительной области), затем его направление, в методе линейного поиска выбирают, сначала направление шага, а затем его размер.
Подходящий размер вычисляется после сравнения отношения ожидаемого улучшения по числовой функции и действительного улучшения, полученного вычислением целевой функции ,
В качестве критерия расширения или сужения, используется простой принцип — числовая функция достоверна только в области, где она обеспечивает приемлемую аппроксимацию.
Пример
Концептуально, в алгоритме Левенберга — Марквардта целевая функция итеративно аппроксимируется поверхностью второго порядка , затем решается соответствующая система линейных уравнений и оценка обновляется, после чего цикл повторяется до достижения нужной точности аппроксимации. Если использовать только этот алгоритм и если начальное предположение было «слишком далеко» от оптимального решения, то метод может не дать сходимости к нужной точности аппроксимации. По этой причине алгоритм ограничивает каждый шаг, предотвращая слишком «далёкую» аппроксимацию. Алгоритм определяет «слишком далеко» следующим образом. Вместо решения относительно метод предлагает решать , где является диагональной матрицей с той же диагональю, что и у матрицы A , а является параметром, который контролирует размер доверительной области. Геометрически, метод добавляет параболоид с центром в , что приводит к меньшему шагу каждой итерации.
Смысл заключается в том, чтобы изменять размер доверительной области ( ). На каждой итерации квадратичная аппроксимация предсказывает уменьшение целевой функции (здесь и ниже означает полученное аппроксимацией значение, а означает действительное значение функции), которая ожидается меньшей по сравнению с истинным уменьшением. Если дано , мы можем вычислить
После вычисления отношения мы можем изменить размер доверительной области. В общем случае ожидается, что будет чуть меньше, чем , так что отношение окажется в интервале между 0.25 и 0.5. Если отношение больше 0.5, то значит взят слишком большой шаг, поэтому требуется расширить доверительную область (уменьшить ) и продолжить итерации. Если отношение меньше 0.25, то истинная функция «слишком сильно» отличается от аппроксимации в доверительной области, значит требуется уменьшить доверительную область (увеличиваем ) и продолжить итерации.
Литература
- Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint. . — (MPS-SIAM Series on Optimization).
- Byrd R. H, Schnabel R. B., Schultz G. A. // SIAM J. Numer. Anal.,. — 1987. — Т. 24 . — С. 1152–1170 .
- Sorensen D. C. // SIAM J. Numer. Anal.. — 1982. — Т. 19 , № 2 .
- Yuan Y. A review of trust region algorithms for optimization // . — Oxford University Press, USA, 2000.
- Yuan Y. // Math. Program.. — 2015.
Примечания
- А. Я. Дороговцев . Доверительная область / от 4 июня 2021 на Wayback Machine // Ред. коллегия: В. М. Глушков (отв. ред.) и др.; АН УССР. — Киев: Укр. сов. энциклопедия, 1974. — Т. 1: Абс — Мир. — 606 с. — С. 296.
- . search.rsl.ru . Дата обращения: 4 июня 2021. 4 июня 2021 года.
- . search.rsl.ru . Дата обращения: 4 июня 2021. 4 июня 2021 года.
- Корн Г. А., Корн Т. М. . — М. : « Наука », 1970. — С. 559.
- . search.rsl.ru . Дата обращения: 4 июня 2021. 4 июня 2021 года.
- . search.rsl.ru . Дата обращения: 4 июня 2021. 4 июня 2021 года.
- Картамышев А. И., Коноплев Л. Н. // Ученые записки ЦАГИ. — 1976. — № 5 . 4 июня 2021 года.
Ссылки
- 2020-12-10
- 1