GPU-Based Global Optimization and Constraint Satisfaction Using Interval Analysis
Mathematical optimization is prevalent in many science and engineering fields. In many practical applications, it is desirable, and sometimes indispensable, to find the global optimum when solving nonconvex optimization problems. However, popular gradient-based methods (e.g., gradient descent methods, interior-point methods, and trust region methods) and heuristic methods (e.g., genetic algorithms, simulated annealing, and particle swarm optimization) often become trapped in local optima and are not guaranteed to find the global optimum, leading to inconsistent or incorrect assumptions and applications. Our research uses interval arithmetic, coupled with the computational power and architecture of GPU, to design and implement a GPU-based global optimization method that can efficiently enclose the guaranteed global optimum for nonconvex optimization problems. Our method is validated by enclosing the global optimum of 10 multimodal benchmark test functions with scalable dimensions. These test functions represent grand challenges of global optimization, and enclosing the guaranteed global optimum of these test functions with more than 80 variables has not been reported in the literature. Our method successfully encloses the global optimum for each of these 10 test functions with up to 10,000 variables using a server with only one GPU in reasonable computation time, far exceeding the reported results in the literature due to the unique method design and implementation based on GPU architecture. Our method is also applied to solve several practical engineering optimization problems, such as a launch vehicle design optimization problem, where the guaranteed global optimum derived by our method leads to significant profit, quality, and performance advantages in these practical applications.
People
