Adjoint Function as Bisection Heuristic for Guaranteed Global Optimization with Nonlinear Ordinary Differential Equations

Julien Alexandre Dit Sandretto (1)

1 U2IS - Unité d'Informatique et d'Ingénierie des Systèmes

We focus on interval algorithms for computing guaranteed enclosures of the solutions of constrained global optimization problems where differential constraints occur. To solve such a problem of global optimization with nonlinear ordinary differential equations, a branch and bound algorithm can be used based on guaranteed numerical integration methods. Nevertheless, this kind of algorithms is expensive in term of computation. Defining new methods to reduce the number of branches is still a challenge. Bisection based on the smear value is known to be often the most efficient heuristic for branching algorithms. This heuristic consists in bisecting in the coordinate direction for which the values of the considered function change the most " rapidly ". We propose to define a smear-like function using the adjoint (or sensitivity) function obtained from the differentiation of ordinary differential equation with respect to parameters. The adjoint has been already used in validated simulation for local optimization but not as a bisection heuristic. We implement this heuristic in a branch and bound algorithm to solve a problem of global optimization with nonlinear ordinary differential equations. Experiments show that the gain in term of number of branches could be up to 30%.

Domaines: Géométrie différentielle [math.DG]; Algorithme et structure de données [cs.DS]

Julien Alexandre Dit Sandretto. Adjoint Function as Bisection Heuristic for Guaranteed Global Optimization with Nonlinear Ordinary Differential Equations. OMS, Dec 2017, La Havane, Cuba. ⟨hal-01762198⟩