GEAR: A GPU-Accelerated Global Solver for Nonlinear Programs via Linear Bound Propagation

We present a novel GPU-accelerated global solver for constrained nonlinear programming (NLP) inspired by the efficient linear bound propagation framework in neural network (NN) verification. Existing work on NN verification, a problem that can be cast as feasibility detection for a nonlinear objective, demonstrated orders-of-magnitude speedups with the linear bound propagation-based framework when compared to traditional solvers. Extending this paradigm to global nonlinear programming requires addressing many challenges: a global constrained NLP solver must effectively exploit all, possibly unstructured, nonlinear constraints to improve the objective, whereas NN verification typically handles simple input box constraints over a well-structured NN and does not directly optimize an objective function. We address these challenges by fully exploiting the linear bounds produced by bound propagation: these linear bounds can be viewed as relaxations of nonlinear constraints and used to provide dual objectives, check infeasibility, and guide the search for a primal solution. In addition, we proposed tighter linear relaxations (essential for linear bound propagation) for bilinear functions commonly used in NLP problems, and a projected augmented Lagrangian method tightly coupled to our dual solving procedure to produce primal solutions. Our method solves 399 of 505 bounded and continuous NLP problems in the GAMS and MINLPLib benchmarks under a 180-second limit, outperforming many strong global solvers (including commercial ones) such as SCIP, BARON, and LindoGlobal. Compared to SCIP (the strongest solver on these problems), we solve 104 problems exclusively, including large-scale, highly nonlinear ones that are often out of reach for traditional approaches. Our method demonstrates a distinct, highly complementary regime for GPU-accelerated global optimization of nonlinear programming problems.