Numerical Optimal Trajectory Generation using NLP

Question

I have been reading about direct collocation for trajectory generation and I am a bit confused - the examples I have seen result in having to maintain a separate nonlinear equality constraint for every sample point.

Is this normal?

How do numerical solvers maintain this many equality constraints in nonlinear programs?(I'm talking in the 100s). I have taken a course on nonlinear optimization using things like the projected gradient method but my understanding is that it is only viable for smaller scale problems. How is this normally handled?

Answer 1

SQP and interior point methods iterative approximate the optimization problem with an optimization problem with a quadratic objective and linear equality constraints: $$\min \left\{ \frac{1}{2} x^TQx + c^Tx : Ax = b \right\}.$$ What is nice about this approximation is that the KKT conditions (necessary and sufficient if $Q$ is positive semidefinite) are just a linear system: $$ \begin{pmatrix}Q & A^T \\ A & O\end{pmatrix}\begin{pmatrix}x \\ \lambda\end{pmatrix}=\begin{pmatrix}-c \\ b\end{pmatrix}. $$ Therefore, the optimal solution to the approximation can be obtained by solving a system of linear equations. Just a few hundred variables is not a big deal. Especially when $A$ is sparse, you can solve such problems with millions of variables.

Answer 2

As my background is mainly focused on MPC but not mathematical solvers, I only answer the first part of your question.

An example of NLP with many constraints is a Model Predictive Control (MPC) problem with a stability condition of

System Energy $|_{t=N_p T_s}$ = 0

This enforces every state of the system to be placed at a certain value. So, such equality conditions are normal.