Numerical probabalistic methods for high-dimensional problems in finance

The American Institute of Mathematics

This is a hard–copy version of a web page available through http://www.aimath.org

Input on this material is welcomed and can be sent to workshops@aimath.org Version: Fri Mar 26 16:54:11 2004

Table of Contents

A. Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1. High-dimensional Problems in Finance and extension a. Some stochastic control problems in finance b. Extensions and BSDE’s

2. Some New Methodologies a. The case where b and a does not depend on Y and Z b. The case where b or a depends on Y and Z

3. A test problem

4. Reduction of the dimension

5. References

Chapter A: Open problems

A.1 High-dimensional Problems in Finance and extension

A.1.a Some stochastic control problems in finance. Several examples were considered.

Optimal Stopping and free boundary problems.

Let’s consider the following financial market containing a non-risky asset S_{t}^{0} = e^{rt}, and d risky assets (e.g. stocks) with prices modeled by a d-dimensional diffusion process S with dynamics

dS_{t} = rS_{t}dt + diag(S_{t})σ(t, S_{t})dW_{t} ,

where W is a standard Brownian motion.

An important problem in finance is the pricing of American options. Given a reward function g, an American option is a contract that provides to the owner the right to receive (from the seller) the amount g(S_{t}) at any time t if exercised before some fixed maturity T. This right can be exercised only once during the period [0, T]. The price of this option at time t can be expressed as the value function associated to the optimal stopping problem

v(t, S_{t}) = sup_{τ∈T_{[t,T]}} E[e^{−r(τ−t)}g(S_{t}) | S_{t}] (1.1.1)

where T_{[t,T]} is the set of all stopping times with values in [t, T].

The associated value function v is the solution of the free boundary problem

min{rv − v_{t} − Lv ; v − g} = 0  on [0, T) × [0, ∞)^{d}
v(T, .) = g(.) on [0, ∞)^{d}

where L is the generator of the diffusion S.

Optimal Investment and Hamilton-Jacobi-Bellman equations.

An other important issue in finance is that of optimal investment. Denoting by ν_{t} the number of stocks held by a given financial agent at time t, the associated wealth-process X^{ν} has dynamics given by

dX_{t} = ν_{t}dS_{t} + (X_{t} − ν_{t}^{∗}S_{t})dS_{t}^{0}

where ^{∗} stands for transposition, and S may have a general dynamics of the form

dS_{t} = μ(t, S_{t}, ν_{t})dt + σ(t, S_{t}, ν_{t})dW_{t},

in order to take into account a possible influence of the agent’s financial strategy on the dynamics of the risky assets. Given a concave (utility) function V, the agent tries to maximize the expected utility of terminal wealth

max E[V (X_{T}^{ν})] (1.1.2)

over a set of admissible financial strategies (ν_{t}) with values in some subset U of R^{d}. The associated value function v is the solution of Hamilton-Jacobi-Bellman equation

−v_{t} − sup_{ν∈U} L^{ν}v = 0 on [0, T) × [0, ∞)^{d} × R
v(T, s, x) = V (x) for (s, x) ∈ [0, ∞)^{d} × R

where L^{ν} is the generator of the diffusion (S, X^{ν}) .

A.1.b Extensions and BSDE’s. The value function of Problem (1.1.1) can be reformulated in terms of the Y component of the solution (Y, Z, A) of the Backward Stochastic Differential Equation

Y_{t} = g(S_{T}) − ∫_{t}^{T} Z_{t}^{∗}dW_{t} + A_{T} − A_{t}
Y_{t} ≥ g(S_{t})

where A is a non-decreasing process satisfying

∫_{0}^{T} (Y_{t} − g(S_{t}))dA_{t} = 0,

see e.g. [KKPPQ].

This leads us to consider the more general problem of approximating the solution of Reflected Forward - Backward Stochastic Differential Equations of the form

X_{t} = X_{0} + ∫_{t}^{T} b(t, X_{t}, Y_{t}, Z_{t})dt + ∫_{t}^{T} a(t, X_{t}, Y_{t}, Z_{t})dW_{t}
Y_{t} = g(T, X_{T}) + ∫_{t}^{T} f(t, X_{t}, Y_{t}, Z_{t})dt − ∫_{t}^{T} Z_{t}^{∗}dW_{t} + A_{T} − A_{t}
Y_{t} ≥ g(t, X_{t})

where A is a non-decreasing process satisfying

∫_{0}^{T} (Y_{t} − g(t, X_{t}))dA_{t} = 0.

This framework partially includes control problems associated to HJB equations. It is related to non-linear PDE’s of the form

min\{−v_{t}(t, x) − \frac{1}{2}Trace[v_{xx}(t, x)aa^{∗}(t, x, v(t, x), θ(t, x))]

−b(t, x, v(t, x), θ(t, x))^{∗}v_{x}(t, x) − f(t, x, v(t, x), θ(t, x))
; v(t, x) − g(t, x)} = 0

v(T, .) = g(T, .)

where θ(t, x) solves

v_{x}(t, x)a(t, x, v(t, x), θ(t, x)) = θ(t, x) ,

through the relations

v(t, X_{t}) = Y_{t} and θ(t, X_{t})^{∗} = Z_{t} .

See e.g. [MY].

A.2 Some New Methodologies

A.2.a The case where b and a does not depend on Y and Z. Several methods were considered.

Pure Monte Carlo Methods.

Pure Monte-Carlo methods are based on a discrete time approximation of the forwardbackward equation. Once discretized the forward process can be simulated. These simulations are then used to compute the conditional expectations involved in the backward discrete time approximation of (Y, Z). Two different methods can be used to compute these conditional expectations.

a. The Longstaff-Schwartz (Carriere) approach consists in approximating the conditional expectations by regressions on a given basis of functions. This provides a very powerful, and, easy to implement, algorithm for which convergence has been shown to hold in the case of the American option pricing problem. However, no rate of convergence is given and the choice of the basis is a quite difficult problem. It has been used successfully in up to 20 factors models. See [C] , [LS], [CLP].

b. The Malliavin approach consists in re-writing the conditional expectations as the ratio of two unconditional expectations that can be estimated by standard Monte-Carlo methods. Upper bounds for the rate of convergence are proved. Contrary to the previous approach, this algorithm also provides good approximations for the greeks, i.e. the gradient of the associated value function (which is related to the Z, see above). So far, the existing algorithm has a too important complexity, which explains why it has only been tested in small dimensions (up to 5). Some numerical improvements have been proposed, reducing the complexity from N^{2} to N ln(N)^{d}, where N is the number of simulated paths. This work is still in progress, the aim being to develop an algorithm such that the major part of the work is done before a reward function is specified, so as to reduce as much as possible the effective computation time once a particular payoff is defined. See [BET], [BT].

Grid approximations.

The Quantization approach consists in approximating the original forward process by a discrete time process which evolves on some finite grid. The grid is constructed so has to provide the best L^{p} approximation. It was first applied to the pricing of American options in dimension up to 10. The construction of the optimal grid (and the computation of the associated transition probabilities) is very time consuming, but it can be done once for all. Once the grid, which is independent of the payoff function, is constructed, it provides a very quick algorithm for pricing American options on different payoffs, whenever they are written on the same assets. As in the Malliavin and Longstaff-Schwartz approach, the use of a good control variable is required. Extensions to non-linear filtering, optimal control and Asian-type options have also been studied. See [BP1], [BP2], [PP1], [PP2].

Dual formulation.

This algorithm is based on a dual formulation for problem (1.1.1):

v(0, S_{0}) = inf E [sup_{t≤T}(e^{−rt}g(S_{t}) − M_{t})]

where the inf is taken over a well suited set of martingales M. This algorithm consists in providing a upper bound for v by choosing some martingale M^{∗} and computing

E [sup_{t≤T}(e^{−rt}g(S_{t}) − M_{t}^{∗})]

In cases where a good martingale M̂ can be found, typically when

E[e^{−r(T −t)}g(S_{T})|S_{t}] =: M̂_{t}

is known as a function of S, this provides a quite sharp upper bound for the price of the American option. Numerical experiments, up to dimension 15, have been performed. See [R].

Cubature on Wiener spaces.

Cubature formula on Wiener spaces have been developed in [VL] in order to construct probability measures with finite support which approximate the Wiener measure in the sense that the expectation of iterated Stratonovich integrals under the approximating measure and the Wiener measure are close. In a sense, this approach is similar to that of the quantization since it allows to reduce to a finite dimensional setting. So far, it has been used to develop high order numerical schemes for high dimensional SDE’s and semi-elliptic PDE’s.

A.2.b The case where b or a depends on Y and Z. In that case, it is no more possible to approximate (or simulate) the forward process X since its dynamic depends on the solution. In such situations, two different solutions have been proposed:

a - Construct an a priori grid for X, possibly based on some a priori on the dynamics of Y and Z.

b - Given an a priori solution Y_{0} and Z_{0}, approximate (or simulate) the corresponding forward process X_{0} and use the above methodologies to construct the corresponding solution (Y_{1}, Z_{1}) of the BSDE. Then, use this solution (Y_{1}, Z_{1}) to approximate (or simulate) the corresponding forward process X_{1} and go on iterating this procedure. Under some mild assumptions, this algorithm should be convergent. However, it seems to be quite heavy to implement.

Solution a. has already been applied in the quantization approach but, so far, does not provide very good results. See [PP1].

A.3 A test problem

A test problem has been proposed to compare the performance of the different methods. It corresponds to the computation of a d dimensional at-the-money American min-put option in the Black-Scholes model.

The assets are uncorrelated, have the same volatility and the same initial value :

S_{t}^{i} = 100 exp((r − σ^{2}/2)t − σW_{t}^{i}) for each i = 1, ..., d

where W = (W^{1}, ..., W^{d}) is a standard Brownian motion. The payoff function is

g(x) = [100 − min{x^{1}, ..., x^{d}}]^{+}.

Numerical tests will be performed for different dimensions with σ = 20% and r = 5% . Results will be collected and compared by J. Cvitanic.

A.4 Reduction of the dimension

Different ways of reducing the dimension were proposed.

a- The first consists in using Principal Component Analysis in order to ”aggregate” a large number of random variables in a small number of principal directions. Also it is used in practice, it does not really solve the problem of the dimension, but only surrounds it, replacing the initial model by a more tractable, but different, one.

b- Instead of relying on PCA, dimension could be reduced by considering models where a few number of economic fundamentals could explain the behavior of many financial assets.

c- In some cases, it is possible to reduce the dimension without changing the initial model. This is the case in P. Carr’s Canadization approach for the computation of American options, where the randomization of the maturity allows to reduce to a time homogeneous problem. Extensions to Markovian control problems have been discussed. See [Carr] and [BKT].

A.5 References

[BP1] Bally V. and G. Pages: A quantization algorithm for solving discrete time multidimensional optimal stopping problems, Bernoulli, (9) 6, 1-47, 2003.

[BP2] Bally V. and G. Pages: Error analysis of the quantization algorithm for obstacle problems, Stochastic Processes and their Applications,106 (1), 1-40, 2003.

[BT] Bouchard B. and N. Touzi: Discrete Time Approximation and Monte-Carlo Simulation of Backward Stochastic Differential Equations, Stochastic Processes and their Applications, to appear.

[BET] Bouchard B., I. Ekeland and N. Touzi: On the Malliavin approach to Monte Carlo approximation of conditional expectations, Finance and Stochastics, 8 (1), 2004.

[BKT] Bouchard B., N. El Karoui and N. Touzi: Maturity randomization for stochastic control problems, in preparation.

[Carr] Carr P.: Randomization and the American Put, The Review of Financial Studies, 11, 597-626, 1997.

[C] Carriere E.: Valuation of the Early-Exercise Price for Options using Simulations and Nonparametric Regression, Insurance: mathematics and Economics, 19, 19-30, 1996.

[CLP] Clément E., D. Lamberton, and P. Protter: An analysis of a least squares regression method for American option pricing, Finance and Stochastics, 6, 449-472, 2002.

[KKPPQ] El Karoui N., C. Kapoudjan, E. Pardoux, S. Peng and M.C. Quenez: Reflected solutions of backward stochastic differential equations and related obstacle problems for PDE’s, Annals of Probability, 25, 702-737, 1997.

[LS] Longstaff F.A. and R.S. Schwartz: Valuing American Options By Simulation: A simple Least-Square Approach, Review of Financial Studies, 14, 113-147, 2001.

[MY] Ma J. and J. Yong: Forward-Backward Stochastic Differential Equations and Their Applications, Lecture Notes in Math., 1702, Springer, 1999.

[PP1] Pages G. and H. Pham: A quantization algorithm for multidimensional stochastic control problems, preprint LPMA n^{∘}697, 2001.

[PP2] Pages G. and H. Pham: Optimal quantization methods for nonlinear filtering with discrete-time observations, preprint LPMA n^{∘}778, 2002.

[R] Rogers L.C.G.: Monte Carlo valuation of American options, Mathematical Finance, 12, 271-286, 2002.

[VL] Victoir N. and T. Lyons: Cubature on Wiener space, Proc. R. Soc. Lond. A, 460, 169-198, 2004.