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