Nested interval branch-and-bound algorithm for min-max problem
Daniel Ioan  1@  , Jordan Ninin  2@  , Benoit Clement  3@  
1 : Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC)
Laboratoire des sciences et techniques de l\'information, de la communication et de la connaissance : UMR6285, Laboratoire des sciences et techniques de l\'information, de la communication et de la connaissance : UMR6285
2 : Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance  (Lab-STICC)
PRES Université Européenne de Bretagne (UEB), CNRS : UMR6285, ENSTA Bretagne
Technopole Brest Iroise BP 832 29285 BREST CEDEX -  France
3 : Laboratoire des sciences et techniques de línformation, de la communication et de la connaissance
École Nationale Supérieure de Techniques Avancées Bretagne

This work pertains to the global resolution of the min-max problems where the goal is to minimize over x the maximum over y of f(x,y). This kind of problem has a broad field of applications: from structured robust control up to motion planning and collision detection. The proposed approach employs a set-valued technique, relying on two nested branch-and-bound algorithms using interval analysis. To address the resulting non-smooth objective function and improve the convergence, we exploit a discrete restriction of the feasible set of y to focus on some key points without losing the global optimum. Moreover, a warm start procedure for the secondary branch-and-bound algorithm is used. The benefits of this approach are highlighted and exploited through proof of concept illustrations as well as simulation results. 


Personnes connectées : 2 Vie privée
Chargement...