Data-driven Lipschitz-informed convex underestimators for branch-and-bound optimization of black-box functions

Abstract To address optimization of computationally expensive black-box functions, we build upon the Data-Driven Spatial Branch-and-Bound (DDSBB) algorithm, which utilizes underestimators of sampled data, branching and pruning to locate global optima. A key challenge of DDSBB is the potential invalidity of data-driven underestimators, especially in limited sampling scenarios. In this work, we propose new formulations that incorporate Lipschitz continuity information, estimated directly from sampled data, to enhance the validity of the underestimators and overall algorithm performance. The new approaches improve the fraction of successfully solved benchmark problems by 10% across a set of 325 problems to global optimality, compared to previous DDSBB literature. Although convergence to an ε -optimal solution increases sampling requirements, the proposed methods consistently identify near-optimal regions with fewer function evaluations. We further compare the proposed methods against eight widely used gradient-free optimizers and provide a formal convergence analysis for the case of black-box Lipschitz continuous problems. These results advance data-driven global optimization methods for expensive black-box problems, which are frequently encountered in engineering and scientific applications.