A branch and bound-outer approximation algorithm for concave minimization over a convex set (Q757243)

The authors consider a concave minimization problem (P): minimize f(x), subject to g(x)\(\leq 0\), where f is a concave, not necessarily separable, function on \(R^ n\), and \(g(x)=(g_ 1(x),...,g_ m(x))\). The authors propose a new algorithm for solving P which uses branch and bound and outer approximation, and is guaranteed to converge to a globally optimal solution. One of the major advantages of the algorithm is that the only significant nonlinear computation required at each iteration can be accomplished by any of a number of simple univariate search procedures. The only other major computations required involve solving either linear programming problems or systems of \((n+1)\) equations in \((n+1)\) unknowns which each have a unique solution.