Serving the Quantitative Finance Community

 
User avatar
londoner
Topic Author
Posts: 1
Joined: January 28th, 2008, 2:52 am

Fastest numerical method to price barrier options?

July 13th, 2012, 2:02 pm

What is the fastest and accurate method to price barrier options with a continuous barrier? How about options with a discrete barrier?ADEADIhybrid (Laplace Transform + FDM)FEMMarkov Chain(any others?)
Last edited by londoner on July 12th, 2012, 10:00 pm, edited 1 time in total.
 
User avatar
Darou
Posts: 2
Joined: August 6th, 2002, 11:03 am

Fastest numerical method to price barrier options?

July 13th, 2012, 8:26 pm

This highly depends on your market model. E.g. for Black-Scholes with constant interest-rate and constant volatility, there are very fast analytic solutions (Up-and-out-barrier option: http://www.thetaris.com/wiki/Barrier_Option). Fast PDE methods can handle Black-Scholes with interest-rate curves and volatility surfaces. What kind of Market Model are you looking at?--Darou
 
User avatar
londoner
Topic Author
Posts: 1
Joined: January 28th, 2008, 2:52 am

Fastest numerical method to price barrier options?

July 14th, 2012, 3:27 am

Ultimately, I will use a GBM model with interest rate term structures and local volatilities.I know that analytical solutions exist for GBM with constant interest rate and volatility. But to begin with, I intend to price barrier options with constant parameter values using finite difference methods and see which one is the most efficient.After some internet search, I found that Daniel Duffy had pointed out that ADE is faster than Crank-Nicolson. Is ADE the fastest finite difference method then?
 
User avatar
Darou
Posts: 2
Joined: August 6th, 2002, 11:03 am

Fastest numerical method to price barrier options?

July 14th, 2012, 9:10 am

Ok, for PDE the speed also highly depends on your mesh structure and your boundary conditions. Under some conditions I observed that purely implicit conditions are faster than CN or ADE. Especially, sharp edges like in up-and-out call options can be a problem. So, my advice is that you should do some research on mesh structures (see e.g. Pooley et al), too.If you change your volatility surface not very often, you might also combine Monte-Carlo with a sparse-grid high-dimensional interpolation: We did that in Theta Proxy and we could get extremely fast pricings.
 
User avatar
londoner
Topic Author
Posts: 1
Joined: January 28th, 2008, 2:52 am

Fastest numerical method to price barrier options?

July 14th, 2012, 3:55 pm

Let's assume that the mesh structure is optimal for the respective numerical scheme. Is implicit finite difference still faster than ADE?
 
User avatar
Darou
Posts: 2
Joined: August 6th, 2002, 11:03 am

Fastest numerical method to price barrier options?

July 16th, 2012, 11:17 am

I cannot tell - in theory, all three methods can have quadratic convergence. And I guess that you will not find a definite answer to this question. ADE and CN are good candidates for high-speed but in many cases Implicit is fast enough and less error prone. The final speed of your implementation will depend mostly on the setting: E.g. sparse matrix structure, type of matrix solver, potential for parallelization, boundary conditions, grid, smoothing, tricks like Rannacher timestepping or sparse-grid combination technique, usage of libraries like Intel MKL or NAG...). If speed is such an issue for you I can only tell you to implement and benchmark a few of your relevant cases.
 
User avatar
Cuchulainn
Posts: 17658
Joined: July 16th, 2004, 7:38 am
Location: Lviv

Fastest numerical method to price barrier options?

July 19th, 2012, 8:26 pm

ADE is faster than ADIA good way to quantify this question is to ask what your desired accuracy is and where in the region. This will determine the NS, NT and hence speed.See the article July 11 Wilmott by Pealat and Duffy. ADE is 40% more fast than CN.I have now ADE for pde in the conservative form a(bV_x)_x and Tavella 2000 nonuniform grids and is great around K. Implicit is OK but it introduces numerical dispersion. edit: IMO Rannacher is a blunt instrument, a fudge.
Last edited by Cuchulainn on July 18th, 2012, 10:00 pm, edited 1 time in total.
вот мой дорогой двоюродный брат
 
User avatar
Cuchulainn
Posts: 17658
Joined: July 16th, 2004, 7:38 am
Location: Lviv

Fastest numerical method to price barrier options?

July 21st, 2012, 8:25 pm

Here's a comparison from a while back.
Attachments
BarrierFDM_FEM_Exact.zip
(57.43 KiB) Downloaded 85 times
вот мой дорогой двоюродный брат
 
User avatar
Cuchulainn
Posts: 17658
Joined: July 16th, 2004, 7:38 am
Location: Lviv

Fastest numerical method to price barrier options?

July 29th, 2012, 5:50 pm

I have a question. For double barrier options with narrow barriers and/or large vol. (e.g. [90, 110] and .35) I get funny results using ADE and uniform meshes (it might be a coding bug). This is a different PDE from the usual one on a semi-infinite interval as we now have explicit Dirichlet boundary conditions at the lower and upper boundaries. If I take NT > 5*NS it works but this is not satisfactory.Is this a pathological case or is there something else going on? I am using continuous monitoring.
Last edited by Cuchulainn on July 28th, 2012, 10:00 pm, edited 1 time in total.
вот мой дорогой двоюродный брат
 
User avatar
londoner
Topic Author
Posts: 1
Joined: January 28th, 2008, 2:52 am

Fastest numerical method to price barrier options?

August 2nd, 2012, 6:01 pm

Below is my Matlab code for pricing down-and-out call options by explicit finite difference. I transformed two variables, which are x = ln(S) and tau = T-t = time to expiry. The upper boundary condition is u(i+1,1)=exp(-r*tau)*u(i,1) and the lower boundary condition is u(i,Nx) = 0 for all i. Can anyone have a look at my code and let me know why the price produced by this code is way off the analytical value? Thanks!function price = test_SingleBarrier_EFD(H,K,Texp,So,r,sig,Nt,NX)% Pricing down-and-out call options by the explicit finite difference% method.% H : barrier% K : strike price% Texp : time to expiry% So : spot price% r : risk-free rate% q : dividend yield (not included yet)% sig : volatility% Nt : number of time partitions% NX : number of variable X partitions% time griddt = Texp / (Nt - 1);t = (0 : Nt - 1) * dt;% X grid Xmin = log(H);Xmax = log(3 * K); % a dummy upper barrierdX = (Xmax - Xmin) / (NX - 1);X = Xmax : -dX : Xmin;% check stability condition: dt/dX^2 < 1instable = (dt / dX ^ 2 > 1);if instable disp('need more time steps.');end% calculate coefficientsalpha = dt / dX ^ 2;a_ = -0.5 * alpha * dX * (r - sig ^ 2 / 2) + 0.5 * sig ^ 2 * alpha;b_ = 1 - sig ^ 2 * alpha - r * dt;c_ = 0.5 * alpha * dX * (r - sig ^ 2 / 2) + 0.5 * sig ^ 2 * alpha;a = repmat(a_, 1, NX - 2);b = repmat(b_, 1, NX - 2);c = repmat(c_, 1, NX - 2);A = diag([a, 0], -1) + diag([exp(-r * dt), b, 0]) + diag([0, c], 1);Vold = [max(exp(X(1 : NX - 1)) - K, 0)'; 0];Vnew = A * Vold;for i = 2 : Nt - 1 Vold = Vnew; Vnew = A * Vold;end% optVal = Vnew * exp(-r * Texp);optVal = Vnew;logS = log(So);j = (Xmax - logS) / dX;j1 = 1 + ceil(j); % index of the lower pricej2 = 1 + floor(j); % index of the higher priceprice = ((X(j2) - logS) / (X(j2) - X(j1))) * optVal(j1) + ((logS - X(j1)) / (X(j2) - X(j1))) * optVal(j2);% -------------- Results -----------------% % test_SingleBarrier_EFD(90,100,1,95,.1,.25,10000,100)% ans = 2.4881 Analytical value for this down-and-out call option = 5.9968
 
User avatar
Cuchulainn
Posts: 17658
Joined: July 16th, 2004, 7:38 am
Location: Lviv

Fastest numerical method to price barrier options?

August 3rd, 2012, 10:27 am

First, sanity check is to take H --> infinity and check that the price approaches classical BS price (this checks your code). Second, the scheme is explicit (!?) so Nt might need to be bigger. What about implicit or ADE?
вот мой дорогой двоюродный брат
 
User avatar
londoner
Topic Author
Posts: 1
Joined: January 28th, 2008, 2:52 am

Fastest numerical method to price barrier options?

August 3rd, 2012, 6:11 pm

Since this is a down-and-out call option, setting H to 0 should yield the BS price, but my code does not!Yes, the scheme is explicit, and Nt=10000 should be big enough as NX=100 and the stability condition is satisfied. I also implemented the implicit scheme. Interestingly, the "implicit" price is similar to the "explicit" price, which means both prices are way off the analytical price. What's wrong? Are there mistakes in my boundary conditions? Is log transformation problematic? I haven't implemented ADE yet. I plan to get the standard schemes right first. Then, they will be used as benchmarks to evaluate ADE.
Last edited by londoner on August 2nd, 2012, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 17658
Joined: July 16th, 2004, 7:38 am
Location: Lviv

Fastest numerical method to price barrier options?

August 4th, 2012, 11:43 am

The upper boundary log(3K) might be an issue. The usual truncatiion is well documented so it migt be an idea to try it. (btw I prefer domain transfrormation y = S/(S+a)). If XMax is to small then incorrect answers are possible. Quote Is log transformation problematic? It makes life easier but it might be useful to do FDM directly with S.
Last edited by Cuchulainn on August 3rd, 2012, 10:00 pm, edited 1 time in total.
вот мой дорогой двоюродный брат
 
User avatar
londoner
Topic Author
Posts: 1
Joined: January 28th, 2008, 2:52 am

Fastest numerical method to price barrier options?

August 16th, 2012, 2:20 pm

Questions to Cuchulainn:1. You mentioned that "ADE is 40% more fast than CN". Was the comparison based on non-parallel code?The following questions are based on your paper titled "Unconditionally stable and second-order ...... Part I. One-Factor Equity Problems".2. Can ADE be applied to the original PDE? Do you expect similar results will be achieved?3. On page 20, the sentence above Table 12 says "The processing time for non-parallel code is similar to that of the ADE method ...". Given that the implicit Euler method is almost as accurate as ADE (compare Tables 11 and 12) and ADE is not much faster for non-parallel code, is ADE still preferred to implicit Euler when parallel programming is not used?4. Is ADE a consistent (convergent to the true value) scheme? Examining Tables 1 and 2 on page 17, I found that increasing NT for a fixed NY (and vice versa) does not necessarily improve the price accuracy. For instance, the second row (NY=200) in Table 1 indicates that the option price at NT=1000 is farther away from the true price than that at NT=100, 200 or 500. In Table 2, the option price at NY=500, NT=500 is worse than that at NY=200, NT=500. 5. I am concerned with the accuracy of ADE. In Table 3 on page 18, the ADE price in the rightmost column is significantly worse than the IEuler price (73.70187 versus 73.63129, and the exact price is 73.6463). In the leftmost column, the ADE price is worse than both IEuler and Monte Carlo prices. I understand the Monte Carlo price is a statistical estimate, but still I did not expect ADE was beaten by Monte Carlo.Thank you!
Last edited by londoner on August 15th, 2012, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 17658
Joined: July 16th, 2004, 7:38 am
Location: Lviv

Fastest numerical method to price barrier options?

August 16th, 2012, 6:31 pm

Thanks for the feedback. I have run these again as a lot has changed since the SSRN paper. I have two new chapters on the wqy.Quote1. You mentioned that "ADE is 40% more fast than CN". Was the comparison based on non-parallel code?DD Sequential. ADE is too small to run parallel.QuoteThe following questions are based on your paper titled "Unconditionally stable and second-order ...... Part I. One-Factor Equity Problems".2. Can ADE be applied to the original PDE? Do you expect similar results will be achieved?DD you mean w/o domain transformation i.e. rather using truncation? Then yes.Quote3. On page 20, the sentence above Table 12 says "The processing time for non-parallel code is similar to that of the ADE method ...". Given that the implicit Euler method is almost as accurate as ADE (compare Tables 11 and 12) and ADE is not much faster for non-parallel code, is ADE still preferred to implicit Euler when parallel programming is not used?DD It's a choice in 1d. For 2 factors, IE is not there. Hers is a relevant analysis:http://arnetminer.org/publication/simpl ... htmlQuote4. Is ADE a consistent (convergent to the true value) scheme? Examining Tables 1 and 2 on page 17, I found that increasing NT for a fixed NY (and vice versa) does not necessarily improve the price accuracy. For instance, the second row (NY=200) in Table 1 indicates that the option price at NT=1000 is farther away from the true price than that at NT=100, 200 or 500. In Table 2, the option price at NY=500, NT=500 is worse than that at NY=200, NT=500. DD it is conditionally consistent O(k^2 + h^2 + (h/k)^2) See Lapidus and Pinder 1982.Did the tests again. I get better answers now (BTW P_exact = 5.84584)Seems ok now. Maybe my code was wrong...Quote5. I am concerned with the accuracy of ADE. In Table 3 on page 18, the ADE price in the rightmost column is significantly worse than the IEuler price (73.70187 versus 73.63129, and the exact price is 73.6463). In the leftmost column, the ADE price is worse than both IEuler and Monte Carlo prices. I understand the Monte Carlo price is a statistical estimate, but still I did not expect ADE was beaten by Monte Carlo.DD ADE has a wee bit of bother with this extreme case. With ADE extrapolated I get 73.63493 (NY = 300, NT = 500)
Last edited by Cuchulainn on August 15th, 2012, 10:00 pm, edited 1 time in total.
вот мой дорогой двоюродный брат