scipy.optimize.minimize精度

Question

我试图计算函数的最小点

f(x)=(x-2e-17)*(x-2e-17)

用scipy.optimize.minimize。预期的，精确的结果是2e-17。但是，无论我如何微调容差参数xtol和ftol of scipy.optimize.minimize，它仍然只给出了不精确的结果0 (见下文)。我们怎么能让scipy返回精确的答案呢？谢谢。

In [35]: scipy.optimize.minimize(lambda x: (x-2e-17)**2,2,method='Powell',options={'xtol': 1e-30, 'ftol': 1e-30})
Out[35]:
  status: 0
 success: True
   direc: array([[ 1.]])
    nfev: 20
     fun: array(4.0000000000000006e-34)
       x: array(0.0)
 message: 'Optimization terminated successfully.'
     nit: 2

Answer 1

我理解你的技术问题，但在我看来，这是因为不恰当地使用优化器。在回答你提出的问题之前，我会先谈几句哲学上的废话。

具有有用答案的典型“优化问题”的最优函数值在几个数量级(即远小于17个)数量级内，在坐标都在几个数量级为1的点上达到。(或最优值为零，或某些最优坐标为零。)但在这种情况下，用户仍然满足于非常小的目标值和坐标。)

通常情况下，提供给黑匣子优化器的目标函数(以及它们的梯度，也提供给一些黑匣子优化器)编写得不够仔细。在优化器附近，f的计算梯度受舍入误差的控制。梯度甚至可能偏离最优值。如果黑盒子优化器总是执行长度为0的步骤，或者在接近最优值时出现错误，那么它的用处就大大降低了，因此参数的名称为"ftol“和"gtol”，默认值非常宽松，比如1e-4。

即使在理想的情况下，用户提供的函数总是在x上返回最接近f(x)的浮点数，而另一个函数总是在x返回正确的四舍五入的梯度到f at x，试图找到使f最小化的浮点向量是一个非常难看的离散优化问题。(NP，如果内存正常的话)如果f是以正确的四舍五入的方式进行的二次评估--这是我能想象到的最重要的情况--当你开始在1e-8周围采取长度相当长的步骤时，丑陋的离散行为开始压倒良好的连续行为。

基于线搜索的方法会发现自己在整个t of f(x + td)上计算出某个点x和某个方向d的最小值。考虑一下浮点算法中的f(x + td)是什么；对于某些t，您可以以某种方式计算x+td，最好是得到离x+td最近的浮点向量，然后将其插入f。一般来说，这条线搜索将沿着一条锯齿状的线计算f，通过x沿着d方向蜿蜒而行。即使f行为良好，并且实现得很好，行搜索也可以在很小的范围内发现非常糟糕的行为。因此，参数具有像xtol这样的名称，用于说明何时停止行搜索。

很多方法--除了直接牛顿法之外，我能想到的几乎所有东西--都需要对你的问题进行一些猜测，知道什么尺度是合理的，这样才能开始。(BFGS通常以恒等矩阵作为初始猜测。我认为迈出了第一步。梯度下降法通常首先尝试固定倍数的梯度。信任区域方法使用信任区域，这些区域必须从一定的半径开始。如果你在做数值微分，你的步长需要足够大，这样你才能捕捉到“连续”行为，而不是函数的“离散”行为，但是足够小，以至于你能捕捉到它的精细行为，而不是接近你点的粗劣行为。)

在这里，你在优化一个函数，它的最优值是零，非常接近于零。从理论上讲，我上面没有说过问题是可怕的，而它们的子问题是可怕的，需要加以应用。但是，你真的期望解的函数有一个特例，它的最优值是零，非常接近于零？特别是当这是额外的代码(很可能)降低了健壮性？为什么不直接给解决者一个规模很大的问题呢？

为了回答你的直接问题，鲍威尔在枕中的方法称为布伦特的线搜索，从坐标方向开始。布伦特的线搜索，正如在scipy中实现的，无论你用一个添加剂1e-11来喂养它，它都能提高它的容忍度。如果你黑了scipy.optimize，让Brent的_mintol变成1e-111，我敢打赌你会得到想要的答案。(_mintol是x中的一种绝对容忍，它被添加到您指定的相对公差中。在这里，行搜索不会浪费函数的评估，决定是由1e-200还是1e-201来进行，而这两种情况都可能没有结果。所以不要实际这么做。)

Answer 2

从输出中可以看到，在发现点处的函数值为4.0000000000000006e-34，这比ftol=1e-30小得多。

试着把ftol往下推，例如1e-37。这应该能解决这个问题。

或者，您可以尝试缩放您的函数，例如，不要使用(x-2e-17)**2，而是尝试使用函数1e+34 * (x-2e-17)**2。这两个函数在同一点上有它们的最小值。

Answer 3

尝试更改使用的method，例如使用“Nelder”：

res = scipy.optimize.minimize(lambda x: (x-2e-17)**2,2,method='Nelder-Mead',options={'xtol': 1e-30, 'ftol': 1e-30})
print(res.x)

打印所需的结果：[2.e-17]

看来，这些类型的精度问题似乎与最小化的方法有很大关系。