On convex envelopes and underestimators for bivariate functions

Marco Locatelli (locatellce.unipr.it)
Fabio Schoen (fabio.schoenunifi.it)

Abstract: In this paper we discuss convex underestimators for bivariate functions. We first present a method for deriving convex envelopes over the simplest two-dimensional polytopes, i.e., triangles. Next, we propose a technique to compute the value at some point of the convex envelope over a general two-dimensional polytope, together with a supporting hyperplane of the convex envelope at that point. Noting that the envelopes might be of quite complicated form and their computation not easy, we move later on to the discussion of a method, based on the solution of a semidefinite program, to derive convex underestimators (not necessarily convex envelopes) of simple enough form for bivariate quadratic functions over general two-dimensional polytopes.

Keywords: convex envelopes, convex underestimators, semidefinite programming, quadratic problems

Category 1: Global Optimization

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation:

Download: [PDF]

Entry Submitted: 11/17/2009
Entry Accepted: 11/17/2009
Entry Last Modified: 04/28/2010

Modify/Update this entry