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.


 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 %
0072 %
0073 % See also: conjugategradient trustregions manopt/solvers/linesearch manopt/examples
0074 
0075 % This file is part of Manopt: www.manopt.org.
0076 % Original author: Nicolas Boumal, Dec. 30, 2012.
0077 % Contributors:
0078 % Change log:
0079 %
0080 %   April 3, 2015 (NB):
0081 %       Works with the new StoreDB class system.
0082 %
0083 %   Aug. 2, 2018 (NB):
0084 %       Now using storedb.remove() to keep the cache lean.
0085 
0086     
0087     % Verify that the problem description is sufficient for the solver.
0088     if ~canGetCost(problem)
0089         warning('manopt:getCost', ...
0090                 'No cost provided. The algorithm will likely abort.');
0091     end
0092     if ~canGetGradient(problem) && ~canGetApproxGradient(problem)
0093         % Note: we do not give a warning if an approximate gradient is
0094         % explicitly given in the problem description, as in that case the
0095         % user seems to be aware of the issue.
0096         warning('manopt:getGradient:approx', ...
0097                ['No gradient provided. Using an FD approximation instead (slow).\n' ...
0098                 'It may be necessary to increase options.tolgradnorm.\n' ...
0099                 'To disable this warning: warning(''off'', ''manopt:getGradient:approx'')']);
0100         problem.approxgrad = approxgradientFD(problem);
0101     end
0102     
0103     % Set local defaults here.
0104     localdefaults.minstepsize = 1e-10;
0105     localdefaults.maxiter = 1000;
0106     localdefaults.tolgradnorm = 1e-6;
0107     
0108     % Depending on whether the problem structure specifies a hint for
0109     % line-search algorithms, choose a default line-search that works on
0110     % its own (typical) or that uses the hint.
0111     if ~canGetLinesearch(problem)
0112         localdefaults.linesearch = @linesearch;
0113     else
0114         localdefaults.linesearch = @linesearch_hint;
0115     end
0116     
0117     % Merge global and local defaults, then merge w/ user options, if any.
0118     localdefaults = mergeOptions(getGlobalDefaults(), localdefaults);
0119     if ~exist('options', 'var') || isempty(options)
0120         options = struct();
0121     end
0122     options = mergeOptions(localdefaults, options);
0123     
0124     timetic = tic();
0125     
0126     % If no initial point x is given by the user, generate one at random.
0127     if ~exist('x', 'var') || isempty(x)
0128         x = problem.M.rand();
0129     end
0130     
0131     % Create a store database and get a key for the current x.
0132     storedb = StoreDB(options.storedepth);
0133     key = storedb.getNewKey();
0134     
0135     % Compute objective-related quantities for x.
0136     [cost, grad] = getCostGrad(problem, x, storedb, key);
0137     gradnorm = problem.M.norm(x, grad);
0138     
0139     % Iteration counter.
0140     % At any point, iter is the number of fully executed iterations so far.
0141     iter = 0;
0142     
0143     % Save stats in a struct array info, and preallocate.
0144     stats = savestats();
0145     info(1) = stats;
0146     info(min(10000, options.maxiter+1)).iter = [];
0147     
0148     if options.verbosity >= 2
0149         fprintf(' iter\t               cost val\t    grad. norm\n');
0150     end
0151     
0152     % Start iterating until stopping criterion triggers.
0153     while true
0154 
0155         % Display iteration information.
0156         if options.verbosity >= 2
0157             fprintf('%5d\t%+.16e\t%.8e\n', iter, cost, gradnorm);
0158         end
0159         
0160         % Start timing this iteration.
0161         timetic = tic();
0162         
0163         % Run standard stopping criterion checks.
0164         [stop, reason] = stoppingcriterion(problem, x, options, ...
0165                                                              info, iter+1);
0166         
0167         % If none triggered, run specific stopping criterion check.
0168         if ~stop && stats.stepsize < options.minstepsize
0169             stop = true;
0170             reason = sprintf(['Last stepsize smaller than minimum '  ...
0171                               'allowed; options.minstepsize = %g.'], ...
0172                               options.minstepsize);
0173         end
0174     
0175         if stop
0176             if options.verbosity >= 1
0177                 fprintf([reason '\n']);
0178             end
0179             break;
0180         end
0181 
0182         % Pick the descent direction as minus the gradient.
0183         desc_dir = problem.M.lincomb(x, -1, grad);
0184         
0185         % Execute the line search.
0186         [stepsize, newx, newkey, lsstats] = options.linesearch( ...
0187                              problem, x, desc_dir, cost, -gradnorm^2, ...
0188                              options, storedb, key);
0189         
0190         % Compute the new cost-related quantities for x
0191         [newcost, newgrad] = getCostGrad(problem, newx, storedb, newkey);
0192         newgradnorm = problem.M.norm(newx, newgrad);
0193         
0194         % Transfer iterate info, remove cache from previous x.
0195         storedb.removefirstifdifferent(key, newkey);
0196         x = newx;
0197         key = newkey;
0198         cost = newcost;
0199         grad = newgrad;
0200         gradnorm = newgradnorm;
0201         
0202         % Make sure we don't use too much memory for the store database.
0203         storedb.purge();
0204         
0205         % iter is the number of iterations we have accomplished.
0206         iter = iter + 1;
0207         
0208         % Log statistics for freshly executed iteration.
0209         stats = savestats();
0210         info(iter+1) = stats;
0211         
0212     end
0213     
0214     
0215     info = info(1:iter+1);
0216 
0217     if options.verbosity >= 1
0218         fprintf('Total time is %f [s] (excludes statsfun)\n', ...
0219                 info(end).time);
0220     end
0221     
0222     
0223     
0224     % Routine in charge of collecting the current iteration stats
0225     function stats = savestats()
0226         stats.iter = iter;
0227         stats.cost = cost;
0228         stats.gradnorm = gradnorm;
0229         if iter == 0
0230             stats.stepsize = NaN;
0231             stats.time = toc(timetic);
0232             stats.linesearch = [];
0233         else
0234             stats.stepsize = stepsize;
0235             stats.time = info(iter).time + toc(timetic);
0236             stats.linesearch = lsstats;
0237         end
0238         stats = applyStatsfun(problem, x, storedb, key, options, stats);
0239     end
0240     
0241 end

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