Подопечный

редактировать

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

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

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

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

Пример

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

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

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

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

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

Ссылки

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

Внешние ссылки

Сайт Kranf: Алгоритмы доверительной области
Методы доверительной области