Finite-horizon shooting and Runge–Kutta collocation transcription

Inputs. Supply pointwise smooth data on $[0,T]$ from Finite-horizon ODE optimal-control transcription data, an original mesh, a piecewise-constant control parameterization, an explicit tableau from Explicit Runge–Kutta tableaus, stage maps, and failure status or a possibly implicit tableau from Runge–Kutta tableaux and stage collocation equations, one of single-shooting, multiple-shooting, or collocation mode, a finite smooth representation of the control constraints when a solver-ready NLP is requested, finite sets of declared path-constraint times, endpoint constraints, the tableau quadrature rule, an initial decision vector $z_0$ and multiplier vector ${\mu }_0$, a stage residual tolerance ${\tau }_s\ge 0$, a quadrature error tolerance ${\tau }_q\ge 0$, a stage Newton correction cap $M_s\in {\mathbb{N}}_0$, and a maximum number of mesh nodes. For the direct linear-stage branch, optionally supply exact pointwise coefficient maps $A:[0,T]\to {\mathbb{R}}^{n\times n}$ and $B:[0,T]\to {\mathbb{R}}^{n\times m}$ satisfying $f(t,x,u)=A(t)x+B(t)u$ at every queried stage input; only this explicit representation enables that branch. Supply a deterministic derivative evaluator for the actual returned stage maps and resulting finite NLP on an open neighborhood of the queried candidate. On a locally fixed strict stopping branch of the finite stage-iteration procedure, differentiate that finite graph, including when the residual happens to be exactly zero at the queried point. Implicit differentiation as in Implicit differentiation and adjoint formulas under a nonsingular residual Jacobian is permitted only when the selected returned stage map is certified to agree on that neighborhood with the exact local solution branch and its residual Jacobian is nonsingular there; an exact residual at the queried point alone does not establish this agreement. Return derivative-failure when no derivative of the actual returned map is available. Supply a quadrature error evaluator which returns a certified upper bound for the objective quadrature discrepancy or unavailable. Each supplied evaluator returns a value or failure in finite time. An optional trajectory-estimation request supplies the inputs of Finite-budget adaptive Runge–Kutta controller. $X_{j,i}=X_{j,0}+h_j{\sum }_{k<i}{a}_{ik}{F}_{j,k},t_{j,i}=t_j+c_i{h}_j,F_{j,i}=f(t_{j,i},X_{j,i},u_j),{\mathrm{\Phi }}_j(X_{j,0},u_j)=X_{j,0}+h_j{\sum }_i{b}_i{F}_{j,i}\mathrm{.}$

Mesh and constraints. Check that the original mesh satisfies $0=t_0<\cdots <t_N=T$ and that all declared constraint and quadrature times lie in $[0,T]$; if either check fails, return mesh-domain-failure without evaluation. If the original node count exceeds the supplied cap, return mesh-budget-exhausted. Insert every declared path-constraint time not already a node, unless this exceeds the node cap, in which case return mesh-budget-exhausted. Tie each inserted subcell's control to its original containing cell, so the parameterization is unchanged. On the resulting mesh, check all stage times $t_j+c_i{h}_j$ lie in $[0,T]$ before querying $f$ or $L$; an invalid time returns mesh-domain-failure with no evaluation. Each tableau stage and its quadrature contribution use the control $u_j$ of that cell, as in the stage equations below. At a declared path- or endpoint-constraint time that is a mesh node before $T$, use the right-hand original-cell value from the half-open representative in Time meshes and piecewise-constant control parameterization; at $T$, use the last original-cell control value unless a separate endpoint-control variable is supplied. Use the same convention at separately declared non-stage quadrature times. An endpoint constraint is evaluated at its declared endpoint. This is finite sampling and does not assert continuous-path feasibility.

Stage evaluation. On each cell write $h_j=t_{j+1}-t_j$ and $u_j$ for its tied constant control. Before forming any stages, check $X_{j,0}\in {\mathrm{\Omega }}_x$ and $u_j\in {\mathrm{\Omega }}_u$; a failed check returns stage-domain-failure with the cell and no objective candidate. For an explicit tableau, form the stages recursively by the displayed equations. Before each query of $f$ or $L$, check that the time is in $[0,T]$, the state lies in ${\mathrm{\Omega }}_x$, and the control lies in ${\mathrm{\Omega }}_u$; a failed membership check returns stage-domain-failure, and an unavailable function value returns stage-evaluation-failure with the cell and stage index. Apply the same checks to every declared path-constraint evaluation.

For an implicit tableau, do not leave the collocation stages as outer NLP decision variables. Form the coupled slope residual $R_j(K;X_{j,0},u_j{)}_i=K_i-f\text{\hspace{0.17em}⁣}(t_j+c_i{h}_j,X_{j,0}+h_j{\sum }_k{a}_{ik}{K}_k,u_j),i=1,\dots ,s\mathrm{.}$ With the stage times fixed and already checked in $[0,T]$, its open evaluation domain consists of stage vectors for which every induced stage state lies in ${\mathrm{\Omega }}_x$ and the cell control lies in ${\mathrm{\Omega }}_u$; require $R_j$ to be $C^1$ on this domain. A compact tube used for bounds does not replace this open evaluation domain. If exact coefficient maps $A,B$ were supplied and satisfy $f(t,x,u)=A(t)x+B(t)u$ at every queried stage input, form the finite matrix $M_j$ with blocks $(M_j{)}_{ik}={\delta }_{ik}I-h_j{a}_{ik}A(t_{j,i})$ and right-hand side $r_i=A(t_{j,i})X_{j,0}+B(t_{j,i})u_j$. Use exact Gaussian elimination on the stored sample coefficients: scan columns left to right, pivot on the first nonzero entry at or below the current row, swap, eliminate below, and back-substitute. If no pivot is available, return singular-stage-matrix; otherwise form every induced stage state and check every stage time-state-control input belongs to the smooth-data tube. A failed domain check returns stage-domain-failure with the failing cell and stage index, the partial result record, and no objective candidate. If all checks pass, the exact solution of $M_{j}K=r$ is the stage vector and the nonlinear-solve status is exact-linear-stage-solve. In all other smooth cases, form the deterministic initial guess $K_i^{(0)}=f(t_j,X_{j,0},u_j)$ after checking that this query is defined. Before calling Newton, check that the entire seed $K^{(0)}$ belongs to the declared open domain of $R_j$, equivalently that every induced stage state lies in ${\mathrm{\Omega }}_x$ and every required control lies in ${\mathrm{\Omega }}_u$. If this check fails, return stage-domain-failure with the failing cell and stage index, the partial result record, and no objective candidate. Otherwise call Finite-budget Newton for a square vector residual on $R_j$ with that open evaluation domain, tolerance ${\tau }_s$ and cap $M_s$. Record its iterate, residual vector, and exact status for each cell. Only root supplies a stage candidate; it means $\mathrm{\parallel }{R}_j{\mathrm{\parallel }}_2\le {\tau }_s$, not an exact root unless ${\tau }_s=0$. Any other status returns the partial result record with nlp_status=stage-solve-failure, the failing cell, and no objective candidate. On a returned stage vector use $X_{j,i}=X_{j,0}+h_j{\sum }_k{a}_{ik}{K}_k$ and ${\mathrm{\Phi }}_j=X_{j,0}+h_j{\sum }_i{b}_i{K}_i$. A singular stage Jacobian or failed stage query is reported, not interpreted as lack of an exact solution.

Transcription modes. In single shooting, the decision variables are the original-cell controls; set $X_{0,0}=x_0$ and recursively compute $X_{j+1,0}={\mathrm{\Phi }}_j(X_{j,0},u_j)$. In multiple shooting, the decision variables are node states and controls; fix $X_{0,0}=x_0$ and impose the continuity equalities $d_j=X_{j+1,0}-{\mathrm{\Phi }}_j(X_{j,0},u_j)=0$ for $j=0,\dots ,N-1$. In collocation mode, use the same node/control variables, impose the same continuity equalities $d_j=0$, and use solved internal stage states; the collocation equations are solved internally by the implicit-stage procedure above. Explicit stages are likewise internal deterministic evaluations. After every interval map in every mode, check ${\mathrm{\Phi }}_j\in {\mathrm{\Omega }}_x$ before using it as a later start or evaluating a path constraint, terminal cost, or endpoint constraint; otherwise return stage-domain-failure with no objective candidate. Independently of the computed endpoints and defect residuals, check $X_{N,0}\in {\mathrm{\Omega }}_x$ before evaluating $\varphi (X_{N,0})$ or any terminal constraint; in multiple shooting and collocation this node is an independent decision variable even when ${\mathrm{\Phi }}_{N-1}\in {\mathrm{\Omega }}_x$. Before any endpoint-constraint query, also check every actual state and control argument, including a separately supplied endpoint-control variable, belongs to that function's declared domain. Any failed membership check returns stage-domain-failure with no objective candidate. In every mode the finite feasible set includes $u_j\in U_c$ for each original cell. The finite objective is ${\sum }_j{h}_j{\sum }_i{b}_{i}L(t_{j,i},X_{j,i},u_j)+\varphi (X_{N,0})$, and the finite constraints are exactly the fixed initial-state condition, the continuity equalities $d_j=0$ in multiple shooting and collocation, the declared node/time constraints, the represented control constraints, and endpoint constraints. Include every continuity defect in the equality residual $h$ and its corresponding multiplier in $\nu$; in single shooting the initial state and continuity are enforced by recursive elimination. If $U_c$ is available only as a compact set-membership constraint and has no finite smooth representation, return the finite set-constrained model with nlp_status=not-smooth-nlp; the dispatcher must not treat it as an SQP-ready NLP. A QP solver route additionally requires the sampled control constraints to be affine.

Output. Evaluate the supplied initial candidate and return a record containing its ordered decision variables, defect residuals, per-cell implicit-stage residuals, path/endpoint constraint residuals, KKT residuals, and objective value, when available. For equality residual $h$, inequality residual $g\le 0$, and multiplier pair $(\nu ,\lambda )$, report $r_p=(h,[g{]}_{+})$, $r_d=\mathrm{\nabla }{J}_N+D{h}^T\nu +D{g}^T\lambda$, $r_{\lambda }=[-\lambda {]}_{+}$, and $r_c=\lambda \odot g$. Include a model that can reevaluate these quantities at a later solver candidate. Return separate nlp_status, per-cell implicit_stage_status, optional ivp_status, quadrature_status, mesh_status, and budget_status fields. A quadrature bound at most ${\tau }_q$ is bound-met; a larger bound is bound-not-met; an unavailable bound is unavailable. The build-stage budget field is not-run; the solver dispatcher fills its final value. A failed derivative evaluation leaves KKT residuals unavailable with its exact status. An unevaluated optional IVP estimate is not-requested; if requested, report the adaptive controller's exact finite status, not an error certificate.

This direct transcription samples pointwise data; an $L^{\mathrm{\infty }}$ equivalence class without a chosen representative and sampling rule is not stage-evaluable. For a single-shooting reduced objective represented as the finite state-step graph of Finite parameterized state-step graphs and objectives, its exact real-arithmetic reduced gradient is given by The reverse recursion is the exact gradient of a finite state-step objective. Agreement with the continuous ODE adjoint gradient is only conditional on the weighted discrete-gradient representation and the separate state, adjoint, derivative-data, endpoint, and quadrature estimates in Discrete and continuous ODE gradients agree to order p under augmented error bounds. The optional adaptive RK estimate is separate from the fixed NLP and its embedded difference is not a certified global error bound. If all construction, stage, sample-domain and objective checks succeed, return nlp_status=constructed for a solver-ready NLP, or nlp_status=not-smooth-nlp for a finite set-constrained model without a smooth control representation; set mesh_status=valid and retain budget_status=not-run. The algorithm makes no continuous-path feasibility, convergence-rate, global-optimality, or unconditioned discrete-adjoint accuracy claim.