scipy.optimize.minimize的精度

Question

我试图计算函数的最小点

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

与scipy.optimize.minimize.预期的,精确的结果是2e-17.但无论我怎么微调耐性的参数xtol和ftol的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

我理解您的技术问题,但在我看来,它源于对优化器的不恰当使用.在回答你提出的问题之前,我会沉迷于一些哲学上的谣言.

具有有用答案的"典型"优化问题具有在坐标均在1的几个数量级内的点处获得的几个(即,基本上少于17个)数量级1的最佳函数值.(或最优值为零,或者某些最佳坐标为零.但在这种情况下,用户通常仍然对非常小的目标值和坐标感到满意.)

通常,用于黑盒优化器的目标函数(以及它们的渐变,也用于某些黑盒优化器)并没有特别仔细地编写.在优化器附近,f的计算梯度将由舍入误差支配.梯度甚至可以指向最佳点.如果一个黑盒优化器永远循环使用长度为0的步骤,或者当它非常接近最佳值时出现错误,那么黑盒优化器就没那么有用了,因此参数的名称如"ftol"和"gtol"具有相当宽松的默认值如1e-4.

即使在理想情况下,用户提供的函数总是以x最接近的浮点数返回,f(x)而另一个函数总是以x正确舍入的渐变返回到fat x,尝试找到最小化的浮点向量f是a非常丑陋的离散优化问题.(NP-hard,如果内存服务的话.)如果f是一个以正确的方式评估的大规模二次方 - 关于我可以想象的最好的非常重要的情况 - 丑陋的离散行为开始压倒你的漂亮的连续行为开始采取长度的步骤1e-8.

根据线搜索方法会发现自己在计算最低在所有t的f(x + td)一些点x和一些方向d.考虑f(x + td)浮点运算中的内容; 对某些人来说t,你x+td以某种方式进行计算,最好将浮点向量最接近x+td,然后将其插入f.一般来说,这种线搜索将通过f沿着x方向的蜿蜒沿着锯齿状线进行评估d.即使f行为良好并且实施得很好,行搜索也可以很好地发现非常糟糕的行为.因此,具有这样的名称的参数xtol表示何时停止线搜索.

很多方法---除了牛顿的方法之外我几乎可以想到的所有方法 - 需要对你的问题的合理范围进行某种猜测才能启动.(BFGS通常将单位矩阵作为初始猜测.我认为L-BFGS的第一步采取单位步骤.梯度下降方法通常首先尝试梯度的固定倍数.信任区域方法使用信任区域,必须启动如果你正在进行数值微分,你的步长需要足够大,以至于你捕捉到"连续"行为而不是函数的"离散"行为,但是足够小以至于你正在捕获它良好的行为,而不是在你的观点附近的粗略行为.)

在这里,您正在优化一个最佳值为零的函数,该函数非常接近于零.从理论上讲,我上面所说的任何关于问题都很可怕而且他们的子问题很糟糕的事情都需要适用.但是你真的希望求解器有一个特殊情况,用于最优值为零,达到非常接近零的函数吗？特别是当(可能)降低稳健性的额外代码时？为什么不直接给求解器提供一个很好的问题呢？

要回答你的直接问题,鲍威尔的scipy方法称为布伦特的线搜索,从坐标方向开始.布伦特的线搜索,如scipy所实现的,通过添加剂来提高你所提供的任何公差1e-11.如果你砍scipy.optimize,这样Brent的_mintol是1e-111不是,我打赌你得到想要的答案.(_mintol是一个绝对容差,x它被添加到你指定的相对容差.它就在那里,因此行搜索不会浪费功能评估决定是否逐步1e-200或1e-201何时可能导致任何一个步骤都没有步骤.所以不要实际上那样做.)