Section: New Results

Interval analysis

Inner Regions and Interval Linearizations for Global Optimization

Participants : Gilles Trombettoni [correspondant] , Bertrand Neveu.

Researchers from interval analysis and constraint (logic) programming communities have studied intervals for their ability to manage infinite solution sets of numerical constraint systems. In particular, inner regions represent subsets of the search space in which all points are solutions. Our main contribution is the use of recent and new inner region extraction algorithms in the upper bounding phase of constrained global optimization.

Convexification is a major key for efficiently lower bounding the objective function. We have adapted the convex interval taylorization proposed by Lin & Stadtherr for producing a reliable outer and inner polyhedral approximation of the solution set and a linearization of the objective function. Other original ingredients are part of our optimizer, including an efficient interval constraint propagation algorithm exploiting monotonicity of functions.

We end up with a new framework for reliable continuous constrained global optimization. This interval Branch & Bound significantly outperforms the best reliable global optimizers [22] , [25] , [28] .

An Interval Extension Based on Occurrence Grouping

Participants : Bertrand Neveu [correspondant] , Gilles Trombettoni.

We proposed last year a new “occurrence grouping” interval extension ${\left[f\right]}_{og}$ of a function $f$. When $f$ is not monotonic w.r.t. a variable $x$ in a given domain, we try to transform $f$ into a new function $f^{og}$ which is monotonic w.r.t. two subsets $x_a$ and $x_b$ of the occurrences of $x$: $f^{og}$ is increasing w.r.t. $x_a$ and decreasing w.r.t. $x_b$. ${\left[f\right]}_{og}$ is the interval extension by monotonicity of $f^{og}$ and produces a sharper interval image than the natural extension does.

This year we have improved the linear program and algorithm that minimize a Taylor-based over-estimate of the image diameter of ${\left[f\right]}_{og}$. We have detailed the proofs of correctness and reliability of this occurrence grouping algorithm [8] , [29] .