Optymalne zatrzymanie

W matematyce teoria optymalnego zatrzymania lub wczesnego zatrzymania dotyczy problemu wyboru czasu na podjęcie określonego działania, aby zmaksymalizować oczekiwaną nagrodę lub zminimalizować oczekiwany koszt. Problemy optymalnego zatrzymania można znaleźć w obszarach statystyki , ekonomii i finansów matematycznych (związanych z wyceną opcji amerykańskich ). Kluczowym przykładem optymalnego problemu zatrzymania jest problem sekretarki . Problemy optymalnego zatrzymania można często zapisać w postaci równania Bellmana i dlatego często rozwiązuje się je za pomocą programowania dynamicznego .

Definicja

Przypadek czasu dyskretnego

Problemy z regułą zatrzymywania są powiązane z dwoma obiektami:

Sekwencja zmiennych losowych , $rozkład$ jest czymś, co zakłada
Sekwencja funkcji „nagrody”
${\ Displaystyle y_ {i} = y_ {i} (x_ {1}, \ ldots, x_ {i})}$
$obserwowanych$ losowych w 1

Biorąc pod uwagę te obiekty, problem jest następujący:

Obserwujesz sekwencję zmiennych losowych i na każdym kroku $kontynuować$ przerwać obserwację lub
Jeśli przestaniesz obserwować w kroku $displaystyle$ otrzymasz nagrodę $y_ {i}}$
Chcesz wybrać regułę zatrzymania , aby zmaksymalizować oczekiwaną nagrodę (lub równoważnie, zminimalizować oczekiwaną stratę)

Przypadek czasu ciągłego

$Ω$ proces ${\ Displaystyle (\ Omega, {\ mathcal {F}}, ({\ mathcal {F}} _ {t}) _ {t \ geq 0}, \ mathbb {P})} i załóżmy, że$ na filtrowanej sol $\ styl wyświetlania G}$ jest dostosowany do filtracji. Optymalnym problemem zatrzymania jest znalezienie czasu zatrzymania , który maksymalizuje oczekiwany zysk ${\ Displaystyle \ tau ^ {*}}$

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

gdzie $_$ funkcją . _ Tutaj może przyjąć wartość $displaystyle \ infty}$ $\$ .

Bardziej specyficzna formuła jest następująca. Rozważamy $zdefiniowany$ proces ${\ Displaystyle (\ Omega, {\ mathcal {F}}, ({\ mathcal {F}} _ {t}) _ {t \ geq 0}, \ mathbb {P} _ {x} )}$ przestrzeni gdzie ${\ Displaystyle \ mathbb {P} _ {x}}$ oznacza miarę prawdopodobieństwa , w której proces stochastyczny rozpoczyna się w ${\ displaystyle x}$ . Biorąc pod uwagę funkcje ciągłe i optymalnym problemem zatrzymania jest ${\ displaystyle M,$ $}$

{\ Displaystyle V (x) = \ sup _ {0 \ równoważnik \ tau \ równoważnik T} \ mathbb {E} _ {x} \ lewo (M (X_ {\ tau}) + \ int _ {0} ^ { \tau }L(X_{t})dt+\sup _{0\równoważnik t\równik \tau}K(X_{t})\prawo).}

Nazywa się to czasem formułą MLS (co oznacza odpowiednio Mayer, Lagrange i supremum).

Metody rozwiązania

Zasadniczo istnieją dwa podejścia do rozwiązywania problemów z optymalnym zatrzymaniem. Gdy podstawowy proces (lub proces wzmocnienia) jest opisany przez jego bezwarunkowe rozkłady skończonych wymiarów , odpowiednią techniką rozwiązania jest podejście martyngałowe, zwane tak, ponieważ wykorzystuje teorię martyngałów , przy czym najważniejszą koncepcją jest obwiednia Snella . W przypadku czasu dyskretnego, jeśli horyzont planowania $.$ skończony , problem można również łatwo rozwiązać za pomocą programowania dynamicznego

Kiedy podstawowy proces jest określony przez rodzinę (warunkowych) funkcji przejściowych prowadzących do rodziny prawdopodobieństw przejścia Markowa, często można wykorzystać potężne narzędzia analityczne dostarczane przez teorię procesów Markowa, a podejście to jest określane jako metoda Markowa. Rozwiązanie zwykle uzyskuje się, rozwiązując powiązane problemy swobodnej granicy ( problemy Stefana ).

Wynik dyfuzji skoku

Niech będzie dyfuzją Lévy'ego w $\ mathbb {R} ^ {k}}$ $Displaystyle$ podaną przez SDE Y t

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

gdzie jest $-wymiarowym$ ${\ Displaystyle B}$ ruchem Browna $-wymiarową$ jest L $\ displaystyle l}$ miarą losową Poissona , ${\ Displaystyle b: \ mathbb {R} ^ {k} \ do \ mathbb {R} ^ {k}}$ , ${\ Displaystyle \ sigma: \ mathbb {R} ^ {k} \ do \ mathbb {R} ^ {k \ razy m}} i γ : R k$ × $: \mathbb {R} ^{k}\times \mathbb {R} ^{k}\to \mathbb {R} ^{k\times l}} podane są takie funkcje, że unikalne rozwiązanie ($ Y $Displaystyle (Y_{t})}$ istnieje. Niech ${\ Displaystyle {\ mathcal {S}} \ podzbiór \ mathbb {R} ^ {k}}$ być zbiorem otwartym (obszar wypłacalności) i

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

być czasem bankructwa. Optymalny problem zatrzymania to:

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

Okazuje się, że przy pewnych warunkach regularności zachodzi następujące twierdzenie weryfikacyjne:

Jeśli funkcja spełnia ϕ $\ Displaystyle \ phi: {\ bar {\ mathcal {S}}} \ do \ mathbb {R}}$

${\ Displaystyle \ phi \ w C ({\ bar {\ mathcal {S}}}) \ czapka C ^ {1} ({\mathcal {S}})\cap C^{2}({\mathcal {S}}\setminus \partial D)} gdzie$ regionem kontynuacji jest ${\ Displaystyle D = \ {y \ w {\ mathcal {S}}: \ phi (y)> M (y) \}}$ ,
${\ Displaystyle \ phi \ geq M}$ na ${\ Displaystyle {\ mathcal {S}}}$ i
${\ Displaystyle {\ mathcal {A}} \ phi + L \ równoważnik 0}$ na ${\ Displaystyle {\ mathcal {S}} \ setminus \ częściowy D}$ gdzie ${\ Displaystyle {\ mathcal {A}}}$ jest nieskończenie małym generatorem ( $\ Displaystyle (Y_ {t})}$

wtedy ${\ Displaystyle \ phi (y) \ geq V (y)}$ dla wszystkich ${\ Displaystyle y \ in {\ bar {\ mathcal {S}}}}$ . Co więcej, jeśli

${\ Displaystyle {\ mathcal {A}} \ phi + L = 0}$ na ${\ displaystyle D}$

ϕ $V (y)}$ dla wszystkich ${\ Displaystyle y \ in {\ bar {\ mathcal {S}}}}$ i ${\ Displaystyle \ tau ^ {*} = \ inf \ {t> 0: Y_ {t} \ notin D \}}$ to optymalny czas zatrzymania.

Warunki te można również zapisać w bardziej zwartej postaci ( nierówność całkowo-wariacyjna ):

${\ Displaystyle \ max \ lewo \ {{\ mathcal {A}} \ phi + L, M- \ phi \ prawej \} = 0}$ na ${\ Displaystyle {\ mathcal {S}} \ setminus \ częściowe D.}$

Przykłady

Rzucanie monetą

(Przykład, gdzie ${\ Displaystyle \ mathbb {E} (y_ {i})}$ zbiega się)

Masz uczciwą monetę i wielokrotnie ją rzucasz. Za każdym razem, zanim zostanie wyrzucony, możesz zatrzymać rzucanie i otrzymać zapłatę (powiedzmy w dolarach) za średnią liczbę zaobserwowanych orłów.

Chcesz zmaksymalizować kwotę, którą otrzymujesz, wybierając regułę zatrzymania. Jeżeli X _i (dla i ≥ 1) tworzy ciąg niezależnych zmiennych losowych o identycznym rozkładzie z rozkładem Bernoulliego

{\ Displaystyle {\ tekst {Berno}} \ lewo ({\ Frac {1} {2}} \ prawej)}

i jeśli

{\ Displaystyle y_ {i} = {\ Frac {1} {i}} \ suma _ {k = 1} ^ {i} X_ {k}}

$i}) _ {$ sekwencje ${\$ { to obiekty powiązane z tym problemem.

Sprzedaż domu

(Przykład, gdzie ${\ Displaystyle \ mathbb {E} (y_ {i})}$ niekoniecznie jest zbieżny)

Masz dom i chcesz go sprzedać. $dnia$ otrzymujesz ofertę $nadal$ swojego domu i płacisz, go reklamować. Jeśli sprzedasz swój dom w dniu $(X_ { n}-nk)}$ $=$ n - $}$ .

Chcesz zmaksymalizować zarobioną kwotę, wybierając regułę zatrzymania.

W tym przykładzie sekwencja ( $)$ to sekwencja ofert dla twojego domu, a sekwencja funkcji nagród to, ile

Problem z sekretarką

(Przykład, gdzie ${\ Displaystyle (X_ {i})}$ jest skończoną sekwencją)

Obserwujesz sekwencję obiektów, które można uszeregować od najlepszego do najgorszego. Chcesz wybrać regułę zatrzymania, która zmaksymalizuje twoje szanse na wybranie najlepszego obiektu.

Tutaj, jeśli ( n jest jakąś ${n}} }$ liczbą) to rangi obiektów ${\ Displaystyle R_ {1}, \ ldots, R_$ to szansa, że wybierzesz najlepszy obiekt, jeśli przestaniesz celowo odrzucać obiekty w kroku i, a następnie ${\ Displaystyle (R_ {i})}$ i ${\ Displaystyle (y_ {i})}$ to sekwencje związane z tym problemem. Problem ten został rozwiązany na początku lat 60. przez kilka osób. Eleganckie rozwiązanie problemu sekretarki i kilka modyfikacji tego problemu zapewnia nowszy algorytm prawdopodobieństwa optymalnego zatrzymania (algorytm Brussa).

Teoria wyszukiwania

Ekonomiści przestudiowali szereg optymalnych problemów zatrzymania podobnych do „problemu sekretarki” i zazwyczaj nazywają ten typ analizy „teorią poszukiwań”. Teoria wyszukiwania koncentrowała się szczególnie na poszukiwaniu przez pracownika wysoko płatnej pracy lub poszukiwaniu przez konsumenta taniego towaru.

Problem z parkowaniem

Szczególnym przykładem zastosowania teorii poszukiwań jest zadanie optymalnego wyboru miejsca parkingowego przez kierowcę udającego się do opery (teatru, na zakupy itp.). Zbliżając się do celu, kierowca jedzie ulicą, wzdłuż której znajdują się miejsca parkingowe – zazwyczaj tylko niektóre miejsca na parkingu są wolne. Cel jest dobrze widoczny, więc łatwo ocenić odległość od celu. Zadaniem kierowcy jest wybranie wolnego miejsca parkingowego jak najbliżej celu bez zawracania, tak aby odległość z tego miejsca do celu była jak najkrótsza.

Handel opcjami

W obrocie opcjami na rynkach finansowych posiadacz opcji amerykańskiej może skorzystać z prawa do kupna (lub sprzedaży) instrumentu bazowego po z góry określonej cenie w dowolnym momencie przed lub w dniu wygaśnięcia opcji. Dlatego wycena opcji amerykańskich jest zasadniczo problemem optymalnego zatrzymania. $Rozważmy$ klasyczną konfigurację Blacka-Scholesa i niech $}$ { \ displaystyle \ i ${\ displaystyle \ sigma}$ być stopą dywidendy i zmiennością akcji. Cena akcji $za$ geometrycznymi ruchami Browna

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

w ramach środka neutralnego pod względem ryzyka.

Gdy opcja jest wieczna, optymalnym problemem zatrzymania jest

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

gdzie funkcja wypłaty to ${\ Displaystyle g (x) = (xK) ^ {+}}$ dla opcji kupna i ${\ displaystyle g(x)=(Kx)^{+}}$ dla opcji put. Nierówność wariacyjna jest

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

dla wszystkich gdzie ${\ Displaystyle x \ in (0, \ infty) \ setminus \ {b \}}$ $granicą$ ćwiczenia . Rozwiązanie znane jest

(Nieustanna rozmowa) ${\ Displaystyle V (x) = {\ rozpocząć {przypadki }(bK)(x/b)^{\gamma }&x\in (0,b)\\xK&x\in [b,\infty )\end{przypadki}}}$ gdzie ${\ Displaystyle \ gamma = ({\ sqrt {\ nu ^ {2} + 2r}} - \ nu) / \ sigma}$ i ${\ Displaystyle \ nu = (r- \ delta) / \ sigma - \ sigma / 2, \ quad b = \ gamma K / (\ gamma -1).}$
(Perpetual put) ${\ Displaystyle V (x) = {\ rozpocząć { przypadki}Kx&x\in (0,c]\\(Kc)(x/c)^{\tilde {\gamma }}&x\in (c,\infty )\end{przypadki}}}$ gdzie $_$ _ ${\ Displaystyle \ nu = (r- \ delta) / \ sigma - \ sigma / 2, \ quad c = {\ tylda {\ gamma}} K / ({\ tylda {\ gamma}} -1).}$

Z drugiej strony, gdy data wygaśnięcia jest skończona, problem jest związany z dwuwymiarowym problemem swobodnej granicy bez znanego rozwiązania w postaci zamkniętej. Można jednak zastosować różne metody numeryczne. Zobacz model Blacka-Scholesa #opcje amerykańskie, aby zapoznać się z różnymi metodami wyceny tutaj, a także Fugit , aby uzyskać dyskretne, oparte na drzewie obliczenie optymalnego czasu na wykonanie.

Zobacz też

Cytaty

Źródła

Thomas S. Ferguson , Optimal Stopping and Applications , dostęp 21 czerwca 2007 r.
Thomas S. Ferguson , „ Kto rozwiązał problem sekretarki? ” Statistical Science , tom. 4.282-296 (1989)
F. Thomasa Brussa . „Zsumuj szanse do jednego i przestań”. Roczniki prawdopodobieństwa , tom. 28, 1384-1391, (2000)
F. Thomasa Brussa. „Sztuka podejmowania właściwych decyzji: dlaczego decydenci chcą znać algorytm prawdopodobieństwa”. Biuletyn Europejskiego Towarzystwa Matematycznego , wydanie 62, 14–20, (2006)
Rogerson, R.; Shimer, R.; Wright, R. (2005). „Teoretyczne modele wyszukiwania rynku pracy: ankieta” (PDF) . Dziennik Literatury Ekonomicznej . 43 (4): 959–88. doi : 10.1257/002205105775362014 . JSTOR 4129380 .