Class for performing optimization with Conjugate Gradient, where only the derivatives are available. More...
#include <conjugate_gradient_only.h>
Public Member Functions | |
template<class Deriv > | |
ConjugateGradientOnly (const TooN::Vector< Size > &start, const Deriv &deriv, const TooN::Vector< Size > &d) | |
template<int S, class P , class B > | |
void | init (const TooN::Vector< Size > &start, const TooN::Vector< S, P, B > &deriv) |
template<class Deriv > | |
void | init (const TooN::Vector< Size > &start, const Deriv &deriv) |
template<class Deriv > | |
void | find_next_point (const Deriv &deriv) |
bool | finished () |
void | update_vectors_PR (const TooN::Vector< Size > &grad) |
template<class Deriv > | |
bool | iterate (const Deriv &deriv) |
Public Attributes | |
const int | size |
TooN::Vector< Size > | g |
TooN::Vector< Size > | new_g |
TooN::Vector< Size > | h |
TooN::Vector< Size > | minus_h |
TooN::Vector< Size > | old_g |
TooN::Vector< Size > | old_h |
TooN::Vector< Size > | x |
TooN::Vector< Size > | old_x |
Precision | tolerance |
int | max_iterations |
TooN::Vector< Size > | delta_max |
Precision | linesearch_tolerance |
Precision | linesearch_epsilon |
int | iterations |
Class for performing optimization with Conjugate Gradient, where only the derivatives are available.
Definition at line 28 of file conjugate_gradient_only.h.
ConjugateGradientOnly< Size, Precision >::ConjugateGradientOnly | ( | const TooN::Vector< Size > & | start, | |
const Deriv & | deriv, | |||
const TooN::Vector< Size > & | d | |||
) | [inline] |
Initialize the ConjugateGradient class with sensible values.
start | Starting point, x | |
deriv | Function to compute ![]() | |
d | Maximum allowed movement (delta) in any dimension |
Definition at line 55 of file conjugate_gradient_only.h.
References ConjugateGradientOnly< Size, Precision >::init().
void ConjugateGradientOnly< Size, Precision >::init | ( | const TooN::Vector< Size > & | start, | |
const TooN::Vector< S, P, B > & | deriv | |||
) | [inline] |
Initialise given a starting point and the derivative at the starting point.
start | starting point | |
deriv | derivative at starting point |
Definition at line 65 of file conjugate_gradient_only.h.
References ConjugateGradientOnly< Size, Precision >::g, ConjugateGradientOnly< Size, Precision >::h, ConjugateGradientOnly< Size, Precision >::iterations, ConjugateGradientOnly< Size, Precision >::linesearch_epsilon, ConjugateGradientOnly< Size, Precision >::linesearch_tolerance, ConjugateGradientOnly< Size, Precision >::max_iterations, ConjugateGradientOnly< Size, Precision >::minus_h, ConjugateGradientOnly< Size, Precision >::size, ConjugateGradientOnly< Size, Precision >::tolerance, and ConjugateGradientOnly< Size, Precision >::x.
Referenced by ConjugateGradientOnly< Size, Precision >::ConjugateGradientOnly(), fit_spots_historic(), ConjugateGradientOnly< Size, Precision >::init(), and FitSpots::try_modifying_model().
00066 { 00067 00068 using std::numeric_limits; 00069 x = start; 00070 00071 //Start with the conjugate direction aligned with 00072 //the gradient 00073 g = deriv; 00074 h = g; 00075 minus_h=-h; 00076 00077 tolerance = sqrt(numeric_limits<Precision>::epsilon()); 00078 max_iterations = size * 100; 00079 00080 00081 linesearch_tolerance = sqrt(numeric_limits<Precision>::epsilon()); 00082 linesearch_epsilon = 1e-20; 00083 00084 iterations=0; 00085 }
void ConjugateGradientOnly< Size, Precision >::init | ( | const TooN::Vector< Size > & | start, | |
const Deriv & | deriv | |||
) | [inline] |
Initialise given a starting point and a functor for computing derivatives.
start | starting point | |
deriv | derivative computing functor |
Definition at line 90 of file conjugate_gradient_only.h.
References ConjugateGradientOnly< Size, Precision >::init().
00091 { 00092 init(start, deriv(start)); 00093 }
void ConjugateGradientOnly< Size, Precision >::find_next_point | ( | const Deriv & | deriv | ) | [inline] |
Perform a linesearch from the current point (x) along the current conjugate vector (h).
The linesearch does not make use of values. You probably do not want to call this function directly. See iterate() instead. This function updates:
deriv | Functor returning the derivative value at a given point. |
Definition at line 106 of file conjugate_gradient_only.h.
References ConjugateGradientOnly< Size, Precision >::delta_max, ConjugateGradientOnly< Size, Precision >::g, ConjugateGradientOnly< Size, Precision >::h, ConjugateGradientOnly< Size, Precision >::iterations, ConjugateGradientOnly< Size, Precision >::linesearch_epsilon, ConjugateGradientOnly< Size, Precision >::linesearch_tolerance, ConjugateGradientOnly< Size, Precision >::minus_h, ConjugateGradientOnly< Size, Precision >::new_g, and ConjugateGradientOnly< Size, Precision >::x.
Referenced by ConjugateGradientOnly< Size, Precision >::iterate().
00107 { 00108 iterations++; 00109 using std::abs; 00110 //Conjugate direction is -h 00111 //grad.-h is (should be negative) 00112 00113 //We should have that f1 is negative. 00114 new_g = g; 00115 double f1 = g * minus_h; 00116 //If f1 is positive, then the conjugate vector points agains the 00117 //newly computed gradient. This can only happen if there is an error 00118 //in the computation of the gradient (eg we're using a stochastic method) 00119 //not much to do here except to stop. 00120 if(f1 > 0) 00121 { 00122 //Return, so try to search in a direction conjugate to the current one. 00123 return; 00124 } 00125 //What step size takes us up to the maximum length 00126 Precision max_step = HUGE_VAL; 00127 for(int i=0; i < minus_h.size(); i++) 00128 max_step = min(max_step, abs(delta_max[i]/h[i])); 00129 00130 //Taking the maximum step size may result in NaNs. 00131 //Try the maximum step size, and seccessively reduce it. 00132 Precision full_max_step = max_step; 00133 00134 for(;;) 00135 { 00136 new_g = deriv(x + max_step * minus_h); 00137 00138 if(!TooN::isnan(new_g)) 00139 { 00140 // cout << "new_g is NAN free :)\n"; 00141 break; 00142 } 00143 else 00144 max_step /=2; 00145 00146 //If the step size gets too small then 00147 //return as we can't really do anything 00148 if(max_step < full_max_step * linesearch_tolerance) 00149 return; 00150 } 00151 00152 double f2 = new_g * minus_h; 00153 00154 00155 //If f2 hasn't gone negative, then the largest allowed step is not large enough. 00156 //So, take a full step, then keep going in the same direction 00157 if(f2 < 0) 00158 { 00159 //Take a full step 00160 x += max_step * minus_h; 00161 return; 00162 } 00163 00164 //Now, x1 and x2 bracket a root, and find the root using bisection 00165 //x1 and x2 are represented by the scalars s1 and s2 00166 double s1 = 0; 00167 double s2 = max_step; 00168 double s_new = max_step; 00169 00170 int updates[2] = {0,0}; 00171 00172 while(abs(s1 - s2) > abs(s1 + s2) * linesearch_tolerance + linesearch_epsilon) 00173 { 00174 if(updates[0] != updates[1] && updates[0] != 0) 00175 { 00176 00177 //Compute the new point using false position. 00178 s_new = s1 + f1 * (s2 - s1)/(f1 - f2); 00179 new_g = deriv(x + s_new * minus_h); 00180 double f_new = new_g*minus_h; 00181 00182 updates[0] = updates[1]; 00183 00184 if(f_new == 0) 00185 break; 00186 00187 if(f_new < 0) 00188 { 00189 s1 = s_new; 00190 f1 = f_new; 00191 updates[1] = 1; 00192 } 00193 else 00194 { 00195 s2 = s_new; 00196 f2 = f_new; 00197 updates[1] = 2; 00198 } 00199 } 00200 else 00201 { 00202 //Compute the new point 00203 00204 s_new = (s1 + s2) / 2; 00205 00206 new_g = deriv(x + s_new * minus_h); 00207 double f_new = new_g*minus_h; 00208 00209 if(f_new < 0) 00210 { 00211 s1 = s_new; 00212 f1 = f_new; 00213 updates[0] = 1; 00214 } 00215 else 00216 { 00217 s2 = s_new; 00218 f2 = f_new; 00219 updates[0] = 2; 00220 } 00221 00222 } 00223 00224 } 00225 00226 //Update the current position and value 00227 //The most recent gradient computation is at s_new 00228 x += minus_h * s_new; 00229 00230 }
bool ConjugateGradientOnly< Size, Precision >::finished | ( | ) | [inline] |
Check to see it iteration should stop.
You probably do not want to use this function. See iterate() instead. This function updates nothing.
Definition at line 234 of file conjugate_gradient_only.h.
References ConjugateGradientOnly< Size, Precision >::iterations, ConjugateGradientOnly< Size, Precision >::max_iterations, ConjugateGradientOnly< Size, Precision >::new_g, and ConjugateGradientOnly< Size, Precision >::tolerance.
Referenced by ConjugateGradientOnly< Size, Precision >::iterate().
00235 { 00236 using std::abs; 00237 return iterations > max_iterations || norm_inf(new_g) < tolerance; 00238 }
void ConjugateGradientOnly< Size, Precision >::update_vectors_PR | ( | const TooN::Vector< Size > & | grad | ) | [inline] |
After an iteration, update the gradient and conjugate using the Polak-Ribiere equations.
This function updates:
grad | The derivatives of the function at x |
Definition at line 248 of file conjugate_gradient_only.h.
References ConjugateGradientOnly< Size, Precision >::g, ConjugateGradientOnly< Size, Precision >::h, ConjugateGradientOnly< Size, Precision >::minus_h, ConjugateGradientOnly< Size, Precision >::old_g, and ConjugateGradientOnly< Size, Precision >::old_h.
Referenced by ConjugateGradientOnly< Size, Precision >::iterate().
bool ConjugateGradientOnly< Size, Precision >::iterate | ( | const Deriv & | deriv | ) | [inline] |
Use this function to iterate over the optimization.
Note that after iterate returns false, g, h, old_g and old_h will not have been updated. This function updates:
deriv | Functor to compute derivatives at the specified point. |
Definition at line 275 of file conjugate_gradient_only.h.
References ConjugateGradientOnly< Size, Precision >::find_next_point(), ConjugateGradientOnly< Size, Precision >::finished(), ConjugateGradientOnly< Size, Precision >::new_g, and ConjugateGradientOnly< Size, Precision >::update_vectors_PR().
Referenced by fit_spots_historic(), FitSpots::optimize_each_spot_in_turn_for_several_passes(), and FitSpots::try_modifying_model().
00276 { 00277 find_next_point(deriv); 00278 00279 if(!finished()) 00280 { 00281 update_vectors_PR(new_g); 00282 return 1; 00283 } 00284 else 00285 return 0; 00286 }
const int ConjugateGradientOnly< Size, Precision >::size |
Dimensionality of the space.
Definition at line 30 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::init().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::g |
Gradient vector used by the next call to iterate().
Definition at line 31 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), ConjugateGradientOnly< Size, Precision >::init(), and ConjugateGradientOnly< Size, Precision >::update_vectors_PR().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::new_g |
The new gradient set at the end of iterate().
Definition at line 32 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), ConjugateGradientOnly< Size, Precision >::finished(), and ConjugateGradientOnly< Size, Precision >::iterate().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::h |
Conjugate vector to be searched along in the next call to iterate().
Definition at line 33 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), ConjugateGradientOnly< Size, Precision >::init(), and ConjugateGradientOnly< Size, Precision >::update_vectors_PR().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::minus_h |
negative of h as this is required to be passed into a function which uses references (so can't be temporary)
Definition at line 34 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), ConjugateGradientOnly< Size, Precision >::init(), and ConjugateGradientOnly< Size, Precision >::update_vectors_PR().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::old_g |
Gradient vector used to compute $h$ in the last call to iterate().
Definition at line 35 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::update_vectors_PR().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::old_h |
Conjugate vector searched along in the last call to iterate().
Definition at line 36 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::update_vectors_PR().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::x |
Current position (best known point).
Definition at line 37 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), fit_spots_historic(), ConjugateGradientOnly< Size, Precision >::init(), FitSpots::optimize_each_spot_in_turn_for_several_passes(), and FitSpots::try_modifying_model().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::old_x |
Previous point (not set at construction).
Definition at line 38 of file conjugate_gradient_only.h.
Precision ConjugateGradientOnly< Size, Precision >::tolerance |
Tolerance used to determine if the optimization is complete. Defaults to square root of machine precision.
Definition at line 40 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::finished(), and ConjugateGradientOnly< Size, Precision >::init().
int ConjugateGradientOnly< Size, Precision >::max_iterations |
Maximum number of iterations. Defaults to size
.
Definition at line 41 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::finished(), fit_spots_historic(), ConjugateGradientOnly< Size, Precision >::init(), and FitSpots::optimize_each_spot_in_turn_for_several_passes().
TooN::Vector<Size> ConjugateGradientOnly< Size, Precision >::delta_max |
Maximum distance to travel along all axes in line search.
Definition at line 43 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point().
Precision ConjugateGradientOnly< Size, Precision >::linesearch_tolerance |
Tolerance used to determine if the linesearch is complete. Defaults to square root of machine precision.
Definition at line 45 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), and ConjugateGradientOnly< Size, Precision >::init().
Precision ConjugateGradientOnly< Size, Precision >::linesearch_epsilon |
Additive term in tolerance to prevent excessive iterations if . Known as
ZEPS
in numerical recipies. Defaults to 1e-20.
Definition at line 46 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), and ConjugateGradientOnly< Size, Precision >::init().
int ConjugateGradientOnly< Size, Precision >::iterations |
Number of iterations performed.
Definition at line 49 of file conjugate_gradient_only.h.
Referenced by ConjugateGradientOnly< Size, Precision >::find_next_point(), ConjugateGradientOnly< Size, Precision >::finished(), and ConjugateGradientOnly< Size, Precision >::init().