Differential dynamic programming (DDP) is an optimal control algorithm of the trajectory optimization class. The algorithm was introduced in 1966 by Mayne and subsequently analysed in Jacobson and Mayne's eponymous book. The algorithm uses locally-quadratic models of the dynamics and cost functions, and displays quadratic convergence. It is closely related to Pantoja's step-wise Newton's method.
describe the evolution of the state given the control from time to time . The total cost is the sum of running costs and final cost , incurred when starting from state and applying the control sequence until the horizon is reached:
where , and the for are given by Eq. 1. The solution of the optimal control problem is the minimizing control sequence Trajectory optimization means finding for a particular , rather than for all possible initial states.
DDP proceeds by iteratively performing a backward pass on the nominal trajectory to generate a new control sequence, and then a forward-pass to compute and evaluate a new nominal trajectory. We begin with the backward pass. If
is the argument of the operator in Eq. 2, let be the variation of this quantity around the -th pair:
and expand to second order
The notation used here is a variant of the notation of Morimoto where subscripts denote differentiation in denominator layout. Dropping the index for readability, primes denoting the next time-step , the expansion coefficients are
The last terms in the last three equations denote contraction of a vector with a tensor. Minimizing the quadratic approximation (3) with respect to we have
giving an open-loop term and a feedback gain term . Plugging the result back into (3), we now have a quadratic model of the value at time :
Recursively computing the local quadratic models of and the control modifications , from down to , constitutes the backward pass. As above, the Value is initialized with . Once the backward pass is completed, a forward pass computes a new trajectory:
The backward passes and forward passes are iterated until convergence.
Differential dynamic programming is a second-order algorithm like Newton's method. It therefore takes large steps toward the minimum and often requires regularization and/or line-search to achieve convergence  . Regularization in the DDP context means ensuring that the matrix in Eq. 4 is positive definite. Line-search in DDP amounts to scaling the open-loop control modification by some .
^Morimoto, J.; G. Zeglin; C.G. Atkeson (2003). "Minimax differential dynamic programming: Application to a biped walking robot". Intelligent Robots and Systems, 2003.(IROS 2003). Proceedings. 2003 IEEE/RSJ International Conference on. 2. pp. 1927–1932.
^Liao, L. Z; C. A Shoemaker (1991). "Convergence in unconstrained discrete-time differential dynamic programming". IEEE Transactions on Automatic Control. 36 (6): 692. doi:10.1109/9.86943.