EE 512 - Fall 2020 Class Project
Due Friday, Dec. 4th.
Solve one of the two simulation problems below in any computational language of your
choice. Submit a report (strongly recommend either a Jupyter notebook or an R Markdown
document) with your results, including all relevant captioned figures.
1. [Options Pricing via Monte Carlo Estimation]: Generate T = 500-day sample
paths of the geometric Brownian motion (GBM) for different values of (µ, σ) using the
Euler-Maruyama simulation scheme. Recall that the GBM is the stochastic process
that satisfies the following SDE:
dSt = µ(t, St)dt + σ(t, St)dBt = µ · Stdt + σ(t, St) · StdBt
.
(a) Assume a GBM model for an underlying asset’s spot price St
. Suppose we have a
European call option for the asset St given a strike price of K. Write and test an
evaluation function that takes a GBM sample path and K as input. The output
is the payoff for the call option. Recall that European call options may only be
exercised at the expiration time T = 500 and has the value Z
Z = g(ST ) = max{ST − K, 0} .
(b) Specify 5 sets of GBM parameters (µ, σ) for 5 different assets {S
k
t }k. Use Monte
Carlo to estimate the expected value of European call options on each of these
underlying assets. And provide confidence intervals for your estimates. You may
make any simplifying assumptions (e.g. constant asset volatilities) as long as you
state your assumptions.
(c) Suppose the risk-free rate of return is r = 0.05. Modify your value estimation
process to estimate the discounted expected payoff for the option.
(d) Replace the European call option with a Asian call option monitored every 50
days. This is a path-dependent option also exercised at the expiration time T but
valued at ZAs
ZAs = gAs(ST ) = max{S¯ − K, 0}
where S¯ = Avg ({S50, S100, · · · , ST })
Use Monte Carlo to estimate the value of Asian options on the same 5 sets of
GBM-modeled assets you chose above. Compare the value of the European and
Asian call options based on the results of your experiments.
(e) Repeat the European option value estimation process using Jump-Diffusion stochastic
processes for the underlying asset prices instead of just a diffusion GBM process.
2. [Optimal City Paths]: The famous Traveling Salesman Problem (TSP) is an NP-hard
routing problem. The time to find optimal solutions to TSPs grows exponentially with
the size of the problem (number of cities). A statement of the TSP goes thus:
A salesman needs to visit each of N cities exactly once and in any order.
Each city is connected to other cities via an air transportation network. Find
a minimum length path on the network that goes through all N cities exactly
once (an optimal Hamiltonian cycle).
A TSP solution is just an ordered list of the N cities with minimum path length. We
will be exploring MCMC solutions to small and larger scale versions of the problem.
(a) Pick N = 10 2-D points in the [0, 1000] × [0, 1000] rectangle. These 2-D samples
will represent the locations of N = 10 cities.
i. Write a function to capture the objective function of the TSP problem:
ii. Start with a random path through all N cities ~c (a random permutation of the
cities), an initial high temperature T0, and a cooling schedule Tk = f(T0, k).
iii. Randomly pick any two cities in your current path. Swap them. Use the
difference between the new and old path length to
iv. calculate a Gibbs acceptance probability. Update the path accordingly.
v. Update your annealing temperature and repeat the previous city swap step.
Run the simulated annealing procedure “to convergence.”
vi. Plot the values of your objective function from each step. Plot your final TSP
city tour.
(b) Run the Simulated Annealing TSP solver you just developed for N = {40, 400, 1000}
cities. Explore the speed and convergence properties at these different problem
sizes. You might want to play with the cooling schedules.