Optimization Online


Global optimization of rational functions: a semidefinite programming approach

Dorina Jibetean (D.Jibetean***at***cwi.nl)
Etienne De Klerk (E.deKlerk***at***its.tudelft.nl)

Abstract: We consider the problem of global minimization of rational functions on $\LR^n$ (unconstrained case), and on an open, connected, semi-algebraic subset of $\LR^n$, 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. This extends the analogous results by Nesterov 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. For the NP-hard multivariate case, we discuss semidefinite programming-based relaxations for obtaining lower bounds on the infimum, by using results by Parrilo, and Lasserre.

Keywords: Semidefinite programming, global optimization, rational functions, positive polynomials

Category 1: Global Optimization (Theory )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Nonlinear Optimization

Citation: CWI report CWI, Amsterdam, The Netherlands

Download: [Postscript][PDF]

Entry Submitted: 05/13/2003
Entry Accepted: 05/13/2003
Entry Last Modified: 05/13/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society