Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Global optimization of rational functions using semidefinite programming

Joint work with Dorina Jibetean (CWI, Amsterdam)// We consider the problem of global minimization of rational functions on R^n (unconstrained case), or on a connected semi-algebraic subset of R^n. We show that in the univariate case (n=1), these problems have exact reformulations as semidefinite programming problems (SDP), by using reformulations introduced by Jibetean (2001). This extends the analogous results by Nesterov (2000) 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 (2002). For the NP-hard multivariate case, we discuss semidefinite programming-based heuristics for obtaining lower bounds on the infimum, by using results by Lasserre (2001). References E. de Klerk, D.V. Pasechnik (2002). Products of positive forms, linear matrix inequalities, and Hilbert 17-th problem for ternary forms. European J. of Operational Research, to appear. D. Jibetean. Global optimization of rational multivariate functions. Technical Report PNA-R0120, CWI, Amsterdam, 2001. J. Lasserre. Global optimization with polynomials and the problem of moments. SIAM J.Optim., 11(3):796--817, 2001. Y. Nesterov. Squared functional systems and optimization problems. In H. Frenk, K. Roos, and T. Terlaky, editors, High Performance Optimization, pages 405--439, Dordrecht, 2000. Kluwer Academic Publishers.

Type of Seminar:
Public Seminar
Prof. Etienne de Klerk
Delft University of Technology, The Netherlands
May 19, 2003   11:15

ETH Zentrum, Physikstr.3, Building ETL, Room K25
Contact Person:

Prof. P. Parrilo
File Download:

Request a copy of this publication.
Biographical Sketch:
Etienne de Klerk is an assistant professor at the Delft University of Technology in the Netherlands. In September 2003 he will take up a position as associate professor at the Department of Combinatorics and Optimization in the Faculty of Mathematics at the University of Waterloo, Canada. His research interests are: Semidefinite and Cone programming, Approximation Algorithms for Combinatorial and Global Optimization, and Interior Point Algorithms. Dr. De Klerk is the author of the monograph Aspects of Semidefinite Programming: Interior Point Algorithms and selected Applications.