Многоуровневый метод Монте-Карло - Multilevel Monte Carlo method

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

Цель

Цель многоуровневого метода Монте-Карло - аппроксимировать ожидаемое значение ${ displaystyle operatorname {E} [G]}$ из случайная переменная ${ displaystyle G}$ это результат стохастическое моделирование. Предположим, что эту случайную величину невозможно точно смоделировать, но существует последовательность приближений ${ Displaystyle G_ {0}, G_ {1}, ldots, G_ {L}}$ с увеличением точности, но также и с увеличением стоимости, которая сходится к ${ displaystyle G}$ так как ${ Displaystyle L rightarrow infty}$ . В основе многоуровневого метода лежит телескопическая сумма личность^[1]

{ displaystyle operatorname {E} [G_ {L}] = operatorname {E} [G_ {0}] + sum _ { ell = 1} ^ {L} operatorname {E} [G _ { ell } -G _ { ell -1}],}

что тривиально выполняется из-за линейности оператора математического ожидания. Каждое из ожиданий ${ displaystyle operatorname {E} [G _ { ell} -G _ { ell -1}]}$ затем аппроксимируется методом Монте-Карло, в результате чего получается многоуровневый метод Монте-Карло. Обратите внимание, что взяв образец разницы ${ displaystyle G _ { ell} -G _ { ell -1}}$ в уровень ${ displaystyle ell}$ требуется симуляция обоих ${ displaystyle G _ { ell}}$ и ${ displaystyle G _ { ell -1}}$ .

Метод MLMC работает, если отклонения ${ displaystyle operatorname {V} [G _ { ell} -G _ { ell -1}] rightarrow 0}$ так как ${ displaystyle ell rightarrow infty}$ , что будет иметь место, если оба ${ displaystyle G _ { ell}}$ и ${ displaystyle G _ { ell -1}}$ приблизительно одинаковая случайная величина ${ displaystyle G}$ . Посредством Центральная предельная теорема, это означает, что требуется все меньше и меньше выборок, чтобы точно аппроксимировать математическое ожидание разницы. ${ displaystyle G _ { ell} -G _ { ell -1}}$ так как ${ displaystyle ell rightarrow infty}$ . Следовательно, большинство проб будет отобрано на уровне ${ displaystyle 0}$ , где образцы дешевы, и потребуется очень мало образцов на самом высоком уровне ${ displaystyle L}$ . В этом смысле MLMC можно рассматривать как рекурсивную управление варьировать стратегия.

Приложения

Аппроксимация пробного тракта СДУ на разных уровнях.

Первое приложение MLMC приписывают Джайлзу,^[2] в контексте стохастические дифференциальные уравнения (SDE) для опционная цена Однако более ранние следы обнаруживаются в работе Генриха в контексте параметрического интегрирования.^[3] Здесь случайная величина ${ Displaystyle G = е (Х (Т))}$ называется функцией выигрыша, а последовательность приближений ${ displaystyle G _ { ell}}$ , ${ Displaystyle ell = 0, ldots, L}$ использовать приближение к траектории образца ${ Displaystyle X (т)}$ с шагом по времени ${ displaystyle h _ { ell} = 2 ^ {- ell} T}$ .

Применение MLMC к проблемам в количественная оценка неопределенности (UQ) - активная область исследований.^[4]^[5] Важным прототипическим примером этих проблем являются: уравнения в частных производных (PDE) с случайные коэффициенты. В этом контексте случайная величина ${ displaystyle G}$ называется интересующей величиной, а последовательность приближений соответствует дискретизация PDE с различными размерами ячеек.

Алгоритм моделирования MLMC

Ниже в псевдокоде приводится простой алгоритм с адаптацией к уровню для моделирования MLMC.

 ${ displaystyle L получает 0}$ повторение    Взять образцы для разминки на уровне  ${ displaystyle L}$     Вычислить выборочную дисперсию на всех уровнях  ${ Displaystyle ell = 0, ldots, L}$     Определите оптимальное количество образцов  ${ displaystyle N _ { ell}}$  на всех уровнях  ${ Displaystyle ell = 0, ldots, L}$     Возьмите дополнительные образцы на каждом уровне  ${ displaystyle ell}$  согласно с  ${ displaystyle N _ { ell}}$     если  ${ displaystyle L geq 2}$  тогда        Тест на сходимость конец    если не сходится тогда         ${ displaystyle L получает L + 1}$     конецдо тех пор сходился

Расширения MLMC

Недавние расширения многоуровневого метода Монте-Карло включают многоиндексный Монте-Карло,^[6] где рассматривается более одного направления уточнения, и сочетание MLMC с Квази-Монте-Карло метод.^[7]^[8]

Смотрите также

использованная литература

^ Джайлз, М. Б. (2015). «Многоуровневые методы Монте-Карло». Acta Numerica. 24: 259–328. arXiv:1304.5472. Дои:10.1017 / s096249291500001x.
^ Джайлз, М. Б. (2008). «Многоуровневое моделирование траектории Монте-Карло». Исследование операций. 56 (3): 607–617. CiteSeerX 10.1.1.121.713. Дои:10.1287 / opre.1070.0496.
^ Генрих, С. (2001). «Многоуровневые методы Монте-Карло». Конспект лекций по информатике (многосеточные методы). Конспект лекций по информатике. Springer. 2179: 58–67. Дои:10.1007/3-540-45346-6_5. ISBN 978-3-540-43043-8.
^ Клифф, А .; Giles, M. B .; Scheichl, R .; Текентруп А. (2011). «Многоуровневые методы Монте-Карло и приложения к эллиптическим УЧП со случайными коэффициентами» (PDF). Вычислительная техника и визуализация в науке. 14 (1): 3–15. Дои:10.1007 / s00791-011-0160-х.
^ Pisaroni, M .; Nobile, F. B .; Лейланд, П. (2017). «Продолжение многоуровневого метода Монте-Карло для количественной оценки неопределенности в сжимаемой невязкой аэродинамике» (PDF). Компьютерные методы в прикладной механике и технике. 326 (C): 20–50. Дои:10.1016 / j.cma.2017.07.030.
^ Хаджи-Али, А.Л .; Нобиле, Ф .; Темпоне, Р. (2016). «Мультииндексный Монте-Карло: когда разреженность встречается с выборкой». Numerische Mathematik. 132 (4): 767–806. arXiv:1405.3757. Дои:10.1007 / s00211-015-0734-5.
^ Giles, M. B .; Уотерхаус, Б. (2009). «Многоуровневое моделирование траектории квази-Монте-Карло» (PDF). Расширенное финансовое моделирование, серия Radon по вычислительной и прикладной математике. Де Грюйтер: 165–181.
^ Robbe, P .; Nuyens, D .; Вандевалле, С. (2017). «Многоиндексный квази-Монте-Карло алгоритм для задач логнормальной диффузии». Журнал SIAM по научным вычислениям. 39 (5): A1811 – C392. arXiv:1608.03157. Дои:10.1137 / 16M1082561.

[1] Джайлз, М. Б. (2015). «Многоуровневые методы Монте-Карло». Acta Numerica. 24: 259–328. arXiv:1304.5472. Дои:10.1017 / s096249291500001x.

[2] Джайлз, М. Б. (2008). «Многоуровневое моделирование траектории Монте-Карло». Исследование операций. 56 (3): 607–617. CiteSeerX 10.1.1.121.713. Дои:10.1287 / opre.1070.0496.

[3] Генрих, С. (2001). «Многоуровневые методы Монте-Карло». Конспект лекций по информатике (многосеточные методы). Конспект лекций по информатике. Springer. 2179: 58–67. Дои:10.1007/3-540-45346-6_5. ISBN 978-3-540-43043-8.

[4] Клифф, А .; Giles, M. B .; Scheichl, R .; Текентруп А. (2011). «Многоуровневые методы Монте-Карло и приложения к эллиптическим УЧП со случайными коэффициентами» (PDF). Вычислительная техника и визуализация в науке. 14 (1): 3–15. Дои:10.1007 / s00791-011-0160-х.

[5] Pisaroni, M .; Nobile, F. B .; Лейланд, П. (2017). «Продолжение многоуровневого метода Монте-Карло для количественной оценки неопределенности в сжимаемой невязкой аэродинамике» (PDF). Компьютерные методы в прикладной механике и технике. 326 (C): 20–50. Дои:10.1016 / j.cma.2017.07.030.

[6] Хаджи-Али, А.Л .; Нобиле, Ф .; Темпоне, Р. (2016). «Мультииндексный Монте-Карло: когда разреженность встречается с выборкой». Numerische Mathematik. 132 (4): 767–806. arXiv:1405.3757. Дои:10.1007 / s00211-015-0734-5.

[7] Giles, M. B .; Уотерхаус, Б. (2009). «Многоуровневое моделирование траектории квази-Монте-Карло» (PDF). Расширенное финансовое моделирование, серия Radon по вычислительной и прикладной математике. Де Грюйтер: 165–181.

[8] Robbe, P .; Nuyens, D .; Вандевалле, С. (2017). «Многоиндексный квази-Монте-Карло алгоритм для задач логнормальной диффузии». Журнал SIAM по научным вычислениям. 39 (5): A1811 – C392. arXiv:1608.03157. Дои:10.1137 / 16M1082561.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]