Introduction to Optimal Control

Optimal control theory is a branch of mathematics that deals with finding a control law for a dynamic system over a period of time such that an objective function is optimized. These problems appear in aerospace trajectory design, chemical process control, robotics, economics, and many other fields. The general formulation involves a set of ordinary differential equations (ODEs) or differential-algebraic equations (DAEs) describing system dynamics, a performance index (cost functional) to be minimized or maximized, and possibly path constraints and boundary conditions.

Solving optimal control problems analytically is usually impossible except for very simple cases. Hence numerical methods are essential. Among the most powerful and widely used numerical techniques are collocation methods. This article explains what collocation methods are, why they are beneficial, and how they compare to other approaches.

What Are Collocation Methods?

Collocation methods are a class of direct transcription methods for solving optimal control problems. The core idea is to parameterize the state and control variables using piecewise polynomial functions (typically Lagrange or Hermite polynomials) and enforce the system dynamics at specific points called collocation points within each mesh interval. By doing so, the infinite-dimensional optimal control problem is transformed into a finite-dimensional nonlinear programming problem (NLP). The NLP can then be solved using standard optimization algorithms such as sequential quadratic programming (SQP) or interior-point methods.

Mathematically, consider an optimal control problem with time horizon [t0, tf]. The state vector x(t) and control vector u(t) are approximated as:

  • x(t) ≈ Σ Σ a_i * φ_i(t) where φ are basis functions (e.g., Lagrange polynomials).
  • u(t) ≈ Σ Σ b_j * ψ_j(t) similarly.

The system dynamics dx/dt = f(x(t), u(t), t) are imposed at the collocation points by requiring the derivative of the polynomial approximation to match the function evaluation at those points. This yields a set of algebraic constraints. The cost function is also discretized, often using a quadrature rule based on the collocation points. The resulting NLP has variables representing the coefficients of the polynomials (or the values at collocation points) and possibly additional parameters.

Types of Collocation Methods

Collocation methods can be categorized along several dimensions:

  • Local vs. Global Collocation: Local methods divide the time domain into multiple mesh intervals and use low-degree polynomials within each interval (e.g., trapezoidal, Hermite-Simpson). Global methods use a single high-degree polynomial over the entire domain, often based on Gaussian quadrature points (e.g., Legendre or Chebyshev points).
  • Orthogonal Collocation: A specific type of global collocation that uses orthogonal polynomials and quadrature rules. Examples include the Legendre-Gauss-Radau (LGR) collocation, which has excellent convergence properties and is used in the GPOPS-II software package.
  • Direct vs. Indirect Collocation: Direct collocation directly discretizes the optimal control problem. Indirect methods first apply the calculus of variations to derive necessary conditions (boundary value problem) and then discretize those conditions; collocation can also be applied there, but direct collocation is more common in practice due to robustness regarding initial guesses.

Local Collocation Example: Hermite-Simpson

In a typical local collocation method like Hermite-Simpson, the time horizon is divided into N intervals. Within each interval, the state is approximated by a cubic Hermite polynomial, and the control by a linear or constant function. The dynamics are enforced at the midpoint and endpoints of each interval. This method is second-order accurate and straightforward to implement.

Global Orthogonal Collocation

Global orthogonal collocation methods, such as the Legendre-Gauss-Radau scheme, use a single polynomial of degree K over the entire time domain, with collocation points chosen as roots of orthogonal polynomials. These methods can achieve exponential convergence (spectral accuracy) for smooth problems, meaning that the error decreases faster than any finite polynomial order. They are particularly effective for problems with smooth dynamics and constraints.

Advantages of Collocation Methods

Collocation methods offer several significant benefits over other numerical approaches like single shooting, multiple shooting, or dynamic programming.

High Accuracy with Spectral Convergence

For sufficiently smooth problems, global orthogonal collocation methods achieve exponential convergence: doubling the number of collocation points can dramatically reduce the error. This is a major advantage over finite-difference or Euler methods that converge only at a polynomial rate. Even local collocation methods like Hermite-Simpson provide fourth-order accuracy when using cubic polynomials, which is better than standard Runge-Kutta or Euler methods for the same number of discretization points.

Efficient NLP Formulation

Collocation methods produce a sparse NLP because the constraints only couple variables within the same interval (for local methods) or have a structured pattern (for global methods). This sparsity can be exploited by modern optimization solvers like IPOPT or SNOPT, allowing large-scale problems to be solved efficiently. Moreover, the number of variables in a collocation formulation grows linearly with the number of mesh points, making it linearly scalable to longer time horizons and finer grids.

Handling Path Constraints and Complex Dynamics

Unlike indirect methods that require analytical derivation of costate equations, direct collocation can easily handle inequality constraints on state and control variables. Path constraints are simply included as algebraic constraints in the NLP. This flexibility is crucial in aerospace applications where thrust bounds, heat flux limits, or structural load constraints must be respected.

Robustness and Convergence

Collocation methods are more robust to poor initial guesses than single shooting methods. In single shooting, a small change in initial conditions can lead to large deviations in the final state, making the optimization difficult. Collocation methods explicitly enforce the dynamics over the whole trajectory, so the NLP solver is less likely to get stuck in infeasible regions. This robustness is especially valuable in non-linear problems with sensitive dynamics.

Parallelizability

Local collocation methods are naturally parallelizable because each mesh interval can be processed independently. This allows leveraging high-performance computing clusters to solve very large problems quickly. Even global methods have some parallel structure when using domain decomposition or multi-mesh approaches.

Straightforward Integration of Adjoints and Sensitivities

In many applications, the user also needs the sensitivity of the optimal solution to parameters or initial conditions. Collocation methods produce a set of algebraic equations; the derivative of the solution with respect to parameters can be computed efficiently using the implicit function theorem. This is simpler than deriving costate equations for indirect methods.

Comparison with Other Methods

Single Shooting

Single shooting methods parameterize the control only and integrate the dynamics forward in time, adjusting initial conditions to satisfy terminal constraints. They are simple but often suffer from extreme sensitivity to initial guesses and cannot handle state constraints easily.

Multiple Shooting

Multiple shooting divides the time horizon into intervals and uses initial value problems within each interval, matching states at interval boundaries. This improves robustness compared to single shooting but still requires integration of the dynamics, which can be expensive for stiff systems. Collocation methods, being fully implicit, handle stiff dynamics naturally without the need for stiff integrators.

Dynamic Programming (DP)

DP, including the Hamilton-Jacobi-Bellman approach, provides a global optimal solution but suffers from the "curse of dimensionality": the computational cost grows exponentially with the number of state variables. Collocation methods can scale to high-dimensional problems, especially when the problem has sparse structure or when using direct transcription techniques that avoid gridding the state space.

Applications of Collocation Methods

Aerospace Engineering

Perhaps the most prominent application is trajectory optimization for launch vehicles, spacecraft, and aircraft. For example, NASA's OTIS (Optimal Trajectories by Implicit Simulation) and the open-source PyGMO/pygmo use collocation techniques to compute fuel-optimal ascent trajectories, reentry paths, and orbit transfers. The ability to handle atmospheric drag, gravity models, and thrust constraints makes collocation methods indispensable.

Robotics and Autonomous Systems

In robotics, motion planning and control often require solving optimal control problems online. Collocation methods, especially local ones with real-time capabilities, are used to generate smooth, obstacle-avoiding trajectories for manipulators and mobile robots. The flexibility to add constraints like joint limits and torque bounds is a key advantage.

Chemical Process Control

Batch reactors, distillation columns, and other processes benefit from optimal control to maximize yield or minimize energy consumption. Collocation methods handle the stiff, nonlinear differential equations common in chemical kinetics and can incorporate path constraints on temperature or pressure.

Economics and Finance

Optimal control of economic growth models, resource extraction, and portfolio optimization often involve continuous-time systems. Collocation methods can solve these problems efficiently, especially when the utility functions are non-quadratic and constraints on consumption or investment are present.

Practical Considerations

Mesh Refinement

The accuracy of collocation methods depends on the placement and number of collocation points. For local methods, mesh refinement strategies (such as those implemented in MATLAB’s Direct Collocation or GPOPS-II) allow automatic distribution of mesh points to resolve regions with rapid changes (e.g., sharp turns in a spacecraft’s trajectory). Error estimates derived from the collocation conditions can guide adaptive refinement.

Initial Guess Generation

Although collocation methods are more robust than shooting methods, a good initial guess still helps convergence. Common strategies include using a coarser mesh first, linear or quadratic interpolation of a guessed trajectory, or solving a simpler version of the problem.

Software Tools

Several mature software packages implement collocation methods. Notable examples include GPOPS-II (global LGR collocation), PSOPT (pseudospectral collocation), IPOPT (interior-point solver often used with collocation), and the MATLAB Optimization Toolbox’s direct collocation functions. In Python, libraries like CasADi provide a symbolic framework for implementing custom collocation schemes.

Conclusion

Collocation methods are a powerful and versatile set of numerical techniques for solving optimal control problems. Their key benefits include high accuracy through spectral convergence (for global methods), efficient sparse NLP formulations, robust handling of constraints and stiff dynamics, and the ability to scale to large problems. Whether you are optimizing a rocket trajectory, planning a robot’s motion, or controlling a chemical plant, collocation methods offer a practical and reliable solution. As computational power and algorithm development continue to advance, these methods will only become more central to the design of high-performance control systems across scientific and engineering disciplines.

For engineers and researchers looking to implement collocation methods, starting with an established software package like GPOPS-II or CasADi is recommended, along with a thorough understanding of the underlying mathematics to select the appropriate mesh strategy and solver settings.