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

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

Цель

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

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

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

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

Приложения

Первое применение MLMC приписывают Майку Джайлзу. ^[2] в контексте стохастических дифференциальных уравнений (СДУ) для ценообразования опционов , однако более ранние следы обнаруживаются в работах Генриха в контексте параметрического интегрирования. ^[3] Здесь случайная величина $G=f(X(T))$ известна как функция выигрыша, а последовательность аппроксимаций $G_{\ell }$ , $\ell =0,\ldots ,L$ использовать приближение к пути выборки $X(t)$ с шагом по времени $h_{\ell }=2^{-\ell }T$ .

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

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

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

 $L\gets 0$ 
repeat
    Take warm-up samples at level  $L$ 
    Compute the sample variance on all levels  $\ell =0,\ldots ,L$ 
    Define the optimal number of samples  $N_{\ell }$  on all levels  $\ell =0,\ldots ,L$ 
    Take additional samples on each level  $\ell$  according to  $N_{\ell }$ 
    if  $L\geq 2$  then
        Test for convergence
    end
    if not converged then
         $L\gets L+1$ 
    end
until converged

Расширения MLMC

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

См. также

Ссылки

^ Джайлз, МБ (2015). «Многоуровневые методы Монте-Карло». Акта Нумерика . 24 : 259–328. arXiv : 1304.5472 . дои : 10.1017/s096249291500001x . S2CID 13805654 .
^ Джайлз, МБ (2008). «Многоуровневое моделирование пути Монте-Карло» . Исследование операций . 56 (3): 607–617. CiteSeerX 10.1.1.121.713 . дои : 10.1287/opre.1070.0496 . S2CID 3000492 .
^ Генрих, С. (2001). «Многоуровневые методы Монте-Карло». Крупномасштабные научные вычисления . Конспекты лекций по информатике. Том. 2179. Спрингер. стр. 58–67. дои : 10.1007/3-540-45346-6_5 . ISBN 978-3-540-43043-8 .
^ Клифф, А.; Джайлз, МБ; Шейхл, Р.; Текцентрруп, А. (2011). «Многоуровневые методы Монте-Карло и приложения к эллиптическим уравнениям частного уравнения со случайными коэффициентами» (PDF) . Вычисления и визуализация в науке . 14 (1): 3–15. дои : 10.1007/s00791-011-0160-x . S2CID 1687254 .
^ Писарони, М.; Нобиле, ФБ; Лейланд, П. (2017). «Продолжение многоуровневого метода Монте-Карло для количественного определения неопределенности в аэродинамике сжимаемой невязкой жидкости» (PDF) . Компьютерные методы в прикладной механике и технике . 326 (С): 20–50. дои : 10.1016/j.cma.2017.07.030 . S2CID 10379943 . Архивировано из оригинала (PDF) 14 февраля 2018 г.
^ Хаджи-Али, Алабама; Нобиле, Ф.; Темпоне, Р. (2016). «Мультииндексный Монте-Карло: когда разреженность встречается с выборкой». Нумерическая математика . 132 (4): 767–806. arXiv : 1405.3757 . дои : 10.1007/s00211-015-0734-5 . S2CID 253742676 .
^ Джайлз, МБ; Уотерхаус, Б. (2009). «Многоуровневое моделирование пути квази-Монте-Карло» (PDF) . Расширенное финансовое моделирование, серия «Радон» по вычислительной и прикладной математике . Де Грюйтер: 165–181.
^ Робб, П.; Нуйенс, Д.; Вандевалле, С. (2017). «Многоиндексный алгоритм квазимонте-карло для задач логнормальной диффузии». Журнал SIAM по научным вычислениям . 39 (5): А1811–С392. arXiv : 1608.03157 . Бибкод : 2017ГАК...39С.851Р . дои : 10.1137/16M1082561 . S2CID 42818387 .

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

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

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

[4] Клифф, А.; Джайлз, МБ; Шейхл, Р.; Текцентрруп, А. (2011). «Многоуровневые методы Монте-Карло и приложения к эллиптическим уравнениям частного уравнения со случайными коэффициентами» (PDF) . Вычисления и визуализация в науке . 14 (1): 3–15. дои : 10.1007/s00791-011-0160-x . S2CID 1687254 .

[5] Писарони, М.; Нобиле, ФБ; Лейланд, П. (2017). «Продолжение многоуровневого метода Монте-Карло для количественного определения неопределенности в аэродинамике сжимаемой невязкой жидкости» (PDF) . Компьютерные методы в прикладной механике и технике . 326 (С): 20–50. дои : 10.1016/j.cma.2017.07.030 . S2CID 10379943 . Архивировано из оригинала (PDF) 14 февраля 2018 г.

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

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

[8] Робб, П.; Нуйенс, Д.; Вандевалле, С. (2017). «Многоиндексный алгоритм квазимонте-карло для задач логнормальной диффузии». Журнал SIAM по научным вычислениям . 39 (5): А1811–С392. arXiv : 1608.03157 . Бибкод : 2017ГАК...39С.851Р . дои : 10.1137/16M1082561 . S2CID 42818387 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]