ในทางคณิตศาสตร์ทฤษฎีการหยุดที่เหมาะสมที่สุด^{[ 1 ] [ 2 ]}หรือการหยุดก่อนกำหนด^{[ 3 ]}เกี่ยวข้องกับปัญหาการเลือกเวลาที่จะดำเนินการเฉพาะอย่าง เพื่อเพิ่มผล ตอบแทนที่คาดหวังให้ สูงสุดหรือลดต้นทุนที่คาดหวังให้น้อยที่สุด ปัญหาการหยุดที่เหมาะสมที่สุดสามารถพบได้ในสาขาสถิติเศรษฐศาสตร์และการเงินเชิงคณิตศาสตร์ (ที่เกี่ยวข้องกับการกำหนดราคาของออปชั่นแบบอเมริกัน ) ตัวอย่างสำคัญของปัญหาการหยุดที่เหมาะสมที่สุดคือปัญหาเลขานุการปัญหาการหยุดที่เหมาะสมที่สุดมักจะเขียนได้ในรูปสมการเบลล์แมนและมักจะแก้โดยใช้ การ เขียน โปรแกรมแบบไดนามิก

ปัญหาเกี่ยวกับกฎการหยุดนั้นเกี่ยวข้องกับสองสิ่ง:

1. ลำดับของตัวแปรสุ่มซึ่งการแจกแจงร่วมของตัวแปรเหล่านั้นเป็นสิ่งที่สันนิษฐานว่าทราบอยู่แล้ว${\displaystyle X_{1},X_{2},\ldots }$
2. ลำดับของฟังก์ชัน 'รางวัล' ซึ่งขึ้นอยู่กับค่าที่สังเกตได้ของตัวแปรสุ่มในข้อ 1: ${\displaystyle (y_{i})_{i\geq 1}}$

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

เมื่อพิจารณาจากวัตถุเหล่านั้น ปัญหาจึงเป็นดังนี้:

• คุณกำลังสังเกตลำดับของตัวแปรสุ่ม และในแต่ละขั้นตอนคุณสามารถเลือกได้ว่าจะหยุดการสังเกตหรือสังเกตต่อไป${\displaystyle i}$
• หากคุณหยุดสังเกตการณ์ที่ขั้นตอนนี้คุณจะได้รับรางวัล${\displaystyle i}$${\displaystyle y_{i}}$
• คุณต้องการเลือกกฎการหยุดเพื่อเพิ่มผลตอบแทนที่คาดหวังให้สูงสุด (หรือในทางกลับกัน ลดการขาดทุนที่คาดหวังให้น้อยที่สุด)

พิจารณาถึงกระบวนการได้กำไรที่กำหนดไว้บนปริภูมิความน่าจะเป็นแบบกรองและสมมติว่ากระบวนการนั้นปรับให้เข้ากับการกรองแล้ว ปัญหาการหยุดที่เหมาะสมที่สุดคือการหาเวลาหยุดที่ทำให้กำไรที่คาดหวังสูงสุด ${\displaystyle G=(G_{t})_{t\geq 0}}$${\displaystyle (\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )}$${\displaystyle G}$${\displaystyle \tau ^{*}}$

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

เมื่อกระบวนการพื้นฐานถูกกำหนดโดยตระกูลของฟังก์ชันการเปลี่ยนสถานะ (แบบมีเงื่อนไข) ซึ่งนำไปสู่ตระกูลความน่าจะเป็นการเปลี่ยนสถานะแบบมาร์คอฟ เครื่องมือวิเคราะห์ที่มีประสิทธิภาพซึ่งได้มาจากทฤษฎีของกระบวนการมาร์คอฟมักจะสามารถนำมาใช้ได้ และวิธีการนี้เรียกว่าวิธีมาร์คอฟ โดยปกติแล้วจะได้คำตอบโดยการแก้ปัญหาขอบเขตอิสระ ที่เกี่ยวข้อง ( ปัญหาของสเตฟาน )

ให้เป็นการ แพร่แบบ เลวี (Lévy diffusion) ที่กำหนดโดยSDE${\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)}$

คุณต้องการเพิ่มผลตอบแทนสูงสุดโดยการเลือกกฎการหยุดการถอน

ในตัวอย่างนี้ ลำดับ ( ) คือลำดับของข้อเสนอสำหรับบ้านของคุณ และลำดับของฟังก์ชันรางวัลคือจำนวนเงินที่คุณจะได้รับ^{[ 6 ]}${\displaystyle X_{i}}$

(ตัวอย่างที่ลำดับเป็นลำดับจำกัด) ${\displaystyle (X_{i})}$

คุณกำลังสังเกตลำดับของวัตถุที่สามารถจัดอันดับจากดีที่สุดไปแย่ที่สุด คุณต้องการเลือกกฎการหยุดที่เพิ่มโอกาสในการเลือกวัตถุที่ดีที่สุดให้มากที่สุด

ในที่นี้ ถ้า( nเป็นจำนวนมาก) คือลำดับของวัตถุ และคือโอกาสที่คุณจะเลือกวัตถุที่ดีที่สุดหากคุณหยุดการปฏิเสธวัตถุโดยเจตนาในขั้นตอนที่ i แล้วและคือลำดับที่เกี่ยวข้องกับปัญหานี้ ปัญหานี้ได้รับการแก้ไขในช่วงต้นทศวรรษ 1960 โดยหลายคน วิธีแก้ปัญหาที่สง่างามสำหรับปัญหาเลขานุการและการดัดแปลงหลายอย่างของปัญหานี้ได้รับการนำเสนอโดยอัลกอริทึมความน่าจะเป็นของการหยุดที่เหมาะสมที่สุด (อัลกอริทึม Bruss) ที่ใหม่กว่า${\displaystyle R_{1},\ldots ,R_{n}}$${\displaystyle y_{i}}$${\displaystyle (R_{i})}$${\displaystyle (y_{i})}$

นักเศรษฐศาสตร์ได้ศึกษาปัญหาการหยุดที่เหมาะสมที่สุดหลายปัญหาที่คล้ายกับ 'ปัญหาเลขานุการ' และโดยทั่วไปเรียกการวิเคราะห์ประเภทนี้ว่า 'ทฤษฎีการค้นหา' ทฤษฎีการค้นหามุ่งเน้นเป็นพิเศษไปที่การค้นหางานที่มีค่าจ้างสูงของคนงาน หรือการค้นหาสินค้าที่มีราคาต่ำของผู้บริโภค

ตัวอย่างพิเศษของการประยุกต์ใช้ทฤษฎีการค้นหาคือภารกิจการเลือกที่จอดรถที่เหมาะสมที่สุดสำหรับผู้ขับขี่ที่กำลังจะไปชมโอเปร่า (โรงละคร ช้อปปิ้ง ฯลฯ) เมื่อใกล้ถึงจุดหมายปลายทาง ผู้ขับขี่จะขับไปตามถนนที่มีที่จอดรถ – โดยปกติจะมีที่ว่างเพียงบางส่วนในลานจอดรถเท่านั้น เป้าหมายสามารถมองเห็นได้อย่างชัดเจน ดังนั้นจึงสามารถประเมินระยะทางจากเป้าหมายได้อย่างง่ายดาย ภารกิจของผู้ขับขี่คือการเลือกที่จอดรถว่างที่ใกล้กับจุดหมายปลายทางมากที่สุดโดยไม่ต้องหันกลับ เพื่อให้ระยะทางจากจุดนั้นไปยังจุดหมายปลายทางสั้นที่สุด^{[ 7 ]}

ในการซื้อขายออปชั่นในตลาดการเงินผู้ถือออปชั่นแบบอเมริกันจะได้รับสิทธิ์ในการซื้อ (หรือขาย) สินทรัพย์อ้างอิงในราคาที่กำหนดไว้ล่วงหน้าได้ตลอดเวลาก่อนหรือในวันหมดอายุ ดังนั้น การประเมินมูลค่าของออปชั่นแบบอเมริกันจึงเป็นปัญหาการหยุดที่เหมาะสมที่สุด (optimal stopping problem) ลองพิจารณาการตั้งค่า แบบ Black–Scholes แบบคลาสสิก โดยให้ เป็นอัตราดอกเบี้ยที่ปราศจากความเสี่ยงและและเป็นอัตราเงินปันผลและความผันผวนของหุ้น ราคาหุ้นเป็นไปตามการเคลื่อนที่แบบบราวน์แบบเรขาคณิต (geometric Brownian motion) ${\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}$

สำหรับทุกกรณี ที่ขอบเขตการออกกำลังกายอยู่ วิธีแก้ปัญหาเป็นที่ทราบกันดีอยู่แล้วคือ^{[ 8 ]}${\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).}$
• (การขายแบบไม่จำกัดระยะเวลา) ที่และ${\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).}$

ในทางกลับกัน เมื่อวันหมดอายุมีขอบเขตจำกัด ปัญหาจะเกี่ยวข้องกับปัญหาขอบเขตอิสระแบบ 2 มิติ ซึ่งไม่มีคำตอบในรูปแบบปิดที่ทราบ อย่างไรก็ตาม สามารถใช้วิธีการเชิงตัวเลขต่างๆ ได้ ดูแบบจำลอง Black–Scholes#American optionsสำหรับวิธีการประเมินมูลค่าต่างๆ ได้ที่นี่ รวมถึงFugitสำหรับการคำนวณเวลาที่เหมาะสมที่สุดในการใช้สิทธิ แบบไม่ต่อเนื่องโดย ใช้โครงสร้างต้นไม้

• ปัญหาการหยุด
• กระบวนการตัดสินใจแบบมาร์คอฟ
• ทฤษฎีบทการหยุดแบบเลือกได้
• ความไม่เท่าเทียมกันของศาสดา
• การควบคุมแบบสุ่ม
• การวิเคราะห์ตามลำดับ