Global minimization of a minimum of a finite collection of functions

We consider the global minimization of a particular type of minimum structured optimization problems wherein the variables must belong to some basic set, the feasible domain is described by the intersection of a large number of functional constraints and the objective stems as the pointwise minimum of a collection of functional pieces. Among others, this setting includes all non-convex piecewise linear problems. The global minimum of a minimum structured problem can be computed using a simple enumeration scheme by solving a sequence of individual problems involving each a single piece and then taking the smallest individual minimum. We propose a new algorithm, called Upper-Lower Optimization (ULO), tackling problems from the aforementioned class. Our method does not require the solution of every individual problem listed in the baseline enumeration scheme, yielding potential substantial computational gains. It alternates between (a) local-search steps, which minimize upper models, and (b) suggestion steps, which optimize lower models. We prove that ULO can return a solution of any prescribed global optimality accuracy. According to a computational complexity model based on the cost of solving the individual problems, we analyze in which practical scenarios ULO is expected to outperform the baseline enumeration scheme. Finally, we empirically validate our approach on a set of piecewise linear programs (PL) of incremental difficulty.