Minimizing Polynomial Functions

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We compare algorithms for global optimization of polynomial functions in many variables. It is demonstrated that existing algebraic methods (Gröbner bases, resultants, homotopy methods) are dramatically outperformed by a relaxation technique, due to N.Z. Shor and the first author, which involves sums of squares and semidefinite programming. This opens up the possibility of using semidefinite programming relaxations arising from the Positivstellensatz for a wide range of computational problems in real algebraic geometry. This paper was presented at the Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, held at DIMACS, Rutgers University, March 12-16, 2001.
This paper was presented at the Workshop on Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, held at DIMACS, Rutgers University, March 12-16, 2001

Keywords

Optimization and Control, Commutative Algebra, Algebraic Geometry, 13J30, 90C22, 13P10, 65H10

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/61143

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0103170
 http://arxiv.org/abs/math/0103170
 Algorithmic and quantitative real algebraic geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 60, pp. 83--99, AMS, 2003. ISBN: 0-8218-2863-0.

Collections

arXiv