Generalization of Pantoja's Optimal Control Algorithm
by
Bruce Christianson
Coauthors: Michael Bartholomew-Biggs

Generalization of Pantoja's Optimal Control Algorithm

Bruce Christianson and Michael Bartholomew-Biggs

Extended Abstract.   In 1983 Pantoja described a stagewise construction of the Newton direction for a general class of discrete time optimal control problems. His algorithm incurs amazingly low overheads: for an N-step problem with p control variables and q state variables at each step, the computational cost of calculating the Newton direction using Pantoja's algorithm amounts to order p+q single target function evaluations, independent of N, together with order (p+q)³ multiply-and-add operations per time step, less if there is structural sparsity.

Checkpointing can be used to reduce the total space requirement of Pantoja's algorithm for a typical problem to the order of 4p floating point numbers per timestep. Automatic Differentiation techniques can be used to calculate the Newton direction accurately, without incurring any truncation error and without requiring extensive re-writing of target function code to form derivatives.

Pantoja's Algorithm also determines with certainty whether or not the Hessian of the target function is positive definite at a point of interest. This allows computationally inexpensive post-hoc verification that a second-order minimum has been reached, regardless of what method has been used to obtain it. The algorithm can be modified to verify that the Hessian contains no eigenvalues less than a postulated quantity.

Pantoja's algorithm can also be modified so as to produce an appropriate descent direction in the case where the Hessian fails to be positive definite and global convergence becomes an issue. Coleman and Liao have proposed a specific damping strategy in this context.

The purpose of the present paper is two-fold: first, to consider some alternative globalization strategies; and second, to demonstrate that a combination of the forward and reverse modes of AD can be conveniently deployed within the context of such globalized versions of Pantoja's algorithm to obtain the accurate second derivative values required at an extremely low operations count.

As a vehicle for this discussion, we construct a general algorithm for solving equations of the form (H+\Lambda)t=b for arbitrary vector b and block diagonal matrix \Lambda, where H is the Hessian of the target function for a discrete time optimal control problem. This algorithm reduces to Pantoja's original algorithm in the case where -b is the gradient and \Lambda = 0, and is related to the algorithm studied by Coleman and Liao in case \Lambda = \lambdaI, but has lower operation counts and allows adaptive choice of the values of b and the blocks of \Lambda to be made on the reverse pass of the algorithm in the light of the globalization strategy.

References

[]

M. Bartholomew-Biggs, 1998, Automatic Differentiation of Implicit Functions using Forward Accumulation, Computational Optimization and Applications, 9 69-84.

[]

M. Bartholomew-Biggs, S. Brown, B. Christianson and L.C.W. Dixon, 2000, Automatic Differentiation of Algorithms, Journal of Computational and Applied Mathematics, to appear

[]

Jochen Benary, 1996, Parallelism in the Reverse Mode, in Computational Differentiation, SIAM, Philadelphia

[]

Bruce Christianson, 1992, Automatic Hessians by Reverse Accumulation, IMA Journal of Numerical Analysis 12, 135-150

[]

Bruce Christianson, 1994, Reverse Accumulation and Attractive Fixed Points, Optimization Methods and Software 3(4), 311-326

[]

Bruce Christianson, 1996, Reverse Accumulation and Implicit Functions, Optimization Methods and Software

[]

Bruce Christianson, 1999, Cheap Newton Steps for Optimal Control Problems: Automatic Differentiation and Pantoja's Algorithm, Optimization Methods and Software, 10 729-743.

[]

Thomas Coleman and Aiping Liao, 1995, An Efficient Trust Region Method for Unconstrained Discrete-Time Optimal Control Problems, Computational Optimization and Applications 4, 47-66

[]

Laurence Dixon et al, 1990, Automatic Differentiation of Large Sparse Systems, Journal of Economic Dynamics and Control 14, 299-311

[]

J.C. Dunn and D.P. Bertsekas, 1989, Efficient Dynamic Programming Implementations of Newton's Method for Unconstrained Optimal Control Problems, JOTA 63(1) 23-38

[]

Jean Charles Gilbert, 1992, Automatic Differentiation and Iterative Processes, Optimization Methods and Software 1(1), 13-21

[]

Andreas Griewank, 1992, Achieving Logarithmic Growth of Temporal and Spatial Complexity in Reverse Automatic Differentiation, Optimization Methods and Software 1, 35-54

[]

Andreas Griewank et al, 1993, Derivative Convergence for Iterative Equation Solvers, Optimization Methods and Software 2(4) 321-355

[]

Andreas Griewank, 2000, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, SIAM, Philadelphia.

[]

D.H. Jacobson and D.Q. Mayne, 1970, Differential Dynamic Programming, American Elsevier, New York

[]

D.M. Murray and S.J. Yakowitz, 1984, Differential Dynamic Programming and Newton's Method for Discrete Optimal Control Problems, JOTA 43(3), 395-414

[]

J.F.A.De O. Pantoja, 1983, Algorithms for Constrained Optimization Problems, PhD thesis, Imperial College of Science and Technology, University of London

[]

J.F.A.De O. Pantoja, 1988, Differential Dynamic Programming and Newton's Method, Int J Control 47(5), 1539-1553

[]

J.F.A.De O. Pantoja and D.Q. Mayne, 1991, Sequential Quadratic Programming Algorithm for Discrete Optimal Control Problems with Control Inequality Constraints, Int J Control 53(4), 823-836

[]

Louis B. Rall et al, 1996, An Introduction to Automatic Differentiation, pp 1-18 in Computational Differentiation, SIAM, Philadelphia

Date received: February 14, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cads-78.