Semidefinite Relaxations of Fractional Programs via Novel Convexification Techniques

Mohit Tawarmalani, Nikolaus V. Sahinidis

Research output: Contribution to journalArticlepeer-review


In a recent work, we introduced the concept of convex extensions for lower semi-continuous functions and studied their properties. In this work, we present new techniques for constructing convex and concave envelopes of nonlinear functions using the theory of convex extensions. In particular, we develop 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 convex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting relaxation is shown to be a semidefinite program. Finally, we derive the convex envelope for a class of functions of the type f (x, y) over a hypercube under the assumption that f is concave in x and convex in y.

Original languageEnglish (US)
Pages (from-to)137-158
Number of pages22
JournalJournal of Global Optimization
Issue number2
StatePublished - Jun 2001


  • Convex envelopes
  • Convex Extensions
  • Disjunctive Programming
  • Fractional Programs
  • Semidefinite Relaxations

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'Semidefinite Relaxations of Fractional Programs via Novel Convexification Techniques'. Together they form a unique fingerprint.

Cite this