"Error: not a descent direction" when trying to minimize `LinearAlgebra.norm` (!) with `trunk`

[ForceBru]

import Pkg; Pkg.activate(temp=true)
Pkg.add(name="JSOSolvers", version="0.11.2")
Pkg.add(name="ADNLPModels", version="0.7.0")

using LinearAlgebra, ADNLPModels; import JSOSolvers

julia> JSOSolvers.trunk( ADNLPModel(norm, ones(10)) )
┌ Error: not a descent direction: slope = -0.0, ‖∇f‖ = 0.9999999999999999
└ @ JSOSolvers ~/.julia/packages/JSOSolvers/zfm1c/src/trunk.jl:282
"Execution stats: not a descent direction"

When I use the example from the docs everything works OK:

julia> JSOSolvers.trunk( ADNLPModel(x -> sum(x.^2), ones(10)) )
"Execution stats: first-order stationary"

Throw in a square root and I get the error message:

julia> stats = @time JSOSolvers.trunk( ADNLPModel(x -> sum(x.^2) |> sqrt, ones(10)) )
┌ Error: not a descent direction: slope = -0.0, ‖∇f‖ = 0.9999999999999999
└ @ JSOSolvers ~/.julia/packages/JSOSolvers/zfm1c/src/trunk.jl:282
  3.395720 seconds (1.91 M allocations: 140.653 MiB, 1.06% gc time, 99.83% compilation time)
"Execution stats: not a descent direction"

However, the solution itself is fine:

julia> stats.solution
10-element Vector{Float64}:
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
 -6.420466675466589e-19
julia> stats.solution_reliable
true # but there's an error message, so the solution shouldn't be reliable?

[tmigot]

Hi @ForceBru !

true # but there's an error message, so the solution shouldn't be reliable?

When the algorithm returns an error message, the stats.solution corresponds to the last iterate, so it can still be of interest. As you noticed, the solution computed is actually very close to the solution you expected.

The issue in your example is that the problem is not continuously differentiable.

using NLPModels
nlp = ADNLPModel(x -> sum(x.^2) |> sqrt, ones(10))
grad(nlp, zeros(10)) # the square root function is not differentiable in 0, return NaNs

and so there is no theoretical guarantees. In general, optimizing x -> sum(x.^2) is equivalent to norm though.

If you are interested in least squares problems, I would recommend using ADNLSModel instead of ADNLPModel. If you are interested in nonsmooth formulations like your example, I would first look into https://github.com/JuliaSmoothOptimizers/RegularizedOptimization.jl

[tmigot]

@ForceBru Can we close this?

[dpo]

As @tmigot mentioned, the issue arises because the iterates converge to a place where the objective is not differentiable.