Journal
MATHEMATICS OF OPERATIONS RESEARCH
Volume -, Issue -, Pages -Publisher
INFORMS
DOI: 10.1287/moor.2023.1378
Keywords
nonlinear dynamic programming; temporal decomposition; sequential quadratic programming; augmented Lagrangian
Ask authors/readers for more resources
We propose a fast temporal decomposition procedure using sequential quadratic programming (SQP) to solve long-horizon nonlinear dynamic programs. The procedure utilizes a differentiable exact augmented Lagrangian as the merit function. By approximately solving the Newton system with an overlapping temporal decomposition strategy, we establish the global convergence and a uniform, local linear convergence rate.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available