Оптимальная остановка

В математике теория оптимальной остановки ^{[ 1 ]}^{[ 2 ]} или ранняя остановка ^{[ 3 ]} занимается проблемой выбора времени для совершения определенного действия, чтобы максимизировать ожидаемое вознаграждение или минимизировать ожидаемые затраты. Задачи оптимальной остановки можно найти в областях статистики , экономики и математических финансов (связанных с ценообразованием американских опционов ). Ключевым примером задачи оптимальной остановки является задача секретаря . Задачи оптимальной остановки часто можно записать в форме уравнения Беллмана и поэтому часто решают с помощью динамического программирования .

Определение

Случай дискретного времени

Проблемы с правилом остановки связаны с двумя объектами:

Последовательность случайных величин $X_{1},X_{2},\ldots$ , совместное распределение которых предполагается известным
Последовательность функций «награды» $(y_{i})_{i\geq 1}$ которые зависят от наблюдаемых значений случайных величин в 1:
$y_{i}=y_{i}(x_{1},\ldots ,x_{i})$

Учитывая эти объекты, проблема заключается в следующем:

Вы наблюдаете за последовательностью случайных величин, и на каждом шаге $i$ , вы можете либо прекратить наблюдение, либо продолжить
Если вы перестанете наблюдать на шаге $i$ , вы получите награду $y_{i}$
Вы хотите выбрать правило остановки , чтобы максимизировать ожидаемое вознаграждение (или, что то же самое, минимизировать ожидаемый убыток).

Случай непрерывного времени

Рассмотрим процесс получения $G=(G_{t})_{t\geq 0}$ определенный в отфильтрованном вероятностном пространстве $(\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )$ и предположим, что $G$ адаптирован к фильтрации. Задача оптимальной остановки состоит в нахождении времени остановки. $\tau ^{*}$ который максимизирует ожидаемый выигрыш

V_{t}^{T}=\mathbb {E} G_{\tau ^{*}}=\sup _{t\leq \tau \leq T}\mathbb {E} G_{\tau }

где $V_{t}^{T}$ называется функцией ценности . Здесь $T$ может иметь значение $\infty$ .

Более конкретная формулировка выглядит следующим образом. Мы рассматриваем адаптированный сильный марковский процесс $X=(X_{t})_{t\geq 0}$ определенный в отфильтрованном вероятностном пространстве $(\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} _{x})$ где $\mathbb {P} _{x}$ обозначает вероятностную меру, при которой случайный процесс начинается в точке $x$ . Учитывая непрерывные функции $M,L$ , и $K$ , задача оптимальной остановки

V(x)=\sup _{0\leq \tau \leq T}\mathbb {E} _{x}\left(M(X_{\tau })+\int _{0}^{\tau }L(X_{t})dt+\sup _{0\leq t\leq \tau }K(X_{t})\right).

Иногда ее называют формулировкой MLS (что означает Майер, Лагранж и супремум соответственно). ^{[ 4 ]}

Методы решения

Обычно существует два подхода к решению задач оптимальной остановки. ^{[ 4 ]} Когда основной процесс (или процесс выигрыша) описывается его безусловными конечномерными распределениями , подходящим методом решения является подход мартингала, названный так потому, что он использует теорию мартингала , наиболее важной концепцией которого является конверт Снеллиуса . В случае дискретного времени, если горизонт планирования $T$ конечна, проблема также может быть легко решена с помощью динамического программирования .

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

Результат скачкообразной диффузии

Позволять $Y_{t}$ быть диффузией Леви в $\mathbb {R} ^{k}$ предоставлено SDE

dY_{t}=b(Y_{t})dt+\sigma (Y_{t})dB_{t}+\int _{\mathbb {R} ^{k}}\gamma (Y_{t-},z){\bar {N}}(dt,dz),\quad Y_{0}=y

где $B$ это $m$ -мерное броуновское движение , ${\bar {N}}$ это $l$ -мерная компенсированная случайная мера Пуассона , $b:\mathbb {R} ^{k}\to \mathbb {R} ^{k}$ , $\sigma :\mathbb {R} ^{k}\to \mathbb {R} ^{k\times m}$ , и $\gamma :\mathbb {R} ^{k}\times \mathbb {R} ^{k}\to \mathbb {R} ^{k\times l}$ заданы функции такие, что единственное решение $(Y_{t})$ существует. Позволять ${\mathcal {S}}\subset \mathbb {R} ^{k}$ быть открытым множеством (область платежеспособности) и

\tau _{\mathcal {S}}=\inf\{t>0:Y_{t}\notin {\mathcal {S}}\}

быть время банкротства. Оптимальная задача остановки:

V(y)=\sup _{\tau \leq \tau _{\mathcal {S}}}J^{\tau }(y)=\sup _{\tau \leq \tau _{\mathcal {S}}}\mathbb {E} _{y}\left[M(Y_{\tau })+\int _{0}^{\tau }L(Y_{t})dt\right].

Оказывается, при некоторых условиях регулярности ^{[ 5 ]} имеет место следующая проверочная теорема:

Если функция $\phi :{\bar {\mathcal {S}}}\to \mathbb {R}$ удовлетворяет

$\phi \in C({\bar {\mathcal {S}}})\cap C^{1}({\mathcal {S}})\cap C^{2}({\mathcal {S}}\setminus \partial D)$ где находится область продолжения $D=\{y\in {\mathcal {S}}:\phi (y)>M(y)\}$ ,
$\phi \geq M$ на ${\mathcal {S}}$ , и
${\mathcal {A}}\phi +L\leq 0$ на ${\mathcal {S}}\setminus \partial D$ , где ${\mathcal {A}}$ является генератором бесконечно малым $(Y_{t})$

затем $\phi (y)\geq V(y)$ для всех $y\in {\bar {\mathcal {S}}}$ . Более того, если

${\mathcal {A}}\phi +L=0$ на $D$

Затем $\phi (y)=V(y)$ для всех $y\in {\bar {\mathcal {S}}}$ и $\tau ^{*}=\inf\{t>0:Y_{t}\notin D\}$ – оптимальное время остановки.

Эти условия можно записать и в более компактной форме ( интегро-вариационное неравенство ):

$\max \left\{{\mathcal {A}}\phi +L,M-\phi \right\}=0$ на ${\mathcal {S}}\setminus \partial D.$

Примеры

Подбрасывание монет

(Пример, где $\mathbb {E} (y_{i})$ сходится)

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

Вы хотите максимизировать сумму, которую вам платят, выбрав правило остановки. Если X _i (при i ≥ 1) образует последовательность независимых одинаково распределенных случайных величин с распределением Бернулли

{\text{Bern}}\left({\frac {1}{2}}\right),

и если

y_{i}={\frac {1}{i}}\sum _{k=1}^{i}X_{k}

тогда последовательности $(X_{i})_{i\geq 1}$ , и $(y_{i})_{i\geq 1}$ являются объектами, связанными с этой проблемой.

Продажа дома

(Пример, где $\mathbb {E} (y_{i})$ не обязательно сходится)

У вас есть дом и вы хотите его продать. Каждый день вам предлагают $X_{n}$ за свой дом и заплати $k$ продолжать рекламировать его. Если вы продадите свой дом в день $n$ , ты заработаешь $y_{n}$ , где $y_{n}=(X_{n}-nk)$ .

Вы хотите максимизировать заработанную сумму, выбрав правило остановки.

В этом примере последовательность ( $X_{i}$ ) — это последовательность предложений для вашего дома, а последовательность функций вознаграждения — это то, сколько вы заработаете. ^{[ 6 ]}

Проблема с секретарем

(Пример, где $(X_{i})$ является конечной последовательностью)

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

Вот, если $R_{1},\ldots ,R_{n}$ ( n — некоторое большое число) — ранги объектов, а $y_{i}$ это шанс, что вы выберете лучший объект, если перестанете намеренно отвергать объекты на шаге i, а затем $(R_{i})$ и $(y_{i})$ являются последовательностями, связанными с этой проблемой. Эту проблему решили в начале 1960-х годов несколько человек. Элегантное решение проблемы секретаря и несколько модификаций этой проблемы обеспечивает более поздний алгоритм оптимальной остановки (алгоритм Брюсса).

Теория поиска

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

Проблема с парковкой

Особым примером применения теории поиска является задача оптимального выбора парковочного места водителем, направляющимся в оперу (театр, магазин и т.п.). Подъезжая к месту назначения, водитель идет по улице, вдоль которой есть парковочные места – обычно на парковке только некоторые места свободны. Цель хорошо видна, поэтому легко оценить расстояние до цели. Задача водителя – выбрать свободное парковочное место как можно ближе к пункту назначения, не оборачиваясь, чтобы расстояние от этого места до пункта назначения было кратчайшим. ^{[ 7 ]}

Опционная торговля

При торговле опционами на финансовых рынках держателю американского опциона разрешается реализовать право купить (или продать) базовый актив по заранее установленной цене в любое время до или в дату истечения срока действия. Таким образом, оценка американских опционов, по сути, представляет собой задачу оптимальной остановки. Рассмотрим классическую Блэка–Шоулза и пусть схему $r$ быть безрисковой процентной ставкой и $\delta$ и $\sigma$ быть ставкой дивидендов и волатильностью акций. Цена акции $S$ следует геометрическому броуновскому движению

S_{t}=S_{0}\exp \left\{\left(r-\delta -{\frac {\sigma ^{2}}{2}}\right)t+\sigma B_{t}\right\}

в рамках риск-нейтральной меры.

Когда опцион бессрочный, задача оптимальной остановки имеет вид

V(x)=\sup _{\tau }\mathbb {E} _{x}\left[e^{-r\tau }g(S_{\tau })\right]

где функция выигрыша $g(x)=(x-K)^{+}$ для опциона колл и $g(x)=(K-x)^{+}$ для опциона пут. Вариационное неравенство

\max \left\{{\frac {1}{2}}\sigma ^{2}x^{2}V''(x)+(r-\delta )xV'(x)-rV(x),g(x)-V(x)\right\}=0

для всех $x\in (0,\infty )\setminus \{b\}$ где $b$ является границей упражнения. Известно, что решение ^{[ 8 ]}

(Вечный звонок) $V(x)={\begin{cases}(b-K)(x/b)^{\gamma }&x\in (0,b)\\x-K&x\in [b,\infty )\end{cases}}$ где $\gamma =({\sqrt {\nu ^{2}+2r}}-\nu )/\sigma$ и $\nu =(r-\delta )/\sigma -\sigma /2,\quad b=\gamma K/(\gamma -1).$
(вечный пут) $V(x)={\begin{cases}K-x&x\in (0,c]\\(K-c)(x/c)^{\tilde {\gamma }}&x\in (c,\infty )\end{cases}}$ где ${\tilde {\gamma }}=-({\sqrt {\nu ^{2}+2r}}+\nu )/\sigma$ и $\nu =(r-\delta )/\sigma -\sigma /2,\quad c={\tilde {\gamma }}K/({\tilde {\gamma }}-1).$

С другой стороны, когда срок годности конечен, проблема связана с двумерной задачей со свободной границей без известного решения в замкнутой форме. Однако можно использовать различные численные методы. См . здесь модель Блэка-Шоулза#Американские опционы для различных методов оценки, а также метод Fugit для дискретного древовидного расчета оптимального времени для исполнения.

См. также

Ссылки

Цитаты

^ Чоу, Ю.С.; Роббинс, Х .; Зигмунд, Д. (1971). Большие надежды: теория оптимальной остановки . Бостон: Хоутон Миффлин .
^ Фергюсон, Томас С. (2007). Оптимальная остановка и приложения . Калифорнийский университет в Лос-Анджелесе.
^ Хилл, Теодор П. (2009). «Знать, когда остановиться». Американский учёный . 97 (2): 126–133. дои : 10.1511/2009.77.126 . ISSN 1545-2786 . S2CID 124798270 .
(Перевод на французский язык см. на обложке июльского номера журнала Pour la Science (2009).)
^ Jump up to: ^а ^б Пескир, Горан; Ширяев, Альберт (2006). Оптимальная остановка и задачи со свободной границей . Лекции по математике. ETH Цюрих. дои : 10.1007/978-3-7643-7390-0 . ISBN 978-3-7643-2419-3 .
^ Оксендалл, Б. ; Сулем, А. (2007). Прикладное стохастическое управление скачкообразными диффузиями . дои : 10.1007/978-3-540-69826-5 . ISBN 978-3-540-69825-8 . S2CID 123531718 .
^ Фергюсон, Томас С .; Класс, Майкл Дж. (2010). «Поиски дома без вторых мгновений». Последовательный анализ . 29 (3): 236–244. дои : 10.1080/07474946.2010.487423 . ISSN 0747-4946 .
^ Маккуин, Дж.; Миллер-младший, Р.Г. (1960). «Оптимальная политика сохранения». Исследование операций . 8 (3): 362–380. дои : 10.1287/opre.8.3.362 . ISSN 0030-364X .
^ Карацас, Иоаннис; Шрив, Стивен Э. (1998). Методы математических финансов . Стохастическое моделирование и прикладная теория вероятности. Том. 39. дои : 10.1007/b98840 . ISBN 978-0-387-94839-3 .

Источники

Томас С. Фергюсон , « Кто решил проблему секретаря? » Статистическая наука , Vol. 4., 282–296, (1989)
Ф. Томас Брусс . «Суммируйте шансы к одному и остановитесь». Анналы вероятности , Том. 28, 1384–1391, (2000)
Ф. Томас Брусс. «Искусство правильного решения: почему лица, принимающие решения, хотят знать алгоритм шансов». Информационный бюллетень Европейского математического общества , выпуск 62, 14–20, (2006)
Роджерсон, Р.; Шимер, Р.; Райт, Р. (2005). «Поисковые модели рынка труда: обзор» (PDF) . Журнал экономической литературы . 43 (4): 959–88. дои : 10.1257/002205105775362014 . JSTOR 4129380 .

[ChowRobSig1971-1] Чоу, Ю.С.; Роббинс, Х .; Зигмунд, Д. (1971). Большие надежды: теория оптимальной остановки . Бостон: Хоутон Миффлин .

[Ferguson2007-2] Фергюсон, Томас С. (2007). Оптимальная остановка и приложения . Калифорнийский университет в Лос-Анджелесе.

[Hill2009-3] Хилл, Теодор П. (2009). «Знать, когда остановиться». Американский учёный . 97 (2): 126–133. дои : 10.1511/2009.77.126 . ISSN 1545-2786 . S2CID 124798270 .
(Перевод на французский язык см. на обложке июльского номера журнала Pour la Science (2009).)

[opt2006-4] Jump up to: ^а ^б Пескир, Горан; Ширяев, Альберт (2006). Оптимальная остановка и задачи со свободной границей . Лекции по математике. ETH Цюрих. дои : 10.1007/978-3-7643-7390-0 . ISBN 978-3-7643-2419-3 .

[oksendal2007-5] Оксендалл, Б. ; Сулем, А. (2007). Прикладное стохастическое управление скачкообразными диффузиями . дои : 10.1007/978-3-540-69826-5 . ISBN 978-3-540-69825-8 . S2CID 123531718 .

[FerKla2010-6] Фергюсон, Томас С .; Класс, Майкл Дж. (2010). «Поиски дома без вторых мгновений». Последовательный анализ . 29 (3): 236–244. дои : 10.1080/07474946.2010.487423 . ISSN 0747-4946 .

[MacQueenMiller1960-7] Маккуин, Дж.; Миллер-младший, Р.Г. (1960). «Оптимальная политика сохранения». Исследование операций . 8 (3): 362–380. дои : 10.1287/opre.8.3.362 . ISSN 0030-364X .

[karatzas1998-8] Карацас, Иоаннис; Шрив, Стивен Э. (1998). Методы математических финансов . Стохастическое моделирование и прикладная теория вероятности. Том. 39. дои : 10.1007/b98840 . ISBN 978-0-387-94839-3 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]