Convex and concave envelopes: Revisited and new perspectives

We discuss two approaches to approximate the convex and concave envelopes of bilinear functions over hypercubes. The first approach is based on a semidefinite program. The second approach considers some predefined cover sets of a hypercube and leads to a linear program. Then we establish a connection between the convex envelope of a bilinear function and the concave envelope of a piecewise linear function. Numerical experiments are conducted to compare the two approaches. As an extension, a novel approach is discussed.