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.
Published July 1996 , 22 pages
This cahier was revised in October 1998