On the complexity of optimization over the standard simplex

DOI10.1016/J.EJOR.2007.01.055zbMath1156.90009OpenAlexW2082724503MaRDI QIDQ932197

G. Elabwabi, Etienne de Klerk, Dick den Hertog

Publication date: 10 July 2008

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2007.01.055

zbMATH Keywords

global optimizationlinear programmingPTASstandard simplexmultivariate Lagrange interpolationmultivariate Bernstein approximation

Mathematics Subject Classification ID

Quadratic programming (90C20) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (11)

Numerical optimization and positivity certificates for polynomials and rationals over simplices ⋮ A numerical approach based on Bernstein collocation method: application to differential Lyapunov and Sylvester matrix equations ⋮ Convergence of the Simplicial Rational Bernstein Form ⋮ A reformulation-linearization technique for optimization over simplices ⋮ A refined error analysis for fixed-degree polynomial optimization over the simplex ⋮ The complexity of optimizing over a simplex, hypercube or sphere: a short survey ⋮ Matrix methods for the simplicial Bernstein representation and for the evaluation of multivariate polynomials ⋮ Convergence analysis for Lasserre's measure-based hierarchy of upper bounds for polynomial optimization ⋮ Rounding on the standard simplex: regular grids for global optimization ⋮ An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution ⋮ An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the convergence of derivatives of Bernstein approximation
• Bounding the Lebesgue function for Lagrange interpolatin in a simplex
• Inverse theorems for multidimensional Bernstein operators
• Structure preserving reductions among convex optimization problems
• Optimal approximation class for multivariate Bernstein operators
• Korovkin-type approximation theory and its applications
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• The complexity of approximating a nonlinear program
• Polynomial interpolation in several variables
• Geometry of interpolation sets in derivative free optimization
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• A Multivariate Form of Hardy's Inequality and $L_p$-Error Bounds for Multivariate Lagrange Interpolation Schemes
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• From Electrostatics to Almost Optimal Nodal Sets for Polynomial Interpolation in a Simplex
• On Multivariate Lagrange Interpolation
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Some optimal inapproximability results
• Global minimization of increasing positively homogeneous functions over the unit simplex

This page was built for publication: On the complexity of optimization over the standard simplex