Serving the Quantitative Finance Community

 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

American options -- Reference prices

February 4th, 2016, 6:54 pm

QuoteOriginally posted by: AlanPoor choice of phrase. See my edit. Most free boundary problems are intractable in the same sense as the put option, AFAIK.Thinking out loud. Is BS PDE sooh much more difficult than Stefan? the former can be transformed into heat equation.
 
User avatar
Alan
Topic Author
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

American options -- Reference prices

February 4th, 2016, 10:39 pm

It is for purposes of trying to derive a scaling solution to a free boundary problem. Try it; I will guess you have a copy of Cannon's 'The one-dimensional heat equation". Go through the Stefan solution on pgs 287-288.Now try to imitate that exact solution approach with the BS put problem. It doesn't work even though the operator is essentially the heat operator both ways. Probably everybody interested in the put problem tries this at least once because the known answers and setups look so similar.For example, look in Paul's 1994 Option Pricing book with Dewynne and Howison; it's clear they attempted this. This comes to mind readily because I was trying it myself a couple weeks ago.I was actually trying to do something of the reverse. Namely, I have a nice solver version for the American-style put,using my favorite tool: NDSolve. So, I thought, gee it should be easy to show this solver method works to reproduce the famousStefan problem scaling solution, too. But I couldn't see how to translate the latter (Stefan) problem into something closeenough to the former (put) problem so as to apply my method. For example, the put can be approximated by a sequence of Bermudan put problems -- what is the analog of the Bermudan approach to the Stefan problem? I don't know, probably due to my having very superficial knowledge about the Stefan problem. That's where I got stuck ..
Last edited by Alan on February 4th, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

American options -- Reference prices

February 5th, 2016, 8:36 am

I think th definitive book is John Crank's "Free and Moving boundary problem". Chapter 5 has a good overview of front-fixing (e.g. Landau x = S/B(t) as implemented in the Nielson et al paper) coupled with a further transformation of timetau = Integral (0,t; B^-2(t)).This is an overview from outrun's alma mater. //Maybe the level-set method is worth a try because it can model the interface implicitly via a level-set function described by HJ equation. Seems the methods until now need ~explicit form for B(t)? Would be a good MSc IMO and it probably also works for 2/3 factors as well, which is not true for binomial nor Andersen?And maybe faster than penalty method.. // I was not familiar with Cannon heat bookBut I do know Canned Heat:)
Last edited by Cuchulainn on February 4th, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

American options -- Reference prices

February 6th, 2016, 10:34 am

QuoteOriginally posted by: outrunThe Andserson paper changes (S,t) to log(S/K, sqrt(t) )The first part look easy?[$]\begin{equation}\frac{dB(t)}{dt}= \frac{dv(t,B(t))}{dB(t)}\frac{dB(t)}{dt}+\cdots\end{equation}[$]the first fraction on the RHS is de delta of the European put.. Rearange this...What's ...?Which equation in Andersen are you working from? The general consensus seems to be that B(t) _cannot_ be written as an ODE.
Last edited by Cuchulainn on February 5th, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

American options -- Reference prices

March 7th, 2016, 8:34 am

QuoteOriginally posted by: AlanApparently we don't have a thread for this, so here is a good place to start.I am investigating convergence of some numerical methods and would appreciate it ifsomebody could confirm a 7-digit reference value under the Black-Scholes model.It is an American-style put option with [$]S_0 = K = 50[$], [$]T=1[$], [$]\sigma=0.40[$], and [$]r = 0.08[$] (no dividends).The put value is 6.299XXX; I need confirmation of the value I have for the 3 remaining digits, XXX.So as to not prejudice the answers, I'll give my value later in the thread.Thanks!This has been a fruitful thread.Another variant I have is (similar to NDSolve) consisting of several methods rolled into one:1. Using Courant's original barrier functions for the penalty term (I find it more intuitive than the Nielsen/Khaliq approach). Take lambda = 10^10.2. Boost odeint (MOL using Graag Bulisch Stoer (cf NDSOLVE).3. Extrapolation in S to get h^2 -> h^4 accuracy (A NS == 400 and extrap gives as good or better accuracy than NS = 5000 without extrap). And its seems to work well even with the semilinear penalty term.I took NS = 6000 and get P = 6.2995904 which is nice seeing all the new stuff to test. It is possible to get better by taking NS bigger. What's next? this approach can be extended in many ways. I think binomial and integral methods get stuck in one-factor problems and are a cul-de-sac in this regard I suppose. And the PDE/FDM approach is mathematically well-founded and you build on all that numerical analysis.
Last edited by Cuchulainn on March 6th, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

American options -- Reference prices

March 7th, 2016, 8:43 am

A nice feature in C++11 is the use of lambda functions to create PDEs on the fly/drop of a hat. So to change BS to CEV or CIR it's just a one-liner.I reckon NDSolve is even more user-friendly.
Last edited by Cuchulainn on March 6th, 2016, 11:00 pm, edited 1 time in total.
 
User avatar
Billy7
Posts: 262
Joined: March 30th, 2016, 2:12 pm

American options -- Reference prices

March 30th, 2016, 6:36 pm

Hello everybody,I like stressing numerical methods to their accuracy limits and have been playing with my old pricer recently, so I found you guys here. I guess I'm a little late to the party, but surely outrun used some kind of witchery to get that many digits, so I think his results don't count and he should be burned at the stake:-) But seriously, as far as standard methods go, I see that a textbook PDE method has not been represented. And it's a pity because I get much closer and faster with it to outrun's benchmarks than the other methods seem to do. So, just for reference here's what one can do with Crank-Nicolson / Brennan-Schwartz:Using NS=25,000 and NT=100,000 I getAlan case: 6.299596935MJ case: 5.929804895For both cases grid goes up to 4 x Strike. That's 7-8 significant digits correct. Execution time is about 45 secs on a budget laptop, implementation in C++. In order to squeeze out the maximum accuracy possible I applied Richardson extrapolation using NT >> NS in order to have negligible time-discretization error (compared to that due to spatial discretization) and thus be able to observe the spatial convergence on its own. NS was kept below 30,000 where convergence was smooth and perfectly quadratic. For higher NS things get worse and convergence eventually stops being monotonic. I am assuming that this is due to round-off error contamination, presumably creeping in during the LU substitutions. At some point I might test this assumption by using some higher precision library. So for "fast" (100 secs for each run) high precision I tried the following:Alan case: NS = 5000, NT =1Mil: 6.299595083 NS = 6000, NT =1Mil: 6.299595700 RE result: 6.299597102 Abs Error: 4e-9MJ case: NS = 5000, NT =1Mil: 5.929805765 NS = 6000, NT =1Mil: 5.929805495 RE result: 5.929804881 Abs Error: 5e-9For max accuracy I used NT=5Mil and an NS range from 10,000 to 32,000. Those averaged at:Alan case, RE result : 6.29959710634MJ case, RE result : 5.92980487655Finally tackling Cuchulainn's more extreme case I get 0.164996416 in 0.5 secs (that's more than 100 times faster than Tian's binomial apparently, though obviously depends on implementation and processor speed), then 0.1650017 in 1 sec, 0.1650031 in 2 sec, 0.1650044 in 20 secs and finally in about 10 min 0.16500487. The error due to the time discretization here is a lot lower than in the cases with high vol, so I used a lot less time steps in this case. Didn't try RE here. If you want me to run another case just to double check, let me know. Could also do American/Bermudan barriers or Asians if someone's interested.
Last edited by Billy7 on March 30th, 2016, 10:00 pm, edited 1 time in total.
 
User avatar
Alan
Topic Author
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

American options -- Reference prices

March 30th, 2016, 7:49 pm

QuoteOriginally posted by: Billy7Hello everybody,If you want me to run another case just to double check, let me know. Could also do American/Bermudan barriers or Asians if someone's interested.Welcome Billy,I'm not so much interested in these reference cases now.But, as long as you offer --if you can develop the early exercise boundary for the case in this thread, I'm interested.It's an unusual Bermudan call that, when exercised at time t, has the payoff of [$]\{S_t - K + \text{a put with the same strike} \, K\}[$].First, take the case of 5 years to maturity, where the put acquired upon exercise is Euro-style. Do you get the same chart as I posted on Mar 28?Second, assume the same, but the put acquired upon exercise is itself Bermudan/American.In all cases, the put that is acquired cannot be exercised on the day it is acquired, so on expiration T you can take the Bermudan call payoff to be the ordinary [$]\max(S_T - K,0)[$].What does the 5 year continuation/stopping region plot look like for that one? I used weekly expiration opportunities, but I am also interested in the case of continuous exercise.Of course, the thread author, pcaspers, will be interested also! (My post of Mar 28 has all the parameters). Fire away with any questions if the exercise payoffs are not clear.
Last edited by Alan on March 29th, 2016, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

American options -- Reference prices

March 31st, 2016, 8:21 am

Welcome to Wilmott :)This is a nice thread as a number of methods were used to arrive at the answer. Personally, I was able to test lattice and FDM and their variations. So about 6 combinations. The results from the Andersen paper look spectacular but it can be slowed down by taking high convexity/low which stops it in its tracks :) The method may not scale to 2 factors. In fairness, most methods will have difficulty here. No silver bullet.One new combination I used for early exercise was - Extrapolation in h to get h^2 to h^4 (NS = 400 gives ~ accuracy as normal NS ~ 5000).- Boost odeint with Bulirsh-Stoer adaptive method- Courant's barrier method The results were > 5 digits accurate.The CN is OK bit it has got some issues lately and probably will not easily work for nonlinear problems, in contrast to ADE and MOL.CNQuoteFor higher NS things get worse and convergence eventually stops being monotonic. I am assuming that this is due to round-off error contamination, presumably creeping in during the LU substitutions.Many methods suffer.For ADE, take fixed dt and let h -> you get spatial amplification errors, slowly but surely. The problem seems to be caused by the far field boundary bity AFAIK no one has addressed it in a study. I've done some jigory-pokery to dampen the oscillations but does not help.A discussion is here as well as in Roache's CFD book. //BTW did you ever try Extrapolation in h to get h^2 to h^4 for Crank Nicolson? It does work with normal discretization in S (constant mesh) with both ADE and Bulirch-Stoer so my hunch it will work with CN as well.
Last edited by Cuchulainn on March 30th, 2016, 10:00 pm, edited 1 time in total.
 
User avatar
Billy7
Posts: 262
Joined: March 30th, 2016, 2:12 pm

American options -- Reference prices

March 31st, 2016, 10:23 am

Hello Alan and thanks for your welcome,At first you got me scared when I saw your post before I go to bed last night, but now that I read it again it seems easy enough to do numerically (I still haven't finished my coffee mind you!). I mean all one has to do is add the put premium to the intrinsic value (the call payoff) wherever in the code the continuation value is floored to the intrinsic value right? Then it's just a question of having the put premium ready to use at each exercise time point and for all S's. If the put is European and we're lazy then we can just use BS for every point, though surely that's not the most efficient way numerically. Alternatively and if we want to cover the case of the put being Bermudan/American in itself, we can first calculate the put values at each time point of interest (the first Bermudan call's exercise dates) for all S points, store them and then do a second calculation for the first Bermudan call using the same space/time grid so that we can use the put values directly. This assumes that I have understood the option correctly: Say for the 5Y case you run, if we exercise say at t=1Y then we acquire a 4Y put, if we exercise at t=2.5Y then we acquire a 2.5Y put, if we exercise 1 week away from the first Bermudan call's maturity, we get a 1W put, etc? If that's so, then I'll try to reproduce your graph later today when I find some time.QuoteOriginally posted by: AlanWelcome Billy,I'm not so much interested in these reference cases now.But, as long as you offer --if you can develop the early exercise boundary for the case in this thread, I'm interested.Fire away with any questions if the exercise payoffs are not clear.
 
User avatar
Billy7
Posts: 262
Joined: March 30th, 2016, 2:12 pm

American options -- Reference prices

March 31st, 2016, 11:11 am

QuoteOriginally posted by: CuchulainnWelcome to Wilmott :)The CN is OK bit it has got some issues lately and probably will not easily work for nonlinear problems, in contrast to ADE and MOL.CNHi Daniel and thanks for the welcome:)I clicked on your CN link and it got me to the newest article on the magazine instead, where Paul talks about how quantitative finance has become boring! Just when I was rediscovering my enthusiasm for it... But yeah I read your article too:) Yes CN has the known problems if used without any tweaks, but in my experience a simple Rannacher step (or multiple in the case of discrete barriers), combined with discontinuity smoothing takes very good care of things. Just how good though compared to the other methods mentioned I don't know as I haven't tried them...QuoteOriginally posted by: CuchulainnOne new combination I used for early exercise was - Extrapolation in h to get h^2 to h^4 (NS = 400 gives ~ accuracy as normal NS ~ 5000)....Yes, sounds familiar, I mean one could naively think that it should give the same accuracy as NS ~ 160000, but it doesn't quite work like that. Did you check what your observed order was and if it was consistent across different sets of NSs? QuoteOriginally posted by: Cuchulainn//BTW did you ever try Extrapolation in h to get h^2 to h^4 for Crank Nicolson? It does work with normal discretization in S (constant mesh) with both ADE and Bulirch-Stoer so my hunch it will work with CN as well.Yes indeed it does work pretty well. With extrapolation in about 100 secs I get 8-9 digits of accuracy and the maximum I can get is 10-11 digits correct (as in agreeing with outrun's last benchmarks). The numbers are in my first post, maybe they were not clear before so I've now marked the RE (Richardson Extrapolation) results as bold. I only applied RE where my observed orders where 1.99-2.01, though most where more like 1.995-2.005.
Last edited by Billy7 on March 30th, 2016, 10:00 pm, edited 1 time in total.
 
User avatar
Alan
Topic Author
Posts: 2958
Joined: December 19th, 2001, 4:01 am
Location: California
Contact:

American options -- Reference prices

March 31st, 2016, 1:10 pm

QuoteOriginally posted by: Billy7Hello Alan and thanks for your welcome,At first you got me scared when I saw your post before I go to bed last night, but now that I read it again it seems easy enough to do numerically (I still haven't finished my coffee mind you!). I mean all one has to do is add the put premium to the intrinsic value (the call payoff) wherever in the code the continuation value is floored to the intrinsic value right? Then it's just a question of having the put premium ready to use at each exercise time point and for all S's. If the put is European and we're lazy then we can just use BS for every point, though surely that's not the most efficient way numerically. Alternatively and if we want to cover the case of the put being Bermudan/American in itself, we can first calculate the put values at each time point of interest (the first Bermudan call's exercise dates) for all S points, store them and then do a second calculation for the first Bermudan call using the same space/time grid so that we can use the put values directly. This assumes that I have understood the option correctly: Say for the 5Y case you run, if we exercise say at t=1Y then we acquire a 4Y put, if we exercise at t=2.5Y then we acquire a 2.5Y put, if we exercise 1 week away from the first Bermudan call's maturity, we get a 1W put, etc? If that's so, then I'll try to reproduce your graph later today when I find some time.QuoteOriginally posted by: AlanWelcome Billy,I'm not so much interested in these reference cases now.But, as long as you offer --if you can develop the early exercise boundary for the case in this thread, I'm interested.Fire away with any questions if the exercise payoffs are not clear."add the put premium to the intrinsic value (the call payoff) wherever in the code the continuation value is floored to the intrinsic value right?"Well, not quite. You add the put premium to [$]S_t-K[$] at each node to construct the exercise value. Then, the final option value at that node isthe maximum of that exercise value or the continuation value. If that maximum is indeed the exercise value, then that node is in thestopping region. I want to see a chart of where the stopping regions are for my 5-year example.
Last edited by Alan on March 30th, 2016, 10:00 pm, edited 1 time in total.
 
User avatar
Billy7
Posts: 262
Joined: March 30th, 2016, 2:12 pm

American options -- Reference prices

March 31st, 2016, 1:48 pm

QuoteOriginally posted by: Alan Originally posted by: Alan"add the put premium to the intrinsic value (the call payoff) wherever in the code the continuation value is floored to the intrinsic value right?"Well, not quite. You add the put premium to [$]S_t-K[$] at each node to construct the exercise value. Then, the final option value isthe maximum of that exercise value or the continuation value.Yes you're right, I missed the fact that S-K can actually go negative here, so not really the call payoff... I'm moving to the other thread then.
Last edited by Billy7 on March 30th, 2016, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20252
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Re: American options -- Reference prices

September 10th, 2017, 6:32 pm

Apparently we don't have a thread for this, so here is a good place to start.I am investigating convergence of some numerical methods and would appreciate it ifsomebody could confirm a 7-digit reference value under the Black-Scholes model.It is an American-style put option with [$]S_0 = K = 50[$], [$]T=1[$], [$]\sigma=0.40[$], and [$]r = 0.08[$] (no dividends).The put value is 6.299XXX; I need confirmation of the value I have for the 3 remaining digits, XXX.So as to not prejudice the answers, I'll give my value later in the thread.Thanks!
I had a look at this from another/new  "FDM perspective"

1. Use C++ MOL with Cash Karp or Bulirsch-Stoer for ODE solver.
2. Courant's quadratic penalty function for early exercise constraint.

The code is very easy to do because all the hard work is done in Boost C++. And this approach is easy to generalise, structurally to 2 factors. It took about 1-2 hours to write it as a POC.

With NS = 1800 and 300,000 evals in CK I get P = 6.2995.
With NS = 3000 I get P = 2.99569. Tried NS = 12000 but I waited all day.
It is a very good test! It's clear.