On the Convergence of Cone Splitting Algorithms with -Subdivisions


BibTeX reference

We present a convergence proof of Tuy's cone splitting algorithm with a pure -subdivision strategy, for the minimization of a concave function over a polytope. The key idea of the convergence proof is to associate with the current hyperplane one that supports the whole polytope instead of only the portion of it contained in the current cone. A branch-and-bound variant of the algorithm is also discussed.

, 22 pages

This cahier was revised in October 1998