Updates

One of the most central objects in SimpleSolvers are update! routines. They can be used together with many different types and structs:

So update! always takes an object that has to be updated and a single vector in the simplest case. For some methods more arguments need to be provided.

Examples

`Hessian`

If we look at the case of the Hessian, we store a matrix $H$ that has to be updated in every iteration. We first initialize the matrix^[1]:

f = x -> sum(x .^ 3 / 6 + x .^ 2 / 2)
x = [1., 0., 0.]
hes = HessianAutodiff(f, x)
hes.H

3×3 Matrix{Float64}:
 NaN  NaN  NaN
 NaN  NaN  NaN
 NaN  NaN  NaN

And then update:

update!(hes, x)

hes.H

3×3 Matrix{Float64}:
 2.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0

`NewtonOptimizerCache`

In order to update an instance of SimpleSolvers.NewtonOptimizerCache we have to supply a value of the Gradient and the Hessian in addition to x:

grad = GradientAutodiff(f, x)
cache = NewtonOptimizerCache(x)
state = NewtonOptimizerState(x)
update!(cache, state, grad, hes, x)

SimpleSolvers.NewtonOptimizerCache{Float64, Vector{Float64}}([1.0, 0.0, 0.0], [-0.75, -0.0, -0.0], [1.5, 0.0, 0.0], [-1.5, -0.0, -0.0], [1.97430488437535e-310, 2.2578035216463e-311, 0.0], [6.9394987803345e-310, 6.9394987803361e-310, 6.9394987803377e-310])

Info

We note that when calling update! on the NewtonOptimizerCache, the Hessian hes is not automatically updated! This has to be done manually.

Info

Calling update! on the NewtonOptimizerCache updates everything except x as this in general requires another line search!

Info

When updating the cache we also need to supply the state. This is needed for the direction.

NewtonOptimizerCache, OptimizerResult and NewtonOptimizerState (through OptimizerProblem) all store things that are somewhat similar, for example x. This may make it somewhat difficult to keep track of all the things that happen during optimization.

An Optimizer stores a OptimizerProblem, an SimpleSolvers.OptimizerResult and an OptimizerState (and therefore the OptimizerProblem again). We also give an example:

obj = OptimizerProblem(f, x)
opt = Optimizer(x, obj)

update!(opt, state, x)

Optimizer{Float64, BFGS, OptimizerProblem{Float64, Vector{Float64}, Main.var"#2#3", Missing, Float64, Vector{Float64}}, 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}}}}, HessianBFGS{Float64, Vector{Float64}, Matrix{Float64}, OptimizerProblem{Float64, Vector{Float64}, Main.var"#2#3", Missing, Float64, Vector{Float64}}}, SimpleSolvers.NewtonOptimizerCache{Float64, Vector{Float64}}, SimpleSolvers.BacktrackingState{Float64}}(BFGS, OptimizerProblem (for vector-valued quantities only the first component is printed):

    f(x)              = 6.67e-01 
    g(x)₁             = 1.50e+00 
    x_f₁              = 1.00e+00 
    x_g₁              = 1.00e+00 
, 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}}(1.0,1.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,1.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,1.0)])), HessianBFGS{Float64, Vector{Float64}, Matrix{Float64}, OptimizerProblem{Float64, Vector{Float64}, Main.var"#2#3", Missing, Float64, Vector{Float64}}}(OptimizerProblem (for vector-valued quantities only the first component is printed):

    f(x)              = 6.67e-01 
    g(x)₁             = 1.50e+00 
    x_f₁              = 1.00e+00 
    x_g₁              = 1.00e+00 
, [0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 0.0, 0.0], [1.5, 0.0, 0.0], [1.5, 0.0, 0.0], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [1.5 0.0 0.0; 0.0 0.0 0.0; 0.0 0.0 0.0], [1.0 0.0 0.0; 0.0 0.0 0.0; 0.0 0.0 0.0]),                 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}}([1.0, 0.0, 0.0], [0.0, 0.0, 0.0], [1.5, 0.0, 0.0], [-1.5, -0.0, -0.0], [6.0e-323, 6.4e-323, 6.9395310259799e-310], [7.0e-323, 8.0e-323, 6.9394183809229e-310]), Backtracking with α₀ = 1.0, ϵ = 0.0001and p = 0.5., 1)

Equivalent to calling update! on SimpleSolvers.OptimizerResult, the diagnostics cannot be computed with only one iterations; we have to compute a second one:

x₂ = [.9, 0., 0.]
update!(opt, state, x₂)

Optimizer{Float64, BFGS, OptimizerProblem{Float64, Vector{Float64}, Main.var"#2#3", Missing, Float64, Vector{Float64}}, 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}}}}, HessianBFGS{Float64, Vector{Float64}, Matrix{Float64}, OptimizerProblem{Float64, Vector{Float64}, Main.var"#2#3", Missing, Float64, Vector{Float64}}}, SimpleSolvers.NewtonOptimizerCache{Float64, Vector{Float64}}, SimpleSolvers.BacktrackingState{Float64}}(BFGS, OptimizerProblem (for vector-valued quantities only the first component is printed):

    f(x)              = 5.27e-01 
    g(x)₁             = 1.31e+00 
    x_f₁              = 9.00e-01 
    x_g₁              = 9.00e-01 
, 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.9,1.0,0.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,1.0,0.0), Dual{ForwardDiff.Tag{Main.var"#2#3", Float64}}(0.0,0.0,0.0,1.0)])), HessianBFGS{Float64, Vector{Float64}, Matrix{Float64}, OptimizerProblem{Float64, Vector{Float64}, Main.var"#2#3", Missing, Float64, Vector{Float64}}}(OptimizerProblem (for vector-valued quantities only the first component is printed):

    f(x)              = 5.27e-01 
    g(x)₁             = 1.31e+00 
    x_f₁              = 9.00e-01 
    x_g₁              = 9.00e-01 
, [1.0, 0.0, 0.0], [0.9, 0.0, 0.0], [-0.09999999999999998, 0.0, 0.0], [1.5, 0.0, 0.0], [1.3050000000000002, 0.0, 0.0], [-0.19499999999999984, 0.0, 0.0], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [NaN NaN NaN; NaN NaN NaN; NaN NaN NaN], [0.01949999999999998 -0.0 -0.0; -0.0 0.0 0.0; -0.0 0.0 0.0], [0.009999999999999995 -0.0 -0.0; -0.0 0.0 0.0; -0.0 0.0 0.0]),                 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}}([0.9, 0.0, 0.0], [-0.09999999999999998, 0.0, 0.0], [1.3050000000000002, 0.0, 0.0], [-1.3050000000000002, -0.0, -0.0], [6.0e-323, 6.4e-323, 6.9395310259799e-310], [7.0e-323, 8.0e-323, 6.9394183809229e-310]), Backtracking with α₀ = 1.0, ϵ = 0.0001and p = 0.5., 1)

We note that simply calling update! on an instance of SimpleSolvers.Optimizer is not enough to perform a complete iteration since the computation of a new $x$ requires a line search procedure in general.

We also note that update! always returns the first input argument.

1The constructor uses the function SimpleSolvers.initialize!.