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

G-98-70

A New Finite Cone Covering Algorithm for Concave Minimization

et

We propose a new finite cone covering algorithm for concave minimization over a polytope, in which the cones are defined by extreme points of the polytope. The main novelties are the use of cones defined by an arbitrary number of edges, and the subdivision process. This latter is shown to have a "descent property", i.e., all subcones are strictly better in some sense than the subdivided cone, which eliminates the possibility of cycling. The main task in the subdivision process consists in expressing a given point of a face of the polytope as a convex combination of extreme points of this face.

, 15 pages