DZ~/duo-zhou
← All research notes

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.

Global OptimizationNonlinear ProgrammingLinear Bound PropagationGPU Computing

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 B0⊂RnB_0 \subset \mathbb{R}^n:

p⋆=min⁡x∈B0f0(x)subject tofi(x)≤0,i=1,…,m.p^\star = \min_{x\in B_0} f_0(x) \quad\text{subject to}\quad f_i(x)\leq 0,\qquad i=1,\ldots,m.

Source equalities and two-sided inequalities are written as pairs of one-sided inequalities with an absolute feasibility tolerance τfeas=10−6\tau_{\mathrm{feas}} = 10^{-6} absorbed into each fif_i (for example, g(x)=0g(x) = 0 becomes g(x)−τfeas≤0g(x) - \tau_{\mathrm{feas}} \leq 0 and −g(x)−τfeas≤0-g(x) - \tau_{\mathrm{feas}} \leq 0), 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 B=[x‾,x‾]⊆B0B = [\underline{x}, \overline{x}] \subseteq B_0, write the feasible set and local optimum as F(B)={x∈B:fi(x)≤0,  i=1,…,m}\mathcal{F}(B) = \{x \in B : f_i(x) \leq 0,\; i = 1, \ldots, m\} and p⋆(B)=min⁡x∈F(B)f0(x)p^\star(B) = \min_{x \in \mathcal{F}(B)} f_0(x) (Equation (3)). A run certifies global optimality when its verified feasible incumbent P=f0(xˉ)P = f_0(\bar{x}) and global lower bound D≤p⋆D \leq p^\star satisfy the relative gap criterion (Paper, Section 4, Equation (13)):

P−Dmax⁡(1,∣P∣,∣D∣)≤10−4.\frac{P - D}{\max(1, \lvert P\rvert, \lvert D\rvert)} \leq 10^{-4}.

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 f0f_0 over the entire box—including infeasible points—so it can remain strictly below p⋆p^\star no matter how finely the box is split. Minimizing xx on [0,1][0, 1] subject to x≥1/2x \geq 1/2 has optimum 1/21/2, yet every sub-box containing 00 retains an objective-only lower bound of 00; 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 KK, a useful runtime accounting model is

Tsearch≈NvisitedTbatchK+Tqueue.T_{\mathrm{search}}\approx N_{\mathrm{visited}}\frac{T_{\mathrm{batch}}}{K} +T_{\mathrm{queue}}.

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 mm constraints as the outputs of a single computation graph F(x)=(f0(x),f1(x),…,fm(x))F(x) = (f_0(x), f_1(x), \ldots, f_m(x)) (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 fi(x)=ai⊤x+cif_i(x) = a_i^\top x + c_i 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 B=[x‾,x‾]B = [\underline{x}, \overline{x}], backward linear bound propagation substitutes valid local linear relaxations h‾(y)≤h(y)≤h‾(y)\underline{h}(y) \leq h(y) \leq \overline{h}(y) from the outputs toward the inputs according to the sign of each backward weight (γh‾(y)\gamma \underline{h}(y) for γ≥0\gamma \geq 0 and γh‾(y)\gamma \overline{h}(y) for γ<0\gamma < 0; Section 2, Equations (4)–(5), and Appendix A.2, Equation (15)), producing valid linear lower bounds on F(B)\mathcal{F}(B):

f‾i(x)=ai⊤x+ci≤fi(x)∀x∈F(B),i=0,…,m.\underline{f}_i(x) = a_i^\top x + c_i \leq f_i(x) \qquad \forall x \in \mathcal{F}(B), \quad i = 0, \ldots, m.

Across a batch of KK boxes in nn variables with mm constraints, the coefficients form dense tensors (Paper, Section 3.2, Equation (7), and Appendix A.2, Equation (17)):

A∈RK×(m+1)×n,c∈RK×(m+1).A \in \mathbb{R}^{K \times (m+1) \times n}, \qquad c \in \mathbb{R}^{K \times (m+1)}.

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 min⁡x∈Bf‾i(x)=ci+∑j=1nmin⁡{ai,jx‾j,ai,jx‾j}\min_{x \in B} \underline{f}_i(x) = c_i + \sum_{j=1}^n \min\{a_{i,j}\underline{x}_j, a_{i,j}\overline{x}_j\} (Section 2, Equation (6)). Its slope vector aia_i records how the function varies across BB. Stacking the constraint linear bounds (together with any exact linear rows and presolve cuts) as A=[a1,…,am]⊤A = [a_1, \ldots, a_m]^\top and c=(c1,…,cm)⊤c = (c_1, \ldots, c_m)^\top defines an outer polyhedral relaxation of the feasible set on BB (Paper, Section 3.3, Equation (8)):

P(B)={x∈B:Ax+c≤0}⊇F(B),pLP(B)=min⁡x∈P(B)f‾0(x)≤p⋆(B).\mathcal{P}(B) = \{x \in B : Ax + c \leq 0\} \supseteq \mathcal{F}(B), \qquad p^{\mathrm{LP}}(B) = \min_{x \in \mathcal{P}(B)} \underline{f}_0(x) \leq p^\star(B).

Instead of calling a simplex or interior-point LP solver at every box to evaluate pLP(B)p^{\mathrm{LP}}(B), GEAR reuses (a0,c0)(a_0, c_0) and (A,c)(A, c) in five ways (Paper, Figure 1 and Sections 3.3–3.5):

  1. Lagrangian objective lower bound: Dualizing the constraint rows Ax+c≤0Ax + c \leq 0 with nonnegative multipliers λ≥0\lambda \geq 0 while keeping the box B=[x‾,x‾]B = [\underline{x}, \overline{x}] as the inner minimization domain yields the Lagrangian bound (Paper, Section 3.3, Equation (9), and Appendix A.4, Proposition A.1):
dB(λ)=min⁡x∈B[f‾0(x)+λ⊤(Ax+c)]=c0+c⊤λ+∑j=1nmin⁡{aj(λ)x‾j,  aj(λ)x‾j},d_B(\lambda) = \min_{x \in B}\left[\underline{f}_0(x) + \lambda^\top (Ax + c)\right] = c_0 + c^\top \lambda + \sum_{j=1}^n \min\left\{a_j(\lambda)\underline{x}_j,\; a_j(\lambda)\overline{x}_j\right\},

where a(λ)=a0+A⊤λa(\lambda) = a_0 + A^\top \lambda. At every feasible point x∈F(B)x \in \mathcal{F}(B), f‾i(x)≤fi(x)≤0\underline{f}_i(x) \leq f_i(x) \leq 0, so dB(λ)≤pLP(B)≤p⋆(B)d_B(\lambda) \leq p^{\mathrm{LP}}(B) \leq p^\star(B) for any λ≥0\lambda \geq 0, and LP strong duality gives max⁡λ≥0dB(λ)=pLP(B)\max_{\lambda \geq 0} d_B(\lambda) = p^{\mathrm{LP}}(B) whenever P(B)≠∅\mathcal{P}(B) \neq \emptyset (Proposition A.1). In the toy example min⁡x∈[0,1]x\min_{x \in [0,1]} x subject to 1/2−x≤01/2 - x \leq 0, setting λ=1\lambda = 1 gives x+1⋅(1/2−x)=1/2x + 1 \cdot (1/2 - x) = 1/2 across the entire box, recovering the constrained optimum without branching (Section 3.3 and Appendix A.4). More generally, if a constraint row ii is strictly positive across the minimizing face X0=argmin⁡x∈Bf‾0(x)X_0 = \operatorname{argmin}_{x \in B} \underline{f}_0(x) (vi=min⁡x∈X0(ai⊤x+ci)>0v_i = \min_{x \in X_0}(a_i^\top x + c_i) > 0), small steps along eie_i strictly raise dBd_B at rate viv_i (Theorem A.2). Because the inner minimization is coordinate-separable, each evaluation of dB(λ)d_B(\lambda) and its supergradient Axλ+cAx_\lambda + c at an inner minimizer xλx_\lambda costs O(mn)O(mn) 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 mn≤2×105mn \leq 2 \times 10^5), evaluating dB(λ)d_B(\lambda) with outward rounding every 50 PDHG steps and retaining the best certified bound (Paper, Section 3.3 and Appendix B.5, Figure 12).

  1. Incumbent-independent infeasibility certificates: Whenever a nonnegative combination ν≥0\nu \geq 0 satisfies
min⁡x∈Bν⊤(Ax+c)>0,ν≥0  ⟹  F(B)=∅,\min_{x \in B} \nu^\top (Ax + c) > 0, \qquad \nu \geq 0 \implies \mathcal{F}(B) = \emptyset,

the box BB cannot contain a feasible point and is discarded immediately (Paper, Section 3.3, Equation (10)). Unit vectors ν=ei\nu = e_i test each individual constraint in closed form; for the lowest-bound boxes whose constraints are only jointly inconsistent, ν\nu is taken from the multipliers of a phase-one LP minimizing the maximum violation min⁡{t:Ax+c≤t1,  t≥0,  x∈B}\min\{t : Ax + c \leq t\mathbf{1},\; t \geq 0,\; x \in B\} 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).

  1. Relaxed and complete domain clipping: Adapting Clip-and-Verify (Zhou et al., 2025) to nonlinear constraint rows, relaxed clipping uses Li=min⁡x∈B(ai⊤x+ci)L_i = \min_{x \in B}(a_i^\top x + c_i) to tighten each coordinate interval in O(mn)O(mn) per sweep (Paper, Section 3.3 and Appendix A.5, Equation (25)):
x‾j←min⁡ ⁣{x‾j,  x‾j−Liai,j}(ai,j>0),x‾j←max⁡ ⁣{x‾j,  x‾j−Liai,j}(ai,j<0).\overline{x}_j \leftarrow \min\!\left\{\overline{x}_j,\; \underline{x}_j - \frac{L_i}{a_{i,j}}\right\} \quad (a_{i,j} > 0), \qquad \underline{x}_j \leftarrow \max\!\left\{\underline{x}_j,\; \overline{x}_j - \frac{L_i}{a_{i,j}}\right\} \quad (a_{i,j} < 0).

Complete clipping tightens intermediate graph intervals by maximizing min⁡x∈B[z‾(x)+β⊤(Ax+c)]\min_{x \in B}[\underline{z}(x) + \beta^\top(Ax + c)] over β≥0\beta \geq 0—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 F(B)=∅\mathcal{F}(B) = \emptyset.

Reuse geometry without growing the node state with depth

Because any child box Bchild⊆BparentB_{\mathrm{child}} \subseteq B_{\mathrm{parent}} satisfies F(Bchild)⊆F(Bparent)\mathcal{F}(B_{\mathrm{child}}) \subseteq \mathcal{F}(B_{\mathrm{parent}}), 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).

  1. Multiplier-weighted smart branching (λ\lambda-SB): Classical smart branching in neural verification splits each candidate coordinate and bounds both children, requiring 2n2n 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 jj directly from the cached linear bounds and the best Lagrangian multipliers λbest\lambda_{\mathrm{best}} without bounding any child (Paper, Section 3.5, Equation (12)):
Sj=wj(∣a0,j∣+∑i=1mλibest∣ai,j∣),wj=x‾j−x‾j.S_j = w_j \left(\lvert a_{0,j}\rvert + \sum_{i=1}^m \lambda_i^{\mathrm{best}}\lvert a_{i,j}\rvert\right), \qquad w_j = \overline{x}_j - \underline{x}_j.

Summing absolute coefficient magnitudes prevents opposing objective and constraint slopes from cancelling, and Lemma A.5 shows that Sj/4S_j / 4 upper-bounds the average one-step midpoint gain of the mixed row a(λ)⊤x+c(λ)a(\lambda)^\top x + c(\lambda) (Paper, Appendix A.9, Equation (51)). Maximization is restricted to coordinates with wj≥τmax⁡kwkw_j \geq \tau \max_k w_k (τ∈(0,1]\tau \in (0, 1]) and paired with a count guard that forces a split along the relatively widest coordinate at least once every n+1n + 1 splits, guaranteeing geometric box shrinkage max⁡j(wj(B)/wj0)≤2−⌊k/(n(n+1))⌋\max_j (w_j(B)/w_j^0) \leq 2^{-\lfloor k/(n(n+1))\rfloor} at depth kk and conditional finite ε\varepsilon-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 (LB(B)≥UB\mathrm{LB}(B) \geq \mathrm{UB}) without a good feasible incumbent. Calling a sequential KKT-factorization solver per box would bottleneck the GPU pipeline.

  1. 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):
ϕρ(x;μ)=f0(x)+ρ2∑i=1m[fi(x)+μiρ]+2−∥μ∥222ρ,[t]+=max⁡{t,0}.\phi_\rho(x; \mu) = f_0(x) + \frac{\rho}{2}\sum_{i=1}^m \left[f_i(x) + \frac{\mu_i}{\rho}\right]_+^2 - \frac{\lVert\mu\rVert_2^2}{2\rho}, \qquad [t]_+ = \max\{t, 0\}.

Each outer iteration takes a fixed budget of projected Adam steps on BB using the exact gradient ∇xϕρ(x;μ)=∇f0(x)+∑i=1m[μi+ρfi(x)]+∇fi(x)\nabla_x \phi_\rho(x; \mu) = \nabla f_0(x) + \sum_{i=1}^m [\mu_i + \rho f_i(x)]_+ \nabla f_i(x) (Equation (43)), updates μ←[μ+ρf(x)]+\mu \leftarrow [\mu + \rho f(x)]_+, and increases ρ\rho when the maximum constraint violation fails to shrink sufficiently. The dual evaluation warm-starts this primal search: GEAR initializes xx at xbest∈argmin⁡x∈B[f‾0(x)+λbest⊤(Ax+c)]x_{\mathrm{best}} \in \operatorname{argmin}_{x \in B}[\underline{f}_0(x) + \lambda_{\mathrm{best}}^\top(Ax + c)]—which already lies in the low-objective basin of the linear relaxation—and initializes μ(0)=κλbest\mu^{(0)} = \kappa \lambda_{\mathrm{best}} 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 PP only after passing the unscaled feasibility gate max⁡i[fi(xˉ)]+≤10−6\max_i [f_i(\bar{x})]_+ \leq 10^{-6} 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 10−610^{-6}, and relative optimality gap 10−410^{-4} (Paper, Section 4, Table 1, Figure 2, and Appendix C):

SolverTypegams_world Feas. / Solved (of 265)minlplib Feas. / Solved (of 240)Total Feas. / 505Total Solved / 505Solved (%)Exclusive vs. GEAR (GEAR only / Baseline only)
GEARGlobal (GPU + CPU)264 / 251237 / 17050142183.4%—
GurobiGlobal (commercial, 16T)254 / 227218 / 17447240179.4%38 / 18
SCIPGlobal (open-source, 16T)262 / 209219 / 15548136472.1%64 / 7
BARONGlobal (commercial)217 / 168186 / 12940329758.8%131 / 7
XpressGlobal (commercial, 16T)218 / 176173 / 12039129658.6%138 / 13
CouenneGlobal (open-source)222 / 182152 / 10037428255.8%139 / 0
LindoGlobalGlobal (commercial)180 / 164169 / 11034927454.3%149 / 2
Global union (all 6)6 global solvers combined———42784.6%16 / 22
Knitro*Local (matched to global D)263 / 231225 / 17048840179.4%37 / 17
IPOPT*Local (matched to global D)256 / 203202 / 11745832063.4%111 / 10
CONOPT*Local (matched to global D)259 / 205205 / 9146429658.6%133 / 8
LGO*Local (matched to global D)249 / 206160 / 7840928456.2%138 / 1
MINOS*Local (matched to global D)247 / 193133 / 5338024648.7%179 / 4
SNOPT*Local (matched to global D)235 / 182133 / 5136823346.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)FeasibleOptimal*SolvedStep gain in Solved
Bound propagation + PGD (verification baseline)95560—
+ presolve and CPU solving components480396219+219
+ projected ALM primal search (GPU)496471269+50
+ constraint-aware dual bounds and clipping (GPU)498472366+97
+ lifted and refined operator relaxation (GPU)501478410+44
+ λ\lambda-SB branching (full GEAR)501478421+11

Here Optimal* counts runs whose returned feasible point is already within the 10−410^{-4} relative gap of the best known optimum verified by any global solver, whereas Solved requires GEAR’s own certified lower bound DD to close Equation (13). Two structural facts stand out (Paper, Section 4.2):

  1. 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 fi(x)≤0f_i(x) \leq 0; 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.
  2. 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 λ\lambda-SB branching (+11)—raise Solved from 269 to 421 (+152) while adding only 7 optimal points (471→478471 \to 478). 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 (xyxy): 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 γ≥0\gamma \geq 0) or both upper planes (for γ<0\gamma < 0) by closed-form box concretization (Equation (37)) and selects the tighter one per element. On [−5,−1]×[−5,−2][-5, -1] \times [-5, -2], this raises the product lower bound from −10-10 to +2+2 (Figure 4a,b).
  • Guarded 8-plane fused division (x/yx/y): Rather than decomposing x/y=x⋅(1/y)x/y = x \cdot (1/y) through an intermediate variable, GEAR scores four corner tangents (Equation (40)) and four three-corner secant planes directly on sign-fixed guarded denominator intervals (yL≥δdiv>0y_L \geq \delta_{\mathrm{div}} > 0 or yU≤−δdiv<0y_U \leq -\delta_{\mathrm{div}} < 0), accepting a candidate plane p(x,y)p(x,y) only after a quadratic-bilinear residual check certifies Rp(x,y)=yp(x,y)−x≤0R_p(x,y) = y p(x,y) - x \leq 0 across the rectangle (Equation (41)). On [1,3]×[0.5,2][1, 3] \times [0.5, 2], fused division lifts the lower bound from 0.320.32 to 0.500.50 (Figure 4c,d).
  • Parallel secant-tangent univariate bounds and exact presolve rewrites: For convex/concave univariate operators (log⁡\log, ⋅\sqrt{\cdot}, 1/x1/x, exp⁡\exp, tpt^p), choosing the tangent point t0t_0 whose slope matches the secant slope, h′(t0)=(h(β)−h(α))/(β−α)h'(t_0) = (h(\beta) - h(\alpha))/(\beta - \alpha) (Equations (32)–(36)), cuts the tangent-side gap by 26% for log⁡\log, 27% for ⋅\sqrt{\cdot}, 31% for 1/x1/x, and 23% for exp⁡\exp 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 (u⋅u→Sqr(u)u \cdot u \to \mathrm{Sqr}(u), 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 10510^5 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)InstancesGEARSCIPGurobi6-Solver Global UnionGEAR-only vs. UnionUnion-only vs. GEAR
≤5\leq 5 variables18318217117718200
6–206\text{–}20 variables15114511812714083
21–10021\text{–}100 variables806658667138
101–1000101\text{–}1000 variables652817293259
>1000> 1000 variables26002202
Box constraints only (m=0m = 0)959281818930
1–201\text{–}20 constraints23523019721722662
>20> 20 constraints1759986103112720
Transcendental terms (exp, log, sqrt, trig)147131100110118163
Polynomial / rational only358290264291309019

Three operational lessons emerge from Tables 10 and 11:

  1. 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, and Xpress at 6–9 s, SCIP at 15 s, and Gurobi at 35 s (Paper, Section 4.1 and Appendix D.1).
  2. 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 1.4×10−61.4 \times 10^{-6} to 0.160.16 upon AMPL re-evaluation (GEAR’s largest violation is 9.9999994×10−79.9999994 \times 10^{-7}; Appendix B.7 and Table 11).
  3. GPU batching does not replace RLT and warm-started simplex on large bilinear networks: On problems with >20> 20 constraints (pooling, wastewater, water networks, and kall circle packing), 20 of the 22 Global-union-only wins occur, and GEAR solves no instance with >1,000> 1{,}000 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 2.9×1032.9 \times 10^3 to 4.0×1044.0 \times 10^4 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 A∈RK×(m+1)×nA \in \mathbb{R}^{K \times (m+1) \times n} together with intermediate graph intervals scales with K(m+1)nK(m+1)n, so the dynamic batch controller doubles KK from k0=2k_0 = 2 only while <45%< 45\% of GPU memory is reserved and halves KK 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

BIBTEX

@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}
}