Approximating the maximum of a polynomial over a polytope: Handelman decomposition and\n continuous generating functions

2016/01/15 by Jesús A. De Loera, De Loera, Jesús, Brandon Dutra +3
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Complexity and Algorithms in Graphs #FOS: Mathematics #Machine Learning and Algorithms #Numerical Methods and Algorithms #Optimization and Control (math.OC) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.1601.04118

openalex publication_date 2016/01/15 · openalex created_date 2022/09/14 · openalex updated_date 2026/08/01

Abstract

We investigate a way to approximate the maximum of a polynomial over a polytopal\n region by using Handelman's polynomial decomposition and continuous multivariate generating\n functions. The maximization problem is NP-hard, but our approximation methods will run in\n polynomial time when the dimension is fixed.

Citations

• Semidefinite programming relaxations for semialgebraic problems
• A polyhedral branch-and-cut approach to global optimization
• On the Alexander-Hirschowitz Theorem

Related

• Decomposition Methods for Nonlinear Optimization and Data Mining
• Handelman's hierarchy for the maximum stable set problem
• Poising on Ariadne's thread: An algorithm for computing a maximum clique in polynomial time
• Extended formulations for the multilinear polytope of acyclic hypergraphs
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex