Exercise "Minimization"

1. (6 points)

   Implement the downhill simplex method.

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

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

   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;
   3. pick the best (the lowest) 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 in the direction phi-pce 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.