Home > manopt > solvers > linesearch > linesearch_hint.m

linesearch_hint

PURPOSE ^

Armijo line-search based on the line-search hint in the problem structure.

SYNOPSIS ^

function [stepsize, newx, newkey, lsstats] =linesearch_hint(problem, x, d, f0, df0, options, storedb, key)

DESCRIPTION ^

 Armijo line-search based on the line-search hint in the problem structure.

 function [stepsize, newx, newkey, lsstats] = 
            linesearch_hint(problem, x, d, f0, df0, options, storedb, key)

 Base line-search algorithm for descent methods, based on a simple
 backtracking method. The search direction provided has to be a descent
 direction, as indicated by a negative df0 = directional derivative of f
 at x along d.

 The algorithm obtains an initial step size candidate from the problem
 structure, typically through the problem.linesearch function. If that
 step does not fulfill the Armijo sufficient decrease criterion, that step
 size is reduced geometrically until a satisfactory step size is obtained
 or until a failure criterion triggers. If the problem structure does not
 provide an initial alpha, then alpha = 1 is tried first.
 
 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.

 Inputs/Outputs : see help for linesearch

 See also: steepestdescent conjugategradients linesearch

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function [stepsize, newx, newkey, lsstats] = ...
0002              linesearch_hint(problem, x, d, f0, df0, options, storedb, key)
0003 % Armijo line-search based on the line-search hint in the problem structure.
0004 %
0005 % function [stepsize, newx, newkey, lsstats] =
0006 %            linesearch_hint(problem, x, d, f0, df0, options, storedb, key)
0007 %
0008 % Base line-search algorithm for descent methods, based on a simple
0009 % backtracking method. The search direction provided has to be a descent
0010 % direction, as indicated by a negative df0 = directional derivative of f
0011 % at x along d.
0012 %
0013 % The algorithm obtains an initial step size candidate from the problem
0014 % structure, typically through the problem.linesearch function. If that
0015 % step does not fulfill the Armijo sufficient decrease criterion, that step
0016 % size is reduced geometrically until a satisfactory step size is obtained
0017 % or until a failure criterion triggers. If the problem structure does not
0018 % provide an initial alpha, then alpha = 1 is tried first.
0019 %
0020 % Below, the step is constructed as alpha*d, and the step size is the norm
0021 % of that vector, thus: stepsize = alpha*norm_d. The step is executed by
0022 % retracting the vector alpha*d from the current point x, giving newx.
0023 %
0024 % Inputs/Outputs : see help for linesearch
0025 %
0026 % See also: steepestdescent conjugategradients linesearch
0027 
0028 % This file is part of Manopt: www.manopt.org.
0029 % Original author: Nicolas Boumal, July 17, 2014.
0030 % Contributors:
0031 % Change log:
0032 %
0033 %   April 3, 2015 (NB):
0034 %       Works with the new StoreDB class system.
0035 %
0036 %   April 8, 2015 (NB):
0037 %       Got rid of lsmem input/output.
0038 %
0039 %   July 20, 2017 (NB):
0040 %       Now using alpha = 1 by default.
0041 %
0042 %   Aug. 28, 2017 (NB):
0043 %       Adding two options: ls_backtrack and ls_force_decrease, both true
0044 %       by default. Setting them to false can disable parts of the line
0045 %       search that, respectively, execute an Armijo backtracking and
0046 %       reject a cost increasing step.
0047 %
0048 %   Aug. 2, 2018 (NB):
0049 %       Now using storedb.remove() to keep the cache lean.
0050 
0051 
0052     % Allow omission of the key, and even of storedb.
0053     if ~exist('key', 'var')
0054         if ~exist('storedb', 'var')
0055             storedb = StoreDB();
0056         end
0057         key = storedb.getNewKey();
0058     end
0059 
0060     % Backtracking default parameters. These can be overwritten in the
0061     % options structure which is passed to the solver.
0062     default_options.ls_contraction_factor = .5;
0063     default_options.ls_suff_decr = 1e-4;
0064     default_options.ls_max_steps = 25;
0065     default_options.ls_backtrack = true;
0066     default_options.ls_force_decrease = true;
0067     
0068     if ~exist('options', 'var') || isempty(options)
0069         options = struct();
0070     end
0071     options = mergeOptions(default_options, options);
0072     
0073     contraction_factor = options.ls_contraction_factor;
0074     suff_decr = options.ls_suff_decr;
0075     max_ls_steps = options.ls_max_steps;
0076     
0077     % Obtain an initial guess at alpha from the problem structure.
0078     if canGetLinesearch(problem)
0079         alpha = getLinesearch(problem, x, d, storedb, key);
0080     else
0081         alpha = 1;
0082     end
0083     
0084     % Make the chosen step and compute the cost there.
0085     newx = problem.M.retr(x, d, alpha);
0086     newkey = storedb.getNewKey();
0087     newf = getCost(problem, newx, storedb, newkey);
0088     cost_evaluations = 1;
0089     
0090     % Backtrack while the Armijo criterion is not satisfied.
0091     while options.ls_backtrack && newf > f0 + suff_decr*alpha*df0
0092         
0093         % Reduce the step size,
0094         alpha = contraction_factor * alpha;
0095         
0096         % and look closer down the line.
0097         storedb.remove(newkey);              % we no longer need this cache
0098         newx = problem.M.retr(x, d, alpha);
0099         newkey = storedb.getNewKey();
0100         newf = getCost(problem, newx, storedb, newkey);
0101         cost_evaluations = cost_evaluations + 1;
0102         
0103         % Make sure we don't run out of budget.
0104         if cost_evaluations >= max_ls_steps
0105             break;
0106         end
0107         
0108     end
0109     
0110     % If we got here without obtaining a decrease, we reject the step.
0111     if options.ls_force_decrease && newf > f0
0112         alpha = 0;
0113         newx = x;
0114         newkey = key;
0115         newf = f0; %#ok<NASGU>
0116     end
0117     
0118     % As seen outside this function, stepsize is the size of the vector we
0119     % retract to make the step from x to newx. Since the step is alpha*d:
0120     norm_d = problem.M.norm(x, d);
0121     stepsize = alpha * norm_d;
0122     
0123     % Return some statistics also, for possible analysis.
0124     lsstats.costevals = cost_evaluations;
0125     lsstats.stepsize = stepsize;
0126     lsstats.alpha = alpha;
0127     
0128 end

Generated on Mon 10-Sep-2018 11:48:06 by m2html © 2005