Semidefinite relaxations of fractional programs via novel convexification techniques

In a recent work, we introduced the concept of convex extensions for lower semi-continuous functions and studied their properties. In this work, we pr esent new techniques for constructing convex and concave envelopes of nonli near functions using the theory of convex extensions. In particular, we dev elop the convex envelope and concave envelope of z=x/y over a hypercube. We show that the convex envelope is strictly tighter than previously known co nvex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting re laxation is shown to be a semidefinite program. Finally, we derive the conv ex envelope for a class of functions of the type f(x,y) over a hypercube un der the assumption that f is concave in x and convex in y.