search

madsjulia / Mads.jl

MADS: Model Analysis & Decision Support
http://mads.gitlab.io
GNU General Public License v3.0
101 stars 20 forks source link

Mads.levenberg_marquardt not finding optimum, even for Rosenbrock example, could it be that different settings are needed? #51

Closed donboyd5 closed 10 months ago

donboyd5 commented 2 years ago

Hi. Thank you for this amazing software.

This post is background information; the next post has reproducible code and results.

I am hoping you might advise on settings or other adjustments to resolve the problem I describe below.

I am not an optimization expert. I am seeking to minimize, in Julia, the sum of squared residuals for a relatively large problem (1,000 residuals based on 1,000 parameters plus external data). Every residual depends on every parameter (I guess this means the jacobian is completely dense). It is not practical to compute the jacobian analytically but autodifferentiation works well. LsqFit.lmfit works reasonably well on this problem but is slow. After extensive search, I found Mads. Surprisingly, there doesn't seem to be much mention of it in various Julia discussions.

As far as I can tell, Mads installed properly (latest release, and current master) although there was one seemingly small warning when I first imported Mads and one error when running Mads.test() - I'll copy the messages into the 2nd post below.

I found Mads.levenberg_marquardt to be amazingly fast on test versions of my problem but when I used my more challenging actual problems I noticed that it was not finding the optimum value that LsqFit.lmfit was finding.

I adjusted many parameters but found that it was almost always stopping after 3 iterations no matter what I did.

Then I reran Mads.levenberg_marquardt successively with starting values from the prior run and found that the objective function improved with each successive run, but it still would run for only 3 iterations each time.

After much head-scratching, I tried the same thing with a Rosenbrock example, and found it to happen with that, too - see next post.

donboyd5 commented 2 years ago

Minimal reproducible example:

Setup -- I could not get show_trace to work so I used a callback function:

import Mads

function callback(x_best::AbstractVector, of::Number, lambda::Number)
  global callbacksucceeded
  callbacksucceeded = true
  # println("The callback function was called: $x_best, $of, $lambda")
  println(of, " ", lambda)
end

ndim = 200

Here are the results of the initial run with arguments from an online example (plus callback). It stopped after 5 iterations, finding a minimum of 194.209:

results = Mads.levenberg_marquardt(Mads.makerosenbrock(ndim), Mads.makerosenbrock_gradient(ndim), zeros(ndim),
  lambda_mu=2.0, np_lambda=10, show_trace=true, maxJacobians=1000, callbackiteration=callback)

199.0 NaN
198.23585672156162 1.616
196.02336056127456 3.232
195.53487943980062 3.232
194.87083365351668 1.616
194.20908763543298 1.616
OptimBase.MultivariateOptimizationResults{LsqFit.LevenbergMarquardt, Float64, 1}(LsqFit.LevenbergMarquardt(), [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [0.8354459560429608, 0.6914560478488004, 0.45997878568603756, 0.18070529280425973, 0.026133524627512415, 0.010552791398802898, 0.010215197855675854, 0.010208551538302487, 0.010208420950213442, 0.010208418384502472  …  0.010208418333082964, 0.010208418333082645, 0.01020841833306728, 0.010208418332321646, 0.010208418296146864, 0.010208416541523314, 0.01020833145115144, 0.01020420555056359, 0.010004084362008978, 0.00010008148412392112], 194.20908763543298, 5, true, false, 0.0001, 0.0, false, 0.001, 0.0, false, 1.0e-6, 0.0, false, Iter     Function value   Gradient norm
------   --------------   --------------
, 1051, 5, 0)

Next, rerunning with initial values set to the minimizer above brings the found optimum down to 191.6:

results = Mads.levenberg_marquardt(Mads.makerosenbrock(ndim), Mads.makerosenbrock_gradient(ndim), results.minimizer,
         lambda_mu=2.0, np_lambda=10, show_trace=false, maxJacobians=1000, callbackiteration=callback)
194.20908763543298 NaN
193.59386062313567 2.3379566915413843
193.08554483140267 2.3379566915413843
192.58941336193575 2.3379566915413843
192.09289137376737 2.3379566915413843
191.5973596471983 2.3379566915413843
OptimBase.MultivariateOptimizationResults{LsqFit.LevenbergMarquardt, Float64, 1}(LsqFit.LevenbergMarquardt(), [0.8354459560429608, 0.6914560478488004, 0.45997878568603756, 0.18070529280425973, 0.026133524627512415, 0.010552791398802898, 0.010215197855675854, 0.010208551538302487, 0.010208420950213442, 0.010208418384502472  …  0.010208418333082964, 0.010208418333082645, 0.01020841833306728, 0.010208418332321646, 0.010208418296146864, 0.010208416541523314, 0.01020833145115144, 0.01020420555056359, 0.010004084362008978, 0.00010008148412392112], [0.9672626705833888, 0.9355746234725513, 0.875032976171471, 0.7642386844976807, 0.5789582894082582, 0.32372635302649344, 0.09542746097178234, 0.015550140848797377, 0.010319742254332553, 0.01021059600578051  …  0.010208423834357183, 0.010208423834356866, 0.010208423834341458, 0.010208423833594406, 0.010208423797378192, 0.010208422041654367, 0.010208336925996644, 0.010204210572704937, 0.010004085062783958, 0.00010008171794335949], 191.5973596471983, 5, true, false, 0.0001, 0.0, false, 0.001, 0.0, false, 1.0e-6, 0.0, false, Iter     Function value   Gradient norm
------   --------------   --------------
, 1051, 5, 0)

Additional runs using most-recent minimizer show continued improvement.

Changing tolerances does not seem to lead to success in a single run, but I am not sure I know how to set tolerances properly:

results = Mads.levenberg_marquardt(Mads.makerosenbrock(ndim), Mads.makerosenbrock_gradient(ndim), zeros(ndim),
         tolOF=1e-99, tolX=1e-99, tolG=1e-99,
         lambda_mu=2.0, np_lambda=10, show_trace=false, maxJacobians=1000, callbackiteration=callback)
199.0 NaN
198.23585672156162 1.616
196.02336056127456 3.232
195.53487943980062 3.232
194.87083365351668 1.616
194.20908763543298 1.616
OptimBase.MultivariateOptimizationResults{LsqFit.LevenbergMarquardt, Float64, 1}(LsqFit.LevenbergMarquardt(), [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [0.8354459560429608, 0.6914560478488004, 0.45997878568603756, 0.18070529280425973, 0.026133524627512415, 0.010552791398802898, 0.010215197855675854, 0.010208551538302487, 0.010208420950213442, 0.010208418384502472  …  0.010208418333082964, 0.010208418333082645, 0.01020841833306728, 0.010208418332321646, 0.010208418296146864, 0.010208416541523314, 0.01020833145115144, 0.01020420555056359, 0.010004084362008978, 0.00010008148412392112], 194.20908763543298, 5, true, false, 1.0e-99, 0.0, false, 1.0e-99, 0.0, false, 1.0e-99, 0.0, false, Iter     Function value   Gradient norm
------   --------------   --------------
, 1051, 5, 0)

I apologize if I am missing something simple. I would much appreciate any advice on settings or other adjustments that would lead Mads.levenberg_marquardt to achieve success in single run.

Thanks!

donboyd5 commented 2 years ago

Here is the warning I saw when I first imported Mads:

(process:45304): GLib-GIO-WARNING **: 08:14:53.323: Unexpectedly, UWP app `Clipchamp.Clipchamp_2.3.2.0_neutral__yxz26nhyzhsrt' (AUMId `Clipchamp.Clipchamp_yxz26nhyzhsrt!App') supports 46 extensions but has no verbs

Here is the error I saw when running Mads.test(). It seems to be related to plotting and not a source of the problem I am running into, but I am not sure.

# ERROR: LoadError: MethodError: no method matching layer(::Vector{Gadfly.Geom.LineGeometry}, ::Vector{Gadfly.Geom.LineGeometry}, ::Vector{Gadfly.Geom.LineGeometry}, ::Vector{Gadfly.Geom.LineGeometry}, ::Vector{Gadfly.Geom.LineGeometry}; x=1:4, y=[0.9724953537852915, 0.955955284443903, 0.9008697445870358, 0.6321582462815516])
# Closest candidates are:
#   layer(::Any, ::Union{Function, Gadfly.Element, Gadfly.Theme, Type}...; mapping...) at C:\Users\donbo\.julia\packages\Gadfly\B5yQc\src\Gadfly.jl:169
# Stacktrace:
#  [1] plotseries(X::Matrix{Float64}, filename::String; nT::Int64, nS::Int64, format::String, xtitle::String, ytitle::String, title::String, logx::Bool, logy::Bool, keytitle::String, name::String, names::Vector{String}, combined::Bool, hsize::Measures.AbsoluteLength, vsize::Measures.AbsoluteLength, linewidth::Measures.AbsoluteLength, linestyle::Symbol, pointsize::Measures.AbsoluteLength, key_position::Symbol, major_label_font_size::Measures.AbsoluteLength, minor_label_font_size::Measures.AbsoluteLength, dpi::Int64, colors::Vector{String}, opacity::Float64, xmin::Nothing, xmax::Nothing, ymin::Nothing, ymax::Nothing, xaxis::UnitRange{Int64}, plotline::Bool, plotdots::Bool, firstred::Bool, lastred::Bool, nextgray::Bool, code::Bool,
#  returnplot::Bool, colorkey::Bool, background_color::Nothing, gm::Vector{Any}, gl::Vector{Any}, quiet::Bool, truth::Bool)
#    @ Mads C:\Users\donbo\.julia\packages\Mads\ZVE7t\src\MadsPlot.jl:1213
#  [2] top-level scope
#    @ C:\Users\donbo\.julia\packages\Mads\ZVE7t\test\miscellaneous.jl:174
# in expression starting at C:\Users\donbo\.julia\packages\Mads\ZVE7t\test\miscellaneous.jl:174
# in expression starting at C:\Users\donbo\.julia\packages\Mads\ZVE7t\test\runtests.jl:35
montyvesselinov commented 2 years ago

The new push resolves the plotting error above.

montyvesselinov commented 2 years ago

@donboyd5

in the examples above, the optimization was terminated early due to impose a limit on the number of evaluations. Try this:

results = Mads.levenberg_marquardt(Mads.makerosenbrock(ndim), Mads.makerosenbrock_gradient(ndim), results.minimizer, lambda_mu=0.1, np_lambda=10, show_trace=true, maxJacobians=10000, callbackiteration=callback, maxEval=1000000)
donboyd5 commented 2 years ago

Thanks! I don't know how I missed those arguments. It ran for 290 iterations and found a minimum (within tolerances). I am eager to try this out on some challenging problems I need to solve.

Meanwhile, the new version I used (github master -- v1.3.2) failed the blind_source_separation tests. I've copied the relevant terminal output into the next comment, FYI.

donboyd5 commented 2 years ago
montyvesselinov commented 10 months ago

now these issues are fixed.