Minimizing Polynomial Functions

Abstract

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

Cited by in corpus (28)

• Prime factorization using quantum annealing and computational algebraic geometry
• Reliable Graph Neural Networks via Robust Aggregation
• Solving Fractional Polynomial Problems by Polynomial Optimization Theory
• Fast minimization of structured convex quartics
• Bounding Multivariate Trigonometric Polynomials with Applications to Filter Bank Design
• Structured Semidefinite Representation of Some Convex Sets
• Exact relaxation for polynomial optimization on semi-algebraic sets
• Semidefinite Representation of Convex Sets
• A convex data-driven approach for nonlinear control synthesis
• An Exact Jacobian SDP Relaxation for Polynomial Optimization
• Discriminants and Nonnegative Polynomials
• Linear Optimization with Cones of Moments and Nonnegative Polynomials
• Radii minimal projections of polytopes and constrained optimization of symmetric polynomials
• Unconstraint global polynomial optimization via Gradient Ideal
• Sparse SOS Relaxations for Minimizing Functions that are Summations of Small Polynomials
• Minimizing Polynomials via Sum of Squares over the Gradient Ideal
• A Semidefinite Representation for some Minimum Cardinality Problems
• Certifying Convergence of Lasserre's Hierarchy via Flat Truncation
• The Hierarchy of Local Minimums in Polynomial Optimization
• Tight Relaxations for Polynomial Optimization and Lagrange Multiplier Expressions
• On Flattenability of Graphs
• Regularization Methods for SDP Relaxations in Large Scale Polynomial Optimization
• Primal-dual interior-point Methods for Semidefinite Programming from an algebraic point of view, or: Using Noncommutativity for Optimization
• Algebraic Degree of Polynomial Optimization
• Decomposition Methods for Nonlinear Optimization and Data Mining
• Noise threshold for universality of 2-input gates
• Approximating the maximum of a polynomial over a polytope: Handelman decomposition and continuous generating functions
• Sum of Squares Method for Sensor Network Localization