Concave Minimization via Collapsing Polytopes.

摘要

The global minimization of a concave function over a (bonded) polytope is accomplished 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 kth iteration, the most promising vertex of the current containing polytope is chosen to refine the approximation. A tree whose ultimate terminal nodes coincide with the vertices of the feasible region is generated, and accounts for the vertices of the containing polytopes. (Author)