Parallel cyclic reduction strategies for linear systems that arise in dynamic optimization problems

Dynamic optimization problems are constrained by differential and algebraic equations and are found everywhere in science and engineering. A well-established method to solve these types of problems is direct transcription, where the differential equations are replaced with discretized approximations based on finite-difference or Runge–Kutta schemes. However, for problems with thousands of state variables and discretization points, direct transcription may result in nonlinear optimization problems which are too large for general-purpose optimization solvers to handle. Also, when an interior-point solver is applied, the dominant computational cost is solving the linear systems resulting from the Newton step. For large-scale nonlinear programming problems, these linear systems may become prohibitively expensive to solve. Furthermore, the systems also become too large to formulate and store in memory of a standard computer. On the other hand, direct transcription can exploit sparsity and structure of the linear systems in order to overcome these challenges. In this paper we investigate and compare two parallel linear decomposition algorithms, Cyclic Reduction (CR) and Schur complement decomposition, which take advantage of structure and sparsity. We describe the numerical conditioning of the CR algorithm when applied to the linear systems arising from dynamic optimization problems, and then compare CR with Schur complement decomposition on a number of test problems. Finally, we propose conditions under which each should be used, and describe future research directions.