L-BFGS storage. More...

#include <LBFGSStorage.hpp>

Public Member Functions
	LBFGSStorage (Eigen::Index n, Eigen::Index m, Scalar epsilon, OutputFunction &output_function)
	Construct a BFGS storage. More...

void	reset ()
	Reset the (inverse) Hessian approximation to identity matrix. More...

Vector< Scalar >	calculate_Hv (const Vector< Scalar > &v, const Vector< Scalar > &STv, const Vector< Scalar > &YTv)
	Calculate product of inverse Hessian approximation $\mathbf{H}$ with vector $\mathbf{v}$ . More...

Vector< Scalar >	calculate_Hv (const Vector< Scalar > &v)
	Calculate product of inverse Hessian approximation $\mathbf{H}$ with vector $\mathbf{v}$ . More...

Scalar	calculate_vHv (const Vector< Scalar > &v)
	Calculate normalized scalar product of vector $\mathbf{v}$ with inverse Hessian approximation $\mathbf{H}$ . More...

Vector< Scalar >	calculate_Bv (const Vector< Scalar > &v, const Vector< Scalar > &STv, const Vector< Scalar > &YTv)
	Calculate product of Hessian approximation $\mathbf{B}$ with vector $\mathbf{v}$ . More...

Vector< Scalar >	calculate_Bv (const Vector< Scalar > &v)
	Calculate product of Hessian approximation $\mathbf{B}$ with vector $\mathbf{v}$ . More...

Scalar	calculate_vBv (const Vector< Scalar > &v)
	Calculate normalized scalar product of vector $\mathbf{v}$ with Hessian approximation $\mathbf{B}$ . More...

Matrix< Scalar >	calculate_B ()
	Calculate the Hessian matrix approximation $\mathbf{B}$ . More...

bool	update (const Vector< Scalar > &s, const Vector< Scalar > &y, const Vector< Scalar > &g)
	Update the (inverse) Hessian approximation. More...

void	resize (Eigen::Index b)
	Function that resizes the storage to `b`. More...

Public Attributes
Eigen::Index	n
	Dimensionality of the problem.

Eigen::Index	m
	Maximal number of update pairs to store.

Eigen::Index	b
	Current number of stored update pairs.

Matrix< Scalar >	W
	working matrix

Matrix< Scalar >	M
	working matrix

Matrix< Scalar >	S
	matrix storing the last $\mathbf{s}$ vectors

Matrix< Scalar >	Y
	matrix storing the last $\mathbf{y}$ vectors

Matrix< Scalar >	R
	helper matrix

Matrix< Scalar >	L
	helper matrix

Matrix< Scalar >	D
	helper matrix

Matrix< Scalar >	YTY
	matrix storing $\mathbf{Y}^\intercal \mathbf{Y}$

Matrix< Scalar >	STS
	matrix storing $\mathbf{S}^\intercal \mathbf{S}$

Matrix< Scalar >	LOW
	working matrix

Matrix< Scalar >	UPP
	working matrix

Scalar	gamma = Scalar{1}
	current scaling of the inverse Hessian

Scalar	epsilon
	numerical stability check epsilon

OutputFunction &	output_function
	output function for status messages.

Detailed Description

template<typename Scalar, typename OutputFunction>
struct LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >

L-BFGS storage.

Template Parameters

Scalar The scalar type of vector/matrix coefficients.

This is the implementation of the limited memory BFGS algorithm. Here, the approximation of the (inverse) Hessian is stored as the last m update pairs.

It requires $\Theta(nm + m^2)$ storage.

We use the matrix representation described in

Byrd, R.H., Nocedal, J., Schnable, R.B. Representation of quasi-Newton matrices and their use in limited memory methods. 1994. Mathematical Programming. 63. 129-156.

Byrd, R.H., Lu, P., Nocedal, J., Zhu, C. A Limited Memory Algorithm for Bound Constrained Optimization. 1995. SIAM Journal of Scientific and Statistical Computing. 16(5). 1190-1208.

Constructor & Destructor Documentation

◆ LBFGSStorage()

template<typename Scalar , typename OutputFunction >

LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::LBFGSStorage	(	Eigen::Index	n,
		Eigen::Index	m,
		Scalar	epsilon,
		OutputFunction &	output_function
	)

Construct a BFGS storage.

Parameters

n	Dimensionality of the problem.
m	Number $(\mathbf{s}, \mathbf{y})$ update pairs to store.
epsilon	Small value for numerical stability check.
output_function	Output function for status messages.

Member Function Documentation

◆ calculate_B()

template<typename Scalar , typename OutputFunction >

Matrix< Scalar > LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::calculate_B ( )

Calculate the Hessian matrix approximation $\mathbf{B}$ .

Returns: The Hessian matrix approximation $\mathbf{B}$ .

Warning: This is only for debugging and testing. This can get very large and it undermines the limited-memory concept!

◆ calculate_Bv() [1/2]

template<typename Scalar , typename OutputFunction >

Vector< Scalar > LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::calculate_Bv	(	const Vector< Scalar > &	v,
		const Vector< Scalar > &	STv,
		const Vector< Scalar > &	YTv
	)

Calculate product of Hessian approximation $\mathbf{B}$ with vector $\mathbf{v}$ .

Parameters

v	Vector $\mathbf{v}$ for calculation.
STv	Product of the $\mathbf{S}^\intercal$ matrix with $\mathbf{v}$
YTv	Product of the $\mathbf{S}^\intercal$ matrix with $\mathbf{v}$

Returns: The product $\mathbf{B} \mathbf{v}$ .

Runtime $\Theta(mn)$ .

◆ calculate_Bv() [2/2]

template<typename Scalar , typename OutputFunction >

Vector< Scalar > LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::calculate_Bv ( const Vector< Scalar > & v )

Calculate product of Hessian approximation $\mathbf{B}$ with vector $\mathbf{v}$ .

Parameters

v	Vector $\mathbf{v}$ for calculation.

Returns: The product $\mathbf{B} \mathbf{v}$ .

Runtime $\Theta(mn)$ .

◆ calculate_Hv() [1/2]

template<typename Scalar , typename OutputFunction >

Vector< Scalar > LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::calculate_Hv	(	const Vector< Scalar > &	v,
		const Vector< Scalar > &	STv,
		const Vector< Scalar > &	YTv
	)

Calculate product of inverse Hessian approximation $\mathbf{H}$ with vector $\mathbf{v}$ .

Parameters

v	Vector $\mathbf{v}$ for calculation.
STv	Product of the $\mathbf{S}^\intercal$ matrix with $\mathbf{v}$
YTv	Product of the $\mathbf{S}^\intercal$ matrix with $\mathbf{v}$

Returns: The product $\mathbf{H} \mathbf{v}$ .

Runtime $\Theta(mn)$ .

◆ calculate_Hv() [2/2]

template<typename Scalar , typename OutputFunction >

Vector< Scalar > LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::calculate_Hv ( const Vector< Scalar > & v )

Calculate product of inverse Hessian approximation $\mathbf{H}$ with vector $\mathbf{v}$ .

Parameters

v	Vector $\mathbf{v}$ for calculation.

Returns: The product $\mathbf{H} \mathbf{v}$ .

Runtime $\Theta(mn)$ .

◆ calculate_vBv()

template<typename Scalar , typename OutputFunction >

Scalar LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::calculate_vBv ( const Vector< Scalar > & v )

Calculate normalized scalar product of vector $\mathbf{v}$ with Hessian approximation $\mathbf{B}$ .

Parameters

v	Vector $\mathbf{v}$ for calculation.

Returns: The normalized scalar product $\mathbf{v}^\intercal \mathbf{B} \mathbf{v}$ .

Runtime $\Theta(mn)$ .

Todo:: There is a formulation that calculates this in $\Theta(m^2)$ .

◆ calculate_vHv()

template<typename Scalar , typename OutputFunction >

Scalar LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::calculate_vHv ( const Vector< Scalar > & v )

Calculate normalized scalar product of vector $\mathbf{v}$ with inverse Hessian approximation $\mathbf{H}$ .

Parameters

v	Vector $\mathbf{v}$ for calculation.

Returns: The normalized scalar product $\mathbf{v}^\intercal \mathbf{H} \mathbf{v}$ .

Runtime $\Theta(mn)$ .

◆ reset()

template<typename Scalar , typename OutputFunction >

void LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::reset ( )

Reset the (inverse) Hessian approximation to identity matrix.

This function deletes all $(\mathbf{s}, \mathbf{y})$ update pairs.

Runtime $\Theta(n)$ .

◆ resize()

template<typename Scalar , typename OutputFunction >

void LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::resize ( Eigen::Index b )

Function that resizes the storage to b.

Parameters

b	New size of the storage.

If $ b < m $ , then the size of the storage is increased. Otherwise the oldest update pair is deleted.

Runtime $\Theta(mn + m^2)$ .

◆ update()

template<typename Scalar , typename OutputFunction >

bool LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >::update	(	const Vector< Scalar > &	s,
		const Vector< Scalar > &	y,
		const Vector< Scalar > &	g
	)

Update the (inverse) Hessian approximation.

Parameters

s	Change in x coordinate.
y	Change in gradient.
g	New gradient.

Returns: true if successful, false otherwise

The runtime of update is $4*n*m + \Theta(m^3)$

The $\Theta(m^3)$ part stems from the Cholesky decomposition and the inversion of $\mathbf{M}$ .

The documentation for this struct was generated from the following file:

include/LSLOpt/Implementation/LBFGSStorage.hpp

Public Member Functions

Public Attributes

Detailed Description

template<typename Scalar, typename OutputFunction> struct LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >

Constructor & Destructor Documentation

◆ LBFGSStorage()

Member Function Documentation

◆ calculate_B()

◆ calculate_Bv() [1/2]

◆ calculate_Bv() [2/2]

◆ calculate_Hv() [1/2]

◆ calculate_Hv() [2/2]

◆ calculate_vBv()

◆ calculate_vHv()

◆ reset()

◆ resize()

◆ update()

template<typename Scalar, typename OutputFunction>
struct LSLOpt::Implementation::LBFGSStorage< Scalar, OutputFunction >