Optimization - Revision history

Carver: /* Animating the Nelder-Meade Method */

2009-04-21T19:37:05Z

‎Animating the Nelder-Meade Method

Carver: /* Animating the Nelder-Meade Method */

2009-04-21T19:34:29Z

‎Animating the Nelder-Meade Method

Carver: /* The Nelder-Meade Method */

2009-04-21T18:55:27Z

‎The Nelder-Meade Method

Carver: /* When you care about local optima: Nelder-Meade Modified for Simulated Annealing */

2009-04-21T18:51:20Z

‎When you care about local optima: Nelder-Meade Modified for Simulated Annealing

Carver: /* When you care about local optima: Nelder-Meade Modified for Simulated Annealing */

2009-04-21T18:50:35Z

‎When you care about local optima: Nelder-Meade Modified for Simulated Annealing

Carver: /* When you care about local optima: Nelder-Meade Modified for Simulated Annealing */

2009-04-21T18:48:27Z

‎When you care about local optima: Nelder-Meade Modified for Simulated Annealing

Carver: /* The Nelder-Meade Method */

2009-04-21T18:47:36Z

‎The Nelder-Meade Method

Carver: /* The Nelder-Meade Method */

2009-04-21T18:44:32Z

‎The Nelder-Meade Method

Carver: /* What is Optimization */

2009-04-21T18:33:18Z

‎What is Optimization

Carver: /* Homework */

2009-04-21T16:46:53Z

‎Homework

@@ Line 176: / Line 176: @@
   bestmb = Anneal('UGcost',[m0,b0],options,pdata,dev);
-Now lets try running with annealing turned off (that is, quench turned on)
+Now lets try running with annealing turned on (that is, quench turned off)
   options = AnnealSet('Display','anim');

@@ Line 176: / Line 176: @@
   bestmb = Anneal('UGcost',[m0,b0],options,pdata,dev);
-Now lets try running with annealing turned off (that is, quench turned off)
+Now lets try running with annealing turned off (that is, quench turned on)
   options = AnnealSet('Display','anim');

@@ Line 55: / Line 55: @@
 == The Nelder-Meade Method ==
-The Nelder-Meade method is appropriate if you are not worried about getting caught in local (non-global) extrema.  Nelder-Meade assumes that the only tool you have is the evaluation of the function at any values of the parameters (e.g. the kangaroos only have altimeters).  For example, it does not assume that you can evaluate the derivatives.  Much faster methods exist if you can.
+The Nelder-Meade method is appropriate if you are not worried about getting caught in local (non-global) extrema.  Nelder-Meade assumes that the only tool you have is the evaluation of the function at any values of the parameters (i.e. the kangaroos only have altimeters).  For example, it does not assume that you can evaluate the derivatives.  Much faster methods exist if you can.
 * Because we have two parameters (m and b), we start with 3 points, chosen arbitarily (3 kangaroos).  If we had n parameters, we would use n+1 points (n+ 1 kangaroos).

@@ Line 73: / Line 73: @@
 The trick here is to add noise to your evaluations of the function (i.e noisy altimeter).  What this means is you go in the wrong direction sometimes (drunk kangaroo).  The noise can get you out of a bad optimum and into a better one (that's more likely than going from a good to a bad).  The amount of noise you add depends on a quantity called "temperature" which slowly decreases to zero (kangaroo sobers up).  When it gets to zero there is no longer any noise added.  An analogous situation happens when atoms find their perfect crystaline structure (lowest energy configuration) as the temperature (and thermal noise) decreases.  If the cooling of an annealing crystal happens too rapidly (quenching) a nonoptimal semi-crystaline structure is found.
-The critical quantity is the cooling schedule.  Cool too quickly and you get bad results, too slowly and it takes forever.
+The critical quantity is the cooling schedule.  Cool too quickly and you get bad results, too slowly and it takes too long.
 == Animating the Nelder-Meade Method ==

@@ Line 71: / Line 71: @@
 == When you care about local optima: Nelder-Meade Modified for Simulated Annealing ==
-The trick here is to add noise to your evaluations of the function (i.e noisy altimeter or drunk kangaroo).  What this means is you go in the wrong direction sometimes.  That gets you out of nonglobal optima.  The amount of noise you add, depends on a quantity called "temperature" which slowly decreases to zero.  When it gets to zero there is no longer any noise added.  An analogous situation happens when atoms find their perfect crystaline structure (lowest energy configuration) as the temperature (and thermal noise) decreases.  If the cooling of an annealing crystal happens to rapidly (quenching) a nonoptimal crystaline structure is found.
+The trick here is to add noise to your evaluations of the function (i.e noisy altimeter).  What this means is you go in the wrong direction sometimes (drunk kangaroo).  The noise can get you out of a bad optimum and into a better one (that's more likely than going from a good to a bad).  The amount of noise you add depends on a quantity called "temperature" which slowly decreases to zero (kangaroo sobers up).  When it gets to zero there is no longer any noise added.  An analogous situation happens when atoms find their perfect crystaline structure (lowest energy configuration) as the temperature (and thermal noise) decreases.  If the cooling of an annealing crystal happens too rapidly (quenching) a nonoptimal semi-crystaline structure is found.
 The critical quantity is the cooling schedule.  Cool too quickly and you get bad results, too slowly and it takes forever.

@@ Line 59: / Line 59: @@
 * Because we have two parameters (m and b), we start with 3 points, chosen arbitarily (3 kangaroos).  If we had n parameters, we would use n+1 points (n+ 1 kangaroos).
-* Take the worst point (e.g. the kangaroo with the lowest likelihood), and reflect it across the line (plane, hyperplane, etc) determine by the other points.
+* Take the worst point (e.g. the kangaroo with the lowest likelihood), and "reflect" it across the line (plane, hyperplane, etc) determine by the other points.
-* If the reflected point is no longer the worst, but neither the best, repeat the above step with the new worst point.
+* If the reflected point is no longer the worst, but neither the best, repeat the above step (reflect) with the new worst point.
-* If on the other hand the reflected point is now the best, take a larger step.
+* If on the other hand the reflected point is now the best, take a larger step ("expand").
-* If on the other hand the reflected point is still the worst, take a smaller step, and if that doesn't work, shrink the triangle (move all kangaroos) on the assumption that it spans the desired optimum.
+* If on the other hand the reflected point is still the worst, take a smaller step ("contract"), and if that doesn't work, "shrink" the triangle (move all kangaroos) on the assumption that the optimum lies inside the triangle.
 And there you have it (basically, sometimes details differ).

@@ Line 3: / Line 3: @@
 Now on to today's topic.
-== What is Optimization ==
+== What is Optimization? ==
 Given a function that depends upon parameters, the optimization problem is to find the value of the parameters that optimizes (meaning, in different contexts, either minimizes or maximizes) the function.  For example, if the function is likelihood, you want to find the maximum likelihood.

@@ Line 205: / Line 205: @@
 == Homework ==
-'''Homework W.1:''' First go through today's tutorial and make sure you know how to do everything.  Generate some data and plot the LScost function.  Try to find an LScost function with more than one optimum.  (I think this is impossible so it's OK if you can't find one).  Plot (1) the data and best fitting line and (2) the cost function.  Put both plots into your PowerPoint.
+'''Homework W.1:''' First go through today's tutorial.  Generate some data and plot the LScost function.  Try to find an LScost function with more than one optimum.  (I think this is impossible so it's OK if you can't find one).  Plot (1) the data and best fitting line and (2) the cost function.  Put both plots into your PowerPoint.
 '''Homework W.2:''' Run Anneal in quench mode, with Animate.  How many function evaluations were needed? Print the final image and put into PowerPoint,
 '''Homework W.3:''' Use UG cost function to come up with a hard problem for optimization.  Run Anneal with quench and 3 cooling schedules (fast, medium, and slow) and compare results.  The results will depend on your problem.