A Posteriori Second-Order Guarantees for Bolza Problems via Collocation

1. Problem Statement

The paper addresses a fundamental gap in direct collocation methods for solving Bolza optimal control problems.

• The Discrepancy: Practical solvers for optimal control (based on direct collocation) output discrete data: primal-dual iterates $(x_N, u_N, \lambda_N)$, reduced Hessians, and KKT Jacobians. However, theoretical optimality guarantees (specifically Second-Order Sufficient Conditions (SSOC)) exist in the continuous domain, requiring knowledge of continuous trajectories and functional second variations.
• The Challenge: There is no direct way to certify that a discrete solution corresponds to a strong local minimizer of the continuous problem using only the solver's output. Existing literature focuses on convergence analysis, but lacks a mechanism to provide a posteriori certificates of continuous optimality from discrete data.
• Goal: To develop a framework that constructs continuous optimality certificates (specifically, a lower bound on the continuous second variation) starting solely from the discrete KKT point and associated solver data.

2. Methodology

The authors propose a constructive a posteriori certification framework that bridges the discrete and continuous domains through three main steps:

A. Reconstruction and Residual Evaluation

From a discrete KKT point $(x_N, u_N, p_N)$, the method reconstructs continuous piecewise polynomial trajectories for the state ($X_N$), control ($u_N$), and costate ($p_N$).

• Residuals: The method evaluates the residuals of the continuous KKT conditions (dynamics, adjoint equations, stationarity, and boundary conditions) using these reconstructed trajectories.
• Metrics: Two residual indicators are defined:
  • $E^{(2)}_N$: An $L_2$-aggregate residual used for theoretical bounds.
  • $E_\infty$: An $L_\infty$-indicator used for diagnostics and visualization.

B. Curvature Transfer (The Core Theoretical Contribution)

The framework derives a computable lower bound for the continuous second variation, denoted as $\alpha_{cont}$. This is achieved by transferring the curvature from the discrete reduced Hessian ($\hat{\alpha}_N$) to the continuous space, corrected by error terms.
The acceptance test is defined as:
$$\hat{\alpha}_N (1 - C_T E^{(2)}_N)^2 > (\Gamma + C_{quad} + C'_T) E^{(2)}_N$$
Where:

• $\hat{\alpha}_N$: The minimum eigenvalue of the discrete reduced Hessian.
• $C_T E^{(2)}_N$: A term accounting for the stability of the projection from continuous to discrete tangent spaces.
• $\Gamma E^{(2)}_N$: A geometric term derived from the Lipschitz bounds of the Lagrangian and the norm of the inverse KKT mapping ($C_{geo}$).
• $C_{quad} E^{(2)}_N$: Error due to numerical quadrature discrepancies.
• $C'_T E^{(2)}_N$: Error due to non-conformity (projection/lifting errors between spaces).

If the left-hand side exceeds the right-hand side, $\alpha_{cont} > 0$, certifying that the continuous second variation is positive definite.

C. Proximity and Trust-Region Guarantees

The paper establishes that if the discrete solution is sufficiently close to an exact KKT point (verified via the residuals and a proximity constant $C_{close, \infty}$), the certified positive curvature implies:

1. Strong Local Optimality: The continuous solution is a strong local minimizer.
2. Quadratic Growth: The cost function exhibits quadratic growth in a neighborhood of the solution.
3. Trust-Region Sizing: A computable radius $r = \alpha_{cont} / (2\Lambda)$ is provided, defining the region where the quadratic growth holds.

3. Key Contributions

1. Bridging the Gap: The first framework to provide rigorous a posteriori certificates for continuous SSOC using only discrete collocation solver outputs.
2. Explicit Acceptance Test: Derivation of a scalar inequality (Eq. 45) that is operationally verifiable. It allows practitioners to accept a solution or trigger adaptive mesh refinement based on a quantitative threshold.
3. Quantitative Bounds: The method provides not just a binary "pass/fail" but quantitative information, including the magnitude of the continuous curvature ($\alpha_{cont}$) and the size of the trust region ($r$).
4. Extension to Path Constraints: The paper outlines how the framework extends to problems with isolated transversal path inequality switches (Section VI), showing that the structure remains valid with modified geometric constants.
5. Constructive Constants: All constants required for the test (geometric, Lipschitz, interpolation) are shown to be conservatively estimable from the discrete data itself, making the method self-contained.

4. Results

The framework was validated on a nonlinear planar quadrotor maneuver problem:

• Setup: A rigid-body quadrotor with 6 states and 2 controls, minimizing a quadratic cost over a 2-second horizon.
• Implementation: Used Hermite–Simpson collocation with varying mesh sizes ($N=10$ to $35$).
• Findings:
  • For $N=35$, the discrete reduced Hessian eigenvalue was $\hat{\alpha}_N \approx 6.29 \times 10^{-4}$.
  • The residual threshold was estimated at $\approx 4.67 \times 10^{-11}$.
  • Since $\hat{\alpha}_N \gg \text{threshold}$, the continuous curvature was certified as strictly positive ($\alpha_{cont} \approx 6.29 \times 10^{-4}$).
  • The proximity condition was satisfied ($C_{close, \infty} E_\infty \ll r$), confirming the existence of a nearby exact KKT point with quadratic growth.
  • The method successfully certified optimality even at relatively sparse discretizations ($N \ge 10$), demonstrating robustness.

5. Significance

• Reliability in Optimal Control: This work moves optimal control verification from heuristic convergence checks to rigorous mathematical certification. It ensures that a "solved" discrete problem actually represents a valid local minimum for the physical (continuous) system.
• Adaptive Mesh Refinement: The residual decomposition naturally guides adaptive mesh refinement. If the test fails, the inequality identifies whether the failure is due to insufficient curvature (requiring better optimization) or excessive residuals (requiring mesh refinement or higher polynomial order).
• Trust-Region Applications: The derived trust-region radius is crucial for algorithms that rely on local quadratic models, providing a mathematically grounded step-size limit.
• Practical Implementation: By relying on standard solver outputs (Hessians, Jacobians) and automatic differentiation, the method is immediately applicable to existing optimal control software without requiring fundamental changes to the solver architecture.

In summary, Zheng and Mei provide a rigorous mathematical tool that transforms the "black box" output of direct collocation solvers into a verified, continuous-time optimality certificate, enhancing the reliability and interpretability of numerical optimal control solutions.