pith. sign in

arxiv: 2507.13071 · v2 · submitted 2025-07-17 · 💻 cs.SC · math.OC

Probabilistic algorithm for computing all local minimizers of Morse functions on a compact domain

Mohab Safey El Din (PolSys) , Georgy Scholten (MPI-CBG , CSBD) , Emmanuel Tr\'elat (LJLL (UMR\_7598) , CaGE) This is my paper

Pith reviewed 2026-05-19 04:36 UTC · model grok-4.3

classification 💻 cs.SC math.OC
keywords Morse functionslocal minimizersnoisy evaluationspolynomial approximationcomputer algebraprobabilistic algorithmsglobal optimization
0
0 comments X

The pith

A probabilistic algorithm returns rational points whose epsilon-balls contain and separate all local minimizers of a Morse function given by noisy evaluations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper designs an algorithm that locates every local minimizer of a Morse function on the unit cube when the function is supplied only through an evaluation program that returns noisy approximations. It first builds polynomial approximants from samples at randomly chosen points, then solves the resulting algebraic systems to produce candidate rational points. Under probabilistic conditions on the sample locations, these points isolate each minimizer inside a ball of prescribed radius epsilon while keeping the balls disjoint. The method supplies explicit bit-complexity bounds once regularity parameters are known and has been implemented to solve previously unreachable examples.

Core claim

Given a noisy evaluation program Gamma, noise bound eta, target accuracy epsilon, and known regularity parameters, the algorithm outputs finitely many rational points in the unit cube such that the epsilon-balls centered at these points contain every local minimizer of the Morse function and the balls remain pairwise disjoint.

What carries the argument

Polynomial approximants obtained from noisy samples, followed by computer-algebra methods that solve the critical-point equations of the approximants.

If this is right

  • The returned rational points give certified isolation regions for each local minimizer.
  • Bit complexity is polynomial in the input size once regularity parameters are fixed.
  • The same framework applies to any compact domain that can be mapped to the unit cube.
  • The implementation in Globtim demonstrates that the method scales to examples beyond reach of prior symbolic approaches.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The separation property could be used to initialize local descent methods with guaranteed distinct basins.
  • Replacing the Morse assumption with a generic transversality condition might allow the same pipeline to find all critical points.
  • The probabilistic sampling step suggests a natural Monte-Carlo variant that repeats the procedure until the output set stabilizes.

Load-bearing premise

The function is Morse with all regularity parameters supplied in advance, and the randomly chosen evaluation points satisfy the stated probabilistic conditions.

What would settle it

Apply the algorithm to a concrete Morse function whose local minimizers are known exactly, then verify whether every output ball contains precisely one minimizer and whether any minimizer is missed.

Figures

Figures reproduced from arXiv: 2507.13071 by CaGE), CSBD), Emmanuel Tr\'elat (LJLL (UMR\_7598), Georgy Scholten (MPI-CBG, Mohab Safey El Din (PolSys).

Figure 1
Figure 1. Figure 1: Separating distance between critical points of the objective and approximant functions [PITH_FULL_IMAGE:figures/full_fig_p021_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The critical points of the approximant wd,S computed with Msolve are plotted in green and blue. Green if they fall within a distance of 5.e−3 from a critical point computed with Chebfun2 and blue for those not. The white points are the missing critical points computed by Chebfun2 but not Globtim. Using chebfun2, we compute 330 critical points of f in the domain [−3/8, 3/8]2 via the construc￾tion of a rank … view at source ↗
Figure 3
Figure 3. Figure 3: The vanishing curves of the partials of the partials of the De Jong function computed [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: The 25 local minimizers of the De Jong function are depicted in green, and the red stars [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Starting at degree d = 20, the approximant wd fully captures the local minimizers of the De Jong function over the domain [−50, 50]2 , although it also add many spurious critical points around the boundary. As the degree d increases from 2 to 24, we observe convergence of the critical points of wd,S towards the critical points of f, which we computed using chebfun2. Example 4 (Deuflhard Function). The leve… view at source ↗
Figure 6
Figure 6. Figure 6: Critical points of w22,S captured using Chebyshev tensorized polynomials. Polynomial Degree 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 0 2 4 6 8 [PITH_FULL_IMAGE:figures/full_fig_p026_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Total number of local minimizers globtim has computed (BFGS-optimized solutions). In [PITH_FULL_IMAGE:figures/full_fig_p026_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Analysis of polynomial approximation quality: (a) discrete [PITH_FULL_IMAGE:figures/full_fig_p027_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Contour plot of the H¨older table 2 function. The blue points depict all the local mini [PITH_FULL_IMAGE:figures/full_fig_p028_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Analysis of polynomial approximation quality: (a) discrete [PITH_FULL_IMAGE:figures/full_fig_p029_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Analysis of polynomial approximation quality: (a) discrete [PITH_FULL_IMAGE:figures/full_fig_p029_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Combined output from all 16 subdomains. In blue the minimal distance from the each [PITH_FULL_IMAGE:figures/full_fig_p030_12.png] view at source ↗
read the original abstract

Let K be the unit-cube in Rn and f\,: K $\rightarrow$ R^n be a Morse function. We assume that the function f is given by an evaluation program $\Gamma$ in the noisy model, i.e., the evaluation program $\Gamma$ takes an extra parameter $\eta$ as input and returns an approximation that is $\eta$-close to the true value of f . In this article, we design an algorithm able to compute all local minimizers of f on K . Our algorithm takes as input $\Gamma$, $\eta$, a numerical accuracy parameter $\epsilon$ as well as some extra regularity parameters which are made explicit. Under assumptions of probabilistic nature -- related to the choice of the evaluation points used to feed $\Gamma$ --, it returns finitely many rational points of K , such that the set of balls of radius $\epsilon$ centered at these points contains and separates the set of all local minimizers of f . Our method is based on approximation theory, yielding polynomial approximants for f , combined with computer algebra techniques for solving systems of polynomial equations. We provide bit complexity estimates for our algorithm when all regularity parameters are known. Practical experiments show that our implementation of this algorithm in the Julia package Globtim can tackle examples that were not reachable until now.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper presents a probabilistic algorithm for computing all local minimizers of a Morse function f on the unit cube K in R^n, where f is provided via a noisy evaluation oracle Γ with noise parameter η. Given also an accuracy parameter ε and known regularity parameters, the algorithm selects random evaluation points, constructs polynomial approximants of controlled degree, solves the resulting algebraic critical-point systems exactly, and outputs finitely many rational points such that the ε-balls around them contain and separate all true local minimizers with high probability under the stated sampling assumptions. Bit-complexity estimates are derived and the method is implemented in the Globtim Julia package with supporting experiments.

Significance. If the central claims are verified, the work supplies a concrete bridge between approximation theory, algebraic geometry, and global optimization for Morse functions under noise. The explicit bit-complexity bounds when regularity parameters are known, together with the reproducible implementation, constitute a measurable contribution that could be used as a baseline for further symbolic-numeric global optimization algorithms.

minor comments (3)
  1. The abstract states that regularity parameters are 'made explicit,' yet the input specification and any procedure for obtaining or validating them should be stated more precisely in the algorithm description to avoid ambiguity for implementers.
  2. In the complexity analysis, the dependence of the success probability on the number of sample points and the noise level η could be summarized in a single displayed inequality for quick reference.
  3. The experimental section would benefit from reporting the observed success rate over multiple random trials rather than single-run timings, to illustrate the probabilistic guarantee in practice.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful summary of our manuscript, the positive assessment of its significance, and the recommendation for minor revision. We are pleased that the work is viewed as providing a concrete bridge between approximation theory, algebraic geometry, and global optimization.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation proceeds from known regularity parameters and a noisy evaluation oracle to polynomial approximants via standard approximation theory, followed by exact algebraic solution of critical-point systems; the Morse assumption and known derivative bounds control the approximation error to preserve the non-degenerate critical points, while probabilistic sampling only guarantees sufficient accuracy with high probability. No quantity is defined in terms of the output, no fitted parameter is relabeled as a prediction, and no load-bearing step reduces to a self-citation whose content is itself unverified or to an ansatz smuggled from prior work by the same authors. The central claim therefore rests on independent external results from approximation theory and computer algebra rather than on any internal redefinition or circular reduction.

Axiom & Free-Parameter Ledger

3 free parameters · 2 axioms · 0 invented entities

The central claim depends on the function being Morse, on known regularity parameters, and on probabilistic success over random evaluation points; these are domain assumptions and inputs rather than derived quantities.

free parameters (3)
  • η (noise level)
    Input tolerance for the noisy evaluation program Γ.
  • ε (accuracy parameter)
    User-specified radius for the isolating balls.
  • regularity parameters
    Extra parameters required by the algorithm and made explicit as inputs.
axioms (2)
  • domain assumption f is a Morse function on the compact domain K
    Ensures all critical points are non-degenerate so that local minimizers can be isolated.
  • ad hoc to paper Probabilistic assumptions on the random choice of evaluation points
    The success probability and separation guarantees rely on these assumptions about how points are chosen to feed Γ.

pith-pipeline@v0.9.0 · 5789 in / 1419 out tokens · 39853 ms · 2026-05-19T04:36:09.898415+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    A. G. Babenko, The exact constant in the Jackson inequality in L2, Mat. Zametki, 39 (1986), pp. 651–664

    work page 1986

  2. [2]

    Bagby, L

    T. Bagby, L. Bos, and N. Levenberg , Multivariate simultaneous approximation, Constr. Approx., 18 (2002), pp. 569–577

    work page 2002

  3. [3]

    B. Bank, M. Giusti, J. Heintz, and M. Safey El Din , Intrinsic complexity estimates in polynomial optimization , Journal of Complexity, 30 (2014), pp. 430–443. 30

    work page 2014

  4. [4]

    Bel-Afia, C

    Z. Bel-Afia, C. Meroni, and S. Telen , Chebyshev varieties, 2024

    work page 2024

  5. [5]

    Berrut and H

    J.-P. Berrut and H. D. Mittelmann , Lebesgue constant minimizing linear rational in- terpolation of continuous functions over the interval , Computers & Mathematics with Appli- cations, 33 (1997), pp. 77–86

    work page 1997

  6. [6]

    Berrut and L

    J.-P. Berrut and L. N. Trefethen, Barycentric lagrange interpolation, SIAM Review, 46 (2004), pp. 501–517

    work page 2004

  7. [7]

    Berthomieu, C

    J. Berthomieu, C. Eder, and M. Safey El Din, msolve: A library for solving polynomial systems, in 2021 International Symposium on Symbolic and Algebraic Computation, 46th International Symposium on Symbolic and Algebraic Computation, Saint Petersburg, Russia, July 2021, ACM, pp. 51–58

    work page 2021

  8. [8]

    Berthomieu, V

    J. Berthomieu, V. Neiger, and M. Safey El Din , Faster change of order algorithm for Gr¨ obner bases under shape and stability assumptions , in 47th International Symposium on Symbolic and Algebraic Computation, Lille, France, July 2022

    work page 2022

  9. [9]

    Bornemann, D

    F. Bornemann, D. Laurie, S. Wagon, and J. Waldvogel , The SIAM 100-Digit Chal- lenge, Society for Industrial and Applied Mathematics, 2004

    work page 2004

  10. [10]

    Breiding and S

    P. Breiding and S. Timme, Homotopycontinuation.jl: A package for homotopy continuation in julia , in Mathematical Software – ICMS 2018, J. H. Davenport, M. Kauers, G. Labahn, and J. Urban, eds., Cham, 2018, Springer International Publishing, pp. 458–465

    work page 2018

  11. [11]

    E. W. Cheney , Introduction to approximation theory. , International series in pure and ap- plied mathematics, McGraw-Hill, 1966

    work page 1966

  12. [12]

    Chkifa, A

    A. Chkifa, A. Cohen, G. Migliorati, F. Nobile, and R. Tempone , Discrete least squares polynomial approximation with random evaluations - application to parametric and stochastic elliptic pdes , ESAIM: M2AN, 49 (2015), pp. 815–837

    work page 2015

  13. [13]

    Cohen, M

    A. Cohen, M. A. Davenport, and D. Leviatan , On the stability and accuracy of least squares approximations, Foundations of Computational Mathematics, 13 (2013), pp. 819–834

    work page 2013

  14. [14]

    Cohen and G

    A. Cohen and G. Migliorati, Optimal weighted least-squares methods, The SMAI Journal of computational mathematics, 3 (2017), pp. 181–203

    work page 2017

  15. [15]

    D. Cox, J. Little, and D. O’Shea , Ideals, Varieties, and Algorithms. An Introduction to Computational Algebraic Geometry and Commutative Algebra , 2007

    work page 2007

  16. [16]

    Dolgov, D

    S. Dolgov, D. Kressner, and C. Str ¨ossner, Functional Tucker approximation using Chebyshev interpolation, SIAM Journal on Scientific Computing, 43 (2021), pp. A2190–A2210

    work page 2021

  17. [17]

    Eisenbud, Commutative algebra: with a view toward algebraic geometry , vol

    D. Eisenbud, Commutative algebra: with a view toward algebraic geometry , vol. 150, Springer Science & Business Media, 2013

    work page 2013

  18. [18]

    J. C. Faug`ere, A new efficient algorithm for computing gr¨ obner bases without reduction to zero (f5) , in Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC ’02, New York, NY, USA, 2002, Association for Computing Machinery, p. 75–83

    work page 2002

  19. [19]

    Faug `ere, P

    J. Faug `ere, P. Gianni, D. Lazard, and T. Mora , Efficient computation of zero- dimensional Gr¨ obner bases by change of ordering , Journal of Symbolic Computation, 16 (1993), pp. 329–344. 31

    work page 1993

  20. [20]

    Faug´ere, A new efficient algorithm for computing gr¨ obner bases (f4), Journal of Pure and Applied Algebra, 139 (1999), pp

    J.-C. Faug´ere, A new efficient algorithm for computing gr¨ obner bases (f4), Journal of Pure and Applied Algebra, 139 (1999), pp. 61–88

    work page 1999

  21. [21]

    Heintz, Definability and fast quantifier elimination in algebraically closed fields , Theoret- ical Computer Science, 24 (1983), pp

    J. Heintz, Definability and fast quantifier elimination in algebraically closed fields , Theoret- ical Computer Science, 24 (1983), pp. 239–277

    work page 1983

  22. [22]

    Incardona, A

    P. Incardona, A. Leo, Y. Zaluzhnyi, R. Ramaswamy, and I. F. Sbalzarini, Openfpm: A scalable open framework for particle and particle-mesh codes on parallel computers , Com- puter Physics Communications, 241 (2019), pp. 155–177

    work page 2019

  23. [23]

    Jamil and X.-S

    M. Jamil and X.-S. Yang, A literature survey of benchmark functions for global optimisation problems, International Journal of Mathematical Modelling and Numerical Optimisation, 4 (2013), pp. 150–194

    work page 2013

  24. [24]

    Korneichuk, Exact constants in approximation theory , vol

    N. Korneichuk, Exact constants in approximation theory , vol. 38 of Encyclopedia of Math- ematics and its Applications, Cambridge University Press, Cambridge, 1991. Translated from the Russian by K. Ivanov

    work page 1991

  25. [25]

    Laumond, ed., Robot motion planning and control, vol

    J.-P. Laumond, ed., Robot motion planning and control, vol. 229 of Lecture Notes in Control and Information Sciences, Springer-Verlag London, Ltd., London, 1998

    work page 1998

  26. [26]

    Lazard, Gr¨ obner bases, gaussian elimination and resolution of systems of algebraic equa- tions, in Computer Algebra, J

    D. Lazard, Gr¨ obner bases, gaussian elimination and resolution of systems of algebraic equa- tions, in Computer Algebra, J. A. van Hulzen, ed., Berlin, Heidelberg, 1983, Springer Berlin Heidelberg, pp. 146–156

    work page 1983

  27. [27]

    Melczer and B

    S. Melczer and B. Salvy , Effective coefficient asymptotics of multivariate rational func- tions via semi-numerical algorithms for polynomial systems , Journal of Symbolic Computa- tion, 103 (2021), pp. 234–279

    work page 2021

  28. [28]

    G. Migliorati, Multivariate Markov-type and Nikolskii-type inequalities for polynomials as- sociated with downward closed multi-index sets, Journal of Approximation Theory, 189 (2015), pp. 137–159

    work page 2015

  29. [29]

    Migliorati, F

    G. Migliorati, F. Nobile, and R. Tempone , Convergence estimates in probability and in expectation for discrete least-squares with noisy evaluations at random points , Journal of Multivariate Analysis, 142 (2015), pp. 167–182

    work page 2015

  30. [30]

    Minguez, F

    J. Minguez, F. Lamiraux, and J.-P. Laumond , Motion planning and obstacle avoid- ance, in Springer Handbook of Robotics, Springer Handbooks. Springer, Cham. Siciliano, B., Khatib, O. (eds)., 2016, pp. 1177–1201

    work page 2016

  31. [31]

    Nakatsukasa, V

    Y. Nakatsukasa, V. Noferini, and A. Townsend , Computing the common zeros of two bivariate functions via B´ ezout resultants, Numerische Mathematik, 129 (2015), pp. 181–209

    work page 2015

  32. [32]

    Ple´sniak, Multivariate Jackson inequality, Journal of Computational and Applied Math- ematics, 233 (2009), pp

    W. Ple´sniak, Multivariate Jackson inequality, Journal of Computational and Applied Math- ematics, 233 (2009), pp. 815–820. 9th OPSFA Conference

    work page 2009

  33. [33]

    Rivlin, The Chebyshev Polynomials , A Wiley-Interscience publication, Wiley, 1974

    T. Rivlin, The Chebyshev Polynomials , A Wiley-Interscience publication, Wiley, 1974

    work page 1974

  34. [34]

    M. Safey El Din and ´Eric Schost , Bit complexity for multi-homogeneous polynomial system solving—application to polynomial minimization , Journal of Symbolic Computation, 87 (2018), pp. 176–206

    work page 2018

  35. [35]

    I. R. Shafarevich, Basic algebraic geometry; 3rd ed. , Springer, Berlin, 2013. 32

    work page 2013

  36. [36]

    T. M. Shami, A. A. El-Saleh, M. Alswaitti, Q. Al-Tashi, M. A. Summakieh, and S. Mirjalili, Particle swarm optimization: A comprehensive survey , IEEE Access, 10 (2022), pp. 10031–10061

    work page 2022

  37. [37]

    Timan, I

    A. Timan, I. Sneddon, S. Ulam, and M. Stark , Theory of Approximation of Functions of a Real Variable, ISSN, Elsevier Science, 2014

    work page 2014

  38. [38]

    Townsend and L

    A. Townsend and L. N. Trefethen , An extension of Chebfun to two dimensions , SIAM Journal on Scientific Computing, 35 (2013), pp. C495–C518

    work page 2013

  39. [39]

    L. N. Trefethen , Approximation Theory and Approximation Practice, Extended Edition , Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019

    work page 2019

  40. [40]

    Tr´elat, Optimal control and applications to aerospace: some results and challenges , J

    E. Tr´elat, Optimal control and applications to aerospace: some results and challenges , J. Optim. Theory Appl., 154 (2012), pp. 713–758

    work page 2012

  41. [41]

    Tr´elat, Control in finite and infinite dimension , SpringerBriefs on PDEs and Data Sci- ence, Springer, Singapore, [2024] ©2024

    E. Tr´elat, Control in finite and infinite dimension , SpringerBriefs on PDEs and Data Sci- ence, Springer, Singapore, [2024] ©2024. 33

    work page 2024