One of the main reasons for the interest in convex envelopes is the fact that the set of global minimum points of f on S is contained in the set of global minimum points of conv_S(f) on S and the two minimum values coincide (see, e.g., [11, 17]). Hence, if the convex envelope were efficiently computable or available in closed form, one could replace the nonconvex problem of minimizing f on S with the convex problem of minimizing f on conv_S(f).