On the global minimization of concave functions (Q800693)

Many important classes of decision models give rise to the problem of finding a global minimum of a concave function over a convex set. Since many local minima can occur, concave minimization belongs to the ''hard'' global optimization problems, where standard nonlinear programming procedures fail. After a brief survey on important specific classes of decision models that can be formulated as concave minimization problems, two main solution approaches for the general concave problem are discussed: branch-and-bound combined with convex underestimation and outer approximation by cutting planes. It should be noted that in the meantime a much more general and flexible branch-and-bound procedure is available [cf. the author, A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization. Discussion Paper, Fachbereich Mathematik/Informatik, Universität Oldenburg].