RESEARCH NOTE / October 3, 2026
GEAR: Scaling Global Optimization with Reusable Linear Bounds
GEAR makes global search scale in two ways: GPU batches reduce the effective cost of processing a domain, while reusable constraint-aware linear bounds close optimality proofs across 421 of 505 bounded continuous NLPs.
GEAR: A GPU-Accelerated Global Solver for Bounded Continuous Nonlinear Programs via Linear Bound Propagation · NeurIPS 2026
Duo Zhou, Hesun Chen, Xiangru Zhong, Grani A. Hanasusanto, Huan Zhang
arXiv · PDF · OpenReview · Project page
Global optimization becomes expensive when a solver must inspect thousands or millions of regions before it can certify a solution. Each region needs an objective lower bound, an infeasibility test, a tightened domain, a search for a feasible incumbent, and a decision about the next split. GEAR makes all five operations consume a single set of propagated linear bounds, allowing an active frontier of boxes to be processed as one GPU tensor workload and making the geometry from each propagation pass useful throughout the search (Paper, Sections 1 and 3, Figure 1).
There are two sources of scalability here: lower the effective cost of processing a domain, and reduce the number of domains that need processing. The interaction between them—and where it trades off against per-node polyhedral LP strength—explains the solver’s behavior across problem classes far better than the hardware label alone.
Account for the cost of a proof
Consider a bounded continuous nonlinear program over an initial finite box :
Source equalities and two-sided inequalities are written as pairs of one-sided inequalities with an absolute feasibility tolerance absorbed into each (for example, becomes and ), so primal feasibility checks and dual lower bounds refer to the exact same problem (Paper, Section 2, Equation (1), and Appendix A.3). On any sub-box , write the feasible set and local optimum as and (Equation (3)). A run certifies global optimality when its verified feasible incumbent and global lower bound satisfy the relative gap criterion (Paper, Section 4, Equation (13)):
Extending linear bound propagation (LBP) from neural network verification to constrained global optimization is not automatic (Paper, Section 3.1). A verifier tests a property against a fixed threshold and never needs a feasible point. In constrained NLP, the pruning threshold is the objective value of a feasible incumbent that the solver must find and improve, and an objective-only lower bound minimizes over the entire box—including infeasible points—so it can remain strictly below no matter how finely the box is split. Minimizing on subject to has optimum , yet every sub-box containing retains an objective-only lower bound of ; branching alone never prunes that box by dominance unless the constraint rules it out or raises its lower bound (Paper, Section 3.1).
For a spatial branch-and-bound run with batch size , a useful runtime accounting model is
The first factor measures how many boxes the tree must visit; the second measures the effective cost per box across bounding, clipping, and primal search. GEAR targets both factors simultaneously by turning propagated linear bounds into a shared constraint-aware representation on the GPU.
Batch the nodes and the constraint outputs together
GEAR compiles the objective and all constraints as the outputs of a single computation graph (Paper, Section 2, Equation (2), and Section 3.2). Forward evaluation, automatic differentiation, and backward linear bound propagation operate on this same graph. Linear constraints require no relaxation: LBP substitutes affine operators exactly, and when the parser exposes linear constraints as an explicit matrix, that matrix is reused directly across subproblems (Paper, Section 3.2 and Appendix A.2).
On each sub-box , backward linear bound propagation substitutes valid local linear relaxations from the outputs toward the inputs according to the sign of each backward weight ( for and for ; Section 2, Equations (4)–(5), and Appendix A.2, Equation (15)), producing valid linear lower bounds on :
Across a batch of boxes in variables with constraints, the coefficients form dense tensors (Paper, Section 3.2, Equation (7), and Appendix A.2, Equation (17)):
The batch dimension indexes heterogeneous boxes in the branch-and-bound frontier; the output dimension indexes the objective and constraints. Because every box shares the same graph topology while carrying its own interval and affine bounds, one batched GPU pass bounds thousands of subproblems without building a separate optimization model per node.
Turn one propagation pass into five kinds of progress
A linear lower bound carries more information than its scalar box minimum (Section 2, Equation (6)). Its slope vector records how the function varies across . Stacking the constraint linear bounds (together with any exact linear rows and presolve cuts) as and defines an outer polyhedral relaxation of the feasible set on (Paper, Section 3.3, Equation (8)):
Instead of calling a simplex or interior-point LP solver at every box to evaluate , GEAR reuses and in five ways (Paper, Figure 1 and Sections 3.3–3.5):
- Lagrangian objective lower bound: Dualizing the constraint rows with nonnegative multipliers while keeping the box as the inner minimization domain yields the Lagrangian bound (Paper, Section 3.3, Equation (9), and Appendix A.4, Proposition A.1):
where . At every feasible point , , so for any , and LP strong duality gives whenever (Proposition A.1). In the toy example subject to , setting gives across the entire box, recovering the constrained optimum without branching (Section 3.3 and Appendix A.4). More generally, if a constraint row is strictly positive across the minimizing face (), small steps along strictly raise at rate (Theorem A.2). Because the inner minimization is coordinate-separable, each evaluation of and its supergradient at an inner minimizer costs arithmetic per box without rerunning bound propagation. GEAR runs 20 projected Adam ascent steps and 500 batched GPU primal-dual hybrid gradient (PDHG) iterations with Ruiz equilibration (plus CPU LP solves on the 16 lowest-bound boxes when ), evaluating with outward rounding every 50 PDHG steps and retaining the best certified bound (Paper, Section 3.3 and Appendix B.5, Figure 12).
- Incumbent-independent infeasibility certificates: Whenever a nonnegative combination satisfies
the box cannot contain a feasible point and is discarded immediately (Paper, Section 3.3, Equation (10)). Unit vectors test each individual constraint in closed form; for the lowest-bound boxes whose constraints are only jointly inconsistent, is taken from the multipliers of a phase-one LP minimizing the maximum violation on the CPU and verified by evaluating Equation (10) with outward rounding on the GPU (Paper, Section 3.3 and Appendix B.5, Figure 12c).
- Relaxed and complete domain clipping: Adapting Clip-and-Verify (Zhou et al., 2025) to nonlinear constraint rows, relaxed clipping uses to tighten each coordinate interval in per sweep (Paper, Section 3.3 and Appendix A.5, Equation (25)):
Complete clipping tightens intermediate graph intervals by maximizing over —replacing coordinate descent with gradient descent when constraints are numerous, or sweeping up to 16 active rows through a fused double-precision piecewise-linear breakpoint kernel (Paper, Section 3.3, Appendix A.5, and Appendix B.5). Tighter intervals shrink the domains of downstream nonlinear operators on the next propagation pass, and any empty interval certifies .
Reuse geometry without growing the node state with depth
Because any child box satisfies , constraint linear bounds derived on a parent remain valid on its children (Paper, Section 3.5 and Appendix A.3, Equation (18)). GEAR forwards the parent’s lower bound and constraint rows to both children so each child can be clipped immediately, before running its own bound propagation pass. Once the child computes fresh linear bounds, the new nonlinear rows replace the inherited ones while the original linear constraints stay shared. Consequently, the active row set per box never grows with tree depth (Paper, Section 3.5 and Appendices A.3, A.11).
- Multiplier-weighted smart branching (-SB): Classical smart branching in neural verification splits each candidate coordinate and bounds both children, requiring bound evaluations per box. In constrained NLP, a split can help either by raising the objective bound or by tightening a bottleneck constraint. GEAR scores every coordinate directly from the cached linear bounds and the best Lagrangian multipliers without bounding any child (Paper, Section 3.5, Equation (12)):
Summing absolute coefficient magnitudes prevents opposing objective and constraint slopes from cancelling, and Lemma A.5 shows that upper-bounds the average one-step midpoint gain of the mixed row (Paper, Appendix A.9, Equation (51)). Maximization is restricted to coordinates with () and paired with a count guard that forces a split along the relatively widest coordinate at least once every splits, guaranteeing geometric box shrinkage at depth and conditional finite -convergence (Theorem A.8, Paper, Appendices A.9, A.13, and B.5, Equation (67)).
Keep primal recovery in the same batching regime
Strong lower bounds cannot prune by dominance () without a good feasible incumbent. Calling a sequential KKT-factorization solver per box would bottleneck the GPU pipeline.
- Dual-guided projected ALM primal search: GEAR searches for feasible incumbents across active boxes in parallel using the Hestenes–Powell–Rockafellar inequality-form augmented Lagrangian on the original nonlinear graph (Paper, Section 3.4, Equation (11), and Appendix A.8, Algorithm 1):
Each outer iteration takes a fixed budget of projected Adam steps on using the exact gradient (Equation (43)), updates , and increases when the maximum constraint violation fails to shrink sufficiently. The dual evaluation warm-starts this primal search: GEAR initializes at —which already lies in the low-objective basin of the linear relaxation—and initializes so the first outer loop immediately weights the constraints that bottlenecked the dual bound (Paper, Section 3.4 and Appendix A.8). In the full solver (Appendix B.6, Figure 14), batched ALM-PGD (20,480 starts at the root; ~1,000 starts across a tree batch) is followed on the GPU by damped Gauss–Newton / Levenberg–Marquardt feasibility restoration (Equation (71)) and Mehrotra interior-point SQP polish (Equation (72)), alongside root CPU IPOPT and LP alternation. Every candidate updates the incumbent only after passing the unscaled feasibility gate on the original model (Equations (50) and (70)), keeping global soundness strictly decoupled from heuristic convergence (Paper, Section 3.5, Table 4, and Appendix A.12).
Measure both coverage and the proof contribution of each component
The paper evaluates GEAR on 505 bounded continuous NLP instances—265 from gams_world and 240 from minlplib (minlplib_linear)—against six global solvers (Gurobi, SCIP, BARON, Xpress, Couenne, LindoGlobal) and six local solvers (Knitro, IPOPT, CONOPT, LGO, MINOS, SNOPT) through AMPL on one workstation (8-core 16-thread AMD Ryzen 9700X, 256 GB RAM, one NVIDIA RTX 5090) with a 180-second wall-clock limit, feasibility tolerance , and relative optimality gap (Paper, Section 4, Table 1, Figure 2, and Appendix C):
| Solver | Type | gams_world Feas. / Solved (of 265) | minlplib Feas. / Solved (of 240) | Total Feas. / 505 | Total Solved / 505 | Solved (%) | Exclusive vs. GEAR (GEAR only / Baseline only) |
|---|---|---|---|---|---|---|---|
| GEAR | Global (GPU + CPU) | 264 / 251 | 237 / 170 | 501 | 421 | 83.4% | — |
| Gurobi | Global (commercial, 16T) | 254 / 227 | 218 / 174 | 472 | 401 | 79.4% | 38 / 18 |
| SCIP | Global (open-source, 16T) | 262 / 209 | 219 / 155 | 481 | 364 | 72.1% | 64 / 7 |
| BARON | Global (commercial) | 217 / 168 | 186 / 129 | 403 | 297 | 58.8% | 131 / 7 |
| Xpress | Global (commercial, 16T) | 218 / 176 | 173 / 120 | 391 | 296 | 58.6% | 138 / 13 |
| Couenne | Global (open-source) | 222 / 182 | 152 / 100 | 374 | 282 | 55.8% | 139 / 0 |
| LindoGlobal | Global (commercial) | 180 / 164 | 169 / 110 | 349 | 274 | 54.3% | 149 / 2 |
| Global union (all 6) | 6 global solvers combined | — | — | — | 427 | 84.6% | 16 / 22 |
| Knitro* | Local (matched to global D) | 263 / 231 | 225 / 170 | 488 | 401 | 79.4% | 37 / 17 |
| IPOPT* | Local (matched to global D) | 256 / 203 | 202 / 117 | 458 | 320 | 63.4% | 111 / 10 |
| CONOPT* | Local (matched to global D) | 259 / 205 | 205 / 91 | 464 | 296 | 58.6% | 133 / 8 |
| LGO* | Local (matched to global D) | 249 / 206 | 160 / 78 | 409 | 284 | 56.2% | 138 / 1 |
| MINOS* | Local (matched to global D) | 247 / 193 | 133 / 53 | 380 | 246 | 48.7% | 179 / 4 |
| SNOPT* | Local (matched to global D) | 235 / 182 | 133 / 51 | 368 | 233 | 46.1% | 191 / 3 |
GEAR certifies 421 of 505 instances (83.4%) and returns a feasible point on 501, exceeding Gurobi (401) by 20 instances and SCIP (364) by 57. Its lead is largest on gams_world (251 / 265, 94.7% vs. 227 for Gurobi and 209 for SCIP), while on minlplib GEAR (170 / 240) sits ahead of SCIP (155) and 4 instances behind Gurobi (174). Against the union of all six global solvers (427 instances), GEAR certifies 16 instances that no global baseline solves and misses 22, bringing combined portfolio coverage to 443 / 505 (Paper, Section 4.1, Table 1, and Figure 2).
The cumulative ablation in Table 2 (Paper, Section 4.2, page 9) shows how each component contributes across all 505 instances under the 180-second limit:
| Cumulative configuration (505 instances, 180 s) | Feasible | Optimal* | Solved | Step gain in Solved |
|---|---|---|---|---|
| Bound propagation + PGD (verification baseline) | 95 | 56 | 0 | — |
| + presolve and CPU solving components | 480 | 396 | 219 | +219 |
| + projected ALM primal search (GPU) | 496 | 471 | 269 | +50 |
| + constraint-aware dual bounds and clipping (GPU) | 498 | 472 | 366 | +97 |
| + lifted and refined operator relaxation (GPU) | 501 | 478 | 410 | +44 |
| + -SB branching (full GEAR) | 501 | 478 | 421 | +11 |
Here Optimal* counts runs whose returned feasible point is already within the relative gap of the best known optimum verified by any global solver, whereas Solved requires GEAR’s own certified lower bound to close Equation (13). Two structural facts stand out (Paper, Section 4.2):
- Why the verification pipeline alone solves 0 constrained NLPs: Standard input branch-and-bound with a box PGD attack (
Bound propagation + PGD) solves 0 instances. PGD searches only for a counterexample on the box without respecting ; on the 95 unconstrained (box-only) instances where every box point is feasible, PGD reaches the optimal value on 56, but the verification pipeline keeps no verified feasible incumbent to serve as a dominance-pruning threshold. - Separating primal discovery from proof completion: Once presolve (
+219, closing 72 at the root and 147 in the tree) and GPU projected ALM (+50) are active, GEAR already holds an optimal feasible point on 471 of 505 instances, yet only 269 are certified. The next three rows—constraint-aware dual bounds and clipping (+97, the single largest GPU gain), lifted and refined operator relaxations (+44), and -SB branching (+11)—raiseSolvedfrom 269 to 421 (+152) while adding only 7 optimal points (). Their primary role is closing the dual proof, turning already-found optimal incumbents into certified global optima.
Choose a relaxation that can sustain the workload
Propagating a single affine bound per operator output keeps backward passes regular and tensorized, at the price of dropping simultaneous multi-facet closure on a single box. GEAR narrows that local relaxation gap in three ways before relying on spatial refinement (Paper, Section 3.3, Appendix A.7, Table 6, and Appendices B.1–B.4):
- Coefficient-aware McCormick selection for bilinear products (): A lifted LP keeps all four McCormick facets (Equations (38)–(39)), whereas backward LBP keeps one plane per output. Instead of fixing one McCormick vertex, GEAR evaluates both candidate lower planes (for backward weight ) or both upper planes (for ) by closed-form box concretization (Equation (37)) and selects the tighter one per element. On , this raises the product lower bound from to (Figure 4a,b).
- Guarded 8-plane fused division (): Rather than decomposing through an intermediate variable, GEAR scores four corner tangents (Equation (40)) and four three-corner secant planes directly on sign-fixed guarded denominator intervals ( or ), accepting a candidate plane only after a quadratic-bilinear residual check certifies across the rectangle (Equation (41)). On , fused division lifts the lower bound from to (Figure 4c,d).
- Parallel secant-tangent univariate bounds and exact presolve rewrites: For convex/concave univariate operators (, , , , ), choosing the tangent point whose slope matches the secant slope, (Equations (32)–(36)), cuts the tangent-side gap by 26% for , 27% for , 31% for , and 23% for relative to midpoint tangents (Paper, Appendix A.7, Figure 3), while trigonometric intervals are localized at inflection points. At presolve and the root, exact graph rewrites (, completing squares, quadratic eigenbasis and log-coordinate posynomial rewrites; Figures 6–8), root certificates (Appendix B.3), and a lifted linear relaxation with McCormick, reduced RLT, OBBT, and leaf certificate transfer (Appendix B.4, Figures 9–11) close 293 of the 421 solved instances at the root, leaving 128 to close in the GPU branch-and-bound tree (with a median of 318 boxes and at least boxes on five instances; Paper, Section 4.1 and Appendix B.2).
The breakdown by problem class in Table 10 and the 40-instance disagreement audit against Gurobi and SCIP in Table 11 (Paper, Section 4.1 and Appendices D.1–D.2, pages 50–51) locate the exact boundary between GPU-batched bound propagation and CPU LP branch-and-bound:
| Problem class (Table 10) | Instances | GEAR | SCIP | Gurobi | 6-Solver Global Union | GEAR-only vs. Union | Union-only vs. GEAR |
|---|---|---|---|---|---|---|---|
| variables | 183 | 182 | 171 | 177 | 182 | 0 | 0 |
| variables | 151 | 145 | 118 | 127 | 140 | 8 | 3 |
| variables | 80 | 66 | 58 | 66 | 71 | 3 | 8 |
| variables | 65 | 28 | 17 | 29 | 32 | 5 | 9 |
| variables | 26 | 0 | 0 | 2 | 2 | 0 | 2 |
| Box constraints only () | 95 | 92 | 81 | 81 | 89 | 3 | 0 |
| constraints | 235 | 230 | 197 | 217 | 226 | 6 | 2 |
| constraints | 175 | 99 | 86 | 103 | 112 | 7 | 20 |
Transcendental terms (exp, log, sqrt, trig) | 147 | 131 | 100 | 110 | 118 | 16 | 3 |
| Polynomial / rational only | 358 | 290 | 264 | 291 | 309 | 0 | 19 |
Three operational lessons emerge from Tables 10 and 11:
- The benefit is hard-tail coverage, not easy-instance latency: On the 405 instances certified by both GEAR and at least one global baseline, the fastest CPU solver needs a median of 0.03–0.06 s across size classes, whereas GEAR pays a few seconds of graph-compilation and GPU-initialization overhead (4–29 s median). GEAR overtakes
LindoGlobal,Couenne,BARON, andXpressat 6–9 s,SCIPat 15 s, andGurobiat 35 s (Paper, Section 4.1 and Appendix D.1). - GEAR dominates on low- to medium-dimensional problems with composite transcendental nonlinearities: On instances with at most 20 constraints, GEAR certifies 322 / 330 (97.6%) versus 298 for Gurobi and 278 for SCIP. On instances with transcendental terms, GEAR certifies 131 / 147 (89.1%) versus 110 for Gurobi and 100 for SCIP—including all 16 instances certified by none of the six global solvers. In the 22-instance win audit against Gurobi and SCIP (Table 11), 16 wins come from stronger bounds on log-coordinate posynomials (
hs101,hs102,schitt_s380), polar polygon diameter bounds (polygon25–100), symmetric log-barrier collapsing (Paviani,hs110), and loose baseline factorable relaxations (pricing050,Shekelfox10), while 6 come from baseline solutions that violate original constraints by to upon AMPL re-evaluation (GEAR’s largest violation is ; Appendix B.7 and Table 11). - GPU batching does not replace RLT and warm-started simplex on large bilinear networks: On problems with constraints (pooling, wastewater, water networks, and
kallcircle packing), 20 of the 22 Global-union-only wins occur, and GEAR solves no instance with variables. On 16 of the 18 instances where Gurobi or SCIP beats GEAR (Table 11), GEAR’s lifted McCormick LP matches Gurobi’s root bound, but Gurobi re-solves warm-started node LPs with RLT and cuts at to nodes/s versus 1.1–207 nodes/s (median 27) in GEAR’s CPU lifted-LP tree, while the batched GPU bounds close a median of only 0.74% of the remaining gap on those bilinear-heavy leaves (Paper, Appendix D.2, Table 11).
Memory shapes this boundary as well: storing the dense coefficient tensor together with intermediate graph intervals scales with , so the dynamic batch controller doubles from only while of GPU memory is reserved and halves upon out-of-memory (Paper, Appendix B.5). Within its scope—bounded continuous NLPs over supported factorable operators—GEAR establishes a complementary GPU regime for global optimization, extending linear bound propagation and domain clipping from neural network verification into a complete primal-dual global solver.
Cite this note
@misc{zhou2026gear,
author = {Zhou, Duo},
title = {{GEAR: Scaling Global Optimization with Reusable Linear Bounds}},
year = {2026},
url = {https://www.duo-zhou.com/blog/gear/},
note = {Research note}
}