« search calendars« DIMACS Workshop on ADMM and Proximal Splitting Methods in Optimization

«  Parallel Schur-complement and ADMM Decomposition Strategies for Dynamic Optimization Problems

Parallel Schur-complement and ADMM Decomposition Strategies for Dynamic Optimization Problems

June 13, 2018, 1:30 PM - 2:00 PM



Rutgers University

CoRE Building

96 Frelinghuysen Road

Piscataway, NJ 08854

Click here for map.

John Siirola, Sandia National Laboratories

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.