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 linesearch0001 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