Corrector Stepping

The stepping module provides step-size control interfaces for Newton-type correction algorithms.

Base Step Interface

_CorrectorStepBase()

Abstract base class for step-size control strategy interfaces.

class hiten.algorithms.corrector.stepping._CorrectorStepBase(**kwargs)

Bases: ABC

Provide an abstract base class for step-size control strategy interfaces.

This class provides the foundation for implementing different step-size control strategies in Newton-type correction algorithms. It defines the interface that correction algorithms use to obtain step transformation functions tailored to specific problems.

The interface follows the strategy pattern, allowing correction algorithms to be parameterized with different stepping behaviors without changing their core logic. This enables flexible combinations of:

• Different Newton variants (standard, damped, quasi-Newton)

• Different step control strategies (full steps, line search, trust region)

• Different problem-specific constraints and safeguards

Subclasses must implement the step transformation logic while this base class handles common initialization patterns and ensures compatibility with multiple inheritance chains commonly used in the correction framework.

Parameters:

**kwargs – Additional keyword arguments passed to parent classes. This enables clean cooperation in multiple-inheritance chains.

Notes

The interface is designed to work seamlessly with multiple inheritance, allowing correction algorithms to mix step interfaces with other capabilities (convergence monitoring, Jacobian computation, etc.).

The abstract method _build_line_searcher() is responsible for creating CorrectorStepProtocol objects that encapsulate the step transformation logic for specific problems.

Examples

>>> class CustomStepInterface(_CorrectorStepBase):
...     def _build_line_searcher(self, residual_fn, norm_fn, max_delta):
...         def custom_step(x, delta, current_norm):
...             # Custom step logic here
...             alpha = compute_step_size(x, delta, current_norm)
...             x_new = x + alpha * delta
...             r_norm_new = norm_fn(residual_fn(x_new))
...             return x_new, r_norm_new, alpha
...         return custom_step

See also

_CorrectorPlainStep

Concrete implementation for simple Newton steps.

_ArmijoStep

Concrete implementation with Armijo line search.

CorrectorStepProtocol

Protocol for step transformation functions.

Plain Stepping

_CorrectorPlainStep()

Step interface for plain Newton updates with safeguards.

class hiten.algorithms.corrector.stepping._CorrectorPlainStep(**kwargs)

Bases: _CorrectorStepBase

Provide a step interface for plain Newton updates with safeguards.

This class implements the simplest step-size control strategy: taking full Newton steps with optional step size capping for numerical stability. It provides a robust baseline stepping strategy suitable for well-behaved problems where the Newton method converges reliably.

The interface includes an infinity-norm safeguard that prevents excessively large steps, which can cause numerical overflow or instability. This makes it suitable for a wide range of problems while maintaining the simplicity of the basic Newton method.

See also

_ArmijoStep

More sophisticated interface with line search capabilities.

_CorrectorStepBase

Abstract base class that this class extends.

Armijo Line Search

_ArmijoStep()

Step interface with Armijo line search for robust convergence.

class hiten.algorithms.corrector.stepping._ArmijoStep(*, alpha_reduction=0.5, min_alpha=0.0001, armijo_c=0.1, **kwargs)

Bases: _CorrectorStepBase

Provide a step interface with Armijo line search for robust convergence.

This class extends the plain step interface with Armijo line search capabilities. It provides a more robust stepping strategy that can handle poorly conditioned problems, bad initial guesses, and nonlinear systems where full Newton steps might diverge.

Parameters:

• alpha_reduction (float, default=0.5) – Factor to reduce step size in backtracking.

• min_alpha (float, default=1e-4) – Minimum step size before giving up.

• armijo_c (float, default=0.1) – Armijo parameter for sufficient decrease condition.

• **kwargs – Additional arguments passed to parent classes.

Notes

The Armijo condition requires that the residual norm decrease by a sufficient amount proportional to the step size, providing a balance between convergence speed and robustness.

Examples

>>> # Default line search parameters
>>> interface = _ArmijoStep()
>>>
>>> # Custom line search parameters
>>> interface = _ArmijoStep(alpha_reduction=0.7, min_alpha=1e-5)

See also

_CorrectorPlainStep

Parent class providing plain Newton step capabilities.

_ArmijoLineSearch

Line search implementation used by this interface.

_ArmijoLineSearch()

Implement Armijo line search with backtracking for Newton methods.

class hiten.algorithms.corrector.stepping._ArmijoLineSearch(*, residual_fn, norm_fn=None, max_delta=0.01, alpha_reduction=0.5, min_alpha=0.0001, armijo_c=0.1)

Bases: object

Implement Armijo line search with backtracking for Newton methods.

Implements the Armijo rule for sufficient decrease, ensuring that each step reduces the residual norm by a sufficient amount proportional to the step size. Includes step size capping and fallback strategies.

Parameters:

• residual_fn (ResidualFn) – Function to compute residual vectors.

• norm_fn (NormFn, optional) – Function to compute residual norms. Uses L2 norm if None.

• max_delta (float, optional) – Maximum allowed step size (infinity norm).

• alpha_reduction (float, default=0.5) – Factor to reduce step size in backtracking.

• min_alpha (float, default=1e-4) – Minimum step size before giving up.

• armijo_c (float, default=0.1) – Armijo parameter for sufficient decrease condition.

__call__(*, x0, delta, current_norm)

Execute Armijo line search with backtracking.

Finds step size satisfying Armijo condition: ||R(x + alpha * delta)|| <= (1 - c * alpha) * ||R(x)||

Starts with full Newton step and reduces by backtracking until sufficient decrease is achieved or minimum step size is reached.

Parameters:

• x0 (np.ndarray) – Current parameter vector.

• delta (np.ndarray) – Newton step direction.

• current_norm (float) – Norm of residual at current point.

Returns:

• x_new (np.ndarray) – Updated parameter vector.

• r_norm_new (float) – Norm of residual at new point.

• alpha_used (float) – Step size scaling factor that was accepted.

Raises:

• ValueError – If residual function is not provided.

• BackendError – If line search fails to find any productive step.

Return type:

Tuple[ndarray, float, float]

Factory Functions

make_plain_stepper()

Factory function for creating plain Newton steppers.

hiten.algorithms.corrector.stepping.make_plain_stepper()

Return a factory that builds a plain capped stepper per problem.

Return type:

Callable[[Callable[[ndarray], ndarray], Callable[[ndarray], float], float | None], CorrectorStepProtocol]

make_armijo_stepper()

Factory function for creating Armijo line search steppers.

hiten.algorithms.corrector.stepping.make_armijo_stepper(*, alpha_reduction=0.5, min_alpha=0.0001, armijo_c=0.1)

Return a factory that builds an Armijo stepper per problem.

Parameters:

• alpha_reduction (float, default=0.5) – Factor to reduce step size in backtracking.

• min_alpha (float, default=1e-4) – Minimum step size before giving up.

• armijo_c (float, default=0.1) – Armijo parameter for sufficient decrease condition.

Return type:

Callable[[Callable[[ndarray], ndarray], Callable[[ndarray], float], float | None], CorrectorStepProtocol]

Utility Functions

_default_norm()

Compute L2 norm of residual vector.

_infinity_norm()

Compute infinity norm of residual vector.