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 = 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.