Convex-Concave Extensions

In this paper we introduce a new notion which we call convex-concave extensions. Convex-concave extensions provide for given nonlinear functions convex lower bound functions and concave upper bound functions, and can be viewed as a generalization of interval extensions. Convex-concave extensions can approximate the shape of a given function in a better way than interval extensions which deliver only constant lower and upper bounds for the range. Therefore, convex-concave extensions can be applied in a more flexible manner. For example, they can be used to construct convex relaxations. Moreover, it is demonstrated that in many cases the overestimation which is due to interval extensions can be drastically reduced. Applications and some numerical examples, including constrained global optimization problems of large scale, are presented.