Assignment given 10 February 2009

This assignment was given on 10 February 2009. The work is due 17 February 2009.

NOTE: You are only responsible for question #1! Question #2 may be moved to the next assignment, and question #3 is just something for you to think about.

Question 1: Write a program that uses the Monte Carlo method to seek the minimum of a function f(x) in an interval [a,b].

For your first try, we will simply choose values of x at random in [a,b], evaluate f(x), and remember the "best" x and f(x).

For each problem, make a series of estimates for the minimizer using 100, 10,000 and 1,000,000 points.

Question 2: Write a program that uses the parabolic interpolation method to seek the minimum of a function f(x) in an interval [a,b]. We can only expect this program to work well if f(x) is convex in the interval.

Test your program on:

What happens when your program tries:

Question 3: EXTRA CREDIT HEADACHE

We are going to look at some traveling salesperson problems. To do this, we would like to have a file containing the (X,Y) coordinates of each city. If you go to a travel atlas, you will often find, instead, a table of distances between every pair of cities. Can such information be turned into a list of coordinates?

An exact answer usually does not exist - the tables often measure highway distance; they have errors; the earth is curved, and so on. However, it is possible to find an approximate answer, that is, one that minimizes the l2 norm of the errors.

Suppose you have a (short!) table D(I,J) of city distances. Can you describe a geometric procedure by which you could estimate the (relative) city positions.

This problem may remind you of the SVD, where we could have M equations in N unknowns. The SVD would give us some kind of answer in such cases. Could we use the SVD here? Unfortunately, the equations we are trying to solve are nonlinear, so the SVD won't help.

There are algorithms we can use for solving this example of a nonlinear least squares problem. MATLAB has a function called lsqnonlin which we can use.

However, in order to make use of such a program, we have to clean up the problem first. The difficulty is that the solution is not unique. If I take any set of city positions, I can shift them all by the same amount, rotate them about any angle, and even "flip" the map, and the distances will be the same. In order for MATLAB to get a good answer, we have to arbitrarily "nail down" the position of one city (to remove the shift singularity) and also pick one coordinate of another city (to remove the rotational singularity). The "flip" singularity isn't bad enough that we have to remove it.

Here is an example of a table of distances between 15 cities. 

    0  29  82  46  68  52  72  42  51  55  29  74  23  72  46  
   29   0  55  46  42  43  43  23  23  31  41  51  11  52  21  
   82  55   0  68  46  55  23  43  41  29  79  21  64  31  51  
   46  46  68   0  82  15  72  31  62  42  21  51  51  43  64  
   68  42  46  82   0  74  23  52  21  46  82  58  46  65  23  
   52  43  55  15  74   0  61  23  55  31  33  37  51  29  59  
   72  43  23  72  23  61   0  42  23  31  77  37  51  46  33  
   42  23  43  31  52  23  42  0  33   15  37  33  33  31  37  
   51  23  41  62  21  55  23  33   0  29  62  46  29  51  11  
   55  31  29  42  46  31  31  15  29   0  51  21  41  23  37  
   29  41  79  21  82  33  77  37  62  51   0  65  42  59  61  
   74  51  21  51  58  37  37  33  46  21  65   0  61  11  55  
   23  11  64  51  46  51  51  33  29  41  42  61   0  62  23  
   72  52  31  43  65  29  46  31  51  23  59  11  62   0  59  
   46  21  51  64  23  59  33  37  11  37  61  55  23  59   0

This data is available at http://www.scs.fsu.edu/~burkardt/datasets/cities/lau15_dist.txt.

Last revised on 16 February 2009.