CONVERGENCE IN UNCONSTRAINED DISCRETE-TIME DIFFERENTIAL DYNAMIC-PROGRAMMING

This paper investigates the conditions under which the original differential dynamic programming (DDP) algorithm can be expected to converge and proposes modifications in the algorithm to improve convergence properties. Quadratic convergence of DDP requires that the stagewise Hessian matrices (C(t)) computed in the algorithm are positive definite (Theorem 1); and DDP may not converge at all in other situations. If the transition equations are linear, then a sufficient condition to guarantee positive definite stagewise Hessian matrices and quadratic convergence is for the objective function to be "PD-convex" (Theorem 2). We also show that for nonlinear transition equations, the DDP algorithm will not necessarily generate positive definite stagewise Hessian matrices, even if both the objective function and transition equations are PD-convex (Theorem 3). We propose three procedures for modifying the stagewise Hessian matrices to guarantee convergence for situations in which the stagewise Hessian matrices are not positive definite. One of the procedures (an "active shift") will converge quadratically (Theorem 4). The computational requirements for DDP with and without the shift procedures are presented and the impact of the ratio of state variable dimension to control variable dimension on the relative efficiency of the different shift procedures is discussed. Numerical results for a series of problems, including one with 16 state variables and 200 time steps, are presented. The most robust shift procedure is an adaptive shift that utilizes a constant shift followed by an active shift.