Efficient Dynamic Programming Implementations of Newton's Method for Unconstrained Optimal Control Problems

Authors

J. C. Dunn, D. P. Bertsekas

Year

1989

Journal Paper

Algorithm

Dynamic Programming Newton Method

Source

Journal of Optimization Theory and Applications

Identifiers

DOI 10.1007/BF00940728

Abstract¶

Naive implementations of Newton's method for unconstrainedN-stage discrete-time optimal control problems with Bolza objective functions tend to increase in cost likeN 3 asN increases. However, if the inherent recursive structure of the Bolza problem is properly exploited, the cost of computing a Newton step will increase only linearly withN. The efficient Newton implementation scheme proposed here is similar to Mayne's DDP (differential dynamic programming) method but produces the Newton step exactly, even when the dynamical equations are nonlinear. The proposed scheme is also related to a Riccati treatment of the linear, two-point boundary-value problems that characterize optimal solutions. For discrete-time problems, the dynamic programming approach and the Riccati substitution differ in an interesting way; however, these differences essentially vanish in the continuous-time limit.

Summary¶

Dunn develops efficient dynamic-programming implementations of Newton's method for unconstrained optimal-control problems. The paper clarifies how dynamic-programming structure can be exploited to solve the Newton system efficiently, connecting second-order optimization with trajectory-optimization algorithms such as DDP.