function [Xm,Xval,itr,fig] = linesearch(fun,startvalues,funargs,varargin)% Global optimization by exhaustive search over the parameter space   %% >> Xopt = gridsearch(fun, startvalues)%% The most simple algorithm to determine the minimum of a cost% function with possibly multiple optima is to evaluate a grid over% the parameter space and to pick the minimum. This procedure% iteratively zooms to the candidate optimum.% The startvalues determine the limits of the grid over parameter% space. %%% Full syntax%% >> [Xopt, Yopt, Evaluations, fig] = linesearch(fun, startvalues, funargs, option1,value1,...)% %       Outputs    %         Xopt           : Optimal parameter set%         Yopt           : Criterion evaluated at Xopt%         Evaluations    : Used number of function evaluations%         fig            : handle to used figure%       Inputs    %         fun Function   : implementing the cost criterion%         startvalues    : 2*d matrix with starting values of the optimization routine%         funargs(*)     : Cell with optional extra function arguments of fun%         option (*)     : The name of the option one wants to change%         value  (*)     : The new value of the option one wants to change%% The different options and their meanings are:%%         Nofigure      : 'figure'(*) or 'nofigure'%         MaxFunEvals   : Maximum number of function evaluations (default: 20)%         GridReduction : grid reduction parameter (e.g. '1.5':%                           small reduction; `10': heavy reduction; default '2')%         TolFun        : Minimal toleration of improvement on function value (default: 0.01) %         TolX          : Minimal toleration of improvement on X value (default: 0.01)%         Grain         : number of evaluations per iteration (default: 10)% % see also:%   gridsearch, tunelssvm, crossvalidate, fminunc    % Copyright (c) 2002,  KULeuven-ESAT-SCD, License & help @ http://www.esat.kuleuven.ac.be/sista/lssvmlabdim = prod(size(startvalues));if dim~=2,  error('optimization only possible for 1-dimensional problems...');end%% defaults%nofigure='figure';eval('funargs;','funargs={};');maxFunEvals = 20;TolFun = .01;TolX = .01;grain = 10;zoomfactor=2;%% extra input arguments%for t=1:2:length(varargin),  if t+1>length(varargin),    warning('extra arguments should occur in pairs (''name'',value)');  else      if strcmpi(varargin{t},'nofigure'),        nofigure=varargin{t+1};    elseif strcmpi(varargin{t},'maxFunEvals'), maxFunEvals=varargin{t+1}    elseif strcmpi(varargin{t},'zoomfactor'),  zoomfactor=varargin{t+1}    elseif strcmpi(varargin{t},'TolFun'),      TolFun=varargin{t+1}    elseif strcmpi(varargin{t},'TolX'),        TolX=varargin{t+1}    elseif strcmpi(varargin{t},'grain'),       grain=varargin{t+1};     else  warning(['option ' varargin{t} ' unknown']);    end  endenditr =maxFunEvals;%% initiate grid%graina = -.5:1/(grain-1):.5;grid   = [min(startvalues) max(startvalues)];center = mean(grid);if nofigure(1) =='f',fig = figure; hold on; enditr = 0;Xm_old = inf;Xval_old = inf;Xm = -inf;Xval = -inf;while itr<maxFunEvals & norm(Xm-Xm_old)>TolX & norm(Xval-Xval_old)>TolFun,  Xm_old   = Xm;  Xval_old = Xval;    xtrma = [min(startvalues) max(startvalues)];  xline = xtrma(1):(xtrma(2)-xtrma(1))/(grain-1):xtrma(2);  for i = 1:length(xline),    cost(i) = feval(fun, xline(i), funargs{:});    itr = itr+1;    if nofigure(1) =='f',      plot(xline(i),cost(i),'dk');drawnow    end  end  [sc, si] = sort(cost);  Xm   = xline(si(1));   Xval = sc(1);   selected = si(1:ceil(length(si)/zoomfactor));  startvalues = [min(xline(selected)) max(xline(selected))];  end