%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Part of the replication package for the paper
%   "Marginal Effects for Probit and Tobit with Endogeneity"
%   by Kirill S. Evdokimov, Ilze Kalnina, and Andrei Zeleneev.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [x,fval,exitflag] = fn_grid_fminbnd(fn, lb0, ub0, TolX, n_grid)
% [x,fval,exitflag] = fn_grid_fminbnd(fn, lb0, ub0, TolX, n_grid)
% Robustified version of fminbnd for dealing with non U-shaped functions  
% Uses a grid to find the initial point, and then runs fminbnd around it.
  if nargin<4; TolX=1e-4; end
  if nargin<5; n_grid=11; end
  assert(n_grid>=3);
  assert(TolX>0 && TolX<0.1);
  
  lb = min(lb0,ub0);
  ub = max(lb0,ub0);
  if ub-lb<=2*TolX
    x = (ub+lb)/2; % the middle point is a correct output x
    fval = fn(x);
    exitflag = 1;
    return
  end

  eps_bnd = min(1e-7, 0.1*TolX); % avoid evaluating exactly at lb and ub
  arr_xs = lb + eps_bnd + (ub-lb-2*eps_bnd)*(0:n_grid-1)'/(n_grid-1);
  
  arr_fvals = arrayfun(fn, arr_xs);
  [~, i_min] = min(arr_fvals);
  i0 = max(1,i_min-1);
  i1 = min(length(arr_xs),i_min+1);
  
  [x_opt,fval_opt,exitflag] = fminbnd(fn, arr_xs(i0), arr_xs(i1), optimset("TolX", TolX/2));
  arr_fvals = [arr_fvals; fval_opt];
  arr_xs = [arr_xs; x_opt];
  
  [~,i_min] = min(arr_fvals); % just in case, checking that x_opt is indeed the minimizer
  x = arr_xs(i_min);
  fval = arr_fvals(i_min);
end
