[Toon-members] TooN/optimization downhill_simplex.h

[Edward Rosten]

CVSROOT:        /cvsroot/toon
Module name:    TooN
Changes by:     Edward Rosten <edrosten>        09/05/27 10:50:37

Modified files:
        optimization   : downhill_simplex.h 

Log message:
        Similar interface to Gonjugate-Gradient.

CVSWeb URLs:
http://cvs.savannah.gnu.org/viewcvs/TooN/optimization/downhill_simplex.h?cvsroot=toon&r1=1.5&r2=1.6

Patches:
Index: downhill_simplex.h
===================================================================
RCS file: /cvsroot/toon/TooN/optimization/downhill_simplex.h,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -b -r1.5 -r1.6
--- downhill_simplex.h  27 May 2009 10:13:18 -0000      1.5
+++ downhill_simplex.h  27 May 2009 10:50:32 -0000      1.6
@@ -3,6 +3,7 @@
 #include <TooN/TooN.h>
 #include <TooN/helpers.h>
 #include <algorithm>
+#include <cstdlib>
 
 namespace TooN
 {
@@ -40,21 +41,11 @@
 using namespace std;
 using namespace TooN;
 
-template<class C> double length(const C& v)
-{
-       return sqrt(v*v);
-}
-
 double sq(double x)
 {
        return x*x;
 }
 
-template<class C> double simplex_size(const C& s)
-{
-       return abs(length(s.get_simplex()[s.get_best()] - 
s.get_simplex()[s.get_worst()]) / length( s.get_simplex()[s.get_best()]));
-}
-
 double Rosenbrock(const Vector<2>& v)
 {
                return sq(1 - v[0]) + 100 * sq(v[1] - sq(v[0]));
@@ -65,9 +56,10 @@
                Vector<2> starting_point = makeVector( -1, 1);
 
                DownhillSimplex<2> dh_fixed(Rosenbrock, starting_point, 1);
-               while(simplex_size(dh_fixed) > 0.0000001)
+
+               while(dh_fixed.iterate(Rosenbrock))
                {
-                               dh_fixed.iterate(Rosenbrock);
+                       cout << dh.get_values()[dh.get_best()] << endl;
                }
 
                cout << dh_fixed.get_simplex()[dh_fixed.get_best()] << endl;
@@ -105,8 +97,10 @@
                        gamma = 0.5;
                        sigma = 0.5;
 
-                       restart(func, c, spread);
+                       epsilon = sqrt(numeric_limits<Precision>::epsilon());
+                       zero_epsilon = 1e-20;
 
+                       restart(func, c, spread);
                }
                
                /// This function sets up the simplex around, with one point at 
\e c and the remaining
@@ -127,6 +121,21 @@
                                values[i] = func(simplex[i]);
                }
                
+               ///Check to see it iteration should stop. You probably do not 
want to use
+               ///this function. See iterate() instead. This function updates 
nothing.
+               ///The termination criterion is that the simplex span 
(distancve between
+               ///the best and worst vertices) is small compared to the scale 
or 
+               ///small overall.
+               bool finished()
+               {
+                       Precision span =  norm(simplex[get_best()] - 
simplex[get_worst()]);
+                       Precision scale = norm(simplex[get_best()]);
+
+                       if(span/scale < epsilon || span < zero_epsilon)
+                               return 1;
+                       else 
+                               return 0;
+               }
                
                /// This function resets the simplex around the best current 
point.
                ///
@@ -163,7 +172,7 @@
 
                ///Perform one iteration of the downhill Simplex algorithm
                ///@param func Functor to minimize
-               template<class Function> void iterate(const Function& func)
+               template<class Function> void find_next_point(const Function& 
func)
                {
                        //Find various things:
                        // - The worst point
@@ -258,11 +267,21 @@
                                }
                }
 
+               ///Perform one iteration of the downhill Simplex algorithm, and 
return the result
+               ///of not DownhillSimplex::finished.
+               ///@param func Functor to minimize
+               template<class Function> bool iterate(const Function& func)
+               {
+                       find_next_point(func);
+                       return !finished();
+               }
 
-
-
-
-               Precision alpha, rho, gamma, sigma;
+               Precision alpha; ///< Reflected size. Defaults to 1.
+               Precision rho;   ///< Expansion ratio. Defaults to 2.
+               Precision gamma; ///< Contraction ratio. Defaults to .5.
+               Precision sigma; ///< Shrink ratio. Defaults to .5.
+               Precision epsilon;  ///< Tolerance used to determine if the 
optimization is complete. Defaults to square root of machine precision.
+               Precision zero_epsilon; ///< Additive term in tolerance to 
prevent excessive iterations if \f$x_\mathrm{optimal} = 0\f$. Known as \c ZEPS 
in numerical recipies. Defaults to 1e-20
 
        private: