Gauss pseudospectral method

The Gauss Pseudospectral Method (abbreviated "GPM") is a direct transcription method for discretizing a continuous optimal control problem into a nonlinear program (NLP). The Gauss pseudospectral method differs from several other pseudospectral methods in that the dynamics are not collocated at either endpoint of the time interval. This collocation, in conjunction with the proper approximation to the costate, leads to a set of KKT conditions that are identical to the discretized form of the first-order optimality conditions. This equivalence between the KKT conditions and the discretized first-order optimality conditions leads to an accurate costate estimate using the KKT multipliers of the NLP.

Description

The method is based on the theory of orthogonal collocation where the collocation points (i.e., the points at which the optimal control problem is discretized) are the Legendre-Gauss (LG) points. The approach used in the GPM is to use a Lagrange polynomial approximation for the state that includes coefficients for the initial state plus the values of the state at the N LG points. In a somewhat opposite manner, the approximation for the costate (adjoint) is performed using a basis of Lagrange polynomials that includes the final value of the costate plus the costate at the N LG points. These two approximations together lead to the ability to map the KKT multipliers of the nonlinear program (NLP) to the costates of the optimal control problem at the N LG points PLUS the boundary points. The costate mapping theorem that arises from the GPM has been described in several references including two MIT PhD theses [Benson, D.A., "A Gauss Pseudospectral Transcription for Optimal Control", Ph.D. Thesis, Dept. of Aeronautics and Astronautics, MIT, November 2004,] [Huntington, G.T., "Advancement and Analysis of a Gauss Pseudospectral Transcription for Optimal Control", Ph.D. Thesis, Dept. of Aeronautics and Astronautics, MIT, May 2007] and journal articles that include the theory along with applications [Benson, D.A., Huntington, G.T., Thorvaldsen, T.P., and Rao, A.V., "Direct Trajectory Optimization and Costate Estimation via an Orthogonal Collocation Method", "Journal of Guidance, Control, and Dynamics". Vol. 29, No. 6, November-December 2006, pp. 1435-1440.,] [Huntington, G.T., Benson, D.A., and Rao, A.V., "Optimal Configuration of Tetrahedral Spacecraft Formations", "The Journal of The Astronautical Sciences". Vol. 55, No. 2, March-April 2007, pp. 141-169.] [Huntington, G.T. and Rao, A.V., "Optimal Reconfiguration of Spacecraft Formations Using the Gauss Pseudospectral Method", "Journal of Guidance, Control, and Dynamics". Vol. 31, No. 3, March-April 2008, pp. 689-698.]

Background

Pseudospectral methods, also known as "orthogonal collocation methods", in optimal control arose from spectral methods which were traditionally used to solve fluid dynamics problems. [Canuto, C., Hussaini, M.Y., Quarteroni, A., Zang, T.A., "Spectral Methods in Fluid Dynamics", Springer-Verlag, New York, 1988. ] [Fornberg, B., "A Practical Guide to Pseudospectral Methods", Cambridge University Press,1998.] Seminal work in orthogonal collocation methods for optimal control problems date back to 1979 with the work of Reddien [Reddien, G.W., "Collocation at Gauss Points as a Discretization in Optimal Control,"SIAM Journal of Control and Optimization", Vol. 17, No. 2, March 1979.] and some of the first work using orthogonal collocation methods in engineering can be found in the chemical engineering literature. [Cuthrell, J.E. and Biegler, L.T., “Simultaneous Optimization and Solution Methods for Batch Reactor Control Profiles,” "Computers and Chemical Engineering", Vol. 13, Nos. 1/2, 1989, pp.49–62.] More recent work in chemical and aerospace engineering have used collocation at the Legendre-Gauss-Radau (LGR) points. [Fahroo, F. and Ross, I., “Pseudospectral Methods for Infinite Horizon Nonlinear Optimal Control Problems,” 2005 AIAA Guidance, Navigation, and Control Conference, AIAA Paper 2005-6076, San Francisco, CA, August 15–18, 2005.] [Kameswaran, S. and Biegler, L.T., “Convergence Rates for Dynamic Optimization Using Radau Collocation,” "SIAM Conference on Optimization", Stockholm, Sweden, 2005.] [Kameswaran, S. and Biegler, L.T., “Convergence Rates for Direct Transcription of Optimal Control Problems at Radau Points,” "Proceedings of the 2006 American Control Conference", Minneapolis, Minnesota, June 2006.] Within the aerospace engineering community, several well-known pseudospectral methods have been developed for solving optimal control problems such as the Chebyshev pseudospectral method (CPM) [Vlassenbroeck, J. and Van Doreen, R., “A Chebyshev Technique for Solving Nonlinear Optimal Control Problems,” "IEEE Transactions on Automatic Control", Vol. 33, No. 4, 1988, pp. 333–340.] [Vlassenbroeck, J., “A Chebyshev Polynomial Method for Optimal Control with State Constraints,” "Automatica", Vol. 24, 1988, pp. 499–506.] the Legendre pseudospectral method (LPM) [Elnagar, J., Kazemi, M. A. and Razzaghi, M., The Pseudospectral Legendre Method for Discretizing Optimal Control Problems, "IEEE Transactions on Automatic Control", Vol. 40, No. 10, 1995, pp. 1793-1796] and the Gauss pseudospectral method (GPM). [Benson, D.A., Huntington, G.T., Thorvaldsen, T.P., and Rao, A.V., “Direct Trajectory Optimization and Costate Estimation via an Orthogonal Collocation Method,” "Journal of Guidance, Control, and Dynamics", Vol. 29, No. 6, November–December 2006, pp. 1435–1440.] The CPM uses Chebyshev polynomials to approximate the state and control, and performs orthogonal collocation at the Chebyshev-Gauss-Lobatto (CGL) points. An enhancement to the Chebyshev pseudospectral method that uses a Clenshaw-Curtis quadrature was developed. [Fahroo, F. and Ross, I.M., “Direct Trajectory Optimization by a Chebyshev Pseudospectral Method,” "Journal of Guidance, Control, and Dynamics", Vol. 25, No. 1, January-February 2002, pp. 160–166.] The LPM uses Lagrange polynomials for the approximations, and Legendre-Gauss-Lobatto (LGL) points for the orthogonal collocation. A costate estimation procedure for the Legendre pseudospectral method was also developed. [Ross, I. M., and Fahroo, F., ``Legendre Pseudospectral Approximations of Optimal Control Problems," "Lecture Notes in Control and Information Sciences", Vol.295, Springer-Verlag, New York, 2003] Recent work shows several variants of the standard LPM, The Jacobi pseudospectral method [Williams, P., “Jacobi Pseudospectral Method for Solving Optimal Control Problems”, "Journal of Guidance", Vol. 27, No. 2,2003] is a more general pseudospectral approach that uses Jacobi polynomials to find the collocation points, of which Legendre polynomials are a subset. Another variant, called the Hermite-LGL method [Williams, P., “Hermite-Legendre-Gauss-Lobatto Direct Transcription Methods In Trajectory Optimization,” "Advances in the Astronautical Sciences". Vol. 120, Part I, pp. 465-484. 2005] uses piecewise cubic polynomials rather than Lagrange polynomials, and collocates at a subset of the LGL points.

ee also

* [http://gpops.sourceforge.net/ Gauss Pseudospectral Optimal Control Software (GPOPS)] for a software implementation of the Gauss pseudospectral method.

References and notes