Mixed coordination method for long-horizon optimal control problems

We present a new approach to solving long-horizon, discrete-time optimal control problems using the mixed coordination method. The idea is to decompose a long-horizon problem into subproblems along the time axis. The requirement that the initial state of a subproblem equal the terminal state of the preceding subproblem is relaxed by using Lagrange multipliers. The Lagrange multipliers and initial state of each subproblem are then selected as high-level variables. The equivalence of the two-level formulation and the original problem is proved for both convex and non-convex cases. The low-level subproblems are solved in parallel using extended differential dynamic programming (DDP). An efficient way to find the gradient and hessian of a low-level objective function with respect to high-level variables is developed. The high-level problem is solved using the modified Newton method. An effective procedure is developed to select initial values of multipliers based on the initial trajectory. The method can convexify the high-level problem while maintaining the separability of an originally non-convex problem. The method performs better and faster than one-level DDP for both convex and non-convex test problems.