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

  1. 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’

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s