Оптимальна зупинка

У математиці теорія оптимальної зупинки або ранньої зупинки пов'язана з задачею вибору часу для здійснення певної дії, щоб максимізувати очікувану винагороду або мінімізувати очікувані витрати. Проблеми оптимальної зупинки можна знайти в областях статистики, економіки та фінансової математики (які пов'язані із ціноутворенням американських опціонів). Ключовим прикладом задачі оптимальної зупинки є задача про перебірливу наречену (в англомовній літературі зустрічається також під назвою задача про секретаря). Проблеми оптимальної зупинки часто можна записати у формі рівняння Беллмана, і тому їх часто розв'язують за допомогою динамічного програмування.

Визначення

Випадок безперервного часу

Задачі з правилом зупинки пов'язані з двома об'єктами:

1. Послідовність випадкових величин $X_{1},X_{2},\ldots$, спільний розподіл яких вважається відомим
2. Послідовність функцій «винагороди». $(y_{i})_{i\geq 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 (що розшифровується як Mayer, Lagrange and supremum відповідно).

Методи вирішення

Загалом існує два підходи до вирішення задачі оптимальної зупинки. Коли основний процес (або процес посилення) описується безумовними кінцевовимірними розподілами, відповідним методом вирішення є мартингальний підхід, який називається так тому, що він використовує мартингальну теорію, найважливішою концепцією якої є конверт Снелла. У випадку дискретного часу, якщо горизонт планування $T$ скінченний, задачу також можна легко вирішити за допомогою динамічного програмування.

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

Результат дифузії стрибка

Нехай $Y_{t}$ буде дифузією Леві в $\mathbb {R} ^{k}$, яка описується СДР

$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].$

Виявляється, що за деяких умов регулярності справедлива перевірочна теорема: Якщо функція $\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 \geqslant M$ на ${\mathcal {S}}$, і
• ${\mathcal {A}}\phi +L\leqslant 0$ на ${\mathcal {S}}\setminus \partial D$, де ${\mathcal {A}}$ є нескінченно-малим генератором $(Y_{t})$,

то $\phi (y)\geqslant 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}$) — це послідовність пропозицій для вашого будинку, а послідовність функцій винагород — це те, скільки ви заробите.

Задача про перебірливу наречену

(Приклад де $(X_{i})$ є скінченною послідовністю)

Ви спостерігаєте за послідовністю об'єктів, які можна ранжувати від найкращого до найгіршого. Ви хочете вибрати правило зупинки, яке максимізує ваші шанси вибрати найкращий об'єкт.

Ось, якщо $R_{1},\ldots ,R_{n}$ (n — деяке велике число) — ранги об'єктів, і $y_{i}$ — це ймовірність вибору найкращого об'єкта, якщо ви припините навмисно відхиляти об'єкти на кроці i $(R_{i})$ і $(y_{i})$ — це послідовності, пов'язані з цією задачею. Ця задача була розв'язана на початку 1960-х років кількома людьми. Елегантне розв'язання задачі про перебірливу наречену та кілька модифікацій цієї задачі забезпечує більш сучасний алгоритм шансів (алгоритм Брюса).

Теорія пошуку

Економісти досліджували низку проблем оптимальної зупинки, подібних до «задач про перебірливу наречену», і зазвичай називають цей тип аналізу «теорією пошуку». Теорія пошуку особливо зосереджена на пошуку працівником високооплачуваної роботи або пошуку споживачем недорогого товару.

Проблема паркування

Особливим прикладом застосування теорії пошуку є задача оптимального вибору паркувального місця водієм, який прямує в оперу (театр, шопінг тощо). Наближаючись до пункту призначення, водій їде вулицею, вздовж якої є паркувальні місця — зазвичай вільними є лише деякі місця на парковці. Ціль добре видно, тому відстань до цілі оцінюється легко. Завдання водія — вибрати вільне місце для паркування якомога ближче до пункту призначення, не їздячи по колу, щоб відстань від цього місця до місця призначення була найменшою.

Торгівля опціонами

Під час торгівлі опціонами на фінансових ринках власнику американського опціону дозволяється скористатися правом купити (або продати) базовий актив за заздалегідь визначеною ціною в будь-який час до або на дату закінчення терміну дії. Таким чином, оцінка американських опціонів є, по суті, проблемою оптимальної зупинки. Розглянемо класичну модель Блека — Шоулза і дозволимо $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)^{+}$ для опції call (далі «колл») і $g(x)=(K-x)^{+}$ для put-опціону (далі «пут»). Варіаційна нерівність є

$\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$ є межею вправи. Відомо, що розв'язок

• (Вічний колл) $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 для дискретного розрахунку оптимального часу для тренування на основі дерева.

Див. також

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

Список літератури

Джерела

• Thomas S. Ferguson, Optimal Stopping and Applications, retrieved on 21 June 2007
• Thomas S. Ferguson, «Who solved the secretary problem?» Statistical Science, Vol. 4.,282–296, (1989)
• F. Thomas Bruss. «Sum the odds to one and stop.» Annals of Probability, Vol. 28, 1384—1391,(2000)
• F. Thomas Bruss. «The art of a right decision: Why decision makers want to know the odds-algorithm.» Newsletter of the European Mathematical Society, Issue 62, 14–20, (2006)
• Rogerson, R.; Shimer, R.; Wright, R. (2005). Search-theoretic models of the labor market: a survey (PDF). Journal of Economic Literature. 43 (4): 959—88. doi:10.1257/002205105775362014. JSTOR 4129380.