Dear Olaf,
Thank you for your suggestions.
> - Why is 'h' randomized? Even if there should be a good reason, I think this
> cannot be done inside 'line_min'. Rather, make 'h' configurable so that users
> can randomize it 'from outside'.
Since h is currently set arbitrarily, I have found for my applications
that randomizing it somewhat is helpful in optimization (where
line_min is typically called repeatedly), because it is always
possible that for a particular function the hard-coded value will not
lead to downhill movement.
Another possible fix would be, as you say, to make the step size h
configurable. I added the ability for users to provide h as an input.
> - Are you sure you don't break someones code by limiting number of evaluations
> to 30? Shouldn't this rather be made configurable, too?
I added the maximum number of evaluations as another optional input.
> - I think you should only list those changes in the comments which actually
> are made to the code in SVN now.
I fixed the description of my changes. The diff file shows the changes
in my version from the current SVN version.
> - Minor issue: The preferred style of Octave is leaving a space between
> fuction name and parantheses (e.g. sum ()) (you have deleted the space at
> some point(s)).
Modified accordingly.
Best,
Nir
13c13
< ## [a,fx,nev] = line_min (f, dx, args, narg) - Minimize f() along dx
---
> ## [a,fx,nev] = line_min (f, dx, args, narg, h, nev_max) - Minimize f() along
> dx
18c18
< ## args : list : List of argument of f
---
> ## args : cell : Arguments of f
19a20,21
> ## h : scalar : Step size to use for centered finite difference
> approximation of first and second derivatives. Default=around 1E-3 (exact
> value randomized between calls)
> ## nev_max : integer : Maximum number of function evaluations. Default=30
22,23c24,25
< ## a : scalar : Value for which f(x+a*dx) is a minimum (*)
< ## fx : scalar : Value of f(x+a*dx) at minimum (*)
---
> ## a : scalar : Value for which f(x+a*dx) is a minimum
> ## fx : scalar : Value of f(x+a*dx) at minimum
26d27
< ## (*) The notation f(x+a*dx) assumes that args == list (x).
42c43,49
< function [a,fx,nev] = line_min (f, dx, args, narg)
---
> ## 2011-11-27 Nir Krakauer
> ## * randomized the step size h
> ## * modified to limit the number of function evaluations
> ## * added both h and the number of function evaluations as optional inputs
> ## * added a check to ensure that the function value returned was never more
> than the initial value
>
> function [a,fx,nev] = line_min (f, dx, args, narg, h, nev_max)
47a55,60
> if nargin < 5 || ~isnumeric(h), h = exp(rand() - 0.5)*0.001; end
> #previously h = 1E-3 or 1E-2
>
> if nargin < 6 || ~isnumeric(nev_max), nev_max = 30; end
>
>
49c62
< h = 0.001; # Was 0.01 here
---
>
52,53c65,68
< # was 1e-4
< while (abs (velocity) > 0.000001)
---
>
> min_velocity_change = 0.000001; # was 1e-4
>
> while (abs (velocity) > min_velocity_change) && (nev < nev_max)
56a72,74
> if nev == 0
> fx0 = fx;
> end
65a84,95
>
> fx = feval (f,args{1:narg-1}, x+a*dx, args{narg+1:end});
> nev++;
> if fx >= fx0 %if no improvement, return the starting value
> a = 0;
> fx = fx0;
> end
>
> if (nev >= nev_max)
> disp('line_min: maximum number of function evaluations exceeded')
> end
>
69c99
< ## correspond to (nearly) optimal fx.
\ No newline at end of file
---
> ## correspond to (nearly) optimal fx.
## Copyright (C) 2000 Ben Sapp. All rights reserved.
##
## 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; either version 2, or (at your option) any
## later version.
##
## This 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.
## [a,fx,nev] = line_min (f, dx, args, narg, h, nev_max) - Minimize f() along dx
##
## INPUT ----------
## f : string : Name of minimized function
## dx : matrix : Direction along which f() is minimized
## args : cell : Arguments of f
## narg : integer : Position of minimized variable in args. Default=1
## h : scalar : Step size to use for centered finite difference approximation of first and second derivatives. Default=around 1E-3 (exact value randomized between calls)
## nev_max : integer : Maximum number of function evaluations. Default=30
##
## OUTPUT ---------
## a : scalar : Value for which f(x+a*dx) is a minimum
## fx : scalar : Value of f(x+a*dx) at minimum
## nev : integer : Number of function evaluations
##
## Author: Ben Sapp <bs...@lanl.gov>
## Reference: David G Luenberger's Linear and Nonlinear Programming
##
## Changelog : -----------
## 2002-01-28 Paul Kienzle
## * save two function evaluations by inlining the derivatives
## * pass through varargin{:} to the function
## 2002-03-13 Paul Kienzle
## * simplify update expression
## 2002-04-17 Etienne Grossmann <etie...@isr.ist.utl.pt>
## * Rename nrm.m to line_min.m (in order not to break dfp, which uses nrm)
## * Use list of args, suppress call to __pseudo_func__
## * Add nargs argument, assume args is a list
## * Change help text
## 2011-11-27 Nir Krakauer
## * randomized the step size h
## * modified to limit the number of function evaluations
## * added both h and the number of function evaluations as optional inputs
## * added a check to ensure that the function value returned was never more than the initial value
function [a,fx,nev] = line_min (f, dx, args, narg, h, nev_max)
velocity = 1;
acceleration = 1;
if nargin < 4, narg = 1; end
if nargin < 5 || ~isnumeric(h), h = exp(rand() - 0.5)*0.001; end
#previously h = 1E-3 or 1E-2
if nargin < 6 || ~isnumeric(nev_max), nev_max = 30; end
nev = 0;
x = args{narg};
a = 0;
min_velocity_change = 0.000001; # was 1e-4
while (abs (velocity) > min_velocity_change) && (nev < nev_max)
fx = feval (f,args{1:narg-1}, x+a*dx, args{narg+1:end});
fxph = feval (f,args{1:narg-1}, x+(a+h)*dx, args{narg+1:end});
fxmh = feval (f,args{1:narg-1}, x+(a-h)*dx, args{narg+1:end});
if nev == 0
fx0 = fx;
end
velocity = (fxph - fxmh)/(2*h);
acceleration = (fxph - 2*fx + fxmh)/(h^2);
if abs(acceleration) <= eps, acceleration = 1; end # Don't do div by zero
# Use abs(accel) to avoid problems due to
# concave function
a = a - velocity/abs(acceleration);
nev += 3;
endwhile
fx = feval (f,args{1:narg-1}, x+a*dx, args{narg+1:end});
nev++;
if fx >= fx0 %if no improvement, return the starting value
a = 0;
fx = fx0;
end
if (nev >= nev_max)
disp('line_min: maximum number of function evaluations exceeded')
end
endfunction
## Rem : Although not clear from the code, the returned a always seems to
## correspond to (nearly) optimal fx.
------------------------------------------------------------------------------
All the data continuously generated in your IT infrastructure
contains a definitive record of customers, application performance,
security threats, fraudulent activity, and more. Splunk takes this
data and makes sense of it. IT sense. And common sense.
http://p.sf.net/sfu/splunk-novd2d
_______________________________________________
Octave-dev mailing list
Octave-dev@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/octave-dev
