Gauss pseudospectral method
The Gauss pseudospectral method (GPM), one of many topics named after Carl Friedrich Gauss, 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.
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 and journal articles that include the theory along with applications
Pseudospectral methods, also known as orthogonal collocation methods, in optimal control arose from spectral methods which were traditionally used to solve fluid dynamics problems. Seminal work in orthogonal collocation methods for optimal control problems date back to 1979 with the work of Reddien and some of the first work using orthogonal collocation methods in engineering can be found in the chemical engineering literature. More recent work in chemical and aerospace engineering have used collocation at the Legendre–Gauss–Radau (LGR) points. 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) the Legendre pseudospectral method (LPM) and the Gauss pseudospectral method (GPM). 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. 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. Recent work shows several variants of the standard LPM, The Jacobi pseudospectral method 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 uses piecewise cubic polynomials rather than Lagrange polynomials, and collocates at a subset of the LGL points.
- APMonitor software for dynamic optimization
- PROPT - MATLAB (Gauss and Chebyshev) Optimal Control software with more than 110 examples.
- GPOPS-II: General Pseudospectral Optimal Control Software (peer-reviewed journal article that implements variable-order Gaussian quadrature collocation methods).
- JModelica.org (Modelica-based open source platform for dynamic optimization)
References and notes
- 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
- 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.
- 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.
- Reddien, G.W., "Collocation at Gauss Points as a Discretization in Optimal Control,"SIAM Journal on Control and Optimization, Vol. 17, No. 2, March 1979.
- 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.
- Hedengren, J.D.; Asgharzadeh Shishavan, R.; Powell, K.M.; Edgar, T.F. (2014). "Nonlinear modeling, estimation and predictive control in APMonitor". Computers & Chemical Engineering. 70 (5): 133–148. doi:10.1016/j.compchemeng.2014.04.013.
- 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.
- 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.
- 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
- 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.
- 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.
- 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
- Williams, P., “Jacobi Pseudospectral Method for Solving Optimal Control Problems”, Journal of Guidance, Vol. 27, No. 2,2003
- 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