The complexity of optimizing over a simplex, hypercube or sphere: a short survey

DOI10.1007/S10100-007-0052-9zbMath1152.90607OpenAlexW2114467398MaRDI QIDQ940826

Etienne de Klerk

Publication date: 3 September 2008

Published in: CEJOR. Central European Journal of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10100-007-0052-9

zbMATH Keywords

computational complexityglobal optimizationapproximation algorithmslinear and semidefinite programming

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30)

Related Items (35)

Quantum de Finetti theorems under local measurements with applications ⋮ Homogeneous polynomials and spurious local minima on the unit sphere ⋮ Inexact stabilized Benders' decomposition approaches with application to chance-constrained problems with finite support ⋮ Self-concordance is NP-hard ⋮ Approximation algorithms for homogeneous polynomial optimization with quadratic constraints ⋮ Improved approximation results on standard quartic polynomial optimization ⋮ Optimality conditions for homogeneous polynomial optimization on the unit sphere ⋮ Approximation algorithm for a class of global optimization problems ⋮ Convex optimization approach to a single quadratically constrained quadratic minimization problem ⋮ Convergence of the Simplicial Rational Bernstein Form ⋮ NP-hardness of deciding convexity of quartic polynomials and related problems ⋮ An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization ⋮ Copositive optimization -- recent developments and applications ⋮ Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization ⋮ Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems ⋮ Unnamed Item ⋮ On the computational complexity of membership problems for the completely positive cone and its dual ⋮ Sum-of-Squares Optimization without Semidefinite Programming ⋮ A Survey of Semidefinite Programming Approaches to the Generalized Problem of Moments and Their Error Analysis ⋮ A refined error analysis for fixed-degree polynomial optimization over the simplex ⋮ The sum-of-squares hierarchy on the sphere and applications in quantum information theory ⋮ A note on total degree polynomial optimization by Chebyshev grids ⋮ Rounding on the standard simplex: regular grids for global optimization ⋮ Separable standard quadratic optimization problems ⋮ On refinement of the unit simplex using regular simplices ⋮ Subperiodic Dubiner distance, norming meshes and trigonometric polynomial optimization ⋮ Approximating the existential theory of the reals ⋮ Approximating the existential theory of the reals ⋮ The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem ⋮ A generalization of the Motzkin-Straus theorem to hypergraphs ⋮ First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants ⋮ An active-set algorithmic framework for non-convex optimization problems over the simplex ⋮ Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies ⋮ An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution ⋮ Control analysis and design via randomised coordinate polynomial minimisation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of optimization over the standard simplex
• Structure preserving reductions among convex optimization problems
• Deterministic and stochastic error bounds in numerical analysis
• An exact duality theory for semidefinite programming and its complexity implications
• 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
• Convexity of quadratic transformations and its use in control and optimization
• Integration and optimization of multivariate polynomials by restriction onto a random subspace
• Optimal algorithms for global optimization in case of unknown Lipschitz constant
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
• 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
• Semidefinite relaxation and nonconvex quadratic optimization
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Some optimal inapproximability results
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• A Survey of the S-Lemma

This page was built for publication: The complexity of optimizing over a simplex, hypercube or sphere: a short survey