Large number of iterations

[mbaz]

I am trying to use SPGBox.jl in a simple problem, but the result is not very good and it takes too many iterations. To reproduce, first install the package SinusoidalRegressions.jl. Then,

using SPGBox, ReverseDiff, SinusoidalRegressions

t = range(0, 1, 40)
s = sin.(2π*0.43*t)
alg = IEEE1057()
prob(f) = Sin3Problem(t, s, f)
fun(f) = rmse(sinfit(prob(f[1]), alg), s, t)

Here, fun(f) is "U" shaped with a single minimum at f = 0.43:

Since I know that the minimum is in the range 1 < f < 0, I try to find the minimum as follows:

spgbox!(fun, (g,x) -> ReverseDiff.gradient!(g,fun,x), x0, lower=[0.], upper=[1.])

 SPGBOX RESULT:

 Maximum number of iterations (nitmax) reached.

 Final objective function value = 0.0003527270699352631
 Sample of best point = Vector{Float64}[ 0.42575202091224407]
 Projected gradient norm = 0.08250086313921057

 Number of iterations = 100
 Number of function evaluations = 390

It can be seen that the algorithm fails to converge, the minimum estimate (0.4257) is not very good, and that the number of function evaluations is too high. Other optimization algorithms I've tried can find the minimum in 5-6 iterations.

[pjssilva]

It seems that this function is not well suited for SPGBox for two reasons:

1. It is nondifferentiable (at the minimum). SPGBox assumes differentiability.

2. It looks like it is the maximum between a concave (to the left) and a convex function (to the right). In particular, the portion with negative curvature (the concave part) does not change curvature to become convex near the minimum. SPGBox is uses second order (curvature) information. In this case, whenever the current point is in the concave part near the optimum, the method will try to do a long step to exploit the negative curvature, moving away from the minimum.

I am afraid that there is nothing that can be done. SPGBox was not designed to minimize such a function.

[mbaz]

Thank you for explaining what is going on. I've made a pull request to add these assumptions to the documentation.

[lmiq]

This is a more extreme example, where the curvature is negative on both sides. I have added a parameter to control the step size when the curvature is negative (step_nc) which was fixed by default to 100. Decreasing it is not solving the problem, so I'll keep this issue open until we (if) we find a way for the method to deal better with this kind of situations.

Example:

julia> f(x) = sqrt(abs(x[1]))
f (generic function with 1 method)

julia> g!(g,x) = if x[1] <= 0 g[1] = -inv(2*sqrt(abs(x[1]))) else g[1] = inv(2*sqrt(x[1])) end
g! (generic function with 1 method)

julia> spgbox(f, g!, [0.3], lower=[-1.0], upper=[1.0], m=1, step_nc=1e-1)

 SPGBOX RESULT: 

 Maximum number of function evaluations (nfevalmax) reached.

 Final objective function value = 4.298219575868233e-17
 Sample of best point = Vector{Float64}[ 1.8474691522376893e-33]
 Projected gradient norm = 1.0

 Number of iterations = 59
 Number of function evaluations = 1001