Unexpected behavior of ftol_abs and ftol_rel in NLopt

Question

UPDATE: For everyone who visits this page, it’s worth taking a look at this question and answering it , since I suspect that the solution is related to the problem I had here.

This question duplicates the one I asked on the julia-users mailing list , but I didn’t get an answer there (admittedly, it was only 4 days), so I thought I'd ask here.

I call Julia's NLopt API, although I think my question is independent of Julia's language.

I am trying to solve the optimization problem with COBYLA, but in many cases I cannot call the stop criteria. My problem is quite complicated, but I can reproduce the problem with a simpler example.

In particular, I am trying 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 instructions for printing the current value on the console, so I can observe the convergence. The last five values ​​printed on the console during convergence are as follows:

 1.161 1.074 1.004 1.017 1.038 

I understand that any of these steps should have triggered the stopping criteria. All steps are less than 0.5 , so it should run ftol_abs . In addition, each value is approximately 1 and 0.5*1 = 0.5 , so all steps should also be triggered by ftol_rel . In fact, this behavior refers to the last 8 steps in the convergence procedure.

NLopt has been around for a while, so I assume the problem is in my understanding of how ftol_abs and ftol_rel , and not as an error.

Can someone shed some light on why stopping criteria don't work out much earlier?

If this is useful, the following snippet of Julia's code can be used to reproduce everything that I just said:

 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 and ftol_abs supposed to provide numerical errors . The early values ​​are close enough, but the algorithm may not be able to guarantee this. For example, a gradient or Hessian at the point of estimation may provide such a numerical guarantee. So it goes a little further.

Of course, it’s best to take a look at the source of the optimization algorithm. If I do this, I will add this to this answer.

Update: The COBYLA algorithm approximates the gradient (vector derivative) numerically using multiple evaluation points. As already mentioned, this is used to simulate what might be a mistake. Errors can really be mathematically guaranteed only for functions bounded by some nice family (for example, polynomials with some degree of degree).

Take home message: OK. Not a mistake, but a better algorithm. Let him have those extra iterations.