Неожиданное поведение ftol_abs и ftol_rel в NLopt

Question

ОБНОВЛЕНИЕ: Для любого другого, кто посещает эту страницу, стоит взглянуть на этот SO вопрос и ответить, так как я подозреваю, что решение там имеет отношение к проблеме, с которой я столкнулся здесь.

Этот вопрос дублирует один вопрос, который я задал в списке рассылки julia-users, но я не получил ответа (правда, это было только 4 дня), поэтому подумал, что я задам его здесь.

Я звоню в NLopt API от Джулии, хотя думаю, что мой вопрос не зависит от языка Джулии.

Я пытаюсь решить проблему оптимизации, используя COBYLA, но во многих случаях мне не удается вызвать критерии остановки. Моя проблема достаточно сложна, но я могу воспроизвести проблемное поведение на более простом примере.

Конкретно я стараюсь минимизировать x1^2 + x2^2 + 1 используя COBYLA, и я установил оба ftol_rel а также ftol_abs в 0.5, Моя целевая функция включает в себя инструкцию для вывода текущего значения на консоль, чтобы я мог наблюдать за конвергенцией. Последние пять значений, выводимых на консоль во время конвергенции:

1.161
1.074
1.004
1.017
1.038

Насколько я понимаю, любой из этих шагов должен был инициировать критерии остановки. Все шаги меньше чем 0.5так что должно срабатывать ftol_abs, Далее, каждое значение примерно 1, а также 0.5*1 = 0.5поэтому все шаги также должны были сработать ftol_rel, Фактически, это поведение верно для последних 8 шагов в процедуре сходимости.

NLopt существует уже некоторое время, поэтому я предполагаю, что проблема заключается в моем понимании того, как ftol_abs а также ftol_rel работать, а не быть ошибкой.

Кто-нибудь может пролить свет на то, почему критерии остановки не запускаются намного раньше?

Если это пригодится, следующий фрагмент кода Джулии может быть использован для воспроизведения всего, что я только что сказал:

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 должны предоставлять численно гарантированные ошибки. Более ранние значения достаточно близки, но алгоритм может не гарантировать этого. Например, градиент или гессиан в точке оценки могут предоставить такую ​​числовую гарантию. Итак, это продолжается немного дальше.

Безусловно, лучше всего взглянуть на источник алгоритма оптимизации. Если мне это удастся, я добавлю это к этому ответу.

Обновление: алгоритм COBYLA аппроксимирует градиент (производную вектора) численно, используя несколько точек оценки. Как уже упоминалось, это используется для моделирования, что может быть ошибка. Ошибки действительно могут быть математически гарантированы только для функций, ограниченных некоторым хорошим семейством (например, многочленами с некоторой степенью привязки).

Отнеси домой сообщение: все в порядке. Не ошибка, но лучшее, что может сделать алгоритм. Позвольте этому иметь те дополнительные итерации.