Concave Minimization Via Collapsing Polytopes

James E. Falk and Karla L. Hoffman
Additional contact information
James E. Falk: The George Washington University, Washington, D.C.
Karla L. Hoffman: National Bureau of Standards, Gaithersburg, Maryland

Operations Research, 1986, vol. 34, issue 6, 919-929

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 (search for similar items in EconPapers)
Date: 1986
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.34.6.919 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:34:y:1986:i:6:p:919-929

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().