Types

AbstractEnclosureAlgorithm

Abstract type for range enclosure algorithms.

AbstractDirectRangeAlgorithm <: AbstractEnclosureAlgorithm

Abstract type for range enclosure algorithms that directly evaluate the functions over a given domain.

AbstractIterativeRangeAlgorithm <: AbstractEnclosureAlgorithm

Abstract type for algorithms that iteratively bound the range of a function over a given domain.

AffineArithmeticEnclosure <: AbstractDirectRangeAlgorithm

Data type to bound the range of f over X using affine arithmetic. See AffineArithmetic.jl for more details.

Notes

To use this algorithm, you need to load AffineArithmetic.jl. Note also that AffineArithmetic.jl currently supports only arithmetic operations.

Examples

julia> using AffineArithmetic

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), AffineArithmeticEnclosure())
[0.0625, 2.0]_com_NG

BranchAndBoundEnclosure <: AbstractIterativeRangeAlgorithm

Data type to bound the range of f over X using the branch and bound algorithm.

Fields

• maxdepth (default 10): maximum depth of the search tree
• tol (default 1e-3): tolerance to compute the range of the function

Algorithm

The algorithm evaluates a function f over an interval X. If the maximum depth is reached or the width of f(X) is below the tolerance, the algorithm returns the computed range; otherwise it bisects the interval/interval box.

The algorithm also looks at the sign of the derivative / gradient to see if the range can be computed directly. By default, the derivative / gradient is computed using ForwardDiff.jl, but a custom value can be passed via the df keyword argument to enclose.

Examples

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), BranchAndBoundEnclosure()) # default parameters
[0.914022, 1.00004]_trv_NG

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), BranchAndBoundEnclosure(tol=1e-2, maxdepth=7); df=(x -> -4x^3 + 5x^4))
[0.88221, 1.00098]_trv_NG

NaturalEnclosure <: AbstractDirectRangeAlgorithm

Data type to bound the range of f over X using natural enclosure, i.e., to evaluate f(X) with interval arithmetic.

Examples

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), NaturalEnclosure())
[0.0, 2.0]_com_NG

MeanValueEnclosure

Data type to bound the range of f over X using the mean value form, that is the range is bounded by the expression $f(Xc) + f'(X) * (X - Xc)$, where Xc is the midpoint of X and f' is the derivative of f (gradient in the multivariate case).

MooreSkelboeEnclosure{T} <: AbstractIterativeRangeAlgorithm

Data type to bound the range of f over X using the Moore-Skelboe algorithm, which rigorously computes the global minimum and maximum of the function. See IntervalOptimisation.jl for more details.

Fields

• structure – (default: HeapedVector) the way in which vector elements are kept arranged; possible options are HeapedVector and SortedVector
• tol – (default 1e-3) tolerance to which the optima are computed

Notes

To use this algorithm, you need to load IntervalOptimisation.jl.

Examples

julia> using IntervalOptimisation

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), MooreSkelboeEnclosure()) # default parameters
[0.916034, 1.00213]_com

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), MooreSkelboeEnclosure(; tol=1e-2))
[0.900812, 1.0326]_com

SumOfSquaresEnclosure{T} <: AbstractIterativeRangeAlgorithm

Data type to bound the range of f over X using sum-of-squares optimization. See SumOfSquares.jl for more details

Fields

• backend – backend used to solve the optimization problem; a list of available backends can be found here
• order – (default 5), maximum degree of the SDP relaxation

Notes

To use this solver, you need to load SumOfSquares.jl and a backend.

Since the optimization problem is solved numerically and not with interval arithmetic, the result of this algorithm is not rigorous.

Examples

julia> using SumOfSquares, SDPA, DynamicPolynomials

julia> backend = SDPA.Optimizer;

julia> @polyvar x;

julia> enclose(-x^3/6 + 5x, interval(1, 4), SumOfSquaresEnclosure(; backend=backend)) # default parameters
[4.83333, 10.541]_com

julia> enclose(-x^3/6 + 5x, interval(1, 4), SumOfSquaresEnclosure(; backend=backend, order=6))
[4.83333, 10.541]_com

TaylorModelsEnclosure <: AbstractDirectRangeAlgorithm

Data type to bound the range of f over X using Taylor models. See TaylorModels.jl for more details.

Fields

• order – (default: 10) order of the Taylor model used to compute an enclosure of f over dom
• normalize – (default: true) if true, normalize the Taylor model on the unit symmetric box around the origin

Notes

To use this solver, you need to load TaylorModels.jl and a backend.

Examples

julia> using TaylorModels

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), TaylorModelsEnclosure()) # default parameters
[0.812499, 1.09376]_com_NG

julia> enclose(x -> 1 - x^4 + x^5, interval(0, 1), TaylorModelsEnclosure(; order=4))
[0.781249, 1.12501]_trv_NG