Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • Oct 13 16:22
    schillic synchronize #689
  • Oct 13 16:22

    schillic on schur

    fix Schur transformation add code to undo a coordinate t… (compare)

  • Oct 13 16:22
    schillic synchronize #696
  • Oct 13 16:22

    schillic on schillic-patch-1

    Update to new Documenter change (compare)

  • Oct 13 16:17

    mforets on gh-pages

    build based on fe950d7 (compare)

  • Oct 13 16:07
    schillic updated the wiki
  • Oct 13 16:04

    schillic on 690

    (compare)

  • Oct 13 16:04

    schillic on master

    generalize or concretize contai… use ReachSets of type SVector i… Merge pull request #695 from Ju… (compare)

  • Oct 13 16:04
    schillic closed #695
  • Oct 13 16:04
    schillic closed #690
  • Oct 13 15:11
    schillic commented #42
  • Oct 13 14:44
    schillic synchronize #695
  • Oct 13 14:44

    schillic on 690

    use ReachSets of type SVector i… (compare)

  • Oct 13 14:01
    schillic commented #689
  • Oct 13 14:00
    schillic commented #689
  • Oct 13 13:57
    schillic synchronize #689
  • Oct 13 13:57

    schillic on schur

    fix Schur transformation add code to undo a coordinate t… (compare)

  • Oct 13 11:49
    mforets commented #19
  • Oct 13 11:07
    mforets edited #43
  • Oct 13 11:07
    mforets opened #43
Christian Schilling
@schillic
because you know it's invertible and the inverse is S
Marcelo Forets
@mforets
indeed
Christian Schilling
@schillic
maybe there should be a new function linear_map_inverse?
Marcelo Forets
@mforets
hmm optionally passing the extra stuff to linear_map seems better imo
Christian Schilling
@schillic
@ueliwechsler: sorry that this drifted. do you still follow? :)
Marcelo Forets
@mforets
@ueliwechsler congratulations you earned an issue! :p
hmm this is related but not the same?
we didn't speak about passing the inverse matrix there
Christian Schilling
@schillic
true, we want to do sth even faster
where you already know the inverse
Marcelo Forets
@mforets
yup
Christian Schilling
@schillic
but it's definitely related
Marcelo Forets
@mforets
ok we may want to include the optional inverse in this issue as well
this issue was some logic (my logic) broken
Christian Schilling
@schillic
ok
Marcelo Forets
@mforets
let me add a comment about this discussion.. then i'll head for lunch
Christian Schilling
@schillic
:+1:
Christian Schilling
@schillic
@ueliwechsler: it seems to me be that in your minkowski_difference the second argument is a (again: constant) BallInf. maybe that can be exploited, but from the code for minkowski_difference i don't see how
however, your inputs are zonotopes, minkowski_difference of two zonotopes is again a zonotope (not in our current implementation, but it should be easy to add a method for that; this is JuliaReach/LazySets.jl#586), and the linear map of a zonotope is again a zonotope. the "problematic" operation here is the intersection with a BallInf, which does not preserve "being a zonotope." if you are willing to pay the price of an overapproximation to a zonotope at this point, you would get rid of the remove_redundant_constraints and the linear_map would be cheap as well. but the intersection then becomes more complicated (i think there is no way around some bottleneck :P)
Christian Schilling
@schillic

for the minkowski_difference I know that I solve #constraint linear programs (therefore, it is linear in the number of constraints)

no, the implementation of minkowski_difference performs m support-function queries, which in your case are applied to a BallInf (which is very cheap)

so i'm not surprised that minkowski_difference is fast
ueliwechsler
@ueliwechsler
Thanks for your help guys! :D
Yes, I followed (but then my supervisor interrupted me)
For my problem, I most likely need to work with HPolytopes so even though the Zonotopes option sounds really interesting, I cannot use it for my current issue.
But enabling linear_map to pass the matrix S directly would be exactly what I was looking for since if I can get rid of the performance penalty of computing the inverse every iteration.
Christian Schilling
@schillic
but then my supervisor interrupted me
they tend to do that :)
ueliwechsler
@ueliwechsler
I see, so I have to be really careful with my conclusions since they depend heavily on the type 😅
Christian Schilling
@schillic
so the BallInfs are just examples?
yes, it is common that you can write a much more efficient algorithm if you know the type of set you are dealing with
and that's also why preserving more concrete types is beneficial
for instance in your first loop iteration you could work with zonotopes (assuming we have the efficient minkowski_difference) until the intersection "for free"
but then in the second iteration you will have an HPolytope and have to use the slower methods
but that happens automatically
ueliwechsler
@ueliwechsler
I most cases, I would use the BallInf, but in general, I'd like to know the computational complexity of the general case, which for me is HPolytope.
Christian Schilling
@schillic
ok sure
ueliwechsler
@ueliwechsler
Thanks for the clarification, I was sloppy while dealing with the concrete types
Christian Schilling
@schillic
no problem, it gave us the opportunity to help :)
i can have a look at JuliaReach/LazySets.jl#1500 (the linear map) in the next days, but if you are eager, you can just add this option yourself and see if it helps (here)
this has a nasty tail, so you have to pass the option through several helper functions :)
basically make this line optional
ueliwechsler
@ueliwechsler
👍 thanks, I will try it out. I am curious how much it will change the performance.
Marcelo Forets
@mforets
minkowski_difference for hyperrectangular sets can be specialized as well or not?
Marcelo Forets
@mforets
But it is cheap anyways give 2 ballinf as you said above..
The equality check can also be improved..? Save half the evaluations in the dual inclusion by checking approximate equality of the support functions
Christian Schilling
@schillic

minkowski_difference for hyperrectangular sets can be specialized as well or not?

maybe, but the hyperrectangle will definitely be destroyed by the linear_map
but that would be an alternative to my other suggestion: overapproximate the result of linear_map by a hyperrectangle. hyperrectangles are closed under intersection, so this would give you a "stable" loop. and all of these operations are cheap, so i would really give it a try, just to see the potential performance boost

@ueliwechsler: can you try out the variant of your algorithm with this change?
𝒫⁺ = intersection(overapproximate(linear_map(S_inv, minkowski_difference(𝒫,𝒲)), Hyperrectangle), 𝒟)

The equality check can also be improved..? Save half the evaluations in the dual inclusion by checking approximate equality of the support functions

i didn't understand this proposal. but yeah, if typically one of the two inclusions fails, it is more efficient to do that check first (because it usually avoids the second check). and again for hyperrectangles this equality check can be made very efficient

Benoît Legat
@blegat
@mforets The advantage of JuMP is that it will automatically add needed caching and bridges layers
Christian Schilling
@schillic

@blegat while you are here: i cannot get MOI to work with Rationals. what is wrong here?

using GLPK, MathOptInterface
const MOI = MathOptInterface
N = Rational{Int}
solver = GLPK.Optimizer(method=GLPK.EXACT)
x = MOI.add_variables(solver, 1)
MOI.set(solver, MOI.ObjectiveSense(), MOI.FEASIBILITY_SENSE)
a = MOI.ScalarAffineFunction(MOI.ScalarAffineTerm.(N[1], x), N(0))
b = MOI.LessThan(N(0))
MOI.add_constraint(solver, a, b)

this throws an error:

ERROR: MathOptInterface.UnsupportedConstraint{MathOptInterface.ScalarAffineFunction{Rational{Int64}},MathOptInterface.LessThan{Rational{Int64}}}: `MathOptInterface.ScalarAffineFunction{Rational{Int64}}`-in-`MathOptInterface.LessThan{Rational{Int64}}` constraint is not supported by the model.

note that for N = Float64 this works

this is the LP (no objective) s.t. x <= 0
Christian Schilling
@schillic
hm, it seems that GLPK does not support adding Rational constraints at all