Просмотр кода страницы Доверительная область

'''Доверительная область''' — обобщение понятия [[Доверительный интервал|доверительного интервала]] на случай [[Многомерный параметр|многомерного параметра]]<ref>''А. Я. Дороговцев''. Доверительная область / [https://search.rsl.ru/ru/record/01006782532 Энциклопедия кибернетики] {{Wayback|url=https://search.rsl.ru/ru/record/01006782532 |date=20210604165836 }} // Ред. коллегия: В. М. Глушков (отв. ред.) и др.; АН УССР. — Киев: Укр. сов. энциклопедия, 1974. — Т. 1: Абс — Мир. — 606 с. — С. 296.</ref><ref>{{Cite web|url=https://search.rsl.ru/ru/record/01006990437|title=Крамер, Харальд - Математические методы статистики [Текст] - Search RSL|website=search.rsl.ru|access-date=2021-06-04|archive-date=2021-06-04|archive-url=https://web.archive.org/web/20210604165830/https://search.rsl.ru/ru/record/01006990437|deadlink=no}}</ref><ref>{{Cite web|url=https://search.rsl.ru/ru/record/01007591211|title=Математическая энциклопедия [Текст] / Гл. ред. И.М. Виноградов - Search RSL|website=search.rsl.ru|access-date=2021-06-04|archive-date=2021-06-04|archive-url=https://web.archive.org/web/20210604165826/https://search.rsl.ru/ru/record/01007591211|deadlink=no}}</ref><ref>{{Книга:Корн Г. А., Корн Т. М.: Справочник по математике|1970|страницы=559}}</ref><ref>{{Cite web|url=https://search.rsl.ru/ru/record/01001507344|title=Справочник по прикладной статистике : [В 2 т.] / Под ред. Э. Ллойда, У. Ледермана ; Пер. с англ. под ред. Ю. Н. Тюрина - Search RSL|website=search.rsl.ru|access-date=2021-06-04|archive-date=2021-06-04|archive-url=https://web.archive.org/web/20210604165833/https://search.rsl.ru/ru/record/01001507344|deadlink=no}}</ref><ref>{{Cite web|url=https://search.rsl.ru/ru/record/01007394436|title=Кендэл, Морис Джордж - Статистические выводы и связи [Текст] - Search RSL|website=search.rsl.ru|access-date=2021-06-04|archive-date=2021-06-04|archive-url=https://web.archive.org/web/20210604165833/https://search.rsl.ru/ru/record/01007394436|deadlink=no}}</ref> [[Функция потерь|целевой функции]], которая [[Аппроксимация|аппроксимируется]] с помощью [[Числовая функция|числовой функции]], часто [[Квадратичная функция одной переменной|квадратичной]]: если найдена числовая функция, соответствующая точности целевой функции внутри доверительной области, то область расширяется, и наоборот, если точность [[аппроксимация|аппроксимации]] низкая, то область сужается. Под точностью аппроксимации обычно понимается ширина доверительной области<ref>{{статья|ссылка=https://cyberleninka.ru/article/n/primenenie-metoda-statisticheskih-ispytaniy-dlya-izucheniya-harakteristik-rasseyaniya-vyborochnyh-krivyh-povtoryaemosti|автор=Картамышев А. И., Коноплев Л. Н.|заглавие=Применение метода статистических испытаний для изучения характеристик рассеяния выборочных кривых повторяемости|год=1976|издание=Ученые записки ЦАГИ|номер=5|archivedate=2021-06-04|archiveurl=https://web.archive.org/web/20210604165829/https://cyberleninka.ru/article/n/primenenie-metoda-statisticheskih-ispytaniy-dlya-izucheniya-harakteristik-rasseyaniya-vyborochnyh-krivyh-povtoryaemosti}}</ref>.

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

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

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

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

Смысл заключается в том, чтобы изменять размер доверительной области (<math>\lambda</math>). На каждой итерации квадратичная аппроксимация предсказывает уменьшение целевой функции <math>\Delta f_p</math> (здесь и ниже <math>f_p</math> означает полученное аппроксимацией значение, а <math>f_a </math> означает действительное значение функции), которая ожидается меньшей по сравнению с истинным уменьшением. Если дано <math>\Delta x</math>, мы можем вычислить
: <math>\Delta f_a = f(x) - f(x + \Delta x).</math>
После вычисления отношения <math>\Delta f_p/\Delta f_a</math> мы можем изменить размер доверительной области. В общем случае ожидается, что <math>\Delta f_p</math> будет чуть меньше, чем <math>\Delta f_a</math>, так что отношение окажется в интервале между 0.25 и 0.5. Если отношение больше 0.5, то значит взят слишком большой шаг, поэтому требуется расширить доверительную область (уменьшить <math>\lambda</math>) и продолжить итерации. Если отношение меньше 0.25, то истинная функция «слишком сильно» отличается от аппроксимации в доверительной области, значит требуется уменьшить доверительную область (увеличиваем <math>\lambda</math>) и продолжить итерации.

== Литература ==
{{refbegin|colwidth=30em}}
* {{книга|автор=Andrew R. Conn, Nicholas I. M. Gould, Philippe L. Toint|ссылка=https://books.google.com/books?id=5kNC4fqssYQC|заглавие=Trust-Region Methods|серия=MPS-SIAM Series on Optimization}}
* {{статья|автор=Byrd R. H, Schnabel R. B., Schultz G. A.|ссылка=http://epubs.siam.org/doi/abs/10.1137/0724076|заглавие=A trust region algorithm for nonlinearly constrained optimization|издание=SIAM J. Numer. Anal.,|том=24|год=1987|страницы=1152–1170}}
* {{статья|ref=Sorensen|автор=Sorensen D. C.|ссылка=http://epubs.siam.org/doi/abs/10.1137/0719026|заглавие=Newton’s Method with a Model Trust Region Modification|издание=SIAM J. Numer. Anal.|том=19|номер=2|год=1982}}
* {{книга|автор=Yuan Y.|ссылка=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.9964|часть=A review of trust region algorithms for optimization|заглавие=ICIAM 99: Proceedings of the Fourth International Congress on Industrial & Applied Mathematics, Edinburgh|год=2000|издательство=Oxford University Press, USA}}
* {{статья|автор=Yuan Y.|ссылка=https://link.springer.com/article/10.1007%2Fs10107-015-0893-2|заглавие=Recent Advances in Trust Region Algorithms|издание=Math. Program.|год=2015}}
{{refend}}

== Примечания ==
{{примечания|2}}

== Ссылки ==
* [http://www.applied-mathematics.net/optimization/optimizationIntro.html Kranf site: Trust Region Algorithms]
* [https://optimization.mccormick.northwestern.edu/index.php/Trust-region_methods Trust-region methods]

{{Методы оптимизации|state=collapsed}}
[[Категория:Алгоритмы и методы оптимизации]]
{{rq|checktranslate|style|grammar}}