This assignment was given on 17 February 2009. The work is due 24 February 2009.
Question 1: Last week, I asked you to write a program that generates points in an interval and records the minimum value encountered. For this first exercise, apply this program to O'Leary's function myf.m. You might write your function in the form
[ xmin, fmin ] = sampler ( f, a, b, n )
where f is a "handle" to the function, a and b are
the endpoint intervals, and n is the number of sample points.
Then print a table of n, xmin, and fmin by starting
with n=1 and repeatedly doubling until you reach n=2^15.
Turn in: a plot of the 16 values of log(n) versus fmin.
Question 2: MATLAB has a function called fminbnd which seeks to minimize a function within a given interval. The basic form of the command is
[ xmin, fmin ] = fminbnd ( f, a, b );
Use fminbnd to seek a minimum of the myf function.
In order to see how much work MATLAB did, we need to set some options. Here's how you can do this:
options = optimset ( 'fminbnd' );
options = optimset ( options, 'Display', 'iter' );
[xmin, fmin ] = fminbnd ( f, a, b, options );
Using this form of the command, MATLAB will print out the number
of steps taken.
Turn in: the number of steps taken by MATLAB, and the values of xmin and fmin.
Question 3: The raw Monte Carlo approach is expensive, but "robust" - it isn't fooled by wiggly functions. MATLAB's fminbnd is quick to find an answer, but is fooled by local minima. Now we will try to combine these two methods to get a cheap and robust approach.
Write a function of the form
[ xmin, fmin ] = hybrid ( f, a, b, n )
Your hybrid function works as follows. It carries out n steps. A step involves picking two random values c and d in the interval [a,b], then calling fminbnd to seek the minimizer in that subinterval. (You may want to make sure that c < d)! Each step computes an estimate for xmin and fmin, but hybrid must keep track of the best result, and only return that.
Use the "options" approach discussed in question 2, so that you can keep track of the number of iterations that fminbnd used on every step.
Turn in: the results of using your hybrid function with n = 1, 2, 4, 8, 16 and 32 steps. For each value of n, count the total number of steps taken by fminbnd. A line of your table should read
n total steps xmin fmin
Question 4: (Final version due in two weeks) Write a program that uses simulated annealing to minimize a function f(x) over an interval [A,B].
Use the function myf.m as the function to be minimized over the interval [0,7].
Your program should start with a random initial value x1 that is inside the interval, and store the function value f1=f(x1). Each step of your procedure considers a new value x2 as a possible replacement for x1. Generate x2 as another random value in [0,7].
Evaluate f2=f(x2). If f2 < f1, then immediately replace x1 by x2.
However, even if f2 > f1, we might choose x2! Whether or not we do this depends on the "temperature" and on how much greater f2 is than f1. The details of how to do this are outlined in the project writeup. Suggested values for the inital temperature T and the temperature reduction factor alpha
Run your program until it has made 1,000 updates to x1. Every time you update, store the values of x1 and f1 When you have reached 1,000 updates, make a plot of the x values versus the f values. This will show us how rapidly the function is decreasing.
Turn in: We will NOT turn this program in next time. Instead, I will ask each of you to demonstrate your version of this program on the myf function, and we will talk about the choices for the initial temperature T and the temperature reduction factor alpha. Then I will expect you to clean up this code and turn it in at the following class.
Here's a question that's coming soon:
Write a program that seeks a minimizer for a traveling salesperson problem, where we start with city_num cities, and are given a table city_distance of the distances between any pair of cities.
Let path be a list of the cities, which represents an itinerary for the traveling salesperson.
Write
function m = mileage ( city_num, city_distance, path )
that returns the mileage
corresponding to the given path. Since this is a round trip, you
need to remember to include the cost of returning from the last city
to the first one!
Write
function [ i, j ] = random_pair ( city_num )
which chooses two cities at random from a set of city_num cities.
How do you guarantee that the i and j are distinct?
How do you ensure that every pair of cities has an equal chance of
being picked?
Take the city distance table from the file lau15_distance.txt. Your first guess for path can be simply [ 1, 2, 3, ..., 15 ]. What is the total mileage for this path?
Try to improve your path simply by considering random pairwise switches of cities. But only change the path if the switch reduces the mileage. Consider 1,000 random switches. How many times was a possible switch actually better? How far were you able to reduce the mileage?
How can simulated annealing help us with this problem?