Implement Utilities.distance_to_set for more sets

[freemin7]

Is your feature request related to a problem? Please describe.
I have a model which contains a MathOptInterface.PowerCone and want to verify a the primal feasibility of a point.

Describe the solution you'd like
Support feasibility checking of all standard sets maintained by jump-dev. Short term i need a workaround.

Describe alternatives you've considered
I considered monkey-patching _distance_to_set(var::Vector{Float64},cone::MathOptInterface.PowerCone) = distance_to_set(var::Vector{Float64},cone::MathOptInterface.PowerCone) from MathOptSetDistances by @matbesancon however that did not work.

[matbesancon]

can you be more specific in what did not work on using the PowerCone from MOSD?

[freemin7]

Well it didn't solve the not implemented error. After i ran
_distance_to_set(var::Vector{Float64},cone::MathOptInterface.PowerCone) = distance_to_set(var,cone::MathOptInterface.PowerCone)
I got this error again:

  primal_feasibility_report(mc,AAA, skip_missing=true)
ERROR: Feasibility checker for set type MathOptInterface.PowerCone{Float64} has not been implemented yet.
Stacktrace:
 [1] _distance_to_set(#unused#::Vector{Float64}, set::MathOptInterface.PowerCone{Float64})
   @ JuMP ~/.julia/packages/JuMP/gVq7V/src/feasibility_checker.jl:174
 [2] _add_infeasible_constraints(model::Model, #unused#::Type{Vector{AffExpr}}, #unused#::Type{MathOptInterface.PowerCone{Float64}}, violated_constraints::Dict{Any, Float64}, point_f::Function, atol::Float64)
   @ JuMP ~/.julia/packages/JuMP/gVq7V/src/feasibility_checker.jl:145
 [3] primal_feasibility_report(point::Function, model::Model; atol::Float64, skip_missing::Bool)
   @ JuMP ~/.julia/packages/JuMP/gVq7V/src/feasibility_checker.jl:109
 [4] #primal_feasibility_report#173
   @ ~/.julia/packages/JuMP/gVq7V/src/feasibility_checker.jl:60 [inlined]
 [5] top-level scope
   @ REPL[385]:1

[matbesancon]

You probably need to patch it with:

JuMP._distance_to_set(var::Vector{Float64},cone::MathOptInterface.PowerCone) = MathOptSetDistances.distance_to_set(MathOptSetDistances.DefaultDistance(), var, cone::MathOptInterface.PowerCone)

I think you forgot the JuMP. qualifier

[odow]

We've intentionally avoided implementing distances for conic sets, because it was non-obvious what distances to use. I have to apologize to @matbesancon every time I bring this up, but if you want the backstory, go get a cup of coffee, then read #1023.

[freemin7]

Wearing my user hat it would be acceptable for me if loading some package that includes MathOptSetDistances provided feasibility analysis for checking for conic sets without having to do custom overloads and that that package is documented somewhere.

An alternative might be to use sign(distance_to_set) as that as invariant under different distance metrics. 0 is on boundary, negative inside, positive outside.

[matbesancon]

An alternative might be to use sign(distance_to_set) as that as invariant under different distance metrics. 0 is on boundary, negative inside, positive outside.

why would you need this? If you care about feasibility checking you just want the non-zeroeness of the distance in itself

[freemin7]

Well you are right you don't need a "signed distance function". My bad.

[odow]

So I guess the ask is for MOI.Utilities to provide distance_to_set and for JuMP to use that?

[freemin7]

That would be nice. If i have to include one package like NonLinearFeasibilityCheck to make it work that would also be an acceptable solution. However stuff like JuMP._distance_to_set(var::Vector{Float64},cone::MathOptInterface.PowerCone) = distance_to_set(var,cone::MathOptInterface.PowerCone) is not user friendly and error prone

[odow]

I'll move this to MOI, since this is where we'd add the functionality.

[odow]

Assuming we merge #2048, what distance would we use for this?

MOSD uses:

https://github.com/matbesancon/MathOptSetDistances.jl/blob/a449c4b178855db0b461d1aa13d60a5ae81b0eac/src/distance_sets.jl#L171-L185

[freemin7]

I think we established that what distance is used doesn't matter for the sake of feasibility checking as long as it implies the same discrete metric under ==0.
Since i am not aware of any code base which depends on something else than the discrete metric pick and since this was "broken" before for those cones no code should change by the decision. I'd suggest we pick whatever is cheapest to compute and document what was used and that we guarantee that it satisfies that the distance is zero if and only if it is in set and positive otherwise. Should different features be required in the future by a code base this decision can be revisited in light of more information and touched up with multiple dispatched to let the user communicate what they want.

[odow]

@matbesancon what are your thoughts on this? We could potentially add MathOptSetDistances as a pkg extension?

[matbesancon]

yes that makes sense. The current dependencies are:

BlockDiagonals = "0a1fb500-61f7-11e9-3c65-f5ef3456f9f0"
FillArrays = "1a297f60-69ca-5386-bcde-b61e274b549b"
LinearAlgebra = "37e2e46d-f89d-539d-b4ee-838fcccc9c8e"
MathOptInterface = "b8f27783-ece8-5eb3-8dc8-9495eed66fee"
StaticArrays = "90137ffa-7385-5640-81b9-e52037218182"

[matbesancon]

one of the key things to use these functionalities in solvers would be an in-place version of the projection to set

[blegat]

Not sure it should be a Pkg extension with these extensions, it's weird to have to import StaticArrays to be able to project your sets ^^
For the in-place version, totally agree, implementing in-place version with MA.buffer_for and MA.operate! would make this usable in solvers.
Maybe we should just add it. About the additional dependencies, we should check case by case why we need it and whether one part can be a Pkg extension

[matbesancon]

the other big functionality of SetDistances is the implementation of ChainRules for the projection gradient. Maybe this can be a separate extension

[odow]

it's weird to have to import StaticArrays to be able to project your sets

What does this have to do with it? You'd need using MathOptInterface, MathOptSetDistances

[odow]

I meant add a MathOptInterfaceMathOptSetDistances.jl extension which linked up the distance_to_set functions.

[matbesancon]

and StaticArrays is lightweight enough to bring along, no?

[odow]

I don't understand what StaticArrays has to do with this. It wouldn't become a direct dependency of MOI. We'd add a package extension between MOI and MOSD.

[blegat]

Then I'm missing something. What's the content of the package extension then ? Are we going to move part of the code of MOSD into the package extension and keep part of it in MOSD ?

[odow]

The extension would be:

module MathOptInterfaceMathOptSetDistancesExt
import MathOptInterface as MOI
import MathOptSetDistances as MOSD
MOI.Utilities.distance_to_set(x, s) = MOSD.distance_to_set(MOSD.DefaultDistance(), x, s)
end

That's all. It avoids type-piracy in MOSD, and it avoids MOI having to re-implement everything.

[freemin7]

The name is a tad annoying. I hope no user has to type that.

[odow]

The name is a tad annoying

What name? MathOptInterfaceMathOptSetDistancesExt? No. This would become a package extension like

• https://github.com/jump-dev/JuMP.jl/blob/master/ext/JuMPDimensionalDataExt.jl
• https://jump.dev/JuMP.jl/stable/extensions/DimensionalData/

[blegat]

For which set is distance_to_set implemented in MOSD but not in MOI ? From a quick look, I don't see any

[odow]

There are lots

https://github.com/matbesancon/MathOptSetDistances.jl/blob/dc93010b83f89d41813e8af1aa0153d746ff8fd3/src/distance_sets.jl#L94-L287

[blegat]

Indeed, I think it's simpler to move them to MOI rather than having a package extension.