Convex envelopes for quadratic and polynomial functions over polytopes

In this paper we consider the problem of computing the value and a supporting hyperplane of the convex envelope for quadratic and polynomial functions over polytopes with known vertex set. We show that for general quadratic functions the computation can be carried on through a copositive problem, but in some cases (including all the two-dimensional ones) we can solve a semidefinite problem. The result is also extended to two-dimensional polynomial functions satisfying certain conditions.

Article

Download

View Convex envelopes for quadratic and polynomial functions over polytopes