Биномиальная модель оценки опционов: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[ожидает проверки][ожидает проверки]
 
Строка 121: Строка 121:
  
 
Реализацию алгоритма можно найти здесь: [https://github.com/warm35/binomial/tree/master/NVIDIA_CUDA_SDK]
 
Реализацию алгоритма можно найти здесь: [https://github.com/warm35/binomial/tree/master/NVIDIA_CUDA_SDK]
 +
 +
[[Категория:Алгоритмы]]

Текущая версия на 16:00, 8 июля 2016

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Если быть точнее, биномиальная модель представляет эволюцию цены базового актива опциона как двоичное дерево всех возможных цен при равномерном разбиении временного отрезка с сегодняшнего дня, в предположении, что на каждом шаге цена может только расти, либо падать на фиксированное число с соответствующими вероятностями [math]p_u[/math] и [math]p_d[/math]. Другими словами, корнем дерева является сегодняшняя цена базового актива, каждый уровень представляет собой все возможные цены в данный момент времени. У каждого узла со значением [math]S[/math] есть два дочерних узла со значениями [math]Su[/math] и [math]Sd, u,d[/math] – множители движения цены вверх и вниз соответственно за один шаг по времени [math]dT[/math]. [math]u[/math] и [math]d[/math] зависят от волатильности [math]\sigma[/math] следующим образом:

[math]u = e^{\sigma\sqrt{dT}}, d = e^{-\sigma\sqrt{dT}}, ud = 1.[/math]

где [math]p_d = 1 - p_u[/math], [math]p_u[/math] ищется в предположении, что за [math]dT[/math] доходность базового актива в среднем такая же, как и при отсутствии риска, то есть если в момент времени [math]t[/math] стоимость базового актива [math]S[/math], то в момент времени [math]t + dT[/math] она будет равна [math]Se^{rdT}[/math], где [math]r[/math] - процентная ставка. В результате получается следующее уравнение:

[math]Se^{rdT} = (Su p_u + Sd p_d)[/math],

откуда [math]p_u = \frac{e^{rdT} - d}{u - d}.[/math]

С помощью такого представления можно получить цену в любом узле дерева. Для опциона "колл" она равна [math]V_{call} = max\{S - K, 0\}[/math], для "пут" [math]V_{put} = max\{K - S, 0\}[/math], где [math]K[/math] - страйк опциона. После расчета всех возможных цен опциона, начинается движение от листьев к корню по формуле

[math]V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT} (1)[/math],

где [math]V_t[/math] - цена опциона в некотором узле, [math]V_{u, t+1}[/math] и [math]V_{d, t+1}[/math] - цены опциона в дочерних узлах.

1.2 Математическое описание алгоритма

Для реализации алгоритма потребуются выполнять расчеты по следующим двум формулам:

(1) [math]V_{T_i} = max\{Se^{V_sdT * 2i - N} - K, 0\}[/math] - для расчета стоимости опциона в [math]i[/math]-м листе дерева;

(2) [math]V_t = (p_uV_{u, t+1} + p_dV_{d, t+1})e^{-rdT}[/math] - для расчета справедливой стоимости опциона.

1.3 Вычислительное ядро алгоритма

Вычислительным ядром алгоритма является вычисление справедливой стоимости опциона. Для этого действия потребуется [math]N(N-1)/2[/math] операций, где [math]N[/math] - число шагов по времени.

1.4 Макроструктура алгоритма

Алгоритм состоит из двух шагов:

1. Генерация цен опциона в листьях.

2. Вычисление справедливой стоимости опциона по формуле (1).

1.5 Схема реализации последовательного алгоритма

На вход: количество этапов [math]N[/math], страйк [math]K[/math], цена базового актива на [math]t_0[/math] [math]S[/math], волатильность базового актива [math]sigma[/math], шаг по времени [math]dT[/math], процентная ставка [math]r[/math].

1. Для i = 0,...,N:

1.1 price = S * exp(v * dT * (2 - i * N))

1.2 steps[i] = max(price - K, 0)

2. pu = (exp(r * dT) - exp(-sigma * sqrt(dT))) / (exp(sigma * sqrt(dT)) - exp(-sigma * sqrt(dT)))

3. pd = 1 - pu

4. Для i = N,...,1:

4.1 Для j = 0,..., i - 1:

4.1.1 steps[j] = pu * steps[j + 1] + pd * steps[j]

1.6 Последовательная сложность алгоритма

Алгоритм требует выполнения [math]4N + 4 + N^2 - N = N^2 + 3N + 4[/math] операций умножения, [math]N^2 + 2N + 3[/math] операций вычитания, [math]N + 4[/math] вычислений экспоненты, [math]N[/math] вычислений максимума и 3 операции вычисления квадратного корня. В итоге, последовательная суммарная сложность алгоритма составляет [math]2N^2 + 7N + 14[/math] элементарных операций.

1.7 Информационный граф алгоритма

Информационный граф алгоритма изображен на рисунке 1, где в узлах графа показаны выполняемые арифметические операции, а также функции [math]exp[/math] и [math]max[/math].

BOPM.png

1.8 Ресурс параллелизма алгоритма

Для вычисления значений справедливой стоимости опциона в листьях необходимо последовательно выполнить следующие ярусы:

1. Вычисление экспоненты;

2. Умножение экспоненты на стоимость базового актива в момент времени [math]t_0[/math].

При классификации по ширине ярусно-параллельной формы алгоритм имеет сложность [math]O(N)[/math]. При классификации по высоте ЯПФ - [math]O(N)[/math].

1.9 Входные и выходные данные алгоритма

Входные данные алгоритма, как было указано ранее, это количество этапов [math]N[/math], страйк [math]K[/math], цена базового актива на [math]t_0[/math] [math]S[/math], волатильность базового актива [math]\sigma[/math], шаг по времени [math]\Delta T[/math], процентная ставка [math]r[/math]. На выходе получается справедливая стоимость опциона [math]C[/math].

1.10 Свойства алгоритма

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

2 Программная реализация алгоритма

2.1 Особенности последовательной реализации алгоритма

Код последовательной реализации на языке C может выглядеть так:

#include <stdlib.h>
#include <float.h>
#include <math.h>

double price(int N, double K, double S, double vol, double dT, double r) {
   double *steps = malloc(sizeof(double) * (N + 1));
   for(int i = 0; i <= N; i++) { 
       double price = S * expf(vol * dT * (2. * i - N)); 
       steps[i] = fmaxf(price - K, .0); 
   }

   double pu = (expf(r * dT) - expf(-vol * sqrt(dT))) / (expf(vol * sqrt(dT)) - expf(-vol * sqrt(dT))), pd = 1 - pu;

   for(int i = N; i > 0; i--)
       for(int j = 0; j <= i - 1; j++) 
           steps[j] = pu * steps[j + 1] + pd * steps[j]; 

   double C = steps[0];

   free(steps);
   steps = 0x0;

   return C;
}

2.2 Локальность данных и вычислений

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

2.3 Возможные способы и особенности реализации параллельного алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

При большом количестве периодов, возможна реализация на GPU.

2.7 Существующие реализации

Существует множество реализаций этой модели. Одно из них представлено в качестве примера для NVIDIA CUDA SDK. Оно используется здесь для исследований.

Реализацию алгоритма можно найти здесь: [1]