Minimizing Polynomial Functions

By Pablo A. Parrilo, Bernd Sturmfels. Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science, 2001

383 citations recorded by the source corpus.

We compare algorithms for global optimization of polynomial functions in many variables. It is demonstrated that existing algebraic methods (Gr\"obner 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.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/35b5cf323dace59b24ee515877feae8cd4a3c67a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Analysis of Non-polynomial Systems using the Sum of Squares Decomposition (2005, background): “A more detailed description can be found in [10, 11] and the references therein.”
Parametric optimization and optimal control using algebraic geometry methods (2006, methodology): “Various methods have been proposed in the literature for solving systems of polynomial equations, both numerical and symbolic (Sturmfels, 2002), (Parrilo and Sturmfels, 2000), (Manocha, 1994).”
A tutorial on sum of squares techniques for systems analysis (2005, background): “A more detailed description can be found in [34], [36] and the references therein.”
Geometric median in nearly linear time (2016, methodology): “Parrilo and Sturmfels demonstrated that the problem can be reduced to semidefinite programming, thus obtaining a runtime of Õ(poly(n, d) log −1) [24].”
POSITIVE POLYNOMIALS IN SCALAR AND MATRIX VARIABLES, THE SPECTRAL THEOREM AND OPTIMIZATION (2006, background): “Parrilo and Sturmfels [PS03] reported experiments with a special class of 10,000 polynomials for which the true global minimum could be computed explicitly.”
Obstructions to determinantal representability (2010, methodology): “In two variables such sets were characterized by Helton and Vinnikov [7] by so called rigidly convex sets, thereby answering a question posed by Parrilo and Sturmfels [14].”
Nonlinear control synthesis by sum of squares optimization: a Lyapunov-based approach (2004, background): “Even though the sum of squares condition is not necessary for nonnegativity, numerical experiments seem to indicate that the gap between sum of squares and nonnegativity is small [16].”
Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals (2007, methodology): “This can then be implemented as a semidefinite program (SDP), and solved numerically [18,22].”
Matrix Sum-of-Squares Relaxations for Robust Semi-Definite Programs (2006, methodology): “In contrast to approaches based on scalarization and a subsequent application of existing relaxation techniques [21, 24 , 36], we will be able to show that the size of the constructed LMI relaxations grow at most bi-quadratically in the dimension p of F(x, y) and q of G(x) respectively.”
Representations of Non-Negative Polynomials, Degree Bounds and Applications to Optimization (2009, methodology): “In [12], f∗ is approximated by computing fsos in a large number of random instances with fm = x m 1 + · · · + x n .”
Optimization of Polynomial Functions (2003, methodology): “(3) In the test examples considered by Parrilo and Sturmfels in [ 11 ], f is stably bounded below on Rn. In all these examples exact results are obtained without”
Complete search in continuous global optimization and constraint satisfaction (2004, background): “…and De Klerk (2003), Fujie and Kojima (1997), Kim and Kojima (2001, 2003), Kim, Kojima and Waki (2003), Kojima, Kim and Waki (2003), Kojima and Tuncel (2000), Lasserre (2001), Meziat (2003), Gatermann and Parrilo (2004), Parrilo (2003), Parrilo and Lall (2003), Parrilo and Sturmfels (2003).”
Sums of Squares, Moment Matrices and Optimization Over Polynomials (2009, background): “As the polynomial optimization problem (1.1) is NP-hard, several authors, in particular Lasserre [65–67], Nesterov [95], Parrilo [103, 104], Parrilo and Sturmfels [107], Shor [138–141], have proposed to approximate the problem (1.1) by a hierarchy of convex (in fact, semidefinite) relaxations.”