SimulatedAnnealing (and SAMIN) claims "Status Failure", but output seems to be OK?

Specific Domains Optimization (Mathematical)
1

I am trying to get SimulatedAnnealing to work for an optimisation problem, so I first look at a basic example.

using Optim
f(x) = (1.0 - x[1])^2 + 100.0 * (x[2] - x[1]^2)^2

This works fine:

x0 = [0.0,0.0]
res = optimize(f, x0, NelderMead())

and the output claims success:

 * Status: success

 * Candidate solution
    Final objective value:     3.525527e-09

 * Found with
    Algorithm:     Nelder-Mead

 * Convergence measures
    √(Σ(yᵢ-ȳ)²)/n ≤ 1.0e-08

 * Work counters
    Seconds run:   0  (vs limit Inf)
    Iterations:    60
    f(x) calls:    117

Next, I try using SimulatedAnnealing (with boundaries):

x0 = [0.0,0.0]
lb = [-100.0, -100.0]
ub = [100.0, 100.0]
res = optimize(f, lb, ub, x0, SAMIN(), Optim.Options(iterations=10^6))

the output claims that this was a failure (Status: failure):

================================================================================
SAMIN results
==> Normal convergence <==
total number of objective function evaluations: 23101

     Obj. value:      0.0000000000

       parameter      search width
         1.00000           0.00000 
         1.00000           0.00000 
================================================================================

 * Status: failure

 * Candidate solution
    Final objective value:     3.005018e-17

 * Found with
    Algorithm:     SAMIN

 * Convergence measures
    |x - x'|               = NaN ≰ 0.0e+00
    |x - x'|/|x'|          = NaN ≰ 0.0e+00
    |f(x) - f(x')|         = NaN ≰ 0.0e+00
    |f(x) - f(x')|/|f(x')| = NaN ≰ 0.0e+00
    |g(x)|                 = NaN ≰ 0.0e+00

 * Work counters
    Seconds run:   1  (vs limit Inf)
    Iterations:    23101
    f(x) calls:    23101
    ∇f(x) calls:   0

however, the minimizer is still good, with res.minimizer = [0.9999999587029669, 0.9999999176131619].

Finally, I try normal SimulatedAnnealing:

x0 = [0.0,0.0]
res = optimize(f, x0, SimulatedAnnealing(), Optim.Options(iterations=10^6))

again the output claims failure, and this time gives a reason; (reached maximum number of iterations). Again, the minimizer is actually good (= [0.9999999587029669, 0.9999999176131619]).

What is going on here? This seems like a simple problem (I tried to use this one: Optim.jl). Also, why is it claiming failure while the result seems to be good, am I missing something?

1 Like
2

You are correct, running the example from the documentation at https://github.com/JuliaNLSolvers/Optim.jl/blob/master/docs/src/algo/samin.md

using Optim, OptimTestProblems

prob = UnconstrainedProblems.examples["Rosenbrock"];
res = Optim.optimize(prob.f, fill(-100.0, 2), fill(100.0, 2), prob.initial_x, SAMIN(), Optim.Options(iterations=10^6))
println(res)

I also see

================================================================================
SAMIN results
==> Normal convergence <==
total number of objective function evaluations: 22451

     Obj. value:      0.0000000000

       parameter      search width
         1.00000           0.00000 
         1.00000           0.00000 
================================================================================

 * Status: failure

 * Candidate solution
    Final objective value:     1.178874e-15

 * Found with
    Algorithm:     SAMIN

 * Convergence measures
    |x - x'|               = NaN ≰ 0.0e+00
    |x - x'|/|x'|          = NaN ≰ 0.0e+00
    |f(x) - f(x')|         = NaN ≰ 0.0e+00
    |f(x) - f(x')|/|f(x')| = NaN ≰ 0.0e+00
    |g(x)|                 = NaN ≰ 0.0e+00

 * Work counters
    Seconds run:   1  (vs limit Inf)
    Iterations:    22451
    f(x) calls:    22451
    ∇f(x) calls:   0

Furthermore the documentation and current reporting differ and in the documentation I miss the status information signalling success or failure.

3

This seems to be a problem of SAMIN not fitting into Optim’s general scheme for checking convergence. SAMIN does not use gradients, so the gradient check failing may be normal, as SAMIN does not compute or return a gradient. However, its internal convergence criteria do require that the change in the parameter vector and the change in the function value lie within tolerances (either default or user provided). The source code has the lines

            # last value close enough to last neps values?
            fstar[1] = f_old
            test = 0
            for i=1:neps
                test += (abs(f_old - fstar[i]) > f_tol)
            end
            test = (test > 0) # if different from zero, function conv. has failed
            # last value close enough to overall best?
            if (((fopt - f_old) <= f_tol) && (!test))
                # check for bound narrow enough for parameter convergence
                for i = 1:n
                    if (bounds[i] > x_tol)
                        converge = 0 # no conv. if bounds too wide
                        break
                    else
                        converge = 1
                    end
                end
            end

which check for convergence. So, I think that the problem is that SAMIN’s output must not be providing enough information to allow Optim’s general method of checking convergence to work properly.

However, SAMIN has converged to a point inside the bounds if you see

==> Normal convergence <==

The only remaining concern is that the temperature reduction (rt) may be too low, which could cause SAMIN to skip over local minima which may be better than the one that is reported. If in doubt, set rt to a number closer to but less than 1.0. This will increase the time spent, but is safer for irregular objective functions.

1 Like
4

Thanks,

I am looking at simply using SAMIN now, and ignoring that part of the output message.