function [stepsize, newx, newkey, lsstats] = ...
           linesearch_decrease(problem, x, d, f0, ~, options, storedb, key)
% Backtracking line-search aiming merely for a decrease in cost value.
%
% function [stepsize, newx, newkey, lsstats] = 
%        linesearch_decrease(problem, x, d, f0, df0, options, storedb, key)
%
% Line-search algorithm based on a simple backtracking method. The search
% direction provided has to be a descent direction, but needs not be a
% first-order descent, i.e.: this line-search can be used even if x is a
% critical point, as long as the cost function is strictly decreasing
% along the direction d.
%
% The line-search merely guarantees a decrease in the cost (unless a
% stopping criterion triggers first, such as exceeding a maximal number of
% iterations). This is typically useful to escape saddle points (critical
% points admitting descent directions at the second order). Escape
% directions can be computed using hessianextreme, for example.
% 
% 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.
% An initial stepsize of norm_d thus means the first candidate x is
% obtained by retracting d at x, as is.
%
% Options:
%   options.ls_max_steps (25): maximum number of cost evaluations.
%   options.ls_initial_stepsize (norm_d): first stepsize trial.
%   options.ls_contraction_factor (0.5): stepsize reduction per iteration.
%
%
% Inputs/Outputs : see help for linesearch.
%   f0 is the cost at x.
%   df0 is unused.
%   options, storedb and key are optional.
%   Thus, a simplified calling pattern is (with all outputs still
%   available): linesearch_decrease(problem, x, d, f0)
%
% See also: steepestdescent linesearch hessianextreme

% This file is part of Manopt: www.manopt.org.
% Original author: Nicolas Boumal, April 8, 2015.
% Contributors: 
% Change log: 
%
%   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
    
    norm_d = problem.M.norm(x, d);

    % 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_initial_stepsize = norm_d;
    default_options.ls_max_steps = 25;
    
    if ~exist('options', 'var') || isempty(options)
        options = struct();
    end
    options = mergeOptions(default_options, options);
    
    contraction_factor = options.ls_contraction_factor;
    initial_stepsize = options.ls_initial_stepsize;
    max_ls_steps = options.ls_max_steps;
    
    % Initial step size as a mutliplier of d.
    alpha = initial_stepsize / norm_d;
    
    % 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 no cost decrease is obtained.
    while newf >= f0
        
        % 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.
    % Equal cost is accepted, since if x is critical, it is important to
    % move away from x more than it is important to decrease the cost.
    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;
    
    % Return some statistics also, for possible analysis.
    lsstats.costevals = cost_evaluations;
    lsstats.stepsize = stepsize;
    lsstats.alpha = alpha;
    
end
