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

Не путать с Теорема о необязательной остановке.

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

Определение

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

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

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

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

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

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

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

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

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

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

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

${displaystyle V(x)=sup _{0leq au leq T}mathbb {E} _{x}left(M(X_{ au })+int _{0}^{ au }L(X_{t})dt+sup _{0leq tleq au }K(X_{t})ight).}$

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

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

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

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

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

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

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

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

${displaystyle au _{mathcal {S}}=inf{t>0:Y_{t}otin {mathcal {S}}}}$

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

${displaystyle V(y)=sup _{ au leq au _{mathcal {S}}}J^{ au }(y)=sup _{ au leq au _{mathcal {S}}}mathbb {E} _{y}left[M(Y_{ au })+int _{0}^{ au }L(Y_{t})dtight].}$

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

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

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

тогда ${displaystyle phi (y)geq V(y)}$ для всех ${displaystyle yin {ar {mathcal {S}}}}$. Более того, если

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

потом ${displaystyle phi (y)=V(y)}$ для всех ${displaystyle yin {ar {mathcal {S}}}}$ и ${displaystyle au ^{*}=inf{t>0:Y_{t}otin D}}$ оптимальное время остановки.

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

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

Примеры

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

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

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

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

${displaystyle { ext{Bern}}left({frac {1}{2}}ight),}$

и если

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

тогда последовательности ${displaystyle (X_{i})_{igeq 1}}$, и ${displaystyle (y_{i})_{igeq 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})}$ конечная последовательность)

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

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

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

Основная статья: Теория поиска

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

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

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

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

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

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

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

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

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

где функция выигрыша ${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)ight}=0}$

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

• (Бессрочный звонок) ${displaystyle V(x)={egin{cases}(b-K)(x/b)^{gamma }&xin (0,b)x-K&xin [b,infty )end{cases}}}$ куда ${displaystyle gamma =({sqrt {u ^{2}+2r}}-u )/sigma }$ и ${displaystyle u =(r-delta )/sigma -sigma /2,quad b=gamma K/(gamma -1).}$
• (Бессрочный пут) ${displaystyle V(x)={egin{cases}K-x&xin (0,c](K-c)(x/c)^{ ilde {gamma }}&xin (c,infty )end{cases}}}$ куда ${displaystyle { ilde {gamma }}=-({sqrt {u ^{2}+2r}}+u )/sigma }$ и ${displaystyle u =(r-delta )/sigma -sigma /2,quad c={ ilde {gamma }}K/({ ilde {gamma }}-1).}$

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

Смотрите также

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

Рекомендации

1. Чоу, Ю.С.; Роббинс, Х.; Зигмунд, Д. (1971). Большие надежды: теория оптимальной остановки. Бостон: Houghton Mifflin.
2. Фергюсон, Томас С. (2007). Оптимальная остановка и приложения. UCLA.
3. Хилл, Теодор П. (2009). «Зная, когда остановиться». Американский ученый. 97: 126–133. Дои:10.1511/2009.77.126. ISSN  1545-2786 - via (Французский перевод см. история на обложке в июльском номере Pour la Science (2009)).
4. Пескир, Горан; Ширяев Альберт (2006). «Оптимальная остановка и задачи со свободной границей». Лекции по математике. ETH Zürich. Дои:10.1007/978-3-7643-7390-0. ISBN  978-3-7643-2419-3.
5. Эксендаль, Б.; Сулем, А. С. (2007). «Прикладное стохастическое управление скачкообразными диффузиями». Дои:10.1007/978-3-540-69826-5. ISBN  978-3-540-69825-8.
6. MacQueen, J .; Миллер-младший, Р. (1960). «Оптимальные политики настойчивости». Исследование операций. 8 (3): 362–380. Дои:10.1287 / opre.8.3.362. ISSN  0030-364X.
7. Каратзас, Иоаннис; Шрив, Стивен Э. (1998). «Методы математических финансов». Стохастическое моделирование и прикладная вероятность. 39. Дои:10.1007 / b98840. ISBN  978-0-387-94839-3.

• Томас С. Фергюсон, Оптимальная остановка и приложения, получено 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.