minimization-one.lisp 8.41 KB
Newer Older
 liam committed Jan 21, 2008 1 2 ``````;; Univariate minimization ;; Liam Healy Tue Jan 8 2008 - 21:02 `````` Liam Healy committed Jan 24, 2009 3 ``````;; Time-stamp: <2009-01-24 14:46:49EST minimization-one.lisp> `````` lhealy committed Jul 24, 2008 4 ``````;; \$Id\$ `````` liam committed Jan 09, 2008 5 6 7 `````` (in-package :gsl) `````` 8 9 ``````;;; /usr/include/gsl/gsl_min.h `````` liam committed Jan 09, 2008 10 11 12 13 ``````;;;;**************************************************************************** ;;;; Initialization ;;;;**************************************************************************** `````` Liam Healy committed Dec 25, 2008 14 15 16 17 18 19 20 21 ``````;; The one-dimensional minimizer uses a function (no derivative) only. (defmobject one-dimensional-minimizer "gsl_min_fminimizer" ((type :pointer)) "one-dimensional minimizer" ; FDL "Make an instance of a minimizer of the given type. Optionally set to use the function and the initial search interval [lower, upper], with a guess for the location of the minimum." `````` Liam Healy committed Dec 26, 2008 22 `````` "set" ; should use set_with_values? `````` Liam Healy committed Dec 25, 2008 23 24 `````` ((function :pointer) (minimum :double) (lower :double) (upper :double))) `````` liam committed Feb 18, 2008 25 ``````(defmfun set-fminimizer-with-values `````` liam committed Jan 09, 2008 26 27 28 `````` (minimizer function x-minimum x-lower x-upper f-minimum f-lower f-upper) "gsl_min_fminimizer_set_with_values" `````` Liam Healy committed Dec 26, 2008 29 `````` (((mpointer minimizer) :pointer) (function :pointer) `````` liam committed Jan 09, 2008 30 31 `````` (x-minimum :double) (x-lower :double) (x-upper :double) (f-minimum :double) (f-lower :double) (f-upper :double)) `````` liam committed Feb 18, 2008 32 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 33 34 35 36 37 `````` "Set, or reset, an existing minimizer to use the function and the initial search interval [lower, upper], with a guess for the location of the minimum, using supplied rather than computed values of the function.") `````` Liam Healy committed Dec 26, 2008 38 ``````(defmfun name ((minimizer one-dimensional-minimizer)) `````` liam committed Jan 09, 2008 39 `````` "gsl_min_fminimizer_name" `````` Liam Healy committed Dec 26, 2008 40 41 `````` (((mpointer minimizer) :pointer)) :definition :method `````` liam committed Jan 09, 2008 42 `````` :c-return :string `````` liam committed Feb 18, 2008 43 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 44 45 46 47 48 49 `````` "The name of the minimizer.") ;;;;**************************************************************************** ;;;; Iteration ;;;;**************************************************************************** `````` Liam Healy committed Jan 03, 2009 50 ``````(defmfun iterate ((minimizer one-dimensional-minimizer)) `````` liam committed Jan 09, 2008 51 `````` "gsl_min_fminimizer_iterate" `````` Liam Healy committed Dec 26, 2008 52 `````` (((mpointer minimizer) :pointer)) `````` Liam Healy committed Jan 03, 2009 53 `````` :definition :method `````` liam committed Jan 09, 2008 54 `````` :c-return :success-continue `````` liam committed Feb 18, 2008 55 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 56 `````` "Perform a single iteration of the minimizer. The following `````` Liam Healy committed Nov 16, 2008 57 `````` errors may be signalled: 'bad-function-supplied, `````` liam committed Jan 09, 2008 58 59 60 61 62 `````` the iteration encountered a singular point where the function or its derivative evaluated to infinity or NaN, or :FAILURE, the algorithm could not improve the current best approximation or bounding interval.") `````` Liam Healy committed Jan 03, 2009 63 ``````(defmfun solution ((minimizer one-dimensional-minimizer)) `````` liam committed Jan 21, 2008 64 `````` "gsl_min_fminimizer_x_minimum" `````` Liam Healy committed Dec 26, 2008 65 `````` (((mpointer minimizer) :pointer)) `````` Liam Healy committed Jan 03, 2009 66 `````` :definition :method `````` liam committed Jan 09, 2008 67 `````` :c-return :double `````` liam committed Feb 18, 2008 68 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 69 70 `````` "The current estimate of the position of the minimum for the minimizer.") `````` liam committed Feb 18, 2008 71 ``````(defmfun fminimizer-x-lower (minimizer) `````` liam committed Jan 09, 2008 72 `````` "gsl_min_fminimizer_x_lower" `````` Liam Healy committed Dec 26, 2008 73 `````` (((mpointer minimizer) :pointer)) `````` liam committed Jan 09, 2008 74 `````` :c-return :double `````` liam committed Feb 18, 2008 75 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 76 77 `````` "The current lower bound of the interval for the minimizer.") `````` liam committed Feb 18, 2008 78 ``````(defmfun fminimizer-x-upper (minimizer) `````` liam committed Jan 09, 2008 79 `````` "gsl_min_fminimizer_x_upper" `````` Liam Healy committed Dec 26, 2008 80 `````` (((mpointer minimizer) :pointer)) `````` liam committed Jan 09, 2008 81 `````` :c-return :double `````` liam committed Feb 18, 2008 82 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 83 84 `````` "The current upper bound of the interval for the minimizer.") `````` Liam Healy committed Jan 03, 2009 85 ``````(defmfun function-value ((minimizer one-dimensional-minimizer)) `````` liam committed Jan 09, 2008 86 `````` "gsl_min_fminimizer_f_minimum" `````` Liam Healy committed Dec 26, 2008 87 `````` (((mpointer minimizer) :pointer)) `````` Liam Healy committed Jan 03, 2009 88 `````` :definition :method `````` liam committed Jan 09, 2008 89 `````` :c-return :double `````` liam committed Feb 18, 2008 90 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 91 92 93 `````` "The value of the function at the current estimate of the minimum for the minimizer.") `````` liam committed Feb 18, 2008 94 ``````(defmfun fminimizer-f-lower (minimizer) `````` liam committed Jan 09, 2008 95 `````` "gsl_min_fminimizer_f_lower" `````` Liam Healy committed Dec 26, 2008 96 `````` (((mpointer minimizer) :pointer)) `````` liam committed Jan 09, 2008 97 `````` :c-return :double `````` liam committed Feb 18, 2008 98 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 99 100 101 `````` "The value of the function at the current estimate of the lower bound for the minimizer.") `````` liam committed Feb 18, 2008 102 ``````(defmfun fminimizer-f-upper (minimizer) `````` liam committed Jan 09, 2008 103 `````` "gsl_min_fminimizer_f_upper" `````` Liam Healy committed Dec 26, 2008 104 `````` (((mpointer minimizer) :pointer)) `````` liam committed Jan 09, 2008 105 `````` :c-return :double `````` liam committed Feb 18, 2008 106 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 107 108 109 110 111 112 113 `````` "The value of the function at the current estimate of the upper bound for the minimizer.") ;;;;**************************************************************************** ;;;; Stopping parameters ;;;;**************************************************************************** `````` Liam Healy committed Dec 26, 2008 114 ``````(defmfun min-test-interval (lower upper absolute-error relative-error) `````` liam committed Jan 09, 2008 115 116 117 `````` "gsl_min_test_interval" ((lower :double) (upper :double) (absolute-error :double) (relative-error :double)) `````` liam committed Jan 21, 2008 118 `````` :c-return :success-continue ; guess that this is s-c, not s-f `````` liam committed Feb 18, 2008 119 `````` :documentation ; FDL `````` liam committed Jan 09, 2008 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 `````` "Test for the convergence of the interval [lower,upper] with absolute error and relative error specified. The test returns T if the following condition is achieved: |a - b| < epsabs + epsrel min(|a|,|b|) when the interval x = [a,b] does not include the origin. If the interval includes the origin then min(|a|,|b|) is replaced by zero (which is the minimum value of |x| over the interval). This ensures that the relative error is accurately estimated for minima close to the origin. This condition on the interval also implies that any estimate of the minimum x_m in the interval satisfies the same condition with respect to the true minimum x_m^*, |x_m - x_m^*| < epsabs + epsrel x_m^* assuming that the true minimum x_m^* is contained within the interval.") ;;;;**************************************************************************** ;;;; Minimization algorithms ;;;;**************************************************************************** `````` liam committed Feb 18, 2008 140 ``````(defmpar *golden-section-fminimizer* "gsl_min_fminimizer_goldensection" `````` liam committed Jan 09, 2008 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 `````` "The golden section algorithm is the simplest method of bracketing the minimum of a function. It is the slowest algorithm provided by the library, with linear convergence. On each iteration, the algorithm first compares the subintervals from the endpoints to the current minimum. The larger subinterval is divided in a golden section (using the famous ratio (3-sqrt 5)/2 = 0.3189660...) and the value of the function at this new point is calculated. The new value is used with the constraint f(a') > f(x') < f(b') to a select new interval containing the minimum, by discarding the least useful point. This procedure can be continued indefinitely until the interval is sufficiently small. Choosing the golden section as the bisection ratio can be shown to provide the fastest convergence for this type of algorithm.") `````` liam committed Feb 18, 2008 156 ``````(defmpar *brent-fminimizer* "gsl_min_fminimizer_brent" `````` liam committed Jan 09, 2008 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 `````` "The Brent minimization algorithm combines a parabolic interpolation with the golden section algorithm. This produces a fast algorithm which is still robust. The outline of the algorithm can be summarized as follows: on each iteration Brent's method approximates the function using an interpolating parabola through three existing points. The minimum of the parabola is taken as a guess for the minimum. If it lies within the bounds of the current interval then the interpolating point is accepted, and used to generate a smaller interval. If the interpolating point is not accepted then the algorithm falls back to an ordinary golden section step. The full details of Brent's method include some additional checks to improve convergence.") ;;;;**************************************************************************** ;;;; Example ;;;;**************************************************************************** ;;; This is the example given in Sec. 33.8. The results are different ;;; than given there. `````` Liam Healy committed Jan 24, 2009 178 ``````(defun minimization-one-fn (x) `````` liam committed Jan 09, 2008 179 180 `````` (1+ (cos x))) `````` Liam Healy committed Jan 22, 2009 181 182 ``````(defun minimization-one-example (&optional (minimizer-type *brent-fminimizer*) (print-steps t)) `````` liam committed Jan 09, 2008 183 `````` "Solving a minimum, the example given in Sec. 33.8 of the GSL manual." `````` Liam Healy committed Dec 26, 2008 184 185 186 `````` (let ((max-iter 100) (minimizer (make-one-dimensional-minimizer `````` Liam Healy committed Jan 24, 2009 187 188 189 `````` minimizer-type (make-single-function minimization-one-fn) 2.0d0 0.0d0 6.0d0))) `````` Liam Healy committed Jan 22, 2009 190 191 192 193 `````` (when print-steps (format t "iter ~6t [lower ~24tupper] ~36tmin ~44tmin err ~54tupper-lower~&")) `````` liam committed Feb 03, 2008 194 `````` (loop for iter from 0 `````` Liam Healy committed Jan 03, 2009 195 `````` for min = (solution minimizer) `````` Liam Healy committed Dec 26, 2008 196 197 `````` for lower = (fminimizer-x-lower minimizer) for upper = (fminimizer-x-upper minimizer) `````` Liam Healy committed Jan 03, 2009 198 `````` do (iterate minimizer) `````` Liam Healy committed Jan 22, 2009 199 200 201 202 203 204 `````` (when print-steps (format t "~d~6t~10,6f~18t~10,6f~28t~12,9f ~44t~10,4g ~10,4g~&" iter lower upper min (- min pi) (- upper lower))) `````` Liam Healy committed Dec 26, 2008 205 206 207 `````` while (and (< iter max-iter) ;; abs and rel error swapped in example? (not (min-test-interval lower upper 0.001d0 0.0d0))) `````` Liam Healy committed Jan 22, 2009 208 209 `````` finally (return (values iter lower upper min (- min pi) (- upper lower)))))) `````` liam committed Jan 28, 2008 210 `````` `````` Liam Healy committed Jan 22, 2009 211 212 213 ``````(save-test minimization-one (minimization-one-example *brent-fminimizer* nil) (minimization-one-example *golden-section-fminimizer* nil))``````