search

JuliaIntervals / TaylorModels.jl

Rigorous function approximation using Taylor models in Julia
Other
63 stars 14 forks source link

Add branch-and bound algorithm to bound polynomials #32

Open lbenet opened 5 years ago

lbenet commented 5 years ago

The idea is to have other methods to improve bounding polynomials, specially with many variables.

mforets commented 5 years ago

For a pseudo-code implementing branch-and-bound to bound polynomials see e.g. Algorithm 1 in Implementation of Taylor Models in CORA 2018. M. Althoff, D. Grebenyuk and N. Kochdumper.

lbenet commented 5 years ago

For a pseudo-code implementing branch-and-bound to bound polynomials see e.g. Algorithm 1 in Implementation of Taylor Models in CORA 2018. M. Althoff, D. Grebenyuk and N. Kochdumper.

@dpsanders has a bunch of experience on this. I am thinking of IntervalRootFinding.jl, but perhaps IntervalOptimization.jl is another good option.

In the past I used the function bound_taylor1 (already in TaylorModels.jl) to achieve tighter bounds, but since then IntervalRootFinding.jl has changed a bit, and the methods I introduced are certainly out of date.

dpsanders commented 5 years ago

This is what is implemented in IntervalOptimization.jl, although there will be some details to sort out to make it workable for e.g. > 2 variables. Also, at the moment it is difficult to make it stop in particular circumstances.