NLopt 中 ftol_abs 和 ftol_rel 的意外行为

Question

更新： 对于访问此页面的任何其他人，值得一看因为我怀疑那里的解决方案与我遇到的问题相关有这里

这个问题重复了我在 julia-users mailing list 上问过的一个问题，但我在那里没有得到答复（诚然只有 4 天），所以我想在这里问一下。

我正在从 Julia 调用 NLopt API，尽管我认为我的问题与 Julia 语言无关。

我正在尝试使用 COBYLA 解决优化问题，但在很多情况下我无法触发停止条件。我的问题相当复杂，但我可以用一个更简单的示例重现问题行为。

具体来说，我尝试使用 COBYLA 最小化 x1^2 + x2^2 + 1，并将 ftol_rel 和 ftol_abs 都设置为 0.5。我的 objective 函数包含一个将当前值打印到控制台的语句，因此我可以观察收敛情况。收敛期间打印到控制台的最后五个值是：

我的理解是这些步骤中的任何一个都应该触发停止标准。所有步骤都小于 0.5，因此应该触发 ftol_abs。此外，每个值大约为 1 和 0.5*1 = 0.5，因此所有步骤也应该触发 ftol_rel。事实上，收敛例程的最后 8 个步骤也是如此。

NLopt 已经存在了一段时间，所以我猜问题出在我对 ftol_abs 和 ftol_rel 工作原理的理解上，而不是一个错误。

谁能解释为什么没有更早触发停止条件？

如果有用，可以使用以下 Julia 代码片段来重现我刚才陈述的所有内容：

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])

Answer 1

据推测，ftol_rel 和 ftol_abs 应该提供 数值保证的 错误。较早的值足够接近，但算法可能无法保证。例如，评估点的梯度或 Hessian 矩阵可能会提供这样的数值保证。所以，它继续更进一步。

当然，最好看一下优化算法源码。如果我能解决这个问题，我会把它添加到这个答案中。

更新：COBYLA 算法使用几个评估点在数值上近似梯度（矢量导数）。如前所述，这用于模拟错误可能是什么。这些错误实际上可以 数学上保证 仅适用于仅限于某些不错的族的函数（例如，具有一定程度约束的多项式）。

带回家的信息：没关系。不是错误，而是算法可以做到的最好。让它有那些额外的迭代。

NLopt 中 ftol_abs 和 ftol_rel 的意外行为

Unexpected behaviour of ftol_abs and ftol_rel in NLopt

julia

nlopt