Numerical Optimal Trajectory Generation using NLP

control theorynonlinear optimizationnonlinear systemoptimal controloptimization

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?

Best Answer

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.