Global optimization tailored for graphics processing units: Complete and rigorous search for large-scale nonlinear minimization
Open Access
- 3 April 2026
- journal article
- research article
- Published by Oxford University Press (OUP) in PNAS Nexus
- Vol. 5 (4)
Abstract
This paper introduces a numerical method to enclose the global minimum of a nonlinear function subject to simple bounds on the variables. Using interval analysis, coupled with the computational power and architecture of graphics processing units (GPUs), the method iteratively rules out the regions in the search domain where the global minimum cannot exist and leaves a finite set of regions where the global minimum must exist. For effectiveness, because of the rigor of interval analysis, the method is guaranteed to enclose the global minimum even in the presence of rounding errors. For efficiency, the method employs a novel GPU-based single program, single data parallel programming style to circumvent major GPU performance bottlenecks, and a variable cycling technique is also integrated into the method to reduce computational cost when minimizing large-scale nonlinear functions. The method is validated by minimizing 11 benchmark test functions with scalable dimensions, including the well-known Ackley function, Griewank function, Levy function, Rastrigin function, and Rosenbrock function. These benchmark test functions represent grand challenges of global optimization, and enclosing the guaranteed global minimum of these benchmark test functions with >80 dimensions has not been reported in the literature. Our method completely searches the feasible domain and successfully encloses the guaranteed global minimum of these 11 benchmark test functions with up to 10,000 dimensions using only one GPU in a reasonable computation time, far exceeding the reported results in the literature due to the unique method design and implementation based on GPU architecture.Keywords
All Related Versions
This publication has 36 references indexed in Scilit:
- Recent advances in trust region algorithmsMathematical Programming, 2015
- Design of computer experiments: space filling and beyondStatistics and Computing, 2011
- A review of recent advances in global optimizationJournal of Global Optimization, 2008
- A Branch-and-Prune Method for Global Optimization2001
- A branch-and-reduce approach to global optimizationJournal of Global Optimization, 1996
- Rigorous Global Search: Continuous Problems1996
- Exploratory designs for computational experimentsJournal of Statistical Planning and Inference, 1995
- Lipschitzian optimization without the Lipschitz constantJournal of Optimization Theory and Applications, 1993
- On the limited memory BFGS method for large scale optimizationMathematical Programming, 1989
- Convergence and restart in branch-and-bound algorithms for global optimization. Application to concave minimization and D.C. Optimization problemsMathematical Programming, 1988