基于GPU加速求解MINLP问题的SQP并行算法

摘要

针对确定性算法求解大型复杂混合整数非线性规划的时间不可接受问题,通过对序贯二次规划算法(SQP)和图形处理器(GPU)的架构特点分析,提出了基于GPU加速策略的并行化SQP算法.算法的主要思想是通过枚举法确定二元变量的取值,在保证取值完整的基础上,使用CPU+ GPU的并行策略,同时运用大量线程进行非线性规划子问题的求解.算例的数值实验结果表明:本文所提出的算法较之传统串行计算具有较好的加速效果,特别适合求解二元变量较多,约束条件相对少的MINLP问题.%To solve the problem of unacceptable execution time for solving large-scale and complex mixed integer non-linear programming problems by using deterministic algorithms, a paralleled sequential quadratic programming algorithm on the basis of GPU acceleration was proposed, in which a thorough analysis of the SQP algorithm and the framework of GPU was made. In the proposed method, enumeration algorithm was used to deal with binary variables, and the CPU +GPU strategy and the GPU in parallel were used to accelerate convergence rate. Numerical experiments show that compared to the typical serial algorithm, the proposed algorithm possesses a better convergence performance for solving MINLP problems with more binary variables and less constraints.