Global Optimization of Concave Functions Subject to Separable Quadratic Constraints and of All-Quadratic Separable Problems

Abstract : This paper proposes different methods for finding the global minimum of concave function subject to quadratic separable constraints. THe first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.