Exercise "Minimization"

1. (6 points)

   Implement the downhill simplex method.

   Find the minima of the Rosenbrock's valley function, f(x,y)=(1-x)2+100(y-x2)2.

   Find the minima of the Himmelblau's function, f(x,y)=(x2+y-11)2+(x+y2-7)2.

   Compare the effectiveness (that is, the number of evaluations of the objective function) of the simplex method and the root-finding Newton's methods from the root-finding exercise.

   Make some other interesting examples.

2. (3 points)

   Implement the following strategy of expansion after a successful reflection in the downhill simplex method:

   1. try "expansion" against the old centroid;
   2. try "expansion" against the new centroid (the one which comes up after accepting reflection);
   3. pick the best of the two;

   Find out whether this brings any dividents as compared to the usual strategy.

3. (1 point)

   Try the following variant of the algorithm: instead of usual 1D reflection/expansion/contraction perform a line-search of your choice in the direction phi-pce. For example, starting, say, with expansion factor 3 (or, perhaps, even 4) and then backtracking (as in root-finding methods).

4. (0 points)

   Suppose you are already at the "end-game" parabolic local minimum. Try improve the rate of convergence of the downhill simplex method.