PaperlayerView exact revision on arXiv

Source-linked AI summary

A Second-Order Method for Locating Critical Points of Prescribed Index on Energy Landscapes

Qiang Du, Baoming Shi

arXiv:2609.11038v1math.NAcs.NA

TL;DR

Locating saddle points is difficult because their unstable directions are typically unknown. The paper proposes a cubic-regularized second-order method that reflects Hessian information to target a prescribed index. Exact computations yield local quadratic convergence, while inexact computations yield local linear convergence.

  • Problem

    Saddle-point search is difficult because saddle points are unstable and their unstable eigendirections are typically unknown beforehand.

    Source: §1 · p. 1

  • Method

    The method selects Hessian eigendirections for a prescribed index, reflects gradient and Hessian information along them, and takes a cubic-regularized second-order step.

    Source: §1 · p. 2

  • Results

    Exact eigenspace and subproblem solutions give local quadratic convergence, while inexact computations give local linear convergence and fixed points precisely at critical points of the prescribed index.

    Source: §1 · p. 2, §7 · p. 20

  • Takeaways & Limitations

    The numerical experiments support the convergence results and illustrate the method's use in locating critical points and constructing solution landscapes.

    Source: §7 · p. 21

    With a fixed nonzero absolute subproblem residual, the general guarantee is convergence only to an O(εs) neighborhood of the target.

    Source: §3 · p. 11

Abstract

from arXiv · show

Exploring high dimensional energy landscape is a challenging problem in many applications where both ground states and transition states offer important information about the underlying physical systems. To facilitate the computational exploration, we propose a cubic-regularized second-order method for locating critical points of prescribed index, including both energy minima (with an index $0$) and transition states (saddle points with positive index). At each step of the iteration, the proposed method involves several ingredients, such as updating the eigen-directions of the Hessian according to the prescribed index, reflecting the gradient and the Hessian along selected unstable eigen-directions, if any, and constructing the next step by solving a cubic-regularized subproblem. Under suitable assumptions, we show that, when the eigenspace and the cubic subproblem are solved exactly, the iteration converges locally and quadratically to a critical point of the prescribed index. We further establish convergence results in the inexact setting, where both the eigenspace computation and the solution of the cubic subproblem are performed approximately. We show that the resulting iteration retains local linear convergence, with the convergence rate depending on the accuracy of the inexact computations. Moreover, we prove that the fixed points of the algorithm are precisely critical points of the prescribed index. In addition, we introduce an adaptive strategy for updating the cubic regularization parameter to improve robustness and computational efficiency of the proposed algorithm. Numerical experiments confirm the predicted convergence behavior, demonstrate the effectiveness of the adaptive strategy, and illustrate the capability of the proposed method for locating critical points and constructing solution landscapes.

1. Introduction.

Prescribed-index saddle search is difficult because unstable directions are not known in advance, while existing approaches trade index selectivity against fast local convergence. The paper combines index selection with cubic regularization to target critical points of a chosen index.

1. Introduction.

  • Saddle points are harder to locate than minima because they are unstable and their unstable eigendirections are typically unknown beforehand.The paper distinguishes path-finding methods from surface-walking methods that update directly on the energy landscape.Source: §1 · pp. 1–2
  • HiSD selects a prescribed index but generally converges locally only linearly, whereas Newton converges quadratically without controlling the limiting point's index.This contrast motivates a method that combines index selectivity with faster local convergence.Source: §1 · p. 2
  • The proposed cubic-regularized second-order framework reflects gradient and Hessian information along selected unstable eigendirections to target a prescribed index.With exact eigenspace and cubic-subproblem solutions, it converges locally and quadratically; inexact solutions yield local linear convergence, and its fixed points are precisely critical points of the prescribed index.Source: §1 · p. 2
  • The analysis restricts attention to finite-dimensional energy functions with finitely many nondegenerate critical points.An index-k point has a k-dimensional negative spectral subspace of the Hessian.Source: §1 · p. 3

2. Critical points and the second-order method.

The method combines Hessian-based index selection with a reflected cubic model, then characterizes its local convergence and fixed points. Under local regularity and a strict index-k critical point, exact subproblem solutions give local quadratic convergence.

2. Critical points and the second-order method.

  • Saddle dynamics provides a first-order prescribed-index alternative, but generally converges only linearly, with its rate depending on Hessian conditioning.Newton's method converges quadratically to nondegenerate critical points but does not select their index.Source: §2 · p. 3
  • Reflecting the gradient and Hessian along eigenvectors for the k smallest Hessian eigenvalues embeds index selection in a cubic-regularized second-order step.The method extends cubic regularization, ordinarily aimed at index-0 minima, to critical points of arbitrary prescribed index.Source: §2 · pp. 3–4
  • A strict index-k critical point with a locally Lipschitz Hessian and a spectral gap yields a positive-definite reflected Hessian and a unique local cubic-subproblem minimizer.The stated neighborhood assumptions bound the negative and positive Hessian eigenvalues away from zero.Source: §2 · pp. 4–5
  • With exact computations and regularization parameters bounded above and away from zero, the iteration converges locally and quadratically to the strict index-k critical point.The result applies when the initial point lies within a sufficiently small neighborhood.Source: §2 · pp. 4–5
  • Under the nondegeneracy assumption, the algorithm's fixed points are exactly the critical points of the prescribed index.A critical point of a different index cannot be a fixed point because its reflected Hessian retains a negative direction.Source: §2 · p. 7

3. Inexact invariant subspaces and inexact solutions of subproblem.

The method allows both the unstable subspace and cubic subproblem to be computed approximately, with errors measured through subspace projectors and a relative residual condition. Under suitable assumptions, the inexact iteration converges locally, and a zero step characterizes critical points of the prescribed index.

Inexact computations

  • The inexact method measures eigenspace error through spectral projectors and uses a relative step residual that may be nonzero but shrinks as the target is approached.Projector error is invariant to eigenvector sign changes and orthogonal basis changes within a multiple eigenspace.Source: §3 · p. 8

Approximate cubic model

  • Bounding the subspace error by the stated threshold keeps the approximate reflected Hessian positive definite, making the approximate cubic model strongly convex with a unique global minimizer.The proof gives eBj ⪰ μ/2 I under the stated error bound.Source: §3 · pp. 8–9

Inexact convergence

  • Under suitable assumptions, inexact computations yield local linear convergence, which becomes superlinear or quadratic as the combined errors vanish or decay with the iterate error.The relative convergence factor depends on the approximation accuracies; implementable error choices can preserve quadratic convergence.Source: §3 · p. 10

Accuracy and convergence

  • Fixed sufficiently small subspace-error bounds and relative step residuals generally guarantee only linear convergence, while a fixed nonzero absolute step residual guarantees convergence only to an O(εs) neighborhood.The relative residual condition avoids the additive error term that arises with a fixed absolute residual.Source: §3 · p. 11

Fixed points

  • Under the stated conditions, a zero inexact step occurs if and only if the iterate is an index-k critical point.The result assumes nondegenerate critical points and specified accuracy and second-order conditions on the computed step.Source: §3 · pp. 11–12

4. The methods for updating the invariant subspaces and solving the subproblems.

The implementation reuses approximate unstable eigenspaces across iterations, offers direct and Krylov-based cubic-subproblem solvers, and adapts regularization using observed model error.

4.1. Solvers for the cubic subproblem.

  • For moderate dimensions, spectral decomposition reduces the cubic subproblem to a scalar root-finding problem, with extra care required in the hard case.When the gradient is orthogonal to the leftmost eigenspace and the optimal shift is −θ1, the shifted matrix is singular.Source: §4.1 · pp. 12–13
  • For large-scale problems, Lanczos restricts the cubic subproblem to a Krylov space, requiring only Hessian-vector products and supporting sparse or matrix-free Hessians.Under the stated nondegenerate conditions, its solution and objective errors decay as O(ρ^ℓ) and O(ρ^(2ℓ)), respectively.Source: §4.1 · p. 13
  • If the gradient is orthogonal to the leftmost eigenspace, standard Lanczos may miss a component of the global minimizer, so a restart with an additional direction is needed.Ill-conditioned problems can also require large subspaces, increasing storage and orthogonalization costs.Source: §4.1 · p. 13

4.2. Updating the invariant subspace.

  • The unstable eigenspace is updated from the previous iteration’s approximation rather than recomputed from scratch, using block Lanczos or restarted LOBPCG.LOBPCG combines the current approximation, preconditioned residual, and inherited search directions; block methods can help when targeted eigenvalues are clustered.Source: §4.2 · pp. 14–15
  • The outer algorithm accepts a sufficiently accurate approximation of the invariant subspace and can warm-start it, without depending on a particular eigensolver.The block Krylov variant recycles the updated subspace while keeping the Krylov depth fixed, bounding storage and orthogonalization costs at each outer iteration.Source: §4.2 · pp. 14–15

4.3. Adaptive strategy for the cubic regularization parameter.

  • A large regularization parameter can slow convergence, while a small one can undermine the local model and make invariant-subspace updates less robust.The adaptive strategy measures gradient Taylor-approximation error because total energy variation need not be negative during saddle-point search.Source: §4.2 · p. 15, §4.3 · p. 15
  • The adaptive rule adjusts the cubic regularization using Taylor-model discrepancy relative to the cubic term, increasing stabilization when the discrepancy is too large.It retains the current parameter within an acceptance interval and bounds parameter changes; the discrepancy uses quantities already available in the iteration.Source: §4.3 · pp. 15–16

4. The methods for updating the invariant subspaces and solving the subproblems.

  • Solution-landscape construction searches downward from higher-index points along unstable directions and upward from lower-index points to find higher-index points.Perturbed starts along positive and negative unstable directions can lead to new lower-index critical points; repeating both searches can assemble critical points of different indices.Source: §5 · p. 16

5. Construction of the solution landscape.

The landscape construction procedure uses unstable directions to search from known critical points for points of lower or higher index.

5. Construction of the solution landscape.

  • To find a lower-index point, perturb a known higher-index critical point along an unstable direction and run Algorithm 2.1 with the target lower index.Positive and negative perturbations typically yield a pair of lower-index critical points; repeating downward and upward searches can systematically identify points of different indices.Source: §5 · p. 16
  • Starting from a known lower-index critical point, the procedure can also search for higher-index critical points.The authors contrast this with Newton’s method, which they say would drive the perturbed iterates back toward the original nondegenerate critical point.Source: §5 · p. 16
  • The numerical experiments are designed to illustrate solution-landscape construction alongside the algorithm’s convergence and index-selectivity properties.The experiments also examine adaptive regularization against fixed parameters and a standard optimization strategy.Source: §6 · p. 16

6. Numerical experiments.

The experiments test index selectivity and convergence on benchmark functions, demonstrate landscape construction, and assess adaptive regularization on a discrete liquid-crystal energy.

6.1. Four-well potential.

  • Varying k from 0 to 2 at the same four-well initial point reaches a minimum, an index-1 saddle, and an index-2 saddle, with quadratic convergence.Starting from the index-2 saddle, the procedure also connects to four index-1 saddles and then to the four minima.Source: Figure 1 · p. 17, §6.1 · p. 17

6.2. Rosenbrock function.

  • On the modified Rosenbrock function, the second-order method reaches prescribed accuracy in tens of iterations and under 0.1 seconds, versus thousands of iterations and several seconds for the first-order method.Exact computations show a slope of approximately 2; inexact computations converge linearly, with faster convergence as δ and η decrease.Source: Figure 2 · p. 18, §6.2 · p. 19

6.3. Landau-de Gennes energy functional.

  • For the discrete Landau–de Gennes energy, the method identifies seven distinct critical points up to symmetry for k ≤ 4, including two local minima corresponding to experimentally observed stable configurations.The index-4 saddle is represented by WORS, characterized by two line defects along the square’s diagonals.Source: Figure 3 · p. 19, §6.3 · p. 20
  • For an index-2 saddle, adaptive regularization reaches the solution in fewer iterations than a large fixed σ = 1000, while a small fixed σ = 10 causes divergence.The authors attribute the latter to an excessively large initial step and an inadequate local model.Source: Figure 3 · p. 19, §6.3 · p. 20
  • For a local minimum, both adaptive strategies outperform fixed regularization parameters and show comparable performance.The compared adaptive strategies are the reduction-ratio strategy and the paper’s gradient-remainder-ratio strategy.Source: Figure 3 · p. 19, §6.3 · p. 20

7. Conclusion and discussion.

The conclusion highlights the adaptive regularization strategy and identifies extensions to trust-region and large-scale optimization frameworks as future work.

7. Conclusion and discussion.

  • The adaptive cubic-regularization strategy is presented as improving the algorithm’s robustness and efficiency.The experiments are reported to confirm the predicted convergence behavior and demonstrate landscape construction.Source: §7 · p. 21
  • Future work may extend the framework to trust-region methods and adapt stochastic or subsample optimization variants to prescribed-index critical-point computation.The authors note that cubic regularization and trust-region methods have closely related mechanisms for step-size control and local-model reliability.Source: §7 · p. 21
Loading 2609.11038v1…