Line search module

The line search finds a correct step length in a specific direction so that the cost function is minimized.

Exact line searches

  • GoldenSectionSearch(min_alpha_step, alpha_step = 1.) uses a section method based on the gold number
  • FibonnacciSectionSearch(min_alpha_step, alpha_step = 1.) uses the optimal section search to find the exact minimum
  • QuadraticInterpolationSearch(min_alpha_step, alpha_step = 1.) finds an adequate step with a quadratic interpolation procedure
  • CubicInterpolationSearch(min_alpha_step, alpha_step = 1., grad_tolerance = 1.e-6) finds an adequate step with a cubic interpolation procedure

The interpolation procedures are not bounded (for the moment).

Inexact line searches

  • SimpleLineSearch(alpha_step = 1.) returns alpha_step as the step length
  • DampedLineSearch(min_alpha_step, damped_error, alpha_step = 1.) finds a step that will decrease the cost function or raise it by a maximum factor of damped_error
  • BactrackingSearch(rho = 0.1, alpha_step = 1., alpha_factor = 0.5) uses the Armijo rule with factor rho to find an acceptable step length
  • WolfePowellRule(alpha = 1., rho = 0.1, sigma = 0.4, alpha_min = 0., alpha_max = 1., alpha_limit = 0.1) uses the simple Wolfe-Powell rules with factors rho and sigma with a start estimate alpha (should be changed into alpha_step). alpha_limit indicates the limit for the interpolation method (alpha cannot be lower than this value)
  • StrongWolfePowellRule(alpha = 1., rho = 0.1, sigma = 0.4, alpha_min = 0., alpha_max = 1., alpha_limit = 0.1) uses the strong Wolfe-Powell rules
  • GoldsteinRule(rho = 0.1, alpha_min = 0., alpha_max = 1.) finds a minimum with the Goldstein rules defined by the factor rho

The Wolfe-Powell based procedures are not bounded (for the moment).

Decorators

  • FixedLastStepModifier(line_search, alpha_factor = 2.) allows a line search to start at alpha_factor times the last step length