Mercurial > hg > octave-lyh
annotate scripts/optimization/fminbnd.m @ 10676:f414049847d5
fminbnd.m: Remove unused persistent variable.
| author | Rik <octave@nomad.inbox5.com> |
|---|---|
| date | Tue, 01 Jun 2010 09:26:49 -0700 |
| parents | 7df8f8194c96 |
| children | fbd7843974fa |
| rev | line source |
|---|---|
| 10296 | 1 ## Copyright (C) 2008, 2009, 2010 VZLU Prague, a.s. |
| 2 ## | |
| 3 ## This file is part of Octave. | |
| 4 ## | |
| 5 ## Octave is free software; you can redistribute it and/or modify it | |
| 6 ## under the terms of the GNU General Public License as published by | |
| 7 ## the Free Software Foundation; either version 3 of the License, or (at | |
| 8 ## your option) any later version. | |
| 9 ## | |
| 10 ## Octave is distributed in the hope that it will be useful, but | |
| 11 ## WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 12 ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
| 13 ## General Public License for more details. | |
| 14 ## | |
| 15 ## You should have received a copy of the GNU General Public License | |
| 16 ## along with Octave; see the file COPYING. If not, see | |
| 17 ## <http://www.gnu.org/licenses/>. | |
| 18 ## | |
| 19 ## Author: Jaroslav Hajek <highegg@gmail.com> | |
| 20 | |
| 21 ## -*- texinfo -*- | |
| 22 ## @deftypefn {Function File} {[@var{x}, @var{fval}, @var{info}, @var{output}] =} fminbnd (@var{fun}, @var{a}, @var{b}, @var{options}) | |
| 23 ## Find a minimum point of a univariate function. @var{fun} should be a function | |
| 24 ## handle or name. @var{a}, @var{b} specify a starting interval. @var{options} is a | |
| 25 ## structure specifying additional options. Currently, @code{fminbnd} | |
| 26 ## recognizes these options: @code{"FunValCheck"}, @code{"OutputFcn"}, | |
| 27 ## @code{"TolX"}, @code{"MaxIter"}, @code{"MaxFunEvals"}. | |
| 28 ## For description of these options, see @ref{doc-optimset,,optimset}. | |
| 29 ## | |
| 30 ## On exit, the function returns @var{x}, the approximate minimum point | |
| 31 ## and @var{fval}, the function value thereof. | |
| 32 ## @var{info} is an exit flag that can have these values: | |
|
10297
ed88ea036716
improve docs of fzero/fminbnd
Jaroslav Hajek <highegg@gmail.com>
parents:
10296
diff
changeset
|
33 ## |
| 10296 | 34 ## @itemize |
| 35 ## @item 1 | |
| 36 ## The algorithm converged to a solution. | |
| 37 ## @item 0 | |
| 38 ## Maximum number of iterations or function evaluations has been exhausted. | |
| 39 ## @item -1 | |
| 40 ## The algorithm has been terminated from user output function. | |
| 41 ## @end itemize | |
| 42 ## @seealso{optimset, fzero, fminunc} | |
| 43 ## @end deftypefn | |
| 44 | |
| 45 ## This is patterned after opt/fmin.f from Netlib, which in turn is taken from | |
| 46 ## Richard Brent: Algorithms For Minimization Without Derivatives, Prentice-Hall (1973) | |
| 47 | |
| 48 ## PKG_ADD: __all_opts__ ("fminbnd"); | |
| 49 | |
| 50 function [x, fval, info, output] = fminbnd (fun, xmin, xmax, options = struct ()) | |
| 51 | |
| 52 ## Get default options if requested. | |
| 53 if (nargin == 1 && ischar (fun) && strcmp (fun, 'defaults')) | |
| 54 x = optimset ("MaxIter", Inf, "MaxFunEvals", Inf, "TolX", 1e-8, \ | |
| 55 "OutputFcn", [], "FunValCheck", "off"); | |
| 56 return; | |
| 57 endif | |
| 58 | |
| 59 if (nargin < 2 || nargin > 4) | |
| 60 print_usage (); | |
| 61 endif | |
| 62 | |
| 63 if (ischar (fun)) | |
| 64 fun = str2func (fun, "global"); | |
| 65 endif | |
| 66 | |
| 67 ## TODO | |
| 68 ## displev = optimget (options, "Display", "notify"); | |
| 69 funvalchk = strcmpi (optimget (options, "FunValCheck", "off"), "on"); | |
| 70 outfcn = optimget (options, "OutputFcn"); | |
| 71 tolx = optimget (options, "TolX", 1e-8); | |
| 72 maxiter = optimget (options, "MaxIter", Inf); | |
| 73 maxfev = optimget (options, "MaxFunEvals", Inf); | |
| 74 | |
| 75 if (funvalchk) | |
| 76 ## Replace fun with a guarded version. | |
| 77 fun = @(x) guarded_eval (fun, x); | |
| 78 endif | |
| 79 | |
| 80 ## The default exit flag if exceeded number of iterations. | |
| 81 info = 0; | |
| 82 niter = 0; | |
| 83 nfev = 0; | |
|
10392
b4e5dcf023c9
fix fminbnd termination tolerances
Jaroslav Hajek <highegg@gmail.com>
parents:
10297
diff
changeset
|
84 sqrteps = eps (class (xmin + xmax)); |
| 10296 | 85 |
| 86 c = 0.5*(3-sqrt(5)); | |
| 87 a = xmin; b = xmax; | |
| 88 v = a + c*(b-a); | |
| 89 w = x = v; | |
| 90 e = 0; | |
| 91 fv = fw = fval = fun (x); | |
| 92 nfev++; | |
| 93 | |
| 94 while (niter < maxiter && nfev < maxfev) | |
| 95 xm = 0.5*(a+b); | |
|
10392
b4e5dcf023c9
fix fminbnd termination tolerances
Jaroslav Hajek <highegg@gmail.com>
parents:
10297
diff
changeset
|
96 ## FIXME: the golden section search can actually get closer than sqrt(eps)... |
|
b4e5dcf023c9
fix fminbnd termination tolerances
Jaroslav Hajek <highegg@gmail.com>
parents:
10297
diff
changeset
|
97 ## sometimes. Sometimes not, it depends on the function. This is the strategy |
|
b4e5dcf023c9
fix fminbnd termination tolerances
Jaroslav Hajek <highegg@gmail.com>
parents:
10297
diff
changeset
|
98 ## from the Netlib code. Something yet smarter would be good. |
|
b4e5dcf023c9
fix fminbnd termination tolerances
Jaroslav Hajek <highegg@gmail.com>
parents:
10297
diff
changeset
|
99 tol = 2 * sqrteps * abs (x) + tolx / 3; |
| 10296 | 100 if (abs (x - xm) <= (2*tol - 0.5*(b-a))) |
| 101 info = 1; | |
| 102 break; | |
| 103 endif | |
| 104 | |
| 105 if (abs (e) > tol) | |
| 106 dogs = false; | |
| 107 ## Try inverse parabolic step. | |
| 108 r = (x - w)*(fval - fv); | |
| 109 q = (x - v)*(fval - fw); | |
| 110 p = (x - v)*q - (x - w)*r; | |
| 111 q = 2*(q - r); | |
| 112 p *= -sign (q); | |
| 113 q = abs (q); | |
| 114 r = e; | |
| 115 e = d; | |
| 116 | |
| 117 if (abs (p) < abs (0.5*q*r) && p > q*(a-x) && p < q*(b-x)) | |
| 118 ## The parabolic step is acceptable. | |
| 119 d = p / q; | |
| 120 u = x + d; | |
| 121 | |
| 122 ## f must not be evaluated too close to ax or bx. | |
|
10392
b4e5dcf023c9
fix fminbnd termination tolerances
Jaroslav Hajek <highegg@gmail.com>
parents:
10297
diff
changeset
|
123 if (min (u-a, b-u) < 2*tol) |
| 10296 | 124 d = tol * (sign (xm - x) + (xm == x)); |
| 125 endif | |
| 126 else | |
| 127 dogs = true; | |
| 128 endif | |
| 129 else | |
| 130 dogs = true; | |
| 131 endif | |
| 132 if (dogs) | |
| 133 ## Default to golden section step. | |
| 134 e = ifelse (x >= xm, a - x, b - x); | |
| 135 d = c * e; | |
| 136 endif | |
| 137 | |
| 138 ## f must not be evaluated too close to x. | |
| 139 u = x + max (abs (d), tol) * (sign (d) + (d == 0)); | |
| 140 | |
| 141 fu = fun (u); | |
| 142 nfev++; | |
| 143 niter++; | |
| 144 | |
| 145 ## update a, b, v, w, and x | |
| 146 | |
| 147 if (fu <= fval) | |
| 148 if (u < x) | |
| 149 b = x; | |
| 150 else | |
| 151 a = x; | |
| 152 endif | |
| 153 v = w; fv = fw; | |
| 154 w = x; fw = fval; | |
| 155 x = u; fval = fu; | |
| 156 else | |
| 157 ## The following if-statement was originally executed even if fu == fval. | |
| 158 if (u < x) | |
| 159 a = u; | |
| 160 else | |
| 161 b = u; | |
| 162 endif | |
| 163 if (fu <= fw || w == x) | |
| 164 v = w; fv = fw; | |
| 165 w = u; fw = fu; | |
| 166 elseif (fu <= fv || v == x || v == w) | |
| 167 v = u; | |
| 168 fv = fu; | |
| 169 endif | |
| 170 endif | |
| 171 | |
| 172 ## If there's an output function, use it now. | |
| 173 if (outfcn) | |
| 174 optv.funccount = nfev; | |
| 175 optv.fval = fval; | |
| 176 optv.iteration = niter; | |
| 177 if (outfcn (x, optv, "iter")) | |
| 178 info = -1; | |
| 179 break; | |
| 180 endif | |
| 181 endif | |
| 182 endwhile | |
| 183 | |
| 184 output.iterations = niter; | |
| 185 output.funcCount = nfev; | |
| 186 output.bracket = [a, b]; | |
| 187 ## FIXME: bracketf possibly unavailable. | |
| 188 | |
| 189 endfunction | |
| 190 | |
| 191 ## An assistant function that evaluates a function handle and checks for | |
| 192 ## bad results. | |
| 193 function fx = guarded_eval (fun, x) | |
| 194 fx = fun (x); | |
| 195 fx = fx(1); | |
| 196 if (! isreal (fx)) | |
| 197 error ("fminbnd:notreal", "fminbnd: non-real value encountered"); | |
| 198 elseif (isnan (fx)) | |
| 199 error ("fminbnd:isnan", "fminbnd: NaN value encountered"); | |
| 200 endif | |
| 201 endfunction | |
| 202 | |
| 203 %!shared opt0 | |
| 204 %! opt0 = optimset ("tolx", 0); | |
| 10393 | 205 %!assert (fminbnd (@cos, pi/2, 3*pi/2, opt0), pi, 10*sqrt(eps)) |
| 206 %!assert (fminbnd (@(x) (x - 1e-3)^4, -1, 1, opt0), 1e-3, 10e-3*sqrt(eps)) | |
| 207 %!assert (fminbnd (@(x) abs(x-1e7), 0, 1e10, opt0), 1e7, 10e7*sqrt(eps)) | |
| 208 %!assert (fminbnd (@(x) x^2 + sin(2*pi*x), 0.4, 1, opt0), fzero (@(x) 2*x + 2*pi*cos(2*pi*x), [0.4, 1], opt0), sqrt(eps)) |