betaFeedback

WorksMathematics

Constrained dynamics for searching saddle points on embedded Riemannian submanifolds of Euclidean space

Abstract

Finding constrained saddle points on embedded Riemannian submanifolds of Euclidean space is significant for analyzing energy landscapes arising in physics and chemistry. Existing works exploit explicit global/local regular level-set representations of manifolds, which may be unavailable or computationally inconvenient for manifolds represented through, e.g., projectors, factorizations, or rank constraints. In this paper, we develop a constrained saddle dynamic based on embedded-submanifold geometric primitives, completely avoiding the use of explicit representations. In particular, our dynamic is formulated compactly on the Grassmann bundle of the tangent bundle. By analyzing the Grassmann bundle geometry, we rigorously establish the local linear stability of the dynamic and the local linear convergence of the resulting algorithms. Remarkably, our analysis provides the first iterate convergence result for discretized algorithms to saddle points of prescribed indices in embedded-submanifold settings. Moreover, by virtue of the Grassmann bundle formulation, we remove unnecessary nondegeneracy assumptions on the eigenvalues of the Riemannian Hessian that are present in existing works. We also point out that locating saddle points can be more ill-conditioned than finding local minimizers, and requires using nonredundant parametrizations. Finally, numerical experiments on linear eigenvalue problems and electronic excited-state calculations showcase the effectiveness of the proposed algorithms and corroborate the established local theory.

Introduction

Finding the saddle points (SPs) of potential energy functionals is a fundamental task in various scientific and engineering applications, particularly those involving energy landscape analysis. For example, the transition states between two (meta)stable states, which are crucial in physics [33], chemistry [86], and biology [80], can be identified as index-1 SPs [3]. Higher-index SPs are useful for collective, multi-mode, or concerted transitions and play a key role in the construction of solution landscape [92] [42]. Here, an unconstrained index-kk SP is a critical point where the Euclidean Hessian has exactly kk negative eigenvalues. Additionally, embedded Riemannian submanifolds of Euclidean space can naturally arise as constraint sets due to the incorporation of physical laws, such as in the Thomson problem [67, 85] and Bose-Einstein condensation [2, 8, 14] [30]. In such cases, index-kk constrained SPs can be analogously defined by using the Riemannian gradient and Hessian.

In comparison with finding local or global minimizers, locating SPs exhibits two distinct and major challenges: (1) there are always unknown descent directions at SPs, rendering off-the-shelf optimization methods unstable; (2) in general, it is impossible to construct a global merit function which is variationally minimized (or maximized) at SPs, posing significant difficulties for designing globally convergent numerical methods [52].

There have been numerous algorithmic developments concerning saddle search in the unconstrained settings, together with rigorous theoretical analyses. On the contrary, the exploration in the constrained settings requires explicit global/local level-set representations of submanifolds (see Eq. (3) later for a definition). This limitation rules out applications such as electronic excited-state calculations [29, 37, 72, 88], where quotient structures and rank constraints arise in quantum-mechanical models, and explicit representations are unavailable or computationally inconvenient. In some cases, omitting the quotient structures allows applying the existing methods directly. But unlike searching for local or global minimizers, this simplification can be detrimental in our context; see Example 2 and § 4.1 later for an example involving the Stiefel and Grassmann manifolds.

In this work, we develop a constrained saddle dynamics based on embedded-submanifold geometric primitives and avoid the use of explicit level-set representations completely. We establish the theoretical properties of the continuous dynamics and the resulting discretized algorithms. We further demonstrate the effectiveness of the developed algorithms through electronic excited-state calculations on standard benchmark molecular systems.

Literature review

In the following, we review the existing works for finding SPs in both unconstrained and constrained settings. Most of them primarily focus on developing locally convergent methods, with only few exceptions [51, 83]. Our discussions are confined to cases where objective values, first-order derivatives, and (approximate) Hessian-vector products are available, excluding direct applications of Newton-type methods [5, 7] [22, 82].

Unconstrained settings. In these cases, the numerical methods for finding the index-1 SPs can be mainly categorized into two classes: single-ended and double-ended methods. The double-ended methods (also known as the path-finding or chain-of-states methods) [44, 48, 57] are fed with two candidates of local minimizers and target at finding the minimum energy path (which passes through an index-1 SP under certain conditions by the mountain pass theorem [3]). The single-ended ones (also known as the surface walking or eigenvector-following methods) [71] start with a single initial point without a priori knowledge about the final state. In this work, we focus on the class of single-ended methods1, covering the activation-relaxation technique (nouveau) [10, 11] [20, 24, 27, 62, 64], gentlest ascent dynamics [28, 74], (shrinking) dimer methods [95, 96] [45, 47, 73], among others [55, 68]. All the mentioned three methods can be set in the flow

dxdt(t)=−Proj⁡v(t)⊥(∇f(x(t)))+⟨v(t),∇f(x(t))⟩v(t)=−Rv(t)(∇f(x(t))),(1)\begin{aligned} \frac{\mathrm{d}x}{\mathrm{d}t}(t) = -\operatorname{Proj}_{v(t)^\perp}\left(\nabla f(x(t))\right) + \langle v(t), \nabla f(x(t))\rangle v(t) \\ &= -R_{v(t)}\left(\nabla f(x(t))\right), \tag*{(1)} \end{aligned}

where f:E→Rf:\mathcal{E}\to\mathbb{R} is the objective (or energy) functional, ⟨⋅,⋅⟩:E×E→R\langle\cdot,\cdot\rangle:\mathcal{E}\times\mathcal{E}\to\mathbb{R} is the inner product of the ambient Euclidean space, v(t)∈Ev(t)\in\mathcal{E} is an additional normalized direction variable, Proj⁡v(t)⊥\operatorname{Proj}_{v(t)^\perp} denotes the orthogonal projection operator onto span⁡{v(t)}⊥\operatorname{span}\{v(t)\}^\perp, defined as

Proj⁡v(t)⊥(u):=u−⟨v(t),u⟩v(t),∀ u∈E,\operatorname{Proj}_{v(t)^\perp}(u) := u-\langle v(t),u\rangle v(t),\quad\forall\ u\in\mathcal{E},

and Rv(t)R_{v(t)} represents the (Householder) reflection operator defined using v(t)v(t):

Rv(t)(u):=u−2⟨v(t),u⟩v(t)=Proj⁡v(t)⊥(u)−⟨v(t),u⟩v(t),∀ u∈E.R_{v(t)}(u) := u-2\langle v(t),u\rangle v(t)=\operatorname{Proj}_{v(t)^\perp}(u)-\langle v(t),u\rangle v(t),\quad\forall\ u\in\mathcal{E}.

Briefly speaking, instead of following the gradient flow, which leads the trajectory to a local or global minimizer, the dynamics (1) increases the objective value by climbing up along ±v(t)\pm v(t) (whose sign is determined by the angle between v(t)v(t) and grad⁡f(x(t))\operatorname{grad} f(x(t))), while decreases the value in all the directions perpendicular to v(t)v(t). An effective candidate for v(t)v(t) is the normalized eigenvector corresponding to the lowest eigenvalue of Hess⁡f(x(t))\operatorname{Hess} f(x(t)). In a neighborhood of a nondegenerate index-1 unconstrained SP, the dynamics (1) can then be viewed as the gradient flow of a local strongly convex merit function [32,35], thereby providing a local stabilization for the index-1 SP. This underlies the activation-relaxation technique (nouveau). Instead of solving for the lowest eigenvector directly, the gentlest ascent dynamics includes a direction dynamics,

dvdt(t)=−Proj⁡v(t)⊥(Hess⁡f(x(t))[v(t)]),\frac{\mathrm{d}v}{\mathrm{d}t}(t)=-\operatorname{Proj}_{v(t)^\perp}\left(\operatorname{Hess} f(x(t))[v(t)]\right),

which follows from the Euler-Lagrange equation of the associated Rayleigh-Ritz minimization. The (shrinking) dimer methods further approximate the Hessian-vector product through a central finite-difference scheme, in which the grid size is sometimes driven to 0+0^{+} as t→+∞t\to+\infty [95].

In recent years, there have been extensions for locating index-kk unconstrained SPs [92, 93] [23, 28, 32, 60, 61, 74]. For instance, the gentlest ascent dynamics can be generalized by incorporating kk direction dynamics [93] (k<dim⁡(E)k<\dim(\mathcal{E})), namely,

dxdt(t)=−RV(t)(grad⁡f(x(t)))\frac{\mathrm{d}x}{\mathrm{d}t}(t)=-R_{V(t)}\left(\operatorname{grad} f(x(t))\right)

and

dvidt(t)=−Proj⁡vi(t)⊥(Hess⁡f(x(t))[vi(t)])+2∑j=1i−1Proj⁡vj(t)(Hess⁡f(x(t))[vi(t)]),(2)\begin{aligned} \frac{\mathrm{d}v_i}{\mathrm{d}t}(t)={}&-\operatorname{Proj}_{v_i(t)^\perp}\left(\operatorname{Hess} f(x(t))[v_i(t)]\right)\\ &+2\sum_{j=1}^{i-1}\operatorname{Proj}_{v_j(t)}\left(\operatorname{Hess} f(x(t))[v_i(t)]\right), \tag*{(2)} \end{aligned}

i=1,…,ki=1,\ldots,k, with V(t):=(v1(t),…,vk(t))V(t):=(v_1(t),\ldots,v_k(t)) orthonormalized,

where RV(t)R_{V(t)} is the reflection operator defined using V(t)V(t):

RV(t)(u):=u−2∑j=1k⟨vj(t),u⟩vj(t),∀u∈E,R_{V(t)}(u):=u-2\sum_{j=1}^{k}\langle v_j(t),u\rangle v_j(t),\qquad\forall u\in\mathcal{E},

and Proj⁡vj(t)\operatorname{Proj}_{v_j(t)} refers to the orthogonal projection operator onto span⁡{vj(t)}\operatorname{span}\{v_j(t)\} (j=1,…,kj=1,\ldots,k). The second term on the right-hand side of (2) is introduced to maintain the orthonormality condition ⟨vi(t),vj(t)⟩=δij\langle v_i(t),v_j(t)\rangle=\delta_{ij} (i,j=1,…,ki,j=1,\ldots,k), by combining the Lagrangian formalism with operator splitting. Some improvements have also been made for acceleration and stabilization, including those leveraging second-order information [93, 96] [20, 74], based on local merit functions [32, 35, 38], and incorporating additional inertial terms [60]. Some works have established the linear stability of the dynamics at unconstrained SPs [93, 95] [28, 52, 60] and the local convergence of the discretized algorithms [95] [32, 35, 52, 60, 61] under the nondegeneracy assumption. The error estimates for different discretization schemes can be found in [97] [59]. Recently, there have been some attempts dealing with stochastic and degenerate settings [25,46,81]. A package has been designed for solution landscape exploration and construction based on the dynamics (2) [58].

Constrained settings. The exploration in this context remains rather limited [91, 94, 98] [54, 56]. All these works exploit explicit global/local level-set representations of Riemannian submanifolds, e.g.,

M:={x∈Rn∣c(x)=0}withc(x):=(c1(x),…,cq(x))T∈Rq,(3)\mathcal{M}:=\{x\in\mathbb{R}^{n}\mid c(x)=0\}\quad\text{with}\quad c(x):=(c_1(x),\ldots,c_q(x))^{\mathsf{T}}\in\mathbb{R}^{q}, \tag*{(3)}

where q<nq<n and the functions cic_i’s are smooth and regular, in that rank⁡(grad⁡c(x))=q\operatorname{rank}(\operatorname{grad} \mathbf{c}(\mathbf{x}))=q for any x∈M\mathbf{x}\in\mathcal{M} (note that grad⁡c(x)∈Rq×n\operatorname{grad}\mathbf{c}(\mathbf{x})\in\mathbb{R}^{q\times n}). In this case, a constrained saddle dynamics, targeting index-kk constrained SPs (k<dim⁡(M)k<\dim(\mathcal{M})), can be derived using the Lagrangian function with operator splitting as follows [91]:

dxdt(t):=−Rx(t),V(t)(grad⁡Mf(x(t)))(4)\frac{\mathrm{d}\mathbf{x}}{\mathrm{d}t}(t):=-R_{\mathbf{x}(t),V(t)}\left(\operatorname{grad}_{\mathcal{M}}f(\mathbf{x}(t))\right) \tag*{(4)}

and

dvidt(t):=−Proj⁡x(t),vi(t)⊥(Hess⁡Mf(x(t))[vi(t)])+2∑j=1i−1Proj⁡x(t),vj(t)(Hess⁡Mf(x(t))[vi(t)])+N(x(t),dxdt(t),vi(t)),(5)\begin{aligned} \frac{\mathrm{d}\mathbf{v}_i}{\mathrm{d}t}(t)&:=-\operatorname{Proj}_{\mathbf{x}(t),\mathbf{v}_i(t)^\perp}\left(\operatorname{Hess}_{\mathcal{M}}f(\mathbf{x}(t))[\mathbf{v}_i(t)]\right)\\ &\quad+2\sum_{j=1}^{i-1}\operatorname{Proj}_{\mathbf{x}(t),\mathbf{v}_j(t)}\left(\operatorname{Hess}_{\mathcal{M}}f(\mathbf{x}(t))[\mathbf{v}_i(t)]\right)+N\left(\mathbf{x}(t),\frac{\mathrm{d}\mathbf{x}}{\mathrm{d}t}(t),\mathbf{v}_i(t)\right), \tag*{(5)} \end{aligned}

i=1,…,ki=1,\ldots,k, with V(t):=(v1(t),…,vk(t))V(t):=(\mathbf{v}_1(t),\ldots,\mathbf{v}_k(t)),

where the operators Proj⁡x(t),vi(t)⊥\operatorname{Proj}_{\mathbf{x}(t),\mathbf{v}_i(t)^\perp}, Proj⁡x(t),vj(t)\operatorname{Proj}_{\mathbf{x}(t),\mathbf{v}_j(t)}, and Rx(t),V(t)R_{\mathbf{x}(t),V(t)} are similarly defined on the tangent space Tx(t)MT_{\mathbf{x}(t)}\mathcal{M}, and

N(x,dxdt,vi):=−grad⁡c(x)⊤(grad⁡c(x)⋅grad⁡c(x)⊤)−1(Hess⁡c(x)[dxdt])vi.N\left(\mathbf{x},\frac{\mathrm{d}\mathbf{x}}{\mathrm{d}t},\mathbf{v}_i\right):=-\operatorname{grad}\mathbf{c}(\mathbf{x})^\top\left(\operatorname{grad}\mathbf{c}(\mathbf{x})\cdot\operatorname{grad}\mathbf{c}(\mathbf{x})^\top\right)^{-1}\left(\operatorname{Hess}\mathbf{c}(\mathbf{x})\left[\frac{\mathrm{d}\mathbf{x}}{\mathrm{d}t}\right]\right)\mathbf{v}_i.

Note that the invertibility of grad⁡c(x)⋅grad⁡c(x)⊤\operatorname{grad}\mathbf{c}(\mathbf{x})\cdot\operatorname{grad}\mathbf{c}(\mathbf{x})^\top follows from the full rank assumption. We also recall that

Hess⁡c(x)[u]=(Hess⁡c1(x)[u],…,Hess⁡cq(x)[u])⊤∈Rq×n,∀ u∈Rn.\operatorname{Hess}\mathbf{c}(\mathbf{x})[\mathbf{u}]=\left(\operatorname{Hess}c_1(\mathbf{x})[\mathbf{u}],\ldots,\operatorname{Hess}c_q(\mathbf{x})[\mathbf{u}]\right)^\top\in\mathbb{R}^{q\times n},\quad\forall\ \mathbf{u}\in\mathbb{R}^n.

Similar dynamics have been derived in [94] [54, 56]. In [91], the authors establish the linear stability of dynamics at index-kk constrained SPs. That being said, we shall remark that it is difficult to apply the dynamics (4)–(5) directly to embedded submanifolds that lack easy-to-use explicit global/local representations, such as the Grassmann manifolds, fixed-rank manifolds, and more general cases which find applications in, e.g., electronic excited-state calculations [29, 37, 72, 88]. Moreover, the local convergence to constrained SPs with prescribed indices has not been investigated for the discretized algorithms, due to the complication of manifold settings.

Contributions

References

  1. [1]P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, 2008. MR2364186DOI
  2. [2]R. Altmann, M. Hermann, D. Peterseim, and T. Styel, Riemannian optimization methods for ground states of multicomponent Bose-Einstein condensates, IMA J. Numer. Anal. (2025), draf046.DOI
  3. [3]A. Ambrosetti and P. H. Rabinowitz, Dual variational methods in critical point theory and applications, J. Funct. Anal. 14 (1973), no. 4, 349–381. MR0370183DOI
  4. [4]D. Arrowsmith and C. M. Place, Dynamical Systems: Differential Equations, Maps, and Chaotic Behaviour, Chapman & Hall, 1992. MR1195127
  5. [5]J. Baker, An algorithm for the location of transition states, J. Comput. Chem. 7 (1986), no. 4, 385–395.DOI
  6. [6]V. Balzani, P. Ceroni, and A. Juris, Photochemistry and Photophysics: Concepts, Research, Applications, John Wiley & Sons, 2014.
  7. [7]A. Banerjee, N. Adams, J. Simons, and R. Shepard, Search for stationary points on surfaces, J. Phys. Chem. 89 (1985), no. 1, 52–57.DOI
  8. [8]W. Bao and Y. Cai, Mathematical theory and numerical methods for Bose-Einstein condensation, Kinet. Relat. Models 6 (2013), no. 1, 1–135. MR3005624DOI
  9. [9]G. M. J. Barca, A. T. B. Gilbert, and P. M. W. Gill, Communication: Hartree-Fock description of excited states of H₂, J. Chem. Phys. 141 (2014), no. 11, 111104.DOI
  10. [10]G. T. Barkema and N. Mousseau, Event-based relaxation of continuous disordered systems, Phys. Rev. Lett. 77 (1996), no. 21, 4358.DOI
  11. [11]———, The activation–relaxation technique: an efficient algorithm for sampling energy landscapes, Comput. Mater. Sci. 20 (2001), no. 3-4, 285–292.DOI
  12. [12]T. Bendokat, R. Zimmermann, and P.-A. Absil, A Grassmann manifold handbook: basic geometry and computational aspects, Adv. Comput. Math. 50 (2024), no. 1, 6. MR4721696DOI
  13. [13]J.-D. Boissonnat, A. Lieutier, and M. Wintraecken, The reach, metric distortion, geodesic convexity and the variation of tangent spaces, J. Appl. Comput. Topol. 3 (2019), no. 1, 29–58. MR3988212
  14. [14]S. N. Bose, Plancks gesetz und lichtquantenhypothese, Z. Angew. Phys. 26 (1924), no. 1, 178–181.
  15. [15]N. Boumal, An Introduction to Optimization on Smooth Manifolds, Cambridge University Press, 2023. MR4533407DOI
  16. [90]Q. Xu and A. Delin, A General Optimization Framework for Mapping Local Transition-State Networks, arXiv: 2509.26269 [physics.comp-ph], 2025.arxiv.org/abs/2509.26269
  17. [91]J. Yin, Z. Huang, and L. Zhang, Constrained high-index saddle dynamics for the solution landscape with equality constraints, J. Sci. Comput. 91 (2022), no. 2, 62. MR4405621DOI
  18. [92]J. Yin, B. Yu, and L. Zhang, Searching the solution landscape by generalized high-index saddle dynamics, Sci. China Math. 64 (2021), no. 8, 1801–1816. MR4309540DOI
  19. [93]J. Yin, L. Zhang, and P. Zhang, High-index optimization-based shrinking dimer method for finding high-index saddle points, SIAM J. Sci. Comput. 41 (2019), no. 6, A3576–A3595. MR4031473DOI
  20. [94]J. Zhang and Q. Du, Constrained shrinking dimer dynamics for saddle point search with constraints, J. Comput. Phys. 231 (2012), no. 14, 4745–4758. MR2927969DOI
  21. [95]———, Shrinking dimer dynamics and its applications to saddle point search, SIAM J. Numer. Anal. 50 (2012), no. 4, 18991921. MR3022203
  22. [96]L. Zhang, Q. Du, and Z. Zheng, Optimization-based shrinking dimer method for finding transition states, SIAM J. Sci. Comput. 38 (2016), no. 1, A528–A544. MR3461320DOI
  23. [97]L. Zhang, P. Zhang, and X. Zheng, Error estimates for Euler discretization of high-index saddle dynamics, SIAM J. Numer. Anal. 60 (2022), no. 5, 2925–2944. MR4495680arxiv.org/abs/2111.05156
  24. [98]———, Discretization and index-robust error analysis for constrained high-index saddle dynamics on the high-dimensional sphere, Sci. China Math. 66 (2023), no. 10, 2347–2360. MR4646976

Paper details

vlnc:W_rzstngvb
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 8

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents