EE 512编程讲解、辅导c/c++程序设计、Java，Python语言编程讲解

日期：2020-11-18 11:37

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.