NLopt中ftol_abs和ftol_rel的异常行为 [英] Unexpected behaviour of ftol_abs and ftol_rel in NLopt
问题描述
UPDATE: For anyone else who visits this page, it is worth having a look at this SO question and answer as I suspect the solution there is relevant to the problem I was having here.
此问题重复了我在 julia-users邮件中问过的问题列表，但是我还没有得到答复(诚然只有4天了)，所以我想在这里问.
This question duplicates one I have asked on the julia-users mailing list, but I haven't gotten a response there (admittedly it has only been 4 days), so thought I would ask here.
我正在从Julia调用NLopt API，尽管我认为我的问题与Julia语言无关.
I am calling the NLopt API from Julia, although I think my question is independent of the Julia language.
我正在尝试使用COBYLA解决优化问题，但是在许多情况下，我无法触发停止条件.我的问题相当复杂，但是我可以用一个更简单的示例来重现问题的行为.
I am trying to solve an optimisation problem using COBYLA but in many cases I am failing to trigger the stopping criteria. My problem is reasonably complicated, but I can reproduce the problem behaviour with a much simpler example.
具体来说，我尝试使用COBYLA最小化x1^2 + x2^2 + 1，并将ftol_rel和ftol_abs都设置为0.5.我的目标函数包括一条语句，用于将当前值打印到控制台，因此我可以观察收敛情况.收敛期间打印到控制台的最后五个值是:
Specifically, I try to minimize x1^2 + x2^2 + 1 using COBYLA, and I set both ftol_rel and ftol_abs to 0.5. My objective function includes a statement to print the current value to the console, so I can watch the convergence. The final five values printed to the console during convergence are:
1.161
1.074
1.004
1.017
1.038
我的理解是，这些步骤中的任何一个都应该触发停止条件.所有步骤均小于0.5，因此应触发ftol_abs.此外，每个值大约为1和0.5*1 = 0.5，因此所有步骤也应该触发了ftol_rel.实际上，这种行为在收敛例程的最后8个步骤中都是正确的.
My understanding is that any of these steps should have triggered the stopping criteria. All steps are less than 0.5, so that should trigger ftol_abs. Further, each value is approximately 1, and 0.5*1 = 0.5, so all steps should also have triggered ftol_rel. In fact, this behaviour is true of the last 8 steps in the convergence routine.
NLopt已经存在了一段时间，所以我猜问题出在我对ftol_abs和ftol_rel的工作方式的理解上，而不是一个错误.
NLopt has been around for a while, so I'm guessing the problem is with my understanding of how ftol_abs and ftol_rel work, rather than being a bug.
谁能阐明为什么没有更早触发停止标准?
Can anyone shed any light on why the stopping criteria are not being triggered much earlier?
如果有什么用，下面的Julia代码段可用于重现我刚才所说的一切:
If it is of any use, the following Julia code snippet can be used to reproduce everything I have just stated:
using NLopt
function objective_function(param::Vector{Float64}, grad::Vector{Float64})
obj_func_value = param[1]^2 + param[2]^2 + 1.0
println("Objective func value = " * string(obj_func_value))
println("Parameter value = " * string(param))
return(obj_func_value)
end
opt1 = Opt(:LN_COBYLA, 2)
lower_bounds!(opt1, [-10.0, -10.0])
upper_bounds!(opt1, [10.0, 10.0])
ftol_rel!(opt1, 0.5)
ftol_abs!(opt1, 0.5)
min_objective!(opt1, objective_function)
(fObjOpt, paramOpt, flag) = optimize(opt1, [9.0, 9.0])
推荐答案
假定ftol_rel和ftol_abs应该提供数字保证错误.较早的值足够接近，但是算法可能无法保证.例如，评估点处的梯度或Hessian可能会提供这样的数值保证.因此，它还会继续.
Presumably, ftol_rel and ftol_abs are supposed to supply numerically guaranteed errors. The earlier values are close enough but the algorithm might not be able to guarantee it. For example, the gradient or Hessian at the evaluation point might supply such a numerical guarantee. So, it continues a bit further.
可以肯定的是，最好查看优化算法的来源.如果可以解决，请将其添加到此答案中.
To be sure, it's best to look at the optimization algorithm source. If I manage this, I will add it to this answer.
更新:COBYLA算法使用多个评估点对梯度(矢量导数)进行数值逼近.如前所述，这用于对错误进行建模.仅对于限于某些良好族的函数(例如，度数受限制的多项式)，才能真正数学上保证错误.
Update: The COBYLA algorithm approximates the gradient (vector derivative) numerically using several evaluation points. As mentioned, this is used to model what the error might be. The errors can really be mathematically guaranteed only for functions restricted to some nice family (e.g. polynomials with some bound on degree).
带回家消息:可以.不是错误，而是算法可以做到的最好的错误.让它有那些额外的迭代.
Take home message: It's OK. Not a bug, but the best the algorithm can do. Let it have those extra iterations.
这篇关于NLopt中ftol_abs和ftol_rel的异常行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
