Arrêt optimal

En mathématiques, la théorie de l'arrêt optimal ou de l'arrêt anticipé concerne le problème du choix d'un moment pour entreprendre une action spécifique, afin de maximiser une récompense attendue ou de minimiser un coût attendu. Des problèmes d'arrêt optimaux peuvent être trouvés dans les domaines des statistiques, de l'économie et des mathématiques financières (liés à la tarification des options américaines). Un exemple clé de problème d'arrêt optimal est le problème du secrétaire. Les problèmes d'arrêt optimal peuvent souvent être écrits sous forme d'une équation de Bellman et souvent résolus à l'aide d'une programmation dynamique.

En temps discret

Les problèmes de règle d'arrêt sont liés à deux entités :

1. Une séquence de variables aléatoires $X_{1},X_{2},\ldots$, dont la distribution jointe est supposé connu
2. Une séquence de fonctions de « récompense » $(y_{i})_{i\geq 1}$ qui dépendent des valeurs observées des variables aléatoires en 1 :

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

En considérant ces éléments, le problème se pose de la manière suivante :

• Vous observez la séquence de variables aléatoires, et à chaque étape $i$, vous pouvez choisir d'arrêter l'observation ou de continuer
• Si vous arrêtez d'observer à l'étape $i$, vous recevrez une récompense $y_{i}$
• Vous souhaitez choisir une règle d'arrêt pour maximiser votre récompense attendue (ou de manière équivalente, minimiser votre perte attendue)

En temps continu

Soit un processus de gain $G=(G_{t})_{t\geq 0}$ défini sur un espace de probabilité filtré $(\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} )$ et supposons que $G$ est adapté à la filtration. Le problème d'arrêt optimal est de trouver le temps d'arrêt $\tau ^{*}$ qui maximise le gain attendu

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

où $V_{t}^{T}$ est appelée la fonction valeur . Ici $T$ peut prendre de la valeur $\infty$ .

Nous considérons un processus de Markov adapté $X=(X_{t})_{t\geq 0}$ défini sur un espace de probabilité filtré $(\Omega ,{\mathcal {F}},({\mathcal {F}}_{t})_{t\geq 0},\mathbb {P} _{x})$ où $\mathbb {P} _{x}$ désigne la mesure de probabilité à laquelle le processus stochastique commence à $x$ . Étant donné les fonctions continues $M,L$, et $K$, le problème d'arrêt optimal est

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

Parfois, on fait référence à la formulation MLS, abréviation représentant les noms de Mayer, Lagrange et Supremum.

Méthodes de résolution

Il existe deux approches pour résoudre les problèmes d’arrêt optimal. Lorsque le processus sous-jacent (ou le processus de gain) est décrit par ses distributions inconditionnelles de dimension finie, la technique de solution appropriée est l'approche martingale, ainsi appelée parce qu'elle utilise la théorie de la martingale, le concept le plus important étant l'enveloppe de Snell. Pour des plages de temps discrètes et un horizon de planification fini, la résolution du problème peut être aisément effectuée en utilisant la programmation dynamique.

Lorsque le processus sous-jacent est déterminé par une famille de fonctions de transition (conditionnelles) conduisant à une famille de probabilités de transition de Markov, de puissants outils analytiques fournis par la théorie des processus de Markov peuvent souvent être utilisés et cette approche est appelée méthode de Markov. La solution est généralement obtenue en résolvant les problèmes de frontière libre (problèmes de Stefan).

Un résultat de diffusion par saut

Soit $Y_{t}$, une diffusion Lévy en $\mathbb {R} ^{k}$ donné par le SDE

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

où $B$ est un $m$-dimensionnel mouvement brownien, ${\bar {N}}$ est un $l$-dimensionnel mesure aléatoire de Poisson compensée, $b:\mathbb {R} ^{k}\to \mathbb {R} ^{k}$, $\sigma :\mathbb {R} ^{k}\to \mathbb {R} ^{k\times m}$, et $\gamma :\mathbb {R} ^{k}\times \mathbb {R} ^{k}\to \mathbb {R} ^{k\times l}$ reçoivent des fonctions telles qu'une solution unique $(Y_{t})$ existe. Soit ${\mathcal {S}}\subset \mathbb {R} ^{k}$, un ensemble ouvert (la région de solvabilité) et

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

, le moment de la faillite. Le problème d’arrêt optimal est :

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

Il s’avère que sous certaines conditions de régularité, le théorème de vérification suivant est valable :

Si une fonction $\phi :{\bar {\mathcal {S}}}\to \mathbb {R}$ satisfait

• $\phi \in C({\bar {\mathcal {S}}})\cap C^{1}({\mathcal {S}})\cap C^{2}({\mathcal {S}}\setminus \partial D)$ où se trouve la région de continuation $D=\{y\in {\mathcal {S}}:\phi (y)>M(y)\}$ ,
• $\phi \geq M$ sur ${\mathcal {S}}$, et
• ${\mathcal {A}}\phi +L\leq 0$ sur ${\mathcal {S}}\setminus \partial D$, où ${\mathcal {A}}$ est le générateur infinitésimal de $(Y_{t})$

alors $\phi (y)\geq V(y)$ pour tout $y\in {\bar {\mathcal {S}}}$ . De plus, si

• ${\mathcal {A}}\phi +L=0$ sur $D$

Alors $\phi (y)=V(y)$ pour tout $y\in {\bar {\mathcal {S}}}$ et $\tau ^{*}=\inf\{t>0:Y_{t}\notin D\}$ est un temps d'arrêt optimal.

Exemples

Lancer de pièces

(Exemple où $\mathbb {E} (y_{i})$ converge)

Vous avez une pièce de monnaie et vous la lancez à plusieurs reprises. À chaque fois, avant qu'il ne soit lancé, vous pouvez choisir d'arrêter de le lancer et d'être payé (en dollars, par exemple) le nombre moyen de piles observés.

${\text{Bern}}\left({\frac {1}{2}}\right),$

et si

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

alors les séquences $(X_{i})_{i\geq 1}$, et $(y_{i})_{i\geq 1}$ sont les objets associés à ce problème.

(Exemple où $\mathbb {E} (y_{i})$ ne converge pas nécessairement)

Vous possédez une maison et souhaitez la vendre. Chaque jour on vous propose $X_{n}$ pour votre maison et vous payez $k$ pour continuer à en faire la publicité. Si vous vendez votre maison le jour $n$, vous gagnerez $y_{n}$, où $y_{n}=(X_{n}-nk)$ .

Vous souhaitez maximiser le montant que vous gagnez en choisissant une règle d'arrêt.

Dans cet exemple, la séquence ( $X_{i}$ ) est la séquence d'offres pour votre maison, et la séquence de fonctions de récompense correspond au montant que vous gagnerez.

Problème de secrétaire

(Exemple où $(X_{i})$ est une suite finie)

Vous cherchez à adopter une séquence d’objets qui peuvent être classés du meilleur au pire. Vous souhaitez choisir une règle d'arrêt qui maximise vos chances de sélectionner le meilleur objet.

Ici, si $R_{1},\ldots ,R_{n}$ ( n est un grand nombre) sont les rangs des objets, et $y_{i}$ est la chance que vous choisissiez le meilleur objet si vous arrêtez de rejeter intentionnellement des objets à l'étape i, alors $(R_{i})$ et $(y_{i})$ sont les séquences associées à ce problème. Ce problème a été résolu dans les années 1960 par plusieurs personnes. Une solution au problème du secrétaire et plusieurs modifications de ce problème sont fournies par l'algorithme de cotes d'arrêt optimal le plus récent (algorithme de Bruss).

Théorie de la recherche

Les économistes ont étudié un certain nombre de problèmes d'arrêt optimal similaires au « problème du secrétaire » et appellent généralement ce type d'analyse « théorie de la recherche ». La théorie de la recherche s'est spécifiquement penchée sur la quête d'un employé pour un poste à haute rémunération ou la recherche d'un consommateur pour un produit à prix réduit.

Problème de stationnement

Un exemple particulier d'application de la théorie de la recherche est la sélection optimale d'une place de stationnement par un conducteur se rendant à l'opéra (théâtre, shopping, etc.). En arrivant à destination, le conducteur emprunte la rue le long de laquelle se trouvent des places de stationnement – généralement, seules certaines places du parking sont gratuites. L'objectif est clairement visible, ce qui permet d'évaluer facilement la distance par rapport à la cible. La tâche du conducteur est de sélectionner un emplacement de stationnement gratuit le plus proche possible de la destination sans faire demi-tour afin que la distance de cet endroit à la destination soit la plus courte.

Négociation d'options

Lors de la négociation d'options sur les marchés financiers, le détenteur d'une option américaine est autorisé à exercer le droit d'acheter (ou de vendre) l'actif sous-jacent à un prix prédéterminé à tout moment avant ou à la date d'expiration. La valorisation des options américaines constitue donc essentiellement un problème d’arrêt optimal. Considérons une configuration classique de Black-Scholes et soit $r$,,le taux d’intérêt sans risque ; $\delta$, le taux de dividende et $\sigma$, la volatilité du titre. Le cours de l'action $S$ suit le mouvement brownien géométrique suivant :

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

dans le cadre de la mesure de risque neutre.

Lorsque l’option est perpétuelle, le problème d’arrêt optimal est :

$V(x)=\sup _{\tau }\mathbb {E} _{x}\left[e^{-r\tau }g(S_{\tau })\right]$

où la fonction de paiement est $g(x)=(x-K)^{+}$ pour une option d'achat et $g(x)=(K-x)^{+}$ pour une option de vente. L'inégalité variationnelle est la suivante :

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

pour tout $x\in (0,\infty )\setminus \{b\}$ où $b$ est la limite de l’exercice. La solution est connue pour être

• (Option d'achat perpétuel) $V(x)={\begin{cases}(b-K)(x/b)^{\gamma }&x\in (0,b)\\x-K&x\in [b,\infty )\end{cases}}$ où $\gamma =({\sqrt {\nu ^{2}+2r}}-\nu )/\sigma$ et $\nu =(r-\delta )/\sigma -\sigma /2,\quad b=\gamma K/(\gamma -1).$
• (Option de vente perpétuelle) $V(x)={\begin{cases}K-x&x\in (0,c]\\(K-c)(x/c)^{\tilde {\gamma }}&x\in (c,\infty )\end{cases}}$ où ${\tilde {\gamma }}=-({\sqrt {\nu ^{2}+2r}}+\nu )/\sigma$ et $\nu =(r-\delta )/\sigma -\sigma /2,\quad c={\tilde {\gamma }}K/({\tilde {\gamma }}-1).$

D’un autre côté, lorsque la date d’expiration est finie, le problème est associé à un problème bidimensionnel à frontière libre sans solution de forme fermée connue. Diverses méthodes numériques peuvent cependant être utilisées, comme le modèle Black-Scholes pour diverses méthodes d'évaluation ici, ainsi que Fugit pour un calcul discret, basé sur un arbre, du moment optimal pour exercer.

Articles connexes

• Problème d'arrêt
• Processus de décision markovien
• Théorème d'arrêt facultatif
• Contrôle stochastique