function [stepsize, newx, newkey, lsstats] = ...
  linesearch_adaptive(problem, x, d, f0, df0, options, storedb, key)
% Adaptive line search algorithm (step size selection) for descent methods.
%
% function [stepsize, newx, newkey, lsstats] = 
%        linesearch_adaptive(problem, x, d, f0, df0, options, storedb, key)
%
% Adaptive linesearch algorithm for descent methods, based on a simple
% backtracking method. Contrary to linesearch.m, this function is not
% invariant under rescaling of the search direction d. These two line
% search methods vary mainly in their strategy to pick the initial step
% size.
% 
% Below, the step is constructed as alpha*d, and the step size is the norm
% of that vector, thus: stepsize = alpha*norm_d. The step is executed by
% retracting the vector alpha*d from the current point x, giving newx.
%
% This line-search may create and maintain a structure called lsmem inside
% storedb.internal. This gives the linesearch the opportunity to remember
% what happened in the previous calls. This is typically used to make a
% first guess at the step size, based on previous events.
%
% Inputs/Outputs : see help for linesearch
%
% See also: steepestdescent conjugategradients linesearch

% This file is part of Manopt: www.manopt.org.
% Original author: Bamdev Mishra, Dec. 30, 2012.
% Contributors: Nicolas Boumal
% Change log:
%
%   Sept. 13, 2013 (NB) :
%       The automatic direction reversal feature was removed (it triggered
%       when df0 > 0). Direction reversal is a decision that needs to be
%       made by the solver, so it can know about it.
%
%   Nov. 7, 2013 (NB) :
%       The whole function has been recorded to mimic more closely the new
%       version of linesearch.m. The parameters are available through the
%       options structure passed to the solver and have the same names and
%       same meaning as for the base linesearch. The information is logged
%       more reliably.
%
%   April 3, 2015 (NB):
%       Works with the new StoreDB class system.
%
%   April 8, 2015 (NB):
%       Got rid of lsmem input/output: now maintained in storedb.internal.
%
%   Aug. 2, 2018 (NB):
%       Now using storedb.remove() to keep the cache lean.


    % Allow omission of the key, and even of storedb.
    if ~exist('key', 'var')
        if ~exist('storedb', 'var')
            storedb = StoreDB();
        end
        key = storedb.getNewKey();
    end

    % Backtracking default parameters. These can be overwritten in the
    % options structure which is passed to the solver.
    default_options.ls_contraction_factor = .5;
    default_options.ls_suff_decr = .5;
    default_options.ls_max_steps = 10;
    default_options.ls_initial_stepsize = 1;
    
    if ~exist('options', 'var') || isempty(options)
        options = struct();
    end
    options = mergeOptions(default_options, options);
    
    contraction_factor = options.ls_contraction_factor;
    suff_decr = options.ls_suff_decr;
    max_ls_steps = options.ls_max_steps;
    initial_stepsize = options.ls_initial_stepsize;
    
    % Compute the norm of the search direction.
    norm_d = problem.M.norm(x, d);
    
    % If this is not the first iteration, then lsmem should have been
    % filled with a suggestion for the initial step.
    if isfield(storedb.internal, 'lsmem')
        lsmem = storedb.internal.lsmem;
        if isfield(lsmem, 'init_alpha')
            % Pick initial step size based on where we were last time,
            alpha = lsmem.init_alpha;
        end
    % Otherwise, fall back to a user supplied suggestion.
    else
        alpha = initial_stepsize / norm_d;
    end

    % Make the chosen step and compute the cost there.
    newx = problem.M.retr(x, d, alpha);
    newkey = storedb.getNewKey();
    newf = getCost(problem, newx, storedb, newkey);
    cost_evaluations = 1;
    
    % Backtrack while the Armijo criterion is not satisfied
    while newf > f0 + suff_decr*alpha*df0
        
        % Reduce the step size,
        alpha = contraction_factor * alpha;
        
        % and look closer down the line.
        storedb.remove(newkey);              % we no longer need this cache
        newx = problem.M.retr(x, d, alpha);
        newkey = storedb.getNewKey();
        newf = getCost(problem, newx, storedb, newkey);
        cost_evaluations = cost_evaluations + 1;
        
        % Make sure we don't run out of budget.
        if cost_evaluations >= max_ls_steps
            break;
        end
        
    end
    
    % If we got here without obtaining a decrease, we reject the step.
    if newf > f0
        alpha = 0;
        newx = x;
        newkey = key;
        newf = f0; %#ok<NASGU>
    end
    
    % As seen outside this function, stepsize is the size of the vector we
    % retract to make the step from x to newx. Since the step is alpha*d:
    stepsize = alpha * norm_d;

    % Fill lsmem with a suggestion for what the next initial step size
    % trial should be. On average we intend to do only one extra cost
    % evaluation. Notice how the suggestion is not about stepsize but about
    % alpha. This is the reason why this line search is not invariant under
    % rescaling of the search direction d.
    switch cost_evaluations
        case 1
            % If things go very well, push your luck.
            init_alpha = 2 * alpha;
        case 2
            % If things go reasonably well, try to keep pace.
            init_alpha = alpha;
        otherwise
            % If we backtracked a lot, the new stepsize is probably quite
            % small: try to recover.
            init_alpha = 2 * alpha;
    end
    storedb.internal.lsmem.init_alpha = init_alpha;
    
    % Return some statistics also, for possible analysis.
    lsstats.costevals = cost_evaluations;
    lsstats.stepsize = stepsize;
    lsstats.alpha = alpha;
    
end
