CONSTRAINT DECOMPOSITION ALGORITHMS IN GLOBAL OPTIMIZATION

Many global optimization problems can be formulated in the form min{c(x, y): x is-an-element-of X, y is-an-element-of Y, (x, y) is-an-element-of Z, y is-an-element-of G} where X, Y are polytopes in R(p), R(n), respectively, Z is a closed convex set in R(p+n), while G is the complement of an open convex set in R(n). The function c:R(p+n) --> R is assumed to be linear. Using the fact that the nonconvex constraints depend only upon the y-variables, we modify and combine basic global optimization techniques such that some new decomposition methods result which involve global optimization procedures only in R(n). Computational experiments show that the resulting algorithms work well for problems with small n.