On the Convergence of Overlapping Schwarz Decomposition for Nonlinear Optimal Control

• 成果类型: Article
• 署名作者: Na, Sen; Shin, Sungho; Anitescu, Mihai; Zavala, Victor M.
• 署名单位: University of Chicago; University of Wisconsin System; University of Wisconsin Madison; United States Department of Energy (DOE); Argonne National Laboratory
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3194087
• 发表日期: 2022
• 页码: 5996-6011
• 关键词: Decomposition methods; nonlinear programming; optimal control; overlapping; parallel algorithms

摘要

We study the convergence properties of an overlapping Schwarz decomposition algorithm for solving nonlinear optimal control problems (OCPs). The algorithm decomposes the time domain into a set of overlapping subdomains, and solves all subproblems defined over subdomains in parallel. The convergence is attained by updating primal-dual information at the boundaries of overlapping subdomains. We show that the algorithm exhibits local linear convergence, and that the convergence rate improves exponentially with the overlap size. We also establish global convergence results for a general quadratic programming, which enables the application of the Schwarz scheme inside second-order optimization algorithms (e.g., sequential quadratic programming). The theoretical foundation of our convergence analysis is a sensitivity result of nonlinear OCPs, which we call exponential decay of sensitivity (EDS). Intuitively, EDS states that the impact of perturbations at domain boundaries (i.e., initial and terminal time) on the solution decays exponentially as one moves into the domain. Here, we expand a previous analysis available in the literature by showing that EDS holds for both primal and dual solutions of nonlinear OCPs, under uniform second-order sufficient condition, controllability condition, and boundedness condition. We conduct experiments with a quadrotor motion planning problem and a partial differential equations (PDE) control problem to validate our theory, and show that the approach is significantly more efficient than alternating direction method of multipliers and as efficient as the centralized interior-point solver.