Abstract
The purpose of this paper is to draw a detailed comparison between Newton's method, as applied to discrete-time, unconstrained optimal control problems, and the second-order method known as differential dynamic programming (DDP). The main outcomes of the comparison are: (i) DDP does not coincide with Newton's method, but (ii) the methods are close enough that they have the same convergence rate, namely, quadratic.
The comparison also reveals some other facts of theoretical and computational interest. For example, the methods differ only in that Newton's method operates on a linear approximation of the state at a certain point at which DDP operates on the exact value. This would suggest that DDP ought to be more accurate, an anticipation borne out in our computational example. Also, the positive definiteness of the Hessian of the objective function is easy to check within the framework of DDP. This enables one to propose a modification of DDP, so that a descent direction is produced at each iteration, regardless of the Hessian.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Halkin, H.,A Maximum Principle of Pontryagin Type for Systems Described by Nonlinear Difference Equations, SIAM Journal on Control, Vol. 4, pp. 90–111, 1966.
Mayne, D.,A Second-Order Gradient Method for Determining Optimal Trajectories of Nonlinear Discrete-Time Systems, International Journal on Control, Vol. 3, pp. 85–95, 1966.
Jacobson, D. H., andMayne, D. Q.,Differential Dynamic Programming, American Elsevier, New York, New York, 1970.
Dyer, P., andMcReynolds, S.,The Computational Theory of Optimal Control, Academic Press, New York, New York, 1979.
Ohno, K.,A New Approach of Differential Dynamic Programming for Discrete-Time Systems, IEEE Transactions on Automatic Control, Vol. AC-23, pp. 37–47, 1978.
Bellman, R., andDreyfus, S.,Applied Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1962.
Larson, R.,State Increment Dynamic Programming, Elsevier, New York, New York, 1968.
Yakowitz, S.,Convergence Bounds for the State Increment Dynamic Programming Method, Automatica, Vol. 19, pp. 53–60, 1983.
Murray, M., andYakowitz, S.,The Application of Optimal Control Methodology to Nonlinear Programming Problems, Mathematical Programming, Vol. 21, pp. 331–347, 1981.
Yakowitz, S., andRutherford, B.,Computational Aspects of Differential Dynamic Programming, Applied Mathematics and Computation (to appear).
Murray, D. M., andYakowitz, S. J.,Constrained Differential Dynamic Programming, with Application to Multi-Reservoir Control, Water Resource Research, Vol. 15, pp. 1017–1027, 1979.
Yakowitz, S.,Dynamic Programming Applications in Water Resources, Water Resource Research, Vol. 18, pp. 673–698, 1982.
Murray, D. M.,Differential Dynamic Programming for the Efficient Solution of Optimal Control Problems, University of Arizona, PhD Thesis, 1978.
Szidarovszky, F., andYakowitz, S.,Principles and Procedures of Numerical Analysis, Plenum Press, New York, New York, 1978.
Ortega, J., andRheinboldt, W.,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970.
Dahlquist, G., andBjörck, A.,Numerical Methods, Prentice-Hall, Englewood Cliffs, New Jersey, 1973.
Author information
Authors and Affiliations
Additional information
Communicated by D. Q. Mayne
Efforts of the first author were partially supported by the South African Council for Scientific and Industrial Research, and those of the second author by NSF Grants Nos. CME-79-05010 and CEE-81-10778.
Rights and permissions
About this article
Cite this article
Murray, D.M., Yakowitz, S.J. Differential dynamic programming and Newton's method for discrete optimal control problems. J Optim Theory Appl 43, 395–414 (1984). https://doi.org/10.1007/BF00934463
Issue Date:
DOI: https://doi.org/10.1007/BF00934463