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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Luenberger, D. G.,Optimization by Vector Space Methods, Wiley, New York, New York, 1969.
Dennis, J. E., Jr., andSchnabel, R. B.,Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.
Murray, D. M., andYakowitz, S.,Differential Dynamic Programming and Newton's Method for Discrete Optimal Control Problems, Journal of Optimization Theory and Applications, Vol. 43, pp. 395–414, 1984.
Mayne, D. Q.,A Second-Order Gradient Method for Determining Optimal Trajectories of Nonlinear Discrete-Time Systems, International Journal on Control, Vol. 3, pp. 85–95, 1966.
Bellman, R. E.,Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1957.
Jacobson, D. H., andMayne, D. Q.,Differential Dynamic Programming, American Elsevier, New York, New York, 1970.
Polak, E.,Computational Methods in Optimization, Academic Press, New York, New York, 1971.
Bliss, G. A.,Lectures on the Calculus of Variations, University of Chicago Press, Chicago, Illinois, 1946.
Hestenes, M.,Calculus of Variations and Optimal Control, Robert E. Krieger Publishing Company, Huntington, New York, 1980.
Griewank, A.,A Superlinear Convergence of Secant Methods on Mildly Nonlinear Problems in Hilbert Space (to appear).
Kelley, C. T., andSachs, E.,A Pointwise Quasi-Newton Method for Unconstrained Optimal Control Problems, Numerische Mathematik, Vol. 55, pp. 159–176, 1989.
Dreyfus, S. E.,Dynamic Programming and the Calculus of Variations, Academic Press, New York, New York, 1965.
Keller, H.,Two-Point Boundary-Value Problems, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1976.
Merriam, C. W., III,An Algorithm for the Iterative Solution of a Class of Two-Point Boundary-Value Problems, SIAM Journal on Control and Optimization, Series A, Vol. 2, pp. 1–10, 1964.
Mitter, S. K.,Successive Approximation Methods for the Solution of Optimal Control Problems, Automatica, Vol. 3, pp. 135–149, 1966.
Pantoja, J.,Differential Dynamic Programming and Newton's Method, International Journal on Control, Vol. 47, pp. 1539–1553, 1988.
Author information
Authors and Affiliations
Additional information
Communicated by E. Polak
This work was supported by the National Science Foundation, Grant No. DMS-85-03746.
Rights and permissions
About this article
Cite this article
Dunn, J.C., Bertsekas, D.P. Efficient dynamic programming implementations of Newton's method for unconstrained optimal control problems. J Optim Theory Appl 63, 23–38 (1989). https://doi.org/10.1007/BF00940728
Issue Date:
DOI: https://doi.org/10.1007/BF00940728