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

G-97-48

On Tuy's 1964 Cone Splitting Algorithm for Concave Minimization

Since the work of Zwart, it is known that cycling may occur in the cone splitting algorithm proposed by Tuy in 1964 to minimize a concave function over a polytope. In this paper, we show that despite this fact, Tuy's algorithm is convergent in the sense that it always finds an optimal solution. This is also true for a variant of Tuy's algorithm proposed by Gallo, in which a cone is split into a smaller subset of subcones (in term of inclusion). We show on an example that this variant may also cycle. The transformation of both algorithms into finite ones is discussed.

, 21 pages

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