Retour

G-96-36

On the Convergence of Cone Splitting Algorithms with -Subdivisions

et

référence BibTeX

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