Pseudospectral methods

Pseudospectral methods were originally developed for the solution of partial differential equations [1]. However, over the last 15 years or so, pseudospectral techniques have emerged as important computational methods for solving optimal control problems [2,3].

While finite difference methods approximate the derivatives of a function using local information, psedusospectral methods are, in contrast, global. Using these methods, a function is approximated as a weighted sum of smooth basis functions, which are often chosen to be Legendre or Chebyshev polynomials. One of the main appeals of pseudospectral methods is their exponential (or spectral) rate of convergence, which is faster than any polynomial rate. Moreover, they are virtually free from dissipative or dispersion errors. Another advantage is that with relatively coarse grids it is possible to achieve good accuracy.

Pseudospectral methods directly discretize the original optimal control problem to formulate a nonlinear programming problem, which is then solved numerically using a sparse nonlinear programming solver to find approximate local optimal solutions.

Approximation theory shows that pseudospectral methods are well suited for approximating smooth functions, integrations, and differentiations, all of which are relevant to optimal control problems. For differentiation, the derivatives of the state functions at the discretization nodes are easily computed by multiplying a constant differentiation matrix by a matrix with the state values at the nodes. Thus, the differential equations of the optimal control problem are approximated by a set of algebraic equations. The integration in the cost functional of an optimal control problem is approximated by well known Gauss quadrature rules, consisting of a weighted sum of the function values at the discretization nodes. Moreover, as is the case with other direct methods for optimal control, it is easy to represent state and control dependent constraints.

The current implementation of PSOPT uses either Legendre or Chebyshev polynomials in the interval [−1, 1] for approximating the state and control trajectories. The Legendre pseudospectral method for optimal control problems was originally proposed by Elnagar and coworkers in 1995 [2]. Since then, authors such as Ross, Fahroo and co-workers have analysed, extended and applied the method. For instance, convergence analysis is presented in [4], while an extension of the method to multi-phase problems is given in [5]. An application that has received publicity is the use of the Lagrange pseudospectral method for generating real time trajectories for a NASA spacecraft maneouvre [6]. The Chebyshev pseudospectral method for optimal control problems was originally proposed by Vlassenbroeck and Van Doreen in 1988 [7]. Fahroo and Ross proposed an alternative method for trajectory optimization using Chebyshev polynomials [8].

Approximation theory associated with spectral and pseudospectral methods can be found in the book by Canuto et al [9].

[1] C.G. Canuto, M.Y. Hussaini, A. Quarteroni A., and T.A. Zang. Spectral Methods in Fluid Dynamics. Springer-Verlag, 1988.

[2] G. Elnagar, M. A. Kazemi, and M. Razzaghi. The Pseudospectral Legendre Method for Discretizing Optimal Control Problems. IEEE Transactions on Automatic Control, 40:1793–1796, 1995.

[3] J. Vlassenbroeck and R. Van Doreen. A Chebyshev Technique for Solving Nonlinear Optimal Control Problems. IEEE Transactions on Automatic Control, 33:333–340, 1988.

[4] W. Kang, Q. Gong, I. M. Ross, and F. Fahroo. On the Convergence of Nonlinear Optimal Control Using Pseudospectral Methods for Feedback Linearizable Systems. International Journal of Robust and Nonlinear Control, 17:1251–1277, 2007.

[5] I.M. Ross and F. Fahroo. Pseudospectral Knotting Methods for Solving Nonsmooth Optimal Control Problems. Journal of Guidance Control and Dynamics, 27:397–405, 2004.

[6] W. Kang and N. Bedrossian. Pseudospectral Optimal Control Theory Makes Debut Flight, Saves nasa $1m in Under Three Hours. SIAM News, 40, 2007.

[7] J. Vlassenbroeck and R. Van Doreen. A Chebyshev Technique for Solving Nonlinear Optimal Control Problems. IEEE Transactions on Automatic Control, 33:333–340, 1988.

[8] F. Fahroo and I.M. Ross. Direct Trajectory Optimization by a Chebyshev Pseudospectral Method. Journal of Guidance Control and Dynamics, 25, 2002.

[9] C. Canuto, M.Y. Hussaini, A. Quarteroni, and T.A. Zang. Spectral Methods: Fundamentals in Single Domains. Springer-Verlag, Berlin, 2006.