Concave Minimization Via Collapsing Polytopes

Operations Research · 1986 · Volume 34 · Issue 6

Abstract

We present a procedure for globally minimizing a concave function over a (bounded) polytope by successively minimizing the function over polytopes containing the feasible region, and collapsing to the feasible region. The initial containing polytope is a simplex, and, at the k th iteration, the procedure chooses the most promising vertex of the current containing polytope to refine the approximation. The method generates a tree whose ultimate terminal nodes coincide with the vertices of the feasible region, and accounts for the vertices of the containing polytopes.

Keywords

625 globally minimizing concave functions over polytopes, 627 implicit enumeration of vertices

Enable JavaScript for citation tools and additional paper interactions.