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

Generated on Sat 12-Nov-2016 14:11:22 by m2html © 2005