tests/ctags/matlab_backtracking.m

   1 % http://www.math.washington.edu/~burke/crs/516/HTML/backtrack.html\r
   2 % Backtracking Linesearch\r
   3 \r
   4 function [xn,fn,fcall] = backtrack(xc,d,fc,fnc,DDfnc,c,gamma,eps)\r
   5 %\r
   6 %GENERAL DESCRIPTION\r
   7 %\r
   8 %This function performs the basic backtracking subroutine.\r
   9 %The subroutine requires the following input:\r
  10 %       xc    = the current point,\r
  11 %       d     = the direction of search,\r
  12 %       fc    = the current function value,\r
  13 %       fnc   = a string variable for the function name,\r
  14 %       DDfnc = the directional derivative of fnc at xc in the\r
  15 %               direction d, must have  DDfnc < 0,\r
  16 %       c     = the slope modification parameter in (0,1),\r
  17 %       gamma = the backstepping parameter in (0,1),\r
  18 %       eps   = the stopping criteria for norm(xn - xc),\r
  19 %               that is, the main algorithm stops when\r
  20 %               norm(xn - xc) <= eps.\r
  21 %\r
  22 %The routine returns\r
  23 %       xn  = the new point,\r
  24 %       fn  = the function value at the new point,\r
  25 %       fnc = the number of calls to fnc.\r
  26 %\r
  27 %TERMINATION CRITERIA\r
  28 %\r
  29 %The backtracking is terminated if the step to the new point\r
  30 %xn is so small that it triggers termination in the main algorithm,\r
  31 %i.e. norm(xc - xn) <= eps. In this case we return xn = xc if\r
  32 %fn >= fc (we have not reduced the function value); otherwise,\r
  33 %we return xn.\r
  34 %\r
  35 %THE MATH\r
  36 %\r
  37 %The backtracking routing attempts to find a step size for\r
  38 %reducing the value of the function fnc given the current point xc\r
  39 %and a direction d. It does this by successively trying step sizes\r
  40 %of the form gamma^s for s = 0,1,2... to find the smallest\r
  41 %value of s for which the inequality\r
  42 %\r
  43 %       fnc(xc+gamma^s*d)\le fnc(xc)+c*gamma^s*DD\r
  44 %\r
  45 % is satisfied. The new point to be returned is then given\r
  46 % by xn = xc+gamma^s*d.\r
  47 %\r
  48 %CHECK INPUT SPECIFICATIONS\r
  49 %\r
  50 if DDfnc >= 0,\r
  51         error('The backtracking subroutine has been sent a direction of nondesce\r
  52 nt. Program has been terminated.')\r
  53 end\r
  54 if c<= 0 | c>= 1,\r
  55         error('The slope modification parameter c in the backtracking subroutine\r
  56  is not in (0,1).')\r
  57 end\r
  58 if gamma<=0 | gamma >=1,\r
  59         error('The backtracking parameter gamma is not in (0,1).')\r
  60 end\r
  61 if eps <= 0,\r
  62         error('The termination criteria eps sent to the backtracking line search\r
  63  is not positive.')\r
  64 end\r
  65 \r
  66 %\r
  67 %CHECK DIMENSIONS\r
  68 %\r
  69 if size(xc)~=size(d)\r
  70         error('The vectors sent to backtrack are not of the same dimension.')\r
  71 end\r
  72 \r
  73 %\r
  74 %\r
  75 %EXECUTE THE LINE SEARCH\r
  76 %\r
  77 %\r
  78 \r
  79 xn      =   xc+d;\r
  80 cDDfnc  =   c*DDfnc;\r
  81 fn      =   feval(fnc,xn);\r
  82 fcall   =   1 ;\r
  83 \r
  84 while fn > fc+cDDfnc,\r
  85         d       =  gamma*d;\r
  86         cDDfnc  =  gamma*cDDfnc;\r
  87         xn      =  xc+d;\r
  88         fn      =  feval(fnc,xn);\r
  89         fcall   =  fcall+1;\r
  90 \r
  91 %Check if the step to xn is too small.\r
  92         if norm(d) <= eps,\r
  93         disp('linesearch step too small')\r
  94                 if fn >= fc,\r
  95                         xn  =  xc;\r
  96                 end\r
  97                 break\r
  98         end\r
  99 end\r
 100 \r
 101 \r