M. Tawarmalani et Nv. Sahinidis, Semidefinite relaxations of fractional programs via novel convexification techniques, J GLOB OPT, 20(2), 2001, pp. 137-158
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.