## Thursday, April 11, 2013

### Root finding in Lord Kahl Method to Compute Heston Call Price (Part II)

In my previous post, I explored the Lord-Kahl method to compute the call option prices under the Heston model. One of the advantages of this method is to go beyond machine epsilon accuracy and be able to compute very far out of the money prices or very short maturities. The standard methods to compute the Heston price are based on a sum/difference where both sides are far from 0 and will therefore be limited to less than machine epsilon accuracy even if the integration is very precise.

However the big trick in it is to find the optimal alpha used in the integration. A suboptimal alpha will often lead to high inaccuracy, because of some strong oscillations that will appear in the integration. So the method is robust only if the root finding (for the optimal alpha) is robust.

The original paper looks the Ricatti equation for B where B is the following term in the characteristic function:
$$\phi(u) = e^{iuf+A(u,t)+B(u,t)\sigma_0}$$
The solution defines the $$\alpha_{max}$$ where the characteristic function explodes. While the Ricatti equation is complex but not complicated:
$$dB/dt = \hat{\alpha}(u)-\beta(u) B+\gamma B^2$$
I initially did not understand its role (to compute $$\alpha_{max}$$), so that, later, one can compute alpha_optimal with a good bracketing. The bracketing is particularly important to use a decent solver, like the Brent solver. Otherwise, one is left with, mostly, Newton's method. It turns out that I explored a reduced function, which is quite simpler than the Ricatti and seems to work in all the cases I have found/tried: solve $$1/B = 0$$
If B explodes, $$\phi$$ will explode. The trick, like when solving the Ricatti equation, is to have either a good starting point (for Newton) or, better, a bracketing. It turns out that Lord and Kahl give a bracketing for $$1/B$$, even if they don't present it like this: their $$\tau_{D+}$$ on page 10 for the lower bracket, and $$\tau_+$$ for the upper bracket. $$\tau_+$$ will make $$1/B$$ explode, exactly. One could also find the next periods by adding $$4\pi/t$$ instead of $$2\pi/t$$ like they do to move from $$\tau_{D+}$$ to $$\tau_+$$. But this does not have much interest as we don't want to go past the first explosion.

It's quite interesting to see that my simple approach is actually closely related to the more involved Ricatti approach. The starting point could be the same. Although it is much more robust to just use Brent solver on the bracketed max. I actually believe that the Ricatti equation explodes at the same points, except, maybe for some rare combination of Heston parameters.

From a coding perspective, I found that Apache commons maths was a decent library to do complex calculus or solve/minimize functions. The complex part was better than some in-house implementation: for example the square root was more precise in commons maths, and the solvers are robust. It even made me think that it is often a mistake to reinvent to wheel. It's good to choose the best implementations/algorithms as possible. But reinventing a Brent solver??? a linear interpolator??? Also the commons maths library imposes a good structure. In house stuff tends to be messy (not real interfaces, or many different ones). I believe the right approach is to use and embrace/extends Apache commons maths. If some algorithms are badly coded/not performing well, then write your own using the same kind of interfaces as commons maths (or some other good maths library).

The next part of this series on Lord-Kahl method is here.