Intersection of a halfspace with a polyhedron

[mforets]

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

cc: @kostakoida

[mforets]

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]

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