Backtracking line-search aiming merely for a decrease in cost value. function [stepsize, newx, newkey, lsstats] = linesearch_decrease(problem, x, d, f0, df0, options, storedb, key) Line-search algorithm based on a simple backtracking method. The search direction provided has to be a descent direction, but needs not be a first-order descent, i.e.: this line-search can be used even if x is a critical point, as long as the cost function is strictly decreasing along the direction d. The line-search merely guarantees a decrease in the cost (unless a stopping criterion triggers first, such as exceeding a maximal number of iterations). This is typically useful to escape saddle points (critical points admitting descent directions at the second order). Escape directions can be computed using hessianextreme, for example. 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. An initial stepsize of norm_d thus means the first candidate x is obtained by retracting d at x, as is. Options: options.ls_max_steps (25): maximum number of cost evaluations. options.ls_initial_stepsize (norm_d): first stepsize trial. options.ls_contraction_factor (0.5): stepsize reduction per iteration. Inputs/Outputs : see help for linesearch. f0 is the cost at x. df0 is unused. options, storedb and key are optional. Thus, a simplified calling pattern is (with all outputs still available): linesearch_decrease(problem, x, d, f0) See also: steepestdescent linesearch hessianextreme
0001 function [stepsize, newx, newkey, lsstats] = ... 0002 linesearch_decrease(problem, x, d, f0, ~, options, storedb, key) 0003 % Backtracking line-search aiming merely for a decrease in cost value. 0004 % 0005 % function [stepsize, newx, newkey, lsstats] = 0006 % linesearch_decrease(problem, x, d, f0, df0, options, storedb, key) 0007 % 0008 % Line-search algorithm based on a simple backtracking method. The search 0009 % direction provided has to be a descent direction, but needs not be a 0010 % first-order descent, i.e.: this line-search can be used even if x is a 0011 % critical point, as long as the cost function is strictly decreasing 0012 % along the direction d. 0013 % 0014 % The line-search merely guarantees a decrease in the cost (unless a 0015 % stopping criterion triggers first, such as exceeding a maximal number of 0016 % iterations). This is typically useful to escape saddle points (critical 0017 % points admitting descent directions at the second order). Escape 0018 % directions can be computed using hessianextreme, for example. 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 % An initial stepsize of norm_d thus means the first candidate x is 0024 % obtained by retracting d at x, as is. 0025 % 0026 % Options: 0027 % options.ls_max_steps (25): maximum number of cost evaluations. 0028 % options.ls_initial_stepsize (norm_d): first stepsize trial. 0029 % options.ls_contraction_factor (0.5): stepsize reduction per iteration. 0030 % 0031 % 0032 % Inputs/Outputs : see help for linesearch. 0033 % f0 is the cost at x. 0034 % df0 is unused. 0035 % options, storedb and key are optional. 0036 % Thus, a simplified calling pattern is (with all outputs still 0037 % available): linesearch_decrease(problem, x, d, f0) 0038 % 0039 % See also: steepestdescent linesearch hessianextreme 0040 0041 % This file is part of Manopt: www.manopt.org. 0042 % Original author: Nicolas Boumal, April 8, 2015. 0043 % Contributors: 0044 % Change log: 0045 % 0046 % Aug. 2, 2018 (NB): 0047 % Now using storedb.remove() to keep the cache lean. 0048 0049 0050 % Allow omission of the key, and even of storedb. 0051 if ~exist('key', 'var') 0052 if ~exist('storedb', 'var') 0053 storedb = StoreDB(); 0054 end 0055 key = storedb.getNewKey(); 0056 end 0057 0058 norm_d = problem.M.norm(x, d); 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_initial_stepsize = norm_d; 0064 default_options.ls_max_steps = 25; 0065 0066 if ~exist('options', 'var') || isempty(options) 0067 options = struct(); 0068 end 0069 options = mergeOptions(default_options, options); 0070 0071 contraction_factor = options.ls_contraction_factor; 0072 initial_stepsize = options.ls_initial_stepsize; 0073 max_ls_steps = options.ls_max_steps; 0074 0075 % Initial step size as a mutliplier of d. 0076 alpha = initial_stepsize / norm_d; 0077 0078 % Make the chosen step and compute the cost there. 0079 newx = problem.M.retr(x, d, alpha); 0080 newkey = storedb.getNewKey(); 0081 newf = getCost(problem, newx, storedb, newkey); 0082 cost_evaluations = 1; 0083 0084 % Backtrack while no cost decrease is obtained. 0085 while newf >= f0 0086 0087 % Reduce the step size, 0088 alpha = contraction_factor * alpha; 0089 0090 % and look closer down the line. 0091 storedb.remove(newkey); % we no longer need this cache 0092 newx = problem.M.retr(x, d, alpha); 0093 newkey = storedb.getNewKey(); 0094 newf = getCost(problem, newx, storedb, newkey); 0095 cost_evaluations = cost_evaluations + 1; 0096 0097 % Make sure we don't run out of budget. 0098 if cost_evaluations >= max_ls_steps 0099 break; 0100 end 0101 0102 end 0103 0104 % If we got here without obtaining a decrease, we reject the step. 0105 % Equal cost is accepted, since if x is critical, it is important to 0106 % move away from x more than it is important to decrease the cost. 0107 if newf > f0 0108 alpha = 0; 0109 newx = x; 0110 newkey = key; 0111 newf = f0; %#ok<NASGU> 0112 end 0113 0114 % As seen outside this function, stepsize is the size of the vector we 0115 % retract to make the step from x to newx. Since the step is alpha*d: 0116 stepsize = alpha * norm_d; 0117 0118 % Return some statistics also, for possible analysis. 0119 lsstats.costevals = cost_evaluations; 0120 lsstats.stepsize = stepsize; 0121 lsstats.alpha = alpha; 0122 0123 end