Time-adaptive Lagrangian variational integrators for accelerated optimization

Valentin Duruisseaux; Melvin Leok; Valentin Duruisseaux; Melvin Leok

doi:10.3934/jgm.2023010

Journal of Geometric Mechanics

2023, Volume 15, Issue 1: 224-255. doi: 10.3934/jgm.2023010

Previous Article Next Article

Research article

Time-adaptive Lagrangian variational integrators for accelerated optimization

Valentin Duruisseaux ,
Melvin Leok ^,

Department of Mathematics, University of California San Diego, La Jolla, CA 92093, USA

Received: 02 June 2022 Revised: 05 October 2022 Accepted: 06 October 2022 Published: 15 February 2023
37M15, 37N40, 34A26, 65K10, 70H15

A variational framework for accelerated optimization was recently introduced on normed vector spaces and Riemannian manifolds in ^[1] and ^[2]. It was observed that a careful combination of time-adaptivity and symplecticity in the numerical integration can result in a significant gain in computational efficiency. It is however well known that symplectic integrators lose their near-energy preservation properties when variable time-steps are used. The most common approach to circumvent this problem involves the Poincaré transformation on the Hamiltonian side, and was used in ^[3] to construct efficient explicit algorithms for symplectic accelerated optimization. However, the current formulations of Hamiltonian variational integrators do not make intrinsic sense on more general spaces such as Riemannian manifolds and Lie groups. In contrast, Lagrangian variational integrators are well-defined on manifolds, so we develop here a framework for time-adaptivity in Lagrangian variational integrators and use the resulting geometric integrators to solve optimization problems on vector spaces and Lie groups.
- accelerated optimization,
- time-adaptivity,
- symplectic optimization,
- variational integrators,
- Riemannian optimization,
- Lie group optimization
Citation: Valentin Duruisseaux, Melvin Leok. Time-adaptive Lagrangian variational integrators for accelerated optimization[J]. Journal of Geometric Mechanics, 2023, 15(1): 224-255. doi: 10.3934/jgm.2023010

Related Papers:

Abstract

A variational framework for accelerated optimization was recently introduced on normed vector spaces and Riemannian manifolds in ^[1] and ^[2]. It was observed that a careful combination of time-adaptivity and symplecticity in the numerical integration can result in a significant gain in computational efficiency. It is however well known that symplectic integrators lose their near-energy preservation properties when variable time-steps are used. The most common approach to circumvent this problem involves the Poincaré transformation on the Hamiltonian side, and was used in ^[3] to construct efficient explicit algorithms for symplectic accelerated optimization. However, the current formulations of Hamiltonian variational integrators do not make intrinsic sense on more general spaces such as Riemannian manifolds and Lie groups. In contrast, Lagrangian variational integrators are well-defined on manifolds, so we develop here a framework for time-adaptivity in Lagrangian variational integrators and use the resulting geometric integrators to solve optimization problems on vector spaces and Lie groups.

References

[1]	A. Wibisono, A. Wilson, M. Jordan, A variational perspective on accelerated methods in optimization, Proc. Natl. Acad. Sci., 113 (2016), E7351–E7358. https://doi.org/10.1073/pnas.1614734113 doi: 10.1073/pnas.1614734113
[2]	V. Duruisseaux, M. Leok, A variational formulation of accelerated optimization on Riemannian manifolds, SIAM J. Math. Data Sci., 4 (2022), 649–674. https://doi.org/10.1137/21M1395648 doi: 10.1137/21M1395648
[3]	V. Duruisseaux, J. Schmitt, M. Leok, Adaptive Hamiltonian variational integrators and applications to symplectic accelerated optimization, SIAM J. Sci. Comput., 43 (2021), A2949–A2980. https://doi.org/10.1137/20M1383835 doi: 10.1137/20M1383835
[4]	Y. Nesterov, A method of solving a convex programming problem with convergence rate $\mathcal{O}(1/k^2)$. Sov. Math. Dokl., 27 (1983), 372–376.
[5]	Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization, Kluwer Academic Publishers, Boston, MA, 2004.
[6]	W. Su, S. Boyd, E. Candes, A differential equation for modeling Nesterov's Accelerated Gradient method: theory and insights. J. Mach. Learn. Res., 17 (2016), 1–43.
[7]	M. Betancourt, M. I. Jordan, A. Wilson, On symplectic optimization. 2018. https://doi.org/10.48550/arXiv.1802.03653
[8]	C. M. Campos, A. Mahillo, D. Martín de Diego, A discrete variational derivation of accelerated methods in optimization. 2021. https://doi.org/10.48550/arXiv.2106.02700
[9]	G. França, M. I. Jordan, R. Vidal, On dissipative symplectic integration with applications to gradient-based optimization. J. Stat. Mech., 2021 (2021), 043402. https://doi.org/10.1088/1742-5468/abf5d4 doi: 10.1088/1742-5468/abf5d4
[10]	G. França, A. Barp, M. Girolami, M. I. Jordan, Optimization on manifolds: A symplectic approach, 07 2021. https://doi.org/10.48550/arXiv.2107.11231
[11]	M. I. Jordan, Dynamical, symplectic and stochastic perspectives on gradient-based optimization, In Proceedings of the International Congress of Mathematicians (ICM 2018), 523–549. https://doi.org/10.1142/9789813272880_0022
[12]	E. Hairer, C. Lubich, G. Wanner, Geometric Numerical Integration, volume 31 of Springer Series in Computational Mathematics, Springer-Verlag, Berlin, second edition, 2006.
[13]	J. P. Calvo, J. M. Sanz-Serna, The development of variable-step symplectic integrators, with application to the two-body problem, SIAM J. Sci. Comp., 14 (1993), 936–952. https://doi.org/10.1137/0914057 doi: 10.1137/0914057
[14]	B. Gladman, M. Duncan, J. Candy, Symplectic integrators for long-time integrations in celestial mechanics. Celestial Mech. Dyn. Astr., 52 (1991), 221–240. https://doi.org/10.1007/BF00048485 doi: 10.1007/BF00048485
[15]	E. Hairer, Variable time step integration with symplectic methods, Appl. Numer. Math., 25 (1997), 219–227. https://doi.org/10.1016/S0168-9274(97)00061-5 doi: 10.1016/S0168-9274(97)00061-5
[16]	K. Zare, V. G. Szebehely, Time transformations in the extended phase-space. Celestial Mech., 11 (1975), 469–482. https://doi.org/10.1007/BF01650285 doi: 10.1007/BF01650285
[17]	J. Hall, M. Leok, Spectral Variational Integrators, Numer. Math., 130 (2015), 681–740. https://doi.org/10.1007/s00211-014-0679-0 doi: 10.1007/s00211-014-0679-0
[18]	J. E. Marsden, M. West, Discrete mechanics and variational integrators. Acta Numer., 10 (2001), 357–514. https://doi.org/10.1017/S096249290100006X doi: 10.1017/S096249290100006X
[19]	T. Lee, M. Tao, M. Leok, Variational symplectic accelerated optimization on Lie groups. 2021.
[20]	M. Tao, T. Ohsawa, Variational optimization on Lie groups, with examples of leading (generalized) eigenvalue problems. In Proceedings of the 23rd International AISTATS Conference, volume 108 of PMLR, 2020.
[21]	F. Alimisis, A. Orvieto, G. Bécigneul, A. Lucchi, A continuous-time perspective for modeling acceleration in Riemannian optimization. In Proceedings of the 23rd International AISTATS Conference, volume 108 of PMLR, 1297–1307, 2020.
[22]	V. Duruisseaux, M. Leok, Accelerated optimization on Riemannian manifolds via discrete constrained variational integrators. J. Nonlinear Sci., 32 (2022). https://doi.org/10.1007/s00332-022-09795-9 doi: 10.1007/s00332-022-09795-9
[23]	V. Duruisseaux, M. Leok, Accelerated optimization on Riemannian manifolds via projected variational integrators. 2022. https://doi.org/10.48550/arXiv.2201.02904
[24]	J. Nash, The imbedding problem for Riemannian manifolds, Ann. Math., 63 (1956), 20–63. https://doi.org/10.2307/1969989 doi: 10.2307/1969989
[25]	H. Whitney, The self-intersections of a smooth $n$-manifold in $2n$-space, Ann. Math., 45 (1944), 220–246. https://doi.org/10.2307/1969265 doi: 10.2307/1969265
[26]	H. Whitney, The singularities of a smooth $n$-manifold in $(2n - 1)$-space, Ann. Math., 45 (1944), 247–293. https://doi.org/10.2307/1969266 doi: 10.2307/1969266
[27]	N. Bou-Rabee, J. E. Marsden, Hamilton–Pontryagin integrators on Lie groups part Ⅰ: Introduction and structure-preserving properties, Found. Comput. Math., 9 (2009), 197–219. https://doi.org/10.1007/s10208-008-9030-4 doi: 10.1007/s10208-008-9030-4
[28]	I. I. Hussein, M. Leok, A. K. Sanyal, A. M. Bloch, A discrete variational integrator for optimal control problems on SO(3). Proceedings of the 45th IEEE Conference on Decision and Control, 6636–6641, 2006. https://doi.org/10.1109/CDC.2006.377818 doi: 10.1109/CDC.2006.377818
[29]	T. Lee, Computational geometric mechanics and control of rigid bodies. Ph.D. dissertation, University of Michigan, 2008.
[30]	T. Lee, M. Leok, N. H. McClamroch, Lie group variational integrators for the full body problem, Comput. Methods Appl. Mech. Engrg., 196 (2007), 2907–2924. https://doi.org/10.1016/j.cma.2007.01.017 doi: 10.1016/j.cma.2007.01.017
[31]	T. Lee, M. Leok, N. H. McClamroch, Lie group variational integrators for the full body problem in orbital mechanics, Celestial Mech. Dyn. Astr., 98 (2007), 121–144. https://doi.org/10.1007/s10569-007-9073-x doi: 10.1007/s10569-007-9073-x
[32]	T. Lee, N. H. McClamroch, M. Leok, A Lie group variational integrator for the attitude dynamics of a rigid body with applications to the 3d pendulum, Proceedings of 2005 IEEE Conference on Control Applications. (CCA 2005), 962–967. https://doi.org/10.1109/CCA.2005.1507254 doi: 10.1109/CCA.2005.1507254
[33]	M. Leok, Generalized Galerkin variational integrators: Lie group, multiscale, and pseudospectral methods, (preprint, arXiv: math.NA/0508360), 2004.
[34]	N. Nordkvist, A. K. Sanyal, A Lie group variational integrator for rigid body motion in SE(3) with applications to underwater vehicle dynamics, In 49th IEEE Conference on Decision and Control (CDC), 5414–5419, 2010. https://doi.org/10.1109/CDC.2010.5717622
[35]	T. Lee, M. Leok, N. H. McClamroch, Lagrangian mechanics and variational integrators on two-spheres, Int. J. Numer. Methods Eng., 79 (2009), 1147–1174. https://doi.org/10.1002/nme.2603 doi: 10.1002/nme.2603
[36]	J. E. Marsden, T. S. Ratiu, Introduction to mechanics and symmetry, volume 17 of Texts in Applied Mathematics. Springer-Verlag, New York, second edition, 1999.
[37]	S. Lall, M. West, Discrete variational Hamiltonian mechanics, J. Phys. A, 39 (2006), 5509–5519. https://doi.org/10.1088/0305-4470/39/19/S11 doi: 10.1088/0305-4470/39/19/S11
[38]	M. Leok, J. Zhang, Discrete Hamiltonian variational integrators, IMA J. Numer. Anal., 31 (2011), 1497–1532. https://doi.org/10.1093/imanum/drq027 doi: 10.1093/imanum/drq027
[39]	J. M. Schmitt, M. Leok, Properties of Hamiltonian variational integrators, IMA J. Numer. Anal., 38 (2017), 377–398. https://doi.org/10.1093/imanum/drx010 doi: 10.1093/imanum/drx010
[40]	M. Leok, T. Shingel, Prolongation-collocation variational integrators, IMA J. Numer. Anal., 32 (2012), 1194–1216. https://doi.org/10.1093/imanum/drr042 doi: 10.1093/imanum/drr042
[41]	J. M. Schmitt, T. Shingel, M. Leok, Lagrangian and Hamiltonian Taylor variational integrators, BIT Numer. Math., 58 (2018), 457–488. https://doi.org/10.1007/s10543-017-0690-9 doi: 10.1007/s10543-017-0690-9
[42]	M. Leok, T. Ohsawa, Variational and geometric structures of discrete Dirac mechanics, Found. Comput. Math., 11 (2011), 529–562. https://doi.org/10.1007/s10208-011-9096-2 doi: 10.1007/s10208-011-9096-2
[43]	H. Yoshimura, J. E. Marsden, Dirac structures in Lagrangian mechanics Part Ⅰ: Implicit Lagrangian systems, J. Geom. Phys., 57 (2006), 133–156. https://doi.org/10.1016/j.geomphys.2006.02.009 doi: 10.1016/j.geomphys.2006.02.009
[44]	H. Yoshimura, J. E. Marsden, Dirac structures in Lagrangian mechanics Part Ⅱ: Variational structures, J. Geom. Phys., 57 (2006), 209–250. https://doi.org/10.1016/j.geomphys.2006.02.012 doi: 10.1016/j.geomphys.2006.02.012
[45]	D. Kingma, J. Ba, Adam: A method for stochastic optimization, International Conference on Learning Representations, 12 2014. https://doi.org/10.48550/arXiv.1412.6980
[46]	J. Duchi, E. Hazan, Y. Singer, Adaptive subgradient methods for online learning and stochastic optimization, J. Mach. Learn. Res., 12 (2011), 2121–2159.
[47]	T. Tieleman, G. Hinton, Coursera: Neural Networks for Machine Learning - Lecture 6.5: RMSprop, 2012.
[48]	P. A. Absil, R. Mahony, R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008. https://doi.org/10.1515/9781400830244
[49]	N. Boumal, An introduction to optimization on smooth manifolds, 2020.
[50]	J. M. Lee, Introduction to Riemannian Manifolds, volume 176 of Graduate Texts in Mathematics, Springer, Cham, second edition, 2018.
[51]	J. Jost, Riemannian Geometry and Geometric Analysis, Universitext. Springer, Cham, 7th edition, 2017.
[52]	T. Lee, M. Leok, N. H. McClamroch, Global Formulations of Lagrangian and Hamiltonian Dynamics on Manifolds: A Geometric Approach to Modeling and Analysis, Interaction of Mechanics and Mathematics. Springer International Publishing, 2017.
[53]	J. Gallier, J. Quaintance, Differential Geometry and Lie Groups: A Computational Perspective, Geometry and Computing. Springer International Publishing, 2020.
[54]	E. Celledoni, H. Marthinsen, B. Owren, An introduction to Lie group integrators – basics, new developments and applications, J. Comput. Phys., 257 (2014), 1040–1061. https://doi.org/10.1016/j.jcp.2012.12.031 doi: 10.1016/j.jcp.2012.12.031
[55]	E. Celledoni, E. Çokaj, A. Leone, D. Murari, B. Owren, Lie group integrators for mechanical systems, Int. J. Comput. Math., 99 (2022), 58–88. https://doi.org/10.1080/00207160.2021.1966772 doi: 10.1080/00207160.2021.1966772
[56]	S. H. Christiansen, H. Z. Munthe-Kaas, B. Owren, Topics in structure-preserving discretization, Acta Numer., 20 (2011), 1–119. https://doi.org/10.1017/S096249291100002X doi: 10.1017/S096249291100002X
[57]	A. Iserles, H. Z. Munthe-Kaas, S. P. Nørsett, A. Zanna, Lie group methods, Acta Numer., 9 (2000), 215–365. https://doi.org/10.1017/S0962492900002154
[58]	P. E. Crouch, R. L. Grossman, Numerical integration of ordinary differential equations on manifolds, J. Nonlinear Sci., 3 (1993), 1–33. https://doi.org/10.1007/BF02429858 doi: 10.1007/BF02429858
[59]	D. Lewis, J. C. Simo, Conserving algorithms for the dynamics of Hamiltonian systems on Lie groups, J. Nonlinear Sci., 4 (1994), 253–299. https://doi.org/10.1007/BF02430634 doi: 10.1007/BF02430634
[60]	F. Casas, B. Owren, Cost efficient Lie group integrators in the RKMK class, BIT, 43 (2003), 723–742. https://doi.org/10.1023/B:BITN.0000009959.29287.d4 doi: 10.1023/B:BITN.0000009959.29287.d4
[61]	H. Z. Munthe-Kaas, Lie-Butcher theory for Runge-Kutta methods, BIT, 35 (1995), 572–587. https://doi.org/10.1007/BF01739828 doi: 10.1007/BF01739828
[62]	H. Z. Munthe-Kaas, Runge-Kutta methods on Lie groups, Bit Numer. Math., 38 (1998), 92–111. https://doi.org/10.1007/BF02510919 doi: 10.1007/BF02510919
[63]	H. Z. Munthe-Kaas, High order Runge-Kutta methods on manifolds, Appl. Numer. Math., 29 (1999), 115–127. https://doi.org/10.1016/S0168-9274(98)00030-0 doi: 10.1016/S0168-9274(98)00030-0
[64]	S. Blanes, F. Casas, J. A. Oteo, J. Ros, The Magnus expansion and some of its applications, Phys. Rep., 470 (2008), 151–238. https://doi.org/10.1016/j.physrep.2008.11.001 doi: 10.1016/j.physrep.2008.11.001
[65]	A. Iserles, S. P. Nørsett, On the solution of linear differential equations in Lie groups, Phil. Trans. R. Soc. A, 357 (1999), 983–1019. https://doi.org/10.1098/rsta.1999.0362 doi: 10.1098/rsta.1999.0362
[66]	A. Zanna, Collocation and relaxed collocation for the Fer and the Magnus expansions, SIAM J. Numer. Anal., 36 (1999), 1145–1182. https://doi.org/10.1137/S0036142997326616 doi: 10.1137/S0036142997326616
[67]	E. Celledoni, A. Marthinsen, B. Owren, Commutator-free Lie group methods, Future Gener. Comput. Syst., 19 (2003), 341–352. https://doi.org/10.1016/S0167-739X(02)00161-9 doi: 10.1016/S0167-739X(02)00161-9
[68]	G. Wahba, A Least Squares Estimate of Satellite Attitude, SIAM Rev., 7 (1965), 409. https://doi.org/10.1137/1007077 doi: 10.1137/1007077
[69]	V. Duruisseaux, M. Leok, Practical perspectives on symplectic accelerated optimization, 2022. https://doi.org/10.48550/arXiv.2207.11460

jgm-15-01-010-s001.pdf

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)