Tight Bounds on Polynomials and Its Application to Dynamic Optimization Problems

1. Problem Statement

The paper addresses a fundamental limitation in Dynamic Optimization Problems (DOPs), specifically within the context of pseudo-spectral methods used for optimal control.

• The Core Issue: Standard pseudo-spectral methods approximate state and input trajectories using polynomials (often via Lagrange interpolation). While these methods offer high convergence rates, they typically enforce inequality constraints (e.g., $p_\ell \leq p(t) \leq p_u$) only at discrete sample points (collocation nodes).
• The Consequence: There is no guarantee that the polynomial satisfies constraints between these sample points. This can lead to "constraint violations" in the continuous-time solution, rendering the control strategy infeasible or unsafe.
• Existing Solutions & Limitations:
  • Sum-of-Squares (SOS): Guarantees global non-negativity but requires semi-definite programming, which is computationally expensive and incompatible with many nonlinear optimization solvers.
  • Bernstein Polynomials: The coefficients of a polynomial in the Bernstein basis lie within the convex hull of the polynomial's range. Constraining these coefficients guarantees the polynomial stays within bounds. However, these bounds are often conservative (loose), meaning the feasible region is artificially shrunk, leading to suboptimal solutions (higher cost).
  • Fixed Sub-intervals: Previous attempts to use Bernstein constraints with fixed sub-intervals reduced but did not eliminate this conservatism.

2. Methodology

The authors propose a pseudo-spectral method using flexible sub-intervals combined with Bernstein polynomial constraints to achieve tight bounds.

A. Theoretical Foundation: Tight Bounds

• Bernstein Basis: The method represents polynomials in the Bernstein basis. A key property is that the polynomial's value on $[0, 1]$ is bounded by the minimum and maximum of its Bernstein coefficients.
• The Conservatism Problem: For a single interval, the convex hull of Bernstein coefficients is often much larger than the actual range of the polynomial, especially for higher-degree polynomials or specific shapes (e.g., monotonic functions that are not tightly bounded by their coefficients).
• Key Theoretical Insight (Theorem 1): The authors prove that for any monotonic polynomial on a finite interval, there exists a finite partition of sub-intervals such that the polynomial is tightly bounded by its Bernstein coefficients on every sub-interval.
  • Essentially, by breaking the domain into sufficiently small, flexible pieces, the "looseness" of the Bernstein bounds vanishes, and the bounds become exact (tight).

B. Discretization Strategy

• Flexible Sub-intervals: Instead of dividing the time horizon $[t_0, t_f]$ into fixed, equispaced intervals, the method treats the internal node locations ($\tilde{t}_i$) as optimization variables.
• Flexibility Parameters: The size of each sub-interval is constrained by flexibility parameters $\phi_i \in [0, 1)$, allowing the optimizer to stretch or shrink intervals to best fit the dynamics and constraints.
• Implementation:
  1. Interpolation: States and inputs are interpolated using Legendre-Gauss-Radau (LGR) collocation points within each flexible sub-interval.
  2. Constraint Enforcement: The inequality constraints are enforced on the Bernstein coefficients of the interpolating polynomials.
  3. Optimization: The resulting problem is a Nonlinear Programming (NLP) problem where the decision variables include the polynomial coefficients, the sub-interval boundaries, and the slack variables.

3. Key Contributions

1. Theoretical Proof: The paper provides a rigorous proof that a finite number of sub-intervals is sufficient to tightly bound piecewise-monotonic polynomials using Bernstein coefficients. This challenges the assumption that Bernstein constraints are inherently too conservative for high-precision control.
2. Counter-Example: The authors demonstrate that even monotonic polynomials are not necessarily tightly bounded by their Bernstein coefficients on a single interval, necessitating the use of sub-intervals.
3. Novel Algorithm: They propose a flexible discretization pseudo-spectral method that combines:
   • High-order spectral convergence (via LGR collocation).
   • Rigorous constraint satisfaction (via Bernstein coefficient constraints).
   • Optimality preservation (via flexible sub-intervals that eliminate conservatism).
4. Performance: The method achieves rigorous constraint satisfaction without the significant cost penalty usually associated with conservative bounding techniques.

4. Results

The method was validated on two benchmark DOPs using the Ipopt solver and JuMP modeling language:

A. Bryson-Denham Problem

• Setup: A double-integrator system with a state constraint $r(t) \leq 0.2$. An analytical solution exists for comparison.
• Findings:
  • Standard Method (Fixed nodes, point constraints): Violated the constraint between nodes.
  • Bernstein on Fixed Nodes: Satisfied constraints but was highly conservative, resulting in a significantly higher cost (suboptimal).
  • Proposed Method (Flexible nodes + Bernstein): Satisfied constraints rigorously and achieved a cost nearly identical to the analytical solution.
  • Cost Reduction: Up to a tenfold reduction in relative cost compared to the conservative fixed-node Bernstein approach.

B. Constrained Cart-Pole Swing-Up

• Setup: A cart-pole system where the cart position is constrained ($0 \leq q_1 \leq 1$).
• Findings:
  • Similar to the first example, the flexible sub-interval approach eliminated the conservatism of the Bernstein bounds.
  • The method allowed the system to operate much closer to the constraint boundaries (where the optimal cost lies) without violating them.
  • Flexibility Impact: Increasing the flexibility parameter ($\phi$) significantly reduced the cost. However, excessive flexibility could lead to large sub-intervals, slightly increasing dynamic constraint violations (a trade-off between cost and dynamic accuracy).

5. Significance and Conclusion

• Bridging the Gap: This work successfully bridges the gap between rigorous constraint satisfaction (often associated with slow convergence or high computational cost) and spectral convergence rates (associated with high efficiency but loose constraints).
• Practical Impact: In safety-critical control applications (e.g., aerospace, robotics), guaranteeing that constraints are never violated is paramount. This method provides a computationally efficient way to ensure safety without sacrificing optimality.
• Future Directions: The authors note that flexible discretizations introduce non-linearities and potential non-uniqueness in solutions. Future work may focus on convexification techniques and regularization to handle these numerical challenges.

In summary, the paper demonstrates that by allowing the time discretization to be flexible, one can leverage the safety guarantees of Bernstein polynomials without incurring the penalty of conservative approximations, leading to optimal control solutions that are both safe and highly efficient.