John Siirola, Sandia National Laboratories

Abstract

Nonlinear programming is an effective technique to formulate and solve optimal control problems in many industries. These problems are often formulated as dynamic optimization problems, and in many cases, an optimal solution can be found using current off-the-shelf solvers. However, as the model rigor, system complexity increases, the size of these optimization problems often exceeds the computational capabilities of a serial algorithm on a single workstation. Efficient solution demands the development of algorithms that allow parallel solution.

In this presentation, we describe two decomposition strategies for time-discretized systems. In the first strategy, we focus on the parallelization of the interior-point (IP) algorithm and use a Schur-complement approach to decompose the solution of the KKT system in each iteration of the IP algorithm. We demonstrate the efficiency and scalability of this approach for solving nonlinear programming problems with millions of variables and constraints. In the second strategy, we partition the overall problem into N subproblems and investigate the use of the Alternating Direction Method of Multipliers (ADMM). We demonstrate the applicability of ADMM for decomposing challenging nonconvex optimal control problems.  To study the convergence of ADMM in the nonconvex setting, we present connections between the ADMM and the classical augmented Lagrangian (AL) and summarize our results in terms of a Lyapunov function and primal and dual feasibility metrics.