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

Classes

LBFGS

L-BFGS Optimization

Module Contents

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 nonlinear 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__ = Multiline-String

Show Value

"""
    Gradient Optimization [Optimize Base]
    -------------------------------------
    Defines foundational structure for Optimization module. Applies a
    gradient/steepest descent optimization algorithm.

    Parameters
    ----------
    :type line_search_method: str
    :param line_search_method: chosen line_search algorithm. Currently available
        are 'bracket' and 'backtrack'. See seisflows.plugins.line_search
        for all available options
    :type preconditioner: str
    :param preconditioner: algorithm for preconditioning gradients. Currently
        available: 'diagonal'. Requires `path_preconditioner` to point to a
        set of files that define the preconditioner, formatted the same as the
        input model
    :type step_count_max: int
    :param step_count_max: maximum number of trial steps to perform during
        the line search before a change in line search behavior is
        considered, or a line search is considered to have failed.
    :type step_len_init: float
    :param step_len_init: initial line search step length guess, provided
        as a fraction of current model parameters.
    :type step_len_max: float
    :param step_len_max: optional, maximum allowable step length during the line
        search. Set as a fraction of the current model parameters
    :type step_len_min: float
    :param step_len_min: optional, minimum allowable step length during the line
        search. Set as a fraction of the current model parameters

    Paths
    -----
    :type path_preconditioner: str
    :param path_preconditioner: optional path to a set of preconditioner files
        formatted the same as the input model (or output model of solver).
        Required to exist and contain files if `preconditioner`==True
    ***

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
"""

LBFGS_mem = 3

LBFGS_max

LBFGS_thresh = 0.0

_LBFGS_iter = 0

_memory_used = 0

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

2. L-BFGS internal iteration ticks over the maximum allowable number of

   iterations, force a restart condition, search direction is the inverse gradient

3. New search direction vector is too far from previous direction,

   force a restart, search direction is inverse gradient

4. New search direction is acceptably angled from previous,

   becomes the new search direction

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. The workflow will need to call compute_direction and initialize_search afterwards to properly re-instantiate the line search machinery.

_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)