Home > manopt > solvers > steepestdescent > steepestdescent.m

steepestdescent

PURPOSE ^

Steepest descent (gradient descent) minimization algorithm for Manopt.

SYNOPSIS ^

function [x, cost, info, options] = steepestdescent(problem, x, options)

DESCRIPTION ^

 Steepest descent (gradient descent) minimization algorithm for Manopt.

 function [x, cost, info, options] = steepestdescent(problem)
 function [x, cost, info, options] = steepestdescent(problem, x0)
 function [x, cost, info, options] = steepestdescent(problem, x0, options)
 function [x, cost, info, options] = steepestdescent(problem, [], options)

 Apply the steepest descent minimization algorithm to the problem defined
 in the problem structure, starting at x0 if it is provided (otherwise, at
 a random point on the manifold). To specify options whilst not specifying
 an initial guess, give x0 as [] (the empty matrix).

 In most of the examples bundled with the toolbox (see link below), the
 solver can be replaced by the present one if need be.

 The outputs x and cost are the best reached point on the manifold and its
 cost. The struct-array info contains information about the iterations:
   iter : the iteration number (0 for the initial guess)
   cost : cost value
   time : elapsed time in seconds
   gradnorm : Riemannian norm of the gradient
   stepsize : norm of the last tangent vector retracted
   linesearch : information logged by options.linesearch
   And possibly additional information logged by options.statsfun.
 For example, type [info.gradnorm] to obtain a vector of the successive
 gradient norms reached.

 The options structure is used to overwrite the default values. All
 options have a default value and are hence optional. To force an option
 value, pass an options structure with a field options.optionname, where
 optionname is one of the following and the default value is indicated
 between parentheses:

   tolgradnorm (1e-6)
       The algorithm terminates if the norm of the gradient drops below this.
   maxiter (1000)
       The algorithm terminates if maxiter iterations have been executed.
   maxtime (Inf)
       The algorithm terminates if maxtime seconds elapsed.
   minstepsize (1e-10)
       The algorithm terminates if the linesearch returns a displacement
       vector (to be retracted) smaller in norm than this value.
   linesearch (@linesearch or @linesearch_hint)
       Function handle to a line search function. The options structure is
       passed to the line search too, so you can pass it parameters. See
       each line search's documentation for info. Another available line
       search in manopt is @linesearch_adaptive, in
       /manopt/linesearch/linesearch_adaptive.m
       If the problem structure includes a line search hint, then the
       default line search used is @linesearch_hint.
   statsfun (none)
       Function handle to a function that will be called after each
       iteration to provide the opportunity to log additional statistics.
       They will be returned in the info struct. See the generic Manopt
       documentation about solvers for further information.
   stopfun (none)
       Function handle to a function that will be called at each iteration
       to provide the opportunity to specify additional stopping criteria.
       See the generic Manopt documentation about solvers for further
       information.
   verbosity (3)
       Integer number used to tune the amount of output the algorithm
       generates during execution (mostly as text in the command window).
       The higher, the more output. 0 means silent.
   storedepth (2)
       Maximum number of different points x of the manifold for which a
       store structure will be kept in memory in the storedb for caching.
       For the SD algorithm, a store depth of 2 should always be
       sufficient.
   hook (none)
       A function handle which allows the user to change the current point
       x at the beginning of each iteration, before the stopping criterion
       is evaluated. See applyHook for help on how to use this option.


 See also: conjugategradient trustregions manopt/solvers/linesearch manopt/examples

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function [x, cost, info, options] = steepestdescent(problem, x, options)
0002 % Steepest descent (gradient descent) minimization algorithm for Manopt.
0003 %
0004 % function [x, cost, info, options] = steepestdescent(problem)
0005 % function [x, cost, info, options] = steepestdescent(problem, x0)
0006 % function [x, cost, info, options] = steepestdescent(problem, x0, options)
0007 % function [x, cost, info, options] = steepestdescent(problem, [], options)
0008 %
0009 % Apply the steepest descent minimization algorithm to the problem defined
0010 % in the problem structure, starting at x0 if it is provided (otherwise, at
0011 % a random point on the manifold). To specify options whilst not specifying
0012 % an initial guess, give x0 as [] (the empty matrix).
0013 %
0014 % In most of the examples bundled with the toolbox (see link below), the
0015 % solver can be replaced by the present one if need be.
0016 %
0017 % The outputs x and cost are the best reached point on the manifold and its
0018 % cost. The struct-array info contains information about the iterations:
0019 %   iter : the iteration number (0 for the initial guess)
0020 %   cost : cost value
0021 %   time : elapsed time in seconds
0022 %   gradnorm : Riemannian norm of the gradient
0023 %   stepsize : norm of the last tangent vector retracted
0024 %   linesearch : information logged by options.linesearch
0025 %   And possibly additional information logged by options.statsfun.
0026 % For example, type [info.gradnorm] to obtain a vector of the successive
0027 % gradient norms reached.
0028 %
0029 % The options structure is used to overwrite the default values. All
0030 % options have a default value and are hence optional. To force an option
0031 % value, pass an options structure with a field options.optionname, where
0032 % optionname is one of the following and the default value is indicated
0033 % between parentheses:
0034 %
0035 %   tolgradnorm (1e-6)
0036 %       The algorithm terminates if the norm of the gradient drops below this.
0037 %   maxiter (1000)
0038 %       The algorithm terminates if maxiter iterations have been executed.
0039 %   maxtime (Inf)
0040 %       The algorithm terminates if maxtime seconds elapsed.
0041 %   minstepsize (1e-10)
0042 %       The algorithm terminates if the linesearch returns a displacement
0043 %       vector (to be retracted) smaller in norm than this value.
0044 %   linesearch (@linesearch or @linesearch_hint)
0045 %       Function handle to a line search function. The options structure is
0046 %       passed to the line search too, so you can pass it parameters. See
0047 %       each line search's documentation for info. Another available line
0048 %       search in manopt is @linesearch_adaptive, in
0049 %       /manopt/linesearch/linesearch_adaptive.m
0050 %       If the problem structure includes a line search hint, then the
0051 %       default line search used is @linesearch_hint.
0052 %   statsfun (none)
0053 %       Function handle to a function that will be called after each
0054 %       iteration to provide the opportunity to log additional statistics.
0055 %       They will be returned in the info struct. See the generic Manopt
0056 %       documentation about solvers for further information.
0057 %   stopfun (none)
0058 %       Function handle to a function that will be called at each iteration
0059 %       to provide the opportunity to specify additional stopping criteria.
0060 %       See the generic Manopt documentation about solvers for further
0061 %       information.
0062 %   verbosity (3)
0063 %       Integer number used to tune the amount of output the algorithm
0064 %       generates during execution (mostly as text in the command window).
0065 %       The higher, the more output. 0 means silent.
0066 %   storedepth (2)
0067 %       Maximum number of different points x of the manifold for which a
0068 %       store structure will be kept in memory in the storedb for caching.
0069 %       For the SD algorithm, a store depth of 2 should always be
0070 %       sufficient.
0071 %   hook (none)
0072 %       A function handle which allows the user to change the current point
0073 %       x at the beginning of each iteration, before the stopping criterion
0074 %       is evaluated. See applyHook for help on how to use this option.
0075 %
0076 %
0077 % See also: conjugategradient trustregions manopt/solvers/linesearch manopt/examples
0078 
0079 % This file is part of Manopt: www.manopt.org.
0080 % Original author: Nicolas Boumal, Dec. 30, 2012.
0081 % Contributors:
0082 % Change log:
0083 %
0084 %   April 3, 2015 (NB):
0085 %       Works with the new StoreDB class system.
0086 %
0087 %   Aug. 2, 2018 (NB):
0088 %       Now using storedb.remove() to keep the cache lean.
0089 %
0090 %   July 19, 2020 (NB):
0091 %       Added support for options.hook.
0092 
0093     
0094     % Verify that the problem description is sufficient for the solver.
0095     if ~canGetCost(problem)
0096         warning('manopt:getCost', ...
0097                 'No cost provided. The algorithm will likely abort.');
0098     end
0099     if ~canGetGradient(problem) && ~canGetApproxGradient(problem)
0100         % Note: we do not give a warning if an approximate gradient is
0101         % explicitly given in the problem description, as in that case the
0102         % user seems to be aware of the issue.
0103         warning('manopt:getGradient:approx', ...
0104                ['No gradient provided. Using an FD approximation instead (slow).\n' ...
0105                 'It may be necessary to increase options.tolgradnorm.\n' ...
0106                 'To disable this warning: warning(''off'', ''manopt:getGradient:approx'')']);
0107         problem.approxgrad = approxgradientFD(problem);
0108     end
0109     
0110     % Set local defaults here.
0111     localdefaults.minstepsize = 1e-10;
0112     localdefaults.maxiter = 1000;
0113     localdefaults.tolgradnorm = 1e-6;
0114     
0115     % Depending on whether the problem structure specifies a hint for
0116     % line-search algorithms, choose a default line-search that works on
0117     % its own (typical) or that uses the hint.
0118     if ~canGetLinesearch(problem)
0119         localdefaults.linesearch = @linesearch;
0120     else
0121         localdefaults.linesearch = @linesearch_hint;
0122     end
0123     
0124     % Merge global and local defaults, then merge w/ user options, if any.
0125     localdefaults = mergeOptions(getGlobalDefaults(), localdefaults);
0126     if ~exist('options', 'var') || isempty(options)
0127         options = struct();
0128     end
0129     options = mergeOptions(localdefaults, options);
0130     
0131     timetic = tic();
0132     
0133     % If no initial point x is given by the user, generate one at random.
0134     if ~exist('x', 'var') || isempty(x)
0135         x = problem.M.rand();
0136     end
0137     
0138     % Create a store database and get a key for the current x.
0139     storedb = StoreDB(options.storedepth);
0140     key = storedb.getNewKey();
0141     
0142     % Compute objective-related quantities for x.
0143     [cost, grad] = getCostGrad(problem, x, storedb, key);
0144     gradnorm = problem.M.norm(x, grad);
0145     
0146     % Iteration counter.
0147     % At any point, iter is the number of fully executed iterations so far.
0148     iter = 0;
0149     
0150     % Save stats in a struct array info, and preallocate.
0151     stats = savestats();
0152     info(1) = stats;
0153     info(min(10000, options.maxiter+1)).iter = [];
0154     
0155     if options.verbosity >= 2
0156         fprintf(' iter\t               cost val\t    grad. norm\n');
0157     end
0158     
0159     % Start iterating until stopping criterion triggers.
0160     while true
0161 
0162         % Display iteration information.
0163         if options.verbosity >= 2
0164             fprintf('%5d\t%+.16e\t%.8e\n', iter, cost, gradnorm);
0165         end
0166         
0167         % Start timing this iteration.
0168         timetic = tic();
0169 
0170         % Apply the hook function if there is one: this allows external code to
0171         % move x to another point. If the point is changed (indicated by a true
0172         % value for the boolean 'hooked'), we update our knowledge about x.
0173         [x, key, info, hooked] = applyHook(problem, x, storedb, key, ...
0174                                                     options, info, iter+1);
0175         if hooked
0176             [cost, grad] = getCostGrad(problem, x, storedb, key);
0177             gradnorm = problem.M.norm(x, grad);
0178         end
0179         
0180         % Run standard stopping criterion checks.
0181         [stop, reason] = stoppingcriterion(problem, x, options, ...
0182                                                              info, iter+1);
0183         
0184         % If none triggered, run specific stopping criterion check.
0185         if ~stop && stats.stepsize < options.minstepsize
0186             stop = true;
0187             reason = sprintf(['Last stepsize smaller than minimum '  ...
0188                               'allowed; options.minstepsize = %g.'], ...
0189                               options.minstepsize);
0190         end
0191     
0192         if stop
0193             if options.verbosity >= 1
0194                 fprintf([reason '\n']);
0195             end
0196             break;
0197         end
0198 
0199         % Pick the descent direction as minus the gradient.
0200         desc_dir = problem.M.lincomb(x, -1, grad);
0201         
0202         % Execute the line search.
0203         [stepsize, newx, newkey, lsstats] = options.linesearch( ...
0204                              problem, x, desc_dir, cost, -gradnorm^2, ...
0205                              options, storedb, key);
0206         
0207         % Compute the new cost-related quantities for x
0208         [newcost, newgrad] = getCostGrad(problem, newx, storedb, newkey);
0209         newgradnorm = problem.M.norm(newx, newgrad);
0210         
0211         % Transfer iterate info, remove cache from previous x.
0212         storedb.removefirstifdifferent(key, newkey);
0213         x = newx;
0214         key = newkey;
0215         cost = newcost;
0216         grad = newgrad;
0217         gradnorm = newgradnorm;
0218         
0219         % Make sure we don't use too much memory for the store database.
0220         storedb.purge();
0221         
0222         % iter is the number of iterations we have accomplished.
0223         iter = iter + 1;
0224         
0225         % Log statistics for freshly executed iteration.
0226         stats = savestats();
0227         info(iter+1) = stats;
0228         
0229     end
0230     
0231     
0232     info = info(1:iter+1);
0233 
0234     if options.verbosity >= 1
0235         fprintf('Total time is %f [s] (excludes statsfun)\n', ...
0236                 info(end).time);
0237     end
0238     
0239     
0240     
0241     % Routine in charge of collecting the current iteration stats.
0242     function stats = savestats()
0243         stats.iter = iter;
0244         stats.cost = cost;
0245         stats.gradnorm = gradnorm;
0246         if iter == 0
0247             stats.stepsize = NaN;
0248             stats.time = toc(timetic);
0249             stats.linesearch = [];
0250         else
0251             stats.stepsize = stepsize;
0252             stats.time = info(iter).time + toc(timetic);
0253             stats.linesearch = lsstats;
0254         end
0255         stats = applyStatsfun(problem, x, storedb, key, options, stats);
0256     end
0257     
0258 end

Generated on Sun 05-Sep-2021 17:57:00 by m2html © 2005