seisflows.optimize.LBFGS
L-BFGS (Limited memory Broyden–Fletcher–Goldfarb–Shanno) algorithm for solving nonlinear optimization problems.
- L-BFGS Variables:
s: memory of model differences y: memory of gradient differences
- Optimization Variables:
m: model f: objective function value g: gradient direction p: search direction
- Line Search Variables:
x: list of step lenths from current line search f: correpsonding list of function values m: number of step lengths in current line search n: number of model updates in optimization problem gtg: dot product of gradient with itself gtp: dot product of gradient and search direction
- Status codes
status > 0 : finished status == 0 : not finished status < 0 : failed
TODO store LBFGS_iter during checkpointing
Module Contents
Classes
L-BFGS Optimization |
- class seisflows.optimize.LBFGS.LBFGS(lbfgs_mem=3, lbfgs_max=np.inf, lbfgs_thresh=0.0, **kwargs)
Bases:
seisflows.optimize.gradient.Gradient
L-BFGS Optimization
Limited memory BFGS nonlienar optimization algorithm
Parameters
- type lbfgs_mem
int
- param lbfgs_mem
L-BFGS memory. Max number of previous gradients to retain in local memory for approximating the objective function.
- type lbfgs_max
L-BFGS periodic restart interval. Must be 1 <= lbfgs_max <= infinity.
- type lbfgs_thresh
L-BFGS angle restart threshold. If the angle between the current and previous search direction exceeds this value, optimization algorithm will be restarted.
Paths
- __doc__
- setup()
Set up the LBFGS optimization schema
- checkpoint()
Overwrite default checkpointing to store internal L-BFGS Attributes
- load_checkpoint()
Counterpart to optimize.checkpoint. Loads a checkpointed optimization module from disk and sets internal tracking attributes. Adds additional functionality to restore internal L-BFGS attributes
- compute_direction()
Call on the L-BFGS optimization machinery to compute a search direction using internally stored memory of previous gradients.
The potential outcomes when computing direction with L-BFGS: 1. First iteration of L-BFGS optimization, search direction is defined
as the inverse gradient
- L-BFGS internal iteration ticks over the maximum allowable number of
iterations, force a restart condition, search direction is the inverse gradient
- New search direction vector is too far from previous direction,
force a restart, search direction is inverse gradient
- New search direction is acceptably angled from previous,
becomes the new search direction
TODO do we need to precondition L-BFGS?
- Return type
seisflows.tools.specfem.Model
- Returns
search direction as a Model instance
- restart()
Restart the L-BFGS optimization algorithm by clearing out stored gradient memory.
- _update_search_history()
Updates L-BFGS algorithm history
Note
Because models are large, and multiple iterations of models need to be stored in memory, previous models are stored as memmaps, which allow for access of small segments of large files on disk, without reading the entire file. Memmaps are array like objects.
Note
Notation for s and y taken from Liu & Nocedal 1989 iterate notation: sk = x_k+1 - x_k and yk = g_k+1 - gk
- Rtype s
np.memmap
- Return s
memory of the model differences m_new - m_old
- Rtype y
np.memmap
- Return y
memory of the gradient differences g_new - g_old
- _apply_inverse_hessian(q, s=None, y=None)
Applies L-BFGS inverse Hessian to given vector
- Parameters
q (np.array) – gradient direction to apply L-BFGS to
s (np.memmap) – memory of model differences
s – memory of model differences
y (np.memmap) – memory of gradient direction differences
- Rtype r
np.array
- Return r
new search direction from application of L-BFGS
- _check_status(g, r)
Check the status of the apply() function, determine if restart necessary Return of False means restart, return of True means good to go.
- Parameters
g (np.array) – current gradient direction
r (np.array) – new gradient direction
- Return type
bool
- Returns
okay status based on status check (False==bad, True==good)