A PTAS for the minimization of polynomials of fixed degree over the simplex

DOI10.1016/J.TCS.2006.05.011zbMath1115.90042OpenAlexW2114650657WikidataQ101511646 ScholiaQ101511646MaRDI QIDQ2503350

Pablo A. Parrilo, Monique Laurent, Etienne de Klerk

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.05.011

zbMATH Keywords

global optimizationsemidefinite programmingapproximation algorithmpositive polynomialsum of squares of polynomials

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Numerical methods of relaxation type (49M20)

Related Items (42)

On the accuracy of uniform polyhedral approximations of the copositive cone ⋮ Proximity in concave integer quadratic programming ⋮ On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming ⋮ On the copositive representation of binary and continuous nonconvex quadratic programs ⋮ A linear programming reformulation of the standard quadratic optimization problem ⋮ Approximation algorithms for homogeneous polynomial optimization with quadratic constraints ⋮ Improved approximation results on standard quartic polynomial optimization ⋮ Approximation algorithm for a class of global optimization problems ⋮ On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity ⋮ (Global) optimization: historical notes and recent developments ⋮ Convergence of the Simplicial Rational Bernstein Form ⋮ An approximation algorithm for indefinite mixed integer quadratic programming ⋮ Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems ⋮ Improved Approximation Guarantees through Higher Levels of SDP Hierarchies ⋮ New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability ⋮ On the complexity of optimization over the standard simplex ⋮ A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ A refined error analysis for fixed-degree polynomial optimization over the simplex ⋮ LP Formulations for Polynomial Optimization Problems ⋮ The complexity of optimizing over a simplex, hypercube or sphere: a short survey ⋮ FPTAS for optimizing polynomials over the mixed-integer points of polytopes in fixed dimension ⋮ Impossibility of extending Pólya's theorem to ``forms with arbitrary real exponents ⋮ Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization ⋮ On the convergence rate of grid search for polynomial optimization over the simplex ⋮ A continuous characterization of the maximum vertex-weighted clique in hypergraphs ⋮ Rounding on the standard simplex: regular grids for global optimization ⋮ Subdeterminants and Concave Integer Quadratic Programming ⋮ On approximation algorithms for concave mixed-integer quadratic programming ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ Near-optimal analysis of Lasserre's univariate measure-based bounds for multivariate polynomial optimization ⋮ Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution ⋮ Complexity results for some global optimization problems ⋮ A generalization of the Motzkin-Straus theorem to hypergraphs ⋮ Convergence rates of RLT and Lasserre-type hierarchies for the generalized moment problem over the simplex and the sphere ⋮ An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution ⋮ Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems ⋮ On an extension of Pólya's Positivstellensatz ⋮ Completely positive reformulations for polynomial optimization ⋮ An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex ⋮ Exploiting symmetry in copositive programs via semidefinite hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure preserving reductions among convex optimization problems
• The \(K\)-moment problem for compact semi-algebraic sets
• An algorithm for sums of squares of real polynomials
• Semidefinite programming relaxations for semialgebraic problems
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Uniform denominators in Hilbert's seventeenth problem
• The complexity of approximating a nonlinear program
• Sums of even powers of real linear forms
• An analysis of approximations for maximizing submodular set functions—I
• On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
• On a Class of Finite Elements Generated by Lagrange Interpolation
• Maxima for Graphs and a New Proof of a Theorem of Turán
• LMI Approximations for Cones of Positive Semidefinite Forms
• A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.

This page was built for publication: A PTAS for the minimization of polynomials of fixed degree over the simplex