Estimating lower bound functions in surrogate optimization

Abstract

Abstract Lower bounds play a vital role in optimization by guiding search, improving solution quality, and quantifying optimality gaps. In expensive black-box settings, however, the quality of Lipschitz-based estimated lower bounds can deteriorate when function behavior varies across the domain. To address this limitation, we propose a surrogate-based lower-bound framework that combines surrogate predictions with nonlinear distance metrics. The resulting formulation is designed to provide more informative lower-bound estimates when only a sparse set of function evaluations is available. We study superlinear, linear, and sublinear distance metrics under a Hölder-type construction and analyze how the choice of metric affects the resulting estimated lower bounds. In particular, we derive a confidence radius that characterizes when the ordering among these bounds is guaranteed. We also introduce an evaluation metric for comparing estimated lower bounds and use it to assess the proposed method against a traditional Lipschitz estimated lower bound and a statistical lower bound based on the Working–Hotelling procedure. Finally, we incorporate the proposed lower bounds as acquisition functions within surrogate optimization. Experiments on benchmark test problems and a planar robot pushing task show that the proposed framework improves lower-bound quality, supports more effective candidate selection, and compares favorably with standard Lipschitz-based, statistical, and six surrogate-optimization baselines.