Нижегородский государственный университет им.Н.И.Лобачевского.

ЛАБОРАТОРИЯ ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

Факультет вычислительной математики и кибернетики

Лаборатория ITLabИсследованияПроекты 2011 г. Switch to English version  
Новости
О Лаборатории
Обучение
Исследования
Проекты 2011 г.
Проекты 2010 г.
Проекты 2003-2009 гг.
Образовательные комплексы
Семинар Лаборатории
Мероприятия
Вакансии Интел
Сотрудничество
Разработчики сайта
О нас пишут
Летняя школа 2011
Видео лекции
Клуб У.М.Н.И.К.
Имя:
Пароль:
запомнить:
Забыли пароль? Регистрация

Проекты 2011 г.

Финансовая математика

Подробная информация о проекте доступна по адресу: http://itlab.unn.ru/?doc=1058.

Проект развивается в лаборатории с 2005 года при поддержке компании Интел. За 5 лет существования проекта (2005-2010) были получены следующие основные результаты: http://itlab.unn.ru/?doc=1058

Работы, выполненные в 2011 году

I. В 2011 году предложен новый подход к оценке трудоемкости разработки программ с использованием разных технологий для параллельного программирования (Русаков А.В., руководитель – Мееров И.Б.).

Краткое описание

В настоящее время наблюдается неуклонный рост производительности вычислительной техники, что открывает все новые возможности по решению ресурсоемких задач, имеющих большое практическое значение. Такие задачи можно встретить в физике, химии, биологии, экономике, финансах и т.д. При этом одно из основных направлений развития состоит в частичном дублировании устройств, интегрированных на кристалле центрального процессора. На данный момент многоядерные системы прошли путь от исследовательских образцов до настольных компьютеров, что делает возможным их всестороннее использование. Наличие и распространение таких вычислительных систем потребовало новых технологий, моделей, методов и программных средств системного уровня, ориентированных на их эффективное использование. Так, в научной периодике наблюдается неуклонный рост числа публикаций, связанных с новыми технологиями для параллельного программирования. Разрабатываются новые подходы (OpenMP, MPI), фреймворки (OpenCL, CUDA), библиотеки (TBB, ArBB, CCR), языки (Cilk, Erlang, APL, Sisal) параллельного программирования. Одна из основных решаемых проблем заключается в сравнительной сложности разработки параллельных программ с нуля. Переход от обычного последовательного кода к параллельному требует некоторых навыков системного программирования, не всегда присутствующих у прикладных программистов – ключевых потребителей новых технологий параллельных вычислений. Таким образом, на первый план выходят два вопроса: производительность получаемых параллельных программ и трудоемкость их разработки.

Очевидно, параллельные программы, созданные с применением высокоуровневых надстроек, в большинстве своем не могут опередить по производительности код, написанный с использованием низкоуровневых средств параллелизма. Однако в области прикладного программирования часто оправданна попытка пожертвовать незначительной долей производительности ради удобства разработки.

На сегодняшний день существует множество публикаций, в которых дается сравнение производительности программ с использованием различных технологий параллельного программирования, однако вопрос о времени обучения и трудоемкости разработки программ с их использованием является мало изученным. Одними из немногих примеров могут послужить попытки сравнить различные технологии параллельного программирования, применимо к учебным курсам в Калифорнийском Университете (UCSB) и признанном во всем мире центре разработок по программной инженерии – Высшей Технической Школе Цюриха (ETH).

В работе предлагается набор метрик и методика их сбора для определения трудоемкости разработки программ. Разработанный подход применяется автором к одной из прикладных задач для выбранного набора технологий параллельного программирования на системах с общей памятью.

Сравнение выбранных технологий параллельного программирования производится на примере задачи финансовой математики. Финансовая математика – раздел прикладной математики, связанный с финансовыми расчетами. Основу задач данной области составляют вычисления стоимостей производных ценных бумаг (опционов, акций, облигаций и других). Модель финансового рынка в данных задачах описывается с использованием систем стохастических дифференциальных уравнений, а алгоритмы решения обычно задействуют Монте-Карло моделирование, методы оптимизации и численное интегрирование. Исходя из этого, данные задачи относятся к классу высокопроизводительных вычислений, однако имеют ясное прикладное значение и конкретный экономический смысл. В качестве тестовой задачи в работе используется одна из распространенных задач финансовой математики – нахождение справедливой цены опциона Бермудского типа. Для решения этой задачи был реализован основанный на методе Монте-Карло оптимизированный нерекурсивный алгоритм имитационных деревьев Broadie–Glasserman Random Trees. Реализация данного алгоритма является распространенным бенчмарком среди финансовых прикладных задач и хорошо изучена автором данной работы.

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

Основные результаты:

1. В работе предлагается методика анализа трудоемкости разработки параллельных программ. Указанная методика включает систему метрик для проведения анализа, выбор ролевых групп участников процесса, подробные инструкции, регламентирующие процесс анализа, и вспомогательные материалы (шаблоны заполняемых документов в формате Microsoft Excel).

2. В работе проведен сравнительный анализ некоторых широко распространенных технологий и библиотек для параллельного программирования в системах с общей памятью, включая гетерогенные системы с использованием графических процессоров. Анализ проводился на основе решения тестовой задачи – определения справедливой цены опционов Бермудского типа методом имитационных деревьев (Broadie-Glasserman Random Trees). Для сравнения были выбраны следующие технологии и библиотеки: OpenMP, Intel TBB, OpenCL, Cilk Plus. Сравнительный анализ включал измерение производительности программного обеспечения, созданного с использованием указанных технологий и библиотек, а также количественный анализ трудоемкости разработки с использованием предложенной системы метрик.

Анализ производительности

 

Анализ трудоемкости разработки – некоторые диаграммы

3. В рамках работы автором была проведена апробация предлагаемого подхода на студентах магистратуры факультета ВМК в рамках спецкурса «Параллельные численные методы». Класс задач – параллельные алгоритмы классических разделов численных методов. В начале семестра студентам были розданы подробные инструкции по сбору количественных метрик. В конце семестра были собраны результаты и проведен их анализ. Результаты анализа приведены в работе. В целом наблюдаемая тенденция – усложнение работы в случае использования технологий программирования для графических процессоров по сравнению с аналогичными технологиями для центральных процессоров.

По результатам работы защищена магистерская диссертация. Работа была отмечена на заседании ГАК как одна из лучших дипломных работ на факультете и рекомендована для продолжения в аспирантуре.

Приложения:

II. В 2011 году разработана (Мееров И.Б., Сысоев А.В.) новая лабораторная работа по  численному интегрированию стохастических дифференциальных уравнений для курса "Параллельные численные методы". Рассмотрена прикладная задача – моделирование финансового рынка.

III. В 2011 году выполнены работы по исследованию моделей управления портфелем инвестора (Никонов А.С., руководитель – Мееров И.Б.).

Краткое описание:

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

Одношаговая модель управления портфелем инвестора базируется на модели Марковица, имеющей ряд недостатков. В частности, в литературе отмечается ее нестабильность, вызванная большими отклонениями результатов расчетов при небольших изменениях входных параметров. Основываясь на модели Марковица, Ф. Блэк и Р. Литтерман в 90-х годах ХХ века разработали новую модель, учитывающую гипотезу рыночной эффективности и модель CAPM, которая позволяет описать взаимосвязь между риском и ожидаемой доходностью актива. Основным плюсом модели Блэка-Литтермана является возможность учета экспертных оценок. Ведущими финансовыми учреждениями модель признается важным инструментом в процессе управления портфелем инвестора. Вместе с тем, некоторые исследователи, в частности, П. Дуст (P. Doust), указывают на определенные недостатки оригинальной модели и предлагают методы ее улучшения. В настоящей работе, с помощью выполненной автором программной реализации, проводится анализ модели и ее применимости.

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

Для решения этой проблемы строится модель многошаговой задачи управления портфелем инвестора, производится ее тестирование на реальных данных и сравнение с одношаговым подходом.

Основные результаты:

1. Разработанное программное обеспечение решает задачу квадратичного программирования для определения оптимального портфеля на основе имеющейся исторической информации и экспертных оценок о дальнейшем поведении рынка.

2. По результатам экспериментов на различных исходных данных воспроизведены недостатки модели Блэка-Литтермана, а также методы их преодоления, упоминающиеся ранее в англоязычной литературе.

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

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

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

IV. Выполнены работы по теме «Нахождение оптимального портфеля инструментов» (Удалова Т., руководитель – Мееров И.Б.)

Краткое описание:

В данной работе рассмотрены два популярных показателя расчета возможных потерь – VaR и CVaR, описаны алгоритмы вычисления этих величин, а также плюсы и минусы данных подходов к вычислению рисковой стоимости актива. Разработано исследовательское приложение, которое позволяет анализировать состав портфеля и его рисковые показатели при заданной модели рынка.

Основные результаты:

Не все методы, применяемые на стабильном рынке, годятся в условиях кризиса, однако можно и нужно применять адекватные количественные методы для оценки рисков в этот период. Большую помощь менеджерам в этом окажет владение навыками риск-менеджмента и консалтинговая поддержка в планировании непрерывности бизнеса и оценке рисков такими методами, как стресс-тестирование, прогнозирование кризисов, условный VaR, теория экстремальных значений и теория хаоса, теория глобального риск-фактора.

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

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

Программное обеспечение разработано на языке С++ в среде Microsoft Visual Studio с использованием пакета инструментов Intel Parallel Studio (компилятор Intel C++, генераторы псевдослучайных чисел из библиотеки Intel MKL) и решателя GLPK (реализация симплекс-метода). Программное приложение позволяет решать задачи размерности ~15000 за время ~3с.

V. Выполнены работы по теме «Реализация алгоритма Лонгстаффа - Шварца для определения цены опциона бермудского типа» (Малова А., руководитель – Мееров И.Б.)

Краткое описание:

В работе рассматривается задача вычисления справедливых цен опционов американского типа, широко распространенных на фондовых биржах. Данная задача существенно сложнее ее аналога для случая опционов европейского типа, где решение может быть либо найдено по аналитической формуле Блэка-Шоулса, либо построено в результате несложных расчетов по методу Монте-Карло. В случае американского опциона приходится учитывать в модели возможность исполнения опциона в произвольный момент времени до истечения срока действия, что существенно усложняет модель и ее анализ. В настоящее время большинство работ сводит задачу к оцениванию дискретного аналога опциона американского типа – опциона бермудского типа, который может быть предъявлен к исполнению в любой из конечного количества зафиксированных в контракте моментов времени. Решению этой задачи посвящена данная работа.

Решение такой задачи также сопряжено с разными трудностями. В частности, получение точечной оценки цены является затруднительным, в связи с чем активно развивается подход, состоящий в приближении к «точному решению» путем вычисления оценок сверху и снизу с последующим построением доверительного интервала для цены опциона. На протяжении последних нескольких лет в лаборатории ITLab в рамках дипломных работ студентов рассматриваются вопросы эффективной программной реализации алгоритмов, реализующих указанный выше подход. При этом исследуются свойства алгоритмов, особенности их применения для решения задач большой размерности, вопросы их численной устойчивости и т.д. Были рассмотрены алгоритм случайных деревьев (Broadie–Glasserman Random Trees) и алгоритм стохастических сетей (Broadie–Glasserman Stochastic Mesh). В данной работе рассматривается  алгоритм Лонгстаффа–Шварца, существенно отличающийся от упомянутых ранее, и некоторые его модификации, в частности, для использования в многомерном случае.

Основные результаты:

1. Проведен анализ методов определения справедливых цен опционов бермудского типа. Анализ литературы показал, что все подходы к решению поставленной задачи можно разделить на два класса – детерминированные и стохастические. К детерминированным подходам относятся сеточные и конечно-разностные методы, к стохастическим – метод Монте-Карло. Часто исходная задача сводится к решению сформулированной некоторым образом задаче оптимизации. Для более точного определения цены Американского опциона метод Монте-Карло комбинируется с методами динамического и линейного программирования, регрессионными оценками. Последний подход и был использован в данной работе.

2. Выполнена программная реализация алгоритма Лонгстаффа–Шварца для определения нижней оценки цены опциона в соответствии с описанием, опубликованным в открытой печати. Проведены вычислительные эксперименты, решены тестовые задачи. Результаты сопоставимы с результатами авторов алгоритма.

3. Выполнена реализация алгоритма Андерсена–Броди для построения верхней оценки на основе полученной методом Лонгстаффа–Шварца оптимальной и псевдооптимальной политики исполнения опциона. Результаты сопоставимы с результатами, полученными на основе применения других алгоритмов, разработанных ранее на кафедре.

4. Построена модификация метода для применения в многомерном случае, выполнена ее программная реализация. Проведены вычислительные эксперименты, решены тестовые задачи. Результаты экспериментов показывают, что доверительный интервал включает точное решение, но несколько смещен. Устранение смещения – направление дальнейшей работы.

По результатам защищена бакалаврская работа. Работа отмечена ГАК по специальности «Прикладная математика и информатика», рекомендована в публикации, отмечено качества выполненного обзора литературы.

VI. В 2011 году коллектив пополнился двумя студентками – Пашко А., Фетюкова А.

Коллектив

  • Мееров И.Б., к.т.н., доц. - руководитель проекта
  • Козинов Е.А., аспирант
  • Русаков А.В.
  • Никонов А.С.
  • Малова А.
  • Удалова Т.
  • Пашко А.
  • Фетюкова А.

<< вернуться  |   Документ от: 24.01.2012 16:06

Новости

14.11.2015
16.10.2015
16.10.2015
14.10.2015
20.09.2015

© ITLab, Нижний Новгород,  2009