Download Notebook

Summary

Harvard University
Spring 2018
Instructors: Rahul Dave
**Due Date: ** Friday, March 2nd, 2018 at 11:00am

Instructions:

• Upload your final answers in a Jupyter notebook containing all work to Canvas.

• Structure your notebook and your work to maximize readability.

Problem 1: Optimization (contd)

Suppose you are building a pricing model for laying down telecom cables over a geographical region. Your model takes as input a pair of coordinates, $(x, y)$, and contains two parameters, $\lambda_1, \lambda_2$. Given a coordinate, $(x, y)$, and model parameters, the loss in revenue corresponding to the price model at location $(x, y)$ is described by $L(x, y, \lambda_1, \lambda_2) = 0.000045\lambda_2^2 y - 0.000098\lambda_1^2 x + 0.003926\lambda_1 x\exp\left\{\left(y^2 - x^2\right)\left(\lambda_1^2 + \lambda_2^2\right)\right\}$ Read the data contained in HW3_data.csv. This is a set of coordinates configured on the curve $y^2 - x^2 = -0.1$. Given the data, find parameters $\lambda_1, \lambda_2$ that minimize the net loss over the entire dataset.

Simulated Annealing

Implement Simulated Annealing initalized at $(\lambda_1, \lambda_2) = (-5, 0)$ to minimize our loss function $L$. Compare your results to what you obtained for gradient descent and stochastic gradient descent initialized at $(\lambda_1, \lambda_2) = (-5, 0)$.

For your Simulated Annealing implementation, we suggest starting with following settings for parameters (you should further experiment with and tweak these or feel free to set your own):

• Proposal distribution: bivariate normal with covariance $[[1, 0], [0, 1]]$
• Min Length: 500
• Max Temperature: 10

You should also set your own cooling schedule.

For each temperature, plot the parameters accepted or the cost function with respect to the iteration number. What is happening to the these parameters or costs over iterations? Connect the trends you observe in the visualization to the lecture on Markov Chains.

Problem 2: A Tired Salesman

In the famous traveling salesman problem, the quality of the solution can be measured in different ways, beyond finding the shortest path. For example, the total time of travel may also be important, and may depend on the means of transportation that connect pairs of cities. Consider a random distribution of $N$ points on a plane representing the cities that must be visited by the traveling salesman. Each point is an (x,y) coordinate where both x and y are integers in the range [1, 50). Assign a value $s_i$ where $i\in [1,\dots,N]$ to each city that represents its size measured by population. Let $\forall s_i, \ s_i \in [1, 10)$. If two cities are farther away from each other than a distance threshold of 10 and both have populations greater than a population threshold of 5 assume there is a flight connection between them. In all other cases assume that our poor salesman would have to drive between cities. Flying is faster than driving by a factor of 10.

1. Use Simulated Annealing to find solutions to the traveling salesman problem for $N=100$, optimizing the travel path for the total distance travelled (but keeping track of the time of travel).

2. Now redo the problem by optimizing the the path for the total time of travel (but keeping track of the distance traveled). Are the two solutions similar or different?

3. How do your results change if the population and distance thresholds for the exisitence of a flight between two cities are altered?