Minimizing Polynomial Functions

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.

• Publication year

  2001

• Venue

  Algorithmic and Quantitative Aspects of Real Algebraic Geometry in Mathematics and Computer Science

• Publication date

  2001-03-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1090/dimacs/060/08arXiv math/0103170
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Semidefinite programming

  2002cited by this paper
• Handbook of Semidefinite Programming

  2000cited by this paper
• Computer algebra methods for equivariant dynamical systems

  2000cited by this paper
• Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization

  2000cited by this paper
• A new efficient algorithm for computing Grbner bases ( F 4)

  1999cited by this paper
• Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation

  1999cited by this paper
• Polynomial Homotopies for Dense, Sparse and Determinantal Systems

  1999cited by this paper
• An algorithm for sums of squares of real polynomials

  1998cited by this paper
• Ideals, Varieties, and Algorithms

  1997influential reference
• SOME CONCRETE ASPECTS OF HILBERT'S 17TH PROBLEM

  1996cited by this paper
• Gröbner bases and convex polytopes

  1995cited by this paper
• Discriminants, Resultants, and Multidimensional Determinants

  1994influential reference
• Computational Synthetic Geometry

  1989cited by this paper
• Representing polynomials by positive linear functions on compact convex polyhedra.

  1988cited by this paper
• Even symmetric sextics

  1987cited by this paper
• Class of global minimum bounds of polynomial functions

  1987cited by this paper

• Sufficiently Regularized Nonnegative Quartic Polynomials are Sum-of-Squares

  2026influential citation
• Certificates for nonnegativity of multivariate integer polynomials under perturbations

  2025cites this paper
• Generalized collective quantum tomography: algorithm design, optimization, and validation

  2025cites this paper
• SoS1: O1 and R1-Like Reasoning LLMs are Sum-of-Square Solvers

  2025cites this paper
• A novel exact approach to polynomial optimization

  2025cites this paper
• Efficient Polynomial Sum-Of-Squares Programming for Planar Robotic Arms

  2024cites this paper
• Constraint-Aware Refinement for Safety Verification of Neural Feedback Loops

  2024cites this paper
• CaΣoS: A nonlinear sum-of-squares optimization suite⋆

  2024influential citation
• Simultaneous quantum state and detector tomography through multiple Hamiltonians

  2024cites this paper
• Extreme points of matrix convex sets and their spanning properties

  2024cites this paper
• Byzantine Machine Learning: A Primer

  2023cites this paper
• A Fast and Reliable Solution to PnP, Using Polynomial Homogeneity and a Theorem of Hilbert

  2023cites this paper
• Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs

  2023cites this paper
• Energy consumption control in the two-machine Bernoulli serial production line with setup and idleness

  2023cites this paper
• Data-driven optimal control via linear transfer operators: A convex approach

  2023cites this paper
• The Rado multiplicity problem in vector spaces over finite fields

  2023influential citation
• Computing local minimizers in polynomial optimization under genericity conditions

  2023cites this paper
• Subdivision Methods for Sum-Of-Distances Problems: Fermat-Weber Point, n-Ellipses and the Min-Sum Cluster Voronoi Diagram (Media Exposition)

  2022cites this paper
• Data-Driven Optimal Control via Linear Transfer Operators: A Convex Approach

  2022cites this paper
• Atypical points at infinity and algorithmic detection of the bifurcation locus of real polynomials

  2021cites this paper
• Global Certificates of Positivity

  2021cites this paper
• Noncommutative polynomial optimization under symmetry

  2021cites this paper
• Certified Approximation Algorithms for the Fermat Point and n-Ellipses

  2021cites this paper
• A computational algebraic geometry technique for determining nonlinear normal modes of structural systems

  2021cites this paper
• Wiener path integral most probable path determination: A computational algebraic geometry solution treatment

  2021cites this paper
• Reachability Analysis of Neural Feedback Loops

  2021cites this paper
• The Non-Tightness of a Convex Relaxation to Rotation Recovery

  2021cites this paper
• Sum of Squares based Convex Approach for Optimal Control Synthesis

  2021cites this paper
• Sum‐of‐squares‐based policy iteration for suboptimal control of polynomial time‐varying systems

  2021cites this paper
• Positive Polynomials with Special Structure

  2021cites this paper
• New applications in chemometrics

  2020cites this paper
• Control analysis and design via randomised coordinate polynomial minimisation

  2020cites this paper
• Combining Prior Knowledge and Data for Robust Controller Design

  2020cites this paper
• Polynomial-Based Linear Programming Relaxation of Sensor Network Localization Problem

  2020cites this paper
• A convex data-driven approach for nonlinear control synthesis

  2020cites this paper
• Atypical points at infinity and algorithmic detection of the bifurcation locus of real polynomials

  2020cites this paper
• Reliable Graph Neural Networks via Robust Aggregation

  2020cites this paper
• Certified Approximation Algorithms for the Fermat Point

  2020cites this paper
• Highly smooth minimization of non-smooth problems

  2020cites this paper
• Branch-and-Bound Ranked Search by Minimizing Parabolic Polynomials

  2020cites this paper
• Efficient Higher-Order Optimization for Machine Learning

  2019cites this paper
• Polynomial-Based Methods for Localization in Multiagent Systems

  2019cites this paper
• Random Coordinate Minimization Method with Eventual Transverse Directions for Constrained Polynomial Optimization

  2019cites this paper
• Convexification of box-constrained polynomial optimization problems via monomial patterns

  2019cites this paper
• Minimizing polynomial functions on quantum computers

  2019cites this paper
• On Sum of Squares Representation of Convex Forms and Generalized Cauchy-Schwarz Inequalities

  2019cites this paper
• Stochastic polynomial optimization

  2019cites this paper
• Convex Algebraic Geometry of Curvature Operators

  2019cites this paper
• Coercive polynomials: stability, order of growth, and Newton polytopes

  2019cites this paper
• Unbounded convex polyhedra as polynomial images of Euclidean spaces

  2019cites this paper
• On the domain of attraction and local stabilization of nonlinear parameter‐varying systems

  2019cites this paper
• Automated Reasoning for Systems Biology and Medicine

  2019cites this paper
• Complements of Unbounded Convex Polyhedra as Polynomial Images of $${{\mathbb {R}}}^n$$Rn

  2019cites this paper
• Optimality

  2019cites this paper
• On stability and the Łojasiewicz exponent at infinity of coercive polynomials

  2019cites this paper
• Set-Based Analysis for Biological Modeling

  2019cites this paper
• Best Nonnegative Rank-One Approximations of Tensors

  2018cites this paper
• Block SOS Decomposition

  2018cites this paper
• Fast Interpolation and Fourier Transform in High-Dimensional Spaces

  2018cites this paper
• A Novel Algebraic Geometry Compiling Framework for Adiabatic Quantum Computations

  2018cites this paper
• Fast minimization of structured convex quartics

  2018influential citation
• The Saddle Point Problem of Polynomials

  2018cites this paper
• ECONOMIC-EMISSION DISPATCH WITH SEMIDEFINITE PROGRAMMING AND RATIONAL FUNCTION APPROXIMATIONS

  2018cites this paper
• Nonnegative Polynomials and Circuit Polynomials

  2018cites this paper
• On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems

  2018cites this paper
• Optimization over Nonnegative and Convex Polynomials With and Without Semidefinite Programming

  2018cites this paper
• Bounding Multivariate Trigonometric Polynomials

  2018cites this paper
• A Variation on a Random Coordinate Minimization Method for Constrained Polynomial Optimization

  2018influential citation
• A MULTIGRID APPROACH TO SDP RELAXATIONS OF SPARSE

  2018cites this paper
• A New Sparse SOS Decomposition Algorithm Based on Term Sparsity

  2018cites this paper
• Solving Non-smooth Constrained Programs with Lower Complexity than 𝒪(1/ε): A Primal-Dual Homotopy Smoothing Approach

  2018cites this paper
• Logic synthesis for energy-efficient photonic integrated circuits

  2018cites this paper
• Multivariate Newton Interpolation

  2018cites this paper
• Primal-dual interior-point Methods for Semidefinite Programming from an algebraic point of view, or: Using Noncommutativity for Optimization.

  2018cites this paper
• Solving Fractional Polynomial Problems by Polynomial Optimization Theory

  2018influential citation
• Estimate of the Domain of Attraction for Polynomial Systems Using Bisectional Sum-of-Squares Optimization

  2018cites this paper
• Exploiting Sparsity in SOS Programming and Sparse Polynomial Optimization

  2018cites this paper
• Model updating using sum of squares (SOS) optimization to minimize modal dynamic residuals

  2017cites this paper
• Definite determinantal representations of multivariate polynomials

  2017cites this paper
• LP relaxations for a class of linear semi-infinite programming problems

  2017cites this paper
• Efficient Spherical Designs with Good Geometric Properties

  2017cites this paper
• Geometric and algebraic approaches to mixed-integer polynomial optimization using sos programming

  2017cites this paper
• Norm bounds and underestimators for unconstrained polynomial integer minimization

  2017cites this paper
• Robust consensus for a class of uncertain multi-agent systems

  2017cites this paper
• A state space world for detecting and estimating events and learning sparse signal decompositions

  2017cites this paper
• DC decomposition of nonconvex polynomials with algebraic techniques

  2017cites this paper
• Autonomous state space models for recursive signal estimation beyond least squares

  2017cites this paper
• Polynomial , regular and Nash images of Euclidean spaces

  2017cites this paper
• Generic Properties for Semialgebraic Programs

  2017cites this paper
• Tight relaxations for polynomial optimization and Lagrange multiplier expressions

  2017cites this paper
• Geometric median in nearly linear time

  2016cites this paper
• On Newton polytopes and growth properties of multivariate polynomials

  2016influential citation
• Prime factorization using quantum annealing and computational algebraic geometry

  2016cites this paper
• Decomposition Methods for Nonlinear Optimization and Data Mining

  2016cites this paper
• An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming

  2016cites this paper
• PHCpack Documentation Release 2.4.30

  2016cites this paper
• Monomial-wise optimal separable underestimators for mixed-integer polynomial optimization

  2016cites this paper
• Sufficient conditions for a real polynomial to be a sum of squares of polynomials

  2016cites this paper
• Nonnegative Morse polynomial functions and polynomial optimization

  2016cites this paper
• Maximally entangled mixed states for qubit-qutrit systems

  2016cites this paper