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

AbstractThis article presents a new algorithm for solving the problem of globally minimizing a concave function over a compact, convex set. The algorithm uses both branch and bound and outer approximation. One of the major advantages of the algorithm is that the only significant nonlinear computation required can be accomplished using univariate search procedures. After establishing the convergence of the algorithm, we discuss this and other computational considerations. A small example is solved to illustrate the algorithm. Because of its advantages, the algorithm offers significant promise for efficiently minimizing a concave function over a compact, convex set