GALAHAD LMS package#

purpose#

Given a sequence of vectors $\{s_k\}$ and $\{y_k\}$ and scale factors $\{\delta_k\}$, the lms package obtains the product of a limited-memory secant approximation $H_k$ (or its inverse) with a given vector, using one of a variety of well-established formulae.

Currently only the options and inform dictionaries are exposed; these are provided and used by other GALAHAD packages with Python interfaces. Please contact us if you would like full functionality!

See Section 4 of $GALAHAD/doc/lms.pdf for additional details.

method#

Given a sequence of vectors $\{s_k\}$ and $\{y_k\}$ and scale factors $\delta_k$, a limited-memory secant approximation $H_k$ is chosen so that $H_{\max(k-m,0)} = \delta_k I$, $H_{k-j} s_{k-j} = y_{k-j}$ and $\| H_{k-j+1} - H_{k-j}\|$ is ``small’’ for $j = \min(k-1,m-1), \ldots, 0$. Different ways of quantifying ``small’’ distinguish different methods, but the crucial observation is that it is possible to construct $H_k$ quickly from $\{s_k\}$, $\{y_k\}$ and $\delta_k$, and to apply it and its inverse to a given vector $v$. It is also possible to apply similar formulae to the ``shifted’’ matrix $H_k + \lambda_k I$ that occurs in trust-region methods.

reference#

The basic methods are those given by

R. H. Byrd, J. Nocedal and R. B. Schnabel, ``Representations of quasi-Newton matrices and their use in limited memory methods’’. Mathematical Programming **63(2)* (1994) 129–156,

with obvious extensions.

parametric real type T#

Below, the symbol T refers to a parametric real type that may be Float32 (single precision) or Float64 (double precision). Calable functions as described are with T as Float64, but variants (with the additional suffix _s, e.g., lms_initialize_s) are available with T as Float32.

callable functions#

    function lms_initialize(data, control, status)

Parameters:

data

holds private internal data

control

is a structure containing control information (see lms_control_type)

status

is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently):

0
The initialization was successful.

    function lms_information(data, inform, status)

Provides output information

Parameters:

data

holds private internal data

inform

is a structure containing output information (see lms_inform_type)

status

is a scalar variable of type Int32 that gives the exit status from the package. Possible values are (currently):

0
The values were recorded successfully

    function lms_terminate(data, control, inform)

Deallocate all internal private storage

Parameters:

data	holds private internal data
control	is a structure containing control information (see lms_control_type)
inform	is a structure containing output information (see lms_inform_type)

available structures#

lms_control_type structure#

    struct lms_control_type{T}
      f_indexing::Bool
      error::Int32
      out::Int32
      print_level::Int32
      memory_length::Int32
      method::Int32
      any_method::Bool
      space_critical::Bool
      deallocate_error_fatal::Bool
      prefix::NTuple{31,Cchar}

detailed documentation#

control derived type as a Julia structure

components#

Bool f_indexing

use C or Fortran sparse matrix indexing

Int32 error

unit for error messages

Int32 out

unit for monitor output

Int32 print_level

controls level of diagnostic output

Int32 memory_length

limited memory length

Int32 method

limited-memory formula required (others may be added in due course):

1 BFGS (default).
2 Symmetric Rank-One (SR1).
3 The inverse of the BFGS formula.
4 The inverse of the shifted BFGS formula. This should be used instead of .method = 3 whenever a shift is planned.

Bool any_method

allow space to permit different methods if required (less efficient)

Bool space_critical

if space is critical, ensure allocated arrays are no bigger than needed

Bool deallocate_error_fatal

exit if any deallocation fails

NTuple{31,Cchar} prefix

all output lines will be prefixed by prefix(2:LEN(TRIM(.prefix))-1) where prefix contains the required string enclosed in quotes, e.g. “string” or ‘string’

lms_time_type structure#

    struct lms_time_type{T}
      total::T
      setup::T
      form::T
      apply::T
      clock_total::T
      clock_setup::T
      clock_form::T
      clock_apply::T

detailed documentation#

time derived type as a Julia structure

components#

T total

total cpu time spent in the package

T setup

cpu time spent setting up space for the secant approximation

T form

cpu time spent updating the secant approximation

T apply

cpu time spent applying the secant approximation

T clock_total

total clock time spent in the package

T clock_setup

clock time spent setting up space for the secant approximation

T clock_form

clock time spent updating the secant approximation

T clock_apply

clock time spent applying the secant approximation

lms_inform_type structure#

    struct lms_inform_type{T}
      status::Int32
      alloc_status::Int32
      length::Int32
      updates_skipped::Bool
      bad_alloc::NTuple{81,Cchar}
      time::lms_time_type{T}

detailed documentation#

inform derived type as a Julia structure

components#

Int32 status

the return status. Possible values are:

0

the update was successful.
-1

An allocation error occurred. A message indicating the offending array is written on unit control.error, and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.
-2

A deallocation error occurred. A message indicating the offending array is written on unit control.error and the returned allocation status and a string containing the name of the offending array are held in inform.alloc_status and inform.bad_alloc respectively.
-3

One of the restrictions $n > 0$, $\delta_k > 0$, $\lambda_k > 0$ or $s_k^T y_k > 0$ has been violated and the update has been skipped.
-10

The matrix cannot be built from the current vectors $\{s_k\}$ and $\{y_k\}$ and values $\delta_k$ and $\lambda_k$ and the update has been skipped.
-31

A call to the function lhs_apply has been made without a prior call to lhs_form_shift or lhs_form with lambda specified when control.method = 4, or lhs_form_shift has been called when control.method = 3, or lhs_change_method has been called after control.any_method = false was specified when calling lhs_setup.

Int32 alloc_status

the status of the last attempted allocation/deallocation

Int32 length

the number of pairs $(s_k,y_k)$ currently used to represent the limited-memory matrix.

Bool updates_skipped

have $(s_k,y_k)$ pairs been skipped when forming the limited-memory matrix?

NTuple{81,Cchar} bad_alloc

the name of the array for which an allocation/deallocation error occurred.

struct lms_time_type time

timings (see above)

Index