Source code for pymanopt.solvers.linesearch

[docs]class LineSearchBackTracking: """ Back-tracking line-search based on linesearch.m in the manopt MATLAB package. """ def __init__(self, contraction_factor=.5, optimism=2, suff_decr=1e-4, maxiter=25, initial_stepsize=1): self.contraction_factor = contraction_factor self.optimism = optimism self.suff_decr = suff_decr self.maxiter = maxiter self.initial_stepsize = initial_stepsize self._oldf0 = None
[docs] def search(self, objective, manifold, x, d, f0, df0): """ Function to perform backtracking line-search. Arguments: - objective objective function to optimise - manifold manifold to optimise over - x starting point on the manifold - d tangent vector at x (descent direction) - df0 directional derivative at x along d Returns: - stepsize norm of the vector retracted to reach newx from x - newx next iterate suggested by the line-search """ # Compute the norm of the search direction norm_d = manifold.norm(x, d) if self._oldf0 is not None: # Pick initial step size based on where we were last time. alpha = 2 * (f0 - self._oldf0) / df0 # Look a little further alpha *= self.optimism else: alpha = self.initial_stepsize / norm_d alpha = float(alpha) # Make the chosen step and compute the cost there. newx = manifold.retr(x, alpha * d) newf = objective(newx) step_count = 1 # Backtrack while the Armijo criterion is not satisfied while (newf > f0 + self.suff_decr * alpha * df0 and step_count <= self.maxiter): # Reduce the step size alpha = self.contraction_factor * alpha # and look closer down the line newx = manifold.retr(x, alpha * d) newf = objective(newx) step_count = step_count + 1 # If we got here without obtaining a decrease, we reject the step. if newf > f0: alpha = 0 newx = x stepsize = alpha * norm_d self._oldf0 = f0 return stepsize, newx
[docs]class LineSearchAdaptive: ''' Adaptive line-search ''' def __init__(self, contraction_factor=.5, suff_decr=.5, maxiter=10, initial_stepsize=1): self._contraction_factor = contraction_factor self._suff_decr = suff_decr self._maxiter = maxiter self._initial_stepsize = initial_stepsize self._oldalpha = None
[docs] def search(self, objective, man, x, d, f0, df0): norm_d = man.norm(x, d) if self._oldalpha is not None: alpha = self._oldalpha else: alpha = self._initial_stepsize / norm_d alpha = float(alpha) newx = man.retr(x, alpha * d) newf = objective(newx) cost_evaluations = 1 while (newf > f0 + self._suff_decr * alpha * df0 and cost_evaluations <= self._maxiter): # Reduce the step size. alpha *= self._contraction_factor # Look closer down the line. newx = man.retr(x, alpha * d) newf = objective(newx) cost_evaluations += 1 if newf > f0: alpha = 0 newx = x stepsize = alpha * norm_d # Store a suggestion for what the next initial step size trial should # be. On average we intend to do only one extra cost evaluation. Notice # how the suggestion is not about stepsize but about alpha. This is the # reason why this line search is not invariant under rescaling of the # search direction d. # If things go reasonably well, try to keep pace. if cost_evaluations == 2: self._oldalpha = alpha # If things went very well or we backtracked a lot (meaning the step # size is probably quite small), speed up. else: self._oldalpha = 2 * alpha return stepsize, newx