Optimizers

An Optimizer stores an OptimizationAlgorithm, a MultivariateObjective, the SimpleSolvers.OptimizerResult and a SimpleSolvers.NonlinearMethod. Its purposes are:

using SimpleSolvers
using LinearAlgebra: norm

x = rand(3)
obj = MultivariateObjective(x -> sum((x - [0., 0., 1.]) .^ 2), x)
bt = Backtracking()
alg = Newton()
opt = Optimizer(x, obj; algorithm = alg, linesearch = bt)

 * Algorithm: Newton 

 * Linesearch: Backtracking with α₀ = 1.0, ϵ = 0.0001and p = 0.5.

 * Iterations

    n = 0

 * Convergence measures

    |x - x'|               = NaN ≰ 4.4e-16
    |x - x'|/|x'|          = NaN ≰ 4.4e-16
    |f(x) - f(x')|         = NaN ≰ 0.0e+00
    |f(x) - f(x')|/|f(x')| = NaN ≰ 4.4e-16
    |g(x)|                 = NaN ≰ 1.5e-08

 * Candidate solution

    Final solution value:     [NaN, NaN, NaN]
    Final objective value:     NaN

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, OptimizerResult, initialize!

result = OptimizerResult(x, value!(obj, x))
initialize!(result, x)
state = NewtonOptimizerState(x; linesearch = bt)
hes = Hessian(alg, obj, x)
opt₂ = Optimizer(alg, obj, hes, result, state)

 * Algorithm: Newton 

 * Linesearch: Backtracking with α₀ = 1.0, ϵ = 0.0001and p = 0.5.

 * Iterations

    n = 0

 * Convergence measures

    |x - x'|               = NaN ≰ 4.4e-16
    |x - x'|/|x'|          = NaN ≰ 4.4e-16
    |f(x) - f(x')|         = NaN ≰ 0.0e+00
    |f(x) - f(x')|/|f(x')| = NaN ≰ 4.4e-16
    |g(x)|                 = NaN ≰ 1.5e-08

 * Candidate solution

    Final solution value:     [NaN, NaN, NaN]
    Final objective value:     NaN

If we want to solve the problem, we can call solve! on the Optimizer instance:

x₀ = copy(x)

solve!(opt, x₀)

3-element Vector{Float64}:
 0.0
 0.0
 1.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!(opt, x)

3-element Vector{Float64}:
 0.0
 0.0
 1.0

The function SimpleSolvers.solver_step! in turn does the following:

# update objective, hessian, state and result
update!(opt, x)
# solve H δx = - ∇f
ldiv!(direction(opt), hessian(opt), rhs(opt))
# apply line search
α = linesearch(state(opt))(linesearch_objective(objective(opt), cache(opt)))
# compute new minimizer
x .= compute_new_iterate(x, α, direction(opt))

Solving the Line Search Problem with Backtracking

Calling an instance of SimpleSolvers.LinesearchState (in this case SimpleSolvers.BacktrackingState) on an SimpleSolvers.AbstractUnivariateObjective in turn does:

α *= ls.p

as 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(α)
lso = linesearch_objective(objective(opt), cache(opt))
y₀ = value!(lso, x₀)
d₀ = derivative!(lso, x₀)

sdc = SufficientDecreaseCondition(ls.ϵ, x₀, y₀, d₀, d₀, obj)

SimpleSolvers.SufficientDecreaseCondition{Float64, Float64, Float64, MultivariateObjective{Float64, Vector{Float64}, Main.var"#1#2", GradientAutodiff{Float64, Main.var"#1#2", ForwardDiff.GradientConfig{ForwardDiff.Tag{Main.var"#1#2", Float64}, Float64, 3, Vector{ForwardDiff.Dual{ForwardDiff.Tag{Main.var"#1#2", Float64}, Float64, 3}}}}, Float64, Vector{Float64}}}(0.0001, 0.0, 0.6841489676563611, -1.3682979353127223, -1.3682979353127223, MultivariateObjective (for vector-valued quantities only the first component is printed):

    f(x)              = 6.84e-01 
    g(x)₁             = 3.82e-01 
    x_f₁              = 1.91e-01 
    x_g₁              = 1.91e-01 
    number of f calls = 5 
    number of g calls = 5 
)