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

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

Определение [ править ]

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

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

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

   ${\ displaystyle y_ {i} = y_ {i} (x_ {1}, \ ldots, x_ {i})}$

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

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

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

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

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

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

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

${\displaystyle 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 (что означает Mayer, Lagrange и supremum, соответственно). ^[4]

Способы решения [ править ]

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

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

Результат диффузии скачка [ править ]

Пусть - диффузия Леви, заданная СДУ${\displaystyle Y_{t}}$${\displaystyle \mathbb {R} ^{k}}$

${\displaystyle 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}$

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

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

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

${\displaystyle 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] справедлива следующая теорема проверки:

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

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

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

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

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

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

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

Примеры [ править ]

Подбрасывание монет [ править ]

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

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

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

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

и если

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

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

Продажа дома [ править ]

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

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

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

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

Проблема с секретарем [ править ]

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

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

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

Теория поиска [ править ]

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

Проблема с парковкой [ править ]

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

Торговля опционами [ править ]

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

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

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

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

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

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

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

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

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

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

См. Также [ править ]

• Проблема с остановкой
• Марковский процесс принятия решений
• Теорема о необязательной остановке
• Стохастический контроль

Ссылки [ править ]

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