Generalized Cauchy direction sub solver

The generalized Cauchy direction (GCD) sub solver is a component in optimization algorithms that handle problems with bound constraints [BBP26]. It solves the following problem

\[\begin{align*} \operatorname*{arg\,min}_{Y ∈ T_p (D \times \mathcal{M})}&\ m_p(Y), \qquad m_p(Y) = ⟨X_g, Y⟩_p + \frac{1}{2} ⟨\mathcal{H}_p[Y], Y⟩_p\\ \text{such that}& \ \exp_p(Y) = \exp_p(\alpha X) \in D \times \mathcal{M} \text{ for some } \alpha \in [0, A] \end{align*}\]

where $X=(X_{\mathrm{D}}, X_{\mathcal{M}})$ is a given direction, the exponential map handles projection of the tangent vector when reaching the boundary, $D$ is a box domain (Hyperrectangle), $\mathcal{M}$ is a Riemannian manifold, $X_g$ is the gradient of a scalar function $f$ at point $p=(p_{\mathrm{D}}, p_{\mathcal{M}})$, $A$ is the maximum allowed step size on $\mathcal{M}$ at point $p=(p_{\mathrm{D}}, p_{\mathcal{M}})$ in direction $X_{\mathcal{M}}$ (infinity is supported) and $\mathcal{H}_p$ is a linear operator that approximates the Hessian of $f$ at $p$.

Additionally, the sub solver indicates whether the selected direction $Y$ reaches the boundary of $D$ at some point, in which case the subsequent step size selection in direction $Y$ needs to be limited to the interval $[0, s_{\max}]$, where the number $1 ≤ s_{\max} ≤ ∞$ is also returned by the sub solver. Note that the value $s_{\max}=1$ is obtained when the minimum lies at the boundary of $D$, while larger values indicate that we are further away from the boundary along the selected direction $Y$.

The solver is currently primarily intended for internal use by optimization algorithms that require bound-constrained sub problem solutions.

Simple step size limiting

In case there is no Hessian approximation available, a simple step size limiting procedure can be used to limit the step size in direction $X$ to the maximum allowed by the boundary of $D$ and the maximum allowed step size on $\mathcal{M}$. This procedure is available using the following:

Manopt.MaxStepsizeInDirectionSubsolver — Type
MaxStepsizeInDirectionSubsolver{TFT, TBI}

Helper container for finding the maximum stepsize in a direction.

Fields

  • F_list::Vector{TFT}: the bounds met along the direction, as (stepsize, index) pairs
  • bounds_indices::TBI: the indices of the components that are bounded

Constructor

MaxStepsizeInDirectionSubsolver(M::AbstractManifold, p)

Initialize the MaxStepsizeInDirectionSubsolver for manifold M and point p. The F_list is initialized to be empty and will be populated during the search for the maximum stepsize in a direction. Floating point type of the elements bounds in F_list is determined by the number type of p.

The MaxStepsizeInDirectionSubsolver can be reused for multiple different points and directions on the same manifold, but it is not thread-safe.

source
Manopt.find_max_stepsize_in_direction — Function
find_max_stepsize_in_direction(M::AbstractManifold, gcd::MaxStepsizeInDirectionSubsolver, p, d)

Find the maximum stepsize that can be performed from point p in direction d.

The function returns a pair (status, maxstepsize) where status is a symbol describing the result of the search, and `maxstepsizeis the maximum stepsize that can be taken frompin the directiond`.

The status can be one of the following:

  • :found_limited if a finite bound exists; max_stepsize is then the smallest positive stepsize bound,
  • :found_unlimited if no finite bound exists; max_stepsize is then Inf,
  • :not_found if no positive stepsize bound exists at all; max_stepsize is then NaN.
source

Internal types and methods

These symbols are directly used by solvers to compute the descent direction corresponding to the Generalized Cauchy direction.

Manopt.has_anisotropic_max_stepsize — Function
Manopt.has_anisotropic_max_stepsize(::Hyperrectangle)

Returns true, as Hyperrectangle manifold requires generalized Cauchy point computation in solvers.

source
has_anisotropic_max_stepsize(M::AbstractManifold)

Return true if M has a max_stepsize that depends on the direction, for example if M is a Hyperrectangle-like manifold with corners, or a product of it with a standard manifold. Otherwise return false.

source
Manopt.find_generalized_cauchy_direction! — Function
find_generalized_cauchy_direction!(
    M::AbstractManifold,
    gcd::GeneralizedCauchyDirectionSubsolver, d_out, p, d, X
)

Find generalized Cauchy direction looking from point p on manifold M in direction d and save it to d_out. Gradient of the objective at p is X.

Elements of d that point out of the box at a variable that is already at its bound (that is, with a zero breakpoint) are set to zero before the search, so the piecewise quadratic model is minimized along the projected path of d.

The function returns a pair (status, maxstepsize) where status is a symbol describing the result of the search, and `maxstepsizeis the maximum stepsize that can be taken in the directiond_out`.

The status can be one of the following:

  • :found_limited if the point was found and a step of length at most the returned max_stepsize, which is at least 1, can be performed in direction d_out afterwards,
  • :found_unlimited if the point was found and we can perform a step of length at most max_stepsize(M, p, d_out) in direction d_out afterwards,
  • :not_found if d, with the elements described above set to zero, is not a descent direction of the model, or vanishes. In this case d_out is set to the zero vector.
source
Manopt.GeneralizedCauchyDirectionSubsolver — Type
GeneralizedCauchyDirectionSubsolver{TX, T_HA, TFU <: AbstractSegmentHessianUpdater, TFT, TBI, TO}

Helper container for generalized Cauchy direction search. Stores a buffer for the search direction projected onto the tangent cone at the bounds (d_projected), the quasi-Newton direction update ha, the hessian_segment_updater, which computes certain values of the Hessian while advancing segments, the list of bounds F_list, the bound indices bounds_indices, and the heap ordering. Instances are reused across segments during find_generalized_cauchy_direction! to avoid allocations.

source

These symbols are used to evaluate the Hessian approximation at specific tangent vectors during the generalized Cauchy direction computation.

Manopt.hessian_value — Function
hessian_value(d::QuasiNewtonMatrixDirectionUpdate, M, p, X::UnitVector, Y)

Evaluate the quadratic form associated with the stored quasi-Newton matrix. Returns the scalar $c_b^{\mathrm{T}} B c$ where $c_b$ are the coordinates of the UnitVector X at p (assumed to correspond to the basis d.basis), $c$ are the coordinates of the tangent vector Y at p (in the basis d.basis) and $B$ is d.matrix.

source
hessian_value(gh::QuasiNewtonLimitedMemoryBoxDirectionUpdate, M::AbstractManifold, p, X::UnitVector, Y)

Compute $⟨X, B Y⟩$, where $B$ is the (1, 1)-Hessian represented by gh, where X is the UnitVector.

source
hessian_value(ha::LevenbergMarquardtBoxSubsolver, M, p, X::UnitVector, Y)

Evaluate the quadratic form associated with the stored Hessian approximation.

source
hessian_value(ha::CoordinatesNormalSystemState, M, p, X::UnitVector, Y)

Evaluate the quadratic form associated with the stored Hessian approximation. Returns the scalar $c_b^{\top} A c$ where $c_b$ are the coordinates of the UnitVector X at p (assumed to correspond to the basis ha.basis), $c$ are the coordinates of the tangent vector Y at p (in the basis ha.basis) and $A$ is ha.A.

source
Manopt.hessian_value_diag — Function
hessian_value_diag(d::QuasiNewtonMatrixDirectionUpdate, M, p, X)

Evaluate the quadratic form associated with the stored quasi-Newton matrix. Returns the scalar $c^{\mathrm{T}} B c$ where $c$ are the coordinates of the tangent vector X at p (in the basis d.basis) and $B$ is d.matrix.

source
hessian_value_diag(d::QuasiNewtonMatrixDirectionUpdate, M, p, X::UnitVector)

Evaluate the quadratic form associated with the stored quasi-Newton matrix. Returns the scalar $c^{\mathrm{T}} B c$ where $c$ are the coordinates of the UnitVector X at p (in the basis d.basis) and $B$ is d.matrix.

source
hessian_value_diag(gh::QuasiNewtonLimitedMemoryBoxDirectionUpdate, M::AbstractManifold, p, X)

Compute $⟨X, B X⟩$, where $B$ is the (1, 1)-Hessian represented by gh.

source
hessian_value_diag(gh::QuasiNewtonLimitedMemoryBoxDirectionUpdate, M::AbstractManifold, p, X::UnitVector)

Compute $⟨X, B X⟩$, where $B$ is the (1, 1)-Hessian represented by gh, and X is the UnitVector.

source
hessian_value_diag(ha::LevenbergMarquardtBoxSubsolver, M, p, X)

Evaluate the quadratic form associated with the stored Hessian approximation.

source
hessian_value_diag(ha::CoordinatesNormalSystemState, M::AbstractManifold, p, X::UnitVector)

Evaluate the quadratic form associated with the Hessian approximation of a CoordinatesNormalSystemState. Returns the scalar $c^{\top} A c$ where $c$ are the coordinates of the UnitVector X at p (in the basis ha.basis) and $A$ is ha.A.

source
hessian_value_diag(ha::CoordinatesNormalSystemState, M::AbstractManifold, p, X)

Evaluate the quadratic form associated with the Hessian approximation of a CoordinatesNormalSystemState. Returns the scalar $c^{\top} A c$ where $c$ are the coordinates of X at p (in the basis ha.basis) and $A$ is ha.A.

source

These are internal symbols used to manage and manipulate bound constraints during the GCD computation.

Manopt.init_updater! — Function
init_updater!(::AbstractManifold, hessian_segment_updater::AbstractSegmentHessianUpdater, p, d, ha)

Method for initialization of AbstractSegmentHessianUpdater hessian_segment_updater just before the loop that examines subsequent intervals for GCD.

source
Manopt.UnitVector — Type
UnitVector{TB}

A type representing a unit tangent vector on a Hyperrectangle-like manifold with corners, or a product of it with a standard manifold. The field index stores the index of the element equal to 1. All other elements are equal to 0.

source
Manopt.to_coordinate_index — Function
to_coordinate_index(M::AbstractManifold, b::UnitVector{Int}, B::AbstractBasis)

Get the index of coordinate equal to 1 of UnitVector b with respect to AbstractBasis B.

source
to_coordinate_index(M::ProductManifold, b::UnitVector{Tuple{Int, Int}}, B::AbstractBasis)

Get the index of coordinate equal to 1 of UnitVector b with respect to AbstractBasis B.

source
Manopt.GenericSegmentHessianUpdater — Type
GenericSegmentHessianUpdater{TX} <: AbstractSegmentHessianUpdater

Generic f' and f'' calculation that only relies on hessian_value but is relatively slow for high-dimensional domains.

Fields

  • d_z::TX: the accumulated direction of the segments walked so far
  • d_tmp::TX: the current direction, with the components that reached a bound set to zero
source
Manopt.get_bounds_index — Function
get_bounds_index(::Hyperrectangle)

Get the bound indices of Hyperrectangle M. They are the same as the indices of the lower (or upper) bounds.

source
get_bounds_index(::AbstractManifold)

Get the bound indices of manifold M. Standard manifolds don't have bounds, so Base.OneTo(0), that is an empty range, is returned.

source
Manopt.get_stepsize_bound — Function
get_stepsize_bound(M::Hyperrectangle, p, d, i)

Get the upper bound on moving in direction d from point p on Hyperrectangle M, for the bound index i. There are three cases:

  1. If d[i] > 0, the formula reads (M.ub[i] - p[i]) / d[i].
  2. If d[i] < 0, the formula reads (M.lb[i] - p[i]) / d[i].
  3. If d[i] == 0, the result is Inf.
source
get_stepsize_bound(M::AbstractManifold, p, d, i)

Get the upper bound on moving in direction d from point p on manifold M, for the bound index i.

source
Manopt.set_stepsize_bound! — Function
Manopt.set_stepsize_bound!(M::Hyperrectangle, d_out, p, d, t_current::Real)

Limit the per-component stepsize in d_out to the bound imposed by the box constraints.

For each element i in the tangent vector d_out, if the stepsize bound in direction d for that element is less than t_current, set the element of d_out to the distance from p[i] to the bound in the direction of d[i]. If the stepsize bound is non-positive, set the element to 0.

source
set_stepsize_bound!(M::AbstractManifold, d_out, p, d, t_current::Real)

Limit the per-component stepsize in d_out to the bound imposed by the box constraints.

For each component at index i in the tangent vector d_out, if the stepsize bound in direction d for that component is less than t_current, set the element of d_out to the distance from p[i] to the bound in the direction of d[i]. If the stepsize bound is non-positive, set the element to 0.

By default it does not modify d_out because most manifolds don't have direction-specific stepsize bounds, and general anisotropic bounds are handled differently.

source
Manopt.set_zero_at_index! — Function
Manopt.set_zero_at_index!(M::Hyperrectangle, d, i)

Set element of tangent vector d on Hyperrectangle at index i to 0.

source
set_zero_at_index!(M::ProductManifold, d, i::Tuple{Int,Any})

Set the element of the i[1]th component of d at bound index i[2] to zero.

source
Manopt.zero_at_active_bounds! — Function
Manopt.zero_at_active_bounds!(M::Hyperrectangle, Y, p, X)

Set the elements Y[i] of the tangent vector Y at p on Hyperrectangle M to zero, for which p[i] ≤ M.lb[i] and X[i] > 0, or p[i] ≥ M.ub[i] and X[i] < 0.

source
zero_at_active_bounds!(M::AbstractManifold, Y, p, X)

Set the elements of the tangent vector Y at p to zero that belong to variables held at their bounds according to the gradient X at p, that is variables at a lower bound with a positive element of X or at an upper bound with a negative element of X. The negative gradient points out of the box for these variables. Variables with equal lower and upper bounds are hence always held, unless their element of X vanishes. Y may alias X.

By default Y is not modified, since most manifolds don't have box constraints.

source
Manopt.isotropic_max_stepsize — Function
isotropic_max_stepsize(M::AbstractManifold, p)

Return the smallest maximal step size max_stepsize(N, q) among the components N of the product manifold M, at the corresponding components q of p, that do not have an anisotropic maximal step size. Return Inf if there is no such component, and for manifolds that are not product manifolds. These are the limits that find_generalized_cauchy_direction! imposes on the manifold components of the search direction.

source
Manopt.project_truncate — Function
project_truncate(M::AbstractManifold, p, X)
project_truncate!(M::AbstractManifold, Y, p, X)

Project the tangent vector X at p onto the set of tangent vectors $Z$ for which $\exp_p Z$ satisfies the box constraints of M, that is, compute

\[Y = \log_p P(\exp_p X),\]

where $P$ denotes the projection onto the box constraints. The in-place variant can also be called with Y and X being the same tangent vector.

  • On a Hyperrectangle with bounds $l$ and $u$, this is $Y = \operatorname{clamp}(p + X, l, u) - p$.
  • On a product manifold, Y is computed componentwise.
  • On manifolds without box constraints, this is $Y = X$, projected onto the tangent space at p with embed_project! for numerical stability.

The set X is projected onto is contained in the tangent cone at p. Unlike the tangent cone, it changes continuously with p, and Y depends continuously on p and X.

For example, for the negative gradient $X = -\operatorname{grad} f(p)$, Y is the projected negative gradient of L-BFGS-B [BLNZ95]. Its norm vanishes exactly at the stationary points of the problem and is used as a criticality measure by StopWhenProjectedNegativeGradientNormLess and model_decrease_reference.

source
Manopt.project_truncate! — Function
Manopt.project_truncate!(M::Hyperrectangle, Y, p, X)

Compute Y = clamp.(p .+ X, M.lb, M.ub) .- p on Hyperrectangle M, the step from p to the projection of p + X onto M.

source
project_truncate(M::AbstractManifold, p, X)
project_truncate!(M::AbstractManifold, Y, p, X)

Project the tangent vector X at p onto the set of tangent vectors $Z$ for which $\exp_p Z$ satisfies the box constraints of M, that is, compute

\[Y = \log_p P(\exp_p X),\]

where $P$ denotes the projection onto the box constraints. The in-place variant can also be called with Y and X being the same tangent vector.

  • On a Hyperrectangle with bounds $l$ and $u$, this is $Y = \operatorname{clamp}(p + X, l, u) - p$.
  • On a product manifold, Y is computed componentwise.
  • On manifolds without box constraints, this is $Y = X$, projected onto the tangent space at p with embed_project! for numerical stability.

The set X is projected onto is contained in the tangent cone at p. Unlike the tangent cone, it changes continuously with p, and Y depends continuously on p and X.

For example, for the negative gradient $X = -\operatorname{grad} f(p)$, Y is the projected negative gradient of L-BFGS-B [BLNZ95]. Its norm vanishes exactly at the stationary points of the problem and is used as a criticality measure by StopWhenProjectedNegativeGradientNormLess and model_decrease_reference.

source
Manopt.LimitedMemorySegmentHessianUpdater — Type
LimitedMemorySegmentHessianUpdater{TV <: AbstractVector} <: AbstractSegmentHessianUpdater

Hessian value calculation for generalized Cauchy direction line segments that is optimized for QuasiNewtonLimitedMemoryBoxDirectionUpdate. It relies on a specific Hessian structure.

Fields

  • p_s::TV: the inner products of the stored $s_k$ with the current direction
  • p_y::TV: the inner products of the stored $y_k$ with the current direction
  • c_s::TV: the inner products of the stored $s_k$ with the accumulated direction $d_z$
  • c_y::TV: the inner products of the stored $y_k$ with the accumulated direction $d_z$
source
Manopt.hessian_value_from_inner_products — Function
hessian_value_from_inner_products(gh::QuasiNewtonLimitedMemoryBoxDirectionUpdate, iss::Real, cy1, cs1, cy2, cs2)

Evaluate the quadratic form defined by the current blockwise Hessian approximation stored in gh, given precomputed coordinate vectors.

Arguments:

  • iss: inner product of original vectors.
  • cy1, cy2: coordinates of $y$-like vectors in the $Y_k$ basis.
  • cs1, cs2: coordinates of $s$-like vectors in the scaled $S_k$ basis.

The result is $θ·iss - cy₁ᵀ M₁₁ cy₂ - cs₁ᵀ M₂₁ cy₂ - cs₂ᵀ M₂₁ cy₁ - cs₁ᵀ M₂₂ cs₂$ using the blocks $M₁₁$, $M₂₁$, $M₂₂$ stored in gh and the current scale $θ$. Returns the scalar value.

source
Manopt.update_current_scale! — Function
update_current_scale!(M::AbstractManifold, p, gh::QuasiNewtonLimitedMemoryBoxDirectionUpdate)

Refresh the scaling factor and blockwise Hessian approximation stored in gh using the nonzero curvature pairs currently in memory.

  • Identifies the most recent index with nonzero $ρ_i$ to scale the initial Hessian guess by $ρ_i‖y_i‖^2 / θ$.
  • Builds $L_k$ and $S_k^\top S_k$ from the stored $(s_i, y_i)$ pairs and updates the block matrices $M₁₁$, $M₂₁$, and $M₂₂$ via the blockwise inverse formula.
  • If all $ρ_i$ vanish, resets current_scale to the inverse of initial_scale and clears the block matrices.

Returns the mutated gh.

source
Manopt.hessian_norm_bound — Function
hessian_norm_bound(gh::QuasiNewtonLimitedMemoryBoxDirectionUpdate, M::AbstractManifold, p)

Return an upper bound $\hat λ$ on the largest eigenvalue of the Hessian approximation $B$ stored in gh,

\[\hat λ = θ + \sum_{i} \frac{\lVert y_i \rVert^2}{⟨s_i, y_i⟩},\]

where $θ$ is the current scale and the sum runs over the stored pairs with $⟨s_i, y_i⟩ > 0$. $B$ results from BFGS updates of $θ \operatorname{Id}$, each of which subtracts a positive semidefinite rank-one term and adds $\frac{y_i y_i^{\mathrm{T}}}{⟨s_i, y_i⟩}$. By Weyl's inequality, the largest eigenvalue increases by at most $\frac{\lVert y_i\rVert^2}{⟨s_i, y_i⟩}$ per update.

source
Manopt.model_decrease_reference — Function
model_decrease_reference(gh::QuasiNewtonLimitedMemoryBoxDirectionUpdate, M::AbstractManifold, p, X, Y)

Compute the reference value $ψ$ for the sufficient decrease test of the generalized Cauchy direction in QuasiNewtonLimitedMemoryBoxDirectionUpdate,

\[ψ = \frac{h^2}{\lVert X \rVert} \min\Bigl\{\frac{h}{\max\{1, \hat λ\}},\ t_{\max}\Bigr\},\]

where $X$ is the gradient at $p$, $h$ is the norm of the projected negative gradient project_truncate(M, p, -X), $\hat λ$ is the bound from hessian_norm_bound, and $t_{\max}$ is the isotropic_max_stepsize. Y is used as a buffer for the projected negative gradient. If $h = 0$, $ψ = 0$.

The value mimics the lower bound on the model decrease achieved by the generalized Cauchy point along the projected negative gradient from [CGT88, Lemma 5]. There, the bounds on the norm of the gradient and of the Hessian approximation are replaced by $\lVert X \rVert$ and $\hat λ$. If the quasi-Newton step $-B^{-1}X$ is feasible and does not exceed the maximal step size, it is the generalized Cauchy direction, and its model decrease $\frac{1}{2}⟨X, B^{-1}X⟩ ≥ \frac{\lVert X \rVert^2}{2\hat λ}$ is at least $ψ/2$.

source

Literature

[BBP26]
M. Baran, R. Bergmann and P. Przybysz. A Riemannian quasi-Newton algorithm for optimization with Euclidean bounds (2026), arXiv:2605.10573 [math.OC].
[BLNZ95]
R. H. Byrd, P. Lu, J. Nocedal and C. Zhu. A Limited Memory Algorithm for Bound Constrained Optimization. SIAM Journal on Scientific Computing 16, 1190–1208 (1995). Publisher: Society for Industrial and Applied Mathematics.
[CGT88]
A. R. Conn, N. I. Gould and P. L. Toint. Global Convergence of a Class of Trust Region Algorithms for Optimization with Simple Bounds. SIAM Journal on Numerical Analysis 25, 433–460 (1988).