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


A Simplified Convergence Proof for the Cone Partitioning Algorithm


We present a new convergence result for the cone partitioning algorithm with a pure -subdivision strategy, for the minimization of a quasiconcave function over a polytope. It is shown that the algorithm is finite when -optimal solution with > 0 are looked for, and that any cluster point of the points generated by the algorithm is an optimal solution in the case = 0. This result improves on the one given previously by the authors, and its proof is simpler and relies more directly on a new class of hyperplanes and its associated simplicial lower bound.

, 14 pages