A Fast Temporal Decomposition Procedure for Long-Horizon Nonlinear Dynamic Programming

Sen Na (), Mihai Anitescu () and Mladen Kolar ()
Additional contact information
Sen Na: International Computer Science Institute and Department of Statistics, University of California, Berkeley, Berkeley, California 94720
Mihai Anitescu: Mathematics and Computer Science Division, Argonne National Laboratory, Lemont, Illinois 60439
Mladen Kolar: Booth School of Business, University of Chicago, Chicago, Illinois 60637

Mathematics of Operations Research, 2024, vol. 49, issue 2, 1012-1044

Abstract: We propose a fast temporal decomposition procedure for solving long-horizon nonlinear dynamic programs. The core of the procedure is sequential quadratic programming (SQP) that utilizes a differentiable exact augmented Lagrangian as the merit function. Within each SQP iteration, we approximately solve the Newton system using an overlapping temporal decomposition strategy. We show that the approximate search direction is still a descent direction of the augmented Lagrangian provided the overlap size and penalty parameters are suitably chosen, which allows us to establish the global convergence. Moreover, we show that a unit step size is accepted locally for the approximate search direction and further establish a uniform, local linear convergence over stages. This local convergence rate matches the rate of the recent Schwarz scheme (Na et al. 2022). However, the Schwarz scheme has to solve nonlinear subproblems to optimality in each iteration, whereas we only perform a single Newton step instead. Numerical experiments validate our theories and demonstrate the superiority of our method.

Keywords: Primary: 90-08; 90C06; 90C30; 90C39; 90C55; 90C90; nonlinear dynamic programming; temporal decomposition; sequential quadratic programming; augmented Lagrangian (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2023.1378 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:2:p:1012-1044

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().