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), with a differentiable exact augmented Lagrangian being the merit function. Within each SQP iteration, we solve the Newton system approximately using an overlapping temporal decomposition. We show that the approximated 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 global convergence. Moreover, we show that a unit stepsize is accepted locally for the approximated search direction, and further establish a uniform, local linear convergence over stages. Our local convergence rate matches the rate of the recent Schwarz scheme [28]. However, the Schwarz scheme has to solve nonlinear subproblems to optimality in each iteration, while we only perform one Newton step instead. Numerical experiments validate our theories and demonstrate the superiority of our method.
Sen Na
PhD (2016-2021)
Sen Na was a PhD student in the Department of Statistics at The University of Chicago. Prior to graduate school, he obtained BS in mathematics at Nanjing University, China. His research interests lie in nonlinear and nonconvex optimization, dynamic programming, high-dimensional statistics and their interface.
Mladen Kolar
Associate Professor of Econometrics and Statistics
Mladen Kolar is an Associate Professor of Econometrics and Statistics at the University of Chicago Booth School of Business. His research is focused on high-dimensional statistical methods, graphical models, varying-coefficient models and data mining, driven by the need to uncover interesting and scientifically meaningful structures from observational data.