(463e) An Augmented Lagrangian Approach for Parallel Solution of NLP Problems On Graphics Processing Units

Large-scale nonlinear programming
(NLP) has proven to be an effective framework for optimal process design and
operation. As problem sizes continue to grow, the capabilities of a single
workstation can become insufficient. This, coupled with the emergence of new
concurrent computing architectures, drives the need for effective parallel
algorithms.

Graphics processing units (GPUs)
are emerging as massively parallel systems that offer a large degree of
parallelism at a relatively low cost. However, compared with classic
multiple-instruction-multiple-data (MIMD) the single-instruction-multiple-thread
(SIMT) architecture of the modern GPU limits its direct application in many
numerical applications. This architecture contains a large number of processing
cores, however, groups of these cores must be concurrently executing the same
instruction. This makes the architecture inappropriate for parallel direct
factorization – the primary numerical workhorse of most nonlinear
programming solvers.

In this paper, we propose an
Augmented Lagrangian approach for parallel solution of large-scale nonlinear programming
problems on a GPU. The algorithm is iterative at three levels. The first level replaces
the original problem by a sequence of bound-constrained optimization problems using
an Augmented Lagrangian method. Each of these bound-constrained problems is
solved using a nonlinear interior-point method. Inside the interior-point
method, the barrier subproblems are solved using a variation of Newton's method,
where the linear system is solved using a preconditioned conjugate gradient
method (PCG). If the PCG approach detects negative curvature, a diagonal
modification of the Hessian is made to ensure positive definiteness. The primary
advantage of this algorithm is that is allows use of the PCG method, instead of
using direct factorization. The PCG method can be implemented efficiently on
the GPU in parallel.

Finally, numerical experiments are
reported using a set of problems from COPS test collection. We compare the
computational results of our serial and parallel versions with the IPOPT
nonlinear optimization package, and show that significant speedup
(approximately an order of magnitude) is possible.