Теория и приложения рандомизованных методов квази Монте-Карло: 2019 г. этап 3

Проект: исполнение гранта/договораисполнение этапа гранта/договора

Сведения о проекте

описание

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








описание для неспециалистов

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

основные результаты по проекту в целом

1-й этап: В России в последние десятилетия выполнен ряд исследованийИ.М. Соболем с соавторами и авторами настоящего проекта. Так, в рамках проекта№ 11-01-00769-а «(Квази) стохастические алгоритмы моделирования: погрешность,параллелизм, аппаратная поддержка» были разработаны методы пониженияконструктивной размерности при решении систем линейных алгебраических уравнений(С.М.Ермаков и А.И.Рукавишникова) и в рамках проекта № 14-01-00271-а«Исследование асинхронных и квази стохастических методов с приложением кнекоторым задачам оценки малых вероятностей» методы оценивания дисперсии дляодного класса случайных кубатур, точных для обобщенных функций Хаара.(С.М.Ермаков и А.А.Антонов).

Упомянутые результаты послужили основой для данного проекта.
В результате его выполнении за первый год работы удалось показать:
1. В области вычисления интегралов [10].
1.1. Удалось качественно обосновать с иллюстрациями и численными примерамиасимптотику убывания остатка квазислучайных кубатур для интегрирования поs-мерному гиперкубу ($s \sim 10-40$).
1.2. Показано, что рандомизация квазислучайных последовательностей приводит кслучайным кубатурным формулам с одним свободным узлом. Это позволяетиспользовать полученные ранее в упомянутой области результаты и снимает рядвопросов. В частности, указана возможность сочетания рандомизованныхквазислучайных чисел и других методов понижения дисперсии — существеннойвыборки, ветвления и др. Для чисел Холтона указана система функций, для которыхточна соответствующая кубатурная формула.
1.3. Установленная связь со случайными кубатурами позволяет дать четкиерекомендации по методике оценки погрешности и построению доверительныхинтервалов в случае рандомизации.
1.4. Были проведены предварительные численные эксперименты по использованиюрандомизованных квазислучайных чисел в следующих областях:
а) Бессеточных методах решения задачи Коши для эллиптических уравнений спостоянными коэффициентами;
б) Методы деревьев и сеток для расчета американских опционов;
в) Многоуровневых методов решения стохастических дифференциальных уравнений,где для оценки дисперсии в схеме Джиллса (M.B. Giles) использовались методыоценки дисперсии, развитые авторами проекта.

2. Была предложена и строго обоснована новая модификация метода имитацииотжига, использующая квазислучайные последовательности и ориентированная наслучай, когда искомый глобальный экстремум не является единственным [1].
Эта модификация особенно перспективна в задачах планирования эксперимента и прирешении больших систем уравнений. В качестве примеров её применения был решенряд задач построения точных D-оптимальных планов для случая, когда функциярегрессии является многочленом второй степени от двух переменных (ищетсяглобальный максимум функции от 6, 8, 20 переменных, решение не являетсяединственным). По результатам экспериментов готовится к публикации статья (С.М.Ермаков, Д.Н. Семенчиков). В качестве примера ниже приведены результаты —точные D-оптимальные планы для квадратичной регрессии от двух переменных вквадрате и усеченном квадрате ( 14 переменных , 16 переменных) (примерно 20 минут работы персональногокомпьютера).
Также с помощью разработанного метода успешно решена достаточно сложнаяприкладная задача о влиянии гомотетии области планирования на число опорныхточек оптимального плана [5,6] (двумерная модель Эйена-Петерса).
Все полученные в области планирования эксперимента результаты являются новыми ипредставляют несомненный прикладной интерес в соответствующих областях.

2-й этап: В течение 2018 года исполнителями проекта были полученыследующие результаты:
1.В области квази случайного интегрирования продолжалось изучение погрешностиметода.
Как было ранее установлено, для кратности интегралов выше 8 асимптотикаостатка, определяемая неравенством Коксмы-Хлавки, достигается при числеиспытаний, не достижимом на современных компьютерах. Для рандомизованного квазиМонте-Карло на численных примерах изучалась средняя асимптотика убываниядоверительного интервала. В рамках экспериментирования были получены интересныерезультаты.
1.Удалось сравнить последовательности Холтона и Соболя и выяснить ихпреимущества и недостатки.
2.В частности, (это ожидаемый результат) рандомизация позволяет эффективновычислять интеграл с особенностью. Также был опробован ряд методов повышенияэффективности случайных квадратур, упомянутых в заявке на 2018 год. Результатыопубликованы в статье S.M.Ermakov, S.N.Leora «Remarks on randomization ofquasi-random numbers» и докладывались на конференции. Эксперименты поприменению квази Монте-Карло в одном из вариантов бессеточного метода длярешения краевых задач привели в целом к отрицательным результатам (улучшения посравнению с обычным Монте-Карло не наблюдалось). Результат обсуждался на конференции (SeventhConference on Finite Difference Methods:Theory and Applications, June 11-16,2018 Lozenetz, Bulgaria) и будет опубликован в её трудах.
В целом, можно отметить, что дляширокого класса задач РММК может быть эффективно использован, но в некоторыхслучаях затраты на его реализацию могут себя не оправдать. Более чёткоеопределение областей эффективной применимости метода предлагается осуществить в следующем году.
2.Задачи оптимизации. Было продолжено изучение предложенной в статье ЕрмаковаС.М., Семенчикова Д.Н. «О методах оптимизации в задачах планированияэксперимента» модификации метода имитации отжига. Получены новые результаты поего усовершенствованию, в частности, с использованием рандомизованных квазислучайных последовательностей. Установлены связи с другими методами поискаглобального экстремума, в особенности с методами генетического типа. Улучшенныеметоды оптимизации были применены к задачам построения точных Д-оптимальныхпланов регрессивного эксперимента и задачам решения систем уравнений. Частьрезультатов докладывалась на международной конференции в Барселоне(подготовлена статья для публикации в трудах конференции, издатель «Шпрингер»)и будет опубликована статья в январском номере журнала «Заводская лаборатория».Примером применения разработанных методов оптимизации может служить решениезадачи влияния гомотетии области планирования на число опорных точекоптимального плана при фиксированных значениях параметров регрессионной модели.В качестве модели выбрана двумерная, нелинейная по параметрам модельКобба-Дугласа, которая используется в микроэкономике. Показано, что существуетдва типа оптимальных планов: насыщенные (т.е. планы, число точек носителякоторых равно числу параметров модели) и избыточные (число точек носителябольше числа параметров модели). Оптимальные планы с минимальным числом точекнайдены в явном виде. Для нахождения планов с большим числом точек использованычисленные методы. В частности, исследован подход, предложенный руководителемпроекта, и заключающийся в модификации метода имитации отжига. Исследованияпоказывают, что данный подход позволяет находить оптимальные планы с высокой точностью.
Запланированные на 2-й год задачи гранта решены полностью. Результаты доложенына двух международных конференциях и опубликованы в 2-х журналах, входящих всистему Scopus, 2 статьи приняты к печати: Ермаков С.М., Семенчиков Д.Н. «Ометодах оптимизации в задачах планирования эксперимента» /Заводская лаборатория(январь 2019г.), Сипин А.С. «Numerical Experiments For Some Markov Models ForSolving Boundary Value Problemsв» в трудах конференции (Seventh Conference onFinite Difference Methods:Theory and Applications, June 11-16, 2018 Lozenetz,Bulgaria), 2 работы подготовлены к печати в Трудах международной конференции(9th International Workshop on Simulation. Universitat Polit ecnica deCatalunya, Barcelona, June 25 - June 29, 2018).
К сожалению, Каштанов Ю.Н. не поместил ссылку на грант в своей публикации, аРукавишникова А.И. не смогла в полной мере участвовать в работе коллектива пообъективным причинам.

3-й этап, заключительный:  Основныерезультаты, полученные в рамках гранта за последние 3 года, распределены по 3направлениям.

1. Квази стохастические методыинтегрирования. Показано, что для кратностей интеграла >=5 известноенеравенство Коксмы-Хлавки – не залог правильного порядка убывания остатка причисле испытаний, которое может быть реализовано на современных компьютерах.Указаны методы оценки реального порядка асимптотики. Проведены численныеэксперименты [4, 2019], [5, 2019].Полученные результаты подтверждены также прирешении некоторых типов краевых задач [1, 2019 ].Изучены рандомизованные(scrambled) квазислучайные последовательности Холтона. Установлена их связь сослучайными квадратурами с одним свободным узлом. Указан класс функций, длякоторых эти квадратуры точны и получено выражение их дисперсии [4,2017].Полученные результаты позволяют дать четкие рекомендации относительноприменения квазислучайных квадратур при вычислении интегралов и решении болеесложных прикладных задач.

2. Получен ряд новых результатов прирешении задач глобальной оптимизации функций многих переменных. Наряду сиспользованием квазислучайных последовательностей на каждом этапе генетическогоалгоритма предложено использовать технику оценки матрицы ковариаций пробныхвекторов. Эта техника была впервые предложена руководителем проекта в 1976году, показала надёжные результаты, но мало использовалась ввиду её большойтрудоёмкости. В работе [8, 2019] доказана лемма, позволяющая уменьшить этутрудоёмкость на порядок. Полученные результаты легли в основу системы программ,позволивших решить несколько сложных задач планирования эксперимента [1, 2019], [2, 2019].В процессе эксплуатации программы продемонстрировали высокую эффективностьразработанных алгоритмов.

3.Как известно, большие системыдифференциальных уравнений возникают при решении широкого круга прикладныхзадач. Простейший пример – задачи массового обслуживания, описываемыемарковскими цепями даже с бесконечным числом состояний. При использованииквазислучайной техники для решения подобных систем было отмечено, чтополученные алгоритмы позволяют также решать стохастические дифференциальныеуравнения. При этом в линейном случае смещение равно нулю (метод Эйлера даётсмещение порядка $\sqrt{\Delta t}$). Это интересный и важный результат ([3,2019], [7, 2019]), требующий дальнейшего развития.

Публикации:

2019г.

1.Sipin, Alexander S., Zeifman, Alexander I. Numerical Experiments for SomeMarkov Models for Solving Boundary Value Problems. 2019, 493-500.
2. Ермаков С.М., Семенчиков Д.Н. О методах оптимизации в задачах планированияэксперимента. Заводская лаборатория. Диагностика материалов, 2019, 85 - 1,72-77.
3. Ермаков, С. М., Товстик, Т. М. Метод Монте-Карло для решения систем ОДУ.Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия,2019, 6(64) - 3, 411-421.
4. Ermakov Sergej M., Leora Svetlana N. Decrease of the mean of thequasi-random integration error. Communications in StatisticsPart B: Simulation and Computation, 2019, 1-9.
5. Ermakov Sergey, Leora Svetlana. Monte Carlo Methods and the Koksma-HlawkaInequality. Mathematics, 2019, 7 - 8, 725.
6. S. M. Ermakov, T.M. Tovstik. Monte Carlo Method for Solving ODE Systems.Vestnik of the St. Petersburg University: Mathematics, 2019, 52 - 3, 272-280.
7. Ermakov Sergej M., Pogosian Anna A. On solving stochastic differentialequations. Monte Carlo Methods and Applications, 2019, 25 - 2, 155-161.
8. Ermakov Sergej M., Semenchikov Dmitriy N. Genetic global optimizationalgorithms. Communications in Statistics Part B: Simulation and Computation,2019, 1-10.
9. Grigoriev Yu. D., Melas V. B., Shpilev P. V. Excess and saturated D-optimaldesigns for the rational model. Statistical Papers, 2019.
10. Sipin Alexander. Monte Carlo Algorithms for the Parabolic Cauchy Problem.Mathematics, 2019, 7 - 2, 177.
11. Alexander S. Sipin. A RANDOMIZED QUASI-MONTE CARLO ALGORITHMS FOR SOMEBOUNDARY VALUE PROBLEMS. 2020.

2018г.

1. S.M.Ermakov, S.N.Leora.  Remarks on randomization ofquasi-random numbers. Monte Carlo Methods and Applications , 2018, 24 - 2,139-145.
2. Yu. D. Grigoriev, V. B. Melas P. V. Shpilev. Excess of locally D-optimaldesigns for Cobb–Douglas model. Statistical Papers, 2018, 59 - 4, 1425–1439,IPF 1.024.
3. Ermakov S.М.,Leora S.N.  Some properties ofquasirandom numbers and their randomization Booklet of Abstracts of the Ninth Workshop on Simulation, Barcеlona,June 25 - June 29, 2018, 19.
4. Ermakov S.М.,Semenchikov D.N . On quasirandom search . Booklet of Abstracts of the NinthWorkshop on Simulation, Barcеlona,June 25 - June 29, 2018,  21.

2017г.
1. Ермаков Сергей Михайлович, Куликов Денис Валерьевич, Леора СветланаНиколаевна. К анализу метода имитации отжига в многоэкстремальном случае.Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия,2017, 4 (62) - 2, 220-226.

2. S. M. Ermakov, D. V. Kulikov, S. N. Leora . Towardsthe Analysis of the Simulated Annealing Method in the Multiextremal Case. ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГОУНИВЕРСИТЕТА МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ,2017 , 50 - 2, 132-137.
3. Ермаков Сергей Михайлович. О рандомизации квазислучайных последовательностейХолтона . Вестник СПбГУ. Математика. Механика. Астрономия,2017, 4(62) - 4,570-576.
4.  S. M.Ermakov . On Randomization of Halton Quasi-Random Sequences . Вестник СПбГУ. Математика.Механика. Астрономия,2017 , 4 - 50, 337-341.
5. Леонов ГеннадийАлексеевич, Товстик Петр Евгеньевич Товстик Татьяна Михайловна. Областидостижимости положений платформы Стьюарта в шестимерном пространстве обобщенныхкоординат. Вестник Санкт-Петербургского университета. Математика. Механика.Астрономия, 2017, 4(62) - 2, 300-309.6. Kashtanov, Yuri. Stochastic Mesh Method for Optimal Stopping Problems. Monte Carlo Methods and Applications, 2017, 23 - 2, 121-130.
7. Григорьев Юрий Дмитриевич,Мелас Вячеслав Борисович, Шпилев Петр Валерьевич. Избыточность локальноD-оптимальных планов и гомотетии. Вестник СПбГУ. Математика. Механика.Астрономия, 2017, 4(62) - 4, 552-562.8. Yu. D. Grigoriev, V. B. Melas, P. V. Shpilev. Excess ofLocally D-optimal Designs and Homothetic Transformations . Вестник СПбГУ. Математика.Механика.Астрономия,2017, 50 - 4, 329–336.9. Petr E. Tovstik, Tatiana M. Tovstik, Natalia V.Naumova. Harmonic and random vibrations of an anisotropic beam. 2017, DOI:10.7712/120117.5437.17795.

основные результаты по этапу (подробно)

Основные результаты, полученные в рамках гранта за последние 3 года, распределены по 3 направлениям.1. Квази стохастические методы интегрирования. Показано, что для кратностей интеграла >=5 известное неравенство Коксмы-Хлавки – не залог правильного порядка убывания остатка при числе испытаний, которое может быть реализовано на современных компьютерах. Указаны методы оценки реального порядка асимптотики. Проведены численные эксперименты [4, 2019], [5, 2019].Полученные результаты подтверждены также при решении некоторых типов краевых задач [1, 2019 ].Изучены рандомизованные (scrambled) квазислучайные последовательности Холтона. Установлена их связь со случайными квадратурами с одним свободным узлом. Указан класс функций, для которых эти квадратуры точны и получено выражение их дисперсии [4, 2017].Полученные результаты позволяют дать четкие рекомендации относительно применения квазислучайных квадратур при вычислении интегралов и решении более сложных прикладных задач.2. Получен ряд новых результатов при решении задач глобальной оптимизации функций многих переменных. Наряду с использованием квазислучайных последовательностей на каждом этапе генетического алгоритма предложено использовать технику оценки матрицы ковариаций пробных векторов. Эта техника была впервые предложена руководителем проекта в 1976 году, показала надёжные результаты, но мало использовалась ввиду её большой трудоёмкости. В работе [8, 2019] доказана лемма, позволяющая уменьшить эту трудоёмкость на порядок. Полученные результаты легли в основу системы программ, позволивших решить несколько сложных задач планирования эксперимента [1, 2019], [2, 2019]. В процессе эксплуатации программы продемонстрировали высокую эффективность разработанных алгоритмов. 3.Как известно, большие системы дифференциальных уравнений возникают при решении широкого круга прикладных задач. Простейший пример – задачи массового обслуживания, описываемые марковскими цепями даже с бесконечным числом состояний. При использовании квазислучайной техники для решения подобных систем было отмечено, что полученные алгоритмы позволяют также решать стохастические дифференциальные уравнения. При этом в линейном случае смещение равно нулю (метод Эйлера даёт смещение порядка $\sqrt{\Delta t}$). Это интересный и важный результат ([3, 2019], [7, 2019]), требующий дальнейшего развития.
ПУБЛИКАЦИИ:1.Sipin, Alexander S., Zeifman, Alexander I. Numerical Experiments for SomeMarkov Models for Solving Boundary Value Problems. 2019, 493-500.2. Ермаков С.М., Семенчиков Д.Н. О методах оптимизации в задачах планированияэксперимента. Заводская лаборатория. Диагностика материалов, 2019, 85 - 1,72-77.
3. Ермаков, С. М., Товстик, Т. М. Метод Монте-Карло для решения систем ОДУ.Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия,2019, 6(64) - 3, 411-421.
4. Ermakov Sergej M., Leora Svetlana N. Decrease of the mean of thequasi-random integration error. Communications in StatisticsPart B: Simulation and Computation, 2019, 1-9.
5. Ermakov Sergey, Leora Svetlana. Monte Carlo Methods and the Koksma-HlawkaInequality. Mathematics, 2019, 7 - 8, 725.
6. S. M. Ermakov, T.M. Tovstik. Monte Carlo Method for Solving ODE Systems.Vestnik of the St. Petersburg University: Mathematics, 2019, 52 - 3, 272-280.
7. Ermakov Sergej M., Pogosian Anna A. On solving stochastic differentialequations. Monte Carlo Methods and Applications, 2019, 25 - 2, 155-161.
8. Ermakov Sergej M., Semenchikov Dmitriy N. Genetic global optimizationalgorithms. Communications in Statistics Part B: Simulation and Computation,2019, 1-10.
9. Grigoriev Yu. D., Melas V. B., Shpilev P. V. Excess and saturated D-optimaldesigns for the rational model. Statistical Papers, 2019.
10. Sipin Alexander. Monte Carlo Algorithms for the Parabolic Cauchy Problem.Mathematics, 2019, 7 - 2, 177.
11. Alexander S. Sipin. A RANDOMIZED QUASI-MONTE CARLO ALGORITHMS FOR SOMEBOUNDARY VALUE PROBLEMS. 2020.

основные результаты по этапу (кратко)

В процессе выполнения проекта получены новые результаты в следующих направлениях:
1.Указаны новые более точные методы анализа погрешности процедур интегрирования квази Монте-Карло. Установлены связи рандомизованных (serambled) методов квази Монте-Карло со случайными квадратурами с одним свободным узлом. Теория последних хорошо разработана. Эти результаты позволили дать важные, а иногда и исчерпывающие рекомендации по использованию квазислучайных последовательностей при решении больших прикладных задач.
2.Предложен новый вариант генетического алгоритма поиска глобального экстремума, использующий квазислучайные последовательности, метод имитации отжига и матриц ковариации. Метод строго обоснован. Составлены соответствующие программы, с помощью которых решены достаточно сложные задачи планирования регрессионных экспериментов.
3. В процессе исследований наметились новые подходы к решению систем обыкновенных и стохастических дифференциальных уравнений.
Результаты опубликованы в 10 статьях и докладывались на 3-х международных конференциях.
Заявленные в проекте задачи решены полностью.

описание вклада в работу каждого из участников, допустима оценка в процентах (учётная форма ЦИТиС)

Ермаков С.М. – 48% (научное руководство, доказательство основных теорем)
Каштанов Ю.Н – 6% (американские опционы)
Леора С.Н. – 6% (вычислительные эксперименты)
Мелас В.Б. – 8% (планирование эксперимента)
Рукавишникова А.И. – 1% (редактирование текстов на английском языке)
Семенчиков Д.Н. – 6% (вычислительные эксперименты)
Сипин А.С. – 6% (бессеточные методы)
Соловьева Н.Л. – 7% (техническое оформление и вычислит. эксперименты)
Товстик Т.М. – 2% (методы Монте Карло для ОДУ)
Шпилев В.П. – 10% (экстремальные задачи планирования эксперимента)

передача полной копии отчёта третьим лицам для некоммерческого использования: разрешается/не разрешается (учётная форма ЦИТиС)

разрешается

проверка отчёта на неправомерные заимствования во внешних источниках: разрешается/не разрешается (учётная форма ЦИТиС)

разрешается
Короткий заголовок__
АкронимRFBR_a_2017 - 3
СтатусЗавершено
Действительная дата начала/окончания18/03/1915/12/19

Ключевые слова

  • Методы Монте-Карло
  • Вычисление многократных интегралов
  • Глобальный экстремум
  • Расслоение
  • Планирование эксперимента
  • Имитация отжига