Direction providers

group grp_DirectionProviders

Algorithms that provide quasi-Newton steps for the PANOC solver, such as L-BFGS.

template<Config Conf>
struct PANOCDirection

#include <alpaqa/inner/directions/panoc-direction-update.hpp>

This class outlines the interface for direction providers used by PANOC-like algorithms.

Public Types

using Problem = TypeErasedProblem<config_t>

Public Functions

void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0) = delete

Initialize the direction provider.

The references problem, y and Σ are guaranteed to remain valid for subsequent calls to update, apply, changed_γ and reset.

Parameters:

• problem – [in] Problem description.

• y – [in] Lagrange multipliers.

• Σ – [in] Penalty factors.

• γ_0 – [in] Initial step size.

• x_0 – [in] Initial iterate.

• x̂_0 – [in] Result of proximal gradient step in x_0.

• p_0 – [in] Proximal gradient step in x_0.

• grad_ψx_0 – [in] Gradient of the objective in x_0.

bool has_initial_direction() const = delete

Return whether a direction is available on the very first iteration, before the first call to update.

bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ) = delete

Update the direction provider when accepting the next iterate.

Parameters:

• γₖ – [in] Current step size.

• γₙₑₓₜ – [in] Step size for the next iterate.

• xₖ – [in] Current iterate.

• xₙₑₓₜ – [in] Next iterate.

• pₖ – [in] Proximal gradient step in the current iterate.

• pₙₑₓₜ – [in] Proximal gradient step in the next iterate.

• grad_ψxₖ – [in] Gradient of the objective in the current iterate.

• grad_ψxₙₑₓₜ – [in] Gradient of the objective in the next iterate.

bool apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, rvec qₖ) const = delete

Apply the direction estimation in the current point.

Parameters:

• γₖ – [in] Current step size.

• xₖ – [in] Current iterate.

• x̂ₖ – [in] Result of proximal gradient step in xₖ.

• pₖ – [in] Proximal gradient step in xₖ.

• grad_ψxₖ – [in] Gradient of the objective at xₖ.

• qₖ – [out] Resulting step.

void changed_γ(real_t γₖ, real_t old_γₖ) = delete

Called when the PANOC step size changes.

void reset() = delete

Called when using the direction failed.

A possible behavior could be to flush the buffers, hopefully yielding a better direction on the next iteration.

std::string get_name() const = delete

Get a human-readable name for this direction provider.

template<Config Conf>
struct AndersonDirection

#include <alpaqa/inner/directions/panoc/anderson.hpp>

Public Types

using Problem = TypeErasedProblem<config_t>

using AndersonAccel = alpaqa::AndersonAccel<config_t>

using AcceleratorParams = typename AndersonAccel::Params

using DirectionParams = AndersonDirectionParams<config_t>

Public Functions

AndersonDirection() = default

inline AndersonDirection(const Params &params)

inline AndersonDirection(const typename AndersonAccel::Params &params, const DirectionParams &directionparams = {})

inline AndersonDirection(const AndersonAccel &anderson, const DirectionParams &directionparams = {})

inline AndersonDirection(AndersonAccel &&anderson, const DirectionParams &directionparams = {})

inline void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0)

See also

PANOCDirection::initialize

inline bool has_initial_direction() const

See also

PANOCDirection::has_initial_direction

inline bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ)

See also

PANOCDirection::update

inline bool apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, rvec qₖ) const

See also

PANOCDirection::apply

inline void changed_γ(real_t γₖ, real_t old_γₖ)

See also

PANOCDirection::changed_γ

inline void reset()

See also

PANOCDirection::reset

inline std::string get_name() const

See also

PANOCDirection::get_name

inline auto get_params() const

Public Members

mutable AndersonAccel anderson

DirectionParams direction_params

struct Params

#include <alpaqa/inner/directions/panoc/anderson.hpp>

Public Members

AcceleratorParams accelerator = {}

DirectionParams direction = {}

template<Config Conf>
struct LBFGSDirection

#include <alpaqa/inner/directions/panoc/lbfgs.hpp>

Public Types

using Problem = TypeErasedProblem<config_t>

using LBFGS = alpaqa::LBFGS<config_t>

using AcceleratorParams = typename LBFGS::Params

using DirectionParams = LBFGSDirectionParams<config_t>

Public Functions

LBFGSDirection() = default

inline LBFGSDirection(const Params &params)

inline LBFGSDirection(const typename LBFGS::Params &params, const DirectionParams &directionparams = {})

inline LBFGSDirection(const LBFGS &lbfgs, const DirectionParams &directionparams = {})

inline LBFGSDirection(LBFGS &&lbfgs, const DirectionParams &directionparams = {})

inline void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0)

See also

PANOCDirection::initialize

inline bool has_initial_direction() const

See also

PANOCDirection::has_initial_direction

inline bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ)

See also

PANOCDirection::update

inline bool apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, rvec qₖ) const

See also

PANOCDirection::apply

inline void changed_γ(real_t γₖ, real_t old_γₖ)

See also

PANOCDirection::changed_γ

inline void reset()

See also

PANOCDirection::reset

inline std::string get_name() const

See also

PANOCDirection::get_name

inline auto get_params() const

Public Members

LBFGS lbfgs

DirectionParams direction_params

struct Params

#include <alpaqa/inner/directions/panoc/lbfgs.hpp>

Public Members

AcceleratorParams accelerator = {}

DirectionParams direction = {}

template<Config Conf>
struct NoopDirection

#include <alpaqa/inner/directions/panoc/noop.hpp>

Direction provider that provides no directions (apply always returns false).

Public Types

using Problem = TypeErasedProblem<config_t>

using AcceleratorParams = void

using DirectionParams = void

Public Functions

NoopDirection() = default

inline void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0)

See also

PANOCDirection::initialize

inline bool has_initial_direction() const

See also

PANOCDirection::has_initial_direction

inline bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ)

See also

PANOCDirection::update

inline bool apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, rvec qₖ) const

See also

PANOCDirection::apply

inline void changed_γ(real_t γₖ, real_t old_γₖ)

See also

PANOCDirection::changed_γ

inline void reset()

See also

PANOCDirection::reset

inline std::string get_name() const

See also

PANOCDirection::get_name

inline void get_params() const

template<Config Conf = DefaultConfig>
struct StructuredLBFGSDirection

#include <alpaqa/inner/directions/panoc/structured-lbfgs.hpp>

Public Types

using Problem = TypeErasedProblem<config_t>

using LBFGS = alpaqa::LBFGS<config_t>

using AcceleratorParams = typename LBFGS::Params

using DirectionParams = StructuredLBFGSDirectionParams<config_t>

Public Functions

StructuredLBFGSDirection() = default

inline StructuredLBFGSDirection(const Params &params)

inline StructuredLBFGSDirection(const typename LBFGS::Params &params, const DirectionParams &directionparams = {})

inline StructuredLBFGSDirection(const LBFGS &lbfgs, const DirectionParams &directionparams = {})

inline StructuredLBFGSDirection(LBFGS &&lbfgs, const DirectionParams &directionparams = {})

void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0)

See also

PANOCDirection::initialize

inline bool has_initial_direction() const

See also

PANOCDirection::has_initial_direction

inline bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ)

See also

PANOCDirection::update

bool apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, rvec qₖ) const

See also

PANOCDirection::apply

inline void changed_γ(real_t γₖ, real_t old_γₖ)

See also

PANOCDirection::changed_γ

inline void reset()

See also

PANOCDirection::reset

inline std::string get_name() const

See also

PANOCDirection::get_name

inline auto get_params() const

Public Members

DirectionParams direction_params

struct Params

#include <alpaqa/inner/directions/panoc/structured-lbfgs.hpp>

Public Members

AcceleratorParams accelerator = {}

DirectionParams direction = {}

template<Config Conf = DefaultConfig>
struct StructuredNewtonDirection

#include <alpaqa/inner/directions/panoc/structured-newton.hpp>

Public Types

using Problem = TypeErasedProblem<config_t>

using DirectionParams = StructuredNewtonDirectionParams<config_t>

using AcceleratorParams = StructuredNewtonRegularizationParams<config_t>

Public Functions

StructuredNewtonDirection() = default

inline StructuredNewtonDirection(const Params &params)

inline StructuredNewtonDirection(const AcceleratorParams &params, const DirectionParams &directionparams = {})

inline void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0)

See also

PANOCDirection::initialize

inline bool has_initial_direction() const

See also

PANOCDirection::has_initial_direction

inline bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ)

See also

PANOCDirection::update

inline bool apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, rvec qₖ) const

See also

PANOCDirection::apply

inline void changed_γ(real_t γₖ, real_t old_γₖ)

See also

PANOCDirection::changed_γ

inline void reset()

See also

PANOCDirection::reset

inline std::string get_name() const

See also

PANOCDirection::get_name

inline const auto &get_params() const

Public Members

AcceleratorParams reg_params

DirectionParams direction_params

struct Params

#include <alpaqa/inner/directions/panoc/structured-newton.hpp>

Public Members

AcceleratorParams accelerator = {}

DirectionParams direction = {}

template<Config Conf>
struct NewtonTRDirection

#include <alpaqa/inner/directions/pantr/newton-tr.hpp>

Public Types

using Problem = TypeErasedProblem<config_t>

using AcceleratorParams = SteihaugCGParams<config_t>

using DirectionParams = NewtonTRDirectionParams<config_t>

Public Functions

NewtonTRDirection() = default

inline NewtonTRDirection(const Params &params)

inline NewtonTRDirection(const AcceleratorParams &params, const DirectionParams &directionparams = {})

inline void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0)

See also

PANTRDirection::initialize

inline bool has_initial_direction() const

See also

PANTRDirection::has_initial_direction

inline bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ)

See also

PANTRDirection::update

inline real_t apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, real_t radius, rvec qₖ) const

See also

PANTRDirection::apply

inline void changed_γ(real_t γₖ, real_t old_γₖ)

See also

PANTRDirection::changed_γ

inline void reset()

See also

PANTRDirection::reset

inline std::string get_name() const

See also

PANTRDirection::get_name

inline auto get_params() const

Public Members

SteihaugCG<config_t> steihaug

DirectionParams direction_params

const Problem *problem = nullptr

std::optional<crvec> y = std::nullopt

std::optional<crvec> Σ = std::nullopt

mutable indexvec JK_sto

mutable vec rJ_sto

mutable vec qJ_sto

mutable vec work

vec work_2

vec work_n_fd

vec work_m_fd

struct Params

#include <alpaqa/inner/directions/pantr/newton-tr.hpp>

Public Members

AcceleratorParams accelerator = {}

DirectionParams direction = {}

template<Config Conf>
struct PANTRDirection

#include <alpaqa/inner/directions/pantr/pantr-direction.hpp>

This class outlines the interface for direction providers used by PANTR-like algorithms.

Public Types

using Problem = TypeErasedProblem<config_t>

Public Functions

void initialize(const Problem &problem, crvec y, crvec Σ, real_t γ_0, crvec x_0, crvec x̂_0, crvec p_0, crvec grad_ψx_0) = delete

Initialize the direction provider.

The references problem, y and Σ are guaranteed to remain valid for subsequent calls to update, apply, changed_γ and reset.

Parameters:

• problem – [in] Problem description.

• y – [in] Lagrange multipliers.

• Σ – [in] Penalty factors.

• γ_0 – [in] Initial step size.

• x_0 – [in] Initial iterate.

• x̂_0 – [in] Result of proximal gradient step in x_0.

• p_0 – [in] Proximal gradient step in x_0.

• grad_ψx_0 – [in] Gradient of the objective in x_0.

inline bool has_initial_direction() const

Return whether a direction is available on the very first iteration, before the first call to update.

bool update(real_t γₖ, real_t γₙₑₓₜ, crvec xₖ, crvec xₙₑₓₜ, crvec pₖ, crvec pₙₑₓₜ, crvec grad_ψxₖ, crvec grad_ψxₙₑₓₜ) = delete

Update the direction provider when accepting the next iterate.

Parameters:

• γₖ – [in] Current step size.

• γₙₑₓₜ – [in] Step size for the next iterate.

• xₖ – [in] Current iterate.

• xₙₑₓₜ – [in] Next iterate.

• pₖ – [in] Proximal gradient step in the current iterate.

• pₙₑₓₜ – [in] Proximal gradient step in the next iterate.

• grad_ψxₖ – [in] Gradient of the objective in the current iterate.

• grad_ψxₙₑₓₜ – [in] Gradient of the objective in the next iterate.

real_t apply(real_t γₖ, crvec xₖ, crvec x̂ₖ, crvec pₖ, crvec grad_ψxₖ, real_t radius, rvec qₖ) const = delete

Compute the direction in the given point.

Parameters:

• γₖ – [in] Current step size.

• xₖ – [in] Current iterate.

• x̂ₖ – [in] Result of proximal gradient step in xₖ.

• pₖ – [in] Proximal gradient step in xₖ.

• grad_ψxₖ – [in] Gradient of the objective at xₖ.

• radius – [in] Trust radius Δ.

• qₖ – [out] Resulting step.

Returns:

Model decrease.

void changed_γ(real_t γₖ, real_t old_γₖ) = delete

Called when the PANTR step size changes.

void reset() = delete

Called when using the direction failed.

A possible behavior could be to flush the buffers, hopefully yielding a better direction on the next iteration.

std::string get_name() const = delete

Get a human-readable name for this direction provider.