Global optimization of rational functions : a semidefinite programming approach

D. Jibetean, E. Klerk, de

Research output: Contribution to journalArticleAcademicpeer-review

43 Citations (Scopus)

Abstract

We consider the problem of global minimization of rational functions on (unconstrained case), and on an open, connected, semi-algebraic subset of , or the (partial) closure of such a set (constrained case). We show that in the univariate case (n = 1), these problems have exact reformulations as semidefinite programming (SDP) problems, by using reformulations introduced in the PhD thesis of Jibetean [16]. This extends the analogous results by Nesterov [13] for global minimization of univariate polynomials. For the bivariate case (n = 2), we obtain a fully polynomial time approximation scheme (FPTAS) for the unconstrained problem, if an a priori lower bound on the infimum is known, by using results by De Klerk and Pasechnik [1]. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo [15], and Lasserre [12].
Original languageEnglish
Pages (from-to)93-109
JournalMathematical Programming
Volume106
Issue number1
DOIs
Publication statusPublished - 2006

Fingerprint Dive into the research topics of 'Global optimization of rational functions : a semidefinite programming approach'. Together they form a unique fingerprint.

Cite this