Swing Option: Linear vs. Dynamic Programming I

Finding the optimal exercise strategy for a swing option is a challenging task, even for simple payoff structures. In the absence of complicated time-integral constraints dynamic programming can be used to calculate the optimal exercise strategy. Linear programming applied ex post over the whole spot price path is capable to deal with more complicated time-integral constraints but the algorithm leads only to an upper bound of the real option price [1].

A basic payoff structure is e.g.: On the exercise dates $t_i, i\in\{1..N\}$ the decision variables $\beta_i\in\{0,1\}$ indicate whether to exercise $(\beta_i=1)$ or not to exercise $(\beta_i=0)$ the option at a given point $t_i$ in time. Payoff is either $\beta_i (P(t_i)-K)$ for a call or $\beta_i(K-P(t_i))$ for a put option. Here $K$ is the strike price and $P(t_i)$ is the spot price . The number of exercise opportunities is constraint by

$E_{min} \le \sum_{i=1}^N \beta_i \le E_{max}$ .

The price of a swing call option is then given by

$\text{npv} = \max_{\beta}\mathbb{E}^\mathbb{Q} \left[ \sum_{i=1}^N \beta_i \left( P(t_i) - K\right)e^{rt_i}\right]$

Let the dynamics of the spot price in the risk neutral measure $\mathbb{Q}$ be given by the Kluge model [2]:

$\begin{array}{rcl} S &=& exp(X_t + Y_t) \\ dX_t &=& \alpha(\mu(t)-X_t)dt + \sigma dW_t \\ dY_t &=& -\beta Y_{t-}dt + J_tdN_t \\ \omega(J)&=& \eta_u e^{-\eta_u J} \end{array}$

This model is composed of an Ornstein-Uhlenbeck (OU) process $X_t$ , a deterministic period function $\mu(t)$ characterizing the seasonality and a mean reverting process $Y_t$ with jumps to incorporate spikes. $N_t$ is a Poisson process with jump intensity $\lambda$ and the jump size itself is exponentially distributed. The random variables $W_t, N_t$ and $J_t$ are independent. The Monte-Carlo path simulation will be built on top of standard components for an OU process and a Poisson jump-diffusion process [3]. The dynamic programming approach can either be carried out using least squares Monte-Carlo ansatz (Longstaff Schwartz algorithm) or using finite difference methods. We prefer finite difference methods to avoid e.g. the problem of choosing an appropriate basis function set. The Feynman-Kac theorem leads to the corresponding partial integro differential equation (PIDE):

$\begin{array}{rcl} rV =&&\frac{\partial V}{\partial t}+\frac{\sigma^2}{2}\frac{\partial^2 V}{\partial x^2} + \alpha(\mu(t)-x)\frac{\partial V}{\partial x}-\beta y\frac{\partial V}{\partial y}\\&+&\lambda \int_\mathbb{R} \left( V(x,y+z,t)-V(x,y,t)\right )\omega(z) dz \end{array}$

A Gauss-Laguerre quadrature is appropriate to calculate the integral part of the PIDE. Beside this two-dimensional PIDE an additional dimension is needed to keep track of the already consumed exercise rights. The three-dimensional formulation together with Bellman’s principle of optimality transforms the global optimization problem into a local optimization problem.

Target of the linear programming approach is the upper bound

$\text{npv} \le \mathbb{E}^\mathbb{Q}\left[ \max_{\beta} \sum_{i=1}^N \beta_i\left(P(t_i) - K \right) e^{rt_i}\right]$

The linear programming algorithm will calculate the optimal exercise strategy $\left\{ \beta \right\}$ on each Monte-Carlo path separately (perfect foresight) with respect to the given constraints. For this basic type of swing option linear programming is sort of over-engineering because a simple sort algorithm will also reproduce the optimal exercise strategy. But introducing linear programming and mixed integer programming now will enable us later on to deal with more complicated time-integral constraints. Libraries for this task are freely available, e.g. the GNU Linear Programming Kit.

The test parameterization of the model is

$\alpha=1.0, \sigma=200\%, \mu(t)=3.0,\beta=5.0, \eta=2.0, \lambda=1.0, X_0=3.0, Y_0=0.0$ ,

the example swing call option has maturity of one year, strike price is equal 40, one exercise opportunity per month and the minimum number of exercise rights is equal to the maximum number of exercise rights, $E_{min} = E_{max}$ . Interest rates are at $r=10\%$ .

As the diagram above shows for this set-up the upper bound for the swing option price calculated using linear programming differs significantly from the correct price calculated based on dynamic programming on a lattice. For twelve exercise rights both algorithms have to provide the same results because the constraint forces to always exercise on each exercise date. Next to come is to rerun the simulation with a more realistic forward curve and process parameters.

The code is available here. It depends on the GNU Linear Programming Kit, the Boost Thread library for parallelization and at the time of writing on the latest QuantLib version from the SVN trunk. If you want to generate the plot directly out of the C++ program you also need R, RCPP and RInside.

[1] M. Burger, B. Graeber, G. Schindlmayr, Managing Energy Risk, ISDN 978-0-470-ß2962-6

[2] T. Kluge, Pricing Swing Options and other Electricity Derivatives

[3] P. Glasserman, Monte Carlo Methods in Financial Engineering. ISBN-0387004513

4 thoughts on “Swing Option: Linear vs. Dynamic Programming I”

Dennis Zhang says:

August 31, 2011 at 3:55 am

Hi I am trying to replicate the Swing Option code in this post. However, I got the following error message and I wonder if you know why? I for your vanillaswingoption.hpp and vanillarswingoption.cpp from the link of SVN Trunk

1>c:\quantlib\quantlib-1.1\ql\instruments\vanillaswingoption.hpp(5) : error C2059: syntax error : ‘c:\quantlib\quantlib-1.1\ql\instruments\vanillaswingoption.hpp(6) : error C2653: ‘ViewVC’ : is not a class or namespace name
1>c:\quantlib\quantlib-1.1\ql\instruments\vanillaswingoption.hpp(7) : error C2059: syntax error : ‘c:\quantlib\quantlib-1.1\ql\instruments\vanillaswingoption.hpp(18) : fatal error C1021: invalid preprocessor command ‘doc3’

- hpcquantlib says:
  
  August 31, 2011 at 2:15 pm
  
  Hi
  
  Can you please send me the source files vanillaswingoption.hpp and vanillaswingoption.cpp as you have received them from the SVN trunk. (EMail: klaus@spanderen.de). Thanks
  
Swing and Quantlib on a Mac « says:

February 3, 2013 at 6:48 am

[…] will test the result by building the chart generated from the code found in the blog Linear vs Dynamic Programming I. An excellent learning place for options and all things […]

Gas Storage Fair Price | online Calculator says:

June 4, 2017 at 7:08 pm

[…] a great job evaluating the precision of the perfect foresight. Though it can be surprisingly good, another case shows that it should be considered with caution, namely as the highest upper bound of the fair […]

HPC-QuantLib

Swing Option: Linear vs. Dynamic Programming I

4 thoughts on “Swing Option: Linear vs. Dynamic Programming I”

Leave a Reply Cancel reply

Share this:

Like this:

Related

4 thoughts on “Swing Option: Linear vs. Dynamic Programming I”

Leave a Reply Cancel reply