Complexity results for some global optimization problems

DOI10.1007/S10957-008-9448-5MaRDI QIDQ1024247zbMATHOpenAlexFDO

Authors Marco Locatelli

Publication date 16 June 2009

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10957-008-9448-5

zbMATH Keywords

global optimizationcomplexityseparable functionsapproximation problems

Mathematics Subject Classification ID

Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 3878714
• scientific article; zbMATH DE number 757674
• Algorithms and Computation
• Complexity and algorithms for nonlinear optimization problems
• On complexity of a global optimization problem

Cites work

• scientific article; zbMATH DE number 1559516 (Why is no real title available?)
• scientific article; zbMATH DE number 1560333 (Why is no real title available?)
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• Approximating quadratic programming with bound and quadratic constraints
• Approximation algorithms for indefinite quadratic programming
• Computational complexity of norm-maximization
• Geometric optimization problems likely not contained in \(\mathbb A\mathbb P\mathbb X\)
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Quadratic programming with one negative eigenvalue is NP-hard
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• The complexity of approximating a nonlinear program
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• \(NP\)-hardness of linear multiplicative programming and related problems

Cited in

(10)

• A class of increasing positively homogeneous functions for which global optimization problem is NP-hard
• scientific article; zbMATH DE number 1407504 (Why is no real title available?)
• On complexity of unconstrained hyperbolic 0--1 programming problems
• The complexity results of the sparse optimization problems and reverse convex optimization problems
• The complexity of optimization problems
• scientific article; zbMATH DE number 5233906 (Why is no real title available?)
• On the complexity of optimization over the standard simplex
• The complexity of optimizing over a simplex, hypercube or sphere: a short survey
• Studying the complexity of global verification for NP-hard discrete optimization problems
• On complexity of a global optimization problem

This page was built for publication: Complexity results for some global optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024247)