Регион доверия - Trust region

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

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

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

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

Пример

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

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

{ displaystyle Delta f _ { text {actual}} = f (x) -f (x + Delta x).}

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

внешняя ссылка

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

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

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

[1]

[2]

[3]

Регион доверия - Trust region

Пример

Рекомендации

внешняя ссылка