Authors: Gabriel Bousquet and Jean-Jacques Slotine
Abstract
Convergence of Extremum Seeking (ES) algorithms has been established in the limit of small gains. Using averaging theory and contraction analysis, we propose a framework for computing explicit bounds on the departure of the ES scheme from its ideal dominant-order average dynamics. The bounds remain valid for possibly large gains. They allow us to establish stability and estimate convergence rates, and they open the way to selecting "optimal" finite gains for the ES scheme.
Introduction: The Speed-Stability Trade-off
Extremum Seeking (ES) is a robust "black-box" optimization technique used in control systems where a mathematical model of the objective function is unavailable. By applying a periodic dither signal (perturbation) to the system and measuring the resulting output, ES estimates the local gradient and steers the system toward an optimum.
Historically, the mathematical guarantees for ES stability have relied on the "small gain" assumption. This theoretical constraint implies that the system is only guaranteed to converge if the optimization steps are infinitesimally small, leading to extremely slow convergence in practice. For real-world applications—ranging from tuning particle accelerators to optimizing robotic locomotion—glacial speed is unacceptable. However, increasing gains to improve speed often leads to instability or excessive oscillations. This paper bridges this gap by providing a rigorous framework to guarantee stability for finite, larger gains.
Theoretical Framework: Higher-Order Averaging and Contraction
The authors move beyond traditional first-order analysis by integrating three sophisticated mathematical tools:
- Higher-Order Averaging Theory: While standard analysis looks only at the first-order "average" behavior, this work utilizes an algorithmic approach to calculate $n$-th order corrections. This reveals the "hidden" errors and coupling terms that emerge when gains are no longer infinitesimal.
- Contraction Analysis: Using contraction theory, the authors prove that the trajectories of the nonlinear ES system will converge toward an "ideal" gradient descent path. This ensures that even if the system is messy and oscillatory, it remains bounded and predictable.
- Singular Perturbation Theory: This handles the separation of timescales between the fast dither frequency and the slower drift toward the optimum, allowing for a clear decomposition of the system's dynamics.
By combining these, the authors produce a Fundamental Decomposition of ES dynamics, separating the behavior into an ideal descent term and explicit error terms (oscillatory, higher-order, and internal dynamic errors).
Meta-Optimization: Selecting Optimal Gains
A key contribution of this research is the transition from "guessing" gains to a systematic "meta-optimization" framework. Instead of trial and error, engineers can solve a secondary optimization problem: maximizing the gain (and thus the speed of convergence) subject to the constraint that the calculated error bounds stay within a specific budget.
As shown in the Performance and Speed map, the framework allows practitioners to visualize the relationship between parameters (such as gain $p$ and dither amplitude $a$). The contours represent explicit bounds on the departure of the real system from the ideal one. If the practitioner can estimate the bounds of the objective function's derivatives, they can calculate exactly how much precision is sacrificed for a given increase in speed.
Key Insights and Numerical Validation
- The 2D Dither Trap: The paper identifies a common pitfall in multi-dimensional ES. Using a simple sine/cosine dither pair for different dimensions can introduce a "precessing term" that causes the system to orbit the optimum rather than converge to it. This highlights the necessity of careful dither selection.
- Quantifiable Stability: The paper provides explicit bounds ($K_1, K_2, \dots$) for the system's departure from the ideal path. This moves ES analysis from qualitative "limit of zero" statements to quantitative engineering bounds.
- Practical Performance: In numerical simulations of a 1D map optimization, the meta-optimization framework successfully selected gains that allowed the system to reach its error bound in approximately 100 oscillations, demonstrating high-performance tuning that remains theoretically grounded.
Limitations and Future Directions
While the framework is powerful, it requires some knowledge of the objective function's curvature (derivatives) to set the bounds accurately. If the landscape is entirely unknown and highly irregular, the resulting bounds may be overly conservative. Future work aims to extend these results to Stochastic Extremum Seeking, where noise is a primary concern, and to apply the theory to complex non-holonomic robotic source-seeking tasks.
Conclusion
By providing a rigorous way to calculate the stability of finite gains, Bousquet and Slotine have turned Extremum Seeking from a slow, conservative heuristic into a high-performance optimization tool. The ability to explicitly map the trade-off between speed and error allows for the design of faster, more reliable autonomous systems.
Summary updated