Доверительный регион

В математической оптимизации область доверия — это подмножество области целевой функции , которая аппроксимируется с помощью модельной функции (часто квадратичной ). Если в доверительной области найдена адекватная модель целевой функции, то область расширяется; и наоборот, если приближение плохое, область сжимается.

Соответствие оценивается путем сравнения отношения ожидаемого улучшения от аппроксимации модели с фактическим улучшением, наблюдаемым в целевой функции. Простое установление порога отношения используется в качестве критерия расширения и сжатия - модельной функции «доверяют» только в той области, где она обеспечивает разумное приближение.

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

Общая идея методов доверительной области известна под многими именами; самое раннее использование этого термина, по-видимому, принадлежит Соренсену (1982). ^[1] Популярный учебник Флетчера (1980) называет эти алгоритмы методами с ограниченным шагом . ^[2] Кроме того, в ранней основополагающей работе по этому методу Голдфельд , Квандт и Троттер (1966) называют его квадратичным восхождением на холм . ^[3]

Пример [ править ]

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

Хитрость заключается в том, чтобы изменить размер доверительной области (λ). На каждой итерации демпфированная квадратичная аппроксимация предсказывает определенное уменьшение функции стоимости: $\Delta f_{\text{pred}}$ , что, как мы ожидаем, будет меньшим сокращением, чем истинное сокращение. Данный $\Delta x$ , мы можем оценить

\Delta f_{\text{actual}}=f(x)-f(x+\Delta x).

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

Ссылки [ править ]

^ Соренсен, округ Колумбия (1982). «Метод Ньютона с модификацией модельной доверительной области» . СИАМ Дж. Нумер. Анал . 19 (2): 409–426. дои : 10.1137/0719026 .
^ Флетчер, Роджер (1987) [1980]. «Методы ограниченного шага». Практические методы оптимизации (Второе изд.). Уайли. ISBN 0-471-91547-5 .
^ Голдфельд, Стивен М.; Квандт, Ричард Э.; Троттер, Хейл Ф. (1966). «Максимизация путем квадратичного восхождения на холм». Эконометрика . 34 (3): 541–551. дои : 10.2307/1909768 . JSTOR 1909768 .

Деннис, Дж. Э. младший; Шнабель, Роберт Б. (1983). «Глобально конвергентные модификации метода Ньютона». Численные методы неограниченной оптимизации и нелинейных уравнений . Энглвуд Клиффс: Прентис-Холл. стр. 111–154. ISBN 0-13-627216-9 .
Эндрю Р. Конн, Николас И.М. Гулд, Филипп Л. Туан « Методы доверительной области (серия MPS-SIAM по оптимизации) ».
Берд, Р.Х., Р.Б. Шнабель и Г.А. Шульц. « Алгоритм доверительной области для оптимизации с нелинейными ограничениями », SIAM J. Numer. Анал., 24 (1987), стр. 1152–1170.
Юань, Ю. « Обзор алгоритмов доверительной области для оптимизации » в ICIAM 99: Труды Четвертого Международного конгресса по промышленной и прикладной математике, Эдинбург, 2000 Oxford University Press, США.
Юань, Ю. « Последние достижения в алгоритмах доверительной области », Math. Программа., 2015

Внешние ссылки [ править ]

[1] Соренсен, округ Колумбия (1982). «Метод Ньютона с модификацией модельной доверительной области» . СИАМ Дж. Нумер. Анал . 19 (2): 409–426. дои : 10.1137/0719026 .

[2] Флетчер, Роджер (1987) [1980]. «Методы ограниченного шага». Практические методы оптимизации (Второе изд.). Уайли. ISBN 0-471-91547-5 .

[3] Голдфельд, Стивен М.; Квандт, Ричард Э.; Троттер, Хейл Ф. (1966). «Максимизация путем квадратичного восхождения на холм». Эконометрика . 34 (3): 541–551. дои : 10.2307/1909768 . JSTOR 1909768 .

[1]

[2]

[3]