Riemannian Multilevel Optimization Cuts Constrained Solver Time

Multilevel optimization is attractive for discretized energy problems because coarse grids can remove low-frequency error much faster than a fine-grid method alone. The obstacle in this paper is geometric: Kohn-Sham orbitals, Gross-Pitaevskii ground states, and continuous-cut segmentations do not live in unconstrained Euclidean space. Their iterates lie on Stiefel, ellipsoid, or Bernoulli-type manifolds, where a naive coarse correction can fail to be a descent direction after transfer back to the fine level.

The authors introduce a Riemannian multilevel framework that keeps the multigrid idea but rebuilds the coarse model, restriction, prolongation, and descent test in manifold terms. The result is both algorithmic and analytic: a two-level correction scheme, a recursive multilevel method, and a global convergence proof showing that the Riemannian gradient norm tends to zero under compactness, smoothness, Lipschitz, Wolfe-step, and bounded-step assumptions.

Core Contribution

The paper's main contribution is a first-order coherent Riemannian coarse model. At a fine iterate, the method restricts the point to a coarser manifold, builds a coarse objective whose first-order information matches the fine objective through vector restriction, approximately minimizes that coarse model, and then prolongates the resulting coarse search direction back to the fine tangent space. If the transferred direction is not a descent direction, the algorithm falls back to a fine-level Riemannian gradient step.

That fallback is not just an implementation detail. It is what makes the convergence argument work without assuming every coarse model behaves well globally. The proof separates ordinary gradient steps from coarse-correction steps and applies a Riemannian Zoutendijk-type argument to show

Figure 2 gives the clearest map of the design space: differential-based transfer operators satisfy the geometric Galerkin condition without an ambient embedding, while projection-based versions depend on the embedding and need a consistency condition.

Technical Approach

The multilevel algorithm alternates between two moves. A fine-level Riemannian gradient step is used when the coarse-condition test fails. When it passes, the method computes a restricted point, constructs a coarse objective, solves that coarse problem approximately, transfers the coarse correction through a vector prolongation operator, then performs a line search on the fine manifold.

A large part of the paper is about making that transfer legitimate. The authors define metric-compatible vector transfer operators, including intrinsic differential constructions and extrinsic projection-based constructions. The geometric Galerkin condition is the organizing principle: the restricted fine gradient and the gradient of the coarse model must align in the appropriate Riemannian metrics. The paper also studies how this choice changes across applications. On Stiefel and ellipsoid manifolds, the metric is comparatively controlled; on the Bernoulli manifold used for continuous cuts, metric-aware transfer is especially important because the geometry changes with the iterate.

Results and Analysis

The experiments support the main claim, though many of the results are presented as convergence curves rather than compact benchmark tables. On the GaAs Kohn-Sham model, the multilevel variants reduce both energy error and residual norm faster than single-level H1RGD and H1RCG. The CPU-time plots show the 4-level method as the best of the reported multilevel variants, illustrating the practical trade-off that more levels are not automatically better once coarse-model construction and transfer costs are included.

Figure 5 shows the CPU-time version of this comparison for the GaAs experiment. The useful reading is not simply that multilevel wins, but that the adaptive 4-level schedule finds a strong cost balance among the reported methods.

The Gross-Pitaevskii experiments show a similar pattern. The 4-level EARGD scheme converges faster than the single-level EARGD baseline, and the vector-transfer comparison shows that the choice of transfer operator matters even when the high-level algorithm is unchanged.

For binary continuous cuts, the paper uses the Bernoulli manifold setting to test how different vector-transfer constructions affect coarse corrections in a segmentation-style problem. The important conclusion is qualitative but practically relevant: preserving the right Riemannian first-order information matters, and transfer rules that look similar in Euclidean terms can behave differently once the manifold metric is taken seriously.

Limitations

The evidence is strongest for the proposed class of discretized energy problems, not for arbitrary manifold optimization. The authors explicitly leave quantitative convergence-rate analysis open, along with adaptive coarsening strategies and integration with second-order optimization methods. The experiments also depend on problem-specific discretizations and transfer choices; the framework is general, but the best operator is not universal.