Scribd
Upload
202 views3 pages

Backtracking Line Search

The document describes a backtracking line search algorithm. It takes in an initial point, search direction, function value, function name, directional derivative, slope modification parameter, backtracking parameter, and stopping criteria. It returns the new point, function value at the new point, and number of function calls. It attempts to find the smallest step size that satisfies an inequality condition, updating the step size by a backtracking parameter until the condition is met or the step becomes too small.

Uploaded by

mutasili
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
202 views3 pages

Backtracking Line Search

The document describes a backtracking line search algorithm. It takes in an initial point, search direction, function value, function name, directional derivative, slope modification parameter, backtracking parameter, and stopping criteria. It returns the new point, function value at the new point, and number of function calls. It attempts to find the smallest step size that satisfies an inequality condition, updating the step size by a backtracking parameter until the condition is met or the step becomes too small.

Uploaded by

mutasili
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Backtracking Linesearch

function [xn,fn,fcall] = backtrack(xc,d,fc,fnc,DDfnc,c,gamma,eps) % %GENERAL DESCRIPTION % %This function performs the basic backtracking subroutine. %The subroutine requires the following input: % xc = the current point, % d = the direction of search, % fc = the current function value, % fnc = a string variable for the function name, % DDfnc = the directional derivative of fnc at xc in the % direction d, must have DDfnc < 0, % c = the slope modification parameter in (0,1), % gamma = the backstepping parameter in (0,1), % eps = the stopping criteria for norm(xn - xc), % that is, the main algorithm stops when % norm(xn - xc) <= eps. % %The routine returns % xn = the new point, % fn = the function value at the new point, % fnc = the number of calls to fnc. % %TERMINATION CRITERIA % %The backtracking is terminated if the step to the new point %xn is so small that it triggers termination in the main algorithm, %i.e. norm(xc - xn) <= eps. In this case we return xn = xc if %fn >= fc (we have not reduced the function value); otherwise, %we return xn. % %THE MATH % %The backtracking routing attempts to find a step size for %reducing the value of the function fnc given the current point xc %and a direction d. It does this by successively trying step sizes %of the form gamma^s for s = 0,1,2... to find the smallest %value of s for which the inequality % % fnc(xc+gamma^s*d)\le fnc(xc)+c*gamma^s*DD % % is satisfied. The new point to be returned is then given % by xn = xc+gamma^s*d. % %CHECK INPUT SPECIFICATIONS % if DDfnc >= 0, error('The backtracking subroutine has been sent a direction of nondesce nt. Program has been terminated.') end if c<= 0 | c>= 1, error('The slope modification parameter c in the backtracking subroutine is not in (0,1).') end if gamma<=0 | gamma >=1, error('The backtracking parameter gamma is not in (0,1).')

end if eps <= 0, error('The termination criteria eps sent to the backtracking line search is not positive.') end % %CHECK DIMENSIONS % if size(xc)~=size(d) error('The vectors sent to backtrack are not of the same dimension.') end % % %EXECUTE THE LINE SEARCH % % xn cDDfnc fn fcall = = = = xc+d; c*DDfnc; feval(fnc,xn); 1 ;

while fn > fc+cDDfnc, d = gamma*d; cDDfnc = gamma*cDDfnc; xn = xc+d; fn = feval(fnc,xn); fcall = fcall+1; %Check if the step to xn is too small. if norm(d) <= eps, disp('linesearch step too small') if fn >= fc, xn = xc; end break end end function alphak = linesearch(f,d,x,rho,c) % function alphak = linesearch(f,d,x,rho,c) % Backtracking line search % See Algorithm 3.1 on page 37 of Nocedal and Wright % Input Parameters : % f: MATLAB file that returns function value % d: The search direction % x: previous iterate % rho :- The backtrack step between (0,1) usually 1/2 % c: parameter between 0 and 1 , usually 10^{-4} % Output : % alphak: step length calculated by algorithm % Kartik's MATLAB code (27/1/08) alphak = 1; [fk, gk] = feval(f,x); xx = x; x = x + alphak*d; fk1 = feval(f,x);

while fk1 > fk + c*alphak*(gk'*d), alphak = alphak*rho; x = xx + alphak*d; fk1 = feval(f,x); end

You might also like