Adaptive Hamiltonian Variational Integrators and Applications to Symplectic Accelerated Optimization

Valentin Duruisseaux, Jeremy Schmitt, Melvin Leok

TL;DR

This paper introduces a novel framework for constructing adaptive symplectic integrators by leveraging Hamiltonian variational integrators and the Poincaré transformation. This approach addresses the challenge of maintaining energy conservation in numerical simulations when using variable time-steps, a common requirement for efficiency in complex dynamical systems and optimization problems.

What Problem Does This Paper Address?

Symplectic integrators are renowned for their excellent long-term energy preservation in conservative Hamiltonian systems. However, this property degrades significantly when variable time-steps are introduced, which are often necessary to capture phenomena occurring at vastly different time scales or to improve computational efficiency. Traditional methods for combining adaptive time-stepping with symplectic integrators often rely on transformations of the original Hamiltonian, which can lead to degeneracy. This degeneracy prevents the use of standard Lagrangian variational integrators. The paper aims to provide a unified framework for constructing adaptive symplectic integrators that overcome this degeneracy issue.

Methods

The core contribution is the development of a framework for adaptive Hamiltonian variational integrators (HTVIs). Instead of discretizing Hamilton's equations directly, variational integrators discretize Hamilton's principle. The paper extends this to Hamiltonian systems using Type II and Type III generating functions, which are more robust to the degeneracy issues arising from the Poincaré transformation.

Key methodological aspects include:

  • Poincaré Transformation: This technique is used to transform the original Hamiltonian system into a new one that allows for variable time-stepping. The transformation introduces a monitor function $g(q,p)$ that dictates the change of time.
  • Hamiltonian Variational Integrators (Type II and Type III): These integrators are derived from discrete Hamiltonians (generating functions) and are shown to be well-suited for handling the degenerate Hamiltonians that often result from the Poincaré transformation.
  • Hamiltonian Taylor Variational Integrators (HTVIs): The paper specifically utilizes HTVIs, which approximate the flow map using Taylor expansions. This allows for the construction of higher-order integrators.
  • Adaptive Monitor Function: A crucial element is the design of a monitor function $g(q,p)$ that dynamically adjusts the time-step based on properties of the system (e.g., truncation error, energy error, arclength). This function is key to achieving adaptive time-stepping while preserving symplecticity.
  • Application to Accelerated Optimization: The framework is applied to design efficient symplectic integrators for accelerated optimization algorithms, leveraging the connection between Hamiltonian dynamics and optimization.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical testing on well-established problems.

Key Insights and Ideas

  • Hamiltonian Variational Integrators as a Unified Framework: The paper demonstrates that HTVIs provide a systematic and general approach to constructing adaptive symplectic integrators, overcoming limitations of previous methods.
  • Poincaré Transformation and Degeneracy: The Poincaré transformation is a powerful tool for adaptive time-stepping, but it often leads to degenerate Hamiltonians. Type II and Type III Hamiltonian variational integrators are shown to be the natural choice to handle this degeneracy.
  • Monitor Function Design is Crucial: The performance of adaptive integrators heavily relies on the choice of the monitor function. The paper explores several choices, highlighting that efficiency and applicability vary.
  • Symplecticity and Adaptivity for Optimization: The integration of adaptive symplectic methods with accelerated optimization algorithms shows significant gains in efficiency, suggesting a promising direction for high-performance optimization.
  • Adaptive vs. Direct Approaches: The adaptive approach, by intelligently adjusting time-steps, consistently outperforms direct methods that use a fixed fictive time-step, especially in terms of the number of iterations required for convergence.

Key Results

  • Kepler's 2-Body Problem: Numerical tests on Kepler's planar 2-body problem with high eccentricity demonstrated that the adaptive HTVI method significantly outperforms fixed time-step symplectic Euler-B in terms of computational time and number of steps. The choice of monitor function had a notable impact on performance.
  • Accelerated Optimization: The developed adaptive HTVI and non-variational integrators were applied to a quartic objective function. The adaptive HTVI method showed competitive performance against popular optimization algorithms like Nesterov's Accelerated Gradient, especially in terms of the number of iterations.
  • Efficiency Gains: The adaptive approach, by intelligently managing time-steps, achieved convergence with substantially fewer iterations and computational time compared to direct methods, particularly for problems with varying dynamics or high curvature.

Limitations and Future Work

  • Monitor Function Selection: While several monitor functions were tested, finding a universally efficient and general monitor function remains an open challenge. More research is needed in this area.
  • Non-Autonomous and Degenerate Hamiltonians: The theoretical analysis and proofs often rely on assumptions of non-degeneracy and autonomy. While the framework is shown to handle these cases, further theoretical investigation into the solvability of discrete Hamiltonian equations in more complex scenarios is suggested.
  • Higher-Order Methods: The paper notes that for higher-order methods, monitor functions based on truncation errors can become implicitly defined, posing implementation challenges.
  • Stochastic Systems: The authors suggest extending the adaptive Hamiltonian variational integrator framework to stochastic systems, building upon existing work in stochastic variational integrators.
  • General Spaces: Investigating the extension of these adaptive frameworks to more general spaces like Lie groups and Riemannian manifolds is proposed as a future research direction.
  • Nonconvex Optimization: The potential of the adaptive framework for nonconvex optimization problems is highlighted, suggesting further exploration in this domain.

Summary updated

Abstract

It is well known that symplectic integrators lose their near energy\npreservation properties when variable step sizes are used. The most common\napproach to combine adaptive step sizes and symplectic integrators involves the\nPoincar\\'e transformation of the original Hamiltonian. In this article, we\nprovide a framework for the construction of variational integrators using the\nPoincar\\'e transformation. Since the transformed Hamiltonian is typically\ndegenerate, the use of Hamiltonian variational integrators based on Type II or\nType III generating functions is required instead of the more traditional\nLagrangian variational integrators based on Type I generating functions. Error\nanalysis is provided and numerical tests based on the Taylor variational\nintegrator approach of Schmitt, Shingel, Leok (2018) to time-adaptive\nvariational integration of Kepler's 2-Body problem are presented. Finally, we\nuse our adaptive framework together with the variational approach to\naccelerated optimization presented in Wibisono, Wilson, Jordan (2016) to design\nefficient variational and non-variational explicit integrators for symplectic\naccelerated optimization.\n
BibTeX
@article{duruisseaux2021adaptive,
  author = {Valentin Duruisseaux and Jeremy Schmitt and Melvin Leok},
  title = {{Adaptive Hamiltonian Variational Integrators and Applications to Symplectic Accelerated Optimization}},
  journal = {SIAM J. Sci. Comput},
  year = {2021},
  doi = {10.1137/20m1383835},
}
Figure