Important note:

Here are the point values for the homework:

1a. 10 points
1b. 10 points
1c. 0 points (SKIP THIS PROBLEM.)
2. 5 points for program
10 points for design of experiment, presentation of results, and discussion
3. 0 points (SKIP THIS PROBLEM.)
4a. 5 points
4b. 10 points
(Using a lattice "as large as possible" will enable you to discuss how the work grows with the size of the lattice, but grading of the program won't depend on how large you succeed in making it.)

Known typos:

In Challenge 18.1, use fmincon, not fminbnd.

In Algorithm 18.1, p193, the definition of t is wrong. Fix it by interchanging "x" and "^x":
"t = f(^x)-f(x)"

p195, last full paragraph, "arrangment" should be "arrangement"

(10/06/06) p191: The spelling of "nonconvex" (non-convex) should be made consistent.

p191: Since our example is scalar, the Lipschitz relation could just as well have been written with absolute values rather than norms.

Question: 10/06/06. Please explain the first 3 lines on p.192

Answer: I'm using the Lipschitz inequality with x=1, so |f(1)-f(y)| <= (1) || 1-y ||, or |2-f(y)| <= |1-y|. Therefore, letting y range between -1 and 3, we see that f(y) is bounded below by 0.

Question: I'm assuming that "bounded below by 0 in the interval (-1,3)" means that zero is the lower bound of the function in this interval?

Answer: Yes.

Question: How does setting x=1 come into play here? I see that with x=1, f(1)-f(y)| <= (1) || 1-y ||, or |2-f(y)| <= |1-y|. Then plugging in both y=-1 and y=3 yields f(-1)=f(3)=0. Intuitively, I would think that this means that the lower bound of the function between (-1,1) is zero, and the lower bound of the function between (1,3) is zero. How do we conclude then that the global minimizer cannot lie here? Furthermore, what does f(4)=0 add to the problem?

Answer: You are almost there. Since we know that f(4)=0, we know that the global minimizer gives a function value of at most 0. So we are no longer interested in looking at intervals that can't give us a function value smaller than 0 and we can ignore [-1,3].

Question: L=18.1 doesn't seem to be the correct Lipschitz constant for myf.m

Answer: Yes, that is a bad mistake. The correct value is L=90.3. If you have time to plug in the correct value in your program for Challenge 18.1b, that is good; otherwise, I will check your program to see that it would run correctly if it were given the correct Lipschitz constant. (In other words, you won't lose points if you use L=18.1 instead of L=90.3.)

Question: On the dimer problem, part a:

Answer: Here are some comments I have made to students in office hours:

Grading notes (repeated from notes on Homework 1)

1. I grade problem by problem; in other words, I grade everyone's 1st problem (without looking at names), then all of the 2nd problems, etc.

To prevent mistakes in grading, please put all of your work for one problem (programs, plots, output, discussion) together.

2. In plots, make sure you label your axes and give the plot an appropriate title if there is any possibility for confusion. I often could not tell what you were plotting.

3. For full credit, your programs must have documentation.

4. I calculate late penalties problem-by-problem, so if you finish a problem on time, submit it, even if the other problems are not completed.

Question: (10-15-06) I am confused about the KRS algorithm, I followed the steps that you mentioned in the HW assignment, however couldn't figure out why we are not checking the latest dimer configuration with that of the previous recorded dimer configurations (before adding the resulting configuration to the record). If we do so, then we might count a single dimer configuration more than once.

Answer: First, remember that you take many steps in between recording a count, so it is not so likely that one repeats.

Second, we are doing random sampling, not a complete count, so it is ok if one repeats.

It is analogous to having a bag with blue and white papers in it. Suppose we pull out a paper, add one to the appropriate count, put the paper back in the bag, and repeat. We won't find out how many papers are in the bag but we will eventually be able to estimate the proportion of blue and of white.

Question: The Algorithm 18.2 KRS states that "add the dimmer with some probability ...etc" I have no idea how do we use this "Probability "? We could either add it or not add it in our code. But what should we do with this "Probability"??

Answer: It works the same way as the 1st problem on your quiz. You have computed t, and you have T, so use rand to generate a random number. If that number is less than e^{-t/T}, then add the dimer; otherwise, don't add it.

Question: For the first problem, should we compute local minimizers or just the global one?

Answer: Just the global one.

Question: I have a question about the KRS algorithm, I did not understand your answer to the question before the last one on the FAQ page of the homework. You mentioned t and T in you answer, but I did not get what do they mean here, I understand their meaning in the simulated annealing but here I could grab what do they mean in the context of this problem.

Answer: I misread, thinking the question was about Challenge 18.2 rather than Algorithm 18.2. In KRS, you can set the probability to be 1/2.