A survey of methodology for the global minimization of concave functions subject to convex constraints

Methodology is described for the global solution to problems of the form minimize f(x) subject to x[set membership, variant]G, ui [greater-or-equal, slanted] xi [greater-or-equal, slanted] li where f(x) is a concave function of the vector x in Rn space and G is a convex polytope. This paper investigates recent work accomplished to solve this problem. Basically, solution algorithms can be categorized into three distinct areas: (1) branch-and-bound methods, (2) cutting plane methods, and (3) build-up of polyhedra methods. Computational experience with these methods is also examined. Particular attention is paid to the possibility for extension of these algorithms to problems of large scale, specifically to those evidencing separable objective functions which are subject to linear sets of constraints.