Find fixed point of multivariable function in Julia

Question

I need to find the fixed point of a multivariable function in Julia.

Consider the following minimal example:

function example(p::Array{Float64,1})
    q = -p
    return q
end

Ideally I'd use a package like Roots.jl and call find_zeros(p -> p - example(p)), but I can't find the analogous package for multivariable functions. I found one called IntervalRootFinding, but it oddly requires unicode characters and is sparsely documented, so I can't figure out how to use it.

Bogumił Kamiński · Accepted Answer · 2019-10-11T21:18:19.527

There are many options. The choice of the best one depends on the nature of example function (you have to understand the nature of your example function and check against a documentation of a specific package if it would support it).

Eg. you can use fixedpoint from NLsolve.jl:

julia> using NLsolve

julia> function example!(q, p::Array{Float64,1})
           q .= -p
       end
example! (generic function with 1 method)

julia> fixedpoint(example!, ones(1))
Results of Nonlinear Solver Algorithm
 * Algorithm: Anderson m=1 beta=1 aa_start=1 droptol=0
 * Starting Point: [1.0]
 * Zero: [0.0]
 * Inf-norm of residuals: 0.000000
 * Iterations: 3
 * Convergence: true
   * |x - x'| < 0.0e+00: true
   * |f(x)| < 1.0e-08: true
 * Function Calls (f): 3
 * Jacobian Calls (df/dx): 0

julia> fixedpoint(example!, ones(3))
Results of Nonlinear Solver Algorithm
 * Algorithm: Anderson m=3 beta=1 aa_start=1 droptol=0
 * Starting Point: [1.0, 1.0, 1.0]
 * Zero: [-2.220446049250313e-16, -2.220446049250313e-16, -2.220446049250313e-16]
 * Inf-norm of residuals: 0.000000
 * Iterations: 3
 * Convergence: true
   * |x - x'| < 0.0e+00: false
   * |f(x)| < 1.0e-08: true
 * Function Calls (f): 3
 * Jacobian Calls (df/dx): 0

julia> fixedpoint(example!, ones(5))
Results of Nonlinear Solver Algorithm
 * Algorithm: Anderson m=5 beta=1 aa_start=1 droptol=0
 * Starting Point: [1.0, 1.0, 1.0, 1.0, 1.0]
 * Zero: [0.0, 0.0, 0.0, 0.0, 0.0]
 * Inf-norm of residuals: 0.000000
 * Iterations: 3
 * Convergence: true
   * |x - x'| < 0.0e+00: true
   * |f(x)| < 1.0e-08: true
 * Function Calls (f): 3
 * Jacobian Calls (df/dx): 0

If your function would require a global optimization tools to find a fixed point then you can e.g. use BlackBoxOptim.jl with norm(f(x) .-x) as an objective:

julia> using LinearAlgebra

julia> using BlackBoxOptim

julia> function example(p::Array{Float64,1})
           q = -p
           return q
       end
example (generic function with 1 method)

julia> f(x) = norm(example(x) .- x)
f (generic function with 1 method)

julia> bboptimize(f; SearchRange = (-5.0, 5.0), NumDimensions = 1)
Starting optimization with optimizer DiffEvoOpt{FitPopulation{Float64},RadiusLimitedSelector,BlackBoxOptim.AdaptiveDiffEvoRandBin{3},RandomBound{ContinuousRectSearchSpace}}
0.00 secs, 0 evals, 0 steps

Optimization stopped after 10001 steps and 0.15 seconds
Termination reason: Max number of steps (10000) reached
Steps per second = 68972.31
Function evals per second = 69717.14
Improvements/step = 0.35090
Total function evaluations = 10109


Best candidate found: [-8.76093e-40]

Fitness: 0.000000000

julia> bboptimize(f; SearchRange = (-5.0, 5.0), NumDimensions = 3);
Starting optimization with optimizer DiffEvoOpt{FitPopulation{Float64},RadiusLimitedSelector,BlackBoxOptim.AdaptiveDiffEvoRandBin{3},RandomBound{ContinuousRectSearchSpace}}
0.00 secs, 0 evals, 0 steps

Optimization stopped after 10001 steps and 0.02 seconds
Termination reason: Max number of steps (10000) reached
Steps per second = 625061.23
Function evals per second = 631498.72
Improvements/step = 0.32330
Total function evaluations = 10104


Best candidate found: [-3.00106e-12, -5.33545e-12, 5.39072e-13]

Fitness: 0.000000000


julia> bboptimize(f; SearchRange = (-5.0, 5.0), NumDimensions = 5);
Starting optimization with optimizer DiffEvoOpt{FitPopulation{Float64},RadiusLimitedSelector,BlackBoxOptim.AdaptiveDiffEvoRandBin{3},RandomBound{ContinuousRectSearchSpace}}
0.00 secs, 0 evals, 0 steps

Optimization stopped after 10001 steps and 0.02 seconds
Termination reason: Max number of steps (10000) reached
Steps per second = 526366.94
Function evals per second = 530945.88
Improvements/step = 0.29900
Total function evaluations = 10088


Best candidate found: [-9.23635e-8, -2.6889e-8, -2.93044e-8, -1.62639e-7, 3.99672e-8]

Fitness: 0.000000391

This is a hard question as all depends on the nature of `example` function. Eg. if it is a linear operator then IterativeSolvers.jl can be used. — Bogumił Kamiński, Oct 11 '19 at 21:16

score 1 · Answer 2 · answered Oct 15 '19 at 01:07

I'm an author of IntervalRootFinding.jl. I'm happy to say that the documentation has been improved a lot recently, and no unicode characters are necessary. I suggest using the master branch.

Here's how to solve your example with the package. Note that this package should be able to find all of the roots within a box, and guarantee that it has found all of them. Yours only has 1:

julia> using IntervalArithmetic, IntervalRootFinding

julia> function example(p)
           q = -p
           return q
       end
example (generic function with 2 methods)

julia> X = IntervalBox(-2..2, 2)
[-2, 2] × [-2, 2]

julia> roots(x -> example(x) - x, X, Krawczyk)
1-element Array{Root{IntervalBox{2,Float64}},1}:
 Root([0, 0] × [0, 0], :unique)

For more information, I suggest looking at https://discourse.julialang.org/t/ann-intervalrootfinding-jl-for-finding-all-roots-of-a-multivariate-function/9515.

Find fixed point of multivariable function in Julia

2 Answers2