Parallel L-BFGS-B algorithm on GPU

• We approximate the generalized Cauchy point with much less calculation while maintaining a similar rate of convergence.
• We propose several new GPU-friendly expressions to compute the maximal possible step-length for backtracking and line searching.
• We demonstrate the speedup of L-BFGS-B enabled by our parallel implementation with extensive testings.

Due to the rapid advance of general-purpose graphics processing unit (GPU), it is an active research topic to study performance improvement of non-linear optimization with parallel implementation on GPU, as attested by the much research on parallel implementation of relatively simple optimization methods, such as the conjugate gradient method. We study in this context the L-BFGS-B method, or the limited memory Broyden–Fletcher–Goldfarb–Shanno with boundaries, which is a sophisticated yet efficient optimization method widely used in computer graphics as well as general scientific computation. By analyzing and resolving the inherent dependencies of some of its search steps, we propose an efficient GPU-based parallel implementation of L-BFGS-B on the GPU. We justify our design decisions and demonstrate significant speed-up by our parallel implementation in solving the centroidal Voronoi tessellation (CVT) problem as well as some typical computing problems.

Figure optionsDownload high-quality image (488 K)Download as PowerPoint slide