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.