#include <alpaqa/accelerators/lbfgs.hpp>

Detailed Description

template<Config Conf = DefaultConfig>
class alpaqa::LBFGS< Conf >

Limited memory Broyden–Fletcher–Goldfarb–Shanno (L-BFGS) algorithm.

Definition at line 108 of file lbfgs.hpp.

Collaboration diagram for LBFGS< Conf >:

Public Types
enum class	Sign { Positive , Negative }
	The sign of the vectors \( p \) passed to the update method. More...

using	Params = LBFGSParams< config_t >

Public Member Functions
	LBFGS ()=default

	LBFGS (Params params)

	LBFGS (Params params, length_t n)

bool	update_sy (crvec s, crvec y, real_t pₙₑₓₜᵀpₙₑₓₜ, bool forced=false)
	Update the inverse Hessian approximation using the new vectors sₖ = xₙₑₓₜ - xₖ and yₖ = pₙₑₓₜ - pₖ.

bool	update_sy_impl (const auto &s, const auto &y, real_t pₙₑₓₜᵀpₙₑₓₜ, bool forced=false)

bool	update (crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, Sign sign=Sign::Positive, bool forced=false)
	Update the inverse Hessian approximation using the new vectors xₙₑₓₜ and pₙₑₓₜ.

bool	apply (rvec q, real_t γ=-1) const
	Apply the inverse Hessian approximation to the given vector q.

bool	apply_masked (rvec q, real_t γ, crindexvec J) const
	Apply the inverse Hessian approximation to the given vector q, applying only the columns and rows of the Hessian in the index set J.

bool	apply_masked (rvec q, real_t γ, const std::vector< index_t > &J) const
	Apply the inverse Hessian approximation to the given vector q, applying only the columns and rows of the Hessian in the index set J.

bool	apply_masked_impl (rvec q, real_t γ, const auto &J) const
	Apply the inverse Hessian approximation to the given vector q, applying only the columns and rows of the Hessian in the index set J.

void	reset ()
	Throw away the approximation and all previous vectors s and y.

void	resize (length_t n)
	Re-allocate storage for a problem with a different size.

void	scale_y (real_t factor)
	Scale the stored y vectors by the given factor.

std::string	get_name () const
	Get a string identifier for this accelerator.

const Params &	get_params () const
	Get the parameters.

length_t	n () const
	Get the size of the s and y vectors in the buffer.

length_t	history () const
	Get the number of previous vectors s and y stored in the buffer.

index_t	succ (index_t i) const
	Get the next index in the circular buffer of previous s and y vectors.

index_t	pred (index_t i) const
	Get the previous index in the circular buffer of s and y vectors.

length_t	current_history () const
	Get the number of previous s and y vectors currently stored in the buffer.

auto	s (index_t i)

auto	s (index_t i) const

auto	y (index_t i)

auto	y (index_t i) const

real_t &	ρ (index_t i)

real_t &	ρ (index_t i) const

real_t &	α (index_t i)

real_t &	α (index_t i) const

template<class F >
void	foreach_fwd (const F &fun) const
	Iterate over the indices in the history buffer, oldest first.

template<class F >
void	foreach_rev (const F &fun) const
	Iterate over the indices in the history buffer, newest first.

Static Public Member Functions
static bool	update_valid (const Params &params, real_t yᵀs, real_t sᵀs, real_t pᵀp)
	Check if the new vectors s and y allow for a valid BFGS update that preserves the positive definiteness of the Hessian approximation.

Private Attributes
LBFGSStorage< config_t >	sto

index_t	idx = 0

bool	full = false

Params	params

Member Typedef Documentation

◆ Params

using Params = LBFGSParams<config_t>

Definition at line 112 of file lbfgs.hpp.

Member Enumeration Documentation

◆ Sign

enum class Sign

strong

The sign of the vectors \( p \) passed to the update method.

Enumerator
Positive	\( p \sim \nabla \psi(x) \)
Negative	\( p \sim -\nabla \psi(x) \)

Definition at line 115 of file lbfgs.hpp.

Constructor & Destructor Documentation

◆ LBFGS() [1/3]

LBFGS ( )

default

◆ LBFGS() [2/3]

LBFGS ( Params params )

inline

Definition at line 121 of file lbfgs.hpp.

◆ LBFGS() [3/3]

LBFGS	(	Params	params,
		length_t	n
	)

inline

Definition at line 122 of file lbfgs.hpp.

Here is the call graph for this function:

Member Function Documentation

◆ update_valid()

bool update_valid	(	const Params &	params,
		real_t	yᵀs,
		real_t	sᵀs,
		real_t	pᵀp
	)

static

Check if the new vectors s and y allow for a valid BFGS update that preserves the positive definiteness of the Hessian approximation.

Definition at line 12 of file lbfgs.tpp.

◆ update_sy()

bool update_sy	(	crvec	s,
		crvec	y,
		real_t	pₙₑₓₜᵀpₙₑₓₜ,
		bool	forced = `false`
	)

Update the inverse Hessian approximation using the new vectors sₖ = xₙₑₓₜ - xₖ and yₖ = pₙₑₓₜ - pₖ.

Definition at line 60 of file lbfgs.tpp.

◆ update_sy_impl()

bool update_sy_impl	(	const auto &	s,
		const auto &	y,
		real_t	pₙₑₓₜᵀpₙₑₓₜ,
		bool	forced = `false`
	)

See also: update_sy

Definition at line 37 of file lbfgs.tpp.

◆ update()

bool update	(	crvec	xₖ,
		crvec	xₙₑₓₜ,
		crvec	pₖ,
		crvec	pₙₑₓₜ,
		Sign	sign = `Sign::Positive`,
		bool	forced = `false`
	)

Update the inverse Hessian approximation using the new vectors xₙₑₓₜ and pₙₑₓₜ.

Definition at line 65 of file lbfgs.tpp.

Here is the caller graph for this function:

◆ apply()

bool apply	(	rvec	q,
		real_t	γ = `-1`
	)		const

Apply the inverse Hessian approximation to the given vector q.

Initial inverse Hessian approximation is set to \( H_0 = \gamma I \). If γ is negative, \( H_0 = \frac{s^\top y}{y^\top y} I \).

Definition at line 74 of file lbfgs.tpp.

Here is the caller graph for this function:

◆ apply_masked() [1/2]

bool apply_masked	(	rvec	q,
		real_t	γ,
		crindexvec	J
	)		const

Apply the inverse Hessian approximation to the given vector q, applying only the columns and rows of the Hessian in the index set J.

Definition at line 196 of file lbfgs.tpp.

◆ apply_masked() [2/2]

bool apply_masked	(	rvec	q,
		real_t	γ,
		const std::vector< index_t > &	J
	)		const

Apply the inverse Hessian approximation to the given vector q, applying only the columns and rows of the Hessian in the index set J.

Definition at line 201 of file lbfgs.tpp.

◆ apply_masked_impl()

bool apply_masked_impl	(	rvec	q,
		real_t	γ,
		const auto &	J
	)		const

Apply the inverse Hessian approximation to the given vector q, applying only the columns and rows of the Hessian in the index set J.

Definition at line 103 of file lbfgs.tpp.

◆ reset()

void reset

Throw away the approximation and all previous vectors s and y.

Definition at line 207 of file lbfgs.tpp.

Here is the caller graph for this function:

◆ resize()

void resize ( length_t n )

Re-allocate storage for a problem with a different size.

Causes a reset.

Definition at line 213 of file lbfgs.tpp.

Here is the caller graph for this function:

◆ scale_y()

void scale_y ( real_t factor )

Scale the stored y vectors by the given factor.

Definition at line 226 of file lbfgs.tpp.

Here is the caller graph for this function:

◆ get_name()

std::string get_name ( ) const

inline

Get a string identifier for this accelerator.

Definition at line 164 of file lbfgs.hpp.

◆ get_params()

const Params & get_params ( ) const

inline

Get the parameters.

Definition at line 168 of file lbfgs.hpp.

Here is the caller graph for this function:

◆ n()

length_t n ( ) const

inline

Get the size of the s and y vectors in the buffer.

Definition at line 171 of file lbfgs.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ history()

length_t history ( ) const

inline

Get the number of previous vectors s and y stored in the buffer.

Definition at line 173 of file lbfgs.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ succ()

index_t succ ( index_t i ) const

inline

Get the next index in the circular buffer of previous s and y vectors.

Definition at line 175 of file lbfgs.hpp.

Here is the call graph for this function:

◆ pred()

index_t pred ( index_t i ) const

inline

Get the previous index in the circular buffer of s and y vectors.

Definition at line 177 of file lbfgs.hpp.

Here is the call graph for this function:

◆ current_history()

length_t current_history ( ) const

inline

Get the number of previous s and y vectors currently stored in the buffer.

Definition at line 180 of file lbfgs.hpp.

Here is the call graph for this function:

◆ s() [1/2]

auto s ( index_t i )

inline

Definition at line 182 of file lbfgs.hpp.

Here is the call graph for this function:

◆ s() [2/2]

auto s ( index_t i ) const

inline

Definition at line 183 of file lbfgs.hpp.

Here is the call graph for this function:

◆ y() [1/2]

auto y ( index_t i )

inline

Definition at line 184 of file lbfgs.hpp.

Here is the call graph for this function:

◆ y() [2/2]

auto y ( index_t i ) const

inline

Definition at line 185 of file lbfgs.hpp.

Here is the call graph for this function:

◆ ρ() [1/2]

real_t & ρ ( index_t i )

inline

Definition at line 186 of file lbfgs.hpp.

Here is the call graph for this function:

◆ ρ() [2/2]

real_t & ρ ( index_t i ) const

inline

Definition at line 187 of file lbfgs.hpp.

Here is the call graph for this function:

◆ α() [1/2]

real_t & α ( index_t i )

inline

Definition at line 188 of file lbfgs.hpp.

Here is the call graph for this function:

◆ α() [2/2]

real_t & α ( index_t i ) const

inline

Definition at line 189 of file lbfgs.hpp.

Here is the call graph for this function:

◆ foreach_fwd()

void foreach_fwd ( const F & fun ) const

inline

Iterate over the indices in the history buffer, oldest first.

Definition at line 193 of file lbfgs.hpp.

Here is the call graph for this function:

◆ foreach_rev()

void foreach_rev ( const F & fun ) const

inline

Iterate over the indices in the history buffer, newest first.

Definition at line 204 of file lbfgs.hpp.

Here is the call graph for this function:

Member Data Documentation

◆ sto

LBFGSStorage<config_t> sto

private

Definition at line 214 of file lbfgs.hpp.

◆ idx

index_t idx = 0

private

Definition at line 215 of file lbfgs.hpp.

◆ full

bool full = false

private

Definition at line 216 of file lbfgs.hpp.

◆ params

Params params

private

Definition at line 217 of file lbfgs.hpp.

The documentation for this class was generated from the following files:

src/alpaqa/include/alpaqa/accelerators/lbfgs.hpp
src/alpaqa/include/alpaqa/implementation/accelerators/lbfgs.tpp

Detailed Description

Public Types

Public Member Functions

Static Public Member Functions

Private Attributes

Member Typedef Documentation

◆ Params

Member Enumeration Documentation

◆ Sign

Constructor & Destructor Documentation

◆ LBFGS() [1/3]

◆ LBFGS() [2/3]

◆ LBFGS() [3/3]

Member Function Documentation

◆ update_valid()

◆ update_sy()

◆ update_sy_impl()

◆ update()

◆ apply()

◆ apply_masked() [1/2]

◆ apply_masked() [2/2]

◆ apply_masked_impl()

◆ reset()

◆ resize()

◆ scale_y()

◆ get_name()

◆ get_params()

◆ n()

◆ history()

◆ succ()

◆ pred()

◆ current_history()

◆ s() [1/2]

◆ s() [2/2]

◆ y() [1/2]

◆ y() [2/2]

◆ ρ() [1/2]

◆ ρ() [2/2]

◆ α() [1/2]

◆ α() [2/2]

◆ foreach_fwd()

◆ foreach_rev()

Member Data Documentation

◆ sto

◆ idx

◆ full

◆ params