Global Optimization: A Machine Learning Approach
Dimitris Bertsimas Georgios Margaritis
Many approaches for addressing Global Optimization problems typically rely on
relaxations of nonlinear constraints over specific mathematical primitives.
This is restricting in applications with constraints that are black-box,
implicit or consist of more general primitives. Trying to address such
limitations, Bertsimas and Ozturk (2023) proposed OCTHaGOn as a way of solving
black-box global optimization problems by approximating the nonlinear
constraints using hyperplane-based Decision-Trees and then using those trees to
construct a unified mixed integer optimization (MIO) approximation of the
original problem. We provide extensions to this approach, by (i) approximating
the original problem using other MIO-representable ML models besides Decision
Trees, such as Gradient Boosted Trees, Multi Layer Perceptrons and Suport
Vector Machines, (ii) proposing adaptive sampling procedures for more accurate
machine learning-based constraint approximations, (iii) utilizing robust
optimization to account for the uncertainty of the sample-dependent training of
the ML models, and (iv) leveraging a family of relaxations to address the
infeasibilities of the final MIO approximation. We then test the enhanced
framework in 81 Global Optimization instances. We show improvements in solution
feasibility and optimality in the majority of instances. We also compare
against BARON, showing improved optimality gaps or solution times in 11
instances.