Skip to content

Conversation

@MaxenceGollier
Copy link
Collaborator

@MaxenceGollier MaxenceGollier commented Jan 20, 2025

Fixed the merge issues from #166, I will show the benchmarks in the following comments.
Tests will fail as long as opnorm allocates.

Additionnally, I need LinearOperators v2.9 for the test to pass which does not seem to be the case on freeBSD ? @dpo

@MaxenceGollier
Copy link
Collaborator Author

For R2DH

On this branch,

julia> using LinearAlgebra, NLPModels, NLPModelsModifiers, RegularizedProblems, ProximalOperators, Random, ShiftedProximalOperators
julia> Random.seed!(0)
julia> bpdn = SpectralGradientModel(bpdn_model(1)[1])
julia> λ = norm(grad(bpdn, zeros(bpdn.meta.nvar)), Inf) / 10
julia> h = NormL0(λ)

julia> import Pkg; Pkg.add(url = "https://github.com/MaxenceGollier/RegularizedOptimization.jl.git", rev = "R2N-JSOnonalloc")
julia> using RegularizedOptimization
julia> options = ROSolverOptions(ν = 1.0, β = 1e16, ϵa = 1e-6, ϵr = 1e-6, verbose = 1)

julia> R2DH(bpdn, h, options)
[ Info:   iter     f(x)     h(x)   √(ξ/ν)        ρ        σ      ‖x‖      ‖s‖ R2DH 
[ Info:      0  1.8e+00  0.0e+00  1.5e-01  1.1e+01  1.0e+00  0.0e+00  3.8e-01               ↘
[ Info:      1  1.5e+00  1.4e-01  5.5e-01  1.6e+00  3.3e-01  3.8e-01  1.3e+00               ↘
[ Info:      2  5.3e-01  4.1e-01  3.9e-01  1.1e+00  1.1e-01  1.6e+00  1.2e+00               ↘
[ Info:      3  7.3e-02  4.6e-01  1.4e-01  1.0e+00  3.7e-02  2.6e+00  5.2e-01               ↘
[ Info:      4  1.4e-02  4.6e-01  2.8e-02  1.0e+00  1.2e-02  3.1e+00  1.2e-01               ↘
[ Info:      5  1.1e-02  4.6e-01  7.6e-03  1.0e+00  4.1e-03  3.1e+00  4.2e-02               ↘
[ Info:      6  1.1e-02  4.6e-01  1.1e-03  1.0e+00  1.4e-03  3.1e+00  6.5e-03               ↘
[ Info:      7  1.1e-02  4.6e-01  1.2e-03  1.0e+00  4.6e-04  3.1e+00  3.7e-03               ↘
[ Info:      8  1.1e-02  4.6e-01  3.0e-04  1.0e+00  1.5e-04  3.1e+00  7.6e-04               ↘
[ Info:      9  1.1e-02  4.6e-01  7.8e-06  1.0e+00  5.1e-05  3.1e+00  2.0e-05               ↘
[ Info:     10  1.1e-02  4.6e-01  3.1e-06  1.0e+00  1.7e-05  3.1e+00  1.2e-05               ↘
[ Info:     11  1.1e-02  4.6e-01  7.8e-07  1.0e+00  5.6e-06  3.1e+00  3.8e-06               ↘
[ Info: R2DH: terminating with √(ξ/ν) = 7.837416973188258e-7
"Execution stats: first-order stationary"

On the master branch, (note: we have to use $\sigma k$ instead of $\nu$ in the options of the master branch. I think all solvers should use $\nu$ like R2.)

julia> using LinearAlgebra, NLPModels, NLPModelsModifiers, RegularizedProblems, ProximalOperators, Random, ShiftedProximalOperators
julia> Random.seed!(0)
julia> bpdn = SpectralGradientModel(bpdn_model(1)[1])
julia> λ = norm(grad(bpdn, zeros(bpdn.meta.nvar)), Inf) / 10
julia> h = NormL0(λ)

julia> import Pkg; Pkg.add(url = "https://github.com/JuliaSmoothOptimizers/RegularizedOptimization.jl.git")
julia> using RegularizedOptimization
julia> options = ROSolverOptions(σk = 1.0, β = 1e16, ϵa = 1e-6, ϵr = 1e-6, verbose = 10)

julia> R2DH(bpdn, h, options)
[ Info:   iter     f(x)     h(x)  √(ξ/ν)        ρ       σ     ‖x‖     ‖s‖  
[ Info:      1  1.8e+00  0.0e+00 1.5e-01  1.1e+01 1.0e+00 0.0e+00 3.8e-01 ↘
[ Info:      2  1.5e+00  1.4e-01 5.5e-01  1.6e+00 3.3e-01 3.8e-01 1.3e+00 ↘
[ Info:      3  5.3e-01  4.1e-01 3.9e-01  1.1e+00 1.1e-01 1.6e+00 1.2e+00 ↘
[ Info:      4  7.3e-02  4.6e-01 1.4e-01  1.0e+00 3.7e-02 2.6e+00 5.2e-01 ↘
[ Info:      5  1.4e-02  4.6e-01 2.8e-02  1.0e+00 1.2e-02 3.1e+00 1.2e-01 ↘
[ Info:      6  1.1e-02  4.6e-01 7.6e-03  1.0e+00 4.1e-03 3.1e+00 4.2e-02 ↘
[ Info:      7  1.1e-02  4.6e-01 1.1e-03  1.0e+00 1.4e-03 3.1e+00 6.5e-03 ↘
[ Info:      8  1.1e-02  4.6e-01 1.2e-03  1.0e+00 4.6e-04 3.1e+00 3.7e-03 ↘
[ Info:      9  1.1e-02  4.6e-01 3.0e-04  1.0e+00 1.5e-04 3.1e+00 7.6e-04 ↘
[ Info:     10  1.1e-02  4.6e-01 7.8e-06  1.0e+00 5.1e-05 3.1e+00 2.0e-05 ↘
[ Info:     11  1.1e-02  4.6e-01 3.1e-06  1.0e+00 1.7e-05 3.1e+00 1.2e-05 ↘
[ Info:     12  1.1e-02  4.6e-01 7.8e-07          5.6e-06 3.1e+00 3.8e-06
[ Info: R2DH: terminating with √(ξ/ν) = 7.837416973188258e-7)
"Execution stats: first-order stationary"

For R2N (with R2)

On this branch,

julia> using LinearAlgebra, NLPModels, NLPModelsModifiers, RegularizedProblems, ProximalOperators, Random, ShiftedProximalOperators
julia> Random.seed!(0)
julia> bpdn = LBFGSModel(bpdn_model(1)[1])
julia> λ = norm(grad(bpdn, zeros(bpdn.meta.nvar)), Inf) / 10
julia> h = NormL0(λ)

julia> import Pkg; Pkg.add(url = "https://github.com/MaxenceGollier/RegularizedOptimization.jl.git", rev = "R2N-JSOnonalloc")
julia> using RegularizedOptimization
julia> options = ROSolverOptions(ν = 1.0, β = 1e16, ϵa = 1e-6, ϵr = 1e-6, verbose = 1)

julia> R2N(bpdn, h, options)
[ Info:  outer  inner     f(x)     h(x)  √(ξ1/ν)        ρ        σ      ‖x‖      ‖s‖      ‖B‖ R2N 
[ Info:      0      0  1.8e+00  0.0e+00  5.6e-01  1.1e+01  1.0e+00  0.0e+00  3.8e-01  1.0e+00               ↘
[ Info:      1     15  1.5e+00  1.4e-01  6.0e-01  1.4e+00  3.3e-01  3.8e-01  7.9e-01  1.8e+00               ↘
[ Info:      2     25  1.2e+00  1.4e-01  2.6e-01  1.7e+00  1.1e-01  1.2e+00  6.5e-01  1.8e+00               ↘
[ Info:      3     50  9.7e-01  1.8e-01  2.7e-01  1.2e+00  3.7e-02  1.7e+00  5.9e-01  2.2e+00               ↘
[ Info:      4     63  8.8e-01  1.8e-01  8.8e-02  3.4e+00  1.2e-02  2.2e+00  6.1e-01  2.6e+00               ↘
[ Info:      5     66  6.0e-01  3.2e-01  3.5e-01  1.0e+00  4.1e-03  2.4e+00  8.4e-01  2.6e+00               ↘
[ Info:      6     62  4.4e-01  3.2e-01  2.1e-02  1.3e+00  1.4e-03  2.7e+00  3.2e-02  2.6e+00               ↘
[ Info:      7     56  4.4e-01  3.2e-01  9.1e-03  1.1e+00  4.6e-04  2.8e+00  1.9e-02  2.1e+00               ↘
[ Info:      8     50  4.4e-01  3.2e-01  2.7e-03  1.4e+00  1.5e-04  2.8e+00  3.6e-03  2.2e+00               ↘
[ Info:      9     59  4.4e-01  3.2e-01  1.3e-03  1.1e+00  5.1e-05  2.8e+00  2.7e-03  2.3e+00               ↘
[ Info:     10     45  4.4e-01  3.2e-01  2.7e-04  1.3e+00  1.7e-05  2.8e+00  4.2e-04  2.4e+00               ↘
[ Info:     11     59  4.4e-01  3.2e-01  1.2e-04  1.2e+00  5.6e-06  2.8e+00  2.1e-04  2.3e+00               ↘
[ Info:     12  10001  4.4e-01  3.2e-01  4.9e-05  1.2e+00  1.9e-06  2.8e+00  8.3e-05  2.4e+00               ↘
[ Info:     13  10001  4.4e-01  3.2e-01  1.9e-05  1.2e+00  6.3e-07  2.8e+00  3.3e-05  2.5e+00               ↘
[ Info:     14  10001  4.4e-01  3.2e-01  7.6e-06  1.3e+00  2.1e-07  2.8e+00  1.2e-05  2.5e+00               ↘
[ Info:     15  10001  4.4e-01  3.2e-01  3.7e-06  1.2e+00  7.0e-08  2.8e+00  7.0e-06  2.5e+00               ↘
[ Info:     16      0  4.4e-01  3.2e-01  1.5e-06  1.2e+00  2.3e-08  2.8e+00  7.0e-06  2.6e+00               ↘
[ Info: R2N: terminating with √(ξ1/ν) = 1.487806772227812e-6
"Execution stats: first-order stationary"

On the master branch,

julia> using LinearAlgebra, NLPModels, NLPModelsModifiers, RegularizedProblems, ProximalOperators, Random, ShiftedProximalOperators
julia> Random.seed!(0)
julia> bpdn = LBFGSModel(bpdn_model(1)[1])
julia> λ = norm(grad(bpdn, zeros(bpdn.meta.nvar)), Inf) / 10
julia> h = NormL0(λ)

julia> import Pkg; Pkg.add(url = "https://github.com/JuliaSmoothOptimizers/RegularizedOptimization.jl.git")
julia> using RegularizedOptimization
julia> options = ROSolverOptions(σk = 1.0, β = 1e16, ϵa = 1e-6, ϵr = 1e-6, verbose = 10)

julia> R2N(bpdn, h, options)
[ Info:  outer    inner     f(x)     h(x) √(ξ1/ν)      √ξ        ρ       σ     ‖x‖     ‖s‖    ‖Bₖ‖ R2N
[ Info:      1        0  1.8e+00  0.0e+00 5.6e-01 4.0e-01  1.1e+01 1.0e+00 0.0e+00 3.8e-01 1.0e+00 ↘
[ Info:      2       15  1.5e+00  1.4e-01 6.0e-01 4.2e-01  1.4e+00 3.3e-01 3.8e-01 7.9e-01 1.8e+00 ↘
[ Info:      3       25  1.2e+00  1.4e-01 2.6e-01 1.9e-01  1.7e+00 1.1e-01 1.2e+00 6.5e-01 1.8e+00 ↘
[ Info:      4       50  9.7e-01  1.8e-01 2.7e-01 1.8e-01  1.2e+00 3.7e-02 1.7e+00 5.9e-01 2.2e+00 ↘
[ Info:      5       63  8.8e-01  1.8e-01 8.8e-02 5.5e-02  3.4e+00 1.2e-02 2.2e+00 6.1e-01 2.6e+00 ↘
[ Info:      6       66  6.0e-01  3.2e-01 3.5e-01 2.2e-01  1.0e+00 4.1e-03 2.4e+00 8.4e-01 2.6e+00 ↘
[ Info:      7       62  4.4e-01  3.2e-01 2.1e-02 1.3e-02  1.3e+00 1.4e-03 2.7e+00 3.2e-02 2.6e+00 ↘
[ Info:      8       56  4.4e-01  3.2e-01 9.1e-03 6.3e-03  1.1e+00 4.6e-04 2.8e+00 1.9e-02 2.1e+00 ↘
[ Info:      9       50  4.4e-01  3.2e-01 2.7e-03 1.8e-03  1.4e+00 1.5e-04 2.8e+00 3.6e-03 2.2e+00 ↘
[ Info:     10       59  4.4e-01  3.2e-01 1.3e-03 8.6e-04  1.1e+00 5.1e-05 2.8e+00 2.7e-03 2.3e+00 ↘
[ Info:     11       45  4.4e-01  3.2e-01 2.7e-04 1.7e-04  1.3e+00 1.7e-05 2.8e+00 4.2e-04 2.4e+00 ↘
[ Info:     12       59  4.4e-01  3.2e-01 1.2e-04 7.7e-05  1.2e+00 5.6e-06 2.8e+00 2.1e-04 2.3e+00 ↘
[ Info:     13    10001  4.4e-01  3.2e-01 4.9e-05 3.2e-05  1.2e+00 1.9e-06 2.8e+00 8.3e-05 2.4e+00 ↘
[ Info:     14    10001  4.4e-01  3.2e-01 1.9e-05 1.2e-05  1.2e+00 6.3e-07 2.8e+00 3.3e-05 2.5e+00 ↘
[ Info:     15    10001  4.4e-01  3.2e-01 7.6e-06 4.8e-06  1.3e+00 2.1e-07 2.8e+00 1.2e-05 2.5e+00 ↘
[ Info:     16    10001  4.4e-01  3.2e-01 3.7e-06 2.3e-06  1.2e+00 7.0e-08 2.8e+00 7.0e-06 2.5e+00 ↘
[ Info:     17        1  4.4e-01  3.2e-01 1.5e-06 9.3e-07          2.3e-08 2.8e+00 5.8e-07 2.6e+00
[ Info: R2N: terminating with √(ξ1/ν) = 1.487806772227812e-6
"Execution stats: first-order stationary"

For R2N (with R2DH)

On this branch,

julia> using LinearAlgebra, NLPModels, NLPModelsModifiers, RegularizedProblems, ProximalOperators, Random, ShiftedProximalOperators
julia> Random.seed!(0)
julia> bpdn = LBFGSModel(bpdn_model(1)[1])
julia> λ = norm(grad(bpdn, zeros(bpdn.meta.nvar)), Inf) / 10
julia> h = NormL0(λ)

julia> import Pkg; Pkg.add(url = "https://github.com/MaxenceGollier/RegularizedOptimization.jl.git", rev = "R2N-JSOnonalloc")
julia> using RegularizedOptimization
julia> options = ROSolverOptions(ν = 1.0, β = 1e16, ϵa = 1e-6, ϵr = 1e-6, verbose = 1)

julia> R2N(bpdn, h, options, subsolver = R2DHSolver)
[ Info:  outer  inner     f(x)     h(x)  √(ξ1/ν)        ρ        σ      ‖x‖      ‖s‖      ‖B‖ R2N 
[ Info:      0      0  1.8e+00  0.0e+00  5.6e-01  1.1e+01  1.0e+00  0.0e+00  3.8e-01  1.0e+00               ↘
[ Info:      1     23  1.5e+00  1.4e-01  6.0e-01  1.7e+00  3.3e-01  3.8e-01  9.2e-01  1.8e+00               ↘
[ Info:      2     30  9.9e-01  2.3e-01  4.6e-01  1.3e+00  1.1e-01  1.3e+00  9.2e-01  2.1e+00               ↘
[ Info:      3     40  7.2e-01  2.3e-01  1.7e-01  3.0e+00  3.7e-02  2.2e+00  5.7e-01  2.5e+00               ↘
[ Info:      4     33  5.4e-01  3.2e-01  2.7e-01  1.4e+00  1.2e-02  2.5e+00  6.9e-01  2.7e+00               ↘
[ Info:      5     41  3.7e-01  3.7e-01  2.0e-01  1.3e+00  4.1e-03  2.8e+00  3.7e-01  2.8e+00               ↘
[ Info:      6     48  3.3e-01  3.7e-01  9.1e-02  1.2e+00  1.4e-03  2.8e+00  1.9e-01  2.6e+00               ↘
[ Info:      7     49  3.2e-01  3.7e-01  3.1e-02  1.2e+00  4.6e-04  2.8e+00  6.1e-02  2.7e+00               ↘
[ Info:      8     56  3.1e-01  3.7e-01  1.2e-02  9.2e+00  1.5e-04  2.8e+00  3.2e-01  2.6e+00               ↘
[ Info:      9     47  2.3e-01  4.1e-01  2.0e-01  1.6e+00  5.1e-05  2.9e+00  6.7e-01  2.6e+00               ↘
[ Info:     10      9  9.0e-02  4.6e-01  2.2e-01  1.3e+00  1.7e-05  3.1e+00  4.8e-01  2.5e+00               ↘
[ Info:     11     10  2.9e-02  4.6e-01  1.1e-01  1.2e+00  5.6e-06  3.2e+00  2.6e-01  2.6e+00               ↘
[ Info:     12     10  1.3e-02  4.6e-01  4.2e-02  1.3e+00  1.9e-06  3.2e+00  7.8e-02  2.8e+00               ↘
[ Info:     13      9  1.1e-02  4.6e-01  2.0e-02  1.3e+00  6.3e-07  3.2e+00  3.4e-02  2.7e+00               ↘
[ Info:     14      8  1.1e-02  4.6e-01  8.5e-03  1.2e+00  2.1e-07  3.1e+00  1.7e-02  2.7e+00               ↘
[ Info:     15     10  1.1e-02  4.6e-01  3.0e-03  1.2e+00  7.0e-08  3.1e+00  6.0e-03  2.7e+00               ↘
[ Info:     16     10  1.1e-02  4.6e-01  1.2e-03  1.2e+00  2.3e-08  3.1e+00  2.2e-03  2.6e+00               ↘
[ Info:     17      9  1.1e-02  4.6e-01  4.6e-04  1.2e+00  7.7e-09  3.1e+00  7.6e-04  2.6e+00               ↘
[ Info:     18      7  1.1e-02  4.6e-01  1.7e-04  1.3e+00  2.6e-09  3.1e+00  2.9e-04  2.6e+00               ↘
[ Info:     19     10  1.1e-02  4.6e-01  7.7e-05  1.2e+00  8.6e-10  3.1e+00  1.4e-04  2.5e+00               ↘
[ Info:     20     14  1.1e-02  4.6e-01  3.3e-05  1.2e+00  2.9e-10  3.1e+00  5.7e-05  2.6e+00               ↘
[ Info:     21  10001  1.1e-02  4.6e-01  1.1e-05  1.2e+00  9.6e-11  3.1e+00  1.9e-05  2.6e+00               ↘
[ Info:     22  10001  1.1e-02  4.6e-01  4.9e-06  1.3e+00  3.2e-11  3.1e+00  8.8e-06  2.6e+00               ↘
[ Info:     23  10001  1.1e-02  4.6e-01  2.6e-06  1.3e+00  1.1e-11  3.1e+00  5.0e-06  2.5e+00               ↘
[ Info:     24      0  1.1e-02  4.6e-01  1.2e-06  1.3e+00  3.5e-12  3.1e+00  5.0e-06  2.6e+00               ↘
[ Info: R2N: terminating with √(ξ1/ν) = 1.2147419405372909e-6
"Execution stats: first-order stationary"

On the master branch,

julia> using LinearAlgebra, NLPModels, NLPModelsModifiers, RegularizedProblems, ProximalOperators, Random, ShiftedProximalOperators
julia> Random.seed!(0)
julia> bpdn = LBFGSModel(bpdn_model(1)[1])
julia> λ = norm(grad(bpdn, zeros(bpdn.meta.nvar)), Inf) / 10
julia> h = NormL0(λ)

julia> import Pkg; Pkg.add(url = "https://github.com/JuliaSmoothOptimizers/RegularizedOptimization.jl.git")
julia> using RegularizedOptimization
julia> options = ROSolverOptions(σk = 1.0, β = 1e16, ϵa = 1e-6, ϵr = 1e-6, verbose = 10)

julia> R2N(bpdn, h, options, subsolver = R2DH)
[ Info:  outer    inner     f(x)     h(x) √(ξ1/ν)      √ξ        ρ       σ     ‖x‖     ‖s‖    ‖Bₖ‖ R2N
[ Info:      1        1  1.8e+00  0.0e+00 5.6e-01 4.0e-01  1.1e+01 1.0e+00 0.0e+00 3.8e-01 1.0e+00 ↘
[ Info:      2       24  1.5e+00  1.4e-01 6.0e-01 4.2e-01  1.7e+00 3.3e-01 3.8e-01 9.2e-01 1.8e+00 ↘
[ Info:      3       31  9.9e-01  2.3e-01 4.6e-01 3.1e-01  1.3e+00 1.1e-01 1.3e+00 9.2e-01 2.1e+00 ↘
[ Info:      4       41  7.2e-01  2.3e-01 1.7e-01 1.1e-01  3.0e+00 3.7e-02 2.2e+00 5.7e-01 2.5e+00 ↘
[ Info:      5       34  5.4e-01  3.2e-01 2.7e-01 1.7e-01  1.4e+00 1.2e-02 2.5e+00 6.9e-01 2.7e+00 ↘
[ Info:      6       42  3.7e-01  3.7e-01 2.0e-01 1.2e-01  1.3e+00 4.1e-03 2.8e+00 3.7e-01 2.8e+00 ↘
[ Info:      7       49  3.3e-01  3.7e-01 9.1e-02 5.6e-02  1.2e+00 1.4e-03 2.8e+00 1.9e-01 2.6e+00 ↘
[ Info:      8       50  3.2e-01  3.7e-01 3.1e-02 1.9e-02  1.2e+00 4.6e-04 2.8e+00 6.1e-02 2.7e+00 ↘
[ Info:      9       57  3.1e-01  3.7e-01 1.2e-02 7.7e-03  9.2e+00 1.5e-04 2.8e+00 3.2e-01 2.6e+00 ↘
[ Info:     10       48  2.3e-01  4.1e-01 2.0e-01 1.2e-01  1.6e+00 5.1e-05 2.9e+00 6.7e-01 2.6e+00 ↘
[ Info:     11       10  9.0e-02  4.6e-01 2.2e-01 1.4e-01  1.3e+00 1.7e-05 3.1e+00 4.8e-01 2.5e+00 ↘
[ Info:     12       11  2.9e-02  4.6e-01 1.1e-01 6.8e-02  1.2e+00 5.6e-06 3.2e+00 2.6e-01 2.6e+00 ↘
[ Info:     13       11  1.3e-02  4.6e-01 4.2e-02 2.5e-02  1.3e+00 1.9e-06 3.2e+00 7.8e-02 2.8e+00 ↘
[ Info:     14       10  1.1e-02  4.6e-01 2.0e-02 1.2e-02  1.3e+00 6.3e-07 3.2e+00 3.4e-02 2.7e+00 ↘
[ Info:     15        9  1.1e-02  4.6e-01 8.5e-03 5.2e-03  1.2e+00 2.1e-07 3.1e+00 1.7e-02 2.7e+00 ↘
[ Info:     16       11  1.1e-02  4.6e-01 3.0e-03 1.9e-03  1.2e+00 7.0e-08 3.1e+00 6.0e-03 2.7e+00 ↘
[ Info:     17       11  1.1e-02  4.6e-01 1.2e-03 7.7e-04  1.2e+00 2.3e-08 3.1e+00 2.2e-03 2.6e+00 ↘
[ Info:     18       10  1.1e-02  4.6e-01 4.6e-04 2.9e-04  1.2e+00 7.7e-09 3.1e+00 7.6e-04 2.6e+00 ↘
[ Info:     19        8  1.1e-02  4.6e-01 1.7e-04 1.1e-04  1.3e+00 2.6e-09 3.1e+00 2.9e-04 2.6e+00 ↘
[ Info:     20       11  1.1e-02  4.6e-01 7.7e-05 4.9e-05  1.2e+00 8.6e-10 3.1e+00 1.4e-04 2.5e+00 ↘
[ Info:     21       15  1.1e-02  4.6e-01 3.3e-05 2.0e-05  1.2e+00 2.9e-10 3.1e+00 5.7e-05 2.6e+00 ↘
[ Info:     22    10000  1.1e-02  4.6e-01 1.1e-05 7.0e-06  1.2e+00 9.6e-11 3.1e+00 1.9e-05 2.6e+00 ↘
[ Info:     23    10000  1.1e-02  4.6e-01 4.9e-06 3.1e-06  1.3e+00 3.2e-11 3.1e+00 8.8e-06 2.6e+00 ↘
[ Info:     24    10000  1.1e-02  4.6e-01 2.6e-06 1.6e-06  1.3e+00 1.1e-11 3.1e+00 5.0e-06 2.5e+00 ↘
[ Info:     25        1  1.1e-02  4.6e-01 1.2e-06 7.5e-07          3.5e-12 3.1e+00 4.6e-07 2.6e+00
[ Info: R2N: terminating with √(ξ1/ν) = 1.2147419405399635e-6
"Execution stats: first-order stationary"

As you can see, the results are still a bit different but the number of subsolver iterations are exactly the same and the difference between the stationarity measures is of the order $10^{-18}$, I don't know what to think about it, I will try to further investigate. In the mean time, I think you can start reviewing @dpo @MohamedLaghdafHABIBOULLAH.

@dpo
Copy link
Member

dpo commented Jan 21, 2025

I need LinearOperators v2.9 for the test to pass which does not seem to be the case on freeBSD ?

Sorry, I don’t understand the question.

@dpo
Copy link
Member

dpo commented Jan 21, 2025

@MaxenceGollier I would prefer if the file names remained R2DH.jl, R2N.jl, etc. We will rename those that are called *_alg.jl in a follow-up PR.

@MaxenceGollier
Copy link
Collaborator Author

I need LinearOperators v2.9 for the test to pass which does not seem to be the case on freeBSD ?

Sorry, I don’t understand the question.

The R2DH allocation test fails on all checks. This is the case when LinearOperators.jl is installed on a version different from 2.9. I guess we should change the project compatibility...

@dpo
Copy link
Member

dpo commented Jan 21, 2025

I need LinearOperators v2.9 for the test to pass which does not seem to be the case on freeBSD ?

Sorry, I don’t understand the question.

The R2DH allocation test fails on all checks. This is the case when LinearOperators.jl is installed on a version different from 2.9. I guess we should change the project compatibility...

Yes, that’s fine. I think you just need to change https://github.com/JuliaSmoothOptimizers/RegularizedOptimization.jl/blob/master/Project.toml#L21. Maybe in a separate PR, and then rebase this one.

@MaxenceGollier
Copy link
Collaborator Author

MaxenceGollier commented Jan 29, 2025

@dpo I think you can start reviewing.
We can add something with QuadraticModels to replace R2NModel in a later PR.
Thank you !

end
Bk = hess_op(f, xk)
λmax = opnorm(Bk)
solver.subpb.model.B = hess_op(nlp, xk)
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It seems that you do not update solver.subpb.model.∇f, or perhaps I'm mistaken.

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is quite hard to spot why I agree.
Perhaps I should change this to make it clearer (do you have suggestions ?)

The reason is that if you look how I initialize solver.subpb.model I give it the same vector as ∇fk. Hence the memory of solver.subpb.model.∇f is shared with the one of ∇fk and any modification of one changes the other. This is why we don't need to update it, it is already done when we call grad!(...).

@MohamedLaghdafHABIBOULLAH
Copy link
Collaborator

Thank you, @MaxenceGollier, for this enormous work. I’ve started reviewing the R2NModel structure and part of the R2N solver. I’ll try to finish it as soon as possible.

Copy link
Member

@dpo dpo left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks @MaxenceGollier! It looks good!

I have a number of minor comments.

src/LMTR_alg.jl Outdated
jtprod_residual!(nls, xk, Fk, ∇fk)
σmax = opnorm(Jk)
νInv = (1 + θ) * σmax^2 # ‖J'J‖ = ‖J‖²
νInv = σmax^2/θ # ‖J'J‖ = ‖J‖²
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could you please, just open a quick PR for LM and LMTR separately? I think it would be more organized.

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, I agree.

@MohamedLaghdafHABIBOULLAH
Copy link
Collaborator

MohamedLaghdafHABIBOULLAH commented Feb 24, 2025

@MaxenceGollier I have an issue with the type stability of the method R2NSolver.

It seems that the constructor of the R2NSolver struct struggles to infer the output type based on the input types.
Here’s a breakdown:

julia> h = NormL0(λ)
NormL0{Float64}(0.05177434365494306)

julia> reg_nlp = RegularizedNLPModel(LBFGSModel(bpdn), h);

julia> @code_warntype R2NSolver(reg_nlp)

The output reveals the following:

Body::R2NSolver{Float64, _A, Vector{Float64}} where _A<:ShiftedProximableFunction

As you can see, Julia struggles to deduce the concrete type of _A<:ShiftedProximableFunction (highlighted in red in the REPL output).

Ideally, it should have inferred the more specific type:

Body::R2NSolver{Float64, ShiftedNormL0{Float64, Vector{Float64}, Vector{Float64}, Vector{Float64}}, Vector{Float64}}

This type instability suggests that the constructor does not propagate type information effectively, which could negatively impact the performance of R2NSolver.

@MohamedLaghdafHABIBOULLAH
Copy link
Collaborator

MohamedLaghdafHABIBOULLAH commented Feb 24, 2025

Sorry it should have inferred the following:

Body::R2NSolver4{Float64, ShiftedNormL0{Float64, Vector{Float64}, Vector{Float64}, Vector{Float64}}, Vector{Float64}, R2Solver{Float64, ShiftedNormL0{Float64, Vector{Float64}, Vector{Float64}, Vector{Float64}}, Vector{Float64}}, RegularizedNLPModel{Float64, Vector{Float64}, R2NModel{Float64, Vector{Float64}, LBFGSOperator{Float64, Int64, LinearOperators.var"#67#69"{LinearOperators.var"#lbfgs_multiply#68", LinearOperators.LBFGSData{Float64, Int64}}, LinearOperators.var"#67#69"{LinearOperators.var"#lbfgs_multiply#68", LinearOperators.LBFGSData{Float64, Int64}}, LinearOperators.var"#67#69"{LinearOperators.var"#lbfgs_multiply#68", LinearOperators.LBFGSData{Float64, Int64}}}}, ShiftedNormL0{Float64, Vector{Float64}, Vector{Float64}, Vector{Float64}}, UnitRange{Int64}}}

which is the type of the object R2NSolver.

Here are some performance optimization tips: Julia Performance Tips.

@MaxenceGollier
Copy link
Collaborator Author

Ok @MohamedLaghdafHABIBOULLAH, I will fix it.

Note that this does not really matter as we don't expect to spend a lot of time in the function R2NSolver anyway but rather solve! ;)

@MaxenceGollier
Copy link
Collaborator Author

Should be good now with f136eaa

@MohamedLaghdafHABIBOULLAH
Copy link
Collaborator

Thanks, I think, that solve! also has the same issue.

@MaxenceGollier
Copy link
Collaborator Author

Should be good now with f136eaa

Actually, it did not solve it. I am reverting the changes now as it broke R2N.
I think the issue is that we should be able to infer the type of G given the arguments in R2NSolver which is not trivial at all. I don't think it is an issue though.

Yes solve! also throws warnings with JET but they are not important as well, they don't cause allocations and there shouldn't be runtime dispatches nor captured variables issues.

result = zero(T)
n = length(d)
@inbounds for i = 1:n
result += d[i]^2*dkσk[i]/2 + ∇fk[i]*d[i]
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Spacing.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@MaxenceGollier Please use the Julia formatter locally to avoid this type of comment. A reviewer should only need to focus on the code, not the formatting.

Copy link
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I didn't know I could do that, sorry, will make sure to do it in my future PRs.

@MaxenceGollier MaxenceGollier force-pushed the R2N-JSOnonalloc branch 2 times, most recently from 705a38e to 6671aed Compare March 3, 2025 19:43
@MaxenceGollier
Copy link
Collaborator Author

@MohamedLaghdafHABIBOULLAH #156 broke this.
@dpo LM calls R2DH with the old signature: R2DH(f, ∇f!, h,...) which does no longer exist here. What do you suggest I do ?

@MohamedLaghdafHABIBOULLAH
Copy link
Collaborator

Thanks, @MaxenceGollier! I suggest doing the same as for R2 and adding a quick function like this one:
https://github.com/JuliaSmoothOptimizers/RegularizedOptimization.jl/blob/master/src/R2_alg.jl#L217
This would allow taking R2DH(f, ∇f!, h,...) into account until we do the same for LM.

@github-actions
Copy link
Contributor

Here are the
demos-results

@dpo
Copy link
Member

dpo commented Apr 16, 2025

@MohamedLaghdafHABIBOULLAH Please approve if you have no further comments.

@github-actions
Copy link
Contributor

Here are the
demos-results

@MaxenceGollier
Copy link
Collaborator Author

@MohamedLaghdafHABIBOULLAH 069b854 should make you able to send keyword args to the subsolver !

@github-actions
Copy link
Contributor

Here are the
demos-results

@MohamedLaghdafHABIBOULLAH
Copy link
Collaborator

Thank you @MaxenceGollier, please rebase your PR.

@github-actions
Copy link
Contributor

Here are the
demos-results

@github-actions
Copy link
Contributor

Here are the
demos-results

@github-actions
Copy link
Contributor

Here are the
demos-results

@MohamedLaghdafHABIBOULLAH
Copy link
Collaborator

MohamedLaghdafHABIBOULLAH commented May 2, 2025

Thank you, @MaxenceGollier, for this version.
@dpo, quite a few aspects have changed between the GitHub implementation and what’s described in the paper — notably the use of ARPACK, the computation of ν_sub, and others.

I compared Maxence’s implementation directly with the one on GitHub, and the results match quite well on this example:

random_seed = 1234
Random.seed!(random_seed)
compound = 10
model, nls_model, sol = bpdn_model(compound, bounds = false)

# parameters
f = LBFGSModel(model)
λ = norm(grad(model, zeros(model.meta.nvar)), Inf) / 10
h = NormL0(λ)
x0 = zeros(f.meta.nvar)

# Basic R2DH (git)

[ Info:  using R2DH_Spec_NM_B with subsolver = None
[ Info:   iter     f(x)     h(x)  /ν)        ρ       σ     ‖x‖     ‖s‖  
[ Info:      1  2.0e+01  0.0e+00 1.7e+00  2.4e+00 6.1e-06 0.0e+00 3.8e+00 ↘
[ Info:      2  8.7e+00  4.4e+00 1.7e+00  1.1e+00 2.0e-06 3.8e+00 5.7e+00 ↘
[ Info:      3  4.8e-01  5.5e+00 3.5e-01  1.0e+00 6.7e-07 9.1e+00 1.3e+00 ↘
[ Info:      4  1.1e-01  5.5e+00 8.0e-02  1.0e+00 2.2e-07 9.8e+00 3.5e-01 ↘
[ Info:      5  9.3e-02  5.5e+00 1.8e-02  1.0e+00 7.5e-08 1.0e+01 8.4e-02 ↘
[ Info:      6  9.2e-02  5.5e+00 9.6e-03  1.0e+00 2.5e-08 1.0e+01 3.3e-02 ↘
[ Info:      7  9.2e-02  5.5e+00 2.4e-03  1.0e+00 8.3e-09 1.0e+01 6.8e-03 ↘
[ Info:      8  9.2e-02  5.5e+00 2.7e-04  1.0e+00 2.8e-09 1.0e+01 7.4e-04 ↘
[ Info:      9  9.2e-02  5.5e+00 1.2e-04  1.0e+00 9.2e-10 1.0e+01 5.8e-04 ↘
[ Info:     10  9.2e-02  5.5e+00 1.3e-05          3.1e-10 1.0e+01 7.1e-05
[ Info: R2DH_B: terminating with /ν) = 1.3279891624205704e-5)

# Maxence R2DH

[ Info:  using R2DH_Spec_NM_M with subsolver = None
[ Info:   iter     f(x)     h(x)   /ν)        ρ        σ      ‖x‖      ‖s‖ R2DH_M 
[ Info:      0  2.0e+01  0.0e+00  1.7e+00  2.4e+00  6.1e-06  0.0e+00  3.8e+00               ↘
[ Info:      1  8.7e+00  4.4e+00  1.7e+00  1.1e+00  2.0e-06  3.8e+00  5.7e+00               ↘
[ Info:      2  4.8e-01  5.5e+00  3.5e-01  1.0e+00  6.7e-07  9.1e+00  1.3e+00               ↘
[ Info:      3  1.1e-01  5.5e+00  8.0e-02  1.0e+00  2.2e-07  9.8e+00  3.5e-01               ↘
[ Info:      4  9.3e-02  5.5e+00  1.8e-02  1.0e+00  7.5e-08  1.0e+01  8.4e-02               ↘
[ Info:      5  9.2e-02  5.5e+00  9.6e-03  1.0e+00  2.5e-08  1.0e+01  3.3e-02               ↘
[ Info:      6  9.2e-02  5.5e+00  2.4e-03  1.0e+00  8.3e-09  1.0e+01  6.8e-03               ↘
[ Info:      7  9.2e-02  5.5e+00  2.7e-04  1.0e+00  2.8e-09  1.0e+01  7.4e-04               ↘
[ Info:      8  9.2e-02  5.5e+00  1.2e-04  1.0e+00  9.2e-10  1.0e+01  5.8e-04               ↘
[ Info:      9  9.2e-02  5.5e+00  1.3e-05  1.0e+00  3.1e-10  1.0e+01  7.1e-05               ↘
[ Info: R2DH_M: terminating with /ν) = 1.3279891624205704e-5

# Basic R2N (GitHub)

[ Info:  using R2N_R2_B with subsolver = None
[ Info:  outer    inner     f(x)     h(x) (ξ1/ν)      ξ        ρ       σ     ‖x‖     ‖s‖    ‖Bₖ‖ R2N_B
[ Info:      1        2  2.0e+01  0.0e+00 3.1e+00 3.1e+00  2.4e+00 6.1e-06 0.0e+00 3.8e+00 1.0e+00 ↘
[ Info:      2       26  8.7e+00  4.4e+00 2.1e+00 1.6e+00  1.1e+00 2.0e-06 3.8e+00 5.0e+00 1.7e+00 ↘
[ Info:      3       37  2.4e+00  5.0e+00 7.7e-01 5.5e-01  1.8e+00 6.7e-07 8.7e+00 1.1e+00 1.9e+00 ↘
[ Info:      4       53  1.6e+00  5.1e+00 5.9e-01 4.0e-01  1.4e+00 2.2e-07 9.3e+00 1.7e+00 2.2e+00 ↘
[ Info:      5       48  7.2e-01  5.4e+00 4.5e-01 2.9e-01  1.6e+00 7.5e-08 9.7e+00 8.5e-01 2.4e+00 ↘
[ Info:      6       54  4.1e-01  5.4e+00 3.1e-01 2.0e-01  1.5e+00 2.5e-08 9.8e+00 8.5e-01 2.5e+00 ↘
[ Info:      7       12  1.8e-01  5.5e+00 2.5e-01 1.5e-01  1.3e+00 8.3e-09 9.9e+00 5.0e-01 2.7e+00 ↘
[ Info:      8       11  1.1e-01  5.5e+00 1.1e-01 6.8e-02  1.2e+00 2.8e-09 1.0e+01 2.3e-01 2.7e+00 ↘
[ Info:      9        8  9.5e-02  5.5e+00 4.4e-02 2.7e-02  1.2e+00 9.2e-10 1.0e+01 8.6e-02 2.7e+00 ↘
[ Info:     10        9  9.3e-02  5.5e+00 1.8e-02 1.1e-02  1.3e+00 3.1e-10 1.0e+01 3.2e-02 2.6e+00 ↘
[ Info:     11       11  9.2e-02  5.5e+00 8.9e-03 5.5e-03  1.2e+00 1.0e-10 1.0e+01 1.7e-02 2.6e+00 ↘
[ Info:     12       11  9.2e-02  5.5e+00 3.7e-03 2.3e-03  1.2e+00 3.4e-11 1.0e+01 7.2e-03 2.6e+00 ↘
[ Info:     13       11  9.2e-02  5.5e+00 1.6e-03 1.0e-03  1.2e+00 1.1e-11 1.0e+01 3.1e-03 2.6e+00 ↘
[ Info:     14       11  9.2e-02  5.5e+00 7.4e-04 4.6e-04  1.3e+00 3.8e-12 1.0e+01 1.3e-03 2.6e+00 ↘
[ Info:     15       11  9.2e-02  5.5e+00 3.4e-04 2.1e-04  1.2e+00 1.3e-12 1.0e+01 6.4e-04 2.7e+00 ↘
[ Info:     16       11  9.2e-02  5.5e+00 1.5e-04 9.3e-05  1.3e+00 4.2e-13 1.0e+01 2.9e-04 2.7e+00 ↘
[ Info:     17        1  9.2e-02  5.5e+00 7.5e-05 4.6e-05          1.4e-13 1.0e+01 2.8e-05 2.7e+00
[ Info: R2N_B: terminating with (ξ1/ν) = 7.48260420816068e-5

# Maxence R2N
[ Info:  using R2N_R2_M with subsolver = None
[ Info:  outer  inner     f(x)     h(x)  (ξ1/ν)        ρ        σ      ‖x‖      ‖s‖      ‖B‖ R2N_M 
[ Info:      0      1  2.0e+01  0.0e+00  3.1e+00  2.4e+00  6.1e-06  0.0e+00  3.8e+00  1.0e+00               ↘
[ Info:      1     25  8.7e+00  4.4e+00  2.1e+00  1.1e+00  2.0e-06  3.8e+00  5.0e+00  1.7e+00               ↘
[ Info:      2     36  2.4e+00  5.0e+00  7.7e-01  1.8e+00  6.7e-07  8.7e+00  1.1e+00  1.9e+00               ↘
[ Info:      3     52  1.6e+00  5.1e+00  5.9e-01  1.4e+00  2.2e-07  9.3e+00  1.7e+00  2.2e+00               ↘
[ Info:      4     47  7.2e-01  5.4e+00  4.5e-01  1.6e+00  7.5e-08  9.7e+00  8.5e-01  2.4e+00               ↘
[ Info:      5     53  4.1e-01  5.4e+00  3.1e-01  1.5e+00  2.5e-08  9.8e+00  8.5e-01  2.5e+00               ↘
[ Info:      6     11  1.8e-01  5.5e+00  2.5e-01  1.3e+00  8.3e-09  9.9e+00  5.0e-01  2.7e+00               ↘
[ Info:      7     10  1.1e-01  5.5e+00  1.1e-01  1.2e+00  2.8e-09  1.0e+01  2.3e-01  2.7e+00               ↘
[ Info:      8      7  9.5e-02  5.5e+00  4.4e-02  1.2e+00  9.2e-10  1.0e+01  8.6e-02  2.7e+00               ↘
[ Info:      9      8  9.3e-02  5.5e+00  1.8e-02  1.3e+00  3.1e-10  1.0e+01  3.2e-02  2.6e+00               ↘
[ Info:     10     10  9.2e-02  5.5e+00  8.9e-03  1.2e+00  1.0e-10  1.0e+01  1.7e-02  2.6e+00               ↘
[ Info:     11     10  9.2e-02  5.5e+00  3.7e-03  1.2e+00  3.4e-11  1.0e+01  7.2e-03  2.6e+00               ↘
[ Info:     12     10  9.2e-02  5.5e+00  1.6e-03  1.2e+00  1.1e-11  1.0e+01  3.1e-03  2.6e+00               ↘
[ Info:     13     10  9.2e-02  5.5e+00  7.4e-04  1.3e+00  3.8e-12  1.0e+01  1.3e-03  2.6e+00               ↘
[ Info:     14     10  9.2e-02  5.5e+00  3.4e-04  1.2e+00  1.3e-12  1.0e+01  6.4e-04  2.7e+00               ↘
[ Info:     15     10  9.2e-02  5.5e+00  1.5e-04  1.3e+00  4.2e-13  1.0e+01  2.9e-04  2.7e+00               ↘
[ Info:     16      0  9.2e-02  5.5e+00  7.5e-05  1.3e+00  1.4e-13  1.0e+01  2.9e-04  2.7e+00               ↘
[ Info: R2N_M: terminating with (ξ1/ν) = 7.482604208161469e-5

I compared Maxence’s implementation directly with the one on GitHub. Using the same solver options, we observe that the results are practically identical, and the differences in stationarity measures are very small.

I believe we’re ready to merge @dpo @MaxenceGollier.

@dpo
Copy link
Member

dpo commented May 2, 2025

Thank you both!

@dpo dpo merged commit 9bb4a9a into JuliaSmoothOptimizers:master May 2, 2025
14 checks passed
@github-actions
Copy link
Contributor

github-actions bot commented May 2, 2025

Here are the
demos-results

@MaxenceGollier
Copy link
Collaborator Author

@MohamedLaghdafHABIBOULLAH, 069b854 seems to be causing troubles for type stability. I think we might have to remove it and have it the old way, how necessary is it for you to keep it as such ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants