www.pudn.com > starter.zip > ArmijoBacktrack.m, change:2011-01-04,size:3251b


function [t,x_new,f_new,g_new,funEvals,H] = ArmijoBacktrack(... 
    x,t,d,f,fr,g,gtd,c1,LS,tolX,debug,doPlot,saveHessianComp,funObj,varargin) 
% 
% Backtracking linesearch to satisfy Armijo condition 
% 
% Inputs: 
%   x: starting location 
%   t: initial step size 
%   d: descent direction 
%   f: function value at starting location 
%   fr: reference function value (usually funObj(x)) 
%   gtd: directional derivative at starting location 
%   c1: sufficient decrease parameter 
%   debug: display debugging information 
%   LS: type of interpolation 
%   tolX: minimum allowable step length 
%   doPlot: do a graphical display of interpolation 
%   funObj: objective function 
%   varargin: parameters of objective function 
% 
% Outputs: 
%   t: step length 
%   f_new: function value at x+t*d 
%   g_new: gradient value at x+t*d 
%   funEvals: number function evaluations performed by line search 
%   H: Hessian at initial guess (only computed if requested 
 
% Evaluate the Objective and Gradient at the Initial Step 
if nargout == 6 
    [f_new,g_new,H] = feval(funObj, x + t*d, varargin{:});  
else 
    [f_new,g_new] = feval(funObj, x + t*d, varargin{:});  
end 
funEvals = 1; 
 
while f_new > fr + c1*t*gtd || ~isLegal(f_new) 
 
    temp = t; 
    if LS == 0 || ~isLegal(f_new) 
        % Backtrack w/ fixed backtracking rate 
        if debug 
            fprintf('Fixed BT\n'); 
        end 
        t = 0.5*t; 
    elseif LS == 2 && isLegal(g_new) 
        % Backtracking w/ cubic interpolation w/ derivative 
        if debug 
            fprintf('Grad-Cubic BT\n'); 
        end 
        t = polyinterp([0 f gtd; t f_new g_new'*d],doPlot); 
    elseif funEvals < 2 || ~isLegal(f_prev) 
        % Backtracking w/ quadratic interpolation (no derivative at new point) 
        if debug 
            fprintf('Quad BT\n'); 
        end 
        t = polyinterp([0 f gtd; t f_new sqrt(-1)],doPlot); 
    else%if LS == 1 
        % Backtracking w/ cubic interpolation (no derivatives at new points) 
        if debug 
            fprintf('Cubic BT\n'); 
        end 
        t = polyinterp([0 f gtd; t f_new sqrt(-1); t_prev f_prev sqrt(-1)],doPlot); 
    end 
 
    % Adjust if change in t is too small/large 
 
    if t < temp*1e-3 
        if debug 
            fprintf('Interpolated Value Too Small, Adjusting\n'); 
        end 
        t = temp*1e-3; 
    elseif t > temp*0.6 
        if debug 
            fprintf('Interpolated Value Too Large, Adjusting\n'); 
        end 
        t = temp*0.6; 
    end 
 
    f_prev = f_new; 
    t_prev = temp; 
    if ~saveHessianComp && nargout == 6 
        [f_new,g_new,H] = feval(funObj, x + t*d, varargin{:});  
    else 
        [f_new,g_new] = feval(funObj, x + t*d, varargin{:});  
    end 
    funEvals = funEvals+1; 
 
    % Check whether step size has become too small 
    if sum(abs(t*d)) <= tolX 
        if debug 
            fprintf('Backtracking Line Search Failed\n'); 
        end 
        t = 0; 
        f_new = f; 
        g_new = g; 
        break; 
    end 
end 
 
% Evaluate Hessian at new point 
if nargout == 6 && funEvals > 1 && saveHessianComp 
    [f_new,g_new,H] = feval(funObj, x + t*d, varargin{:});  
    funEvals = funEvals+1; 
end 
 
x_new = x + t*d; 
 
end