API Reference

AbstractDFProjectionAlgorithm

Supertype for all derivative-free projection algorithms in DFMethods. Concrete subtypes (e.g., DFProjection in algorithm.jl) wire together a search direction, a line search, an inertial rule, and a constraint set.

Subtypes SciMLBase.AbstractNonlinearAlgorithm, so every concrete algorithm participates in solve(prob::NonlinearProblem, alg; kwargs...) out of the box.

DFProjection(; direction, linesearch, inertial, set,
               abstol, maxiters, stopping, ζ, inner_maxiter, maxbt)

Concrete derivative-free projection algorithm. Each component is swappable; defaults reproduce the Ibrahim 2026 paper setup (SpectralThreeTerm direction, LSII line search, Inertial(0.25), paper ζ = 0.5).

Fields

• direction::AbstractSearchDirection — search-direction rule. Default: SpectralThreeTerm().
• linesearch::AbstractDFLineSearch — line search. Default: LSII().
• inertial::AbstractInertialRule — inertial rule. Default: Inertial(0.25).
• set::AbstractConstraintSet — feasible set $X$. Default: RealSpace().
• abstol::Float64 — residual tolerance used to build the default stopping. Default: 1e-6.
• maxiters::Int — outer-iteration cap used to build the default stopping. Default: 2000.
• stopping::AbstractStoppingCriterion — full stopping rule. If not supplied, built as AnyOf(AbsResidualTol(abstol), MaxIters(maxiters)).
• ζ::Float64 — approximate-projection tolerance factor (paper ζ_k ≡ ζ). Default: 0.5.
• inner_maxiter::Int — max Dykstra iterations inside approx_project_X_halfspace!. Default: 500.
• maxbt::Int — max line-search backtracks per iteration. Default: 50.

Stopping criteria

abstol and maxiters are convenience knobs that build the default stopping rule. For composite or domain-specific criteria, pass stopping = AnyOf(RelResidualTol(...), StepNormTol(...), MaxTime(...), …); the abstol/maxiters fields are still stored (for introspection and SciMLBase kwarg overrides) but step! ignores them in favour of the supplied stopping.

DFProjectionCache

Mutable per-solve state. Created via init_cache(F, x0, alg). All per-iteration buffers are pre-allocated; step! does not allocate.

State fields:

• x, x_prev, w, w_prev, z, d, d_prev — iteration vectors.
• ψw, ψw_prev, ψz — function values.
• x_new, proj_target — buffers for the projection step.
• proj_p, proj_q, proj_scratch, proj_out_prev — Dykstra inner buffers.
• k::Int — iteration counter (0-based).
• n_evals::Int — total ψ evaluations.
• converged::Bool — true on successful early-stop.
• done::Bool — true once solve_df! should exit the loop.
• retcode::Symbol — :Default, :Success, :MaxIters, :LineSearchFailed, :DegenerateResidual.
• resid::Float64 — final ‖ψ‖ at the returned iterate (NaN until set).

DFSolution

Immutable result returned from solve_df. Phase 3 will replace this with a SciMLBase.NonlinearSolution once NonlinearSolveBase is wired in; the field set will be preserved.

solve_df(F, x0, alg) -> DFSolution

Top-level entry point. Builds a cache, runs the loop, returns a DFSolution. F is an out-of-place mapping F(x) -> Vector. Phase 3 will replace this with SciMLBase.solve(prob::NonlinearProblem, alg).

Example

F = x -> x .- [0.3, -0.2]   # solution at [0.3, -0.2]
alg = DFProjection(; set = BoxSet([-1.0, -1.0], [1.0, 1.0]),
                    abstol = 1e-8)
sol = solve_df(F, [1.0, -1.0], alg)
sol.x         # ≈ [0.3, -0.2]
sol.converged # true
sol.retcode   # :Success

solve_df!(cache) -> cache

Drive the algorithm to termination given an initialized cache.

init_cache(F, x0, alg) -> DFProjectionCache

Allocate per-solve buffers and prepare the initial state. Projects x0 onto alg.set to ensure feasibility (paper assumes x_0 ∈ X). Evaluates ψ once at the projected x_0 to populate ψ0_norm (used by RelResidualTol) and starts the wall-clock for MaxTime.

step!(cache) -> cache

Perform one outer iteration of UIDFPAF. Updates cache.x, cache.k, function-value buffers, and sets cache.done = true on termination. Returns the cache (mutated).

DFSciMLCache

Wrapper cache returned by CommonSolve.init(prob, alg; …). Carries the original NonlinearProblem, the user-facing algorithm, and the inner Phase 2 DFProjectionCache. CommonSolve.solve! drives the inner cache to termination and packages the result as a NonlinearSolution.

CommonSolve.init(prob::NonlinearProblem, alg::DFProjection; abstol, maxiters, kwargs...)
    -> DFSciMLCache

Build a cache for solve(prob, alg; …). Accepts SciML's standard abstol and maxiters kwargs (overriding alg.abstol / alg.maxiters); other kwargs are absorbed without effect (Phase 3 polish: route verbose, callback, etc.).

CommonSolve.step!(cache::DFSciMLCache) -> cache

Advance the inner cache by one outer iteration of the algorithm. No-op if the inner cache has already terminated. Returns the wrapper cache so calls chain.

Usage:

using NonlinearSolve, DFMethods
cache = init(prob, alg)
while !cache.inner.done
    step!(cache)
end
sol = solve!(cache)

For batched runs, solve(prob, alg) (or equivalently solve!(init(prob, alg))) is the higher-level entry point that handles the loop internally.

CommonSolve.solve!(cache::DFSciMLCache) -> NonlinearSolution

Drive the inner cache to termination, then build and return a SciMLBase.NonlinearSolution.

monotonicity_required(alg) -> Bool

True iff the algorithm's convergence theory requires ψ to be monotone: $(ψ(x) - ψ(z))^\top (x - z) \geq 0$ for all $x, z \in \mathbb{R}^n$.

pseudomonotonicity_sufficient(alg) -> Bool

True iff the algorithm converges under pseudo-monotonicity of ψ (weaker than monotonicity). When true, monotonicity_required should be read as "monotonicity is sufficient but not strictly necessary".

convex_set_required(alg) -> Bool

True iff X must be a closed convex set for the algorithm's convergence analysis to hold.

AbstractSearchDirection

Supertype for search-direction rules. Concrete subtypes implement the single 3-argument method

direction!(d, rule, ctx)

where the output direction d is written in place and ctx is a NamedTuple carrying the per-iteration cache state. The fields are:

A rule that doesn't need a given field simply ignores it. New cache fields can be added in future versions without breaking existing direction methods — they will just be unused by older code.

For ctx.k == 0, only ctx.ψw is meaningful; the other fields may be uninitialized. Rules typically set d = -ψw at k = 0.

The convergence theory in Ibrahim 2026 (Thm 3.1) requires sufficient descent (-ψw' d ≥ c‖ψw‖²) and boundedness (‖d‖ ≤ c̄‖ψw‖). It is the rule author's responsibility to ensure these hold.

SpectralThreeTerm(; r=0.1, alpha_bar=1.0)

Spectral three-term derivative-free direction. The formula is:

d_0 = -ψ(w_0)
d_k = -ϑ_k^I · ψ(w_k) + β_k · d_{k-1} - ϑ_k^II · y_{k-1}        (k ≥ 1)

with

y_{k-1} = ψ(w_k) - ψ(w_{k-1})
s_{k-1} = (w_k - w_{k-1}) + r · y_{k-1}
ϑ_k^I   = (s_{k-1}' y_{k-1}) / (y_{k-1}' y_{k-1})
v_k     = max(alpha_bar · ‖d_{k-1}‖ · ‖y_{k-1}‖, ‖ψ(w_{k-1})‖²)
β_k     = (ψ(w_k)' y_{k-1}) / v_k
ϑ_k^II  = (ψ(w_k)' d_{k-1}) / v_k

Satisfies the sufficient-descent (eq. 3) and boundedness (eq. 4) properties used in the convergence proofs.

Parameters

• r: spectral parameter in the definition of s_{k-1} (paper uses 0.1).
• alpha_bar: the parameter $\bar{α}_1$ in the definition of v_k (paper uses 1.0).

direction!(d, rule, ctx)

In-place compute $d = d_k$ per rule. See AbstractSearchDirection for the ctx NamedTuple shape.

AbstractDFLineSearch

Supertype for derivative-free line-search rules. Each subtype defines the multiplier gamma_k(rule, ψ_z) entering the unified descent condition.

All concrete rules carry the scalars σ (Armijo coefficient) and ρ (backtracking factor), with defaults σ = 0.01, ρ = 0.6 (paper).

LSI(; σ=0.01, ρ=0.6)

γ_k = 1. Plain Armijo on the dual residual.

LSII(; σ=0.01, ρ=0.6)

γ_k = ‖ψ(z_k)‖. Scales the descent test with the residual at the trial point.

LSIII(; σ=0.01, ρ=0.6)

γ_k = ‖ψ(z_k)‖ / (1 + ‖ψ(z_k)‖). Saturates at 1 for large residuals.

LSIV(; σ=0.01, ρ=0.6, τ=0.5)

γ_k = τ + (1-τ) · ‖ψ(z_k)‖. Paper allows τ ∈ [τ_min, τ_max] ⊆ (0, 1] to vary across iterations; Phase 1 uses a fixed τ.

LSV(; σ=0.01, ρ=0.6)

γ_k = min(1, ‖ψ(z_k)‖). Caps large residuals at 1.

LSVI(; σ=0.01, ρ=0.6, lo=1e-4, hi=10.0)

γ_k = clamp(‖ψ(z_k)‖, lo, hi). Paper's projection onto $[\bar{α}, α]$. lo plays the role of $\bar{α}$, hi the role of $α$ in eq. (vi).

LSVII(; σ=0.01, ρ=0.6, lo=1e-4, Δ_init=1.0)

Adaptive variant of LSVI with shrinking upper bound Δ:

• For k = 1, 2, 3: behaves like LSVI with hi = lo + Δ, then Δ ← min(α_k, Δ).
• For k ≥ 4: Δ ← min(α_k, Δ) / 4 before forming hi = lo + Δ.

This rule carries state across iterations. Phase 1 exposes the parameter struct and a gamma_k(rule, ψ_z; Δ) keyword form that the Phase 2 cache will drive.

gamma_k(rule::AbstractDFLineSearch, ψ_z::AbstractVector) -> Float64

Per-iteration line-search multiplier $\gamma_k$ entering the unified descent condition (Ibrahim 2026 eq. 7)

\[-\psi(w_k + \alpha_k d_k)^\top d_k \;\geq\; \sigma\, \alpha_k\, \gamma_k\, \|d_k\|^2.\]

Each concrete AbstractDFLineSearch subtype (LSI–LSVII) supplies its own formula; see the individual line-search docstrings.

linesearch!(rule, ψ, w, d, z_buf, ψz_buf; maxbt=50)
    -> (α::Float64, ψ_z::AbstractVector, n_evals::Int, ok::Bool)

Backtracking driver satisfying eq. (7):

-ψ(w + α d)' d  ≥  σ · α · γ_k · ‖d‖²

Tries α = ρ^i for i = 0, 1, …, maxbt, returning the first α that satisfies the inequality. Returns ok = false if no acceptable step is found within maxbt backtracks (caller decides whether to retry with a different direction or flag a failure).

Arguments

• rule: an AbstractDFLineSearch.
• ψ: function ψ(x) -> Vector. Out-of-place for Phase 1; Phase 3 will route through NonlinearProblem and support in-place.
• w, d: current iterate w_k and direction d_k.
• z_buf, ψz_buf: pre-allocated buffers for w + α d and ψ(z).

Returns

• α: accepted step size.
• ψ_z: ψ at the accepted trial point (ψz_buf after the final call).
• n_evals: number of ψ evaluations (one per backtrack attempt).
• ok: whether the inequality was satisfied within maxbt backtracks.

AbstractInertialRule

Supertype for inertial-extrapolation rules. A rule produces the inertial coefficient $θ_k$ from the iteration index, current iterate, and previous iterate. The inertial point is then

w_k = x_k + θ_k (x_k - x_{k-1})

(Ibrahim 2026 eq. (2)).

Inertial(θ = 0.25)

Standard summable-step inertial-extrapolation rule:

θ_k = min(θ, 1 / (k² · ‖x_k - x_{k-1}‖))    if x_k ≠ x_{k-1}
      θ                                       otherwise

θ ∈ (0, 1). Ibrahim 2026 uses θ = 0.25 in its experiments.

The 1/k² cap ensures $\sum_k θ_k \|x_k - x_{k-1}\| \le \sum_k 1/k^2 < ∞$, which is the summability condition that drives the convergence proof (Ibrahim 2026 Remark 2.2). Lineage: Alvarez–Attouch 2001 introduced the heavy-ball / inertial idea for monotone operators; Maingé 2008 gave the modern form; Abubakar et al. 2021 (ref [1] in Ibrahim 2026) introduced this specific 1/k² cap for DF projection methods; Ibrahim 2026 carries it into eq. (2) of the unified framework.

NoInertial()

Disables inertia: $w_k = x_k$. Useful for ablation comparisons against the paper's accelerated variant.

inertial_coef(rule, k, xk, xkm1) -> θ_k::Float64

Compute the inertial coefficient. k is the iteration index (0-based); xk is the current iterate; xkm1 is the previous iterate.

apply_inertial!(w, rule, k, xk, xkm1) -> (w, θ_k)

Compute $w = x_k + θ_k (x_k - x_{k-1})$ in place, returning $θ_k$ too.

AbstractStoppingCriterion

Supertype for stopping criteria. Concrete subtypes implement any subset of:

should_stop_at_w(crit, cache)   -> (Bool, Symbol)   # after ψ(w_k) eval
should_stop_at_z(crit, cache)   -> (Bool, Symbol)   # after ψ(z_k) eval
should_stop_at_end(crit, cache) -> (Bool, Symbol)   # after projection → x_{k+1}

The Symbol is the retcode (:Success, :Stalled, :MaxIters, :MaxTime, :MaxFEvals, :UserStop, or any user-defined code).

AbsResidualTol(abstol)

Stop when $\|\psi(\cdot)\| \le \text{abstol}$ at either wk or zk. Retcode :Success.

RelResidualTol(rtol; abstol=0)

Stop when $\|\psi(\cdot)\| \le \text{abstol} + \text{rtol} \cdot \|\psi(x_0)\|$. Matches the Dai 2015 / Ibrahim 2026 stopping convention. Retcode :Success.

StepNormTol(xtol)

Stop when $\|x_k - x_{k-1}\| \le \text{xtol}$ at the end of an iteration. Catches stalls without waiting for MaxIters. Retcode :Stalled.

DirectionNormTol(dtol)

Stop when $\|d_k\| \le \text{dtol}$ at the end of an iteration. Retcode :Stalled.

A vanishing direction near convergence is not the same as a vanishing residual — pair this with AbsResidualTol (via AnyOf) for a complete picture.

MaxIters(maxiters)

Stop when cache.k >= maxiters. Retcode :MaxIters.

MaxTime(maxtime)

Stop when elapsed wall-clock time exceeds maxtime seconds. Retcode :MaxTime. The reference epoch is cache.t_start, set in init_cache.

MaxFEvals(maxevals)

Stop when total function evaluations reach maxevals. Retcode :MaxFEvals.

UserStop(f)

User-supplied predicate. f(cache) -> (stopped::Bool, retcode::Symbol). Called at end-of-iteration. Use for domain-specific criteria — e.g., stopping when an application-level metric crosses a threshold, or when $\|\psi(x_k)\|$ itself drops (which would require evaluating f at cache.x inside the callback — an extra ψ call per iteration).

AnyOf(criteria...)

Composite criterion: stops when any constituent stops. Checked in declaration order at each check point; the first to fire wins and its retcode propagates.

stopping = AnyOf(
    RelResidualTol(1e-8; abstol = 1e-12),
    StepNormTol(1e-10),
    MaxIters(5000),
    MaxTime(60.0),
)

should_stop_at_w(crit, cache) -> (Bool, Symbol)

Check whether the criterion fires immediately after evaluating $\psi(w_k)$ (right after the inertial extrapolation). Returns a (stopped, retcode) tuple. The default for AbstractStoppingCriterion is (false, :Default); concrete criteria override only the dispatch points they care about.

should_stop_at_z(crit, cache) -> (Bool, Symbol)

Check whether the criterion fires after evaluating $\psi(z_k)$ at the trial point $z_k = w_k + \alpha_k d_k$ (post line search). A :Success here is only accepted by the algorithm if $z_k \in X$.

should_stop_at_end(crit, cache) -> (Bool, Symbol)

Check whether the criterion fires after the projection step has produced $x_{k+1}$ (end of iteration). Suitable for iteration-count (MaxIters), wall-clock (MaxTime), and step-norm (StepNormTol) criteria.

AbstractConstraintSet

Supertype for all constraint sets. Concrete subtypes implement project!(y, x, set) that writes the orthogonal projection of x onto the set into y and returns y.

RealSpace()

The whole of $\mathbb{R}^n$ — projection is the identity. Use to disable constraints (e.g., for unconstrained benchmarking against NonlinearSolve.jl's SimpleDFSane).

BoxSet(lower, upper)

Box constraint $\{x : \text{lower}_i \le x_i \le \text{upper}_i\}$. lower and upper are vectors of equal length with lower[i] ≤ upper[i] element-wise. Use BoxSet(fill(a, n), fill(b, n)) for uniform scalar bounds.

HalfSpace(a, c)

Half-space $\{x : a^\top x \le c\}$. a is the normal vector (must be nonzero), c the offset. Projection:

y = x                          if a' x ≤ c
y = x − ((a' x − c)/‖a‖²) a   otherwise

The hyperplane $H_k$ in the Solodov–Svaiter step is a HalfSpace.

Intersection(set1, set2; maxiter=200, tol=1e-12)

Intersection of two closed convex sets. Projection uses Dykstra's algorithm (alternating projection with two correction sequences). For $\text{Box} \cap \text{HalfSpace}$ (the paper's polyhedral $\Omega$), Dykstra converges geometrically.

For workloads that need general polyhedral projection, a direct QP solver (JuMP + HiGHS) will be added in Phase 2 as an alternative backend.

CappedBox(a, b, c)

The polyhedral set $\Omega(a, b, c) = \{x \in \mathbb{R}^n : a \le x_i \le b,\ \sum_i x_i \le c\}$ used in Ibrahim 2026 for the numerical experiments (eq. 33). a, b, c are scalars; the dimension n is inferred from the input vector at projection time.

Projection

Closed-form via bisection on a 1D Lagrange multiplier:

1. Compute the box projection $y_B = \mathrm{clamp}(x, a, b)$.
2. If $\mathbf{1}^\top y_B \le c$ → return $y_B$ (constraint inactive).
3. Otherwise find $λ^* > 0$ such that $\sum_i \mathrm{clamp}(x_i - λ^*, a, b) = c$, then return $\mathrm{clamp}(x - λ^* \mathbf{1}, a, b)$.

The sum is piecewise-linear monotone-decreasing in λ, so bisection converges in O(log(1/tol)) steps.

Feasibility

The set is empty iff n·a > c. project! throws ArgumentError in that case (the feasibility check requires n, so it cannot happen at construction time).

UserSet(proj!)

Constraint set defined by a user-supplied in-place projection proj!(y, x) that writes the projection of x onto the set into y. The user is responsible for ensuring proj! projects onto a closed convex set — otherwise the algorithm's convergence guarantees do not hold.

project!(y::AbstractVector, x::AbstractVector, set::AbstractConstraintSet) -> y

In-place orthogonal projection of x onto set. Writes the projection into y and returns y. Each concrete AbstractConstraintSet subtype provides its own method; see the individual set docstrings for the projection formula or algorithm used.

For an allocating wrapper, see project.

project(x, set) -> Vector

Allocating out-of-place projection. For tests and small problems. Inside the algorithm hot loop, always use project!.

approx_project_X_halfspace!(out, target, X, a, c, ε,
                            p_buf, q_buf, scratch, out_prev;
                            maxiter=500) -> out

Approximate projection of target onto $X \cap H$ with $H = \{x : a^\top x \le c\}$, via Dykstra. Inner buffers (p_buf, q_buf, scratch, out_prev) are pre-allocated by the caller (typically the algorithm cache). Stops when $\|y - y_{\text{prev}}\|^2 \le \epsilon$ or maxiter reached.