최적정지

수학에서 최적 정지^[1][2] 또는 조기 정지^[3] 이론은 기대 보상을 최대화하거나 기대 비용을 최소화하기 위해 특정 행동을 취할 시간을 선택하는 문제와 관련이 있다. 최적의 중지 문제는 통계, 경제 및 수학 금융 분야(미국 옵션의 가격 책정 관련)에서 찾을 수 있다. 최적의 중단 문제의 핵심 예는 비서 문제다. 최적 정지 문제는 벨만 방정식의 형태로 쓰여질 수 있으며, 따라서 동적 프로그래밍을 사용하여 해결되는 경우가 많다.

정의

이산 시간 사례

규칙 문제를 중지하는 것은 다음 두 가지 개체와 관련이 있다.

1. 랜덤 변수 $X{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle {}_{}{X\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$… ${\displaystyle X_{1}, X_{2},\ldots }$의 시퀀스로$,$ 이 변수들의 공동 분포는 알려진 것으로 가정된 것이다.
2. 1: 랜덤 변수의 관측된 값에 따라 달라지는$$ 일련의 'reward' 함수$({\displaystyle y_{}{}_{}}$i ) ${\displaystyle {i1}_{}}$ 1$${\$displaystyle (y_{i}_{i\geq 1}):$

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

그러한 대상들을 감안할 때 문제는 다음과 같다.

• 랜덤 변수의 순서를 관찰하고 있으며 각 단계 $i{\displaystyle }$ ${\displaystyle i$에서 관찰을 중지하거나 계속하도록 선택할 수 있음
• $i{\displaystyle }$ ${\displaystyle i$ 단계에서 관찰을 중단하면 y ${\displaystyle i_{}}$ ${\$ 보상을 받게 된다.
• 예상 보상을 최대화하기 위해(또는 동등하게, 예상 손실을 최소화하기 위해) 중지 규칙을 선택하려는 경우

연속 타임 케이스

Consider a gain process ${\displaystyle G=(G_{t})_{t\geq 0}}$ defined on a filtered probability space ${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )}$ and assume that ${\displaystyle G}$ is adapted to the filtration. 최적의 정지문제는 정지시간${\$을 찾는 것으로 예상$$ 이득 극대화

${\디스플레이 스타일 V_{t}^{T}=\mathb {E}G_{\tau ^{*}}}}\sup _{t\leq \tau \leq T}\mathb {E}G_{\tau }}}}}}}}}$

${\displaystyle {여기}_{}^{}}$서 V ${\displaystyle {}_{}^{}}$ ${\$T$}}$을(를) 값함수라고 한다. 여기서 $T{\displaystyle }$ ${\displaystyle T}$은(는) 값 $\infty {\displaystyle \mathrm{}}$ ${\displaystyle \infit }$을(를) 취할 수 있다$$$.$

좀 더 구체적인 공식은 다음과 같다. We consider an adapted strong Markov process ${\displaystyle X=(X_{t})_{t\geq 0}}$ defined on a filtered probability space ${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} _{x})}$ where ${\displaystyle \mathb$$b {P} _{x}}$는 확률적 $과정$이 x ${\displaystyle x}$에서 시작되는 확률측정을 나타낸다$$$.$ 연속함수 $M{\displaystyle ,}$ ${\displaystyle L}$ ${\displaystyle M,L$ $K{\displaystyle }$ ${\displaysty 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, Supremeum을 의미한다) 공식이라고 부르기도 한다.^[4]

솔루션 방법

최적의 정지 문제를 해결하는 데는 일반적으로 두 가지 방법이 있다.^[4] 기반 프로세스(또는 이득 프로세스)가 그것의 무조건적인 유한 차원 분포에 의해 설명될 때, 적절한 해결 기법은 마팅게일 접근법인데, 마팅게일 이론을 사용하기 때문에 그렇게 불린다. 가장 중요한 개념은 스넬 봉투다. 이산 시간 사례에서 계획 지평선 $T{\displaystyle }$ ${\$디스플레이 $스타일 T}$이(가) 유한하다면 동적 프로그래밍으로도 문제를 쉽게 해결할 수 있다.

기본 프로세스가 마르코프 전환 확률로 이어지는 (조건부) 전환 기능의 패밀리에 의해 결정되는 경우, 마르코프 프로세스 이론에 의해 제공되는 강력한 분석 도구를 종종 활용할 수 있으며 이러한 접근방식을 마르코프 방법이라고 한다. 해법은 보통 관련 자유경계 문제(스테판 문제)를 해결함으로써 얻는다.

점프 확산 결과

$Y{\displaystyle {}_{}}$ ${\displaystyle t_{}}$ ${\$을(를) SDE가 제공한$$ $R{\displaystyle {\mathbb{}}^{}}$ {\$displaystyle \mathb {R}^{k}$의 레비 확산으로 한다$$.

${\displaystyle dY_{t}=b(Y_{t}})=dt+\sigma(Y_{t}}}+\int_{\mathb {R}^{k}}\gamma(Y_{t-}z){{N}}(dz),quad Y_{0=y}$

where ${\displaystyle B}$ is an ${\displaystyle m}$-dimensional Brownian motion, ${\displaystyle {\bar {N}}}$ is an ${\displaystyle l}$-dimensional compensated Poisson random measure, ${\displaystyle b:\mathbb {R} ^{k}\to \mathbb {R} ^{k}}$, ${\displaystyle \sigma :{\mathbb{R}}^k\to {\mathbb{R}}^{k\times m}}$${\displaystyle \sigma :\mathbb {R} ^{k}\to \mathbb {R} ^{k\times m}}$, and ${\displaystyle \gamma :\mathbb {R} ^{k}\times \mathbb {R} ^{k}\to \mathbb {R} ^{k\times l}}$ are given functions such that a unique solution ${\displaystyle (Y_{t})}$ exists. $S{\displaystyle \mathcal{}}$ ${\displaystyle \subset }$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ ${\$을(를) 오픈 세트(지급 능력 영역)로$$ 하고

${\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]

함수 $\varphi {\displaystyle }$: ${\displaystyle S\stackrel{}{\mathcal{}}\to }$ → ${\displaystyle R\mathbb{}}$ ${\$ {$S}\}\to \mathb {R}이($가) 충족되는$$ 경우

• ${\displaystyle \phi \in C({\bar {\mathcal {S}}})\cap C^{1}({\mathcal {S}})\cap C^{2}({\mathcal {S}}\setminus \partial D)}$ where the continuation region is ${\displaystyle D=\{y\in {\mathcal {S}}:\phi (y)>M(y)\}}$,
• ${\displaystyle \varphi }$ ${\$의$$${\displaystyle \ge }$ \ ${\displaystyle M}$ ${\displaystyle \phi \geq M}$ 및
• ${\displaystyle {\mathcal {A}}\phi +L\leq 0}$ on ${\displaystyle {\mathcal {S}}\setminus \partial D}$, where ${\displaystyle {\mathcal {A}}}$ is the infinitesimal generator of ${\displaystyle (Y_{t})}$

$그{\displaystyle }$ 다음 ${\displaystyle (}$ (${\displaystyle y}$ )${\displaystyle v}$V (${\displaystyle y}$ )$${\$displaystyle \phi (y)\$$geq$ V$(y)}$ $모든{\displaystyle }$ y${\displaystyle s\stackrel{}{\mathcal{}}}$ S$'{\bar {\mathcal {S}}$에 대한$$ $.$ 더욱이,

• ${\displaystyle }$$D{\displaystyle }$ ${\displaystyle D}$의 A ${\displaystyle \varphi }$+ ${\displaystyle L}$= ${\displaystyle 0}$ ${\displaystyle {\mathcal {A}\phi +L=0}$

$\varphi {\displaystyle }$( ${\displaystyle y}$)${\displaystyle }$= ${\displaystyle V}$( ${\displaystyle y}$) ${\displaystyle \phi (y)=V(y$$)}$ $모든$ y${\displaystyle s\stackrel{}{\mathcal{}}}$ S의$\\$ y$\in {\\bar {\\\mathcal {S}}$및 = $inf$ $t$> 0: > D ${\displaysty$ \tauy $\tauy ^{*}}$$Y_{t}\notin D\}}$은(는) 최적의 정지 시간이다.

또한 이러한 조건은 보다 압축적인 형태(integro-various confliction):

• ${\displaystyle }$$S{\displaystyle \mathcal{}}$ ${\displaystyle \setminus }$ $∂$ ${\displaystyle D.}$ $displaystyle$$$$\max \left\{\mathcal{A}\l$,M-$\phi \right\}=0}$에 있는 ${\displaystyle 최대}${\$displaystyle {\mathcal$ {$S}\setminus \partial D$$.$$}$

예

동전던지기

($예{\displaystyle \mathbb{}}$: E${\displaystyle }$( ${\displaystyle {}_{}}$ ${\displaystyle i_{}}$) ${\displaystyle \mathb {E}(y_{i})$이 수렴되는$$ 경우)

너는 공정한 동전을 가지고 있고 그것을 반복해서 던지고 있다. 매번 던지기 전에 던지지 않고 관찰된 평균 헤드 수를 지불(달러 단위)하도록 선택할 수 있다.

당신은 정지 규칙을 선택하여 당신이 받는 금액을 최대화하기를 원한다. X_i(i ≥ 1)가 베르누이 분포와 함께 동일한 분포의 독립 랜덤 변수의 시퀀스를 형성하는 경우

${\displaystyle {\text{Vern}\왼쪽({\frac {1}{2}}\오른쪽),}$

그리고 만약

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

그러면 시퀀스$({\displaystyle {Xi}_{}{}_{}}$) i$i$ ${\displaystyle 1_{}}$ ${\${i\$geq$ 1$},$ $({\displaystyle y_{}{}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle {\ge }_{}}$ ${\displaystyle 1_{}}$ ${\$ 1)이 이 문제와 관련된 개체들이다$$.

주택판매

($예{\displaystyle \mathbb{}}$: E${\displaystyle }$( ${\displaystyle y_{}}$ i${\displaystyle {}_{}}$) ${\displaystyle \mathb {E}(y_{i})$이 반드시 수렴되지 않는$$ 경우)

너는 집을 가지고 있고 그것을 팔기를 원한다. 매일 당신은 당신의 집을 위해$$ ${\displaystyle {Xn}_{}}$ ${\$를 제공받고, $계속$해서 광고를 하기 위해$$ k ${\displaystyle k}$을(를) 지불한다. $만약{\displaystyle }$ 당신이 당신의 집을 n일 ${\displaystyle n}$에$$팔면 ${\displaystyle {당신}_{}}$은 y n ${\$를 벌게 될 것이다$.$ ${\displaystyle {여기}_{}}$서 yn${\displaystyle }$=${\displaystyle {}_{}}$( X${\displaystyle {}_{}{n}_{}}$ - $){n}=(X_{n}-nk$ .

중지 규칙을 선택하여 수입을 최대화하려는 경우.

이 예에서 순서(${\displaystyle {Xi}_{}}$ ${\$는 집을 위한 제의의 순서이며, 보상 기능의 순서는 얼마를 벌 것인가이다.

비서 문제

(예:${\displaystyle }$(${\displaystyle {Xi}_{}}$) ${\displaystyle (X_{i})}$은(는) 유한 시퀀스)

당신은 최고에서 최저로 순위가 매겨질 수 있는 일련의 물체들을 관찰하고 있다. 당신은 가장 좋은 물건을 고를 기회를 극대화하는 정지 규칙을 선택하기를 원한다.

Here, if ${\displaystyle R_{1},\ldots ,R_{n}}$ (n is some large number) are the ranks of the objects, and ${\displaystyle y_{i}}$ is the chance you pick the best object if you stop intentionally rejecting objects at step i, then ${\displaystyle (R_{i})}$ and ${\displaystyl$$e (y_{i}})$는 이 문제와 관련된 시퀀스 입니다. 이 문제는 1960년대 초에 몇몇 사람들에 의해 해결되었다. 비서 문제에 대한 우아한 해결책과 이 문제의 몇 가지 수정은 최적 정지(Bruss 알고리즘)의 최신 오즈 알고리즘에 의해 제공된다.

검색이론

경제학자들은 '비서의 문제'와 유사한 최적의 중지 문제를 여러 가지 연구해 왔으며, 일반적으로 이러한 분석을 '탐색 이론'이라고 부른다. 검색 이론은 특히 노동자가 고임금 일자리를 찾거나 소비자가 저가 상품을 찾는 데 초점을 맞췄다.

주차 문제

검색이론을 응용한 특별한 예로는 오페라(연극, 쇼핑 등)에 가는 운전자의 최적의 주차공간 선택 과제가 있다. 목적지에 다가가면 운전자는 주차 공간이 있는 거리를 따라 내려간다. 보통 주차장의 일부 장소만 무료다. 목표가 뚜렷이 보이므로 목표와의 거리가 쉽게 평가된다. 운전자의 과제는 이곳에서 목적지까지의 거리가 가장 짧도록 방향을 돌리지 않고 목적지에 최대한 가까운 무료 주차 공간을 선택하는 것이다.^[6]

옵션거래

금융시장에 대한 옵션의 거래에서 미국옵션 보유자는 만기일 전이나 만료일에 언제든지 미리 정해진 가격으로 기초자산을 매입하거나 매도할 수 있는 권리를 행사할 수 있다. 따라서 미국 옵션의 가치평가는 본질적으로 최적의 중단문제다. $고전적$인 블랙-숄즈 설정을 고려하고 r ${\displaystyle r}$을(를) 무위험 금리로 하고$$ $\Delta {\displaystyle }$ ${\displaystyle \delta }$과 $\Delta {\displaystyle }$ ${\displaystyle \sigma}$을(를) 주식의 배당률과 변동성으로 간주한다$$. 주가 $S{\displaystyle }$ ${\displaystyle S}$은(는) 기하학적 브라운 모션을 따른다$$.

${\displaystyle S_{t}=S_{0}\exp \왼쪽(r-\delta -{\frac {\sigma ^{2}}:\오른쪽)+\sigma B_{t}\오른쪽\}}}}}}$

위험 중립적인 조치하에

옵션이 영구적일 때 최적의 중지 문제는

${\displaystyle V(x)=\sup _{\tau }\mathb {E} _{x}\left[e^{-r\tau }g(S_{\tau }}\오른쪽)}}}$

여기서 지불함수는 ${\displaystyle \mathrm{콜옵션}}$의 경우$$ $g{\displaystyle }$( x${\displaystyle }$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle x}$- ${\displaystyle K{}^{}}$)${\displaystyle {}^{}}$+ ${\$이고, 풋옵션의 $경우$ g${\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle k}$- ${\displaystyle x{}^{}}$)${\displaystyle {}^{}}$+ ${\$이다. 변동성 불평등은

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

모든 $x{\displaystyle }$ ${\displaystyle \in }$(${\displaystyle 0}$ ,${\displaystyle \mathrm{\infty }}$) ${\displaystyle \setminus }$ {${\displaystyle b}$} ${\displaystyle$x\$in (0,\infit )\setminus \{b\}$에 대해, $여기$서 b ${\displaysty$ b$}$은 연습 경계선이다$$. 해결책은 다음과 같은 것으로^[7] 알려져 있다.

• (항구적인 호출)V())){(b− K)(x/b)γ)∈(0, b)x− Kx∈는 경우 b, ∞){\displaystyle V())={\begin{경우}(b-K)(x/b)^{\gamma}&, x\in(0,b)\\x-K&, x\in는 경우에는 b,\infty)\end{경우}}}이γ =(ν 2+2r− ν)/σ{\displaystyle \gamma =({\sqrt{\nu ^{2}+2r}}-\nu)/\sigma}과ν= (r− δ${\displaystyle$$\nu$$}$
• (Perpetual을)V())){K−)x ∈(0c](K− c)(x/c)γ일)∈(c, ∞){\displaystyle V())={\begin{경우}K-x&, x\in(0,c]\\(K-c)(x/c)^{\tilde{\gamma}}&x\in(c,\infty)\end{경우}}}이γ일)−(ν 2r 2++ν)/σ{\displaystyle{\tilde{\gamma}}=-({\sqrt{\nu ^{2.}+2r}}+\$nu )/\sigma }$ and ${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,\quad c={\tilde {\gamma }}K/({\tilde {\gamma }}-1).$$}$

한편, 유효기간이 한정되어 있을 때, 문제는 알려진 폐쇄형 해결책이 없는 2차원 자유경계 문제와 연관된다. 그러나 다양한 수치적 방법을 사용할 수 있다. 여기에서 다양한 평가 방법에 대한 블랙-숄즈 모델#아메리칸 옵션과 이산형 트리 기반 최적의 운동 시간 계산에 대한 푸짓(Pugit)을 참조하십시오.

참고 항목

• 중지 문제
• 마르코프 의사결정 과정
• 선택적 정지 정리
• 예언자 부등식
• 확률 제어

참조

• 토마스 S. 퍼거슨, 최적의 중지 및 애플리케이션, 2007년 6월 21일 검색
• 토마스 S. 퍼거슨 "비서 문제는 누가 해결했나?" 통계학, 제4,282–296권 (1989)
• F. 토마스 브루스. "확률을 1로 요약하고 멈춰라." 확률 연보, 제28권, 1384–1391, 제28권
• F. 토마스 브루스. "올바른 결정의 기술: 왜 의사 결정자들이 오즈 알고리즘을 알고 싶어하는가." 유럽수학학회 소식지, 이슈 62, 14–20, (2006)
• Rogerson, R.; Shimer, R.; Wright, R. (2005). "Search-theoretic models of the labor market: a survey". Journal of Economic Literature. 43 (4): 959–88. JSTOR 4129380.