search

JuliaReach / LazySets.jl

Scalable symbolic-numeric set computations in Julia
https://juliareach.github.io/LazySets.jl/
Other
227 stars 32 forks source link

Intersection of a halfspace with a polyhedron #375

Closed mforets closed 5 years ago

mforets commented 6 years ago

http://spaceex.imag.fr/sites/default/files/frehser_adhs2012.pdf https://sites.google.com/site/frehseg/publications/Frehse_Habil16.pdf

cc: @kostakoida

mforets commented 5 years ago

The support function along direction ℓ of the intersection of a halfspace with normal direction a and displacement b and a convex polytope X can be reformulated as the problem of finding the minimum of the univariate function f(λ) = ρ(ℓ - λ * a, X) + λ * b over non-negative λ (refer to the references for details).

  1. I've tried Optim and it does a good job in some 2D examples. I took LBFGS but i'm not sure if it is the more appropriate method for our problem; given the fact that the gradient is not provided (eg. try with Nelder-Mead).

  2. In [Sec. 2.3 Frehse & Ray] they develop a sandwich algorithm based on a lower bound search.

  3. In [Le Guernic, Girard, 2009] the authors rewrite f(λ) as a function on the finite interval (0, pi). The method of solution is called golden section search in the polar decomposition.

The current proposal is to do 1 for which i have the code, and then consider 2 or 3 as optional "algorithms".

schillic commented 5 years ago

Do we want to keep the other methods described above as a reminder in a new issue?