Home > manopt > solvers > hessianapproximations > approxhessianFD.m

approxhessianFD

PURPOSE ^

Hessian approx. fnctn handle based on finite differences of the gradient.

SYNOPSIS ^

function hessfun = approxhessianFD(problem, options)

DESCRIPTION ^

 Hessian approx. fnctn handle based on finite differences of the gradient.

 function hessfun = approxhessianFD(problem)
 function hessfun = approxhessianFD(problem, options)

 Input:

 A Manopt problem structure (already containing the manifold and enough
 information to compute the cost gradient) and an options structure
 (optional), containing one option:
    options.stepsize (positive double; default: 2^-14).

 If the gradient cannot be computed or approximated on 'problem',
 a warning is issued.

 Output:
 
 Returns a function handle, encapsulating a generic finite difference
 approximation of the Hessian of the problem cost. The finite difference
 is based on computations of the gradient.
 
 The returned hessfun has this calling pattern:
 
   function hessfd = hessfun(x, xdot)
   function hessfd = hessfun(x, xdot, storedb)
   function hessfd = hessfun(x, xdot, storedb, key)
 
 x is a point on the manifold problem.M, xdot is a tangent vector to that
 manifold at x, storedb is a StoreDB object, and key is the StoreDB key to
 point x.

 Usage:

 Typically, the user will set problem.M and other fields to define the
 cost and the gradient (typically, problem.cost and problem.grad or
 problem.egrad). Then, to use this generic purpose Hessian approximation:

   problem.approxhess = approxhessianFD(problem, options);

 See also: trustregions

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SUBFUNCTIONS ^

SOURCE CODE ^

0001 function hessfun = approxhessianFD(problem, options)
0002 % Hessian approx. fnctn handle based on finite differences of the gradient.
0003 %
0004 % function hessfun = approxhessianFD(problem)
0005 % function hessfun = approxhessianFD(problem, options)
0006 %
0007 % Input:
0008 %
0009 % A Manopt problem structure (already containing the manifold and enough
0010 % information to compute the cost gradient) and an options structure
0011 % (optional), containing one option:
0012 %    options.stepsize (positive double; default: 2^-14).
0013 %
0014 % If the gradient cannot be computed or approximated on 'problem',
0015 % a warning is issued.
0016 %
0017 % Output:
0018 %
0019 % Returns a function handle, encapsulating a generic finite difference
0020 % approximation of the Hessian of the problem cost. The finite difference
0021 % is based on computations of the gradient.
0022 %
0023 % The returned hessfun has this calling pattern:
0024 %
0025 %   function hessfd = hessfun(x, xdot)
0026 %   function hessfd = hessfun(x, xdot, storedb)
0027 %   function hessfd = hessfun(x, xdot, storedb, key)
0028 %
0029 % x is a point on the manifold problem.M, xdot is a tangent vector to that
0030 % manifold at x, storedb is a StoreDB object, and key is the StoreDB key to
0031 % point x.
0032 %
0033 % Usage:
0034 %
0035 % Typically, the user will set problem.M and other fields to define the
0036 % cost and the gradient (typically, problem.cost and problem.grad or
0037 % problem.egrad). Then, to use this generic purpose Hessian approximation:
0038 %
0039 %   problem.approxhess = approxhessianFD(problem, options);
0040 %
0041 % See also: trustregions
0042 
0043 % The Riemannian Trust-Region method, used in combination with the present
0044 % Hessian approximation, is called RTR-FD. Some convergence theory for it
0045 % is available in this paper:
0046 %
0047 % @incollection{boumal2015rtrfd
0048 %     author={Boumal, N.},
0049 %     title={Riemannian trust regions with finite-difference Hessian approximations are globally convergent},
0050 %     year={2015},
0051 %     booktitle={Geometric Science of Information}
0052 % }
0053 
0054 % This file is part of Manopt: www.manopt.org.
0055 % Original author: Nicolas Boumal, April 8, 2015.
0056 % Contributors:
0057 % Change log:
0058 %
0059 %   Feb. 19, 2015 (NB):
0060 %       It is sufficient to ensure positive radial linearity to guarantee
0061 %       (together with other assumptions) that this approximation of the
0062 %       Hessian will confer global convergence to the trust-regions method.
0063 %       Formerly, in-code comments referred to the necessity of having
0064 %       complete radial linearity, and that this was harder to achieve.
0065 %       This appears not to be necessary after all, which simplifies the
0066 %       code.
0067 %
0068 %   April 3, 2015 (NB):
0069 %       Works with the new StoreDB class system.
0070 %
0071 %   April 8, 2015 (NB):
0072 %       Changed to approxhessianFD, which now returns a function handle
0073 %       that encapsulates the getHessianFD functionality. Will be better
0074 %       aligned with the other Hessian approximations to come (which may
0075 %       want to use storedb.internal), and now allows specifying the step
0076 %       size.
0077 
0078     % This Hessian approximation is based on the gradient:
0079     % check availability.
0080     if ~canGetGradient(problem) && ~canGetApproxGradient(problem)
0081         warning('manopt:approxhessianFD:nogradient', ...
0082                 'approxhessianFD requires the gradient to be computable.');
0083     end
0084 
0085     % Set local defaults here, and merge with user options, if any.
0086     localdefaults.stepsize = 2^-14;
0087     if ~exist('options', 'var') || isempty(options)
0088         options = struct();
0089     end
0090     options = mergeOptions(localdefaults, options);
0091     
0092     % Finite-difference parameter: how far do we look?
0093     stepsize = options.stepsize;
0094                    
0095     % Build and return the function handle here. This extra construct via
0096     % funhandle makes it possible to make storedb and key optional.
0097     hessfun = @funhandle;
0098     function hessfd = funhandle(x, xdot, storedb, key)
0099         % Allow omission of the key, and even of storedb.
0100         if ~exist('key', 'var')
0101             if ~exist('storedb', 'var')
0102                 storedb = StoreDB();
0103             end
0104             key = storedb.getNewKey();
0105         end 
0106         hessfd = hessianFD(stepsize, problem, x, xdot, storedb, key);
0107     end
0108     
0109 end
0110 
0111 
0112 function hessfd = hessianFD(stepsize, problem, x, xdot, storedb, key)
0113 % This function does the actual work.
0114 %
0115 % Original code: Dec. 30, 2012 (NB).
0116     
0117     % Extract the input vector norm.
0118     norm_xdot = problem.M.norm(x, xdot);
0119     
0120     % First, check whether the step xdot is not too small.
0121     if norm_xdot < eps
0122         hessfd = problem.M.zerovec(x);
0123         return;
0124     end
0125     
0126     % Determine how far to retract xdot, so that the point reached does not
0127     % depend on the norm of xdot. This is what ensures radial linearity of
0128     % this present Hessian approximation.
0129     c = stepsize / norm_xdot;
0130     
0131     % Compute the gradient at the current point.
0132     grad = getGradient(problem, x, storedb, key);
0133     
0134     % Compute a point a little further along xdot, and the gradient there.
0135     % Since this is a new point, we need a new key for it, for storedb.
0136     x1 = problem.M.retr(x, xdot, c);
0137     key1 = storedb.getNewKey();
0138     grad1 = getGradient(problem, x1, storedb, key1);
0139     
0140     % Transport grad1 back from x1 to x.
0141     grad1 = problem.M.transp(x1, x, grad1);
0142     
0143     % Return the finite difference of them: (grad1 - grad)/c.
0144     hessfd = problem.M.lincomb(x, 1/c, grad1, -1/c, grad);
0145     
0146 end

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