标题： 用于计算紧致域上莫尔斯函数的所有局部极小值点的概率算法 显示英文标题

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

摘要： 设 K 为 Rn 中的单位立方体，f : K $\rightarrow$ R^n 为一个莫尔斯函数。 我们假设函数 f 是由一个评估程序$\Gamma$在噪声模型中给出，即评估程序$\Gamma$会多接受一个参数$\eta$作为输入，并返回一个与 f 的真实值$\eta$接近的近似值。 在本文中，我们设计了一个算法，能够计算 f 在 K 上的所有局部极小值点。 我们的算法输入为$\Gamma$, $\eta$, 一个数值精度参数$\epsilon$以及一些明确的正则性参数。 在概率性假设下——与用于馈入$\Gamma$的评估点的选择有关——, 它返回有限多个 K 中的有理点，使得以这些点为中心、半径为$\epsilon$的球的集合包含并分离 f 的所有局部极小值点的集合。 我们的方法基于逼近理论，为 f 提供多项式逼近，结合计算机代数技术求解多项式方程组。 当所有正则性参数已知时，我们提供了该算法的位复杂度估计。 实际实验表明，我们在 Julia 包 Globtim 中对该算法的实现可以处理以前无法解决的示例。 显示英文摘要

摘要： 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.