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

## CROSS-REFERENCE INFORMATION This function calls:
This function is called by:
• barzilaiborwein Riemannian Barzilai-Borwein solver with non-monotone line-search.
• rlbfgs Riemannian limited memory BFGS solver for smooth objective functions.
• steepestdescent Steepest descent (gradient descent) minimization algorithm for Manopt.

## 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 %
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 Fri 30-Sep-2022 13:18:25 by m2html © 2005