//=========================================================================== // GoTools Core - SINTEF Geometry Tools Core library, version 2.0.1 // // Copyright (C) 2000-2007, 2010 SINTEF ICT, Applied Mathematics, Norway. // // This program is free software; you can redistribute it and/or // modify it under the terms of the GNU General Public License // as published by the Free Software Foundation version 2 of the License. // // This program is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., // 59 Temple Place - Suite 330, // Boston, MA 02111-1307, USA. // // Contact information: E-mail: tor.dokken@sintef.no // SINTEF ICT, Department of Applied Mathematics, // P.O. Box 124 Blindern, // 0314 Oslo, Norway. // // Other licenses are also available for this software, notably licenses // for: // - Building commercial software. // - Building software whose source code you wish to keep private. //=========================================================================== 00015 #ifndef _GENERAL_FUNCTIONMINIMIZER_H 00016 #define _GENERAL_FUNCTIONMINIMIZER_H 00017 00018 #include "GoTools/utils/Point.h" 00019 #include <vector> 00020 #include <limits> 00021 00022 namespace Go { 00023 00024 template<class Functor> class FunctionMinimizer; 00025 00026 00030 //=========================================================================== 00031 template<class Functor> 00032 void minimise_conjugated_gradient(FunctionMinimizer<Functor>& dfmin); 00033 //=========================================================================== 00034 00089 template<class Functor> 00090 class FunctionMinimizer 00091 { 00092 public: 00096 FunctionMinimizer(int num_param, const Functor& fun, 00097 const double* const seed, 00098 double tol = std::sqrt(std::numeric_limits<double>::epsilon())); 00099 00100 ~FunctionMinimizer() 00101 {} 00102 00109 double minimize(const Point& dir, bool& hit_domain_edge); 00110 00111 00126 double linminBrent(const Point& dir, 00127 const double* bracket, 00128 const double* fval_brak); 00129 00130 00132 inline double fval() const; 00133 00136 inline double fval(const Point& param) const; 00137 00140 inline void grad(Point& result) const; 00141 00144 inline void grad(const Point& param, Point& result) const; 00145 00148 inline void moveUV(const Point& dir, double multiplier); 00149 00152 bool atMin(int param_ix) const {return at_min_[param_ix];} 00153 bool atMax(int param_ix) const {return at_max_[param_ix];} 00154 00156 double getPar(int param_ix) const {return par_[param_ix];} 00157 00159 const double* getPar() const {return par_.begin();} 00160 00162 int numPars() const {return par_.size();} 00163 00164 private: 00165 const Functor fun_; 00166 00167 Point par_; 00168 std::vector<bool> at_min_; 00169 std::vector<bool> at_max_; 00170 00171 mutable bool cached_value_updated_; 00172 mutable bool cached_grad_updated_; 00173 00174 mutable double cached_value_; 00175 mutable Point cached_grad_; 00176 00177 const double minimization_tol_; 00178 std::vector<double> param_tol_; 00179 00180 static const double root_machine_precision_; 00181 static const double rel_tol_; 00182 static const double perturbation_; 00183 static const double golden_ratio_; 00184 static const double default_partition_; 00185 static const double tiny_; 00186 static const int max_iter_; 00187 00188 00189 // update at_umin_, at_umax_, at_vmin_ and at_vmax_. Should be called whenever the 00190 // current parameters ('cur_uv_') are changed. 00191 inline void checkBorder(); 00192 00193 // clear cached values. Should be called whenever the current parameters ('cur_uv_') 00194 // are changed. 00195 inline void resetCache() const; 00196 00197 // determine how far we are allowed to step from the current parameter point in a certain 00198 // direction ('dir') before going out of the valid parameter domain. 00199 double determineMaxSteplength(const Point& dir) const; 00200 00201 // Bracket the function minimum from the current parameter point along a certain 00202 // direction ('dir'). The maximum allowed steplength is given in 'max_step'. 00203 // Upon completion, two things might happen: 00204 // Possibility 1 : the function was able to bracket a minimum. The position of the 00205 // bracketing points (from current parameters, along 'dir') is 00206 // returned in 'bracket' (3 values), and the corresponding distance 00207 // function values are returned in fval_brak. The function returns 'true'. 00208 // Possibility 2 : the function hit the 'max_step' before it was able to bracket any 00209 // minimum. The function returns 'false'. 00210 bool bracketInterval(const Point& dir, 00211 const double max_step, 00212 //const double working_tolerance, 00213 double* bracket, // points to 3-array 00214 double* fval_brak); // points to 3-array 00215 00216 // given a direction 'dir', this function generates a direction 'result' that is a scaled 00217 // version of 'dir', with a possible sign change to make sure that the direction is 00218 // "downhill" (negative scalar product with function gradient). Returns 'true' on success, 00219 // and 'false' if the direction was practically perpendicular to the function gradient. 00220 bool orientDirection(const Point& dir, Point& result); 00221 00222 // Returns -1 if the scalar product of p1 and p2 is negative, +1 if the scalar product 00223 // is positive and 0 if it close to 0. In this case, 'close to 0' means that it is 00224 // impossible to judge the derivatives sign when taking into account the numerical 00225 // noise associated with the magnitude of the points' components. 00226 int scalarProductSign(const Point& p1, const Point& p2); 00227 00228 // Estimate the minimum of a parabola where two points and one tangent is known. The 00229 // two points are the current parameter point and the point obtained by marching from this 00230 // point a distance of 'dir' multiplied by 'p2'. The function value in this second point 00231 // must also be given by 'fp2'. The tangent known is the one for the current parameter 00232 // point. The abscissa for the minimum point of the parabola is returned. 00233 double parabolicEstimate(double p2, double fp2, const Point& dir); 00234 00235 // Estimate the minimum of a parabola where three points are known. If the minimum is found 00236 // to lie within the distance 'max_from_b' from b, the point is returned as 'u', and the 00237 // function returns 'true'. Otherwise, it returns 'false', and 'u' is not calculated. 00238 static bool parabolicFit(double a, double fa, 00239 double b, double fb, 00240 double c, double fc, 00241 double max_from_b, double&u); 00242 00243 // determine the smallest detectable change around the value 'c' 00244 static double numerical_tolerance(double c); 00245 00246 // Determine the numerical tolerance around a given point in a given direction 00247 static double numerical_tolerance(const Point& x, const Point& dir); 00248 00249 // Determine the numerical tolerance around a given point in a given direction, also 00250 // considering the change in function value (fx is the function at x, dfx is the derivative) 00251 static double numerical_tolerance(const Point& x, const Point& dir, 00252 const double fx, const double dfx); 00253 00254 00255 // A helper function for linminBrent. A new point has been evaluated (u, fu), and we must 00256 // update the other points used by the algorithm. 00257 static void adjustBrackets(double& a, double& fa, 00258 double& b, double& fb, 00259 double& c, double& fc, 00260 double& b2, double& fb2, 00261 double& b3, double& fb3, 00262 double u, double fu); 00263 00264 static void shift3(double& a, double& b, double& c, double d) 00265 { a = b; b = c; c = d;} 00266 static void shift2(double& a, double& b, double c) 00267 { a = b; b = c;} 00268 }; 00269 00270 }; // end namespace Go 00271 00272 #include "GoTools/utils/GeneralFunctionMinimizer_implementation.h" 00273 00274 #endif // _GENERAL_FUNCTIONMINIMIZER_H 00275
Generated on Tue Sep 21 15:44:17 2010 for GoTools Core by  doxygen 1.6.3