Groupe d’études et de recherche en analyse des décisions


On the Convergence of Cone Splitting Algorithms with -Subdivisions


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

Ce cahier a été révisé en octobre 1998