Optimizers
An Optimizer stores an OptimizerState, a OptimizerProblem, the SimpleSolvers.OptimizerResult and a SimpleSolvers.NonlinearMethod. Its purposes are:
using SimpleSolvers
using LinearAlgebra: norm
x = rand(3)
obj = OptimizerProblem(x -> sum((x - [0., 0., 1.]) .^ 2), x)
bt = Backtracking()
alg = Newton()
opt = Optimizer(x, obj; algorithm = alg, linesearch = bt)Optimizer{Float64, Newton, OptimizerProblem{Float64, Main.var"#2#3", Missing, Missing}, GradientAutodiff{Float64, Main.var"#2#3", ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}, HessianAutodiff{Float64, Main.var"#2#3", ForwardDiff.HessianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}, SimpleSolvers.NewtonOptimizerCache{Float64, Vector{Float64}, Matrix{Float64}}, SimpleSolvers.BacktrackingState{Float64}}(Newton, OptimizerProblem{Float64, Main.var"#2#3", Missing, Missing}(Main.var"#2#3"(), missing, missing), GradientAutodiff{Float64, Main.var"#2#3", ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}(Main.var"#2#3"(), ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}((Partials(1.0, 0.0, 0.0), Partials(0.0, 1.0, 0.0), Partials(0.0, 0.0, 1.0)), ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}[Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(5.0e-324,4.243991582e-314,0.0,1.5e-323), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(8.487983164e-314,0.0,2.5e-323,1.2731974746e-313), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,3.5e-323,1.69759663277e-313,0.0)])), HessianAutodiff{Float64, Main.var"#2#3", ForwardDiff.HessianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}(Main.var"#2#3"(), ForwardDiff.HessianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}(ForwardDiff.JacobianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}((Partials(1.0, 0.0, 0.0), Partials(0.0, 1.0, 0.0), Partials(0.0, 0.0, 1.0)), ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}[Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0)]), ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}}((Partials(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0)), Partials(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0)), Partials(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.0,0.0,0.0,0.0))), ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}[Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.9282453064757e-310,6.92828435592397e-310,6.92824530647886e-310,6.92828435592397e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.928245306482e-310,6.92828435592397e-310,6.9282453064852e-310,6.92828435592397e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92824530648835e-310,6.92828435592397e-310,6.9282453064915e-310,6.92828435592397e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92824530649467e-310,6.92828435592397e-310,6.92824530649783e-310,6.92828435592397e-310)), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.928245306501e-310,6.92828435592397e-310,6.92824530650416e-310,6.92828435592397e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.9282453065073e-310,6.92828435592397e-310,6.9282453065105e-310,6.9282867697445e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.6e-322,6.92823214525147e-310,1.0e-323,4.4e-323),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.73e-322,2.8e-322,4.1e-322,5.2e-322)), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.27e-322,7.56e-322,8.65e-322,9.34e-322),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(9.73e-322,1.042e-321,1.08e-321,1.15e-321),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.21e-321,1.28e-321,1.32e-321,1.39e-321),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.43e-321,1.497e-321,1.537e-321,1.606e-321))]))), x_abstol = 4.440892098500626e-16
x_reltol = 4.440892098500626e-16
x_suctol = 4.440892098500626e-16
f_abstol = 0.0
f_reltol = 4.440892098500626e-16
f_suctol = 4.440892098500626e-16
f_mindec = 0.0001
g_restol = 1.4901161193847656e-8
x_abstol_break = Inf
x_reltol_break = Inf
f_abstol_break = Inf
f_reltol_break = Inf
g_restol_break = Inf
allow_f_increases = true
min_iterations = 0
max_iterations = 1000
warn_iterations = 1000
show_trace = false
store_trace = false
extended_trace = false
show_every = 1
verbosity = 1
, SimpleSolvers.NewtonOptimizerCache{Float64, Vector{Float64}, Matrix{Float64}}([NaN, NaN, NaN], [NaN, NaN, NaN], [NaN, NaN, NaN], [NaN, NaN, NaN], [5.4e-323, 6.9282796865483e-310, 0.0], [5.4e-323, 0.756286464275445, 5.0e-324], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN]), Backtracking with α₀ = 1.0, ϵ = 0.0001and p = 0.5., 1)Optimizer Constructor
Internally the constructor for Optimizer calls SimpleSolvers.OptimizerResult and SimpleSolvers.NewtonOptimizerState and Hessian. We can also allocate these objects manually and then call a different constructor for Optimizer:
using SimpleSolvers: NewtonOptimizerState, NewtonOptimizerCache, initialize!, LinesearchState
_cache = NewtonOptimizerCache(x)
hes = Hessian(alg, obj, x)
_linesearch = LinesearchState(Static(.1))
opt₂ = Optimizer(alg, obj, hes, _cache, _linesearch)Optimizer{Float64, Newton, OptimizerProblem{Float64, Main.var"#2#3", Missing, Missing}, GradientAutodiff{Float64, Main.var"#2#3", ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}, HessianAutodiff{Float64, Main.var"#2#3", ForwardDiff.HessianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}, SimpleSolvers.NewtonOptimizerCache{Float64, Vector{Float64}, Matrix{Float64}}, SimpleSolvers.StaticState{Float64}}(Newton, OptimizerProblem{Float64, Main.var"#2#3", Missing, Missing}(Main.var"#2#3"(), missing, missing), GradientAutodiff{Float64, Main.var"#2#3", ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}(Main.var"#2#3"(), ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}((Partials(1.0, 0.0, 0.0), Partials(0.0, 1.0, 0.0), Partials(0.0, 0.0, 1.0)), ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}[Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,6.9281040579225e-310)])), HessianAutodiff{Float64, Main.var"#2#3", ForwardDiff.HessianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}}(Main.var"#2#3"(), ForwardDiff.HessianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}(ForwardDiff.JacobianConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}}}((Partials(1.0, 0.0, 0.0), Partials(0.0, 1.0, 0.0), Partials(0.0, 0.0, 1.0)), ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}[Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(5.0e-324,4.243991582e-314,0.0,1.5e-323), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(8.487983164e-314,0.0,2.5e-323,1.2731974746e-313), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,3.5e-323,1.69759663277e-313,0.0)]), ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}}}((Partials(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0)), Partials(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0)), Partials(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.0,0.0,0.0,0.0))), ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}, Float64, 3}, 3}[Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92827725892155e-310,6.92827725892313e-310,6.9282772589247e-310,6.9282772624061e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92828635997913e-310,6.92827781756356e-310,6.9282772588931e-310,6.9282772590338e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.9282772589342e-310,6.9282772589358e-310,6.92827725893736e-310,6.92827725893894e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92827725894053e-310,6.9282772589421e-310,6.92827725857215e-310,2.298e-320)), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(1.9851e-319,6.92827725903855e-310,6.92827725904013e-310,6.9282772590417e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.9282772590433e-310,6.92827725904487e-310,6.92827725689233e-310,6.9282772588931e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.9282772590354e-310,6.9282772590354e-310,6.9282796820863e-310,6.9282772590496e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92827725904645e-310,6.9282772590512e-310,6.92827725903697e-310,5.0e-324)), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.9282772590528e-310,6.92827725905436e-310,6.92827725905594e-310,6.9282772590575e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.9282772590591e-310,6.9282772590607e-310,6.92827725904803e-310,6.92827725906226e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92827725906384e-310,6.92827725906543e-310,6.928277259067e-310,6.9282772590686e-310),Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(6.92827725907017e-310,6.92827725907175e-310,6.0e-323,4.0e-323))]))), x_abstol = 4.440892098500626e-16
x_reltol = 4.440892098500626e-16
x_suctol = 4.440892098500626e-16
f_abstol = 0.0
f_reltol = 4.440892098500626e-16
f_suctol = 4.440892098500626e-16
f_mindec = 0.0001
g_restol = 1.4901161193847656e-8
x_abstol_break = Inf
x_reltol_break = Inf
f_abstol_break = Inf
f_reltol_break = Inf
g_restol_break = Inf
allow_f_increases = true
min_iterations = 0
max_iterations = 1000
warn_iterations = 1000
show_trace = false
store_trace = false
extended_trace = false
show_every = 1
verbosity = 1
, SimpleSolvers.NewtonOptimizerCache{Float64, Vector{Float64}, Matrix{Float64}}([NaN, NaN, NaN], [NaN, NaN, NaN], [NaN, NaN, NaN], [NaN, NaN, NaN], [6.9281557735768e-310, 6.92815467499774e-310, 1.14e-322], [6.9281557735768e-310, 6.92815453740085e-310, 0.0], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN]), Static with α = 0.1., 1)If we want to solve the problem, we can call solve! on the Optimizer instance:
x₀ = copy(x)
state = NewtonOptimizerState(x)
solve!(x₀, state, opt)SimpleSolvers.OptimizerResult{Float64, Float64, Vector{Float64}, SimpleSolvers.OptimizerStatus{Float64, Float64}}(
* Convergence measures
|x - x'| = 7.92e-01
|x - x'|/|x'| = 7.92e-01
|f(x) - f(x')| = 0.00e+00
|f(x) - f(x')|/|f(x')| = NaN
|g(x) - g(x')| = 0.00e+00
|g(x)| = 0.00e+00
, [0.0, 0.0, 1.0], 0.0)Internally SimpleSolvers.solve! repeatedly calls SimpleSolvers.solver_step! until SimpleSolvers.meets_stopping_criteria is satisfied.
using SimpleSolvers: solver_step!
x = rand(3)
solver_step!(x, state, opt)3-element Vector{Float64}:
0.0
0.0
1.0The function SimpleSolvers.solver_step! in turn does the following:
# update problem, hessian, state and result
update!(opt, state, x)
# solve H δx = - ∇f
# rhs is -g
ldiv!(direction(opt), hessian(opt), rhs(opt))
# apply line search
α = linesearch(opt)(linesearch_problem(problem(opt), gradient(opt), cache(opt), state))
# compute new minimizer
x .= compute_new_iterate(x, α, direction(opt))
cache(opt).x .= xSolving the Line Search Problem with Backtracking
Calling an instance of SimpleSolvers.LinesearchState (in this case SimpleSolvers.BacktrackingState) on an SimpleSolvers.LinesearchProblem in turn does:
α *= ls.pas long as the SimpleSolvers.SufficientDecreaseCondition isn't satisfied. This condition checks the following:
fₖ₊₁ ≤ sdc.fₖ + sdc.c₁ * αₖ * sdc.pₖ' * sdc.gradₖsdc is first allocated as:
ls = linesearch(opt)
α = ls.α₀
x₀ = zero(α)
grad = GradientAutodiff{Float64}(problem(opt).F, length(x))
lso = linesearch_problem(problem(opt), grad, cache(opt), state)
y₀ = value(lso, x₀)
d₀ = derivative(lso, x₀)
sdc = SufficientDecreaseCondition(ls.ϵ, x₀, y₀, d₀, d₀, obj)SimpleSolvers.SufficientDecreaseCondition{Float64, Float64, Float64, OptimizerProblem{Float64, Main.var"#2#3", Missing, Missing}}(0.0001, 0.0, 0.6279134497792394, -0.9489304989415306, -0.9489304989415306, OptimizerProblem{Float64, Main.var"#2#3", Missing, Missing}(Main.var"#2#3"(), missing, missing))