Optimum term in quadratic expansion

[mforets]

Doing (α + βx) x looses the dependency between the arguments, so it may be less precise using interval arithmetic. If there is a general rule, one has to find it by taking the derivative of the expression as in the paper, which is a particular case with alpha, beta being something like t and 1/2t^2.

julia> fprod(α, β, x) = (α + β*x)*x
fprod (generic function with 1 method)

julia> fsum(α, β, x) = α*x + β*x^2
fsum (generic function with 1 method)

julia> y = Interval(-1, 1)
[-1, 1]

julia> fprod(0.0, 1.0, y)
[-1, 1]

julia> fsum(0.0, 1.0, y) # fsum is tighter
[0, 1]

julia> y = Interval(-3, -2)
[-3, -2]

julia> fprod(1.0, 2.0, y) # fprod is tighter
[6, 15]

julia> fsum(1.0, 2.0, y)
[5, 16]

Originally posted by @mforets in #91 (comment)

[lucaferranti]

Assuming $\alpha$ and $\beta$ are not intervals, in this case you can eliminate the dependency problem the following way

fexact(α, β, x) = ((2*β*x + α)^2 - α^2)/(4*β)

this way

julia> y = Interval(-1, 1)
[-1, 1]

julia> fprod(0.0, 1.0, y), fsum(0.0, 1.0, y), fexact(0.0, 1.0, y)
([-1, 1], [0, 1], [-0, 1])

julia> y = Interval(-3, -2)
[-3, -2]

julia> fprod(1.0, 2.0, y), fsum(1.0, 2.0, y), fexact(1.0, 2.0, y)
([6, 15], [5, 16], [6, 15])

julia> y = Interval(-3, 3)
[-3, 3]

julia> fprod(1.0, 2.0, y), fsum(1.0, 2.0, y), fexact(1.0, 2.0, y)
([-21, 21], [-3, 21], [-0.125, 21])

here is a plot of the latest case

[lucaferranti]

well the formula above doesn't work if $\beta=0$, but that's a trivial case to consider

[lucaferranti]

where should this go? I can open a PR for this.

Also does my assumption (alpha and beta are not intervals) hold? If it doesn't, it may make dependency problem worse

[mforets]

where should this go?

i no longer remember the context in which this method was needed. (seems to be the scalar version of this one).

then i suggest to define the method on exponential.jl and with signature

quadratic_expansion(x::Interval, α::Real, β::Real)

(NB this library doesn't depend on LazySets so there is no risk of confusion between LazySets.Interval and IntervalArithmetic.Interval)

Also does my assumption (alpha and beta are not intervals) hold?

yes, that assumption holds

I can open a PR for this.

go for it 👍

[lucaferranti]

Next that function should replace this line ? With a quick glance, the rest of the code should not suffer from dependency issues?