A Parallel Decomposition Scheme for Solving Long-Horizon Optimal Control Problems

We present a temporal decomposition scheme for solving long-horizon optimalcontrol problems. In the proposed scheme, the time domain is decomposed into aset of subdomains with partially overlapping regions. Subproblems associatedwith the subdomains are solved in parallel to obtain local primal-dualtrajectories that are assembled to obtain the global trajectories. We provide asufficient condition that guarantees convergence of the proposed scheme. Thiscondition states that the effect of perturbations on the boundary conditions(i.e., initial state and terminal dual/adjoint variable) should decayasymptotically as one moves away from the boundaries. This condition alsoreveals that the scheme converges if the size of the overlap is sufficientlylarge and that the convergence rate improves with the size of the overlap. Weprove that linear quadratic problems satisfy the asymptotic decay condition,and we discuss numerical strategies to determine if the condition holds in moregeneral cases. We draw upon a non-convex optimal control problem to illustratethe performance of the proposed scheme.