(253b) Advances in Decomposition Strategies for Non-Convex Nonlinear Programs
In this presentation, we describe two decomposition strategies for solving large-scale nonconvex structured optimization problems. In the first strategy, we decompose all scale-dependent operations of a serial algorithm to achieve parallelization. We focus on the parallelization of the interior-point (IP) algorithm and use the Schur-complement to decompose the solution of the KKT system in each iteration of the IP algorithm. The second decomposition strategy partitions the large-scale optimization problem into subproblems and coordinates their solutions to find the overall optimal solution. For this second type of decomposition, we focus on studying the Alternating Direction Method of Multipliers (ADMM). We present the pros and cons of both approaches and propose acceleration techniques to improve both.
We demonstrate these two decomposition strategies on several nonconvex stochastic programming and dynamic optimization problems. We also study the convergence of ADMM on nonconvex problems, and present connections between ADMM and the classical augmented Lagrangian (AL). We summarize our results in terms of a Lyapunov function and primal and dual feasibility metric and demonstrate that performing multiple coordination steps at each ADMM iteration approaches the behavior of the AL method.